دانلود مقاله عملگرهای الگوریتم ژنتیک و الگوریتم های فراابتکاری

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

به طور موردی در زمینه مقایسه کاربردی الگوریتم های فراابتکاری تحقیقاتی به عمل آمده است. اما همین موردی بودن آنها، نشان دهنده توانایی نسبی الگوریتمهای فراابتکاری در حل مسائل است. ابزار و مکانیزمهایی که در سال های اخیر و به مدد ابداع الگوریتمهای فراابتکاری به وجود آمده اند، کمک شایانی در حل مسائل بهینه سازی کرده اند. به طوری که شاید بتوان گفت، قدرتمندترین روشها برای حل مسائل بهینه سازی پیچیده، الگوریتم های فراابتکاری میباشند. اگرچه روشهای فراابتکاری قابلیت تضمین بهینه سراسری بودن پاسخی را که ارائه میدهند ندارند، با این اوصاف، روش های تحلیلی نیز که بهینه بودن پاسخ را تضمین میکنند در حل مسائل پیچیده ناتوانند. علاوه بر این، برخی روشهای تحلیلی نیز ابداع شده اند که از رویههای فراابتکاری در آنها کمک گرفته شده است و قابلیت دست یافتن به بهینه سراسری را در برخی مسائل بهینه سازی پیچیده دارند، که این امر به نوبه خود نشان دهنده اهمیت روشهای فراابتکاری است.


در پایان این بخش به معرفی تعدادی از مهم ترین الگوریتمهای فراابتکاری میپردازیم و نحوه کارکرد آنها را به طور خلاصه شرح میدهیم.
2-5-4-1. الگوریتم ژنتیک (GA)
الگوریتم ژنتیک (GA) یک تکنیک جستجو در علم رایانه برای یافتن راه حل بهینه و مسائل جستجو است. الگوریتم‌های ژنتیک یکی از انواع الگوریتم‌های تکاملی‌اند که از علم زیست‌شناسی مثل وراثت، جهش، انتخاب ناگهانی(زیست‌شناسی)، انتخاب طبیعی و ترکیب الهام گرفته شداند.
به عبارتی دیگر الگوریتم ژنتیک روشی است برای حرکت از جمعیتی از «کروموزوم ها»( به طور مثال آرایه ای از مقادیر 0 و 1 یا چند «بیت») به جمعیتی دیگر با استفاده از نوعی «انتخاب طبیعی» و عملگرهای الگوریتم ژنتیک مانند تقاطع، جهش و معکوس سازی هر کروموزوم از تعدادی «ژن» تشکیل شده است (به طور مثال چند بیت). هر ژن نشان دهنده یک مقدار است (به طور مثال 0 یا 1). عملگرهای انتخاب آن کروموزوم هایی را که اجازه تولید نسل دارند انتخاب می کنند و به طور متوسط، کرورموزومهایی که درجه انطباق بالاتری دارند، تعداد فرزندان بیشتری نسبت به آنهایی که درجه انطباق کمتری دارند تولید میکنند. عملگر تقاطع، بخش هایی از دو کروموزوم را با یکدیگر تعویض میکند که به نوعی تقلیدی از عملیات ترکیب کروموزومها در فرآیند تولید مثل است. عملگر جهش، مقادیر دو بخش از یک کروموزوم را با یکدیگر عوض میکند و عملگر معکوس سازی، ترتیب قرار گیری ژنها در کروموزوم را برعکس میکند. [50]
با توجه به توضیحاتی که داده شد، الگوریتم ژنتیک را می توان به طور خلاصه (برای حل یک مسئله بهینه سازی) به صورت نمودار (2-2) نمایش و تشریح کرد.
نمودار 2-2 مراحل اجرای الگوریتم ژنتیک
– جمعیت اولیهای از کروموزوم‌ها انتخاب کنید.
– تا هنگامی که شرایط پایان حاصل نشده عملیات زیر را انجام دهید :
– تا زمانی که فرزندان کافی درست نشده باشد تکرار کنید.
– اگر شرایط تقاطع حاصل شد آنگاه {کروموزومهای والد را انتخاب کنید پارامترهای تقاطع را انتخاب کنید تقاطع را انجام دهید}.
– اگر شرایط جهش حاصل شده آنگاه: {تقاطع جهش را انتخاب کنید جهش را انجام دهید}.
– درجه تطابق فرزندان را ارزیابی کنید.
– جمعیت جدیدی انتخاب کنید.
– پایان.
الگوریتم DE الگوریتم دیگری است که مشابه الگوریتم ژنتیک، مبتنی بر جمعیت بوده و از عملگرهای جهش و تقاطع استفاده میکند. تفاوت اصلی GA و DE تولید جوابهای بهتر در این است که در GA متکی بر تقاطع است، ولی در DE متکی به عمل جهش است [51].
2-5-4-2. الگوریتم شبیه سازی تبریدی (SA)
الگوریتم تبرید شبیه‌سازی شده (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی است. منشأ الگوریتم تبرید شبیه‌سازی شده، کارهای کریک پاتریک و کرنی و همکارانشان در سال‌های ۱۹۸۳ و ۱۹۸۵ است. کریک پاتریک و همکارانش، متخصصانی در زمینه فیزیک آماری بودند. آنها برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی پیشنهاد نمودند. تکنیک تبرید تدریجی، به وسیله متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده می‌شود. این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. الگوریتم تبرید شبیه‌سازی شده به علت تشابهش و الگو گیری آن از مکانیک آماری و فرآیند پخت فلزات که در آن کریستال یک جامد حرارت داده و به آرامی سرد میشود تا بهترین شکل جایابی بلوری را پیدا کند، به این نام شناخته میشود. روش بهینه سازی SA به این ترتیب است که با شروع از یک جواب اولیه تصادفی برای متغیرهای تصمیم‌گیری، جواب جدید در مجاورت جواب قبلی با استفاده از یک ساختار همسایگی مناسب به طور تصادفی تولید می‌شود. بنابراین، یکی از مسائل مهم در SA روش تولید همسایگی است. الگوریتم در هر گام، دو مقدار را برای پاسخها به دست میدهد (پاسخ فعلی و پاسخ انتخابی جدید) و آنها را با هم مقایسه میکند. پاسخهای بهتر همیشه پذیرفته شود، اما پاسخهای بدتر با احتمالی برای فرار از بهینه محلی پذیرفته میشوند.
برای تعریف خصوصیات نیاز به چند تعریف داریم. را فضای جواب در بگیرید. را تابع هدف قرار دهید. هدف یافتن بهینه سراسری (یعنی که در آن به ازای تمام ) است. را به عنوان تابع همسایگی تعریف می کنیم. بنابراین، هر پاسخ دارای همسایه هایی است که از طریق یک حرکت قابل تبدیل به یکدیگر هستند.
SAبا یک پاسخ اولیه شروع میکند. سپس یک پاسخ همسایه تولید میکند. جواب که همسایه است، بر اساس احتمال زیر پذیرفته میشود.
به عنوان پارامتر دما در گام kام انتخاب میشود، طوری که :
یکی از خصوصیات بارز SA ساده بودن آن است. اما با این اوصاف از زمان ابداع آن تا کنون روش های بسیاری برای بهبود عملکرد آن به کار رفته است .
2-5-4-3. الگوریتم جستجوی ممنوعه (TS)
جستجوی ممنوع (TS) در سال 1986 توسط فرد گلاور به عنوان یک الگوریتم فراابتکاری برای حل مسائل بهینه سازی ترکیبی معرفی شد [52]. TS در اصل روشی بود که برای فائق آمدن بر ضعف روشهای جستجوی محلی (LS) و الگوریتم های ابتکاری طراحی شد و میتوان آن را به نوعی ادامه و تعمیم الگوریتمهای LS به شمار آورد[53] . پایهای ترین و مهم ترین مفاهیم TS شامل دو عنصر «فضای جستجو»و «ساختار همسایگی» میشود.