الگوریتم PSO

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

الگوریتم PSO

همانطور که قبلا اشاره شد، الگوریتم PSO رفتارهای ازدحام پرنده را شبیه سازی می‌کند. تصور کنید سناریوی زیر: گروهی از پرندگان به طور تصادفی در یک منطقه در معرض غذا قرار می‌گیرند. در منطقه مورد جستجو تنها یک قطعه غذا وجود دارد. همه پرندگان نمی‌دانند کجا غذا است. اما آنها می‌دانند که چقدر مواد غذایی در هر تکرار است. بنابراین بهترین استراتژی برای یافتن غذا چیست؟ راه حل این است که دنبال پرنده‌ای که نزدیکتر به غذا است را دنبال کنید.

طراحان PSO از این سناریو اقتباس کردند و از آن برای حل مشکلات بهینه سازی استفاده کردند. در PSO، هر یک از راه حل یک “پرنده” در فضای جستجو است. ما آن را “ذره” می نامیم. تمام ذرات دارای مقادیر تناسب هستند که توسط تابع تناسب برای بهینه سازی ارزیابی می‌شوند و دارای سرعت‌هایی هستند که پرواز ذرات را هدایت می‌کنند. ذرات از طریق فضای مشکل با ذرات بهینه مطلوب جریان می‌یابند.

نحوه عملکرد PSO

الگوریتم PSO با گروهی از ذرات تصادفی (راه حل) آغاز می شود و سپس با به روز رسانی نسل‌ها جستجو می‌کند. در هر تکرار، هر ذره با دو ارزش “بهترین” به روزرسانی می‌شود. اولین مورد بهترین راه حل ( تابع تناسب ) است که تاکنون به دست آورده است. (ارزش تناسب نیز ذخیره می شود.) این ارزش pbest نامیده می‌شود. یکی دیگر از “بهترین‌ها” ارزشی است که تا کنون توسط هر ذره در جمعیت به دست آمده است. این بهترین ارزش جهانی بهترین است و به نام gbest است. هنگامی که یک ذره بخشی از جمعیت را به عنوان همسایگان توپولوژیکی خود می‌گیرد، بهترین ارزش بهترین محلی است و به نام lbest نامیده می‌شود.

پس از پیدا کردن بهترین مقادیر pbest و gbest  ذره سرعت و موقعیت خود را با معادلات زیر به روز می‌کند.

Xnew = Xcurrent + Vnew
Vnew = Vcurrent + c1 * rand() * (Xpbest - Xcurrent) + c2 * rand() * (Xgbest - Xcurrent)

که در آن V سرعت ذرات است، Xcurrent ذره فعلی (راه حل) است. pbest و gbest قبلا تعریف شده‌اند. rand یک عدد تصادفی بین (۰،۱) است. C1، C2 عامل یادگیری هستند. معمولا c1 = c2 = 2 هستند. برای یادگیری کامل این الگوریتم پیشنهاد می‌کنیم فیلم آموزش الگوریتم PSO را تهیه و دانلود کنید.

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

For each particle 
    Initialize particle
END

Do
    For each particle 
        Calculate fitness value
        If the fitness value is better than the best fitness value (pBest) in history
            set current value as the new pBest
    End

    Choose the particle with the best fitness value of all the particles as the gBest
    For each particle 
        Calculate particle velocity according equation (a)
        Update particle position according equation (b)
    End

مراجع نوشته

http://www.engr.iupui.edu/~eberhart/
http://www.alife.org
http://www.aridolan.com
http://www.red3d.com/cwr/boids/
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html

پاورپوینت الگوریتم PSO

پاورپوینت الگوریتم PSO

کلیک کنید