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

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

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

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

 

عملکرد کلی الگوریتم PSO

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

 

انواع مختلف الگوریتم PSO

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

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

یک گرایش دیگر در تحقیقات، تلاش برای دوری از همگرایی زودرس ( ایستایی بهینه سازی) است؛ برای مثال با معکوس کردن یا ایجاد آشفتگی کردن در حرکت ذرات PSO روش هایی برای جلوگیری از رسیدن به همگرایی زودرس است.

یک رویکرد دیگر برای مقابله با همگرایی زودرس، استفاده از چندین دسته است (بهینه سازی چند دسته ای). رویکرد چند دسته ای همچنین می تواند برای پیاده سازی بهینه سازی چند هدفه به کار رود و سرانجام، پیشرفت هایی در به کارگیری پارامترهای رفتاری PSO در طول بهینه سازی انجام گیرد.

 

بهینه سازی چند هدفه

PSO همچنین برای مسائل چند هدفه نیز به کار رفته است که در آنها مقایسه تابع هدف، دامنه pareto را در حرکت ذرات PSO در نظر گرفته و راه حل های نامغلوب برای تخمین pareto front ذخیره می شوند.

 

PSO باینری، گسسته و ترکیبی

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

اغلب اوقات، موقعیت و سرعت توسط n عدد حقیقی نمایش داده می شوند و این عملگرها عبارت اند از -، *، +، و دوباره +. اما تمام این اهداف ریاضی می توانند به روش های بسیار متفاوت به منظور مواجهه با مسائل باینری (یا به صورت عمومی تر، مسائل گسسته)، یا حتی مسائل ترکیبی تعریف شوند. یک رویکرد، بازتعریف عملگرها بر اساس مجموعه هاست.

 

مراجع مطالعاتی و منابع آموزشی مهم

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

 

کتاب های خارجی

	عنوان: Evolutionary Optimization Algorithms ترجمه عنوان: الگوریتم های بهینه سازی تکاملی مولف: Dan SimonRudolf Kruse سال چاپ: ۲۰۱۳ انتشارات: Wiley لینک دسترسی: لینک
	عنوان: Computational Intelligence ترجمه عنوان: هوش محاسباتی مولف: Andries P. Engelbrecht سال چاپ: ۲۰۰۷ انتشارات: Wiley لینک دسترسی: لینک
	عنوان: Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition ترجمه عنوان: بهینه سازی ازدحام ذرات چند بعدی برای یادگیری ماشین و تشخیص الگو مولف: Serkan Kiranyaz سال چاپ: ۲۰۱۳ انتشارات: Springer لینک دسترسی: لینک
	عنوان: Particle Swarm Optimization ترجمه عنوان: بهینه سازی ازدحام ذرات مولف: Maurice Clerc سال چاپ: ۲۰۰۶ انتشارات: Morgan Kaufmann لینک دسترسی: لینک

منابع آموزشی آنلاین

عنوان: مجموعه فرادرس های الگوریتم PSO — شامل مباحث تئوری و عملی مدرس: دکتر سیدمصطفی کلامی هریس مدت زمان: ۹ ساعت و ۵۳ دقیقه نحوه استفاده: دریافت به صورت لینک دانلود و بر روی DVD زبان: فارسی نحوه آموزش: تئوری و عملی ارائه دهنده: سازمان علمی-آموزشی فرادرس لینک دسترسی: لینک