XTb
XTT
XT1
XTa
XTb
XTT
شکل ۱۶-۴: عملگرتقاطع
۲-۴-۳-۸-۴: عملگرهای جهشی[۱۳۸]
در این تحقیق برای ایجاد جهش در کروموزومهای ایجاد شده، سه نوع جهش تعریف میکنیم :
۱-۲-۴-۳-۸-۴: جهش یگانه [۱۳۹]
برای پیاده سازی این نوع جهش، عملیات یک قطعهای بطور تصادفی انتخاب می شود و عملگر جهش یک ماشین دیگری را که این عملیات را می تواند انجام دهد انتخاب می کند و جایگزین ماشین قبلی می کند.
۲-۲-۴-۳-۸-۴: جهش چند گانه[۱۴۰]
این نوع جهش، جهش یگانه را روی تمام عملیات قطعهای که بطور تصادفی انتخاب می شود، انجام میدهد.
۳-۲-۴-۳-۸-۴: جهش معکوس[۱۴۱]
این نوع جهش توالی سلولهای عملیات قطعهای را که بطور تصادفی انتخاب شده است معکوس می کند.
برای انجام جهش یک عدد تصادفی بین ۱ و۳ تولید کرده و یکی از جهشهای فوق را انجام می دهیم.
۵-۳-۸-۴: نخبهگرایی
با توجه روند توسعه داده شده برای الگوریتم ژنتیک، در هر نسل درصدی از بهترین کروموزموزمها به نسل بعد منتقل می کینم. بنابراین نخبهگرایی این الگوریتم تضمین می شود.
۶-۳-۸-۴:استراتژی برخورد با محدودیتها[۱۴۲]
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت‌های مساله می‌باشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزومهای غیرموجه می‌شود. در این تحقیق از استراتژی اصلاحی استفاده شده که در این روش به جای اینکه کروموزوم غیرموجه حذف گردد تبدیل به یک کروموزوم موجه می‌شود. این عمل بعد از انجام ترکیب و جهش که در آن امکان ایجاد کروموزوم غیرموجه وجود دارد، استفاده می شود.
۷-۳-۸-۴:معیار توقف الگوریتم
با توجه به اینکه الگوریتمهای فوق ابتکاری هیچگونه شناختی نسبت به نقطهی بهینه سراسری و بطور کلی درجه بهینه بودن جوابها ندارند، معیاری برای توقف آنها مورد نیاز است. برای توقف الگوریتم از معیار حداکثر تعداد تکرار الگوریتم استفاده شده است.
الگوریتم پیشنهادی در این تحقیق با بهره گرفتن از زبان برنامه نویسی MATLAB کدنویسی شده و با بهره گرفتن از همین زبان نرم افزاری توسعه داده شده است. در جدول ۲۲-۴ برخی از جوابهای این الگوریتمها ارائه شده است که هر دو الگوریتم ارائه شده برای این مدل جوابهای نردیک به بهینهای را در زمانهای کمترنسبت به حل با بهره گرفتن از نرمافزار LINGO ارائه دادهاند. همانطور که در جدول ۲۳-۴ مقایسه بین جوابهای دو الگوریتم ارائه شده و بهترین جواب بدست آمده مشهود است، الگوریتم SA در مقایسه با الگوریتم GA جواب های بهتری را (البته در مدت زمانی بیشتر) گزارش نموده است و همانطور که مشاهده می شود برای مسائلی که نعداد قطعه در دوره بزرگتر از ۵ *۲۰ و تعداد ماشینها بیشتر از ۷ ، تعداد سلول ها بیشتر از ۵ و تعداد عملیاتها بیشتر از ۴ باشد Lingo 9 قادر به حل و پیدا کردن جواب برای آن نخواهد بود .
جدول ۲۲-۴: جواب های بدست آمده با الگوریتم های پیشنهادی
GA
SA
Lingo
تعداد عملیات
تعداد سلولها
تعداد ماشینها
تعداد دوره ها*تعداد قطعات
مسائل
زمان حل
تابع هدف
زمان حل
تابع هدف
زمان حل
آخرین نظرات