بهینه سازی ازدحام ذرات ممتیکی

مقاله: بهینه سازی ازدحام ذرات ممتیکی

این مقاله در سال 2007 توسط Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis در Springer به چاپ رسیده است.

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

به طور کلی مراحل یک الگوریتم ممتیکی در شکل 1 نشان داده شده است.

شکل 1: مراجل الگوریتم ممتیکی

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

برای الگوریتم ازدحام ذرات ممتیکی چون ترکیبی از الگوریتم ازدحام ذرات و یک جستجوی محلی می باشد می توان طرح های مختلفی به صورت زیر برای آن در نظر گرفت:

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

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

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

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

یک الگوریتم ازدحام ذرات ممتیکی در شکل 2 نشان داده شده است.

شکل 2: الگوریتم ازدحام ذرات ممتیکی

آنالیز تجربی الگوریتم ازدحام ذرات ممتیکی

در الگوریتم ازدحام ذرات ممتیکی پیشنهادی از جستجوی محلی گشتن تصادفی با استخراج مستقیم (RWMPSO)  استفاده شده است. این جستجوی محلی یک روش بهینه سازی تصادفی و تکراری می باشد. این الگوریتم شامل چهار مرحله زیر می باشد:

مرحله 1: شروع تکرار با t=0 ، که با نقطه اولیه x⁽¹⁾ شروع می شود. و یک طول گام اسکالر=_init   می باشد. و سپس محاسبه مقدار تابع که F⁽¹⁾=F(x⁽¹⁾)  که منظور از  F تابع هدف می باشد.

مرحله 2: t=t+1 قرار داده می شود. و t با t_max به عنوان آستانه چک می شود اگر از مقدار آستانه بزرگ تر باشد خاتمه می یابد در غیر این صورت یک بردار تصادفی واحد طول بنام z^(t) تولید شده و سپس ادامه می یابد.

مرحله 3: در این مرحله مقدار تابع هدف محاسبه می شود:

=F(x^(t)+z^(t))

مرحله 4: مقایسه مقدار F^’  و F^(t) . اگر< F^(t)   F^’  سپس  x^(t+1) = x^(t) + λz^(t)  می شود.

t = t +1, λ = λ_init, F^(t) = F^’  . اگر t>t_max  پایان می یابد در غیر این صورت مرحله 3 تکرار می شود.

اگر> F^(t)   F^’ ، x^(t+1) = x^(t) قرار داده می شود. سپس طول گام  , λ = λ/2و مرحله 2 تا 4 تکرار می شود.

اگر   F^(t) =  F^’  آنگاه x^(t+1) = x^(t) و مرحله 2 تا 4 تکرار می شود.

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

در جدول 1 تنظیمات پارامترها برای مسائل برنامه نویسی عدد صحیح آورده شده است.

جدول 1: تنظیمات پارامترها برای مسائل برنامه نویسی عدد صحیح

در جدول 2 نتایج مسائل برنامه نویسی عدد صحیح روی الگوریتم های مختلف آورده شده است.

جدول 2: نتایج مسائل برنامه نویسی عدد صحیح روی الگوریتم های مختلف

  [1]. Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis,” Memetic particle swarm optimization”, Springer, 2007.