پایان نامه - مقاله و پروژه

سامانه پژوهشی – طراحی یک مدل ریاضی وحل آن با الگوریتم های ابتکاری و …

فرزند فرزند
شکل۴-۴٫ عملیات جهش
۴-۳٫ الگوریتم رقابت استعماری پیشنهادی
الگوریتم جدید رقابت استعماری با الهامگیری از یک فرایند اجتماعی سیاسی، یک الگوریتم با توانایی بالا بوده و تا حد بسیار زیادی نیز، سریع میباشد. همانطور که در فصل گذشته عنوان شد، کلیات این الگوریتم اولین بار توسط آتشپز و همکارانش ارائه شده است. این الگوریتم همانند سایر روشهای بهینهسازی تکاملی، با تعدادی جمعیت اولیه شروع میشود. در این الگوریتم، هر عنصر جمعیت، یک کشور نامیده میشود. کشورها به دو دسته مستعمره و استعمارگر تقسیم میشوند. هر استعمارگر، بسته به قدرت خود، تعدادی از کشورهای مستعمره را به سلطه خود درآورده و آنها را کنترل میکند. سیاست جذب و رقابت استعماری، هسته اصلی این الگوریتم را تشکیل میدهند.
برای حل مسأله تعریف شده، الگوریتم رقابت استعماری پیشنهاد شده است. رویه کلی الگوریتم رقابت استعماری به صورت شماتیک در شکل (۴-۵) و به صورت فلوچارت در شکل (۴-۶) نشان داده شده است.
مهمترین مراحل پیادهسازی الگوریتم رقابت استعماری به صورت زیر میباشد.

  • نمایش ساختار کشور
  • جمعیت اولیه
  • ارزیابی برازندگی تابع هدف
  • استراتژی تقسیم[۱۱۳]
  • استراتژی حرکت[۱۱۴]
  • استراتژی رقابت[۱۱۵]
  • همگرایی الگوریتم

شکل۴-۵٫ شمای کلی الگوریتم رقابت استعماری ]۱۹[
 
شکل ۴-۶٫ فلوچارت الگوریتم رقابت استعماری ]۱۹[

  • ساختار کشور

همانطور که عنوان شد الگوریتم ژنتیک بر روی کروموزومها اعمال میشود، لذا اولین گام در به کارگیری و پیادهسازی الگوریتم ژنتیک نمایش جوابهای مسأله به صورت یک کروموزوم است. ولی در الگوریتم رقابت استعماری معادل هر کروموزوم در الگوریتم ژنتیک یک کشور وجود خواهد داشت. که البته ویژگیهای کشور الگوریتم رقابت استعماری در مسأله مورد نظر، دقیقاً مشابه ساختار کروموزوم در الگوریتم ژنتیک میباشد، با این تفاوت که به هر قسمت از کروموزوم، یک ژن گفته میشود، ولی به هر قسمت کشور، یک ویژگی مربوط به آن کشور گفته میشود. مانند فرهنگ، زبان، اقتصاد، تاریخ و غیره.

  • جمعیت اولیه

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

  • ارزیابی برازندگی تابع هدف

در این الگوریتم، ما به دنبال بهترین کشور (کمترین مقدار تابع هدف) میگردیم. الگوریتم معرفی شده در این نوشتار، با تولید یک دسته اولیه از این کشورها و دسته بندی آنها در قالب امپراطوریها و اعمال سیاست جذب از طرف استعمارگران به روی مستعمرات و همچنین با ایجاد رقابت استعماری میان امپراطوریها به جستجوی بهترین کشور میپردازد.
برای شروع الگوریتم، همانطور که در فصل قبل نیز گفته شد، تعداد Ncountry کشور اولیه را ایجاد میکنیم. تعداد Nimp تا از بهترین اعضای این جمعیت (کشورهای دارای کمترین مقدار تابع هزینه) را به عنوان امپریالیست انتخاب میکنیم. تعداد باقی مانده Ncol تا از کشورها، مستعمرات را تشکیل میدهند.
محاسبات مربوط به تابع برازندگی در الگوریتم رقابت استعماری، دقیقاً مشابه تابع برازندگی است که در الگوریتم ژنتیک به آن اشاره شده است.

  • استراتژی تقسیم در الگوریتم پیشنهادی

هر کشور مستعمره به یک امپراطوری تعلق دارد. برای تقسیم مستعمرات اولیه بین امپریالستها، متناسب با قدرت هر امپریالیست، تعدادی از مستعمره به امپراطوری تعلق میگیرد. شیوه انجام این کار دقیقاً مشابه روشی است که در فصل قبل برای تقسیم مستعمرات بین امپریالیستها، شرح داده شد. ابتدا هزینه نرمالیزه هر امپراطوری را محاسبه میکنیم. سپس، قدرت نسبی نرمالیزهی هر امپریالیست، که بر مبنای آن کشورهای مستعمره، بین امپریالسیت ها تقسیم میشوند، را طبق فرمولهای بیان شده به دست میآوریم. با داشتن حالت اولیه تمام امپراطوریها، الگوریتم رقابت استعماری شروع میشود. روند تکامل در یک حلقه قرار دارد که تا برآورده شدن یک شرط توقف، ادامه مییابد.
شکل ۴-۷ چگونگی شکلگیری امپراطوریهای اولیه را نشان میدهد. همانگونه که در این شکل نشان داده شدهاست، امپراطورهای بزرگتر، تعداد بیشتری مستعمره دارند. در این شکل، امپریالست شماره ۱ قویترین امپراطوری را ایجاد کرده است و بیشترین تعداد مستعمرات را دارد.

برای دانلود متن کامل این فایل به سایت torsa.ir مراجعه نمایید.