تلفیق الگوریتم رقابت استعماری و انتخاب سریع زمان آماده سازی در حل مسأله برنامه …

 
شکل ۳-۴- چگونگی شکل‌گیری امپراطوریهای اولیه ]۳۷ [
۳-۳-۲- مدلسازی سیاست جذب
سیاست همگون سازی (جذب (باهدف تحلیل فرهنگ و ساختار اجتماعی مستعمرات در فرهنگ حکومت مرکزی انجام می‌گرفت. همان‌گونه که قبلاً نیز بیان شد، کشورهای استعمارگر، برای افزایش نفوذ خود، شروع به ایجاد عمران (ایجاد زیرساخت‌های حمل‌ونقل، تأسیس دانشگاه و …) کردند. به‌عنوان‌مثال کشورهایی نظیر انگلیس و فرانسه با تعقیب سیاست همگون سازی در مستعمرات خود در فکر ایجاد انگلیس نو و فرانسه نو در مستعمرات خویش بودند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسأله بهینه‌سازی، در حقیقت این حکومت مرکزی با اعمال سیاست جذب سعی داشت تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی سیاسی به خود نزدیک کند.
این بخش از فرایند استعمار در الگوریتم بهینهسازی، به‌صورت حرکت مستعمرات به سمت کشور امپریالیست، مدل شده است. شکل ۳-۵ شمای کلی این حرکت را نشان می‌دهد.
 
شکل ۳-۵- شمای کلی حرکت مستعمرات به سمت امپریالیست ]۳۷ [
مطابق این شکل کشور امپریالیست کشور مستعمره را در راستای محورهای فرهنگ و زبان به سمت خود جذب می‌کند. همان‌گونه که در این شکل نشان داده‌شده است، کشور مستعمره (Colony)، به‌اندازه x واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعیت جدیدColony) (New Position of کشانده می‌شود. در این شکل، فاصله میان استعمارگر و مستعمره با d نشان داده‌شده است x نیز عددی تصادفی با توزیع یکنواخت (و یا هر توزیع مناسب دیگر) می‌باشد. یعنی برای x داریم:
که در آن β عددی بزرگ‌تر از ۱ و نزدیک به ۲ می‌باشد.
یک انتخاب مناسب می‌تواند β =۲ باشد. وجود ضریب β >1 باشد باعث می‌شود تا کشور مستعمره در حین حرکت به سمت کشور استعمارگر، از جهت‌های مختلف به آن نزدیک شود.
 
شکل ۳-۶- حرکت واقعی مستعمرات به سمت امپریالیست ]۳۷ [
با بررسی تاریخی پدیده همگون سازی، یک حقیقت آشکار در این زمینه این است که علی‌رغم اینکه کشوهای استعمارگر به‌طورجدی پیگیر سیاست جذب بودند، اما وقایع به‌طور کامل مطابق سیاست اعمال‌شده آن‌ها پیش نمی‌رفت و انحرافاتی درنتیجه کار وجود داشت. در الگوریتم معرفی‌شده، این انحراف احتمالی با افزودن یک زاویه تصادفی به مسیر جذب مستعمرات، انجام میگیرد. بدین منظور، درحرکت مستعمرات به سمت استعمارگر، کمی زاویه تصادفی نیز به جهت حرکت مستعمره، اضافه می‌کنیم.
شکل ۳-۶ این حالت را نشان می‌دهد. بدین منظور این بار به‌جای حرکت به‌اندازه x به سمت، کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان میزان، ولی با انحراف θ در مسیر، به حرکت خود ادامه می‌دهیم θ را به‌صورت تصادفی و با توزیع یکنواخت در نظر میگیریم (اما هر توزیع دلخواه و مناسب دیگر نیز میتواند استفاده شود). پس در این رابطه γ پارامتری دلخواه می‌باشد که افزایش آن باعث افزایش جستجوی اطراف امپریالیست شده و کاهش آن نیز باعث میشود تا مستعمرات تا حد ممکن، به بردار واصل مستعمره به استعمارگر، نزدیک حرکت کنند.
با در نظرگرفتن واحد رادیان برای θ، عددی نزدیک به ۴ π/ در اکثر پیاده‌سازی‌ها، انتخاب مناسبی بوده است.
۳-۳-۳- جابجایی موقعیت مستعمره و امپریالیست
سیاست جذب در عین نابودی ساختارهای اجتماعی سیاسی کشور مستعمره در بعضی موارد نتایج مثبتی را نیز برای آن‌ها در پی داشت. بعضی از کشور درنتیجه اعمال این سیاست به‌نوعی از خودباوری عمومی دست یافتند و پس از مدتی همان تحصیل‌کرده‌ها (به‌عبارت‌دیگر جذب‌شدگان فرهنگ استعماری) بودند که به رهبری ملت خود برای رهایی از چنگال استعمار پرداختند. نمونه‌های فراوانی از این موارد را می‌توان در مستعمرات انگلیس و فرانسه یافت. از سوی دیگر نگاهی به فراز و نشیب چرخش قدرت در کشورها به‌خوبی نشان میدهد که کشورهایی که زمانی در اوج قدرت سیاسی – نظامی بودند، پس از مدتی سقوط کردند و در مقابل کشورهایی سکان قدرت را در دست گرفتند که زمانی هیچ قدرتی در دست نداشتند. در مدل‌سازی این واقعه تاریخی در الگوریتم معرفی‌شده به این صورت عمل شده است که در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن بعضی از این مستعمرات به موقعیتی بهتر از امپریالیست برسند ) به نقاطی در تابع هزینه برسند که هزینه کمتری را نسبت به مقدار تابع هزینه در موقعیت امپریالیست، تولید می‌کنند (.
در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با همدیگر عوض کرده و الگوریتم با کشور استعمارگر در موقعیت جدید ادامه یافته و این بار این کشور امپریالیست جدید است که شروع به اعمال سیاست همگون سازی بر مستعمرات خود میکند. تغییر جای استعمارگر و مستعمره، در شکل ۳-۷ نشان داده‌شده است. در این شکل، بهترین مستعمره‌ی امپراطوری، که هزینه‌ای کمتر از خود امپریالیست دارد، به رنگ تیره‌تر، نشان داده‌شده است. شکل ۳-۸ کل امپراطوری را پس از تغییر موقعیت‌ها، نشان می‌دهد.
 
شکل ۳-۷- تغییر جای استعمارگر و مستعمره ]۳۷ [ شکل ۳-۸ کل امپراطوری، پس از تغییر موقعیت‌ها ]۳۷ [
۳-۳-۴ – قدرت کل یک امپراطوری
قدرت یک امپراطوری برابر است باقدرت کشور استعمارگر، به‌اضافه درصدی از قدرت کل مستعمرات آن بدین ترتیب برای هزینه کل یک امپراطوری داریم.
(۳-۸)
که در آن T.C.n هزینه کل امپراطوری n ام و ξعددی مثبت است که معمولاً بین صفر و یک و نزدیک به صفر در نظر گرفته می‌شود. کوچک در نظر گرفتن ξ، باعث می‌شود که هزینه کل یک امپراطوری، تقریباً برابر با هزینه حکومت مرکزی آن (کشور امپریالیست)، شود و افزایش ξنیز باعث افزایش تأثیر میزان هزینه مستعمرات یک امپراطوری در تعیین هزینه کل آن می‌شود. در حالت نوعی ۰٫۰۵ ξ = در اکثر پیاده‌سازی در اکثر پیاده‌سازی به جواب‌های مطلوبی منجر شده است.
۳-۳-۵- رقابت استعماری
همان‌گونه که قبلاً نیز بیان شد، هر امپراطوری که نتواند بر قدرت خود بیفزاید و قدرت رقابت خود را از دست بدهد، در جریان رقابت‌های امپریالیستی، حذف خواهد شد. این حذف شدن، به‌صورت تدریجی صورت می‌پذیرد. بدین معنی که به‌مرورزمان، امپراطوریهای ضعیف، مستعمرات خود را ازدست‌داده و امپراطوریهای قوی‌تر، این مستعمرات را تصاحب کرده و بر قدرت خویش می‌افزایند. برای مدل کردن این واقعیت، فرض می‌کنیم که امپراطوری در حال حذف، ضعیف‌ترین امپراطوری موجود است. بدین ترتیب، در تکرار الگوریتم، یکی یا چند تا از ضعیف‌ترین مستعمرات ضعیف‌ترین امپراطوری را برداشته و برای تصاحب این مستعمرات، رقابتی را میان کلیه امپراطوریها ایجاد میکنیم. مستعمرات مذکور، لزوماً توسط قوی‌ترین امپراطوری، تصاحب نخواهند شد، بلکه امپراطوریهای قوی‌تر، احتمال تصاحب بیشتری دارند شکل ۳-۹ شمای کلی این بخش از الگوریتم را نشان می‌دهد.
 
شکل ۳-۹ – شمای کلی رقابت استعماری: امپراطوریهای بزرگ‌تر، با احتمال بیشتری، مستعمرات امپراطوریهای دیگر را تصاحب می‌کنند. ]۳۷ [
در این شکل امپراطوری شماره ۱ به‌عنوان ضعیف‌ترین امپراطوری در نظر گرفته‌شده و یکی از مستعمرات آن در معرض رقابت امپریالیستی قرارگرفته است و امپراطوریهای ۲ تا N برای تصاحب آن باهم رقابت می‌کنند. برای مدل‌سازی رقابت میان امپراطوریها برای تصاحب این مستعمرات، ابتدا احتمال تصاحب هر امپراطوری (که متناسب باقدرت آن امپراطوری می‌باشد) را با در نظر گرفتن هزینه کل امپراطوری، به ترتیب زیر محاسبه می‌کنیم. ابتدا از روی هزینه کل امپراطوری، هزینه کل نرمالیزه شده آن را تعیین می‌کنیم.
(۳-۹)
در این رابطه اگر TC هزینه کل امپراطوری n ام و NTC نیز هزینه کل نرمالیزه هر امپراطوری باشد آن امپراطوری که TC کمتری داشته باشد NTCn بیشتری خواهد داشت در حقیقت TCn معادل هزینه کل یک امپراطوری و NTCm معادل قدرت کل آن می‌باشد. امپراطوری با کمترین هزینه، دارای بیشترین قدرت است. با داشتن هزینه کل نرمالیزه شده، احتمال )قدرت( تصاحب مستعمره رقابت، توسط هر امپراطوری، به‌صورت زیر محاسبه می‌شود.
 
(۳-۱۰)
با داشتن احتمال تصاحب هر امپراطوری، مکانیسمی همانند چرخه رولت در الگوریتم ژنتیک موردنیاز است تا مستعمره مورد رقابت را با احتمال متناسب باقدرت امپراطوریها در اختیار یکی از آن‌ها قرار دهد. در کنار امکان استفاده از چرخ رولت موجود، در این نوشتار مکانیسم جدیدی برای پیاده‌سازی این فرایند معرفی‌شده است که نسبت به چرخه رولت دارای هزینه محاسباتی بسیار کمتری می‌باشد. زیرا عملیات نسبتاً زیاد مربوط به محاسبه تابع توزیع جمعی احتمال را که در چرخه رولت موردنیاز است را حذف می‌کند و فقط به داشتن تابع چگالی احتمال نیاز دارد. در ادامه مکانیسم مطرح‌شده برای اختصاص متناسب با احتمال مستعمره مورد رقابت به امپراطوریهای رقیب توضیح داده می‌شود.
با داشتن احتمال تصاحب هر امپراطوری، برای اینکه مستعمرات مذکور را به‌صورت تصادفی، ولی با احتمال وابسته به‌احتمال تصاحب هر امپراطوری، بین امپراطوریها تقسیم کنیم؛ بردار P را از روی مقادیر احتمال فوق، به‌صورت زیر تشکیل می‌دهیم.
 
بردار P دارای سایز *N_imp ۱ می‌باشد و از مقادیر احتمال تصاحب امپراطوریها تشکیل‌شده است. سپس بردار تصادفی R، هم سایز با بردار P را تشکیل میدهیم.
آرایه‌های این بردار، اعدادی تصادفی با توزیع یکنواخت در بازه [ ۰,۱ ] می‌باشند.
 
سپس بردار D را به‌صورت زیر تشکیل می‌دهیم.
 
با داشتن بردار D، مستعمرات مذکور را به امپراطوریای می‌دهیم که اندیس مربوط به آن در بردار D بزرگ‌تر از بقیه می‌باشد. امپراطوریای که بیشترین احتمال تصاحب را داشته باشد، با احتمال بیشتری اندیس مربوط به آن در بردار D بیشترین مقدار را خواهد داشت. عدم نیاز به محاسبه CDF باعث می‌شود که این مکانیسم نسبت به چرخه رولت با سرعت به‌مراتب بیشتری عمل کند. مکانیسم جدید مطرح‌شده نه‌تنها می‌تواند در اختصاص مستعمره به امپراطوری برحسب احتمال تصاحب آن‌ها مفید باشد، بلکه به‌عنوان یک مکانیسم انتخاب برحسب احتمال میتواند جایگزین چرخه رولت در الگوریتم ژنتیک برای انتخاب والدین شود و سرعت اجرای عملیات در آن را تا حد زیادی افزایش دهد.
با تصاحب مستعمره توسط یکی از امپراطوریها، عملیات این مرحله از الگوریتم با تصاحب مستعمره توسط یکی از امپراطوریها، عملیات این مرحله از الگوریتم نیز به پایان می‌رسد.
۳-۳-۶ – سقوط امپراطوریهای ضعیف