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

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

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

شکل 1: جرخه اطلاعات در هوش جمعی و PSO

PSO افرادی را از جمعیت کل در فضای جستجو استخراج می کند. در PSO مفهوم جمعیت، ازدحام  (Swarm)نامیده می شود و افراد، ذرات (Particle) نامیده می شوند.

نحوه عملکرد الگوریتم PSO:

همان طور که در شکل2 نشان داده شده است این الگوریتم در فضای جستجو تعدادی ذره وجود دارد که  در کل فضای جستجو در ابتدا تعدادی ذره به عنوان جمعیت اولیه به صورت تصادفی انتخاب می شود. پس از آن هر ذره براساس جهت و سرعت تغییر موقعیت می دهد. هدف از تغییر موقعیت نزدیک کردن خود به بهینه سراسری ( یعنی موقعیت ذره ای با بهترین شایستگی ) می باشد. برای تغییر موقعیت برای هر ذره، از طریق دو رابطه شکل 2 اقدام می شود. رابطه اول نشان دهنده سرعت حرکت ذره می باشد که از حاصل جمع سرعت فعلی، اختلاف بهترین موقعیت کسب شده برای هر ذره تاکنون و موقعیت فعلی و اختلاف بین موقعیت بهینه سراسری این تکرار با موقعیت فعلی هر ذره بدست می آید. C₁,c₂ را ضرایب یادگیری می نامند که معمولاً با 2 مقداردهی می شود. رابطه دوم هم موقعیت هر ذره را از حاصل جمع رابطه 1 با موقعیت فعلی ذره محاسبه می شود.

شکل2: محاسبه موقعیت و سرعت هر ذره در هر تکرار از الگوریتم PSO

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

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

شکل3: مراحل اجرای الگوریتم PSO

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

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

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