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

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

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

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

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

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

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

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

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

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