در این ویدیو به آموزش تئوری و مبانی الگوریتم بهینه سازی ازدحام ذرات (PSO) میپردازیم. مقدمه این الگوریتم بیان می شود سپس به بیان تعریف ذره در این الگوریتم می پردازیم و موقعیت، سرعت، کیفیت یک ذره را بیان میکنیم. و سپس تولید جمعیت و شرایط توقف الگوریتم را بیان میکنیم. در انتها نیز جزوه الگوریتم pso قرار داده شده است.
الگوریتم بهینه سازی ازدحام ذرات (PSO)
الگوریتم بهینه سازی ازدحام ذرات (PSO) یک الگوریتم بهینه سازی است که برای حل مسائل بهینه سازی مورد استفاده قرار می گیرد. در این الگوریتم، یک گروه از ذرات در فضای جستجو حرکت می کنند و با توجه به موقعیت و سرعت خود، به دنبال بهبود موقعیت خود در فضای جستجو هستند. هر ذره در هر لحظه، با توجه به موقعیت خود و موقعیت بهترین ذره در گروه، سرعت خود را تغییر می دهد و به سمت بهترین موقعیت حرکت می کند. این الگوریتم با تکرار این فرآیند، به بهبود موقعیت و پیدا کردن حل بهینه برای مسئله کمک می کند.
در بیشتر گونه های جانوران رفتارهای گروهی دیده می شود. چه بسا که بعضی از این گونه ها نیز توسط یك عضو برتر گروه راهنمایی می شوند. به عنوان مثال در شیرها، میمون ها گوزن ها این امر کاملا مشاهده میشود. در اوایل سال ۱۹۰۰ با تحقیقاتی که بر روی رفتار اجتماعی میمون ها صورت گرفت مشخص شد که در این گونه از میمون ها عملکرد و رفتار هر عضو از گروه به صورت سلسله مراتبی از طرف جامعه بالاتر ، فرمان داده می شود . مطلب جالب تر یكه وجود دارد این است که گونه هایی از جانوران وجود دارند که به صورت گروهی زندگی می کنند اما راهنمایی ندارند. هر عضو یك رفتار خودسازمانده دارد که بدون استفاده از یك راهنما می تواند در محیط حرکت نموده و نیازهای طبیعی خود را برطرف نماید مانند گروه پرندگان ، ماهی ها و گله گوسفندان . این گونه از جانوران هیچ دانشی نسبت به رفتار عمومی کل گروه ندارند و یا حتی هیچ دانشی نسبت به محیطی که در آن قرار دارند، ندارند. در عوض قادرند با رد و بدل نمودن اطلاعات با اعضای همجوار خود در محیط حركت نمایند. این تعامل ساده بین ذرات باعث ایجاد رفتار پیچیده تر گروه می شود . مانند جستجوی یك محیط توسط نرات. تحقیقات زیادی بر روی رفتارهای اجتماعی ذرات انجام شده است که در ادامه به چند نمونه از آنها می پردازیم : رفتار پرندگان ، رفتار گروه ماهی ها، رفتار شکار کردن وال های گوزیست، رفتار جستجوی غذا در میمون های وحشی و … . اولین بار كندی و ایرهارت پس از شبیه سازی رفتار اجتماعی پرندگان روس بهینه سازی گروه ذرات را ارائه دادند. اجزای یك گروه از یك رفتار ساده تبعیت می نمایند. بدین نحو که هر عضو از گروه از موفقیت سایر همسایگانشان تقلید می نماید. هدف از این الگوریتم ها این است که اعضای گروه در فضای جستجو حرکت نموده و در یك نقطه بهینه ( مانند منبع غذا) جمع شوند.
تاریخچه الگوریتم PSO
روش PSO ریشه در کارهای Reynolds دارد که یک شبیه سازی ابتدایی از رفتار اجتماعی پرندگان است . در این مدل رفتارهای ساده پیدا کردن نزدیك ترین همسایه ها تنظیم سرعت های پیاده شده است. این مدل برندگان به صورت تصادفی در یك فضای جستجوی جدول پیکسلی قرار داده می شوند و در هر تکرار نزدیکترین همسایه ذره انتخاب شده و سرعت نره با سرعت نزدیکترین همسایه اش جایگزین می شود. این عمل باعث می شود که گروه خیلی سریع به یك جهت حرکت نامعین و بدون تغییر همگرا شوند. جهت رفع این مشكل یک مولفه دیوانگی به صورت تغییر تصادفی در گروه ها استفاده شده است. به منظور توسعه بیشتر این مدل مفهوم سردسته پرندگان نیز به مدل اضافه گردید که به شكل یك حافظه از بهترین موقعیت های هر عضو و همسایگان آن بود . بهترین موقعیت قبلی هر عضو بهترین موقعیتی است که آن عضو از ابتدای حیات خود تا به حال کسب نموده است. بهترین موقعیت همسایگی بهترین موقعیتی است که توسط همسایگان یك عضو ملاقات شده است. این دو بهترین موقعیت به عنوان نقاط جذب عمل می نمایند. با استفاده از یك مجموعه قوانین ساده می توان موقعیت های اعضای گروه را به روز نمود . بدین صورت که عضو به یك نسبت به سمت دو موقعیت بهتر حرکت می نماید . به مرور زمان با تكرار الگوریتم اعضا حول یك هدف جمع می شوند. این رفتار که حتی بدون هماهنگی سرعت ها و فاکتور دیوانگی نتیجه بخش بود . مدل نهایی بهینه سازی گروه ذرات نامیده می شود.
الگوریتم PSO الهام گرفته از رفتار دسته جمعی پرندگان یا ماهی ها می باشد به طور خاص به استراتژی تكاملی مرتبط است گروهی از پرندگان یا ماهی ها در محیط دنبال غذا می گردند و تنها یك تكه غذا وجود دارد و هیچ یك از پرندگان از محل غذا اطلاعی ندارد و فقط فاصله خود تا غذا را می داند. یكی از بهترین استراتژی ها دنبال كردن پرنده ای می باشد كه به غذا نزدیك تر است و به عبارت دیگر هر پرنده یا ماهی علاوه بر تفكر خودش به پرنده یا ماهی جلو تر برای پیدا كردن غذا اعتماد می كند.
برای فهم این الگوریتم من یك مثال انسانی برای شما می آورم؛ فرض كنید كه شما دانشجو هستید و می خواهید رشد تحصیلی داشته باشید و در یك مقطعی رشد تحصیلی شما خوب بوده است و همچنین در همون مقطع یك شاگرد اول كلاس هم وجود دارد كه می توان از روش درس خوندن اون الگو برداری كرد. حال برای اینكه شما در رشد تحصیلی پیشرفت داشته باشید دو كار می توانید انجام بدهید یا اینكه بر اساس تجربیات خود پیش بروید یا اینكه از تجربیات شخص الگو پیروی كنید. كه هر دو این كار ضرر هایی دارید اگر به دنبال تجربیات خود بروید یك تصمییم خودخواهانه گرفتید كه ناشی از این است كه به دانش خود اعتماد كامل دارید و چه بسا كه ممكن است دانش شما اشتباه باشد و اگر فقط از تجربه ی شخص الگو استفاده كنید یك خودباختگی برای شما پیش خواهد آمد كه به دانش خود اعتماد ندارید. بهترین كار این است كه از تركیب این دو استفاده كنید.
ویژگی های الگوریتم PSO
- محاسبات فضاي چند بعدي به صورت يكسري از گام هاي زماني انجام مي شود که به اصل پوشش معروف است.
- گروه ذرات به فاكتورهاي كيفي به صورت بهترین موقعيت هاي فردي و همسایگی جواب میدهد.
- تخصيص پاسخ ها بین بهترین موقعیت ملاقات شده ذره و بهترین موقعیت ملاقات شده توسط گروه ، تنوع پاسخ ها را تضمین می نماید.
- گروه حالت خود را فقط هنگامي که بهترین موقعیت ملاقات شده توسط ذره و بهترین موقعیت ملاقات شده توسط گروه تغيير مي كنند ، تغيير میدهد که به اصل پايداري معروف است.
- در نهایت گروه رفتار تطبيقي از خود نشان میدهد بدین صورت که حالت خود را هنگامی که بهترین موقعیت ملاقات شده توسط ذره و بهترین موقعیت ملاقات شده توسط گروه تغيير مي كنند، تغییر میدهد.
الگوریتم بهینه سازي گروه ذرات داراي چندین نقطه ضعف مي باشد. در این الگوریتم احتمال قرار گرفتن ذارت در بهينه هاي محلي وجود دارد. هرچند که PSO نسبت به الگوریتم هاي تكاملي داراي سرعت بالاتري است اما معمولا نمي تواند كيفيت رسیدن به راه حل را با افزایش تكرارها جبران کند. یکی از دلایل این است که در این الگوريتم ذرات به يك نقطه خاص که بین بهترین موقعیت عمومي وبهترین موقعيت شخصي قرار دارند همگرا مي شوند. به علت این نقطه ضعف تغييرات زيادي در Pso داده شده است . یکی از این تغییرات وزن اينرسي يا مي باشد . نقطه ضعف دیگر وابستگی این روش به مسأله مي باشد . این وابستگي معمولا نتیجه تغييرات در تنظیم پارامترهاي الگوريتم است . در کل نمیتوان يك پارامتر را براي كليه مسائل به کار برد. يكي از عيب هاي عمده الگوریتم PSO استاندارد در زیر آورده شده است:
فرض شود که ذره در گروه ، داراي سرعت ، موقعیت و بهترین موقعیت ملاقات شده باشد. هر ذره به تنهايي يك بردار N بعدي را نمایش می دهد که معرف يك پاسخ یا راه حل براي مسئله است. گاهي امكان دارد که قسمت هایی از این بردار به پاسخ هاي صحيح نزديك شده باشند در حالي که قسمت های دیگر بردار از پاسخ صحيح دور باشند . بنابراین در کل این ذره مناسب به نظر نمیرسد و باید به موقعیت بهتري برود . امكان دارد که آن قسمت هايي از بردار ذره که به جواب نزديك بوده اند طي به روز نمودن موقعیت ذره جدید ، از پاسخ جدید فاصله بگیرند بنابراین اطلاعات مفید ذره ازبین می رود.
مزایای الگوریتم ازدحام ذرات
PSO مزایای بسیاری نسبت به دیگر روش های بهینه سازی فراابتکاری دارد. از جمله:
- الگوریتم PSO یک الگوریتم مبتنی بر جمعیت است. این خاصیت باعث می شود که کمتر در مینیمم محلی گرفتار شود
- این الگوریتم براساس قوانین احتمالی عمل می کند نه قوانين قطعی. بنابراین، Pso یک الگوریتم بهینه سازی تصادفی است که می تواند نواحی نامشخص و پیچیده را جستجو کند. این خاصیت، PSO را نسبت به روشهای معمولی انعطاف پذیرتر و مقاومتر می کند.
- PSO با توابع هدف غیر دیفرانسیلی سروکار دارد بدلیل اینکه PSO از نتیجه اطلاعات (شاخص بازدهی یا تابع هدف استفاده می کند تا جستجو را در فضای مسئله هدایت کند.
- كيفيت جواب مسیر پیشنهادی به جمعیت اولیه وابسته نیست. با شروع از هر نقطه در فضای جستجو، الگوریتم جواب مسئله را نهایتا به جواب بهينه همگرا می کند.
- PSO انعطاف پذیری زیادی دارد تا تعادل بین جستجوی محلی و کلی از فضای جستجو را کنترل کند. این خاصیت منحصربفرد PSO به مشکل همگرایی بدموقع غلبه می کند و ظرفیت جستجو را افزایش می دهد که همه این خاصيتها Pso را متفاوت از الگوریتم ژنتیک (GA) و دیگر الگوریتمهای ابتکاری می کند.
الگوریتم PSO در بهینه سازی مسائل چندهدفه
در مسائل بهینه سازی چندهدفه ، اهداف چندگانه نیاز به بهینه شدن به طور همزمان دارند. در اغلب موارد، جواب بهینه تکی (مجرد) معمولا نمی تواند یافت شود تا تمام توابع هدف را بهینه سازد. در عوض یک گروه از جوابها وجود دارد که به عنوان مجموعه بهینه پارتو شناخته می شوند. راه حل ها در این گروه در غیاب برتری در میان اهداف، متعادل (برابر) هستند. مساله تصمیم گیری چندهدفه (MODM) از پرکاربردترین حوزه های الگوریتم PSO شده اند. روشهای رایج PSO چندهدفه را می توان به صورت زیر دسته بندی نمود.
روشهای جمعی
در این روش اهداف مساله را به صورت یک هدف واحد ترکیب می کنند (جمع می کنند). به عبارت دیگر، مساله چندهدفه به مساله تک هدفه تبدیل می شود که ایده جدیدی نمی باشد.
روش رتبه بندی اهداف
در روش رتبه بندی اهداف، رتبه هر هدف با توجه به اهمیت آن مشخص می گردد. جواب بهینه با کمینه (یا بیشینه) نمودن توابع هدف به طور جداگانه و با شروع از مهمترین هدف و سپس با در نظر گرفتن اهداف دیگر به ترتیب ارزش آنها به دست می آید. این روش در صورتی که تعداد هدفها كم ( دو یا سه هدف) باشد، می تواند مفید واقع شود.
روش زیرجمعیت
در این روش، جمعیت به چند زیرجمعیت متناسب با تعداد اهداف در نظر گرفته میشود که این زیر جمعیتها به عنوان بهینه کننده های تکهدفه به کار می روند و با هدف ایجاد سنجش بین جواب های تولید شده برای هدفهایی که به طور جداگانه بهینه می شوند، به طریقی اطلاعات را میان خود مبادله یا بازترکیب می کنند.
روش مبتنی بر پارتو
در این دیدگاه از تکنیک انتخاب راهنما استفاده می گردد. جواب های مغلوب نشده به عنوان دسته راهنما در نظر گرفته می شوند. تفاوت این روش ها در انتخاب راهنما از میان جواب های مغلوب نشده برای هر ذره است. این انتخاب می تواند تصادفی و یا به شیوه ای خاص باشد. به عنوان نمونه روش مور و چاپمن که یکی از تحقیقات در این زمینه است را به صورت مختصر شرح می دهیم. الگوریتم ارائه شده توسط این دو نفر که بر اساس بهینه پارتو می باشد، منتشر نشد. آنها بر اهمیت جستجوی فردی و گروهی برای هر ذره تاکید کرده اند. در این روش هر ذره در خط سیر خود لیستی از جواب های یافت شده غیرمغلوب را ذخیره کرده که برای انتخاب بهترین فردی ( p-best) یک ذره از این لیست به طور تصادفی انتخاب میشود. برای انتخاب بهترین کلی ( g-best) از توپولوژی همسایگی حلقه ای استفاده شده است. در این الگوریتم با مقایسه p-best ها، یک جواب غیرمغلوب به عنوان Leader برای ذره انتخاب می شود. البته نویسنده ها در مورد اینکه اگر بیشتر از یک جواب غیرمغلوب در همسایه وجود داشته باشد، توضیحی نداده اند.
مطالب مرتبط و پیشنهادی:
خلاصه و مفید
با تشکر