الگوریتم بهینه سازی ازدحام ذرات (PSO)

کلمه PSO به معنی Particle Swarm Optimization یا بهینه‌سازی توده ذرات است.
برای حل مسائل بهینه سازی از طریق روش های هوشمند الگوریتم های تکاملی و فراابتکاری ابزارهای بسیار قدرتمند هوش مصنوعی هستند.
این الگوریتم ها، که اغلب از فرایندهای طبیعی الهام گرفته شده اند، در واقع روش های جستجو هستند که در فضای همه پاسخ های ممکن برای یک مساله بهینه سازی جستجو می‌‌کنند.
روش PSO ریشه در کارهای Reynolds دارد که یک شبیه سازی ابتدایی از رفتار اجتماعی پرندگان است .
توده ذرات در طبیعت برای ما بیانگر هوش جمعی است. حرکت جمعی ماهی‌ها درون آب یا پرندگان هنگام مهاجرت را در نظر بگیرید، همگی اعضا با یکدیگر به صورت کاملا هماهنگ حرکت می‌کنند، اگر قرار است شکار کنند با هم شکار می‌کنند و اگر قرار است طعمه شکار دیگری شوند با حرکت گروهی از چنگ شکارچی فرار می‌کنند.

هوش جمعی :

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

ویژگی‌های الگوریتم توده ذرات :

هر ذره به طور مستقل، به دنبال نقطه بهينه می‌گردد.
هر ذره در هر گام با سرعت یکسان حرکت می‌کند.
هر ذره مكان بهترين نقطه‌هایی كه‌تابحال درآن قرارداشته‌ را به خاطر می‌سپارد.
ذرات با هم همكاری می كنند و يكديگر را از مكان‌هايی كه جستجو كرده‌اند مطلع می‌سازند.
هر ذره با ذرات همسایه‌اش، درارتباط است.
هر ذره از فیتنس ذراتی كه در همسايگی قرار دارند مطلع است.
هر ذره ازمكان بهترين ذراتی كه در همسايگيش قرار دارد مطلع است.

مراحل الگوریتم PSO :

ایجاد جمعیت اولیه و ارزیابی آن
تعیین بهترین خاطرات شخصی و بهترین خاطره جمعی
بروزرسانی سرعت و موقعیت
در صورت برآورده نشدن شرایط توقف به مرحله ۲ می رویم.
پایان

انتخاب تعداد ذرات اولیه :

می دانیم که افزایش تعداد ذرات اولیه موجب کاهش تعداد تکرارهای لازم برای همگرا شدن الگوریتم می گردد. اما گاهی مشاهده می شود که کاربران الگوریتم های بهینه سازی تصور می کنند که این کاهش در تعداد تکرارها به معنی کاهش زمان اجرای برنامه برای رسیدن به همگرایی است، در حالی که چنین تصوری کاملاً غلط است. هرچند که افزایش تعداد ذراات اولیه کاهش تعداد تکرارها را در پی دارد. اما افزایش در تعداد ذرات باعث می گردد که الگوریتم در مرحله ارزیابی ذرات زمان بیشتری را صرف نماید که این افزایش در زمان ارزیابی باعث می شود که زمان اجرای الگوریتم تا رسیدن به همگرایی با وجود کاهش در تعداد تکرارها، کاهش نیابد. پس افزایش تعداد ذرات نمی تواند برای کاهش زمان اجرای الگوریتم مورد استفاده قرار گیرد. تصور غلط دیگری وجود دارد و آن این است که برای کاهش زمان اجرای الگوریتم می توان تعداد ذرات را کاهش داد. این تصور نیز وجود دارد و آن این است که برای کاهش زمان لازم برای ارزیابی ذرات می گردد، اما برای این که الگوریتم به جواب بهینه برسد. تعداد تکرارها افزایش می یابد. (اگر شرط همگرایی را عدم تغییر در هزینه بهترین عضو در چندین تکرار متوالی در نظر بگیریم) که در نهایت باعث می شود زمان اجرای برنامه برای رسیدن به پاسخ بهینه کاهشی نداشته باشد. همچنین باید متذکر شد که کاهش تعداد ذرات ممکن است موجب گیر افتادن در مینیم های محلی شود و الگوریتم از رسیدن به مینیمم اصلی باز ماند. اگر ما شرط همگرایی را تعداد تکرارها در نظر گرفته باشیم، هرچند با کاهش تعداد ذرات اولیه زمان اجرای الگوریتم کاهش می یابد اما جواب به دست آمده، حل بهینه ای برای مسئله نخواهد بود. زیرا الگوریتم بصورت ناقص اجرا شده است.
بطور خلاصه، تعداد جمعیت اولیه با توجه به مسئله تعیین می گردد. در حالت کلی تعداد ذرات اولیه مصالحه ای بین پارامترهای درگیر در مسئله است. بطور تجربی انتخاب جمعیت اولیه ذرات به تعداد 20 تا 30 ذره انتخاب مناسبی است که تقریباً برای تمامی مسائل تست به خوبی جواب می دهد. می توانید تعداد ذرات را کمی بیشتر از حد لازم نیز در نظر بگیرید تا کمی حاشیه ایمنی در مواجهه با مینیمم های محلی داشته باشید.

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

در سال ۱۹۹۵ ابرهارت و کندی برای اولین بار PSO به عنوان یک روش جستجوی غیر قطعی برای بهینه‌سازی تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا می‌باشند، الهام گرفته شده‌است. گروهی از پرندگان در فضایی به صورت تصادفی دنبال غذا میگردند. تنها یک تکه غذا در فضای مورد جستجو وجود دارد. هر راه حل که به آن یک ذره گفته میشود، PSO در الگوریتم معادل یک پرنده در الگوریتم حرکت جمعی پرندگان می‌باشد. هر ذره یک مقدار شایستگی دارد که توسط یک تابع شایستگی محاسبه می‌شود. هر چه ذره در فضای جستجو به هدف (غذا در مدل حرکت پرندگان) نزدیکتر باشد، شایستگی بیشتری دارد. همچنین هر ذره دارای یک سرعت است که هدایت حرکت ذره را بر عهده دارد. هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه می‌دهد.

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

الگوریتم PSO یک الگوریتم مبتنی بر جمعیت است. این خاصیت باعث می شود که کمتر در مینیمم محلی گرفتار شود.
این الگوریتم براساس قوانین احتمالی عمل می کند نه قوانين قطعی. بنابراین، PSO یک الگوریتم بهینه سازی تصادفی است که می تواند نواحی نامشخص و پیچیده را جستجو کند. این خاصیت، PSO را نسبت به روشهای معمولی انعطاف پذیرتر و مقاومتر می کند.
PSO با توابع هدف غیر دیفرانسیلی سروکار دارد بدلیل اینکه PSO از نتیجه اطلاعات (شاخص بازدهی یا تابع هدف استفاده می کند تا جستجو را در فضای مسئله هدایت کند.
كيفيت جواب مسیر پیشنهادی به جمعیت اولیه وابسته نیست. با شروع از هر نقطه در فضای جستجو، الگوریتم جواب مسئله را نهایتا به جواب بهينه همگرا می کند.
PSO انعطاف پذیری زیادی دارد تا تعادل بین جستجوی محلی و کلی از فضای جستجو را کنترل کند. این خاصیت منحصربفرد  PSO به مشکل همگرایی بدموقع غلبه می کند و ظرفیت جستجو را افزایش می دهد که همه این خاصيتها PSO را متفاوت از الگوریتم ژنتیک (GA) و دیگر الگوریتمهای ابتکاری می کند.

شرایط توقف:

رسیدن به حد قابل قبولی از پاسخ
سپری شدن تعداد تکرار یا زمان مشخص
سپری شدن تعداد تکرار یا زمان مشخص بدون مشاهده بهبود خاص در نتیجه
بررسی تعداد مشخصی از پاسخ ها

تست همگرایی :

تست همگرایی در این الگوریتم مانند سایر الگوریتم های بهینه سازی است. برای بررسی الگوریتم روش های گوناگونی وجود دارد. برای مثال می توان تعداد مشخصی تکرار را از همان ابتدا معلوم کرد و در هر مرحله بررسی کرد که آیا تعداد تکرارها به مقدار تعیین شده رسیده است؟ اگر تعداد تکرارها کوچکتر از مقدار تعیین شده اولیه باشد، آن گاه باید به مرحله 2 بازگردید در غیر این صورت الگوریتم پایان می پذیرد. روش دیگری که اغلب در تست همگرایی الگوریتم استفاده می‌شود، این است که اگر در چند تکرار متوالی مثلاً 15 یا 20 تکرار تغییری در مقدار هزینه بهترین ذره ایجاد نگردد، آنگاه الگوریتم پایان می یابد، در غیر این صورت باید به مرحله 2 بازگردید. دیاگرام گردشی (فلوچارت) الگوریتم PSO در شکل نشان داده شده است.

الگوریتم PSO در بهینه سازی مسائل چندهدفه :

در مسائل بهینه سازی چندهدفه ، اهداف چندگانه نیاز به بهینه شدن به طور همزمان دارند. در اغلب موارد، جواب بهینه تکی (مجرد) معمولا نمی تواند یافت شود تا تمام توابع هدف را بهینه سازد. در عوض یک گروه از جوابها وجود دارد که به عنوان مجموعه بهینه پارتو شناخته می شوند. راه حل ها در این گروه در غیاب برتری در میان اهداف، متعادل (برابر) هستند. مساله تصمیم گیری چندهدفه (MODM) از پرکاربردترین حوزه های الگوریتم PSO شده اند. روشهای رایج PSO چندهدفه را می‌توان به صورت زیر دسته بندی نمود.