تجدید نسل: ایجاد نسلهای جدید و تکامل موجودات

تجدید نسل: تکرار مراحل الگوریتم بعد از مرحله تکثیرتا حصول پاسخ بهینه یا رسیدن به حد توقف.

رویه انتخاب، برای رقابت افراد در داخل جمعیت به کار میرود که بر اساس یک تابع شایستگی^[۱۸] عمل مینماید. برای هر کروموزوم، یک مقدار مرتبط با شایستگی جوابی که نمایش میدهد، وجود دارد. الگوریتم ژنتیک به دنبال حداکثر کردن مقدار تابع شایستگی است. بعد از اینکه تولید مثل و تابع برازندگی به خوبی تعریف شدند، یک الگوریتم ژنتیک بر اساس یک ساختار مشابه و پایه طراحی میگردد. این ساختار ساده با تولید یک جمعیت اولیه از کروموزومها شروع میگردد. جمعیت اولیه باید به حدی بزرگ باشد که توانایی تولید تمامی راهحلهای فضای جواب را داشته باشد. معمولاً جمعیت اولیه به صورت تصادفی تولید میگردد. سپس الگوریتم ژنتیک یک رویه تکراری را به منظور تکامل جمعیت انجام میدهد. هر تکرار شامل مراحل زیر است:

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

انتخاب: اولین قدم شامل انتخاب افرادی از جمعیت برای تولید مثل است. این انتخاب به صورت تصادفی، با بهره گرفتن از یک احتمال متناسب با تابع برازندگی افراد انجام میگردد. در این مرحله، باید در ارتباط با نحوه انتخاب والدین برای عمل تقاطع (باز ترکیب)^[۱۹]، نحوه تولید فرزندان و تعداد فرزندان تصمیمگیری گردد. هدف این است که والدین شایستهتر انتخابشده که منجر به تولید فرزندانی با برازندگی بالا گردد. کروموزومهایی که از جمعیت اولیه برای تولید مثل انتخاب میشوند، والدین نام دارند. همگرایی الگوریتم ژنتیک وابستگی بالایی به دامنه و شدت فشار رویه انتخاب برای گزینش افراد شایستهتر دارد.
روش های مختلفی برای انتخاب وجود دارد که از آن جمله میتوان به موارد زیر اشاره کرد:
انتخاب مرتبهای
در این روش، کروموزومها بر اساس مقدار برازندگی آن ها رتبهبندی شده و به ترتیب بدترین به بهترین رتبه مرتب میگردند. احتمال انتخاب هر کروموزوم بر اساس درصد نسبی رتبه خود میباشد.
انتخاب تصادفی
در این روش والدین بر اساس یک روش کاملاً تصادفی از جمعیت انتخاب میشوند. این روش با توجه به عدم اهمیت به شانس بیشتر بهترینها برای تولید مثل، از کیفیت پایینی نیز برخوردار است.
انتخاب رقابتی
در این روش یک زیر مجموعه کوچکی از کروموزومها به صورت تصادفی انتخاب شده و به رقابت میپردازند. سرانجام در این رقابت، بر اساس میزان برازندگی، یکی از آنها به پیروزی رسیده و انتخاب میشود. ایراد این روش این است که در آن هیچگاه کروموزوم دارای کمترین شانس برنده نخواهد شد.
انتخاب بولتزمن
این روش بیشتر در الگوریتم انجماد تدریجی مورد استفاده قرار میگیرد. در این حالت دما از یک مقدار بالا در ابتدای الگوریتم شروع میکند و معنای آن این است که فشار انتخاب پایین است. دما به مرور کاهش مییابد و به دنبال آن، فشار انتخاب به مرور افزایش مییابد. بنابراین در این حالت، در ابتدای الگوریتم گوناگونی افزایش یافته و در انتها جستجوی محلی قوت مییابد.
انتخاب چرخ رولت
روشی که غالباً در انتخاب والدین مورد استفاده میگیرد، همانطور که در شکل ۲-۱ می بینید، سطح چرخ رولت به بخش هایی تقسیم میشود که تعداد آنها برابر تعداد اعضای جمعیت و سطح هر بخش متناسب با مقدار برازندگی هر کروموزوم میباشد. سپس چرخ رولت به گردش در میآید تا در نقطهای به تصادف متوقف شود. این نقطه، کروموزوم انتخاب شده را مشخص میسازد. کروموزومهایی انتخاب میشوند که سطح بیش تر(شایستگی بالاتری) را دارا میباشند. این شیوه انتخاب سبب میشود که با گذشت زمان، تعداد کروموزومهای مطلوب در جمعیت افزایش یابد به طوریکه میانگین مقدار برازندگی جمعیت در مقایسه با جمعیت مرحله قبل بیشتر شود.
شکل ۲-۱- نمایش انتخاب چرخ رولت در الگوریتم ژنتیک (فتاحی، ۱۳۹۱)
تولید مثل: در قدم دوم، عملگرهای ترکیب مجدد و جهش روی افراد انتخاب شده به کار گرفته شده و کروموزومهای جدید تولید میگردد. در این مرحله، فرزندان جدید تولید میشوند. در این مرحله عملگر ترکیب مجدد (تقاطع)، فرآیندی است که در ۳ مرحله صورت میگیرد:
الف) اپراتور تولید مثل یک زوج والد را از حوضچه تولید مثل انتخاب مینماید.
ب) یک نقطه تقاطع به طور تصادفی در طول رشته انتخاب میشود.
ج) مقادیر رشته ها با توجه به نقطه تقاطع تعویض میگردند.
عملگر تقاطعی با یک احتمال از قبل تعیین شده، بر روی کروموزومهای والد عمل میکند. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقأ مشابه والدین خواهند بود.
روش های مختلفی برای عملگر تقاطع وجود دارد و بخشی از این روشها به شرح زیر هستند:
تقاطع دو نقطهای
در این عملگر، دو نقطه شکست در طول رشته جواب در نظر گرفته میشود. در این حالت، ابتدا دو مکان تصادفی در طول رشته انتخاب شده و سپس به صورت یک در میان قسمتهای والدها به فرزندان منتقل میشود.
تقاطع چندنقطهای
این عملگر شبیه عملگر دونقطهای است، با این تفاوت که به جای دو نقطه، چند نقطه برای تقاطع انتخاب میشود. تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد. باید توجه داشت افزایش تعداد نقاط شکست، عملکرد الگوریتم ژنتیک را کاهش میدهد ولی باعث میشود فضای مسئله به صورت کاملتری جستجو گردد.
تقاطع یکنواخت
بر اساس این عملگر، یک ژن از هر دو والد به طور مستقل از سایر ژنها، شانس برابر برای حضور در کروموزوم یک فرزند را دارد. در این حالت، بر اساس یک توزیع تصادفی باینری مشخص میشود که یک ژن از کدام والدین انتخاب شده است. مثلاً اگر توزیع باینری ۱ را نشان داد، آن ژن از والد اول و اگر ۰ بود از والد دوم انتخاب میگردد.
تقاطع از سه والد
در این روش، ۳ والد به صورت تصادفی انتخاب میشود. هر ژن از والد اول با همان ژن از والد دوم مقایسه میشود. در صورتی که مشابه باشند، همان ژن به فرزند منتقل میشود و در غیر این صورت با والد سوم مقایسه میشود. این روش بر این پایه استوار است که شباهتهای والدین کشف شده و بر اساس آنها فرزندانی تولید میگردد.
تقاطع مرتب
از این عملگر زمانی استفاده میشود که مسئله مبتنی بر ترتیب باشد. در این روش دو نقطه تقاطع تصادفی انتخاب میشود و آن را به ۳ قسمت چپ، وسط و راست تقسیم میکند. عملگر به این ترتیب عمل مینماید که فرزند اول قسمت چپ و راست را از والد اول و قسمت وسط آن بر اساس ژنهای قسمت وسط والد اول به نحوی که ترتیب آن بر اساس والد دوم باشد، تعیین میگردد.
تقاطع تک نقطهای
عملگر تقاطعی تک نقطهای معمولترین نوع عملگرهای تقاطع محسوب میشود که در مدل ارائه شده در این تحقیق هم از آن بهره گرفته شده است. در این عملگر دو کروموزوم به صورت تصادفی از یک نقطه شکسته میشوند و بخشهای شکسته شده دو کروموزوم با هم جابهجا میگردند. بدین ترتیب، دو کروموزوم جدید بدست میآید. به کروموزومهای اولیه، کروموزومهای والد و به کروموزومهای حاصل شده از عمل جابهجایی، فرزند میگویند (فتاحی، ۱۳۹۰). یک مثال از عملگر تقاطع تکنقطهای در شکل ۲-۲ نشان داده شده است.

شکل۲-۲- نمایش عملگر تقاطع تکنقطهای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)
بعد از تقاطع، کروموزومها تحت اپراتور جهش قرار میگیرند. عملگر جهش از افتادن الگوریتم در بهینه محلی جلوگیری مینمایند. جهش موجب میشود که گوناگونی جمعیت حفظ شود و ساختار ژنتیکی جدیدی در جمعیت با تغییرات تصادفی بعضی از ژنها (هر بیت از یک رشته بیتی به نام کروموزوم) به وجود آید. انتخاب ژنها بر اساس احتمال جهش صورت میگیرد.
شکلهای مختلفی برای جهش به شرح زیر موجود است:
معکوس کردن
تعویض
آنچه در انجام این تحقیق مورد استفاده قرار گرفته استفاده از روش تعویض برای عملگر جهش است. در این نوع جهش، دو موقعیت تصادفی از یک رشته انتخاب و ارزشهای مرتبط آنها با یکدیگر تعویض میگردد. شکل ۲-۳ نوعی از این جهش را نشان میدهد.
شکل۲-۳- نمایش عملگر جهش تک نقطهای در الگوریتم ژنتیک (فتاحی، ۱۳۹۰)
نکتهای که در تفاوت عملگرهای تقاطع و جهش قابل تأمل است این است که عملگر جهش عملیاتی است که تنها روی یک کروموزوم اجرا میشود در حالیکه عملگر تقاطع عملیاتی است که روی دو کروموزوم اجرا میشود.
ارزیابی: در این مرحله، میزان برازندگی فرزندان جدید تولید شده، ارزیابی میگردد.
جابهجایی: در این مرحله، افرادی از جمعیت قبلی کشته شده (حذف میگردند) و با افراد جدیدی که به تازگی تولید شدهاند، جابهجا میگردند. به عبارت دیگر، در این مرحله، جمعیت، یک نسل را پشت سر گذاشته و افرادی از آن حذف و افرادی به آن اضافه میگردند. روش های مختلفی برای انتخاب جمعیت جدید وجود دارد که به طور مثال میتوان به دو روش زیر اشاره کرد:
تمام اعضای جمعیت جدید از میان کروموزومهای فرزندان انتخاب شوند.
تعدادی از افراد جمعیت مرحله بعد، همان افراد جمعیت مرحله قبل بوده و بقیه از میان فرزندان جدید انتخاب گردند. البته در هر مورد، شایستهترین کروموزومها انتخاب میشود.
بر اساس تحقیقات نشان داده شده است که حذف همه کروموزومهای جمعیت مرحله قبل و انتخاب جمعیت جدید از میان فرزندان، ممکن است بسیاری از جوابهای مناسب را که در میان جمعیت مرحله قبل وجود دارد، حذف نماید.