الگوریتم ژنتیک و عملگر انتخاب

دانلود پایان نامه

در مسائل زمانبندی ماشینهای موازی معمولا برای ارزیابی یک کروموزوم یا همان محاسبه مقدار تابع هدف، کافی است که مسئله تکماشینه که به هم وابسته نیستند، بررسی شوند. اما در محیط ماشینهای موازی زمانیکه کارها از هم مستقل نباشند، به دلیل وجود محدودیتهای پیشنیازی دیگر نمیتوان ماشینها را از هم مستقل در نظر گرفت. از اینرو برای حل این مسئله، ما نیاز به یک محدودیت پیشنیازی پویا داریم. این محدودیت پیشنیازی که ترکیبی از است محدودیتهای پیشنیازی اولیه مسئله و محدودیتهای پیشنیازی که از ترتیب قرار گرفتن کارها بر روی ماشینها بوجود میآید. این کار باعث میشود که شما بتوانید یک ترتیب منطقی از کارها را بدست آورید که بدون تخطی از محدودیتهای پیشنیازی روی ماشینها پردازش میشوند. به منظور توضیح بیشتر این روش مثال زیر را در نظر بگیرید ولی قبل از آن را مجموعهی پیشنیازیهای اولیه مسئله و را مجموعهی پیشنیازیهای بدست آمده از این روش در نظر بگیرید.
برای این منظور کروموزومی که در شکل (4-1) نمایش داده است را در نظر بگیرید. با توجه به آن میتوان مشاهده نمود که کارهای 1، 6، 10 و 9 به ترتیب روی ماشین اول و کارهای 2، 3 و 8 به ترتیب روی ماشین دوم و کارهای 4، 5 و 7 به ترتیب روی ماشین سوم میبایستی پردازش شوند. با توجه به نحوهی قرارگیری کارها روی مثلاً ماشین دوم می توان متوجه شد که کار 2 حتماً میبایستی قبل از کار 3 پردازش شود و همین طور کار 3 میبایستی حتماً قبل از کار 8 پردازش شود. پس نحوهی قرارگیری کارها باعث ایجاد یک سری محدودیتهای دیگری علاوه بر محدودیتهای اولیه میگردد. از طرفی دیگر اگر برای این مثال محدودیت های پیش نیازی اولیه را بصورت در نظر بگیریم، آنگاه محدودیتهای پیشنیازی نهایی برای این کروموزوم به صورت میباشد. از این مثال می توان نتیجه گرفت که برای ارزیابی هر کروموزوم ما نیاز به مجموعه ای از محدودیتهای پیشنیازی جدید داریم.
4-2-1-4- مرتب سازی نامغلوب سریع
پس از ارزیابی هر یک از کروموزومها، جمعیت میبایستی با توجه به مفهوم غلبه به لبه های مختلفی تقسیم شوند. مفهوم غلبه با در نظر گرفتن دو تابع هدف کمینه سازی بصورت زیر تعریف میشود : و را دو تابع هدف، و را دو بردار تصمیمگیری در نظر بگیرید. مغلوب می کند را اگریکی از دو شرط زیر برقرار باشد.
1) and
2) and
حال با توجه به مقاله آقای دب و همکاران [77] به توضیح نحوه چگونگی تقسیم جمعیت بر روی لبههای مختلف میپردازیم. به منظور شفافسازی، ابتدا ما به توضیح رویهی خام و کندی که قبلاً برای مرتبسازی جمعیت روی لبههای نامغلوب استفاده میشد، میپردازیم. در رویه خام اولیه برای شناسایی حلهای لبهی نخست در یک جمعیت به اندازه ، هر حل میبایستی با سایر حلهای موجود در جمعیت مقایسه شود، تا مشخص شود که آیا مغلوب میشود یا خیر. از این رو برای هر حل نیاز به مقایسه می باشد، جاییکه تعداد توابع هدف میباشد. زمانیکه این فرآیند برای یافتن تمام اعضای لبهی نخست ادامه پیدا کند، آنگاه پیچیدگی کل برابر خواهد بود. در این مرحله تمامی اعضای لبهی نخست مشخص میشوند. به منظور یافتن اعضایی از جمعیت که در لبههای بعدی قرار میگیرند، حلهای تخصیص یافته به لبهی اول بطور موقتی از مجموعه-ی جوابها حذف و رویهی بالا ادامه مییابد. در بدترین حالت با پیچیدگی ، مجموعه غیرمغلوب بعدی بدست میآید، این فرآیند آنقدر تکرار میشود تا تمامی جوابها درون یک مجموعه نامغلوب قرار بگیرند. در بدترین حالت، این الگوریتم با پیچیدگی عملیاتی به جواب میرسد. اما راهکار سریعتر برای یافتن مجموعههای نامغلوب که در کل دارای پیچیدگی عملیاتی است، به صورت زیر میباشد :
ابتدا برای هر حلی مثل دو پارامتر و تعریف و محاسبه میشوند. بیانکننده تعداد جوابهایی است که حل را مغلوب میکنند و بیانکننده مجموعه حلهایی است که توسط حل مغلوب میشوند. در پایان این مرحله، تمامی حلهایی که دارای پارامتر هستند در لبهی اول قرار میگیرند. برای هر حل که دارای پارامتر ، برای هر حل مثل که در مجموعه قرار دارد، به اندازه یک واحد از پارامتر آن کم میکنیم. با انجام این کار، اگر برای هر عضوی مثل مقدار پارامتر باشد، ما آن را در مجموعه قرار میدهیم. اعضای مجموعهی در لبهی نامغلوب دوم قرار میگیرند. رویه بالا برای یافتن اعضای لبههای نامغلوب بعدی ادامه مییابد.
4-2-1-5- فاصله ازدحامی
همان طور که میدانید، حلهای متعلق به یک لبهی یکسان نمیتوانند یکدیگر را مغلوب کنند، حال این سوال پیش میآید که کدام یک از این حلها بهتر هستند؟ برای پاسخ به این سوال، یک عملگر جدید به منظور شناسایی پاسخهای بهتر نیاز میباشد، این عملگر فاصله ازدحامی نامیده میشود که گوناگونی خوبی را برای الگوریتم با حفظ یک پراکندگی یکنواخت روی لبههای نامغلوب ایجاد میکند. شکل (4-4) نشان دهندهی ناحیه محاسباتی فاصله ازدحامی برای یک حل میباشد که توسط مستطیل قرمز رنگ مشخص شده است. فاصله ازدحامی برای حل ام در لبهی ام با تابع هدف توسط رابطه زیر محاسبه میشود.
بطوریکه و مقادیر تابع هدف ام برای حلهای و میباشند. و به ترتیب بیشترین و کمترین مقادیر تابع هدف ام میباشند.
Cuboid
Cuboid
شکل (4-4)- نمونه ای از منطقه محاسباتی معیار فاصله ازدحامی
شکل (4-4)- نمونه ای از منطقه محاسباتی معیار فاصله ازدحامی

این مطلب مشابه را هم بخوانید :   تعزیرات حکومتی راجع به قاچاق کالا و ارز و تعزیرات حکومتی راجع به قاچاق کالا

4-2-1-6- معیار انتخاب والدین
در مرحله انتخاب، یک جفت از کروموزومها (والدین) برگزیده میشوند تا با هم ترکیب شوند. عملگر انتخاب، رابط بین دو نسل است و بعضی از اعضای نسل کنونی را به نسل آینده منتقل میکند. بعد از انتخاب، عملگرهای ژنتیک یعنی تقاطع و جهش روی دو عضو برگزیده اعمال میشوند. معیار انتخاب اعضا مطابق با برازندگی آن ها میباشد، اما روند انتخاب حالتی تصادفی دارد.
شاید انتخاب مستقیم و ترتیبی به این شکل که بهترین اعضا دو به دو انتخاب شوند در نگاه اول روش مناسبی به نظر برسد اما باید به نکتهای توجه داشت. در الگوریتم ژنتیک ما با ژنها روبرو هستیم. یک عضو با تطابق پایین اگر چه در نسل خودش عضو مناسبی نمیباشد اما ممکن است شامل ژنهای خوبی باشد که اگر به نسل بعدی انتقال یابد بتواند بهبود خوبی در نسل جدید ایجاد کند. پس روش انتخاب باید به گونهای باشد که به این عضو هم شانس انتخاب شدن بدهد. در الگوریتم NSGA- از روش انتخاب مسابقهای دوتایی استفاده میشود. در این روش دو عضو از جامعه به تصادف انتخاب میشوند و سپس بین آنها رقابتی ایجاد میگردد و از طریق اپراتور مقایسه کننده فشردگی بهترین از بین آنها برای انجام عملیات تقاطع انتخاب میگردد. مطابق دب و همکاران [77] اپراتور مقایسه کنندهی فشردگی بصورت زیر تعریف میگردد :
فرض کنید که برای هر عضو از جمعیت دو خصوصیت و وجود داشته باشد. خصوصیت اول بیان کننده این است که این عضو متعلق به کدام لبهی نامغلوب میباشد و خصوصیت دوم که همان فاصله ازدحامی میباشد. آنگاه برای خواهیم داشت :
با توجه به عبارت بالا میتوان استنباط کرد که بین دو حل، حلی در اولویت است که در لبهی بالاتری قرار دارد، البته از نظر کیفیت، یعنی حلی که در لبهی اول قرار دارد دارای بالاترین کیفیت است. در صورتیکه حلها در لبههای یکسانی قرار داشته باشند، حلی در اولویت است که فاصله ازدحامی بزرگتری داشته باشد.
4-2-1-7- عملگر تقاطع