آموزش الگوریتم پرندگان یا بهینه‌سازی ازدحام ذرات (PSO) به همراه کد پیاده سازی

الگوریتم تجمع ذرات که به نام انگلیسی Particle Swarm Optimization معروف است یا به اختصار به آن PSO هم می گویند برگرفته از تجمع انبوهی از ذرات است، به این معنی از حرکت دسته جمعی پرندگانٰ، ماهی ها و … الهام گرفته است. در حرکت جمعی هر جز خود هوشمندی ندارد ولی رفتار گروه یک هوشمندی رو دنبال می کند.

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

حال با این مثال وارد الگوریتم pso می شویم. در این الگوریتم ما np تا ذره داریم که در فضای مسئله به صورت تصادفی پخش شده اند و هر ذره برای خود یک موقعیت و یک هزینه دارد.

برای جابجایی هر ذره از همون قضیه بالا (ترکیب خطی تجربیات خود و تجربیات الگو) استفاده می شود:

که V‌ سرعت حرکت ذره می باشد که به صورت زیر بدست می آید:

Vi_jadid=c1r1(xi_localBest – xi_ghadim) +c2r2 (x_globalBest – xi_ghadim) + wvi_ghadim

که xi_localBest همون تجربیات خود و x_globalBest تجربیات شخص الگو است.

دقت داشته باشید که ما برای هر ذره یک xi_localBest و برای تمام ذرات یک x_globalBest داریم
c1 , c2‌ ضریب های تصمییم گیری هستند، که کدام یک برای ما بیشتر اولویت دارد و اینکه بیشتر به سمت تجربیات خود حرکت کنیم یا به سمت تجربیات شخص الگو که در پیاده سازی ها معمولا c1+c2=4 در نظر می گیرند مثلا:

r1 و r2 هم اعداد تصادفی هستند که از توزیع یکنواخت بین صفر و یک بدست می آیند که معادل همون دستور rand در متلب می باشد.
wvi_ghadim هم به ضریب اینرسی معروف هست. در الگوریتم pso دو ضریب اول مهم هستند و می توان از ضریب اینرسی چشم پوشی کرد.

حال اگر بخواهیم این روند را برای تعدادی از ذرات اعمال کنیم به صورت زیر می شود.
در ابتدا ما np تا ذره رو در فضای جستجو به صورت تصادفی قرار می دهیم سپس برای هر ذره نسبت به موقعیتش هزینه اش رو محاسبه می کنیم.

حال برای جابجایی موقعیت هر ذره باید از فرمول بالا کمک بگیریم:
نکته ای که در همین ابتدا باید به آن اشاره کنم این است که در گام اول مقدار xi_localBest و x_globalBest‌ چیست؟
برای xi_localBest در گام اول مقدار خود ذره می باشد و برای x_globalBest بهترین مقداری ذره بین تمام ذرات.
با داشتن این پارامترها نوبت به آپدیت کردن ذره ها داریم .طبق فرمول بالا موقعیت هر ذره و هزینه آن آپدیت می شود بعد از آپدیت شدن موقعیت هر ذره نوبت می رسد به موقعیت آپدیت کردن نقاط xi_localBest و x_globalBest .
برای هر ذره تصمیم می گیریم که آیا هزینه موقعیت جدید از xi_localBest آن بهتر است یا نه اگر بهتر بود xi_localBest رو آپدیت می کنیم. و در نهایت موقعیت بهترین ذره رو در x_globalBest قرار می دهیم و این فرآیند رو به تعداد مشخصی تکرار می کنیم.

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

ادامه مطلب