زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در نظر گرفتن محدودیت دسترسی …

۵

۳

۶

۴

۱

۲

۱

۲

۱

۲

۱

۲

۲

۱

۱

۲

فرزند ۱ فرزند ۲
شکل ۴-۳٫ عملیات تقاطع
بهمنظور اعمال جهش در الگوریتم ژنتیک مورد استفاده، از مزایای هر سه روش ذکر شده در رابطه با عملگرهای جهش در فصل قبل استفاده شده است، بدین صورتکه در هر تکرار با احتمال یک سوم یکی از روشهای جابجایی، وارونگی و یا الحاق مورد استفاده قرار میگیرد. همچنین این امکان فراهم شدهاست که در تمام تکرارها، تنها یکی از این سه روش به دلخواه مورد استفاده قرار بگیرد.
۴-۲-۶٫ همگرایی الگوریتم ژنتیک
تحقیقات رونکلف[۲۰۲]، همگرایی الگوریتم ژنتیک را تحت شرایط خاص به اثبات میرساند. در این تحقیقات نشان داده شده است که همگرایی به سمت بهینه کلی یک خاصیت ذاتی الگوریتم ژنتیک نمیباشد، ولی با رعایت شرایط خاصی امکانپذیر است. اگر چنانچه در هر مرحله از الگوریتم ژنتیک، بهترین جوابها نگاه داشته و با احتمال یک، به مرحله بعد وارد شوند، الگوریتم به سمت بهینه کلی همگرا میشود. از عوامل موثر بر سرعت همگرایی الگوریتم ژنتیک میتوان به جمعیت اولیه، مقادیر احتمال جهش و تقاطع، چگونگی انجام عمل تقاطع و جهش، تابع برازش و استراتژی انتخاب جمعیت برای نسل بعدی نام برد. چگونگی تاثیر این عوامل در سرعت همگرایی الگوریتم ژنتیک به مسئله مورد نظر بستگی داشته و از طریق طراحی آزمایشات[۲۰۳] میتوان مقادیر مناسبی را به عنوان پارامتر ورودی الگوریتم ژنتیک برای مسئله مورد نظر، بدست آورد.
۴ -۲-۷٫ معیار توقف
در الگوریتم ژنتیک مورد استفاده در این تحقیق از معیار تعداد نسلهای طی شده در الگوریتم به عنوان معیار توقف استفاده شده است. بسته به ابعاد مسئله (کوچک، متوسط و بزرگ) تعداد نسل تعیین شده برای این که الگوریتم به یک جواب همگرا شود متفاوت میباشد.
۴-۳٫ پیاده سازی الگوریتم زنبور عسل( شماره یک)[۲۰۴]
در الگوریتم پیش رو، همان مفاهیم ذکرشده در بخش معرفی الگوریتم زنبورعسل در کدنویسی الگوریتم بکار گرفته شدهاست. روش نمایش جواب در این الگوریتم مشابه همان روشی است که در بخش تعریف ساختار کرومزوم در الگوریتم ژنتیک به آن اشاره شد که بصورت خلاصه میتوان گفت هر جواب در قالب یک ماتریس دو بعدی نمایش داده میشود که سطر اول نمایش دهنده شماره عملیات و سطر دوم نمایشگر ماشینی است که آن عملیات روی آن پردازش میشود و اولویت پردازش عملیاتی که به ماشینهای مشابهی اختصاص یافتهاند، با توجه به ترتیب قرارگیری از سمت چپ به راست مشخص میشود.
۴-۳-۱٫ مراحل اجرای الگوریتم زنبورعسل (شماره یک)
تولید جمعیت اولیه بصورت تصادفی
ارزیابی برازش[۲۰۵] جوابهای تولید شده در جمعیت
انتخاب سایتهای (جواب های) بهتر و ارسال زنبور به آن سایتها
بازگشت زنبورها به کندو و انجام رقص چرخشی
مقایسه همه زنبورهای یک سایت از لحاظ میزان برازش و انتخاب بهترین آنها
بهمنظور تولید جمعیت تکرار بعدی الگوریتم، سایتهای غیرمنتخب با پاسخهای تصادفی جایگزین میشوند.
ذخیره موقعیت بهترین پاسخ
تکرار مراحل ۲ تا ۷ در صورت برآورده نشدن شرایط خاتمه
همانطور که در بخش معرفی الگوریتم اشاره شد، الگوریتم زنبورعسل از یک رویه جستجوی همسایگی بهره میبرد که ساختار این روش بر این موضوع استوار است که جوابهایی که در همسایگی جواب مورد نظر قرار دارند را مورد بررسی قرار میدهد تا در صورتی که جواب یا جواب هایی با برازندگی بیشتر وجود داشته باشند، مورد توجه قرار بگیرند. در ادبیات تحقیق روشهای مختلفی برای پیادهسازی این رویه جستجو پیشنهاد شده است که در الگوریتم زنبور پیشنهاد شده در این تحقیق از روش جابجایی[۲۰۶] مشابه همان روشی که در الگوریتم ژنتیک مورد استفاده قرار میگیرد، استفاده شده است که با ایجاد تغییراتی جزئی در جواب، جوابهایی در همسایگی جواب فعلی ایجاد میکند.
۴-۳-۲٫ پارامترهای الگوریتم زنبورعسل (شماره یک)
n : تعداد زنبورهای پیشآهنگ

منبع فایل کامل این پایان نامه این سایت pipaf.ir است