الگوریتم های فراابتکاری و تبرید شبیه سازی شده

دانلود پایان نامه

الگوریتمهای فراابتکاری نسل جدیدی از الگوریتمهای تقریبی بر مبنای بکارگیری روشهای ابتکاری برگرفته از رویکردهای جستجوی موضعی و ساختاری به منظور جستجوی کارا و اثربخش فضای جستجو میباشند. از مهمترین ویژگیهای الگوریتمهای فراابتکاری بکارگیری استراتژیهای جستجوی منحصر به فرد به منظور اجتناب از قرارگیری در دام جوابهای بهینه موضعی میباشد. تکنیکهای موجود در این الگوریتمها دامنهی گستردهای داشته و میتواند شامل رویکردهای جستجوی محلی ساده یا فرآیندهای یادگیری پیچیده باشد. بدین ترتیب با در نظر گرفتن فلسفه بکاررفته در استراتژی های جستجو، الگوریتم های فراابتکاری گوناگونی همچون الگوریتم کلونی مورچگان، بهینه سازی ازدحام ذرات، تبرید شبیه سازی شده، جستجوی ممنوع و غیره بوجود آمدند.
در زمان بندی تک هدفه، الگوریتم های حل پس از طی مراحل دستیابی به جواب، بهترین حل را در راستای تابع هدف موردنظر ارائه میدهند. در دنیای مسائل چند هدفه نیز ممکن است با اولویت دهی به توابع هدف و ترکیب آنها به منظور داشتن فقط یک تابع هدف، الگوریتم حل در هر لحظه در راستای تنها یک تابع هدف پیش برود. این امر اگرچه روال حل را سادهتر مینماید، ولی با بسیاری از مسائل دنیای واقعی سازگاری ندارد، چرا که اغلب تصمیم گیرندگان نمیتوانند بصورت دقیق اولویت و یا وزن هر تابع هدف را از پیش مشخص کنند. در چنین مواردی ترجیح داده میشود که به جای تمامی حلهای ممکن یک مسئله، تعداد محدودی حل پیشروی تصمیم گیرنده قرار گیرد. همان طور که قبلاً گفته شد این حل ها به گونه ای هستند که هیچ یک بر دیگری برتری ندارند و هر یک از آن ها می توانند به عنوان حل نهایی مسئله انتخاب شوند. چنین مجموعه ای از حل ها را مجموعه پارتو می نامند که از اهمیت ویژه ای برخوردار می باشند.
الگوریتم هایی که برای یافتن نقاط پارتو استفاده میشوند ممکن است با یک جواب اولیه شروع شوند و در هر تکرار بهبودی در جواب حاصل کنند مانند الگوریتم شبیه سازی تبرید چند هدفه و یا ممکن است الگوریتم هایی جمعیت محور باشند و با مجموعهای از حل های اولیه آغاز شوند مانند نسخههای چند هدفه الگوریتم ژنتیک، الگوریتم کلونی مورچگان و غیره. در بخش های آتی این فصل ابتدا به تشریح مبانی الگوریتم ژنتیک و نسخه ی چند هدفه آن یعنی الگوریتم NSGA- و در ادامه به تشریح الگوریتم کلونی مورچگان و نسخه ی چند هدفه آن یعنی الگوریتم MOACO میپردازیم.
4-2- الگوریتم ژنتیک
طبیعت همواره بزرگترین و بهترین معلم انسانها بوده است. بشر با الهام از طبیعت دست به ساخت وسائل و ارائه روشهایی زده است، که نتیجه آن در سالهای اخیر ارائه الگوریتم های فراابتکاری متنوع برای حل مسائل بهینه سازی ترکیبی میباشد. در میان روشهای بهینهسازی الهام گرفته از طبیعت، الگوریتم ژنتیک یکی از اولین و تکامل یافتهترین روشها به شمار میرود.
در طبیعت افراد جامعه برای دستیابی به منابعی از قبیل غذا، آب و سرپناه با یکدیگر رقابت میکنند. در این بین افرادی که به منابع بیشتری دست یابند، امکان بیشتری برای بقا نسبت به سایر افراد برای خود ایجاد کردهاند و با تولید نسل بیشتر نسبت به افراد ضعیف، نمایندگان بیشتری نسبت به سایر افراد در نسلهای بعدی خواهند داشت. دسترسی به منابع بیشتر بیانگر توانایی بیشتر این افراد نسبت به سایرین در سازگاری با شرایط محیط زندگی میباشد. همچنین با پیوند دو فرد که دارای توانایی بالایی میباشند، فرزندانی تولید خواهند شد که به احتمال زیاد نسبت به والدین خود دارای تواناییهای بیشتری جهت سازگاری با محیط زندگی میباشند. با الهام از چنین مفهومی الگوریتم ژنتیک ارائه گردیده است و با توجه به تواناییهای بالای این روش در بسیاری از شاخهها و گرایشهای کاربردی مورد استفاده قرار گرفته است.
ایده اولیه این روش از نظریه تکامل داروین الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار میباشد. اصول اولیه الگوریتم ژنتیک اولین بار توسط هالند [73] و همکارانش در دانشگاه میشیگان در سال 1962 ارائه شد. آنان در تحقیقاتشان دو هدف اصلی زیر را دنبال میکردند:
1) ارائه شرح دقیق و خلاصهای از عملکرد قابل قبولی از سامانههای طبیعی.
2) طراحی نرم افزارهای سامانههای ساختگی که ساز و کارهای اصلی سامانههای طبیعی را در بر داشته باشد.
نتیجه این تلاشها، پیداش الگوریتم ژنتیک بود. سپس در سال 1975، مبانی ریاضی آن توسط هالند[73] منتشر شد و در سال 1990 آرت و همکاران[74] همگرائی الگوریتم ژنتیک را با استفاده از روش آنالیز زنجیره مارکوف به اثبات رساندند. الگوریتم ژنتیک در واقع تلاشی برای شبیه سازی برخی از خصوصیت های تکامل و تغییرات کروموزومهای ارگانیسم های زنده است که همواره در طبیعت صورت می گیرد. به عبارت دیگر این الگوریتم تلاش می کند با وراثت و جهش طی نسل های متوالی، عملکرد مطلوبی را در اعضای یک جامعه از کروموزوم ها ایجاد کند. این کار از طریق ایجاد یک جامعه اولیه و فراهم آوردن شرایط تکامل در نسل های بعدی صورت می گیرد.
در الگوریتم ژنتیک هر جواب بصورت یک رشته از کدها بیان میشود که آن را اصطلاحاً کروموزوم می نامند. هر کروموزوم متناظر با یک جواب از مجموعه جواب های مسئله می باشد. جواب متناظر با هر کروموزوم را برازندگی آن کروموزوم می نامند. عناصر تشکیل دهنده رشته کروموزوم که معمولاً اعداد هستند را ژن میگویند. برای شروع حل، الگوریتم نیاز به مجموعه ای از کروموزوم ها دارد. این مجموعه از کروموزوم ها را یک جامعه می نامند و به هر تکرار از الگوریتم یک نسل گفته میشود.
الگوریتم ژنتیک کار خود را با جامعهای از جواب ها که از طریق یک فرآیند تصادفی ایجاد شده اند، آغاز می کند. جامعه جواب ها توسط یک تابع برازش ارزیابی میشوند. هر بار که ارزیابی اعضای جامعه صورت می پذیرد، تعدادی از آن ها با توجه به میزان برازش محاسبه شده به عنوان والدین انتخاب میشوند. به طور طبیعی اعضایی که میزان برازش بیشتری دارند از احتمال بیشتری برای انتخاب برخوردارند. با بکارگیری عملیات ژنتیک بر روی والدین، جمعیت فرزندان تولید می شوند و پس از آن از میان جمعیت فعلی و جمعیت فرزندان جامعهی جدیدی تولید میشود. تا این مرحله الگوریتم یک تکرار یا یک نسل را طی نموده است و پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا خواهد شد.
از آنجاییکه مسئله مورد بررسی در این تحقیق از نوع دو هدفه می باشد از این رو ما نیاز به نسخههای چند هدفه این الگوریتم برای حل مسئله مورد نظر داریم. تا به امروز نسخههای مختلفی از الگوریتم ژنتیک چند هدفه مبتنی بر مفهوم پارتو توسط محققین مختلف معرفی شده اند، از قبیل الگوریتم ژنتیک چند هدفه [75]، الگوریتم ژنتیک مبتنی بر مرتب سازی نامغلوب [76]، الگوریتم ژنتیک مبتنی بر مرتب سازی نامغلوب ورژن دوم [77]، الگوریتم ژنتیک مبتنی بر پارتو در جایگاه ویژه [78]، الگوریتم تکاملی مبتنی بر قوت پارتو [79]، الگوریتم تکاملی مبتنی بر قوت پارتو ورژن دوم [80] و الگوریتم NRGA [81] که الگوریتمی منطبق بر NSGA- و تنها تفاوت آن در استراتژی انتخاب والدین میباشد. در این پژوهش از الگوریتم ژنتیک برمبنای مرتب سازی نامغلوب ورژن دوم استفاده شده است که در ادامه به توضیح بیشتر آن میپردازیم.
.
4-2-1- الگوریتم ژنتیک بر مبنای مرتب سازی نامغلوب (NSGA-)
در زمینه الگوریتمهای تکاملی، (NSGA-) یکی از معروفترین و موثرترین الگوریتمهای تکاملی چند هدفه میباشد که توسط دب و همکارانش [77] در سال 2002 میلادی معرفی شده است. این الگوریتم با بکارگیری یک جمعیت اولیه و بر مبنای مفهوم غلبه می تواند تقریب خوبی از لبه ی پارتو بهینه بدست آورد. دو عملگر مهم این الگوریتم که بطور گستردهای توسط محققین مورد استفاده قرار گرفته است رتبهبندی نامغلوب سریع و فاصله ازدحامی می باشند. عملگر رتبه بندی جمعیت کروموزوم ها را به لبه های مختلفی تقسیم بندی می کند و عملگر فاصله ازدحامی میزان پراکندگی پاسخ ها را روی هر لبه محاسبه میکند و همچنین باعث حفظ گوناگونی در مسئله میشود.
در شروع الگوریتم، یک جمعیت اولیه به اندازه بصورت تصادفی ایجاد میشود. تمام اعضای با استفاه از الگوریتم رتبه بندی نامغلوب و رویه فاصله ازدحامی مرتب میشوند. در ادامه تعدادی از والدین که از طریق یک رقابت انتخاب میشوند با استفاده از عملگرهای جهش و تقاطع جمعیت فرزندان که معمولاً شامل عضو می باشد را ایجاد میکنند. در ادامه با ترکیب جمعیت اولیه و جمعیت فرزندان، جمعیت ترکیبی به اندازه ایجاد میشود. این رویه با رتبه بندی جمعیت ترکیبی و ایجاد لبه های مختلفی که هر کدام شامل تعدادی حل نامغلوب هستند و همچنین محاسبه فاصله ازدحامی حلهای موجود در هرلبه ادامه مییابد. نسل بعدی والدین به اندازه از طریق انتخاب بهترینهای نسل قبل بر اساس رتبه و فاصله ازدحامی آنها تشکیل میشود. الگوریتم تا رسیدن به معیار توقف ادامه مییابد. پیکر بندی الگوریتم پیشنهادی NSGA- شامل مراحل زیر میباشد :
4-2-1-1- نمایش کروموزومی مسئله
اولین گام در بکارگیری الگوریتم NSGA- کدگذاری و نمایش جوابهای مسئله بصورت یک کروموزوم است. انتخاب ساختار مناسب برای کدگذاری جواب ها موجب ساده سازی و کاهش زمان محاسباتی عملیات صورت گرفته در طول اجرای الگوریتم میشود. همچنین قابل فهم بودن و تطابق با مسئله از ویژگیهای یک کروموزوم کارا میباشد. هر کروموزوم غالباً بوسیله رشتهای از اعداد نمایش داده میشود، بطوریکه هر کدام از عناصر این رشته با قسمتی از یک جواب متناظر است. در هنگام کدگذاری جواب ها به طور طبیعی دو مفهوم اساسی بروز می نماید، یکی موجه بودن کروموزومها که در ارتباط با ارضای محدودیتهای مسئله میباشد و دیگری قانونمندی کروموزومها که مربوط به حالتی است که ممکن است عملیاتهای ژنتیک کروموزومی را تولید نمایند که با هیچ جوابی از فضای جواب متناظر نباشد.
در یک مسئله زمانبندی، یک کروموزوم میبایستی همزمان نشان دهنده تخصیص کارها به ماشینها و توالی کارهای اختصاص یافته به هر ماشین باشد. معمولاً نمایش کروموزومی برای مسائل زمانبندی ماشینهای موازی بصورت یک رشته که شامل ژن است، میباشد. اعضای این رشته شامل جایگشتی از اعداد یک تا می باشند بطوریکه ژن مازاد بعنوان جداکننده کارها و تخصیص آنها روی ماشینهای مختلف عمل میکنند. اما از آنجاییکه که در این پایان نامه محدودیتهای دسترسی محدود به ماشینها در نظر گرفته شده است از این رو دیگر نمیتوان از نمایش کروموزومی یاد شده استفاده نمود. نمایش کروموزومی مناسب برای مسئله مورد بررسی در این تحقیق بصورت یک آرایه دو بعدی میباشد که تعداد سطرهای این آرایه برابر دو و تعداد ستونهای آن برابر تعداد کارهای موجود در مساله میباشد، بطوریکه در سطر اول، شماره کارها ظاهر میشود و در سطر دوم و زیر هر کار شماره ماشین اختصاص یافته به آن قرار میگیرد. در شکل (4-1) مثالی از کروموزومی که (با 10 کار و 3 ماشین) در این تحقیق مورد استفاده قرار گرفته است نمایش داده شده است :
توالی کارها بر روی ماشین ها :
ماشین 1 : 9-10-6-1