الگوریتم PSO در متلب

الگوریتم ازدحام ذرات

یکی دیگر از الگورتیم اکتشافی که 60 سال پس از الگوریتم ژنتیک پا به عرصه رقابت گذاشته است، الگوریتم بهینه سازی ازدحام ذرات یا همان PSO (Particle swarm optimization) می باشد.

• مفاهیم پایه در یاد گیری الگوریتم PSO
• روابط ریاضی PSO
• تنظیم ضرایب وزن دهی
• چارت الگوریتم PSO
• PSO در متلب

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

مفاهیم پایه در یاد گیری الگوریتم PSO:

• ذره: پاسخ های محتمل به مساله بهینه سازی را ذره می گویند. بنابراین ذرات همان عامل جستجو می باشد.
• گروه ذرات: به مجموعه ای ذرات (جواب های محتمل برای مساله بهینه سازی) گروه یا Swarm می گویند. تعداد ذرات در هر گروه swarm size می باشد.
• رهبر گروه: پس از هر تکرار یک ذره در گروه دارای بهترین جواب خواهد بود (best fitness). این ذره، رهبر گروه در آن تکرار است که سایر ذرات در تکرار بعدی سعی دارند به این مقدار نزدیک شوند. (Gbest)
• موقعیت برتر: هر ذره خود به تنهایی موقعیت فعلی خود را با موقعیت قبلی مقایسه می کند و بهترین حالت را در حافظه خود ذخیره می کند. در تکرار های بعدی علاوه بر در نظر گرفتن موقعیت بر تر خود سعی در خیزش به سمت موقعیت رهبر گروه را نیز دارد. (Pbest)

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

روابط ریاضی PSO

در شکل زیر نحوه محاسبه مکان جدید ذره نمایش داده شده است. با در نظر گرفتن سرعت ذره در تکرار قبل، بهترین موقعیت خود ذره که تا کنون تجربه کرده است و همچنین بهترین موقعیتی که در حالت کلی تجربه شده است.

روابط ریاضی: [1]

رابطه اول نشان می دهد که ذره برای تعیین موقعیت جدید xⁱ_k+1، علاوه بر موقعیت فعلی xⁱ_k خود باید مقدار سرعت جدیدی vⁱ_k+1 اتخاذ کند.

در رابطه دوم همانطور که گفته شد، سرعت جدید برای ذره را از جمع وزن دار پارامتر های زیر محاسبه می شود:

• سرعت ذره در تکرار قبلی vⁱ_k
• فاصله موقعیت کنونی ذره از بهترین موقعیتی p_k^best که ذره تجربه کرده است. (p_{k^{best i}} - x_kⁱ)
• فاصله موقعیت کنونی ذره از موقعیت رهبر گروه g_k^best بهترین موقعیت تجربه شده، می باشد. (g_k^best - x_kⁱ)

جمع وزنی پارامتر های بالا نیازمند ضرایب وزن دهی می باشد که در فرمول آورده شده است.

• w وزن اینرسی
• c₁ و c₂ ضرایب شتاب
• r₁ و r₂ اعداد تصادفی بین صفر و یک با توزیع یکنواخت هستند.

تنظیم ضرایب وزن دهی

وزن اینرسی w: مقدار w بزرگ نشان دهنده گام های جستجوی بزرگ می باشد. در این مواقع سرعت تغییرات ذرات بالاتر خواهد بود و فضای بزرگتری را کاوش می کنند. بر عکس این موضوع اگر میزان w را کوچک بگیریم فضای محدودی را با دقت بالاتری بررسی خواهد کرد.
در نتیجه ما می توانید در شروع الگوریتم w را بزرگ فرض کرده و به صورت خطی آن را کاهش دهیم . مقدار w از 0.8 شروع و به 0.1 ختم می شود.

r₁ و r₂ : برای حفظ ماهیت تصادفی الگوریتم مقادیر این ضرائب به صورت تصادفی بین صفر و یک با توزیع یکنواخت تولید می شوند. این ضرائب ماهیت کنترلی بر روی عملکرد الگوریتم را ندارند.

ضرایب شتاب:
c₁ ضریبی است که با آن موقعیت ذره نسبت به بهترین خودش را کنترل می کند. افزایش این ضریب باعث جستجوی سراسری می شود.
c₂ ضریب کنترلی موقعیت ذره نسبت به مقدار بهینه کل می باشد. افزایش این ضریب نرخ همگرایی به بهینه گروه را بالا می برد. توجه داشته باشید که احتمال افتادن در بهینه محلی را نیز زیاد خواهد کرد.

چارت الگوریتم pso

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

PSO در متلب

برای پیاده سازی PSO در نرم افزار متلب تابع particleswarm معرفی شده است. این تابع در ورودی موارد زیر را از کاربر دریافت کند :

• اسم تابع
• تعداد متغیر ها
• بردار حداقل ذرات
• بردار حداکثر ذرات
• آپشن های کنترلی در اجرای الگوریتم

[x,fval,exitflag,output] = particleswarm(fun,nvars,lb,ub,options)

همچنین به عنوان خروجی لیست زیر را ارائه می دهد.

• مقدار ذره بهینه
• مقدار best function
• عاملی که باعث توقف الگوریتم شده
• خروجی عملکرد الگوریتم

fun = @(x)x(1)*exp(-norm(x)^2);
lb = [-10,-15];
ub = [15,20];
nvars = 2;
[x,fval,exitflag,output] = particleswarm(fun,nvars,lb,ub)

در مثال بالا همانطور که می بینید، فانکش مورد نظر با fun تعریف شده است. مساله یافتن مقدار مینیمم برای تابع، با تعداد دو متغییر x می باشد.

برای حل این مساله مقید محدوده متغییرهای x نیز لحاظ شده است. اگر مساله شما مقید نیست باید جای lb و ub از علامت ماتریس خالی [] استفاده کنید. برنامه نوشته شده در نهایت سعی دارد مقدار کمینه را برای تابع با قیود مطرح شده بدست اورد.

لازم است بدانید برای تنظیم پارامتر های الگوریتم می توانیم از ورودی option استفاده کنید.

پست های مرتبط:

الگوریتم ژنتیک بهینه سازی استخراج لبه الگوریتم KNN در متلب