الگوریتم ممتیک مبتنی بر آزادگی برای حل مسئله QAP

معرفی پایان نامه: الگوریتم ممتیک مبتنی بر آزادگی برای حل مسئله QAP

این پایان نامه کارشناسی ارشد در سال 2012 توسط Francesco Puglierin  در دانشگاه Utrecht هلند دفاع شده است. در این پایان نامه مسئله QAP به کمک یک الگوریتم فراابتکاری جدید که BIMP-QAP نامگذاری شده است حل شده است. این الگوریتم از ساختار ممتیک استفاده کرده است که به جای استفاده از الگوریتم ژنتیک برای بدست آوردن نسل های بعدی از یک عملگر جدید بنام Perturb() برای تغییر راه حل ها استفاده می کند. در این روش اطلاعات را روی مولفه های منفرد از طریق جستجو ذخیره می کند. این اطلاعات از طریق عملگرPerturb() که الهام گرفته شده از راه حل های مدل راهزنی چند سلاحی (multi-Armed Bandit Model) به جستجو کمک می کند. کارائی و همگرائی BIMP-QAP بیشتر از Multi-Start Local Search می باشد. همچنین عملگر جدید Perturb() نسبت به دیدگاه های تصادفی راه حل های فعلی را  به راه حل های بهتری تغییر می دهد.

در این روش مولفه ها با بالاترین رتبه راه حل، روی راه حل اصلی اجرا می شوند. میزان رتبه با فرمول های الهام گرفته شده از مدل راهزنی چند سلاحی و UCB به طور ویژه محاسبه می شود. این فرمول دو واژه ذیل را با هم ترکیب می کند:

اولی واژه Exploitation(استخراج یا بهره وری) : یعنی بدست آوردن پاسخ های بهتر حول یک پاسخ و جستجوی محلی می باشد. این کار را به کمک تخمین حدسی کیفیت یک مولفه را تضمین می کند. دومی واژه Exploration  ( اکتشاف ) : یعنی سراسری بودن جستجو برای رسیدن به کیفیت سراسری مولفه ها می باشد.

پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

این پایان نامه در سال 2011 با موضوع " پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE" توسط کارل دورکوتا از دانشگاه Czech پاراگوئه نگارش شده است. در ادامه مفاهیم و راهکارهای پیشنهادی مورد بررسی قرار گرفته شده است.

الگوریتم کرم شب تاب:

الگوریتم کرم شب تاب (FA) در سال 2008 توسط یانگ که از الگوریتم های طبیعت الهام گرفته شده است، معرفی شده است. این الگوریتم از رفتار "حشره" کرم شب تاب که شامل انتشار نور، جذب نور و جذب متقابل بهره می گیرد. این الگوریتم برای حل مسائل بهینه سازی پیوسته توسعه یافته است. شبه کد الگوریتم کرم شب تاب در شکل 1 نشان داده شده است.

مقاله: بهینه سازی ازدحام ذرات ممتیکی (Memetic-PSO)

مقاله: بهینه سازی ازدحام ذرات ممتیکی (Memetic-PSO)

این مقاله توسط  Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis  در سال 2007 در Springer به چاپ رسیده است. در این مقاله یک بهینه سازی ازدحام ذرات ممتیکی پیشنهاد شده است که ترکیبی از الگوریتم های جستجوی محلی با الگوریتم بهینه سازی ازدحام ذرات استاندارد می باشد. به همین دلیل یک روش بهینه سازی کارآمد و موثر خواهد بود که البته از نظر عملی مورد تحلیل قرار می گیرد.

کارائی الگوریتم های مبتنی بر جمعیت وابسته به قابلیت جستجوی سراسری (Exploration) به خوبی جستجوی محلی بهبود یافته (Exploitation) در فضای جستجو می باشد. تعادل در این دو ویژگی باعث افزایش کارائی می شود. در نوع سراسری PSO ، همه ذرات به وسیله بهترین موقعیت سراسری جذب می شوند. و نسبت به نقاط خاص همگرا می شوند. بنابراین این نوع از PSOبه بهره برداری روی اکتشاف اهمیت می دهد. از سوی دیگر، در نوع محلی PSO ، اطلاعات بهترین موقعیت هر همسایه به آرامی به ذرات دیگر جمعیت از طریق همسایگانشان فرستاده می شود. بنابراین، احتمال اینکه به بهترین موقعیت خاصی جذب شود ضعیف تر می باشد.از این طریق از گیر افتادن در بهینه محلی جلوگیری می شود. بنابراین، نوع PSO محلی به اکتشاف (Exploration) روی بهره برداری  (Exploitation) اهمیت می دهد.

انتخاب مناسب اندازه همسایگی روی تعادل بین بهره برداری و اکتشاف تاثیر می گذارد. که این مقدار یک مسئله باز می باشد و براساس تجربه مقدار دهی می شود.

در PSO مقدار دهی اولیه برای اندازه جمعیت (ازدحام) و سرعت به طور تصادفی انجام می شود. 

در برخی از انواع PSO به منظور عملکرد بهتر در جستجوی های محلی شان عملگرهای شان را تغییر و بهبود می دهند. ضعف در این بخش از الگوریتم PSO استاندارد باعث می شود که در این مقاله این الگوریتم به شکل ممتیکی ارائه شود. که در آن الگوریتم بهینه سازی ازدحام ذرات با الگوریتم های جستجوی محلی ترکیب می شوند.