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

الگوریتم رقابت استعماری (Imperialist Competitive Algorithm - ICA) روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینه‌سازی می‌پردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی - سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه‌سازی ارائه می‌دهد. از لحاظ کاربرد، این الگوریتم در دسته الگوریتم‌های بهینه‌سازی تکاملی همچون الگوریتم‌های ژنتیک (Genetic Algorithms)، روش بهینه‌سازی ازدحام ذرات (Particle Swarm Optimization)، الگوریتم کلونی مورچگان (Ant Colony Optimization)، الگوریتم تبرید شبیه‌سازی شده (Simulated Annealing)، الگوریتم تکامل تفاضلی (Differential Evolution)، الگوریتم فرهنگی (Cultural Algorithm)، الگوریتم ممتیک (Memetic Algorithm)، الگوریتم زنبورها (Bees Algorithm)، الگوریتم بهینه‌سازی کاوش مبتنی بر باکتری (Bacterial Foraging Optimization Algorithm) و غیره قرار می‌گیرد. همانند همه الگوریتم‌های قرار گرفته در این دسته، الگوریتم رقابت استعماری نیز مجموعه اولیه‌ای از جوابهای احتمالی را تشکیل می‌دهد. این جوابهای اولیه در الگوریتم ژنتیک با عنوان «کروموزوم»، در الگوریتم ازدحام ذرات با عنوان «ذره» و در الگوریتم رقابت استعماری نیز با عنوان «کشور» شناخته می‌شوند. الگوریتم رقابت استعماری با روند خاصی که در ادامه می‌آید، این جوابهای اولیه (کشورها) را به تدریج بهبود داده و در نهایت جواب مناسب مسئله بهینه‌سازی (کشور مطلوب) را در اختیار می‌گذارد.
پایه‌های اصلی این الگوریتم را سیاست همسان سازی (Assimilation)، رقابت استعماری (Imperialistic Competition) و انقلاب (Revolution) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخشهایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه‌سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه‌سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.
مقدمه
امپریالیسم، در لغت به سیاست توسعه قدرت و نفوذ یک کشور در حوزه خارج از قلمرو شناخته شده برای آن، اطلاق می‌شود. یک کشور می‌تواند کشور دیگر را به طور قانونگذاری مستقیم یا از طریق روش‌های غیر مستقیم، مثل کنترل کالاها و مواد خام، کنترل کند. مورد اخیر اغلب استعمار نو خوانده می‌شود. استعمار یک پدیده ذاتی در تاریخ بوده‌است. استعمار در مراحل ابتدایی، به صورت نفوذ سیاسی‌نظامی در کشورها و به صورت صرف استفاده از منابع زمینی، انسانی و سیاسی بوده‌است. بعضی مواقع نیز استعمار، به صرف جلوگیری از نفوذ کشور استعمارگر رقیب انجام می‌شد. به هر حال کشورهای استعمارگر رقابت شدیدی را برای به استعمار کشیدن مستعمرات همدیگر نشان می‌دادند.
مستقل از اثرات و تبعات مثبت و منفی آن، استعمار به عنوان یک فرایند ذاتی در تاریخ بشر ایجاد شد، و در عین وارد کردن خسارتهای جبران ناپذیر به زیربناهای اساسی یک کشور (خصوصا زیربناهای فرهنگی) در بعضی موارد اثرات مثبتی را نیز برای کشورها مستعمره داشت. از دید بهینه‌سازی، استعمار بعضی از کشورها را که در یک دره معمولی تمدن قرار داشتند، خارج کرده و آنها را به یک حوزه مینیمم دیگر برد که در بعضی موارد وضعیت این حوزه مینیمم بهتر از موقعیت قبلی کشور مستعمره بود. اما به هر حال این حرکت مستلزم پیشروی مستعمره در راستای محورهای مختلف اقتصادی و فرهنگی به سمت یک امپریالیست قویتر بود، یعنی از میان رفتن بعضی از ساختارهای فرهنگی و اجتماعی. شکل زیر حرکت یک مستعمره به سمت استعمارگر قوی را نشان می‌دهد. این روند در الگوریتم رقابت استعماری در قالب سیاست جذب مدلسازی می‌شود.
حرکت یک کشور مستعمره به سمت استعمار گر
همانند دیگر الگوریتم‌های تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هر کدام از آنها یک «کشور» نامیده می‌شوند؛ شروع می‌شود. تعدادی از بهترین عناصر جمعیت (معادل نخبه‌ها در الگوریتم ژنتیک) به عنوان استعمارگر انتخاب می‌شوند. باقی‌مانده جمعیت نیز به عنوان مستعمره، در نظر گرفته می‌شوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یک روند خاص که در ادامه می‌آید؛ به سمت خود می‌کشند. قدرت کل هر امپراطوری، به هر دو بخش تشکیل دهنده آن یعنی کشور استعمارگر (به عنوان هسته مرکزی) و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراطوری به صورت مجوع قدرت کشور استعمارگر به اضافه در صدی از میانگین قدرت مستعمرات آن، مدل شده‌است.
با شکل‌گیری امپراطوری‌های اولیه، رقابت استعماری میان آن‌ها شروع می‌شود. هر امپراطوری‌ای که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید (و یا حداقل از کاهش نفوذش جلوگیری کند)، از صحنه رقابت استعماری، حذف خواهد شد؛ بنابراین بقای یک امپراطوری، وابسته به قدرت آن در جذب مستعمرات امپراطوری‌های رقیب، و به سیطره درآوردن آنها خواهد بود. در نتیجه، در جریان رقابت‌های استعماری، به تدریج بر قدرت امپراطوری‌های بزرگتر افزوده شده و امپراطوری‌های ضعیف‌تر، حذف خواهند شد. امپراطوری‌ها برای افزایش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نیز پیشرفت دهند.
به طور خلاصه این الگوریتم به استعمار به عنوان بخش تفکیک‌ناپذیر از سیر تکامل تاریخی بشر نگریسته شده و از چگونگی اثرگذاری آن بر کشورهای استعمارگر و مستعمره و نیز کل تاریخ، به عنوان منبع الهام یک الگوریتم کارا و نو در زمینه محاسبات تکاملی استفاده شده‌است.
شکل دهی امپراطوری‌های اولیه
در بهینه‌سازی، هدف یافتن یک جواب بهینه بر حسب متغیرهای مسئله، است. ما یک آرایه از متغیرهای مسئله را که باید بهینه شوند، ایجاد می‌کنیم. در الگوریتم ژنتیک این آرایه، کروموزوم نامیده می‌شود. در اینجا نیز آن را یک کشور می‌نامیم. در یک مسئله بهینه‌سازی N var بعدی، یک کشور، یک آرایه به طول N var * ۱ است. این آرایه به صورت زیر تعریف می‌شود.
country =
مقادیر متغیره‌ها در یک کشور، به صورت اعداد اعشاری نمایش داده می‌شوند. از دیدگاه تاریخی‌فرهنگی، اجزای تشکیل دهنده یک کشور را می‌توان ویژگی‌های اجتماعی– سیاسی آن کشور، همچون فرهنگ، زبان، ساختار اقتصادی و سایر ویژگی‌ها در نظر گرفت. شکل زیر نحوه تناظر متغیرهای بهینه‌سازی مسئله با ویژگی‌های اجتماعی سیاسی را نشان می‌دهد.
تناظر متغیرهای بهینه‌سازی مسئله با ویژگی‌های اجتماعی سیاسی
برای شروع الگوریتم، تعداد N country کشور اولیه را ایجاد می‌کنیم. تا N imp از بهترین اعضای این جمعیت (کشورهای دارای کمترین مقدار تابع هزینه) را به عنوان امپریالیست انتخاب می‌کنیم. باقی‌مانده N col تا از کشورها، مستعمراتی را تشکیل می‌دهند که هرکدام به یک امپراطوری تعلق دارند. برای تقسیم مستعمرات اولیه بین امپریالست‌ها، به هر امپریالیست، تعدادی از مستعمرات را که این تعداد، متناسب با قدرت آن است، می‌دهیم. در شکل زیر نحوه تقسیم مستعمرات، میان کشورهای استعمارگر به صورت نمادین نشان داده شده است.
نحوه تقسیم مستعمرات، میان کشورهای استعمارگر
سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست
سیاست همگون‌سازی (جذب) با هدف تحلیل فرهنگ و ساختار اجتماعی مستعمرات در فرهنگ حکومت مرکزی انجام می‌گرفت. همانگونه که قبلا نیز بیان شد، کشورهای استعمارگر، برای افزایش نفوذ خود، شروع به ایجاد عمران (ایجاد زیرساخت‌های حمل و نقل، تاسیس دانشگاه و …) کردند. به عنوان مثال کشورهایی نظیر انگلیس و فرانسه با تعقیب سیاست همگون‌سازی در مستعمرات خود در فکر ایجاد انگیس نو و فرانسه نو در مستعمرات خویش بودند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسلئه بهینه‌سازی، در حقیقت این حکومت مرکزی با اعمال سیاست جذب سعی داشت تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی سیاسی به خود نزدیک کند. این بخش از فرایند استعمار در الگوریتم بهینه‌سازی، به صورت حرکت مستعمرات به سمت کشور امپریالیست، مدل شده‌است.
در راستای این سیاست، کشور مستعمره (Colony)، به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعیت جدید (New Position of Colony)، کشانده می‌شود. x عددی تصادفی با توزیع یکنواخت (و یا هر توزیع مناسب دیگر) می‌باشد. اگر فاصله میان استعمارگر و مستعمره با d نشان داده شود، معمولا برای d داریم.
x ~ U(0,ß*d)
که در آن ß عددی بزرگتر از یک و نزدیک به ۲ می‌باشد. یک انتخاب مناسب می‌تواند ß=۲ باشد. وجود ضریب ß≥۱ باعث می‌شود تا کشور مستعمره در حین حرکت به سمت کشور استعمارگر، از جهت‌های مختلف به آن نزدیک شود. همچنین در کنار این حرکت، یک انحراف زاویه‌ای کوچک نیز با توزیع یکنواخت به مسیر حرکت افزوده می‌شود. یک نمای گرافیکی از اعمال سیاست جذب در الگوریتم رقابت استعماری در صفحه دو بعدی در زیر نشان داده شده است.
اعمال سیاست جذب در الگوریتم رقابت استعماری
انقلاب؛ تغییرات ناگهانی در موقعیت یک کشور
بروز انقلاب تغییرات ناگهانی را در ویژگی‌های اجتماعی سیاسی یک کشور ایجاد می‌کند. در الگوریتم رقابت استعماری، انقلاب با جابجایی تصادفی یک کشور مستعمره به یک موقعیت تصادفی جدید مدلسازی می‌شود. انقلاب از دیدگاه الگوریتمی باعث می‌شود کلیت حرکت تکاملی از گیر کردن در دره‌های محلی بهینگی نجات یابد که در بعضی موارد باعث بهبود موقعیت یک کشور شده و آن را به یک محدوده بهینگی بهتری می‌برد.
اعمال سیاست انقلاب
جابجایی موقعیت مستعمره و امپریالیست
در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن بعضی از این مستعمرات به موقعیتی بهتر از امپریالیست برسند (به نقاطی در تابع هزینه برسند که هزینه کمتری را نسبت به مقدار تابع هزینه در موقعیت امپریالیست، تولید می‌کنند) در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با همدیگر عوض کرده و الگوریتم با کشور استعمارگر در موقعیت جدید ادامه یافته و این این بار این کشور امپریالیست جدید است که شروع به اعمال سیاست همگون‌سازی بر مستعمرات خود می‌کند. نحوه جابجایی موقعیت مستعمره و استعمارگر در شکل زیر نشان داده شده است.
جابجایی موقعیت مستعمره و استعمارگر
رقابت استعماری
قدرت یک امپراطوری به صورت قدرت کشور استعمارگر، به اضافه درصدی از قدرت کل مستعمرات آن تعریف می‌شود.
هر امپراطوری‌ای که نتواند بر قدرت خود بیفزاید و قدرت رقابت خود را از دست بدهد، در جریان رقابت‌های امپریالیستی، حذف خواهد شد. این حذف شدن، به صورت تدریجی صورت می‌پذیرد. بدین معنی که به مرور زمان، امپراطوری‌های ضعیف، مستعمرات خود را از دست داده و امپراطوری‌های قویتر، این مستعمرات را تصاحب کرده و بر قدرت خویش می‌افزایند. در الگوریتم رقابت استعماری، امپراطوری در حال حذف، ضعیف‌ترین امپراطوری موجود است. بدین ترتیب، در تکرار الگوریتم، یکی یا چند مورد از ضعیف‌ترین مستعمرات ضعیف‌ترین امپراطوری را برداشته و برای تصاحب این مستعمرات، رقابتی را میان کلیه امپراطوری‌ها ایجاد می‌کنیم. مستعمرات مذکور، لزوما توسط قویترین امپراطوری، تصاحب نخواهند شد، بلکه امپراطوری‌های قویتر، احتمال تصاحب بیشتری دارند. رقابت استعماری میان چندین استعمار گر برای جذب مستعمرات همدیگر در شکل زیر به خوبی نشان داده شده است.
رقابت استعماری میان چندین استعمارگر
سقوط امپراطوری‌های ضعیف
در جریان رقابت‌های امپریالیستی، خواه ناخواه، امپراطوریهای ضعیف به تدریج سقوط کرده و مستعمراتشان به دست امپراطوری‌های قوی‌تر می‌افتد. شروط متفاوتی را می‌توان برای سقوط یک امپراطوری در نظر گرفت. در الگوریتم پیشنهاد شده، یک امپراطوری زمانی حذف شده تلقی می‌شود که مستعمرات خود را از دست داده باشد. شکل زیر یک نمای کلی از سقوط امپراطوری‌ها در روند چرخه الگوریتم، ارائه می‌دهد.
سقوط امپراطوری‌ها در روند چرخه الگوریتم رقابت استعماری
شبه کد
مراحل ذکر شده در بالا را می‌توان به صورت شبه کد ریز خلاصه کرد.
چند نقطه تصادفی روی تابع انتخاب کرده و امپراطوری‌های اولیه را تشکیل بده.
مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی یا جذب).
عملگر انقلاب (Revolution) را اعمال کن.
اگر مستعمره‌ای در یک امپراطوری، وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد؛ جای مستعمره و امپریالیست را با هم عوض کن.
هزینه کل یک امپراطوری را حساب کن (با در نظر گرفتن هزینه امپریالیست و مستعمراتشان).
یک (یا چند) مستعمره از ضعیف‌ترین امپراطوری انتخاب کرده و آن را به امپراطوری‌ای که بیشترین احتمال تصاحب را دارد، بده.
امپراطوری‌های ضعیف را حذف کن.
اگر تنها یک امپراطوری باقی‌مانده باشد، توقف کن وگرنه به ۲ برو.
روند کامل الگوریتم رقابت استعماری را می‌توان با فلوچارت زیر نشان داد. نکته قابل توجه این است که در این فلوچارت، بخش انقلاب نشان داده نشده است که باید به مرحله مناسب خود اعمال گردد.
فلوچارت الگوریتم رقابت استعماری
کاربردها
در حالت کلی الگوریتم رقابت استعماری به هر نوع مسئله بهینه‌سازی بدون هیچ محدودیتی قابل اعمال است. همین موضوع باعث شده‌است تا از این الگوریتم در حل مسائل بسیاری در حوزه مهندسی برق، مکانیک، صنایع، مدیریت، عمران، هوش مصنوعی و غیره استفاده شود. به عنوان مثال از این الگوریتم با موفقیت در حل مسائل عملی بهینه‌سازی زیر استفاده شده‌است.
طراحی بهینه کنترل کننده برای سیستمهای صنعتی همچون سیستم چند ورودی - چند خروجی تبرید و صنعتی ستون تقطیر
طراحی بهینه سیستم‌های پیشنهاد دهی هوشمند
طراحی بهینه آنتن‌های آرایه‌ای
حل مسائل برنامه‌ریزی تولید در حوزه مهندسی صنایع و مدیریت
یادگیری و تحلیل شبکه‌های عصبی مصنوعی
طراحی بهینه موتورهای القای خطی
طراحی استراتژی بهینه در نظریه بازیها برای رسیدن به نقطه تعادل نش
طراحی بهینه کنترل کننده‌های فازی
انتخاب و بهینه‌سازی سبد سهام
طراحی و بهینه‌سازی ترمودینامیکی مبدل‌های حرارتی صفحه-پره
نسخه‌های دیگر
موارد ذکر شده در این نوشتار، مربوط به نسخه اولیه ارائه شده از الگوریتم رقابت استعماری می‌باشد. پس از معرفی این الگوریتم که ابتدا فقط برای حل مسائل بهینه‌سازی پیوسته استفاده می‌شد، نسخه‌های دیگری نیز معرفی شدند که به حل مسائل گسسته و نیز ترکیبی می‌پرداختند. بسیاری از مقالات و انتشارات مربوط به این الگوریتم که در آنها این نسخه معرفی شده‌اند، در لیست شده‌اند. به عنوان مثال نسخه آشوبی این الگوریتم توسط Duan و دیگران در یکی از مقالات بخش مراجع در زیر معرفی شده است.
مطالعه بیشتر