شکل 3-10- سقوط امپراطوری ضعیف؛ امپراطوری شماره 4، به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوریها حذف شود. ]37 [
شبه کد مربوط به الگوریتم پیشنهادی در قسمت زیر آمده است.
1-چند نقطه تصادفی روی تابع انتخاب کرده و امپراطوریهای اولیه را تشکیل بده.
2- مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی)
3-اگر مستعمره‌ای در یک امپراطوری، وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد؛ جای مستعمره و امپریالیست را باهم عوض کن.
4-هزینه‌ی کل یک امپراطوری را حساب کن (با در نظر گرفتن هزینه‌ی امپریالیست و مستعمراتشان).
5-یک مستعمره از ضعیف‌ترین امپراطوری انتخاب کرده و آن را به امپراطوری ای که بیشترین احتمال تصاحب را دارد، بده.
6- امپراطوریهای ضعیف را حذف کن.
7- اگر تنها یک امپراطوری باقی‌مانده باشد، توقف کن وگرنه به 2 برو.
3-4- الگوریتم رقابت استعماری اصلاحی
چون ICA یک روش تکاملی است، پس در ابتدا باید بهوسیله تعدادی کشور (جمعیت اولیه) شروع کار کند. بنابراین p جمعیت اولیه تصادفی برای مسأله ایجاد میشود و مقادیر تابع هدف f(i)، کشورهایی که دارای مقادیر تابع هدف کمتر برای مسأله مربوطه هستند، به‌عنوان کشورهای استعمارگر در نظر گرفته میشوند و با جابجایی، اندیسهای 1 تا m جمعیت اولیه را تشکیل میدهند. سپس به هرکدام از کشورهای استعمارگر، تعدادی مساوی از کشورهای مستعمره اختصاص مییابند به‌علاوه، به علت خاصیت تابع جزء صحیح، بقیه کشورها نیز به قویترین امپراطوری اختصاص مییابند. باید توجه داشت که اختصاص یافتن هر کشور مستعمره به کشور استعمارگر بهطور تصادفی و با احتمال برابر است. طبق حالت طبیعی که وجود دارد باید کشورهای مستعمره ازلحاظ فرهنگی و اجتماعی به سمت کشورهای استعمارگر با استفاده از تابع جذب حرکت کنند. بنابراین در این الگوریتم]38 [ از روش نزدیکترین همسایه تصادفی(بهبود دهنده دونقطهای) برای تابع جذب استفاده میشود. با توجه به شکل 3-11 اگر در این روش [4 2 5 3 1] نشاندهنده کشور مستعمره و [5 2 1 4 3] نشاندهنده کشور استعمارگر باشد، برای مسأله توالی پرواز با 5 مشخصه الگوریتم از اولین گره کشور مستعمره که 1 است، شروع به حرکت میکند. سپس i=1 در نظر گرفته میشود و همسایههای ملاقات نشده 1 در دو کشور با گرههای 4،3 و 2 را درمجموعه S قرار میدهد. حال، اگر c(ij) نشاندهنده فاصله بین دو گره i و j باشد، آنگاه گرههای متعلق به S به‌احتمال v(j) مورد ملاقات قرار میگیرند.
(3-11)
فرض کنیم گره 2 برگزیده شود؛ پس در جمعیت اولیه تاکنون [ – – 2 1] به وجود میآید. بهعلاوه برای 2، سه گره 4، 1 و 5 به‌عنوان همسایه محسوب میشوند؛ اما چون قبلاً 1 مورد ملاقات قرارگرفته شده است، از بین 4 و 5 که مجموعه S را تشکیل میدهند، نزدیکترین همسایه تصادفی انتخاب میگردد (باید توجه کرد که اگر مجموعه S در مرحلهای تهی شد، آنگاه گرههای تاکنون ملاقات نشده در آن قرار میگیرند). این روش سبب میگردد که به علت ممنوع شدن انتخاب کشورهای قبلاً ملاقات شده، حتماً یک جواب شدنی برای مسأله به دست آید. باید توجه کرد که جواب به‌دست‌آمده در صورتی جایگزین جواب کشور مستعمره میشود که دارای مقدار تابع هدف بهتر باشد. از طرف دیگر استفاده از این روش سبب میگردد که علاوه بر اینکه کیفیت مقادیر تابع هدف کشورهای مستعمره طبق این روال افزایش یابد، تنوع کشورهای مستعمره به علت ساختار تصادفی تابع جذب حفظ شود.

مطلب مرتبط :   مقاله نگهداری وجه نقد و جریان نقدی آزاد

شکل 3-11 گراف همسایگی با پنج گره
بعدازاینکه تابع جذب برای همه کشورهای مستعمره نسبت به کشورهای استعمارگر انجام شد،p درصد از کشورهای مستعمره دچار انقلاب میشوند. برای این عمل از روش بهبوددهنده استفاده میشود. این روش، بر اساس انتخاب دو گره از مسأله و تعویض آن‌ها باهم کار میکند. باید توجه کرد که p درصد کشورهای هر امپراطوری بهتصادف انتخاب و این روش روی آن‌ها انجام میشود. حال، جواب‌های جدید به‌دست‌آمده از انقلاب به همراه کشورهای مستعمره امپراطوری j-ام در نظر گرفته میشوند و بهترین جوابها بهعنوان کشورهای مستعمره امپراطوری j-ام انتخاب میشوند. بعدازاینکه مقدار تابع هدف برای تمامی کشورهای مستعمره به دست آمد، امکان دارد که این کشورها دارای تابع هدف بهتری نسبت به کشورهای استعمارگر امپراطوری خود شوند. بنابراین بهترین کشورهای مستعمره در هر امپراطوری انتخاب‌شده و در صورت داشتن تابع هدف بهتر، جایگزین کشور استعمارگر میشوند.
توجه به این نکته ضروری است که در اجرای الگوریتم دو متغیر وجود دارند که مقادیر بهترین جواب و مقدار تابع هدف را ذخیره میکنند. این دو متغیر بعد از بروز شدن استعمارگرها بررسی میشوند.
در این مرحله بهترین جواب و مقدار تابع هدف کشورهای استعمارگر انتخاب‌شده و الگوریتم بهبوددهنده سهگانه بر روی آن انجام میشود و سپس مقدار به‌دست‌آمده اگر از بهترین مقدار به‌دست‌آمده در تکرارهای قبلی بهتر باشد، آن جواب و مقدار تابع هدف جایگزین میشوند. با توجه به شکل 3-12روش بهبوددهنده سهگانه بر اساس حذف کردن سه یال از تور و متصل کردن دوبارهی مشخصهای انجام میگیرد.

(3) (2) (1)
شکل 3-12 بهبوددهنده سهگانه