۲

۵

۱

۳

۶

۴

۷

۸

۱۰

۹

ماشین ۱
ماشین ۲
ماشین ۳
ماشین ۴
ماشین ۵
شایستگی: در این الگوریتم تابع شایستگی به صورت زیر تعریف شده است:

(۳-۱)

که در آن نشان دهنده زمان پایان آخرین کار و نیز نشان دهنده میانگین زمان اجرای تمامی کارها می باشد. ثابت میزان اهمیت هر یک از معیارها را نشان می دهد. به عنوان مثال اگر این ثابت برابر ۱ در نظر گرفته شود، فقط معیار اول برای ما مهم خواهد بود.

سایر عملگرها: در این الگوریتم از چرخ رولت^[۱۱۲] به عنوان عملگر انتخاب، برش یکنواخت^[۱۱۳]به عنوان عملگر برش برای کدگذاری مستقیم و برش چرخه ای^[۱۱۴]برای کدگذاری جایگشتی استفاده شده است. بعلاوه احتمال برش ها در هر دو نوع، برابر ۰٫۹ در نظر گرفته شده است. از جهش جابجایی^[۱۱۵] به عنوان عملگر جهش استفاده شده است.
اگر چه الگوریتم ژنتیک الگوریتمی قدرتمند در حل مسائل غیر خطی است، ولی اگر میزان غیر خطی بودن مسئله زیاد باشد، این الگوریتم کارایی خود را از دست می دهد و دچار همگرایی زودرس شده و در بهینه های محلی گرفتار می شود. مسئله زمانبندی از جمله مسائل با اندازه درجه غیرخطی بودن بسیار بالا است و در نتیجه احتمال گرفتار شدن این الگوریتم در بهینه های محلی بسیار بالا است و در نتیجه پاسخ های این الگوریتم قابل اعتماد نخواهند بود.

فصل چهارم:

روش پیشنهادی

۴-۱ مقدمه
همان طور که در فصل پیشنه تحقیق بیان شد، الگوریتم های سنتی، مانند الگوریتم دور رابین، دارای مشکلاتی هستند که استفاده از آنها را با مشکل مواجه می کرد. از مهمترین این مشکلات عدم قابلیت در برقراری تعادل بار و عدم تضمین یافتن جواب مناسب برای مسئله بود. این مشکلات به دلیل رفتار سیستماتیک و قطعی این نوع الگوریتم ها رخ می دهد. برای مرتفع کردن این مشکلات، الگوریتم های ابتکاری از جمله الگوریتم ژنتیک و الگوریتم کلونی مورچگان معرفی شدند. الگوریتم ژنتیک به دلیل رفتار مبتنی بر جمعیت، امکان یافتن جواب های مناسب را فراهم می کرد و دو مشکل الگوریتم های سنتی را نداشت، ولی این الگوریتم برای مسائل با درجه غیر خطی بالا مانند مسئله زمانبندی مناسب نیست. زیرا امکان گرفتار شدن الگوریتم در بهینه های محلی بسیار بالا می باشد. از طرفی دیگر الگوریتم کلونی مورچگان با تکیه بر هوش جمعی و رفتار موازی سعی در جستجوی زیرفضاهای مناسبی از فضای بزرگ جستجو دارد که این الگوریتم نیز برای اجرای کارآمد نیاز به سخت افزار مناسبی دارد.
در این فصل، روشی مبتنی بر الگوریتم رقابت استعماری جهت حل مسئله زمانبندی کار ارائه می شود. این الگوریتم در کلاس الگوریتم های ابتکاری مبتنی بر جمعیت طبقه بندی می شود و در نتیجه مشکلات روش های سیستماتیک سنتی را ندارد. علاوه بر این، در روش پیشنهادی، از جستجوی محلی جهت جلوگیری از گرفتار شدن الگوریتم در بهینه های محلی استفاده شده است و به همین دلیل ، این الگوریتم در شرایط بهینه های محلی، رفتار هوشمندانه تری را نسبت به الگوریتم ژنتیک از خود نشان می دهد. علاوه بر این، الگوریتم پیشنهادی نیاز به سخت افزار خاصی جهت اجرا شدن ندارد و از نظر زمانی می تواند بسیار بهتر از الگوریتم کلونی مورچگان عمل کند.
ادامه این فصل بدین ترتیب مرتب شده است که در بخش ۴-۲، ساختار الگوریتم رقابت استعماری پیشنهادی به همراه عملگرهای مختلف آن مورد بررسی قرار گرفته است. در بخش ۴-۳، یک مکانیسم مبتنی بر تشخیص شباهت میان کشورها معرفی شده است که قابلیت تشخیص همگرایی زودرس الگوریتم رقابت استعماری و امکان استفاده از جستجوی محلی را فراهم می کند. این قابلیت به ما کمک می کند تا با افزودن تعدادی کشور جدید به گروه کشورهای فعلی، مجموعه کشورها را از شباهت بیش از اندازه در آورده و امکان خروج الگوریتم از بهینه های محلی را فراهم کنیم.
۴-۲ ساختار الگوریتم رقابت استعماری پیشنهادی
همان طور که در بخش ۲-۴ بیان شد، الگوریتم رقابت استعماری یک الگوریتم مبتنی بر جمعیت است که از طریق شبیه سازی رفتار امپریالیسم، سعی در حل مسائل مختلف بهینه سازی می کند. ساختار کلی این الگوریتم که در شکل ۲-۸ نمایش داده شده، در شکل ۴-۱، تکرار شده است، تا بررسی بخش ها و عملگرهای مختلف این الگوریتم راحت تر صورت گیرد.
شکل۴-۱ فلوچارتالگوریتمرقابتاستعماری

۴-۲-۱ کدگذاری

در الگوریتم پیشنهادی از کدگذاری جایگشتی استفاده شده است. تشکیل این کدگذاری شامل دو مرحله می باشد: ۱) برای هر ماشین ، دنباله از کارهایی که به آن ماشین تخصیص داده شده اند، ایجاد می شود، و ۲) دنباله های کارهای ایجاد شده در مرحله اول به یکدیگر الحاق می شوند. نتیجه این دو مرحله، جایگشتی از کارها می باشد که به ماشین ها تخصیص داده شده اند. شکل ۴-۲ نمونه ای از این نوع کدگذاری را برای ۱۰ کار و ۵ ماشین نشان می دهد. این کدگذاری از دو بخش تشکیل شده است: ۱) بخش زمانبندی و تخصیص کارها و ۲) ساختمان داده مربوط به نمایش تعداد کارهای تخصیص یافته به هر ماشین.
شکل۴-۲: مثالی از کدگذاری های جایگشتی برای زمانبندی ۱۰ کار بر روی ۵ ماشین
کار۱
کار ۲
کار ۳