مباحث و عملگرهای پیشرفته وراثتی

مباحث و عملگرهای پیشرفته وراثتی

اسلاید 1: مباحث و عملگرهای پیشرفته وراثتیفصل چهارم مرتضی گرگین

اسلاید 2: فهرست آشنایی با مفاهیم عملگرهای انتخاب نگاهی عمیق تر به کاوش و بهره گیری (Exploitation vs. Exploration) عملگر همبری عملگرهای جهش در الگوریتم وراثتی حقیقی روشهای جایگزینی (انتخاب نسل بعد) حل مسایل چند مدی با الگوریتم وراثتیمعنی علامت :ادامه بحث در اسلاید بعدی

اسلاید 3: آشنایی با مفاهیم همگرایی زودرسغلبه چند جواب خوب در مراحل اولیه اجرای الگوریتمهمگرایی زود هنگام و به یک بهینه محلیفقدان تنوعنسبت افرادی که در برای تولید مثل برگزیده نمی‌شوند به کل جمعیتفشار انتخابامکان شرکت افراد برتر در تولید نسل بعدافزایش فشار انتخاب  ا فزایش فقدان تنوع  همگرایی زودرس

اسلاید 4: عملگر انتخابنمونه برداری عمومی اتفاقی ( Stochastic Universal Sampling)آشنایی با روشهای مقیاس کردن شایستگیمقیاس کردن خطیمحدود کردن سیگماانتخاب بولتزمنآشنایی با روشهای انتخاب رتبه ای (Ranked Based Selection)رتبه بندی خطی ( Linear Ranking)رتبه بندی نمایی ( Exponential Ranking)انتخاب تورنمنت ( Tournament Ranking)

اسلاید 5: نمونه برداری عمومی اتفاقیمشکلات روش چرخ گردان:اختلاف برازندگی میان کروموزم ها در نسل های اولیه زیاد استانتخاب برای تولید مثل بعضی کروموزمها بیشتر و بعضی کروموزمها کمتر از نرخ انتظاردر نتیجه فشار انتخاب بالا  فقدان تنوع  همگرایی زودرس روش نمونه برداری SUS در اینجا 4 = Nحرکت چرخ فقط یک مرتبه توسط N نشانگر که در فواصل مساوی قرار گرفته اندN والد انتخاب می‌شود.

اسلاید 6: آشنایی با روشهای مقیاس کردن شایستگیهدف تنظیم کردن فشار انتخاب است وقتی واریانس شایستگی کروموزومها خیلی زیاد و یا خیلی کم باشدواریانس شایستگی بالا  افزایش فشار انتخاب  همگرایی زودرسواریانس شایستگی پایین  کاهش فشار انتخاب  همگرایی کند و ضعیف برای ادامه نیاز به تعاریف زیر داریمانواع مقیاس کردن ها عبارتند ازمقیاس کردن خطیمحدود کردن سیگماانتخاب بولتزمن

اسلاید 7:  مقیاس کردن خطی شایستگی کروموزومها در نتیجه نرخ انتظار آنها توسط رابطه خطی زیر مقیاس می شودبه منظور تعیین ضرایب مقیاس یعنی a و b فرض می‌شود که نسبت نرخ انتظار بهترین عضو جمعیت به متوسط جمعیت یعنی بهتر است فرض شود ( کمترین فشار و بیشترین فشار )متوسط شایستگی جمعیت قبل و بعد از مقیاس کردن بدون تغییر باقی بماند.به عبارتی :

اسلاید 8: مقیاس کردن خطیعیب این روشممکن است پس از مقیاس شایستگی بعضی از کروموزمها منفی شود.دو روش برای اصلاح شایستگی های منفی نخست : شایستگی این افراد صفر در نظر گرفته شوددوم : استفاده از فرض البته بجای فرض یعنی ثابت بودن میانگین در قبل و بعد از مقیاس (در تعیین ضرایب a و b )

اسلاید 9: محدود کردن سیگما در ابتدای جستجو : انحراف معیار شایستگی بالا است احتمال انتخاب افراد شایسته بیشتر(کمتر) است احتمال ایجاد فقدان تنوع وجود دارداحتمال همگرایی زودرس وجود داردو با افزایش تعداد تکرار :انحراف معیار شایستگی پایین می آید احتمال انتخاب افراد شایسته کمتر می شودفشار انتخاب پایین می آیدهدف ثابت نگه داشتن فشار انتخاب در طول اجرای الگوریتم

اسلاید 10: محدود کردن سیگما تصحیح مقادیر شایستگی کروموزوم ها از رابطه زیرمیانگین شایستگی کروموزومها پس از تصحیح چون عملگر فوق یک عملگر خطی است پس نرخ انتظار هر کروموزوم پس از تصحیح برابر آیا پس از تصحیح شایستگی ها , شایستگی منفی خواهیم داشت ؟آیا شایستگی های منفی در اینجا نیاز به تصحیح دارند ؟ چرا ؟

اسلاید 11: محدود کردن سیگما If we suppose distribution of population is normal then is a 1/C of Mahalanobis distance.Distance of each chromosome’s fitness from average fitness.Then Expectation rate of each chromosome becomesIncrement of correlated axis value.Disadvantage:Selection intensity is const.It must change during algorithm1+3

اسلاید 12: انتخاب بولتزمن در انتخاب بولتزمنشروع الگوریتم جستجو با یک فشار کم (فرصت کافی برای جستجو)افزایش فشار انتخاب به تدریج ( افزایش سرعت رسیدن به پاسخ )مقیاس کردن شایستگی افراد جمعیت با رابطه زیرمانند روش ذوب شبیه سازی شدهT(t) نشان دهنده درجه حرارتT(t) می تواند یک تابع خطی یا نمایی از t باشد.درجه حرارت با دمای بالا در ابتدا آغاز و با گذشت t کاهش می یابد.در ابتدا فشار انتخاب کم و با گذشت t بر فشار انتخاب افزوده می ‌شود

اسلاید 13: آشنایی با روش های انتخاب رتبه ای  در انتخاب رتبه ایتفاوت میان مقادیر شایستگی افراد اهمیتی نداردصرفا رتبه هر فرد در قیاس با سایر افراد اهمیت داردهدف کنترل فشار انتخاب و جلوگیری از همگرایی زودرس استدو شکل قابل پیاده سازی آن عبارتند ازرتبه بندی خطیرتبه بندی نمایی

اسلاید 14: رتبه بندی خطی در رتبه بندی خطیابتدا افراد جمعیت بر حسب رتبه مرتب می‌شوند.کروموزوم با بیشترین شایستگی رتبه یک کروموزوم با کمترین شایستگی رتبه N نرخ احتمال انتخاب هر کروموزوم به منظور حضور در حوضچه ازدواجq و q0 نرخ احتمال بیشترین و کمترین شایستگی هستنداز آنجا که جمع تمام Pi ها باید یک شود به راحتی نتیجه می‌ شوداگر نرخ انتظار کروموزوم با بیشترین شایستگی 2 و کمترین صفر است . چرا ؟ اگر نرخ انتظار برای تمام کروموزوم ها یکسان است . پایین ترین فشار انتخاب .

اسلاید 15: رتبه بندی خطیدر رتبه بندی خطیاندازه شایستگی افراد هیچ نقشی در نرخ احتمال تخصیص یافته به آنها نداردبه هیچ کروموزمی نرخ انتخاب چندان بزرگی داده نمی‌شود هنگامی که واریانس برازندگی جمعیت بالاست فشار انتخاب کنترل می‌شود.هنگامی که واریانس برازندگی پایین است فشار انتخاب ثابت نگه داشته می‌شودتفاضل نرخ انتظار کروموزوم با رتبه i با کروموزوم با رتبه i+1 مستقل از i و دفعات تکرار الگوریتم است چرا ؟ اثبات کنید .

اسلاید 16: رتبه بندی نماییدر رتبه بندی نماییمانند رتبه بندی خطی مرتب و رتبه بین 1 تا N به کروموزوم ها تخصیص داده می شودسپس به هر یک از کروموزومها نرخ احتمالی بر اساس رابطه زیر تخصیص می یابد.می‌توان تصور کرد Ri تعداد آزمایشات برنولی تا رسیدن به اولین موفقیت است .موفقیت انتخاب کروموزوم با بیشترین شایستگی است که احتمال آن در هر آزمایش مستقل q است .می توان مقدار احتمال q را به راحتی به عنوان یک پارامتر برای این روش تعیین نمود.مانند قبل اندازه شایستگی افراد (در رتبه فعلی) هیچ نقشی در نرخ احتمال تخصیص یافته به آنها نداردنسبت نرخ انتظار کروموزوم با رتبه i با کروموزوم با رتبه i +1 مستقل از i و دفعات تکرار الگوریتم است چرا ؟ اثبات کنید .

اسلاید 17: برای انتخاب کروموزوم ها از شیوه چرخ گردان یا نمونه برداری عمومی اتفاقی استفاده کردعیب رتبه بندی دو عیب روش های رتبه بندی بطور کلی پارامترهای این روشها توسط کاربر تعیین می‌شودبه اختلاف شایستگی کروموزوم ها اهمیتی داده نمی‌شودسوال :در دو روش رتبه بندی و در سه روش مقیاس کردن که تا کنون بحث شدبعد از محاسبه نرخ احتمال مشارکت هر کروموزوم در تولید نسل آتی چه باید کرد ؟پاسخ

اسلاید 18: انتخاب تورنمنت کنترل فشار انتخاب ,مستقل از اندازه شایستگی مانند روش انتخاب رتبه‌ایاز نظر پیچیدگی محاسباتی بسیار کم هزینه تر از سایر روش ها برای انتخاب N کروموزوم N بار مراحل زیر انجام می‌گیردتعداد k کروموزوم (اندازه تورنمنت) بصورت اتفاقی از جمعیت خارج شده .کپی بهترین آنها به حوضچه تزویج منتقل می‌شودکم ترین فشار انتخاب برای حالت K=2 یعنی تورنمنت باینری می باشد .در تورنمنت باینری نرخ انتظار شایسته ترین کروموزوم 2 است. چرا ؟ با افزایش مقدار k فشار انتخاب افزایش می‌یابددر ادامه یک روش برای انتخاب تورنمنت باینری با استفاده از تابع بولتزمن خواهیم دید

اسلاید 19: انتخاب تورنمنت باینریکروموزوم های i وj به صورت تصادفی از جمعیت انتخاب می شوندکروموزوم برنده توسط رابطه روبرو مشخص می شودrand یک عدد تصادفی بین صفر و یکمقدار اولیهT(t) بزرگ است و رفته رفته کاهش می‌یابد پسبا کاهش دما شانس انتخاب کروموزوم های ضعیف تر کمتر می‌گردد الگوریتم با فشار انتخاب کم جستجو را آغاز کرده و به تدریج این فشار افزایش می‌یابد.سمت راست نامساوی یک تابع سیگموئید است به مرکز fitj مقدار T بزرگ انتقال تابع از صفر به یک بصورت نرم استمقدارT کوچک انتقال تابع از صفر به یک بصورت سریع است. T=1T=1/2

اسلاید 20: نگاهی عمیق تر به کاوش و بهره گیری (Exploitation vs. Exploration) در صورتیکه تنوع ژن و کروموزوم در جمعیت وجود داشته باشد ایجاد نقاط جدید با به اشتراک گذاشتن اطلاعات دو کروموزوم یعنی عملگر همبریتوانایی کاوش یک الگوریتم تحت تاثیر عملگر همبری استعملگر جهش با تغییرات کم و یا جزئی پیرامون جواب به جستجو می پردازد .توانایی بهره‌گیری یک الگوریتم تحت تاثیر عملگر جهش استعملگر انتخاب با کنترل فشار نقش بسزایی در توانایی کاوش و بهره‌گیری دارد

اسلاید 21: نگاهی عمیق تر به کاوش و بهره گیری (Exploitation vs. Exploration) در صورتیکه تنوع ژن و کروموزوم در جمعیت وجود نداشته باشد فرزندان تولید شده توسط عملگر همبری اختلاف چندانی با والدین ندارند. نقش عملگر همبری عوض می شود عملگر همبری باعث افزایش توانایی بهره گیری الگوریتم می‌شوداعمال عملگر جهش با نرخ مناسب باعث تنوع در جمعیت خواهد شد عملگر جهش موجبات افزایش توانایی کاوش الگوریتم خواهد شد

اسلاید 22: نگاهی عمیق تر به کاوش و بهره گیری (Exploitation vs. Exploration) الگوریتم وراثتی در صورتی در بهینه های محلی قرار می گیرد کهقدرت کاوش خود را زود هنگام از دست بدهد راه حل :کنترل فشار انتخاب در عملگر انتخاب (کاهش فشار انتخاب) افزایش نرخ جهش ترکیبی از آن ها بطور کلی در تعیین پارامتر های الگوریتم بایدبا توجه به مساله و شرایط حاکم بر روند پیشرفت حل آن بصورت پویا باشددر ابتدای جستجو از قدرت کاوش بالا برخوردار باشد رفته رفته قدرت کاوش کاسته شود و بهره گیری افزایش یابد

اسلاید 23: عملگر همبری ( Crossover )همبری دو نقطه ایهمبری چند نقطه ایهمبری یکنواختهمبری مبتنی بر شایستگیهمبری نا یکنواخت مبتنی بر ماسک الگوهمبری چند والدیهمبری چند والدی قطری

اسلاید 24: عملگر همبری ( Crossover )همبری حسابیمحدبافینخطیهمبری خطهمبری جهت دارهمبری مخلوطهمبری باینری شبیه سازی شده

اسلاید 25: همبری دونقطه ای( Two-point Crossover )در این نوع همبری انتخاب دو موقعیت بطور تصادفی بین 1 و L (طول کروموزوم برحسب بیت) جابجایی تمام بیت های بین این دو نقطه در کروموزوم والد 10110000111010010101Do Crossoverمحل برش 1محل برش 2Binary

اسلاید 26: همبری چند دونقطه ای( Multi-point Crossover )در این نوع همبریانتخاب چند موقعیت بطور تصادفی بین 1وL (طول کروموزوم برحسب بیت) جابجایی بیت های بین نقاط برش کروموزوم والد 101011101001Do Crossover01011000محل های برشBinary

اسلاید 27: 0همبری یکنواخت(Uniform crossover)در این نوع همبرییک ماسک الگو با مقادیر اتفاقی صفر و یک ایجاد می‌شودمقادیر بیت های آن با احتمال 0.5 صفر یا یک است طول آن با طول کروموزوم ها برابر است.مثلاتولید دو فرزند با جابجایی بیت هایی از والد که بر روی ماسک, مقدار یک دارند11Do Crossover01101010011010Binary10101001101001010000000Parent 1Parent 2Mask

اسلاید 28: همبری مبتنی بر شایستگی (Fitness based crossover)در این نوع همبری که ایده آن از همبری یکنواخت گرفته شده :تمام مراحل انجام این عملگر مانند عملگر همبری یکنواخت است .یک ماسک الگو با مقادیر اتفاقی صفر و یک ایجاد می‌شودمقادیر بیت های آن به کروموزوم با شایستگی بیشتر احتمال مشارکت بیشتر می‌دهداحتمال یک شدن بیت های ماسکبنابراین بدیهی است که ماسک را روی کروموزوم با شایستگی کمتر قرار می‌دهیم بیت هایی که بر روی ماسک مقدار یک دارد را از کروموزوم دیگر(شایستگی بیشتر) انتخاب می‌کنیممعایب این روش نیاز به تولید دو ماسک مجزا برای تولید دو فرزندباعث کاهش غنای ژنی و تنوع در جمعیت  کاهش قدرت کاوش الگوریتمBinary

اسلاید 29: همبری نایکنواخت مبتنی بر ماسک الگوبا ایده و هدف استخراج اطلاعات ژن های برتر جمعیت بطور آماری برای هر نسل یک ماسک الگو ایجاد می گردداز ماسک الگوی ایجاد شده در همبری استفاده می شود (به منظور انتقال خصوصیات برتر به فرزندان )برای ایجاد ماسک الگو ابتدا جمعیت بر اساس شایستگی مرتب می‌شودانتخاب N/4 جمعیت با بیشترین برازش برای تهیه ماسک مثبتانتخاب N/4 جمعیت با کمترین برازش برای تهیه ماسک منفیبرای هر بیت از این ماسک ها (مثبت و یا منفی)صفر و یک های بیت متناظر شمرده می‌شود مقدار بیشتر به بیت متناظر نسبت داده می‌شودبرای تهیه ماسک الگو از ماسک مثبت و منفی استفاده می‌شودچنانچه بیت های متناظر در ماسک های مثبت و منفی با یکدیگر متفاوت باشند مقدار بیت متناظر در ماسک مثبتدر غیر اینصورت X ( بدون اهمیت) در نظر گرفته می شود .

اسلاید 30: همبری نایکنواخت مبتنی بر ماسک الگوExample10100100000011101X1X0X0XPopulationPopulationPopulationPopulationPopulationPopulationPopulationPopulation101001001010000011111110010001111111010100110011000000001111111000011000011110010011000001100+-Pattern MaskDescending Fitness

اسلاید 31: همبری نایکنواخت مبتنی بر ماسک الگوپس از تولید ماسک عمل همبری و نحوه استفاده از ماسک به روش زیرانتخاب کروموزوم های والد تعیین هر یک از بیت های کروموزوم فرزند با در نظر گرفتن بیت های متناظر در کروموزوم والد و ماسک الگوبیت های والد مشابه و بیت ماسک الگو نیز یا مشابه و یا بدون اهمیت باشد  بیت فرزند مشابه بیت والدینبیت های والد مشابه و متضاد با بیت ماسک الگو  به احتمال بیت فرزند از ماسک و مشابه بیت والدینبیت های والدین در تضاد و بیت ماسک بدون اهمیت  احتمال انتخاب بیت از والدین با احتمال بیت های والدین در تضاد و بیت ماسک 0 یا 1 به احتمال از ماسک و به احتمال از والد و با احتمال از هر یکمعایب این روش پیچیدگی محاسباتی بالایی دارددر هر نسل ابتدا باید ماسک الگو ساخته شوداز هر دو والد یک فرزند تولید می شودبا افزایش غنی ژنی جمعیت به شدت کاهش می یابد.

اسلاید 32: همبری چند والدیاین روش ها تعمیم یافته روش های همبری دو والدی هستندامکان ایجاد فرزند با هر تعدادی از والدین وجود دارددر عمل همبری با بیش از چهار والد سود چندانی ندارددو همبری متداول چند والدی همبری چند والدی قطریهمبری یکنواخت چند والدیهمبری مبتنی بر شایستگی چند والدیBinary

اسلاید 33: همبری چند والدی قطریهمبری چند والدی قطریدر این روش k والد ازk - 1 نقطه برش داده می‌شودمحل های برش بطور تصادفی بین 1 و L طول کروموزوم است .فقط k فرزند بصورت قطری می‌تواند ایجاد شود اگرچه امکان k ! حالت در انتخاب فرزند (قطری و غیر قطری) داریم شکل زیر همبری سه والدی قطری را نشان می‌دهددو برش(k - 1 )در هر سه والد ایجاد می‌کنیم101100010100010110111110000010Childs101100010100010110111110000010P1 :BinaryP2 :P3 :محل برش 1محل برش 2

اسلاید 34: Binaryهمبری یکنواخت و مبتنی بر شایستگی چند والدیدر همبری یکنواخت چند والدی این همبری تعمیمی بر همبری یکنواخت دو والدی است.هر بیت فرزند از یکی از والدینش با احتمال برابر 1/k انتخاب می‌شوددر هر عمل همبری تنها یک فرزند تولید می‌شوددر همبری مبتنی بر شایستگی چند والدی این همبری تعمیمی بر همبری مبتنی بر شایستگی دو والدی است.همبری یکنواخت چند والدی استهر بیت فرزند از یکی از والدینش با احتمال متناسب با شایستگی آن والد انتخاب می‌شود

اسلاید 35: همبری حسابیشکل کلی عملگرهای حسابیP2 , P1 والد 1 و والد 2 O2 , O1 فرزند 1 و فرزند 2با توجه به محدودیت های اعمال شده روی سه نوع عملگر حسابی خواهیم داشتهمبری محدببا محدودیت های همبری افینبا محدودیت های همبری خطیفقط با محدودیتRealنکته مهم: بردارهایی به طول تعداد ژن های موجود در کروموزوم والد هستند

اسلاید 36: همبری خط(Line Crossover)اتصال والدین توسط یک بردار به یکدیگر در فضای متغییرهای تصمیمانتخاب یک نقطه تصادفی بر روی این بردارشکل کلی همبری خطبرای درک بهتر محدوده حرکت روی نقطه O کلیک کنیدP2 , P1 والد 1 و والد 2 O فرزندα یک عدد اسکالر تصادفی در بازه (0 1)اگرمحدوده α به [-d , 1 + d] محدود شود محدوده‌حرکت O به شکل روبرو استd میزان دور شدن از محدوده والدین را مشخص می‌کندRealOP1P2OP1P2-d 1 + d

اسلاید 37: همبری جهت دار(Direction-based )هدف: استفاده از دانش تولید شده و موجود در نقاط برای ایجاد فرزندان شایسته ترشکل کلی همبری جهت دار(یا حریصانه)با فرض در مساله بیشینه سازیو یا فرض در مساله کمینه سازی برای درک بهتر محدوده حرکت O روی نقطه کلیک کنیدP2 , P1 والد 1 و والد 2 O فرزندr یک عدد اسکالر تصادفی در بازه (0 1)یک نوع عملگر حسابی افین با پارامترهای می باشددر صورتیکه P2 , P1 به هم نزدیک باشند بردار P2 -P1 جهت تقریبی گرادیان را مشخص می‌کند.RealOP1P2بزرگی آن به r بستگی دارد

اسلاید 38: P2P1همبری مخلوط(Blend crossover)در این همبریایجاد دو نقطه طبق رابطه انتخاب یک نقطه تصادفی O بر روی خط واصل این دو نقطه به عنوان فرزند برای درک بهتر محدوده انتخاب O کلیک کنیدP2 , P1 والد 1 و والد 2 α یک عدد نامنفیدر این همبری چنانچه مقدار α بزرگ انتخاب شود محدوده انتخاب فرزند گسترش یافته  قدرت کاوش الگوریتم افزایش می‌یابدبرابر صفر باشد فرزند ایجاد شده بر روی خط واصل والد 1 و 2 خواهد بود.( همبری خط)0/5 انتخاب شود بهترین شرایط برای این همبری حاصل می‌گردد. RealOاینجا

اسلاید 39: همبری باینری شبیه سازی شده Simulated binary Crossover- (SBX)در این همبری فرزندان از رابطه روبرو تولید می‌شونداین همبری یک نوع عملگر حسابی افین می‌باشد P2 , P1 والد 1 و والد 2 βq از رابطه زیر تولید می‌شودβ بردار و اندیس آن نشان دهنده مولفه u یک عدد تصادفی بین صفر و یک است اتا یک عدد حقیقی نامنفی( شاخص عملگر همبری ما )مقادیر بزرگ این پارامتر میل βq به سمت یک ایجاد فرزندان در نزدیکی والدینمقادیر کوچک این پارامترافزایش احتمال تولید فرزندان دورتر از والدینبرای درک شهودی بهتر , u نزدیک به یک و اتا برابر با صفر در نظر بگیرید  βq می تواند عدد بسیار بزرگی شود .β در این همبری نسبت فاصله فرزندان به فاصله والدین در هر بعد برابر ضریب β استشاید بد نباشد چگالی احتمال β هم را بدانید

اسلاید 40: عملگرهای جهش در الگوریتم وراثتی حقیقی  انتخاب تعدادی از متغیرها در جمعیت بصورت اتفاقی و با توجه به نرخ جهش تغییر هر متغییر با توجه به نوع جهش و جایگزین مجدد در جمعیت شکل کلی این عملگر برای اعداد حقیقی به شکل زیر استدر اسلاید بعد دو نوع مهم آنها معرفی می‌شوند.

اسلاید 41: عملگرهای جهش در الگوریتم وراثتی حقیقی جهش یکنواخت: یک عدد تصادفی با توزیع یکنواخت در بازه می باشد جهش غیر یکنواخت (پویا) : طبق رابطه زیر محاسبه می‌شود یک عدد تصادفی b یک عدد ثابت ضریب یکنواختی t شمارنده تعداد تکرار الگوریتم وراثتیT حداکثر تعداد تکرارا الگوریتم وراثتی به مرور زمان جمله کوچک می‌شود بنابراین تغییرات ایجاد شده کوچک می‌شوددر ابتدا افزایش کاوش و در انتها افزایش بهره گیری

اسلاید 42:  روش های جایگزینی (انتخاب نسل بعد)در انتهای هر تکرار از میان دو نسل (شامل 2N عضو ) باید تعداد N عضو برای ادامه انتخاب شود .راههای متعددی برای این منظور موجود است .روش اول : جایگزینی نسلی (حذف همه Delete –all )ضمانتی برای بقا بهترین اعضا جمعیت وجود ندارد چونممکن است برای زاد و ولد انتخاب نشودخصوصیات بارز خود را در خلال عملگرهای همبری و جهش از دست بدهد.N = فرزندانN = نسل والد

اسلاید 43: جایگزینی حالت پایدار  روش دوم:جایگزینی حالت پایدار(Steady State Replacement)تعداد معدودی از جمعیت حذف می شوندحذف بر اساس ضعیف ترینحذف بصورت اتفاقیحذف والدینی که کروموزوم فرزند از آن ایجاد شده است به همان تعداد فرزند تولید و جایگزین می‌شوندفرزندانN = نسل والدانتخاب ضعیف ترین هاانتخاب اتفاقییا انتخاب جهت تولید فرزند

اسلاید 44: نخبه گرا Elitism روش سوم : انتخاب نخبه گرا ( Elitism Selection )این روش مبتنی بر روش اول یعنی جایگزینی نسلی است .یک یا چند فرد با بیشترین شایستگی بطور مستقیم به نسل بعد منتقل می‌شوند.حادترین شکل انتخاب نخبه گرا انتخاب N کروموزمی که برترند از بین 2N اعضای نسل های والد و فرزند.در این حالت قابلیت کاوش در پایین ترین سطح خود می باشد و قابلیت بهره گیری در بالاترین سطح خود قرار دارد

اسلاید 45: روش ازدحامی Crowding replacement روش چهارم : روش ازدحامی ( Crowding replacement )برای هر یک از فرزندان تولید شده ابتدابه تعداد CF عضو از اعضای جمعیت به طور تصادفی انتخاب می‌شوندمعمولا CF (ضریب ازدحام) 2 یا 3 انتخاب می شود.فرزند تولید شده جایگزین شبیه ترین عضو از مجموعه CF می ‌شود مقایسه با سایر روش هانسبت به سایر روش ها زمانگیر تر است .حفظ تنوع جمعیت دراین روش مد نظر قرار می گیردخطر رکود الگوریتم و همگرایی زودرس کمتر است تنوع جمعیت به جمعیت اولیه بستگی زیادی دارد

اسلاید 46: روش ازدحامی Crowding replacement روش چهارم : روش ازدحامی ( Crowding replacement )برای هر یک از فرزندان تولید شده ابتدابه تعداد عضو از اعضای جمعیت به طور تصادفی انتخاب می‌شوندمعمولا (ضریب ازدحام) 2 یا 3 انتخاب می شود.فرزند تولید شده جایگزین شبیه ترین فرزند می ‌شودفرزندانN = نسل والدتولید فرزندانتخاب CF عضو تصادفیمقایسهشبیه‌ترینجایگزینی

اسلاید 47: مسایل چند مدی با الگوریتم وراثتیچند مدی : مسائل دارای چندین بهینه (محلی و فرامحلی) امکان دارد بهینه های مختلف تابع مقادیر یکسان یا متفاوتی داشته باشندهدف : پیدا کردن تمام بهینه هامشکل الگوریتم وراثتی در حل مسایل چند مدی: همگرایی الگوریتم به یک بهینه محلی یا فرا محلی ناشی از پدیده رانش وراثتیعوامل شکل گیری پدیده رانش وراثتی :فشار انتخاب : مراجعه به اسلایدهای قبلینویز انتخاب : تفاوت بین نرخ انتخاب و میزان انتخاب که ناشی از اتفاقی بودن عملگر است اثر تخریبی عملگر:عملگرهای همبری و جهش اثرات مخربی در کروموزوم ها دارند

اسلاید 48: مفهوم گونه سازی و جایگاه گونه سازی :فرایندی که به موجب آن یک گونه به چند گونه متفاوت منشعب می‌شودگونه های متفاوت جایگاه های متفاوت اشغال می‌کنند گونه های متفاوت دارای ویژگی های ژنی متفاوتی هستندگونه های متفاوت با محیط (جایگاه) های متفاوت سازگار هستندجایگاه :در مسائل چند مدی , هر بیشینه تابع معادل با یک جایگاه است هر جایگاه باید متناسب با شایستگی اش به سایر جایگاه ها عضو داشته باشد.عضو های هر جایگاه گونه های متفاوت موجود در یک نسل هستند.

اسلاید 49: روش های جستجوی وراثتی در مسایل چند مدیحفظ تنوع:حفظ تنوع در جمعیت بوسیله ایجاد گونه های متفاوت جلوگیری از همگرایی الگوریتم به یک بهینه و در نتیجه کشف و شناسایی سایر جایگاههاتسهیم :تعیین شایستگی افراد با توجه به تعداد افرادی که در یک جایگاه حضور دارند می‌شودتسهیم شایستگی به منظور جلوگیری از تجمع افراد (گونه ها) در یک جایگاهتعدادی از روشهای ارایه شده در این زمینهسایر روش هاتسهیمحفظ تنوعجایگاه ترتیبی تسهیم شایستگیپیش انتخابروش ازدحامیمحدودیت ازدواجاصلاح نژاد

اسلاید 50: روش پیش انتخاباولین روش در زمینه حمایت از جایگاه Preselection (کاویچیو در سال 1970)هدف : جلوگیری از تجمع کروموزوم ها در یک بهینه تمامی اعضای جمعیت شانس یکسانی برای انتخاب دارندهر فرزند صرفا با والدینش جهت جایگزینی رقابت می‌کند.رقابت حریصانه میان والد و فرزند.در صورتیکه فرزند شایستگی بیشتری داشته باشد با والد خود جایگزین خواهد شداین روش قدری به روش جایگزینی حالت پایدار شباهت دارد.البته با محدودیتی بیشتر یعنی جایگزینی به شرط بهتر بودن شایستگی فرزند از والد

اسلاید 51: روش ازدحامی دی جانگ در سال 1975 یعنی 5 سال بعد روش Preselection را توسعه دادبا انتخاب عضو با بیشتری شباهت برای جایگزینی تغییرات توزیع جمعیت را کم می‌کند.در این روش کسری از جمعیت ,G,انتخاب می شود تا نسل فرزند را از طریق تولید مثل بوجود آوردمعیار فقدان تنوع با تغییرات G قابل کنترل است .برای جایگزینی فرزندان تولید شده , هر بار تعداد CF عضو از اعضای جمعیت بطور تصادفی انتخاب می‌شود.ضریب ازدحام , CF, معمولا 2 و یا 3 انتخاب می‌شودفرزند جایگزین عضو با بالاترین شباهت می شودمعیار شباهت می تواند مانند فاصله همینگ مستقل از نوع مساله و در سطح ژنی Genotype باشد.وابسته به قلمرو مساله و بر مبنای سطح رفتاری Phenotype باشد.روشهای پیش انتخاب و ازدحامی در عمل قادر به یافتن بیش از دو بهینه در مساله نیستند

اسلاید 52: تسهیم شایستگیمعرفی این روش توسط هلند در سال 1975 و توسعه آن توسط گلدبرگ و ریچاردسون در سال 1987 ایده اصلی: کاهش شایستگی آن دسته از اعضای جمعیت که خیلی به یکدیگر نزدیک هستند حفظ تنوع جمعیت و حمایت از گونه سازی برای کشف بهینه های محلی محاسبه تابع شایستگی از رابطه مقابل fiti sh(t) شایستگی تسهیم شده کروموزوم i mi(t) تابعی از چگالی کروموزوم ها در همسایگی کروموزوم id( i, j, t) فاصله شباهت بین کروموزوم i,j در سطح ژنی یا رفتاریSh(.) با توجه به فاصله میان کروموزوم i,j یک عدد بین صفر و یک هر چه میزان شباهت بیشتر باشد (فاصله کم) به یک نزدیک تر استو بیانگر شعاع و پارامتر آلفا عموما برابر یک در نظر گرفته می‌شود

اسلاید 53: تسهیم شایستگیمقایسه مقادیر مختلف آلفا :جلوگیری از همگرایی تمام اعضای جمعیت به یک بهینه در قیاس با روش های پیش انتخاب و ازدحامی ,هوشمندانه تر و موثر تر استیکی از مشهورترین روشهای مبتنی بر جایگاه استعیب اصلی این روش در تخمین شعاع جایگاه و تعداد جایگاه (بهینه) می باشد.

اسلاید 54: محدودیت ازدواجدر حوزه مسایل چند مدی : همبری دو عضو از جایگاه متفاوت(حتی شایسته)  فرزندانی با کارایی پایین (احتمال بالا)هدف : حمایت از گونه سازی و کاهش تولید فرزندان مخرب استروش دب و گلدبرگ برای محدودیت ازدواج(با استفاده از مفهوم شعاع ازدواج)انتخاب والد اول انتخاب همسر در یک همسایگی به شعاع ازدواج در صورت عدم وجود همسر در این شعاع انتخاب والد بعدی بطور تصادفی

اسلاید 55: اصلاح نژادروش اصلاح نژاد (Line breeding)اصلاح نژاد : یک نوع محدودیت جفت گیری در حیوانات اهلی استاز یک حیوان اصیل برای جفت گیری با سایرین استفاده می‌شودصرفا در مسایل تک مدی خوب عمل می‌کندبه منظور غلبه بر این مشکل :ازدواج خویشاوندی با پیوند دو جنسی توسط هلستین در سال 1971تا زمانیکه متوسط شایستگی اعضای درون جایگاه افزایش می‌یابداعضای نزدیک به هم (متعلق به یک جایگاه) با یکدیگر ازدواج کنندچنانچه رشد متوسط شایستگی متوقف شدازدواج بین جایگاهی توصیه می‌شود

اسلاید 56: روش جایگاه ترتیبیبرای حل مسایل چند مدی علاوه بر روش های ذکر شده روش های دیگری ارایه شدهروش جایگاه ترتیبی (Sequential niching)استفاده از الگوریتم وراثتی سادهیافتن یک بهینه از بهینه های مسالهحذف بهینه های قبلی از قلمرو جستجو در هر بار