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

در این مقاله روشی جدید مبتنی بر هوش جمعی برای حل مسائل بهینه سازی با روش الگوریتم بهینه‌سازی دومرحله‌ای ازدحام ذرات (particle swarm optimization algorithm) ارائه می‌شود. روش پیشنهادی, با استفاده از دو مرحله تحرک و همگرایی جمعیت, به نتایج جالبی در انواع توابع می‌رسد. در این روش جمعیت اولیه ذرات مقداردهی شده و سپس این ذرات در هر مرحله ابتدا خود را از نواحی نامناسب دور کرده و پس از آن به نواحی مناسب مهاجرت می‌کنند و در نهایت در این نواحی سعی در نزدیک شدن به نقاط بهینه را دارند. ویژگی الگوریتم، نتیجه گرفتن در توابع با ابعاد بالا و همچنین توابع دارای اکسترمم‌های محلی زیاد است. حرکت در جهت دور شدن از نواحی نامناسب، باعث می‌شود تا الگوریتم در مواجه با مسائل با ابعاد بسیار بزرگ و نیز مسائلی که در آن‌ها جمعیت دارای توزیع اولیه نامناسبی است نیز به خوبی عمل کرده و نتایج مناسبی از خود نشان دهد. پراکندگی نامناسب جمعیت اولیه, در الگوریتم بهینه‌سازی گروه ذرات تأثیر منفی دارد. این الگوریتم با مهاجرت کلی ذرات به سمت فضای مناسب، به نقاط بهینه همگرا می‌شود. در انتها ضمن آزمودن روش پیشنهادی بر روی چند تابع محک شناخته شده و مقایسه با الگوریتم بهینه‌سازی گروه ذرات مشاهده می‌شود که روش پیشنهادی به نتایج بهتری می‌رسد.

psoیک الگوریتم رایانه‌ای مبتنی بر جمعیت و کتره‌ای برای حل مسئله‌است. PSOیک نوع هوش جمعی مبتنی بر اصول روانشناسی اجتماعی و فراهم آوردن بینشی در رفتار اجتماعی و کمک کردن به کاربردهای مهندسی است.

الگوریتمPSO برای اولین بار در ۱۹۷۵ توسط Kennedyو C.Eberhart توصیف شد. این تکنیک‌ها بسیار رشد کرده‌اند و نسخه اصلی این الگوریتم به‌طور واضحی در نسخه‌های امروزی قابل شناخت است.
تاثیرگذاری اجتماعی و یادگیری اجتماعی یک شخص را قادر می‌سازد تا ثبات دانستنی‌هایش را برقرار سازد.
انسان‌ها مسائلشان را به کمک صحبت با دیگران و نیز به کمک برهم کنش با باورهایشان، گرایش هایشان و تغییر رفتارشان حل می‌کنند؛ این تغییرات را می‌توان به‌طور نمونه به شکل حرکت افراد به سوی یکدیگر در فضای آگاهی اجتماعی مجسم کرد.

ذرات جمعی شبیه سازی شده، این نوع از بهینه‌سازی اجتماعی می‌باشند. مسئله داه شده و چند راه برای ارزیابی مسئله پیشنهادی به ….. در شکل کلی "تابع شایستگی"حضور دارند. ساختار ارتباطی یا شبکه اجتماعی برای واگذار کردن هر همسایگی به یک فرد تعریف شده تا آن فرد با آن همسایگی بر هم کنش داشته باشد. سپس گروه کارگزاران به عنوان مهمان‌های سرزده برای راه حل‌های مسئله تعریف می‌شوند که آن‌ها را به نام "ذرات" نیز می‌شناسیم؛ از این رو آن‌ها را "ذرات دسته جمعی" نام نهاده‌ایم.

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

همچنین آن‌ها نیز می‌توانند ببینند که دیگر ذرات موجود در همسایگی در کجا بهترین موفقیت را داشته‌اند.

رکت‌ها در فضای جستجو بوسیلهٔ موفقیت‌های قبلی ؛ با افرادی که بیشتر مواقع همگرایی دارند، سرانجام بهتر از حالتی است که نزدیک شدن به جواب به وسیلهٔ عواملی فاقد هوش جمعی ولی با همین روش صورت گیرد.

گروه به صورت نمونه به وسیلهٔ ذرات در فضای چند بعدی که مکان و سرعت دارد، مدل سازی می‌شود.

این ذرات در میان این ابر فضا(فضای دارای بیش از سه بعد) پرواز می‌کنند و دو توانایی ضرورری دارند:

۱-حافظه‌ای برای ذخیره‌سازی بهترین مکان خود۲-آگاهی در مورد بهترین موقعیت در همسایگی خود یا در کل فضای پاسخ‌ها اعضای دسته جمعی مکان‌های خوب را به یکدیگر از طریق ارتباط انتقال می‌دهند و موقعیت و سرعتشان را با مکان‌های خوب تنظیم می‌کنند.

هر ذره برای اعمال تغییری مناسب در مکان و سرعت خود اطلاعات زیر را دارا می‌باشد:

۱-"بهترین عمومی" که برای همه شناخته شده‌است و هنگامی که هر ذره بهترین مکان جدیدی را شناسایی کند، فوراً برای بقیه ذرات اطلاعات مربوطه را به روزرسانی می‌کند.

۲-"بهترین همسایگی"که ذره از طریق ارتباط با زیر مجموعه‌های گروه، آن را بدست می‌آورد.

۳-"بهترین محلی"که بهترین راه حلی است که ذره تاکنون تجربه کرده‌است.

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

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

رده:الگوریتم‌های بهینه‌سازی