بالاترین سوالات
زمانبندی
چت
دیدگاه

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

از ویکی‌پدیا، دانشنامه آزاد

Remove ads

الگوریتم رقابت استعماری (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) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخش‌هایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه‌سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه‌سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.[۳]

Remove ads

مقدمه

خلاصه
دیدگاه

امپریالیسم در لغت به سیاست توسعه قدرت و نفوذ یک کشور در حوزه خارج از قلمرو شناخته شده برای آن گفته می‌شود. یک کشور می‌تواند کشور دیگر را به‌طور قانونگذاری مستقیم یا از طریق روش‌های غیر مستقیم مثل کنترل کالاها و مواد خام کنترل کند. مورد اخیر اغلب استعمار نو خوانده می‌شود.[۴] استعمار یک پدیده ذاتی در تاریخ بوده‌است. استعمار در مراحل ابتدایی، به صورت نفوذ سیاسی‌نظامی در کشورها و به صورت صرف استفاده از منابع زمینی، انسانی و سیاسی بوده‌است. بعضی مواقع نیز استعمار، به صرف جلوگیری از نفوذ کشور استعمارگر رقیب انجام می‌شد. به هر حال کشورهای استعمارگر رقابت شدیدی را برای به استعمار کشیدن مستعمرات همدیگر نشان می‌دادند.[۵]

مستقل از اثرات و تبعات مثبت و منفی آن، استعمار به عنوان یک فرایند ذاتی در تاریخ بشر ایجاد شد، و در عین وارد کردن خسارتهای جبران ناپذیر به زیربناهای اساسی یک کشور (خصوصاً زیربناهای فرهنگی) در بعضی موارد اثرات مثبتی را نیز برای کشورها مستعمره داشت.[۶] از دید بهینه‌سازی، استعمار بعضی از کشورها را که در یک دره معمولی تمدن قرار داشتند، خارج کرده و آن‌ها را به یک حوزه مینیمم دیگر برد که در بعضی موارد وضعیت این حوزه مینیمم بهتر از موقعیت قبلی کشور مستعمره بود. اما به هر حال این حرکت مستلزم پیشروی مستعمره در راستای محورهای مختلف اقتصادی و فرهنگی به سمت یک امپریالیست قویتر بود، یعنی از میان رفتن بعضی از ساختارهای فرهنگی و اجتماعی. شکل زیر حرکت یک مستعمره به سمت استعمارگر قوی را نشان می‌دهد. این روند در الگوریتم رقابت استعماری در قالب سیاست جذب مدلسازی می‌شود.

Thumb
حرکت یک کشور مستعمره به سمت استعمار گر

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

با شکل‌گیری امپراطوری‌های اولیه، رقابت استعماری میان آن‌ها شروع می‌شود. هر امپراطوری‌ای که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید (و یا حداقل از کاهش نفوذش جلوگیری کند)، از صحنه رقابت استعماری، حذف خواهد شد؛ بنابراین بقای یک امپراطوری، وابسته به قدرت آن در جذب مستعمرات امپراطوری‌های رقیب، و به سیطره درآوردن آن‌ها خواهد بود. در نتیجه، در جریان رقابت‌های استعماری، به تدریج بر قدرت امپراطوری‌های بزرگتر افزوده شده و امپراطوری‌های ضعیف‌تر، حذف خواهند شد. امپراطوری‌ها برای افزایش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نیز پیشرفت دهند.[۳]

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

Remove ads

شکل دهی امپراطوری‌های اولیه

خلاصه
دیدگاه

در بهینه‌سازی، هدف یافتن یک جواب بهینه بر حسب متغیرهای مسئله، است. ما یک آرایه از متغیرهای مسئله را که باید بهینه شوند، ایجاد می‌کنیم. در الگوریتم ژنتیک این آرایه، کروموزوم نامیده می‌شود. در اینجا نیز آن را یک کشور می‌نامیم. در یک مسئلهٔ بهینه‌سازی Nvar بعدی، یک کشور، یک آرایه به طول Nvar * ۱ است. این آرایه به صورت زیر تعریف می‌شود.

country = [p1, p2, ..., pNvar]

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

Thumb
تناظر متغیرهای بهینه‌سازی مسئله با ویژگی‌های اجتماعی سیاسی

برای شروع الگوریتم، تعداد Ncountry کشور اولیه را ایجاد می‌کنیم. تا Nimp از بهترین اعضای این جمعیت (کشورهای دارای کمترین مقدار تابع هزینه) را به عنوان امپریالیست انتخاب می‌کنیم. باقی‌مانده Ncol تا از کشورها، مستعمراتی را تشکیل می‌دهند که هرکدام به یک امپراطوری تعلق دارند. برای تقسیم مستعمرات اولیه بین امپریالست‌ها، به هر امپریالیست، تعدادی از مستعمرات را که این تعداد، متناسب با قدرت آن است، می‌دهیم. در شکل زیر نحوه تقسیم مستعمرات، میان کشورهای استعمارگر به صورت نمادین نشان داده شده‌است.[۳]

Thumb
نحوه تقسیم مستعمرات، میان کشورهای استعمارگر
Remove ads

سیاست جذب: حرکت مستعمره‌ها به سمت امپریالیست

خلاصه
دیدگاه

سیاست همگون‌سازی (جذب) با هدف تحلیل فرهنگ و ساختار اجتماعی مستعمرات در فرهنگ حکومت مرکزی انجام می‌گرفت. همانگونه که قبلاً نیز بیان شد، کشورهای استعمارگر، برای افزایش نفوذ خود، شروع به ایجاد عمران (ایجاد زیرساخت‌های حمل و نقل، تأسیس دانشگاه و …) کردند. به عنوان مثال کشورهایی نظیر انگلیس و فرانسه با تعقیب سیاست همگون‌سازی در مستعمرات خود در فکر ایجاد انگیس نو و فرانسه نو در مستعمرات خویش بودند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسلئه بهینه‌سازی، در حقیقت این حکومت مرکزی با اعمال سیاست جذب سعی داشت تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی سیاسی به خود نزدیک کند. این بخش از فرایند استعمار در الگوریتم بهینه‌سازی، به صورت حرکت مستعمرات به سمت کشور امپریالیست، مدل شده‌است.[۳]

در راستای این سیاست، کشور مستعمره (Colony)، به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعیت جدید (New Position of Colony)، کشانده می‌شود. x عددی تصادفی با توزیع یکنواخت (و یا هر توزیع مناسب دیگر) می‌باشد. اگر فاصله میان استعمارگر و مستعمره با d نشان داده شود، معمولاً برای d داریم.

Thumb
اعمال سیاست جذب در الگوریتم رقابت استعماری

x ~ U(0,ß*d)

که در آن ß عددی بزرگتر از یک و نزدیک به ۲ می‌باشد. یک انتخاب مناسب می‌تواند ß=۲ باشد. وجود ضریب ß≥۱ باعث می‌شود تا کشور مستعمره در حین حرکت به سمت کشور استعمارگر، از جهت‌های مختلف به آن نزدیک شود. همچنین در کنار این حرکت، یک انحراف زاویه‌ای کوچک نیز با توزیع یکنواخت به مسیر حرکت افزوده می‌شود. یک نمای گرافیکی از اعمال سیاست جذب در الگوریتم رقابت استعماری در صفحه دو بعدی در زیر نشان داده شده‌است.[۳]

انقلاب؛ تغییرات ناگهانی در موقعیت یک کشور

Thumb
اعمال سیاست انقلاب
Thumb
جابجایی موقعیت مستعمره و استعمارگر

بروز انقلاب تغییرات ناگهانی را در ویژگی‌های اجتماعی سیاسی یک کشور ایجاد می‌کند. در الگوریتم رقابت استعماری، انقلاب با جابجایی تصادفی یک کشور مستعمره به یک موقعیت تصادفی جدید مدلسازی می‌شود. انقلاب از دیدگاه الگوریتمی باعث می‌شود کلیت حرکت تکاملی از گیر کردن در دره‌های محلی بهینگی نجات یابد که در بعضی موارد باعث بهبود موقعیت یک کشور شده و آن را به یک محدوده بهینگی بهتری می‌برد.[۳]

Remove ads

جابجایی موقعیت مستعمره و امپریالیست

در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن بعضی از این مستعمرات به موقعیتی بهتر از امپریالیست برسند (به نقاطی در تابع هزینه برسند که هزینه کمتری را نسبت به مقدار تابع هزینه در موقعیت امپریالیست، تولید می‌کنند) در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با همدیگر عوض کرده و الگوریتم با کشور استعمارگر در موقعیت جدید ادامه یافته و این بار این کشور امپریالیست جدید است که شروع به اعمال سیاست همگون‌سازی بر مستعمرات خود می‌کند.[۳] نحوه جابجایی موقعیت مستعمره و استعمارگر در شکل زیر نشان داده شده‌است.

Remove ads

رقابت استعماری

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

Thumb
رقابت استعماری میان چندین استعمارگر

هر امپراطوری‌ای که نتواند بر قدرت خود بیفزاید و قدرت رقابت خود را از دست بدهد، در جریان رقابت‌های امپریالیستی، حذف خواهد شد. این حذف شدن، به صورت تدریجی صورت می‌پذیرد. بدین معنی که به مرور زمان، امپراطوری‌های ضعیف، مستعمرات خود را از دست داده و امپراطوری‌های قویتر، این مستعمرات را تصاحب کرده و بر قدرت خویش می‌افزایند. در الگوریتم رقابت استعماری، امپراطوری در حال حذف، ضعیف‌ترین امپراطوری موجود است. بدین ترتیب، در تکرار الگوریتم، یکی یا چند مورد از ضعیف‌ترین مستعمراتِ ضعیف‌ترین امپراطوری را برداشته و برای تصاحب این مستعمرات، رقابتی را میان کلیه امپراطوری‌ها ایجاد می‌کنیم. مستعمرات مذکور، لزوماً توسط قویترین امپراطوری، تصاحب نخواهند شد، بلکه امپراطوری‌های قوی‌تر، احتمال تصاحب بیشتری دارند. رقابت استعماری میان چندین استعمارگر برای جذب مستعمرات همدیگر در شکل زیر به خوبی نشان داده شده‌است.[۳]

Remove ads

سقوط امپراطوری‌های ضعیف

Thumb
سقوط امپراطوری‌ها در روند چرخه الگوریتم رقابت استعماری

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

Remove ads

شبه کد

مراحل ذکر شده در بالا را می‌توان به صورت شبه کد ریز خلاصه کرد.[۳]

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

روند کامل الگوریتم رقابت استعماری را می‌توان با فلوچارت زیر نشان داد. نکته قابل توجه این است که در این فلوچارت، بخش انقلاب نشان داده نشده‌است که باید به مرحله مناسب خود اعمال گردد.

Remove ads

کاربردها

در حالت کلی، الگوریتم رقابت استعماری به هر نوع مسئله بهینه‌سازی بدون هیچ محدودیتی قابل اعمال است. همین موضوع باعث شده‌است تا از این الگوریتم در حل مسائل بسیاری در حوزه مهندسی برق، مکانیک، صنایع، مدیریت، عمران، هوش مصنوعی و غیره استفاده شود. به عنوان مثال از این الگوریتم با موفقیت در حل مسائل عملی بهینه‌سازی زیر استفاده شده‌است.

نسخه‌های دیگر

موارد ذکر شده در این نوشتار، مربوط به نسخه اولیه ارائه شده از الگوریتم رقابت استعماری می‌باشد. پس از معرفی این الگوریتم که ابتدا فقط برای حل مسائل بهینه‌سازی پیوسته استفاده می‌شد، نسخه‌های دیگری نیز معرفی شدند که به حل مسائل گسسته و نیز ترکیبی می‌پرداختند. بسیاری از مقالات و انتشارات مربوط به این الگوریتم که در آن‌ها این نسخه معرفی شده‌اند، در این لینک لیست شده‌اند. به عنوان مثال نسخه آشوبی این الگوریتم توسط Duan و دیگران در یکی از مقالات بخش مراجع در زیر معرفی شده‌است.[۲۷]

Remove ads

برای مطالعهٔ بیشتر

Remove ads

منابع

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads