• جمعیت اولیه

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

• استراتژی تقسیم[۱۱۳]

• استراتژی حرکت[۱۱۴]

• استراتژی رقابت[۱۱۵]

• همگرایی الگوریتم

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

• ساختار کشور

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

• جمعیت اولیه

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

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

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

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

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

موعد تحویل

وزن زودکرد و دیرکرد
سرعت پردازش ماشینها

U~[1,5]
U~[2,8]

تعداد مراحل

۳,۵,۷

از آنجا که هدف مسأله مینیممسازی زمانهای زودکرد ودیرکرد وزنی نسبت به موعد تحویل کارها میباشد. برای طراحی مسأله نمونه ابتدا باید زمان تحویل کارها را تولید کنیم. تولید موعد تحویل کارها با استفاده از توزیع یکنواخت و در محدوده =(+U~[0,1]3)(k/)( تولید میشوند [۳۶]. r زمان دسترسی به کارها، مجموع زمان پردازش هر کار در همه مراحل.
۴-۷
j =۱…n
میانگین مجموع تمام زمانهای نصب برای هریک از کارها در همه مراحل.
۴-۸
j=1… n, l=1...n
۴-۵٫ تنظیم پارامترهای کنترل کننده:
کالیبراسیون الگوریتم یکی از مهمترین مراحل طراحی الگوریتمهای فراابتکاری در دستیابی به جوابهای بهینه مناسب میباشد. از آنجایی که مقادیر مختلف پارامترهای کنترلکننده این الگوریتمها ممکن است شاخصهای محاسباتی شامل کیفیت جوابها و زمان محاسباتی را تحت تأثیر قرار دهند، غالباً مجموعهای از آزمایشات کالیبراسیون به منظور یافتن ترکیب بهینه مقادیر متفاوت پارامترهای کنترل کننده الگوریتم صورت می پذیرد.
الگوریتمهای پیشنهادی این تحقیق الگوریتمهای ژنتیک و رقابت استعماری میباشد. پارامترهای کنترل کننده الگوریتم ژنتیک عبارتند از: اندازه جامعه اولیه ()، نرخ تقاطع ()، نرخ جهش ()، حداکثر تعداد نسلها (). و پارامترهای کنترلکننده الگوریتم رقابت استعماری عبارتند از: تعداد همسایگیهای تولید شده ()، تعداد تکرار الگوریتم رقابت استعماری (Decade) و درصد تأثیر قدرت کل مستعمرات هر امپراطوری روی قدرت آن (PICA). هر یک از این پارامترها در بازه خاصی از مقادیر خود بر روی شاخصهای محاسباتی اثرگذار هستند و در خارج از این بازه تأثیر ناچیز و قابل چشم پوشی دارند، شاخصهای محاسباتی به کار رفته در انجام آزمایشات این بخش و بخشهای آتی، میانگین مقادیر تابع هدف برای جوابهای بهینه و میانگین زمانهای محاسباتی آنها در هر ده تکرار[۱۱۸] از الگوریتم میباشند.
دراین بخش ابتدا محدوده مؤثر هریک از پارامترهای کنترل کننده بطور نسبی مشخص میشود. پس از آن به بررسی و تحلیل اثرات متقابل آنها از طریق طراحی آزمایشات چند عاملی با استفاده از روش تاگوچی پرداخته میشود و در نهایت ترکیب بهینه آنها برآورد میشود.
۴-۵-۱٫ اندازه جامعه اولیه ():
اندازه جامعه اولیه جوابها یکی از مهمترین پارامترهای الگوریتم ژنتیک محسوب میشود. انتخاب یک اندازه مناسب برای جامعه جوابها مستلزم برقراری تعادل بین دو معیار کارایی و اثر بخشی الگوریتم میباشد. اندازههای کوچک جامعه جوابها جستجوی مؤثر فضای جوابها را محدود میسازد در حالی که اندازههای بزرگ کارایی الگوریتم را در دستیابی به جوابهای بهینه در زمان محاسباتی معقول کاهش می دهد.
به منظور بررسی حساسیت الگوریتم پیشنهادی نسبت به پارامتر اندازه جامعه، آزمایشات متعددی برای سطوح مختلف از این پارامتر صورت گرفته است که با افزایش اندازه جامعه کیفیت جوابها بتدریج بهبود مییابد. این افزایش با رسیدن به اندازه ۴۰۰ تأثیر خود را از دست میدهد و کیفیت جوابها به مقدار ثابتی همگرا میشود. افزایش اندازه جامعه تأثیر قابل ملاحظهای در زمان محاسباتی الگوریتم و کارآیی آن دارد.
۴-۵-۲. نسبت تقاطع ():
بررسی تأثیر نسبت تقاطع بر عملکرد الگوریتم ژنتیک نشان میدهد که با افزایش این نسبت زمان محاسباتی افزایش مییابد. آزمایشات مربوط به این نرخ در محدوده مقادیر بین ۵/۰تا ۸/۰صورت گرفتهاند. نتایج بدستآمده حاکی ار آنست که کیفیت جوابها با افزایش نرخ تقاطع تا مقدار۷/۰بهبود مییابد و پس از آن به پایداری میرسد.
۴-۵-۳. نسبت جهش ():
به منظور بررسی تأثیر نسبت جهش بر عملکرد الگوریتم ژنتیک، مقادیر ۰۹/۰ , ۱۲/۰, ۱۵/۰ , ۲/۰ , ۲۵/۰ , ۳/۰برای این نسبت در قالب مجموعهای از آزمایشات بررسی شدهاند. نتایج بدستآمده حاکی ار آنست که کیفیت جوابها در بازه ۱۵/۰ تا ۲/۰ در بهترین میزان خود قرار دارد.
۴-۵-۴. نرخ جهش ():
به منظور بررسی تعداد جهشهای مؤثر در هر تکرار و تأثیر آن بر عملکرد الگوریتم ژنتیک، مقادیر ۱/۰ ، ۱۵/۰ ، ۲/۰ ، ۲۵/۰برای این نرخ در قالب مجموعهای از آزمایشات بررسی شدهاند. نتایج بدستآمده حاکی ار آنست که کیفیت جوابها در بازه ۱۰/۰ تا۲/۰در بهترین میزان خود قرار دارد.
۴-۵-۵٫ حداکثر تعداد نسلها ():