بخشی از مقاله
چکیده
در این مقاله ابتدا به معرفی الگوریتم بهینهسازی ذرات خواهیم پرداخت و کاربردهای متنوعی از این الگوریتم را بیان خواهیم کرد. سپس معایب این الگوریتم را بررسی میشوند. به دنبال آن، نسخههای جدید و بهبود یافته این الگوریتم را معرفی میکنیم. بهبودهای مطرح شده در خصوص افزایش سرعت الگوریتم و همچنین جهت جلوگیری بدام افتادن در بهینه محلی میباشد. غالب روشهای پیشنهاد شده برای بهبود الگوریتم بهینهسازی ذرات از دو مکانیزم بهره میبرند. مکانیزم اول تغییر میزان وزن اینرسی است، در حالی که مکانیزم دوم اعمال یکسری مکانیزمهایی مبتنی بر دافعه میباشد که به وسیله آنها میزان تنوع در بین موقعیت ذرات افزایش پیدا کند. افزایش تنوع در بین ذرات یکی از مهم ترین عوامل داشتن یک جستجوی موفق می باشد.
-1 مقدمه
بهینهسازی ذرات - PSO - 1، یک روش بهینهسازی سراسری و فرامکاشفهای است. همچنین الگوریتم PSO یک روش مبتنی بر جمعیت میباشد که از رفتار پرندگان درون یک دسته الهام گرفته است. به هر عضو از این جمعیت، یک ذره گفته میشود .[1] هر ذره نشان دهنده یک نقطه در فضای جستجو است و بیانگر جوابی برای مسئله است. به منظور یافتن جواب بهتر، ذرات بر اساس تجربیات شخصی خودشان و همچنین تجارب سایر اعضاء گروه شروع به حرکت در فضای مسئله میکنند. برای ارزیابی میزان خوب بودن یک جواب - یک ذره - از تابع برازندگی2 استفاده میشود.
همچنین و به ترتیب بهترین موقعیتی است که خود ذره و کل ذرات تا کنون تجربه کردهاند. C1 و C2 اعدادی مثبت هستند که میزان تأثیر تجربیات فردی و گروهی در میزان شتاب ذرات تعیین میکند. همچنین r1 و r2 دو عدد تصادفی در بازه [0,1] میباشند. در رابطه - 1 - به ، مولفه اینرسی3 نیز گفته میشود. مولفه اینرسی بیانگر سرعت و جهت حرکت، ذره در لحظه قبل میباشد. یکی از وظایف مهم مولفه اینرسی آن است که تعادلی بین exploration و exploitation برقرار میکند. لازم به ذکر است که بر اساس تعریف همسایگی، دو نوع داریم:
-1 اگر همه ذرات را همسایه یکدیگر فرض کنیم، آنگاه یک دسته به بزرگی کل جمعیت خواهیم داشت. در نتیجه - بهترین این دسته - ، بهترین کل اعضاء گله - جمعیت - میباشد.
-2 اگر همسایگی را محدود به عواملی همانند مسافت کنیم آنگاه جمعیت به چند زیر دسته تقسیم میشود. هر دسته برای خود یک بهترین دارد. معمولاً در این حالت به ، lBest - بهترین محلی - گفته میشود. دو مدل مطرح شده برای تعیین همسایگی در بالا، مزایا و معایب خاص خود را دارند بعنوان مثال اگر همسایگی برابر با کل جمعیت باشد، آنگاه سرعت همگرایی به هدف بسیار بیشتر خواهد شد. اما از طرف دیگر تعریف همسایگی بصورت محلی سبب میشد که تنوع1 بین عناصر بالا رود. وجود تنوع بین اعضاء گروه سبب میشود که علاوه بر اینکه محیط بیشتری مورد جستجو قرار گیرد، خطر افتادن در بهینه محلی نیز کاهش یابد.
یکی از مهمترین نکاتی که در کارایی الگوریتم بهینهسازی ذرات اثر گذار است، وجود تنوع در بین ذرات در هنگام مقدار دهی اولیه به مختصات ذرات، است. وجود تنوع در بین ذرات به مفهوم آن است که موقعیت ذرات در فضای جستجو متفاوت و متنوع باشد. هر چه تنوع بیشتر باشد، باعث میشود فضای گستردهتری مورد جستجو قرار گیرد. همچنین وجود تنوع در بین ذرات در طول اجرای الگوریتم سبب میشود تا مسئله همگرایی زودرس رخ ندهد.
همگرایی زودرس به این معناست که ذرات به حدی بهم نزدیک میشوند - در اصطلاح به یک تعادل رسیدهاند - که عملاً بردار سرعت آنها رو به صفر شدن میرود و در نتیجه ذرات دیگر حرکت نمیکنند. عدم حرکت ذرات به این معناست که یک جواب برای مسئله پیدا شده است، اگر همگرایی نابهنگام و زودهنگام باشد، این جواب، یک جواب محلی است. از طرفی وجود تنوع در بین ذرات باعث میشود مشکل دیگر الگوریتم PSO که نرخ پایین سرعت همگرایی است، برطرف گردد. بطور خلاصه وجود تنوع در بین ذرات موجب جلوگیری از بدام افتادن در بهینه محلی می شود، همچنین تنوع یکی از الزامات داشتن یک جستجو سالم و موثر است .[3]
