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

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

هر ذره در الگوریتم PSO از سه بردار d بعُدی تشکیل شده است که d ، بُعد فضای جستجو می باشد. برای ذره ی iاُم این سه بردار عبارتند از xi موقعیت فعلی ذره،vi سرعت حرکت ذره و x ibest  بهترین موقعیتی که ذره تا به حال تجربه کرده است. xi .مجموعه ای از مختصات است که موقعیت فعلی ذره را نشان می دهد. در هر مرحله ای که الگوریتم تکرار می شود، ix به عنوان یک جواب برای مسأله محاسبه می شود. اگر این موقعیت بهتر از جواب های پیشین باشند، در ibestx ذخیره می شود. i f مقدار تابع هدف در ix، و ibestf مقدار تابع هدف در ibestx است که هر دو از عناصر تشکیل دهنده ی هر ذره به حساب می آیند. ذخیره کردن مقدار ibestf برای انجام مقایسه های بعدی، ضروری است. اما ذخیره کردن مقدار i f ضروری نمی باشد. در هر تکرار، ix و iv جدیدی به دست می آیند و طبعاً منظور از اجرای الگوریتم، بهتر کردن ibestx و احتمالاً ix است.

در مرحله ی ابتدایی الگوریتم، ذرات با موقعیتها و سرعت های تصادفی ایجاد می شود. در طی اجرای الگوریتم بهینه سازی ازدحام ذرات pso ، موقعیت و سرعت هر ذره در مرحله ی t+1 ام از الگوریتم، از روی اطلاعات مرحله ی قبل، ساخته  می شوند

به منظور محدود کردن میزان حرکت هر ذره، مقدار مؤلفه های سرعت ذرات در بازه ی [vmax و vmax] در نظرگرفته می شود و مقادیر بزرگتر یا کوچکتر نیز به این بازه تصویر می شود. البته فرض بر این است که، عرض فضای جستجو در تمام ابعاد ثابت و برابر با s ، باشد. در این صورت معمولاً ، در نظر گرفته میشود  vmax=ps .

جهت سفارش کدنویسی این الگوریتم در محیط متلب اینجا کلیک کنید