فهرست مطالب این تاپیک:
منبع: kelidestan.com
- تعریف تابع هزینه در الگوریتم های بهینه سازی
- الگوریتم ژنتیک (GA-Genetic Algorithm)
منبع: kelidestan.com
الگوریتم های بهینه سازی
- شروع کننده موضوع P O U R I A
- تاریخ شروع
تعریف تابع هزینه در الگوریتم های بهینه سازی
تعریف تابع هزینه در الگوریتم های بهینه سازی
هنگام طراحی و کدنویسی الگوریتم های بهینه سازی (مثل الگوریتم ژنتیک)، یکی از رایج ترین سوالات، چگونگی تعریف تابع هزینه می باشد. در اینجا قصد دارم که با چندین مثال، نحوه تعریف تابع هزینه برای الگوریتم های بهینه سازی رو شرح بدم.
قبل از هر چیز، باید بدانید که برای تعریف تابع هزینه، یک قانون کلی که باعث شود شما یک تابع هزینه منحصر بفرد تعریف کنید، وجود ندارد، بلکه تنها یک روند کلی وجود دارد. بنابراین ممکن است که افراد مختلف، برای یک مسئله واحد، توابع هزینه متفاوتی تعریف کنند. در واقع فرد باید در مورد نحوه تعریف تابع هزینه، به خوبی فکر کند و یک تابع هزینه مناسب برای مسئله بیابد.
زمانی که ما یک مسئله بهینه سازی داریم، قرار است که یک یا چند پارامتر را بهینه کنیم (بهترین مقادیر یا انتخاب ممکن را برای آنها بیابیم). برای یافتن جواب بهینه، باید تعدادی جواب توسط الگوریتم بهینه سازی مورد نظر تولید شود. پس از تولید این جواب ها، تابع هزینه مورد استفاده قرار می گیرد تا ببینیم که کدام جواب ها به جواب بهینه مورد نظر ما، نزدیکتر می باشند (مناسبتر هستند).
مثال اول :
مسئله :
یک جهانگرد می خواهد از شهر A به شهر B برود. بین این دو شهر، مسیرهای مختلفی وجود دارد که در هر مسیر باید از چند شهر عبور کند. طول جاده های مختلف نیز معلوم است و هدف این می باشد که جهانگرد کوتاهترین مسیر ممکن را برای رفتن از شهر A به شهر B طی کند.
شکل جواب ها :
جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است (دقت کنید که منظور از شکل جواب، شکل کلی جواب مسئله به طور کلی است وگرنه هر الگوریتم بهینه سازی، جواب را تبدیل به شکلی می کند که بتواند روند بهینه سازی را برای مسئله اجرا نماید)
تعریف تابع هزینه :
در این مثال، تابع هزینه را می توان تنها به صورت یک جمع ساده در نظر گرفت. تنها کافی است که طول جاده های مختلف را که باید طی شوند با هم جمع بزنیم و عدد حاصل، برابر تابع هزینه مسئله می باشد. هر چقدر که این عدد کوچکتر باشد، جواب بهینه تر است. در واقع عبارت ((تابع هزینه)) نیز از همین مفهوم ناشی شده است، زیرا در زندگی عادی، معمولا سعی می شود که برای رسیدن به یک هدف خاص، کمترین ((هزینه)) ممکن پرداخت شود.
مثال دوم :
مسئله :
همان مسئله قبل، تنها با این تفاوت که جهانگرد علاوه بر این که دوست دارد با کمترین مسافت به شهر B برسد، همچنین می خواهد که از تعداد شهر بیشتری نیز عبور کند. منظور این است که اگر یک مسیر داریم که به طول 700 کیلومتر است و از 3 شهر می گذرد و همچنین مسیر دیگری به طول 800 کیلومتر وجود دارد که از 5 شهر می گذرد، جهانگرد مسیر عبوری از 5 شهر را انتخاب می کند و 100 کیلومتر اضافه برایش مهم نیست.
شکل جواب ها :
جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است.
تعریف تابع هزینه :
این مسئله کمی پیچیده است زیرا باید میزان تمایل جهانگرد برای دیدن تعداد شهر بیشتر را هم منظور کنیم. یک پیشنهاد این است که برای هر جواب، ابتدا مسافت کل مسیر را محاسبه کرده و سپس عدد حاصل را بر تعداد شهرهای مسیر تقسیم کنیم. بنابراین هر چه تعداد شهرها بیشتر باشد، تابع هزینه کوچکتر خواهد بود. این می شود شیوه کلی تعریف تابع هزینه و ما می توانیم با تعریف ضرایبی، میزان تاثیرگذاری تعداد شهرها بر تابع هزینه را کم یا زیاد کنیم.
تعریف تابع هزینه در الگوریتم های بهینه سازی
هنگام طراحی و کدنویسی الگوریتم های بهینه سازی (مثل الگوریتم ژنتیک)، یکی از رایج ترین سوالات، چگونگی تعریف تابع هزینه می باشد. در اینجا قصد دارم که با چندین مثال، نحوه تعریف تابع هزینه برای الگوریتم های بهینه سازی رو شرح بدم.
قبل از هر چیز، باید بدانید که برای تعریف تابع هزینه، یک قانون کلی که باعث شود شما یک تابع هزینه منحصر بفرد تعریف کنید، وجود ندارد، بلکه تنها یک روند کلی وجود دارد. بنابراین ممکن است که افراد مختلف، برای یک مسئله واحد، توابع هزینه متفاوتی تعریف کنند. در واقع فرد باید در مورد نحوه تعریف تابع هزینه، به خوبی فکر کند و یک تابع هزینه مناسب برای مسئله بیابد.
زمانی که ما یک مسئله بهینه سازی داریم، قرار است که یک یا چند پارامتر را بهینه کنیم (بهترین مقادیر یا انتخاب ممکن را برای آنها بیابیم). برای یافتن جواب بهینه، باید تعدادی جواب توسط الگوریتم بهینه سازی مورد نظر تولید شود. پس از تولید این جواب ها، تابع هزینه مورد استفاده قرار می گیرد تا ببینیم که کدام جواب ها به جواب بهینه مورد نظر ما، نزدیکتر می باشند (مناسبتر هستند).
مثال اول :
مسئله :
یک جهانگرد می خواهد از شهر A به شهر B برود. بین این دو شهر، مسیرهای مختلفی وجود دارد که در هر مسیر باید از چند شهر عبور کند. طول جاده های مختلف نیز معلوم است و هدف این می باشد که جهانگرد کوتاهترین مسیر ممکن را برای رفتن از شهر A به شهر B طی کند.
شکل جواب ها :
جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است (دقت کنید که منظور از شکل جواب، شکل کلی جواب مسئله به طور کلی است وگرنه هر الگوریتم بهینه سازی، جواب را تبدیل به شکلی می کند که بتواند روند بهینه سازی را برای مسئله اجرا نماید)
تعریف تابع هزینه :
در این مثال، تابع هزینه را می توان تنها به صورت یک جمع ساده در نظر گرفت. تنها کافی است که طول جاده های مختلف را که باید طی شوند با هم جمع بزنیم و عدد حاصل، برابر تابع هزینه مسئله می باشد. هر چقدر که این عدد کوچکتر باشد، جواب بهینه تر است. در واقع عبارت ((تابع هزینه)) نیز از همین مفهوم ناشی شده است، زیرا در زندگی عادی، معمولا سعی می شود که برای رسیدن به یک هدف خاص، کمترین ((هزینه)) ممکن پرداخت شود.
مثال دوم :
مسئله :
همان مسئله قبل، تنها با این تفاوت که جهانگرد علاوه بر این که دوست دارد با کمترین مسافت به شهر B برسد، همچنین می خواهد که از تعداد شهر بیشتری نیز عبور کند. منظور این است که اگر یک مسیر داریم که به طول 700 کیلومتر است و از 3 شهر می گذرد و همچنین مسیر دیگری به طول 800 کیلومتر وجود دارد که از 5 شهر می گذرد، جهانگرد مسیر عبوری از 5 شهر را انتخاب می کند و 100 کیلومتر اضافه برایش مهم نیست.
شکل جواب ها :
جواب به صورت دنباله ای از اعداد است که هر عدد مربوط به شماره متناظر با یک شهر است.
تعریف تابع هزینه :
این مسئله کمی پیچیده است زیرا باید میزان تمایل جهانگرد برای دیدن تعداد شهر بیشتر را هم منظور کنیم. یک پیشنهاد این است که برای هر جواب، ابتدا مسافت کل مسیر را محاسبه کرده و سپس عدد حاصل را بر تعداد شهرهای مسیر تقسیم کنیم. بنابراین هر چه تعداد شهرها بیشتر باشد، تابع هزینه کوچکتر خواهد بود. این می شود شیوه کلی تعریف تابع هزینه و ما می توانیم با تعریف ضرایبی، میزان تاثیرگذاری تعداد شهرها بر تابع هزینه را کم یا زیاد کنیم.
الگوریتم ژنتیک (GA-Genetic Algorithm)
الگوریتم ژنتیک (GA-Genetic Algorithm)
الگوریتم ژنتیک (Genetic Algorithm) یک تکنیک برنامه نویسی می باشد که از تکامل بیولوژیکی تقلید می کند تا بتواند مسئله مورد نظر را حل کند . برای حل یک مسئله در ابتدا مجموعه ای از جواب های پیشنهادی به عنوان ورودی GA در نظر گرفته می شوند که معمولا به صورت تصادفی تولید می شوند که در واقع اولین نسل می باشند . یک معیار برای سنجش جواب ها وجود دارد که تابع سازگاری نامیده می شود . هر جواب توسط تابع سازگاری سنجیده می شود . چون جواب ها به طور تصادفی تولید شده اند بسیاری از آنها مناسب نمی باشند و بنابراین حذف می شوند اما تعدادی که بهتر از بقیه هستند برای ادامه حل مسئله نگه داشته می شوند . این جواب ها باید بازتولید شوند به این صورت که چندین کپی از آنها گرفته می شود اما چون کپی ها مناسب نیستند در حین کپی کردن آنها را به صورت تصادفی تغییر می دهند . بنابراین نسل بعدی ساخته می شود و جواب های پیشنهادی این نسل نیز توسط تابع سازگاری ارزیابی می شود . آنهایی که پس از تغییر بدتر شده اند و یا اینکه بهتر نشده اند یا باید تغییر داده شوند و یا اینکه حذف شوند . اما تعدادی که پس از تغییر بهتر شده اند انتخاب می شوند و از آنها برای نسل بعدی کپی برداری می شود و تغییراتی به صورت تصادفی در حین کپی کردن به آنها اعمال می شود و دوباره این روند تکرار می شود . انتظار این است که میانگین سازگاری جمعیت در هر دوره جدید افزایش یابد و پس از تکرارهای در حد چند صد و یا چند هزار ، جواب های بسیار مناسبی برای مسئله یافت شود .
روش های نمایش :
قبل از آن که الگوریتم زنتیک بتواند یک مسئله را حل کند باید جواب های پیشنهادی به نحوی کدگذاری شوند که کامپیوتر بتواند بر روی آنها پردازش های لازم را انجام دهد . یک روش متداول کدگذاری جواب ها به صورت رشته های باینری (صفر و یک) می باشد که در آن جواب ها به صورت رشته های 0 و 1 نمایش داده می شوند . روش دیگری که به کار می رود کدگذاری جواب ها به صورت آرایه هایی از اعداد صحیح و یا اعداد دسیمال (دهدهی) می باشد . این روش دارای دقت و پیچیدگی بیشتری می باشد و معمولا به فضای مسئله نزدیک تر است . روش سوم بیان جواب ها به صورت رشته هایی از حروف می باشد . ارزش سه روش ذکر شده این است که به راحتی می توان عملگرهایی را برای تغییر تصادفی جواب های پیشنهادی ، تعریف نمود : تغییر 0 به 1 و یا برعکس ، اضافه یا کم کردن مقدار یک عدد با یک مقدار انتخاب شده به صورت تصادفی یا تغییر یک حرف به حرفی دیگر .
در روشی دیگر که برنامه نویسی ژنتیک (Genetic programming) نام دارد ، برنامه ها به صورت ساختارهای اطلاعات شاخه ای که به آنها درخت گفته می شود ، نمایش داده می شوند .
در شکل زیر، سه مثال از روش نمایش برنامه نویسی ژنتیک، نمایش داده شده است :
در این روش تغییرات تصادفی به صورت تغییر یک عملگر یا تغییر دادن مقدار درون یک گره در درخت و یا جایگزینی یک زیردرخت با یکی دیگر ، اعمال می شوند .
الگوریتم های تکاملی احتیاجی ندارند که جواب های پیشنهادی را به صورت رشته های اطلاعاتی با طول محدود نمایش دهند . برخی آنها را این گونه نمایش می دهند و برخی خیر . به عنوان مثال نحوه کدگذاری درختی که ذکر شد می تواند درخت را تا هر اندازه که برای حل مسئله لازم می باشد گسترش دهد و بزرگ کند .
روش های انتخاب :
روش های گوناگونی برای انتخاب افرادی که باید به نسل بعدی کپی شوند وجود دارد :
انتخاب نخبه گرایانه (Elitist selection) :
اغلب افراد سازگار هر نسل انتخاب می شوند .
انتخاب سازگار- متناسب (Fitness-proportionate selection) :
افراد سازگارتر شانس بیشتری برای انتخاب دارند اما معلوم نیست که حتما انتخاب شوند .
انتخاب چرخ قمار (Roulette-wheel selection) :
شکلی از انتخاب سازگار- متناسب می باشد که در آن شانس انتخاب یک فرد متناسب با میزانی از سازگاری است که آن فرد از دیگر رقبای خود بیشتر یا کمتر دارد ( این انتخاب شبیه بازی چرخ قمار می باشد که چرخ به تکه های مختلف تقسیم شده است و گلوله کوچکی درون آن گذاشته می شود و سپس چرخ چرخانده می شود . تکه ها به گونه ای انتخاب می شوند که افرادی که دارای سازگاری بیشتری هستند تکه های بزرگتری داشته باشند . )
انتخاب مقیاس بندی (Scaling selection) :
همان طور که میانگین سازگاری جمعیت افزایش می یابد ، شرایط انتخاب سخت تر شده و تابع سازگاری معیارهای انتخاب خود را دشوارتر می کند . این روش زمانی مناسب است که تمام افراد نسبتا دارای سازگاری بالایی باشند و تنها تفاوت های کوچکی در میزان سازگاری آنها وجود داشته باشد .
انتخاب مسابقه ای (Tournament selection) :
زیرگروه هایی از افراد جمعیت بزرگتر انتخاب می شوند و افراد هر زیر گروه با یکدیگر رقابت می کنند . تنها یک فرد از هر زیرگروه برای بازتولید انتخاب می شود .
انتخاب رتبه بندی (Rank selection) :
به هر فرد بر اساس میزان سازگاری یک رتبه داده می شود و انتخاب به جای این که بر اساس اختلاف های مطلق در سازگاری باشد ، بر اساس رتبه افراد صورت می گیرد . فایده این روش انتخاب این است که می تواند از اینکه افراد بسیار سازگار در مراحل اولیه بر دیگر افراد با سازگاری کمتر غلبه پیدا کنند ، جلوگیری نماید زیرا در صورتی که این اتفاق بیفتد تنوع ژنتیکی جمعیت کاهش پیدا می کند که می تواند از پیدا کردن یک جواب قابل قبول جلوگیری نماید .
انتخاب نسلی (Generational selection) :
نوزادان افراد انتخاب شده از هر نسل ، کل نسل بعدی را تشکیل می دهند . هیچ فردی از یک نسل به نسل دیگر باقی نمی ماند .
انتخاب حالت دائمی (Steady-state selection) :
نوزادان افراد انتخاب شده از هر نسل به منبع ژنی که از قبل موجود بوده است می روند و جایگزین تعدادی از اعضا می شوند که دارای سازگاری کمتری در نسل قبل بوده اند . برخی از افراد بین نسل ها باقی می مانند .
انتخاب مرتبه ای (Hierarchical selection) :
افراد هر نسل در مراحل گوناگونی انتخاب می شوند . مراحل ارزیابی پایین تر ، سریعتر می باشند و کمتر تفاوت قائل می شوند در حالیکه کسانی که برای مراحل بالاتر باقی می مانند به صورت سخت تری مورد ارزیابی قرار می گیرند . فایده این روش این است که زمان محاسبه کلی را کاهش می دهد زیرا ارزیابی های سریعی را برای اکثر افراد انجام می دهد و سپس تنها برای کسانی که از مراحل آسان تر عبور کنند ارزیابی های سنگین تر و دارای محاسبات بیشتر را انجام می دهد .
روش های تغییر :
زمانی که تعدادی از افراد انتخاب می شوند با این امید که میزان سازگاری آنها بیشتر شود باید آنها را تغییر بدهیم . دو روش اصلی برای تغییر افراد منتخب وجود دارد .
روش جهش (Mutation) :
در این روش یک تغییر کوچک در نقاط تنها در کد افراد داده می شود .
مثالی برای روش تغییر جهش که در آن، یک رقم از کد فرد از 0 به 1 تبدیل شده است را می توانید در شکل زیر ببینید :
روش دورگه کردن (Crossover) :
در این روش دو فرد انتخاب می شوند و بخشی از کدهای آنها معاوضه می شود و یک نوزاد از ترکیب این والدین به وجود می آید . شکل متداول دورگه کردن ، دورگه کردن تک نقطه ای می باشد که یک نقطه تبادل در یک نقطه تصادفی از ژن والدین انتخاب می شود ، بخشی از ژن نوزاد که قبل از نقطه می باشد از یک فرد و بخش دیگر از فرد دیگر گرفته می شود تا ژن نوزاد تشکیل شود .
مثالی برای روش تغییر دورگه کردن . 3 رقم سمت راست کد نوزاد از نفر اول و 5 رقم سمت چپ کد نوزاد از نفر دوم گرفته شده است را می توانید در شکل زیر ببینید :
الگوریتم ژنتیک (GA-Genetic Algorithm)
الگوریتم ژنتیک (Genetic Algorithm) یک تکنیک برنامه نویسی می باشد که از تکامل بیولوژیکی تقلید می کند تا بتواند مسئله مورد نظر را حل کند . برای حل یک مسئله در ابتدا مجموعه ای از جواب های پیشنهادی به عنوان ورودی GA در نظر گرفته می شوند که معمولا به صورت تصادفی تولید می شوند که در واقع اولین نسل می باشند . یک معیار برای سنجش جواب ها وجود دارد که تابع سازگاری نامیده می شود . هر جواب توسط تابع سازگاری سنجیده می شود . چون جواب ها به طور تصادفی تولید شده اند بسیاری از آنها مناسب نمی باشند و بنابراین حذف می شوند اما تعدادی که بهتر از بقیه هستند برای ادامه حل مسئله نگه داشته می شوند . این جواب ها باید بازتولید شوند به این صورت که چندین کپی از آنها گرفته می شود اما چون کپی ها مناسب نیستند در حین کپی کردن آنها را به صورت تصادفی تغییر می دهند . بنابراین نسل بعدی ساخته می شود و جواب های پیشنهادی این نسل نیز توسط تابع سازگاری ارزیابی می شود . آنهایی که پس از تغییر بدتر شده اند و یا اینکه بهتر نشده اند یا باید تغییر داده شوند و یا اینکه حذف شوند . اما تعدادی که پس از تغییر بهتر شده اند انتخاب می شوند و از آنها برای نسل بعدی کپی برداری می شود و تغییراتی به صورت تصادفی در حین کپی کردن به آنها اعمال می شود و دوباره این روند تکرار می شود . انتظار این است که میانگین سازگاری جمعیت در هر دوره جدید افزایش یابد و پس از تکرارهای در حد چند صد و یا چند هزار ، جواب های بسیار مناسبی برای مسئله یافت شود .
روش های نمایش :
قبل از آن که الگوریتم زنتیک بتواند یک مسئله را حل کند باید جواب های پیشنهادی به نحوی کدگذاری شوند که کامپیوتر بتواند بر روی آنها پردازش های لازم را انجام دهد . یک روش متداول کدگذاری جواب ها به صورت رشته های باینری (صفر و یک) می باشد که در آن جواب ها به صورت رشته های 0 و 1 نمایش داده می شوند . روش دیگری که به کار می رود کدگذاری جواب ها به صورت آرایه هایی از اعداد صحیح و یا اعداد دسیمال (دهدهی) می باشد . این روش دارای دقت و پیچیدگی بیشتری می باشد و معمولا به فضای مسئله نزدیک تر است . روش سوم بیان جواب ها به صورت رشته هایی از حروف می باشد . ارزش سه روش ذکر شده این است که به راحتی می توان عملگرهایی را برای تغییر تصادفی جواب های پیشنهادی ، تعریف نمود : تغییر 0 به 1 و یا برعکس ، اضافه یا کم کردن مقدار یک عدد با یک مقدار انتخاب شده به صورت تصادفی یا تغییر یک حرف به حرفی دیگر .
در روشی دیگر که برنامه نویسی ژنتیک (Genetic programming) نام دارد ، برنامه ها به صورت ساختارهای اطلاعات شاخه ای که به آنها درخت گفته می شود ، نمایش داده می شوند .
در شکل زیر، سه مثال از روش نمایش برنامه نویسی ژنتیک، نمایش داده شده است :
در این روش تغییرات تصادفی به صورت تغییر یک عملگر یا تغییر دادن مقدار درون یک گره در درخت و یا جایگزینی یک زیردرخت با یکی دیگر ، اعمال می شوند .
الگوریتم های تکاملی احتیاجی ندارند که جواب های پیشنهادی را به صورت رشته های اطلاعاتی با طول محدود نمایش دهند . برخی آنها را این گونه نمایش می دهند و برخی خیر . به عنوان مثال نحوه کدگذاری درختی که ذکر شد می تواند درخت را تا هر اندازه که برای حل مسئله لازم می باشد گسترش دهد و بزرگ کند .
روش های انتخاب :
روش های گوناگونی برای انتخاب افرادی که باید به نسل بعدی کپی شوند وجود دارد :
انتخاب نخبه گرایانه (Elitist selection) :
اغلب افراد سازگار هر نسل انتخاب می شوند .
انتخاب سازگار- متناسب (Fitness-proportionate selection) :
افراد سازگارتر شانس بیشتری برای انتخاب دارند اما معلوم نیست که حتما انتخاب شوند .
انتخاب چرخ قمار (Roulette-wheel selection) :
شکلی از انتخاب سازگار- متناسب می باشد که در آن شانس انتخاب یک فرد متناسب با میزانی از سازگاری است که آن فرد از دیگر رقبای خود بیشتر یا کمتر دارد ( این انتخاب شبیه بازی چرخ قمار می باشد که چرخ به تکه های مختلف تقسیم شده است و گلوله کوچکی درون آن گذاشته می شود و سپس چرخ چرخانده می شود . تکه ها به گونه ای انتخاب می شوند که افرادی که دارای سازگاری بیشتری هستند تکه های بزرگتری داشته باشند . )
انتخاب مقیاس بندی (Scaling selection) :
همان طور که میانگین سازگاری جمعیت افزایش می یابد ، شرایط انتخاب سخت تر شده و تابع سازگاری معیارهای انتخاب خود را دشوارتر می کند . این روش زمانی مناسب است که تمام افراد نسبتا دارای سازگاری بالایی باشند و تنها تفاوت های کوچکی در میزان سازگاری آنها وجود داشته باشد .
انتخاب مسابقه ای (Tournament selection) :
زیرگروه هایی از افراد جمعیت بزرگتر انتخاب می شوند و افراد هر زیر گروه با یکدیگر رقابت می کنند . تنها یک فرد از هر زیرگروه برای بازتولید انتخاب می شود .
انتخاب رتبه بندی (Rank selection) :
به هر فرد بر اساس میزان سازگاری یک رتبه داده می شود و انتخاب به جای این که بر اساس اختلاف های مطلق در سازگاری باشد ، بر اساس رتبه افراد صورت می گیرد . فایده این روش انتخاب این است که می تواند از اینکه افراد بسیار سازگار در مراحل اولیه بر دیگر افراد با سازگاری کمتر غلبه پیدا کنند ، جلوگیری نماید زیرا در صورتی که این اتفاق بیفتد تنوع ژنتیکی جمعیت کاهش پیدا می کند که می تواند از پیدا کردن یک جواب قابل قبول جلوگیری نماید .
انتخاب نسلی (Generational selection) :
نوزادان افراد انتخاب شده از هر نسل ، کل نسل بعدی را تشکیل می دهند . هیچ فردی از یک نسل به نسل دیگر باقی نمی ماند .
انتخاب حالت دائمی (Steady-state selection) :
نوزادان افراد انتخاب شده از هر نسل به منبع ژنی که از قبل موجود بوده است می روند و جایگزین تعدادی از اعضا می شوند که دارای سازگاری کمتری در نسل قبل بوده اند . برخی از افراد بین نسل ها باقی می مانند .
انتخاب مرتبه ای (Hierarchical selection) :
افراد هر نسل در مراحل گوناگونی انتخاب می شوند . مراحل ارزیابی پایین تر ، سریعتر می باشند و کمتر تفاوت قائل می شوند در حالیکه کسانی که برای مراحل بالاتر باقی می مانند به صورت سخت تری مورد ارزیابی قرار می گیرند . فایده این روش این است که زمان محاسبه کلی را کاهش می دهد زیرا ارزیابی های سریعی را برای اکثر افراد انجام می دهد و سپس تنها برای کسانی که از مراحل آسان تر عبور کنند ارزیابی های سنگین تر و دارای محاسبات بیشتر را انجام می دهد .
روش های تغییر :
زمانی که تعدادی از افراد انتخاب می شوند با این امید که میزان سازگاری آنها بیشتر شود باید آنها را تغییر بدهیم . دو روش اصلی برای تغییر افراد منتخب وجود دارد .
روش جهش (Mutation) :
در این روش یک تغییر کوچک در نقاط تنها در کد افراد داده می شود .
مثالی برای روش تغییر جهش که در آن، یک رقم از کد فرد از 0 به 1 تبدیل شده است را می توانید در شکل زیر ببینید :
روش دورگه کردن (Crossover) :
در این روش دو فرد انتخاب می شوند و بخشی از کدهای آنها معاوضه می شود و یک نوزاد از ترکیب این والدین به وجود می آید . شکل متداول دورگه کردن ، دورگه کردن تک نقطه ای می باشد که یک نقطه تبادل در یک نقطه تصادفی از ژن والدین انتخاب می شود ، بخشی از ژن نوزاد که قبل از نقطه می باشد از یک فرد و بخش دیگر از فرد دیگر گرفته می شود تا ژن نوزاد تشکیل شود .
مثالی برای روش تغییر دورگه کردن . 3 رقم سمت راست کد نوزاد از نفر اول و 5 رقم سمت چپ کد نوزاد از نفر دوم گرفته شده است را می توانید در شکل زیر ببینید :