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

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

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

4-2-1-8- عملگر جهش


در طبیعت برخی عوامل مانند اشعه ماورای بنفش باعث به وجود آمدن تغییرات غیر قابل پیشبینی در کروموزومها میشوند. از آنجاییکه الگوریتم ژنتیک از قانون تکاملی پیروی میکند، در این الگوریتم نیز عملگر جهش با احتمال کم اعمال میشود. جهش باعث جستجو در فضاهای دست نخورده مسئله میشود. میتوان استنباط کرد که مهمترین وظیفه جهش اجتناب از همگرایی به بهینه محلی است. در رابطه با این عملگر مفهومی به نام نرخ جهش وجود دارد. نرخ جهش عبارتست از درصدی از تعداد کروموزومها که دچار جهش میشوند. اگر نرخ جهش خیلی کوچک باشد، تعداد زیادی از کروموزومها که با ایجاد یک جهش میتوانستند مفید باشند تست نمیشوند و اگر نرخ جهش خیلی بزرگ باشد، یک اختلال تصادفی بوجود آمده که این امر باعث از بین رفتن حافظه تاریخی الگوریتم میشود. عملگرهای مختلف جهش وجود دارند که مهترین آنها عبارتند از : جابجایی، وارونگی و جاگذاری. عملگر جهشی که در این تحقیق استفاده شده است شبیه به نوع جابجایی می باشد. مثالی از این نوع عملگر جهش در شکل (4-6) نمایش داده است. مکانیزم انجام عملیات جهش به ترتیب مراحل زیر می باشد:
1) به تصادف کروموزومی را از جمعیت انتخاب و سطر اول آن را در نظر میگیریم.
2) دو ژن به تصادف انتخاب کرده و جای آنها را با هم عوض میکنیم.
3) سطر اول بدست آمده برای فرزند ممکن است که محدودیتهای پیشنیازی را رعایت نکند، از این رو با استفاده از الگوریتم اصلاحی، میتوان سطر اول بدست آمده برای فرزند را اصلاح نمود.
4) به منظور ایجاد سطر دوم فرزند، ابتدا برای ژن (کار) هایی که جابجا نشدهاند، ببینید که در کروموزوم والد آن کار به چه ماشینی اختصاص یافته است، در کروموزوم فرزند هم آن کار را به همان ماشین اختصاص دهید. اما به ازای هرکاری که جابجا شده است یک عدد تصادفی بین [0 1] تولید کنید، اگر این عدد کوچکتر از 0.5 بود (50% شانس برای ارث بردن از والد) رویه بالا را دوباره بکار ببرید، در غیر این صورت از میان مجموعه ماشینهایی که میتوانند کار موردنظر را پردازش کنند یکی را به تصادف (بطوریکه ماشین قبلی دوباره تکرار نشود) به آن کار اختصاص دهید.
4-2-1-9- استراتژی تولید دوباره
پس از تولید جمعیت فرزندان، نسل بعدی الگوریتم میبایستی از میان جمعیت ترکیبی که حاصل از ترکیب جمعیت نسل قبلی و جمعیت فرزندان میباشد، انتخاب شوند. در الگوریتم NSGA- از استراتژی نخبه گرایی برای انتخاب جمعیت نسل جدید استفاده شده است. این استراتژی به این صورت است که ابتدا اعضای جمعیت ترکیبی را رتبه بندی و سپس فاصله ازدحامی مربوط به هر یک از اعضای جمعیت را محاسبه میکنیم. در مرحله بعد جمعیت موجود در هر فرانت را بر مبنای فاصلهی ازدحامی و بصورت نزولی مرتب میکنیم و در ادامه کل اعضای جمعیت را بر مبنای رتبهی آنها بصورت صعودی مرتب میکنیم. جمعیت ترکیبی بدست آمده، جمعیتی است که بر اساس ارزش هر یک از اعضا مرتب شده است، یعنی عضوی که در رتبه یک قرار دارد بهترین عضو جمعیت شناخته میشود. برای تولید نسل بعدی کافی است در جمعیت ترکیبی مرتب شده به اندازه جمعیت اولیه بهترینها را جدا کنیم.
Parent 2
Parent 2
Parent 1
Parent 1
(a)
(a)

این مطلب مشابه را هم بخوانید :   اسناد بین المللی و صادرات غیر نفتی

2
1
3
5