الگوریتم پرندگان یا اجتماع ذرات چیست؟

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

در این پست می خواهیم بطور خلاصه به معرفی الگوریتم بهینه Particle Swarm Optimization که به اختصار PSO نامیده شده و تحت نامهای مختلفی همچون الگوریتم انبوه ذرات، الگوریتم ازدحام ذرات و الگوریتم پرندگان درایران شناخته شده است، بپردازیم. با ما در ادامه مطلب همراه باشید.

عبارت Swarm در زبان انگلیسی به اجتماع دسته انبوهی از جانوران و حشرات اشاره می کند. در زیر یک swarm از زنبور ها را می بینید.

تصویر یک swarm از زنبورها

اگر سرعت اینترنتتان مناسب باشد، می توانید حرکت یک swarm از ماهی ها را در زیر ببینید. جهت حفظ امانت، لازم به ذکر است که تصویر متحرک زیر از ویکیپدیا گرفته شده است.

 

تصویر متحرک یک swarm از ماهی ها
ايده Particle Swarm Optimization، براي اولين بار توسط کندي و ابرهارت در سال 1995 مطرح شد. PSO، يک الگوريتم محاسبه اي تکاملي الهام گرفته از طبيعت و براساس تکرار مي‌باشد. منبع الهام اين الگوريتم، رفتار اجتماعي حيوانات، همانند حرکت دسته جمعي پرندگان و ماهي‌ها بود. از اين جهت که PSO نيز با يک ماتريس جمعيت تصادفي اوليه، شروع مي‌شود، شبيه بسیاری دیگر از الگوریتم های تکاملی همچون الگوريتم ژنتيک پيوسته و الگوریتم رقابت استعماری است. برخلاف الگوریتم ژنتیک ، PSO هيچ عملگر تکاملي همانند جهش و تزويج ندارد. از این جهت می شود گفت که الگوریتم رقابت استعماری شباهت بیشتری به PSO دارد تا به GA. هر عنصر جمعيت، يک ذره ناميده مي‌شود (که همان معادل کروموزوم در GA و یا کشور در الگوریتم رقابت استعماری) است. در واقع الگوريتم PSO از تعداد مشخصي از ذرات تشکيل مي-شود که به طور تصادفي، مقدار اوليه مي گيرند. براي هر ذره دو مقدار وضعيت و سرعت، تعريف مي شود که به ترتيب با يک بردار مکان و يک بردار سرعت، مدل مي‌شوند. اين ذرات، بصورت تکرارشونده اي در فضاي n‌ـ‌بعدي مسئله حرکت مي کنند تا با محاسبة مقدار بهينگي به عنوان يک ملاک سنجش، گزينه‌هاي ممکن جديد را جستجو کنند. بُعد فضاي مسئله، برابر تعداد پارامترهاي موجود در تابع مورد نظر براي بهينه سازي مي باشد. يک حافظه به ذخيرة بهترين موقعيت هر ذره در گذشته و يک حافظه به ذخيرة بهترين موقعيت پيش آمده در ميان همة ذرات، اختصاص مي‌يابد. با تجربة حاصل از اين حافظه ها, ذرات تصميم مي گيرند که در نوبت بعدي، چگونه حرکت کنند. در هر بار تکرار، همة ذرات در فضاي nـ‌بعدي مسئله حرکت مي¬کنند تا بالاخره نقطة بهينة عام، پيدا شود. ذرات، سرعت‌هايشان و موقعيت‌شان را بر حسب بهترين جواب‌هاي مطلق و محلي به‌روز مي‌کنند. يعني
v_{m,n}^{new} = v_{m,n}^{old} + {\Gamma _1} \times {r_1} \times (p_{m,n}^{local\,best} - p_{m,n}^{old}) + {\Gamma _2} \times {r_2} \times (p_{m,n}^{global\,best} - p_{m,n}^{old})
p_{m,n}^{new} = p_{m,n}^{old} + v_{m,n}^{new}

که در آن

  • {v_{m,n}}، سرعت ذره
  • {p_{m,n}}، متغير‌هاي ذره
  • {r_1},\,{r_2}، اعداد تصادفي مستقل با توزيع يکنواخت
  • {\Gamma _1},\,{\Gamma _2}\,، فاکتورهاي يادگيري
  • p_{m,n}^{local\,best}، بهترين جواب محلي
  • p_{m,n}^{global\,best}، بهترين جواب مطلق
مي‌باشند. الگوريتم PSO، بردار سرعت هر ذره را به‌روز کرده و سپس مقدار سرعت جديد را به موقعيت و يا مقدار ذره مي‌افزايد. به‌روز کردن‌هاي سرعت، تحت تأثير هر دو مقدار بهترين جواب محلي و بهترين جواب مطلق قرار مي‌گيرند. بهترين جواب محلي و بهترين جواب مطلق، بهترين جوابهايي هستند که تا لحظه‌ي جاري اجراي الگوريتم، به ترتيب توسط يک ذره و در کل جمعيت به دست آمده‌اند. ثابت‌هاي {\Gamma _1} و {\Gamma _2}\, به ترتيب، پارامتر ادراکي و پارامتر اجتماعي ناميده مي‌شوند. مزيت اصلي PSO اين است که پياده‌سازي اين الگوريتم ساده بوده و نياز به تعيين پارامتر‌هاي کمي دارد. همچنين PSO قادر به بهينه‌سازي توابع هزينه‌ي پيچيده با تعداد زياد مينيمم محلي است.

به زودی بر روی وبسایت الگوریتم رقابت استعماری و بهینه سازی تکاملی کدها و مراجع آموزشی مفیدی راجع به این الگوریتم را برایتان قرار خواهیم داد.

_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

————————————-
تبلیغات متنی:

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

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




0 پاسخ

ارسال یک پاسخ

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *