مقاله: بهینه سازی ازدحام ذرات ممتیکی (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 استاندارد باعث می شود که در این مقاله این الگوریتم به شکل ممتیکی ارائه شود. که در آن الگوریتم بهینه سازی ازدحام ذرات با الگوریتم های جستجوی محلی ترکیب می شوند.

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

شبه کد الگوریتم های ممتیکی در شکل 1 آورده شده است. که در آن علاوه بر عملگرهای ترکیب جدید و جهش حستجوهای محلی نیز دخالت داده شده است.

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

الگوریتم پیشنهادی در مقاله:

از جمله از طرح های مختلف بهینه سازی ازدحام ذرات ممتیکی عبارت است از:

طرح 1: جستجوی محلی روی بهترین موقعیت سراسری جمعیت بکابرده شود که p_gنامیده می شود که منظور از g اندیسی است که نشان دهنده بهترین ذره می باشد.

طرح 2: برای هر بهترین موقعیت p_iکه i=1,2,..,N می باشد یک عدد تصادفی r تولید شده که اگر r<Ɛو جائی که Ɛ>0  به عنوان آستانه تعیین شده است آنگاه جستجوی محلی روی p_i بکار برده می شود.

طرح 3-1:جستجوی محلی هم روی بهترین موقعیت p_gبرای کل جمعیت بکاربرده می شود و هم روی بهترین موقعیت تصادفی انتخاب شده یعنی p_i که i є {1,2,…,N} می باشد.

طرح 3-2:جستجوی محلی هم روی بهترین موقعیت p_g برای کل جمعیت بکاربرده می شود و هم رویبهترین موقعیت تصادفی انتخاب شده یعنی p_i که i є {1,2,…,N} می باشد بطوری که |p_g-p_i|> c Δ (s) که c є (0,1) و Δ (s) قطر (diameter) فضای جستجوی S می باشد.

هر کدام از این سه طرح می توانند با هم در هر تکرار یا در کل تکرار های الگوریتم مورد استفاده قرار گیرد.

شبه کد الگوریتم پیشنهادی در شکل 2 آورده شده است.

شکل2: شبه کد الگوریتم پیشنهادی MPSO

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

تحلیل و مقایسه نتایج الگوریتم پیشنهادی:

در جدول 1 مقایسه نتایج بین الگوریتم های RWMPSOg,RWMPSOl,PSOg,PSOl نشان داده شده است. منظور از الگوریتم RWDE(Random Walk Direction Exploitation ) گام های تصادفی با جهت گیری بهره وری می باشد که به عنوان جستجوی محلی می تواند در کنار PSO استفاده شود که در آن صورت با RWMPSO نشان داده می شود. که خود این الگوریتم هم بر دو نوع سراسری RWMPSOg  و نوع محلی RWMPSOl تقسیم می شود. همچنین PSO های سراسری و محلی به ترتیب با PSOg و PSOl نشان داده شده اند.

در این جدول مقادیر min,max,mean نشان دهنده کمترین وماکزیمم و میانگین برازندگی می باشد. همچنین StD و Suc به ترتیب نشان دهنده انحراف معیار و تعداد موفقیت می باشد. یک جواب موفق است اگر مینیمم سراسری آن با دقت 10^-6  اتفاق بی افتد.

جدول 1: مقایسه نتایج الگوریتم پیشنهادی و الگوریتم های دیگر برای مسائل مختلف Benchmark

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

[1].  Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis, “  Memetic particle swarm optimization”, springer, DOI 10.1007/s10479-007-0224-y, August 2007.