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

جوابهای بد را از جمعیت حذف نمایید، آن چنان که نمونه های ایجاد شده از جوابهای خوب بتوانند جایگزین آن ها در جمعیت شوند.
جهت اجرای مراحل فوق روشهای متعددی وجود دارد. تعدادی از روشهای رایج عبارتند از: انتخاب تورنمنتی[۱۹۳] یا مسابقه ای، انتخاب متناسب[۱۹۴] و انتخاب رتبه ای[۱۹۵].
در انتخاب مسابقهای، مسابقههایی بین هر دو جواب اجرا شده و بهترین جواب انتخاب میشود و در استخر جفتگیری[۱۹۶] قرار میگیرد. از نو دو جواب دیگر انتخاب شده و بهترین آنها در استخر جفتگیری جای میگیرد. در صورتی که این رویه بهطور منظم صورت گیرد، هر جواب دقیقا در دو مسابقه شرکت میکند. بهترین جواب در جمعیت جوابی است که دوبار برنده شود و از این رو دو کپی از آن در جمعیت ایجاد میشود. ثابت شده است که انتخاب مسابقه ای نسبت به دیگر عملگرهایی که در بالا به آنها اشاره شد، دارای زمان محاسباتی کمتری است ]۲[..
در روش انتخاب متناسب، تعدادی کپی از جوابهایی ساخته میشود که این تعداد برای هر جواب متناسب با مقدار برازش آن است. اگر میانگین برازش همه عناصر جمعیت باشد، برای جوابی با مقدار برازش fi انتظار میرود که به تعداد کپی ایجاد گردد. اجرای این عملگر را میتوان همچون مکانیزم یک چرخ رولت فرض کرد که در آن چرخ به Pop-Size (اندازه جمعیت) قسمت تقسیم شده است واندازه هر قسمت متناسب با مقدار برازش هر یک از اعضای جمعیت است. این مکانیزم در سال ۱۹۸۹ توسط گلدبرگ به عنوان روشی انتخاب معرفی شد ]۲[.
در الگوریم ژنتیک پیشنهادی در این تحقیق، بهمنظور انتخاب والدین جهت انجام عمل تقاطع و تولید فرزندان جدید از آنها، سه روش انتخاب تصادفی[۱۹۷]، انتخاب مسابقهای و انتخاب بوسیله روش چرخ رولت در الگوریتم لحاظ شده است و میتوان هر کدام از روشها را به دلخواه انتخاب نمود. در روش انتخاب تصادفی، والدین به صورت کاملا تصادفی و بدون در نظر گرفتن میزان برازش آنها انتخاب میشوند. در روش انتخاب مسابقهای، طبق آنچه که در بالا اشاره شد برای انتخاب هر کدام از دو والد مورد نظر، دو (یا بیشتر از دو) جواب در یک مسابقه شرکت داده شده و بهترین آنها انتخاب میشود. روش سوم، روش انتخاب بوسیله چرخ رولت میباشد. در این روش برای افزایش کارایی از روش بولتزمان در محاسبه احتمالها استفاده میکنیم. در چرخه رولت، احتمال انتخاب متناظر با هر کروموزوم بر اساس برازندگی آن محاسبه میشود، به طوری که اگر fi مقدار برازندگی کروموزوم i ام باشد و Worst f بدترین مقدار برازندگی (بدترین مقدار تابع برازش) و beta یک پارامتر کنترل کننده باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
=exp (-beta* fi /Worst f) (4-1)
(۴-۲)
که n= Population size. در رابطه ۴-۱ اگر مقدار betaصفر باشد، روش انتخاب کروموزومهای والد از چرخه رولت به تصادفی تغییر میکند. مقدار beta بهگونه ای تنظیم میشود که مجموع احتمال بقای نیمه ابتدایی جمعیت ( نصف کروموزومها با تابع برازندگی بهتر) برابر ۸۰ درصد شود.
همانطور که میدانیم در روش انتخاب چرخه رولت به این صورت عمل میشود که در ابتدا یک عدد تصادفی بین صفر و یک تولید شده و سپس عدد مذکور در هر بازه ای که قرار بگیرد، کروموزوم متناظر با آن بازه انتخاب میشود. این روش همانند این است که یک چرخ را در نظر گرفته و آن را به تعداد کروموزومها طوری تقسیم کنیم که محیط هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص نگاه کرده و کروموزوم مربوطه را انتخاب میکنیم.
۴-۲-۵٫ اپراتورهای ژنتیک[۱۹۸]
عملگر تقاطعی[۱۹۹] عبارت است از آمیزش دو عضو از جمعیت والد و تولید یک یا دو فرزند جدید، به نحوی که هر فرزند بخشی از خصوصیات ژنتیکی و ساختاری والدین را داشته باشد. این روش توسط دومسایر[۲۰۰] معرفی شده و به نام عملگر تقاطع تک نقطهای[۲۰۱] شناخته شده است. در الگوریتم ژنتیک مورد استفاده در این تحقیق، از عملگر تقاطع تک نقطهای بهمنظور تولید فرزندان جدید از والدین استفاده شده است. نحوه کار این عملگر در توضیحات مربوط به الگوریتم ژنتیک بیان شدهاست. استفاده از این روش در بسیاری از موارد منجر به تولید جوابهایی در فضای غیرقانونی میشود بدین مفهوم که بر فرض مثال ممکن است در فرزندان تولید شده بوسیله این روش یک کار بیش از یکبار ظاهر شده و کار دیگری از مجموعه کارهای قابل پردازش حذف شود. در این صورت باید مکانیزم اصلاحی بر روی فرزندان صورت پذیرد. با توجه به این نکته که کار تکراری در فرزند اول همان کار حذفشده در فرزند دوم میباشد، لذا بدین صورت عمل میشود که در ابتدا کارهای تکراری در هر کدام از فرزندان شناسایی میشوند. سپس، کار تکراری در فرزند اول که در بخش اول کروموزوم (بخش قبل از نقطه تقاطع ) قرار دارد، با کار تکراری از فرزند دوم که در بخش اول آن واقع شده است، تعویض میگردد و در نتیجه جوابهایی قانونی تولید میشوند.
Cutting point Cutting point

۱ ۲ ۳ ۵ ۶ ۴ ۱ ۲ ۴ ۳ ۶ ۵
۱ ۲ ۱ ۲ ۱ ۲ ۱ ۲ ۲ ۱ ۱ ۲
برای دانلود فایل متن کامل پایان نامه به سایت 40y.ir مراجعه نمایید.