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

کروموزوم:

۱

۲

۷

۳

۵

۴

۸

۶

 

۱

۲

۱

۲

۱

۲

۲

۱

 

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

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