این نوشته کاربرد نوعی الگوریتم تکاملی موازی تعبیه شده در واحدهای پردازنده مرکزی و تراشههای شتابدهنده گرافیک بهمنظور مرتفعسازی و حل نمونههای بزرگ از مسئله OneMax با برخورداری از تعداد بیش از یک میلیارد متغیر را ارائه میدهد. در حقیقت، پلتفرمهای گرافیکی جدید از توان محاسباتی مورد نیاز جهت اعمال استراتژیهای موازی برای حل مسائل و مشکلات بزرگ بهرهمند میباشند. بر همین اساس گزارشی از ارزیابی تجربی فرآیند تعبیهسازی الگوریتم در واحدهای پردازنده مرکزی و تراشه شتابدهنده گرافیکی بهمنظور ارائه نوعی الگوریتم فشرده تکاملی در این نوشته گردآوری گشته است. روش ارائه شده نمایانگر تأثیری بالا در رفتار مقیاسپذیری الگوریتم هنگام رویارویی با ابعاد و زوایای مختلف نمونههای مسئله OneMax برخوردار از نویز و اثر عالی در حل مسائل میباشد که این خود منجر به بهبود راندمان محاسباتی و نتایج خروجی در مقایسه با گزارشات مبتنی بر رویههای مشابه پیشتر منتشر شده در حوزه واحد پردازنده مرکزی میشود.
مقدمه
الگوریتمهای تکاملی یا به عبارتی دیگر EA در حالت کلی نوعی از روشهای تصادفی بهمنظور حل و رفع مشکلاتی همچون بهینهسازیهای دشوار و طاقتفرسا، جستجو و یادگیری ماشینی میباشند که با موفقیت در طی بیست و پنج سال گذشته مورد استفاده قرار گرفته و سطح بالایی از تأثیر در بسیاری از زمینههای گوناگون را نیز تاکنون از خود نشان دادهاند. تا زمانی که توان محاسباتی قابل دسترسی در رایانههای مدرن و امروزی پیوسته رو به افزایش است، الگوریتمهای تکاملی بهمنظور رفع مشکلات بهینهسازی موجود با افزایش درجه سختی و پیچیدگی نیز تحت اعمال قرار میگیرند.
بهمنظور بهبود راندمان و بهرهوری الگوریتمهای تکاملی، قابلیتهای اجرای موازی در جهت افزایش چشمگیر میزان سرعت و بهسازی جستجو برای دستیابی به نتایج خروجی برخوردار از کیفیت بالا در مدت زمان معقول، حتی برای مسائل بهینهسازی بسیار مشکل مورد استفاده قرار گرفتهاند.
توانایی افزایش مقیاس جهت حل نمونه مسائل بسیار مشکل از جمله ویژگیهای بسیار مطلوب و پسندیده برای تکنیکهای بهینهسازی و بهخصوص الگوریتمهای تکاملی به شمار میرود. اگرچه، مقالات کمی قابلیت کاربرد استفاده از الگوریتمهای مذکور برای حل مسائل بسیار بزرگ (یک میلیون و یا تعداد بیشتری متغیر) را مورد مطالعه و بررسی قرار دادهاند (خلاصهای از اقدام مشابه را در بخش 3 مشاهده نمایید). امروزه پلتفرمهای محاسباتی جدید همچون واحدهای پردازنده مرکزی و گرافیکی برخوردار از تعداد چندین هسته پردازشی (مالتیکٌر) از قابلیت فراهم آوردن زیرساختی قابل دسترس برای اعمال رویههای موازیسازی عظیم با هدف طراحی الگوریتمهای تکاملی بهینه بهمنظور حل مسائل بزرگ و پیچیده برخوردار میباشند.
بنابراین، به لطف استفاده از توان محاسباتی سیستمهای موازی، مشارکت در حوزه فعلی با استفاده از مطالعه الگوریتمهای تکاملی مختلف بهمنظور فائق آمدن بر مسائل بسیار پیچیده و بزرگ بهینهسازی همچنان امکانپذیر است.
در حوزه جاری، مشارکت اصلی این مقاله عبارتاند از:
1) ارائه تجزیه و تحلیل عملکرد برای یک الگوریتم تکاملی کارآمد هنگام حل مسائل بهینهسازی بزرگ.
2) معرفی نوعی الگوریتم تکاملی موازی نوین برای استفاده مؤثر از توان محاسباتی عظیم موجود در تراشههای شتابدهنده گرافیکی.
3) انجام تجزیه و تحلیل تجربی بهمنظور نمایش تواناییهای تعبیهسازی و اعمال الگوریتمهای تکاملی موازی در واحدهای پردازنده مرکزی و گرافیکی جهت حل مشکلات بهینهسازی بسیار بزرگ و وسیع.
قدم اول در تحقیق ارائه شده، ابداع سرمشقهای بهخصوص برای طراحی الگوریتمهای تکاملی جهت حل سریع، قابل اطمینان و صحیح مسائل پیچیده و مشکل با استفاده از زیرساختهای سختافزاری پیشرفته و امروزی موجود در تمامی آزمایشگاههای تحقیقاتی و همچنین رایانههای شخصی میباشد.
مسائل OneMax و OneMax دارای نویز
بخش فعلی از نوشته به توصیف مسائل OneMax و OneMax دارای نویز استفاده شده جهت ارزیابی و سنجش الگوریتم تکاملی میپردازد.
مسئله OneMax
مسئله OneMax و یا شمارش بیت نوعی مسئله بهینهسازی ساده متشکل از ماکسیومسازی تعداد ارقام یک (1) موجود در یک رشته بیتی (باینری) میباشد. با توجه به دستهای از متغیرهای باینری ، مسئله OneMax بهوسیله رابطه زیر بیان میشود.
مسئله OneMax از ساختار فرمولی بسیار سادهای برخوردار است، اما این موضوع بهمنظور انجام تجزیه و تحلیلهای تجربی برای ارزیابی بهرهوری محاسباتی الگوریتمهای تکاملی سودمند میباشد. تابع سازگاری خطی مسئله OneMax به مدلسازی درجه پیچیدگی تابع ارزیابی مورد استفاده در بسیاری از مشکلات بهینهسازی ترکیبی سنتی میپردازد که این خود شامل:
مسائل مسیریابی و برنامهریزی مسیر، شامل چرخه همیلتون و مسئله فروشنده مسافر (TSP)، کوتاهترین مسیر و مسائل درخت پوشا.
مسائل نموداری و تنظیمی، شامل احاطهسازی و پارتیشنبندی، رنگآمیزی، تطابق و غیره.
مسائل زمانبندی، شمال توالی کار، برنامهریزی چند پردازندهای، Open-shop و flow-shop.
مسائل منطقی گزارهای، شامل مسئله رضایتمند (SAT) و تمامی موارد مشتق شده از آن.
مسئله OneMax دارای نویز
در یک مسئله بهینهسازی دارای نویز، تابع مورد استفاده جهت ارزیابی راهحلهای مختلف بهوسیله نویز برونزادی (خارجی) تحت تأثیر قرار میگیرد. در عمل، بسیاری از مسائل بهینهسازی دنیای واقعی توابع عینی که وضعیت عادی آنها توسط نویز تحت تغییر قرار میگیرند را مربوط میباشند.
یک تابع سازگاری دارای نویز در بطن یک الگوریتم تکاملی توسط رابطه معادله F (noisy) = f + N که در آن متغیر f نمایانگر سازگاری واقعی از یک راهحل و متغیر N نمایانگر میزان نویز خارجی (متغیری تصادفی که اغلب متناسب با میانگین صفر توزیع گاوسی تعریف میشود) میباشد مدل میشود.
تابع سازگاری برای مسئله OneMax دارای نویز بهوسیله معادله زیر تعریف میشود که عبارت N(0,σ^2N) نمایانگر یک متغیر گاوسی تصادفی با میانگین 0 و واریانس σ^2N است.
با شامل نمودن نویز خارجی در ارزیابی سازگاری، مسئله OneMax میتواند بهمنظور مدل نمودن مشکلات بهینهسازی برخوردار از محدودیتها و دیگر ویژگیهای مختلف مورد استفاده قرار گیرد.
محاسبات تکاملی
این بخش به معرفی الگوریتمهای تکاملی و الگوریتم ژنتیک فشرده میپردازد.
الگوریتمهای تکاملی
الگوریتمهای تکاملی بهطور کلی در قالب روشهای غیرقطعی طبقهبندی میگردند که به تقلید و شبیهسازی تکامل گونههای مختلف در طبیعت پرداخته و تاکنون بهمنظور حل مشکلات بهینهسازی موجود در زیرساخت بسیاری از کاربردهای زندگی حقیقی در بیست و پنج سال گذشته با موفقیت مورد اعمال و استفاده قرار گرفتهاند.
یک EA نوعی تکنیک تکراری محسوب میگردد که به اعمال عملگرهای تصادفی بر جمعیتی از اشخاص گوناگون جهت رمزگذاری راهحلهای پیشبینی شده مسئله بهمنظور بهبود سازگاری آنها میپردازد. یک تابع ارزیابی بهطور کلی یک مقدار سازگاری را بهتمامی اشخاص حاضر جهت نمایش مناسب بودن آنها به مسئله منتسب مینماید. بزرگی جمعیت اولیه بهطور تصادفی و یا بهوسیله استفاده از یک متغیر ابتکاری بهخصوص برای مسئله ایجاد میشود. بر همین اساس بهطور منظم و تکراری، کاربرد احتمالی ترکیب مجدد اشخاص و یا ایجاد تغییرات (جهش) تصادفی در محتویات آنها با استفاده از انتخاب تکنیک موجود منجر به هدایت الگوریتم تکاملی به سمت پاسخها و راهحلهای بهتر و بهینهتر میشود.
ملاک توقف اغلب شامل مواردی همچون تعداد ثابت تولیدات و یا سپری گشتن مدت زمان انجام اعمال، دستیابی به حد آستانهای با کیفیت بر روی بهترین مقدار سازگاری و یا شناسایی یک حالت رکود میباشد. قوانین ویژه و بهخصوص جهت انتخاب اشخاص برای ترکیب مجدد و تعیین اشخاص جایگزین موارد قدیمی در نسول جدید مورد استفاده قرار گرفتهاند. بر همین اساس الگوریتم تکاملی بهترین راهحل یافت شده را با توجه به مقادیر تابع سازگاری باز میگرداند.
الگوریتم ژنتیک فشرده
الگوریتم ژنتیک فشرده (cGA) نوعی الگوریتم تکاملی میباشد که فاکتور جمعیت را بهعنوان یک توزیع احتمال در سرتاسر راهحلهای موجود جهت استفاده بهینه از میزان حافظه در دسترس بیان میدارد. از دیدگاه الگوریتم، cGA مشابه با یک GA (الگوریتم ژنتیک) معمولی است که به استفاده از پارامترهای کروموزومی یکپارچه و عملگرهای جهشی حرکت زیگزاگی بیتها مبادرت میورزد. هر کدام از عناصر موجود در بردار احتمال نمایانگر بخشی از مقدار داده شده (بهعنوان مثال ارقام یک) در هر موقعیت ژن میباشد. ازآنجاییکه مقدار جمعیت بهصراحت ذخیره نگشته و هر کدام از ژنها بهصورت مجزا مورد پردازش قرار میگیرند، میزان قابل توجهی از حافظه هنگام استفاده از روش فعلی در مقایسه با دیگر الگوریتمهای ژنتیک سنتی تحت صرفهجویی قرار میگیرد.
فازهای موجود در الگوریتم ژنتیک فشرده (cGA) عبارتنداز:
1) مقداردهی اولیه: مقدار اولیه ورودیهای موجود در بردار احتمال برابر با 0.5 تنظیم میگردند؛
2) نمونهبرداری مدل: تولید دو پاسخ داوطلبگونه بهوسیله نمونهبرداری بردار احتمال؛
3) ارزیابی: سازگاری اشخاص انتخاب شده مورد محاسبه قرار میگیرد؛
4) انتخاب: عملگر انتخاب رقابت بهمنظور اطمینان از انتخاب بهترین شخص جهت گسترش مشخصات خود اعمال میشود؛
5) بهروزرسانی مدل احتمالی: پس از انتخاب بهترین شخص، تناسب آللهای در حال پیروزی، به توجه به رابطه موجود در معادله زیر بهاندازه 1/n گسترش یافته است.
الگوریتمهای تکاملی موازی
فرآیند تعبیهسازی موازی بهعنوان تلاشی برای بهبود راندمان الگوریتمهای تکاملی در یک دهه گذشته از محبوبیت برخوردار گشتند. الگوریتمهای تکاملی موازی (PEA) با استفاده از شکستن جمعیت موجود به چندین عناصر پردازشی، امکان دستیابی به نتایج پر کیفیت در مدت زمان مناسب و معقول، حتی برای مسائل بهینهسازی مشکل را فراهم میآورند.
الگوریتمهای تکاملی موازی ارائه شده در این نوشته در قالب مدل ارباب-برده طبقهبندی گشتهاند: یک فرآیند ارباب هنگامیکه مجموعهای از فرآیندهای برده به انجام جستجوی توابع محاسباتی غنی در حالت موازی میپردازند به هدایت و پیشبرد عملیات تکامل مبادرت میورزد.
اقدامات مشابه
شخص Deb et al اولین اقدام به حل مسائل بهینهسازی مبتنی بر تعداد بیش از یک میلیون متغیر بهوسیله الگوریتمهای تکاملی را ارائه داد. گروه وی نشان داد که استفاده از روش سنتی الگوریتم ژنتیک (GA) بهمنظور حل مسائل بسیار بزرگ و عظیم نمیتواند مفید واقع شده، زیرا مدت زمان مورد نیاز جهت اجرای آن بسیار زیاد میباشد. الگوریتم تکاملی (EA) ارائه شده توسط Deb و Pal راهحلهای نزدیک به حالت بهینه و مطلوب برای مسئلهای با برخورداری از 100 هزار متغیر را در کمتر از چند دقیقه به انجام رساند، اما هنگام رویارویی با نمونهای مبتنی بر تعداد یک میلیون متغیر بیش از 10 ساعت به طول انجامید. اشخاص Semet و Schoenauer با ارائه نوعی الگوریتم تکاملی ویژه موفق به حل نمونهای حقیقی از مسئله زمانبندی قطارگونه عظیم با برخورداری از تعداد بیش از یک میلیون متغیر و دو میلیون محدودیت شدند. الگوریتم معرفی شده جهت ارائه پاسخ برای تعداد 20 نسل مختلف تا قبل از همگرایی پیش از موعد مدت زمانی برابر با 15 دقیقه به طول انجامید، لذا بهمنظور تولید نتایج بهتر، الگوریتم مربوط با نرمافزار بهینهسازی CPLEX پیوند خورد، اما با این وجود همچنان 4 ساعت زمان جهت انجام محاسبات نیاز بود. کاربرد رویکردهای پیشین برای حل مسائل بهینهسازی عمومی محدود میباشند، زیرا اغلب آنها به استفاده از عملگرهای مجزا و مختص به مسئله و جمعیتهایی با اندازه کوچک میپردازند که این خود منجر به همگرایی زودرس و پیش از موعد میگردد.
نظر به پیشنهادات عمومیتر، شخص Kunasol et. al مسائل مبتنی بر تعداد یک میلیون بیت را با رویکرد اعمال یک الگوریتم ژنتیک و یک فرآیند کاهش فضای جستجو به حل رساند. ارزیابی تجربی موفق به یافتن پاسخ مسائلی همچون OneMax، جاده سلطنتی و تله شد، ازآنجاییکه فرآیند کاهش فضا در روش اعمال شده بود، الگوریتم تکاملی در واقعیت در رویارویی با مسائل مبتنی بر تعداد یک میلیون متغیر قرار نگرفته بود.
در سال 2007، شخص Goldberg et al با استفاده از نوعی تعبیهسازی موازی الگوریتم ژنتیک فشرده که قادر به ” حل مسائل حاضر در مقیاس عظیم با برخورداری از تعداد بیش از 32 میلیون متغیر تا همگرایی کامل” بود به رویارویی با مسئله OneMax پرداخت. چندین تغییر مختلف جهت افزایش میزان راندمان در بطن الگوریتم اعمال گشتند، اما cGA مربوطه همچنان نیازمند زیرساخت محاسبات موازی بسیار عظیم بوده و خواستار چندین ساعت زمان جهت اجرای تنها یک روند بود که علت اصلی این امر به جمعیت بسیار بزرگ مدل شده (بیش از تعداد یک میلیون فرد که مطابق با یک مدل Gambler Ruin سایزبندی گشتهاند) مربوط بوده است. هنگام رویارویی با مسئله مبتنی بر تعداد یک میلیارد متغیر، حتی با وجود استفاده از یک سرور خوشهای بزرگ با برخورداری از تعداد 256 پردازشگر، مؤلفان نیازمند کاهش ضابطه توقف بهنوعی “همگرایی آرام” بسیار ضعیف (بهعنوان مثال مقدار احتمال هر متغیر برابر با 0.501 میباشد) بودند که این خود در واقعیت بدان معنی است که الگوریتم cGA از احتمالی بسیار اندک در نمونهبرداری راهحل مناسب و معقول برخوردار است.
اشخاص Sunwannik و Chongstitvatana برآوردی از الگوریتم توزیع (EDA) با برخورداری از نحوه کد نویسی فشرده بهمنظور حل مسئله OneMax دارای نویز مبتنی بر تعداد یک میلیون متغیر را اعمال کردند. جمعیتی بهاندازه 3200 نفر در این آزمایش مورد استفاده قرار گرفته بود که در مقایسه با نمونه تلاش شده توسط مؤلف Goldberg et al بسیار کوچکتر میباشد. الگوریتم EDA پیشنهاد شده در هنگام حل مسئله OneMax نیازمند 16 ساعت زمان جهت بررسی تعداد 100 نسل مختلف بود که این مقدار در هنگام بررسی مسئله OneMax دارای نویز به تقریباً 34 ساعت افزایش پیدا کرد.
اقدامات مشابه صورت گرفته در این حوزه حکایت از این موضوع دارند که تعداد کمی از مقالات گزارش شده موفق به فائق آمدن بر مسائل بهینهسازی بسیار بزرگ با استفاده از الگوریتمهای تکاملی (EA) گشته و پیشنهادات ارائه شده در حوزه محاسبات از راندمان بالایی برخوردار نیستند. در این مقاله، ما بهمنظور تجزیه و تحلیل پتانسیل به ارمغان آورده شده توسط پلتفرمهای محاسباتی چند رشتهای نوین (پردازندههای مرکزی و تراشههای شتابدهنده گرافیکی چند هستهای) جهت گسترش قابلیتهای حل مسائل بهینهسازی بسیار عظیم با بهرهوری بالا به اتخاذ الگوریتم ژنتیک فشرده (cGA) پیشتر استفاده شده توسط مؤلف Goldberg et al پرداختهایم.
رفع مشکلات بهینهسازی بسیار بزرگ با نوعی الگوریتم تکاملی موازی در CPU و GPU
دانلود آخرین ورژن برنامه