الگوریتم رقابت استعماری Imperialist Competitive Algorithm

در این پست می خواهیم در مورد الگوریتم رقابت استعماری صحبت کنیم. این الگوریتم در سال 2007 توسط Esmaeil Atashpaz-Gargari و Caro Lucas در کنفرانس Congress on Evolutionary Computation تحت عنوان مقاله Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition منتشر شده است. الگوریتم رقابت استعماری را معمولاً با نام الگوریتم ICA نیز معرفی می کنند. در ادامه به توضیح و تشریح این الگوریتم بهینه سازی و فرا ابتکاری خواهیم پرداخت.

مقدمه

الگوریتم رقابت استعماری (Imperialist Competitive Algorithm ) یا الگوریتم ICA روشی در حوزه محاسبات تکاملی است که برای پیدا کردن پاسخ بهینه مسئله‌های مختلف بهینه‌سازی می‌پردازد. این الگوریتم با مدل‌سازی ریاضی، فرآیند تکامل اجتماعی – سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه‌سازی ارائه می‌دهد.

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

پایه‌های اصلی این الگوریتم را سیاست همسان سازی (Assimilation)، رقابت استعماری (Imperialistic Competition) و انقلاب (Revolution) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدل‌سازی ریاضی بخش‌هایی از این فرآیند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه‌سازی کمک کنند. در واقع این الگوریتم جواب‌های مسئله بهینه‌سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرآیندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.

مراحل الگوریتم رقابت استعماری

مراحل کلی روند الگوریتم به‌صورت زیر است.

1. چند نقطه تصادفی روی تابع انتخاب کرده و امپراتوری‌های اولیه را تشکیل بده.
2. مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی یا جذب).
3. عملگر انقلاب را اعمال کن.
4. اگر مستعمره‌ای در یک امپراتوری وجود داشته باشد که هزینه ای کمتر از امپریالیست داشته باشد جای مستعمره و امپریالیست را عوض کن.
5. هزینه کل یک امپراتوری را حساب کن (با در نظر گرفتن هزینه امپریالیست و مستعمراتشان).
6. یک (چند) مستعمره از ضعیف‌ترین امپراتوری را انتخاب کرده و آن را به امپراتوری که بیشترین احتمال تصاحب را دارد، بده.
7. امپراتوری‌های ضعیف را حذف کن.
8. اگر تنها یک امپراتوری باقیمانده باشد توقف کن و در غیر این صورت به 2 برو.

فلوچارت الگوریتم رقابت استعماری

عملکرد الگوریتم رقابت استعماری

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

سخن پایانی در مورد الگوریتم رقابت استعماری

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