همانگونه که قبلا نیز بیان شد، هر امپراطوری‌ای که نتواند بر قدرت خود بیفزاید و قدرت رقابت خود را از دست بدهد، در جریان رقابت‌های امپریالیستی، حذف خواهد شد. این حذف شدن، به صورت تدریجی صورت می‌پذیرد. بدین معنی که به مرور زمان، امپراطوری‌های ضعیف، مستعمرات خود را از دست داده و امپراطوری‌های قوی تر، این مستعمرات را تصاحب کرده و بر قدرت خویش می‌افزایند. برای مدل کردن این واقعیت، فرض می‌کنیم که امپراطوری در حال حذف، ضعیف‌ترین امپراطوری موجود است. بدین ترتیب، در تکرار الگوریتم، یکی یا چند تا از ضعیف‌ترین مستعمرات ضعیف‌ترین امپراطوری را برداشته و برای تصاحب این مستعمرات، رقابتی را میان کلیه امپراطوری‌ها ایجاد می‌کنیم. مستعمرات مذکور، لزوما توسط قوی ترین امپراطوری، تصاحب نخواهند شد، بلکه امپراطوری‌های قوی تر، احتمال تصاحب بیشتری دارند. شکل ۲-۹ شمای کلی این بخش از الگوریتم را نشان می‌دهد]۱۱.[
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
شکل ۲-۹ شمای کلی رقابت استعماری: امپراطوری‌های بزرگتر، با احتمال بیشتری، مستعمرات امپراطوری‌های دیگر را تصاحب می‌کنند]۱۱[
در این شکل امپراطوری شماره ۱ به عنوان ضعیف‌ترین امپراطوری در نظر گرفته شده و یکی از مستعمرات آن در معرض رقابت امپریالیستی قرار گرفته است و امپراطوری های ۲ تا N برای تصاحب آن با هم رقابت می‌کنند. برای مدل‌سازی رقابت میان امپراطوری‌ها برای تصاحب این مستعمرات، ابتدا احتمال تصاحب هر امپراطوری (که متناسب با قدرت آن امپراطوری می‌باشد)، را با در نظر گرفتن هزینه کل امپراطوری، به ترتیب زیر محاسبه می‌کنیم. ابتدا از روی هزینه کل امپراطوری، هزینه کل نرمالیزه شده آن را تعیین می‌کنیم.
(۲-۷)
در این رابطه ، هزینه کل امپراطوری nام و نیز، هزینه کل نرمالیزه شده آن امپراطوری می‌باشد. هر امپراطوری که کمتری داشته باشد بیشتری خواهد داشت. در حقیقت معادل هزینه کل یک امپراطوری و معادل قدرت کل آن می‌باشد. امپراطوری با کمترین هزینه، دارای بیشترین قدرت است. با داشتن هزینه کل نرمالیزه شده، احتمال (قدرت) تصاحب مستعمره رقابت، توسط هر امپراطوری، به صورت زیر محاسبه می‌شود.
(۲-۸)
با داشتن احتمال تصاحب هر امپراطوری، روشی همانند چرخه رولت در الگوریتم ژنتیک مورد نیاز است تا مستعمره مورد رقابت را با احتمال متناسب با قدرت امپراطوری ها در اختیار یکی از آنها قرار دهد. در کنار امکان استفاده از چرخ رولت موجود، در این نوشتار مکانیزم جدیدی برای پیاده‌سازی این فرایند معرفی شده است که نسبت به چرخه رولت دارای هزینه محاسباتی بسیار کمتری می‌باشد. زیرا عملیات نسبتا زیاد مربوط به محاسبه تابع توزیع جمعی احتمال را که در چرخه رولت مورد نیاز است را حذف می‌کند و فقط به داشتن تابع چگالی احتمال نیاز دارد. در ادامه مکانیزم مطرح شده برای اختصاص متناسب با احتمال مستعمره مورد رقابت به امپراطوری های رقیب توضیح داده می‌شود.
با داشتن احتمال تصاحب هر امپراطوری، برای اینکه مستعمرات مذکور را به صورت تصادفی، ولی با احتمال وابسته به احتمال تصاحب هر امپراطوری، بین امپراطوری‌ها تقسیم کنیم؛ بردار را از روی مقادیر احتمال فوق، به صورت زیر تشکیل می دهیم.
بردار دارای سایز ۱*Nimp می‌باشد و از مقادیر احتمال تصاحب امپراطوری‌ها تشکیل شده است. سپس بردار تصادفی ، هم سایز با بردار را تشکیل می‌دهیم. آرایه‌های این بردار، اعدادی تصادفی با توزیع یکنواخت در بازه [۰,۱] می‌باشند.
سپس بردار را به صورت زیر تشکیل می‌دهیم.
با داشتن بردار ، مستعمرات مذکور را به امپراطوری‌ای می‌دهیم که اندیس مربوط به آن در بردار بزرگتر از بقیه می‌باشد. امپراطوری‌ای که بیشترین احتمال تصاحب را داشته باشد، با احتمال بیشتری اندیس مربوط به آن در بردار ، بیشترین مقدار را خواهد داشت. عدم نیاز به محاسبه CDF باعث می‌شود که این مکانیزم نسبت به چرخه رولت با سرعت به مراتب بیشتری عمل کند. مکانیزم جدید مطرح شده نه تنها می‌تواند در اختصاص مستعمره به امپراطوری بر حسب احتمال تصاحب آنها مفید باشد، بلکه به عنوان یک مکانیزم انتخاب بر حسب احتمال می‌تواند جایگزین چرخه رولت در الگوریتم ژنتیک برای انتخاب والدین شود و سرعت اجرای عملیات در آن را تا حد زیادی افزایش دهد.
با تصاحب مستعمره توسط یکی از امپراطوری ها، عملیات این مرحله از الگوریتم نیز به پایان می‌رسد.
۲-۵-۱-۶ سقوط امپراطوری‌های ضعیف
همانگونه که بیان شد، در جریان رقابت‌های امپریالیستی، خواه ناخواه، امپراطوری های ضعیف به تدریج سقوط کرده و مستعمراتشان به دست امپراطوری‌های قوی‌تر می‌افتد. شروط متفاوتی را می‌توان برای سقوط یک امپراطوری در نظر گرفت. در الگوریتم پیشنهاد شده، یک امپراطوری زمانی حذف شده تلقی می‌شود که مستعمرات خود را از دست داده باشد. شکل ۲-۱۰ این مسئله را به خوبی نشان می‌دهد. در این شکل، امپراطوری شماره ۴ به علت از دست دادن کلیه مستعمراتش، دیگر قدرتی برای رقابت ندارد و باید از میان بقیه امپراطوری‌ها حذف شود]۱۱[.
شکل ۲-۱۰ سقوط امپراطوری ضعیف ]۱۱[
۲-۵-۱-۷ همگرایی
الگوریتم مورد نظر تا برآورده شدن یک شرط همگرایی، و یا تا اتمام تعداد کل تکرارها، ادامه می‌یابد. پس از مدتی، همه امپراطوری‌ها، سقوط کرده و تنها یک امپراطوری خواهیم داشت و بقیه کشورها تحت کنترل این امپراطوری واحد، قرار می‌گیرند. در این دنیای ایده آل جدید، همه‌ی مستعمرات، توسط یک امپراطوری واحد اداره می‌شوند و موقعیت‌ها و هزینه‌های مستعمرات، برابر با موقعیت و هزینه کشور امپریالیست است. در این دنیای جدید، تفاوتی، نه تنها میان مستعمرات، بلکه میان مستعمرات و کشور امپریالیست، وجود ندارد. به عبارت دیگر، همه‌ی کشورها، در عین حال، هم مستعمره و هم استعمارگرند. در چنین موقعیتی رقابت امپریالیستی به پایان رسیده و به عنوان یکی از شروط توقف الگوریتم متوقف می‌شود. شبه کد مربوط به الگوریتم رقابت استعماری در شکل ۲-۱۱، نشان داده شده است]۱۱.[
-
- ۱- چند نقطه تصادفی روی تابع انتخاب کرده و امپراطوری‌های اولیه را تشکیل بده.
-
- ۲- مستعمرات را به سمت کشور امپریالیست حرکت بده (سیاست همسان‌سازی).
-
- ۳- اگر مستعمره‌ای در یک امپراطوری، وجود داشته باشد که هزینه‌ای کمتر از امپریالیست داشته باشد؛ جای مستعمره و امپریالیست را با هم عوض کن.
-
- ۴- هزینه‌ی کل یک امپراطوری را حساب کن (با در نظر گرفتن هزینه‌ی امپریالیست و مستعمراتشان).
-
- ۵- یک مستعمره از ضعیف‌ترین امپراطوری انتخاب کرده و آن را به امپراطوری‌ای که بیشترین احتمال تصاحب را دارد، بده.
-
- ۶- امپراطوری‌های ضعیف را حذف کن.
-
- ۷- اگر تنها یک امپراطوری باقی مانده باشد، توقف کن وگرنه به ۲ برو.
شکل۲-۱۱ شبه کد مربوط به الگوریتم رقابت استعماری]۱۱[
شمای کلی الگوریتم در شکل ۲-۱۲ نیز نشان داده شده است. مطابق این شکل، الگوریتم با جمعیت اولیه تصادفی و تشکیل امپراطوری های اولیه آغاز شده و در یک چرخه سیاست جذب و رقابت امپریالیستی تکرار می‌شوند]۱۱[.
شکل ۲-۱۲ شمای کل الگوریتم رقابت استعماری به صورت گرافیکی]۱۱[
۲-۵-۲ مزایای الگوریتم رقابت استعماری
الگوریتم توسعه داده شده، در وهله اول با داشتن یک دیدگاه کاملأ نو به مبحث بهینه‌سازی، پیوندی جدید میان علوم انسانی و اجتماعی از یک سو و علوم فنی و ریاضی از سوی دیگر، برقرار می‌کند. ارتباط میان این دو شاخه از علم به گونه‌ای می‌باشد که غالبا ریاضیات به عنوان ابزاری قوی و دقیق در خدمت علوم انسانی کلی نگر قرار گرفته و به درک و تحلیل نتایج آن کمک می‌کند. اما الگوریتم توسعه داده شده بر خلاف معمول، نقطه‌ی قوت علوم انسانی و اجتماعی، یعنی کلی‌نگری و وسعت دید آن را به خدمت ریاضیات درآورده و از آن به عنوان ابزاری برای درک بهتر ریاضیات و حل بهتر مسائل ریاضی استفاده می‌کند. بنابراین حتی بدون در نظر گرفتن قابلیت‌های ریاضی و عملی روش توسعه داده شده، پیوند ایجاد شده میان این دو شاخه به ظاهر جدا از هم، به عنوان یک پژوهش میان رشته‌ای، در نوع خود دارای ارزش بسیاری می‌باشد]۱۱.[
مزایای الگوریتم اجتماعی پیشنهادی را می‌توان به صورت زیر خلاصه کرد:
-
- نو بودن ایده‌ی پایه‌ای الگوریتم: به عنوان اولین الگوریتم بهینه سازی مبتنی بر یک فرایند اجتماعی‌ـ سیاسی
-
- مبتنی بر رفتار اجتماعی انسان که هوشمندانه تر از رفتار های بیولوژیکی اوست.
-
- سرعت همگرایی بالا
- توانایی بهینه سازی توابعی با تعداد متغییر زیاد: توانایی بهینه سازی هم‌تراز و حتی بالاتر در مقایسه با الگوریتم های مختلف بهینه سازی، در مواجهه با انواع مسائل بهینه سازی
