در نسخه اولیه الگوریتم ژنتیک که توسط جان هلند پیشنهاد شد, از انتخاب متناسب با برازندگی استفاده شده است که در آن نرخ انتظار هر فرد از تقسیم برازندگی آن فرد بر متوسط برازندگی ‏های جمعیت بدست می‏ آید. برای پیاده ‏سازی انتخاب متناسب با برازندگی, روش‏های نمونه‏ برداری متعددی  از قبیل چرخ رولت و روش SUS پیشنهاد شده ‏اند. 

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

به طور کلی, الگوریتم‏ ژنتیک از اجزاء زیر تشکیل می‏ شوند:

 کروموزوم

در الگوریتم‏ ژنتیک, هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راه‏حل ممکن برای مسئله مورد نظر است. خود کروموزوم‏ها (راه حل‏ها) از تعداد ثابتی ژن (متغیر) تشکیل می‏شوند. برای نمایش کروموزوم‏ها, معمولاً از کدگذاری‏های دودویی (رشته‏های بیتی) استفاده می‏شود.

جمعیت

مجموعه‏ای از کروموزوم‏ها یک جمعیت را تشکیل می‏دهند. با تاثیر عملگرهای ژنتیکی  بر روی هر جمعیت, جمعیت جدیدی با همان تعداد کروموزوم تشکیل می‏شود.

تابع برازندگی

به منظور حل هر مسئله با استفاده از الگوریتم‏ ژنتیک, ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم, این تابع عددی غیر منفی را برمی‏گرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.

عملگر های ژنتیکی

در الگوریتم‏ ژنتیک, در طی مرحله تولید مثل ازعملگرهای ژنتیکی استفاده می‏شود. با تاثیر این عملگرها بر روی یک جمعیت, نسل بعدی آن جمعیت تولید می‏شود.

عملگرهای انتخاب , آمیزش  و جهش معمولاً بیشترین کاربرد را در الگوریتم‏ ژنتیک دارند.

کدینگ

الگوریتم ژنتیک به جای این که بر روی پارامترها یا متغیرهای مساله کار کند، با شکل کد شده آنها  سروکار دارد. یکی از روش‌های کد کردن،کدکردن دودویی می­باشد که در آن هدف تبدیل جواب مساله به رشته‌ای از اعدادباینری (در مبنای ۲) است. تعداد بیت‌هایی که برای کدگذاری متغیرها استفاده می‌شود، به دقت مورد نظر برای جواب‌ها، محدوده تغییر پارامترها و رابطه بین متغیرها وابسته است. رشته یا دنباله‌ای از بیت‌ها که به عنوان شکل کدشده یک جواب از مساله مورد نظر می­باشد،‌کروموزوم نامیده می‌شود. در حقیقت بیت‌های یک کروموزوم،‌ نقش ژن­ها در طبیعت را بازی می‌کنند. یکی از ویژگی‌های اصلی الگوریتم‌های ژنتیک آن است که متناوباً بر روی فضای کدینگ و فضای جواب کار می‌کنند. اعمال ژنتیک بر روی فضای کدینگ یا کروموزوم‌ها اعمال شده، در حالی که انتخاب و ارزیابی بر روی فضای جواب عمل می‌نماید. درطبیعت نیز به همین شکل است یعنی افراد (کروموزوم ها) در یک فضای حقیقی غیر کدشده در حالت فنوتیپ حضور دارند. در صورت کدشدن با هر مکانیزمی حالت ژنوتیپ خود را بروز می‌دهند. ذکر این نکته ضروری است که هر زمان که از کدینگ صحبت به میان می‌آید به­طور پیش فرض منظور کد کردن از نوع باینری می‌باشد(رشته‌ های دودویی). همچنین ساختمان داده مورد استفاده به­طور پیش فرض، رشته می‌باشد.

 ایجاد جمعیت اولیه

پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به کروموزوم، باید یک جمعیت اولیه از کروموزوم‌ها تولید نمود. در اکثر موارد، جمعیت اولیه به صورت تصادفی تولید می‌شود. اما گاهی اوقات برای بالا بردن سرعت و کیفیت الگوریتم از روش‌های ابتکاری نیز برای تولید جمعیت اولیه استفاده می‌گردد. در هر صورت عمومی‌ترین و راحت‌ترین روش، استفاه از یک رویکرد تصادفی می باشد. اندازه جمعیت اولیه معمولاً به سایز رشته کدشده وابسته است. به عنوان مثال اگر کروموزوم­ها دریک مساله ۳۲ بیتی هستند قطعاً باید جمعیت انتخابی اولیه بیشتر از حالتی باشد که کروموزوم ها به عنوان مثال ۱۶ بیتی هستند.

معمولا احتمال برش بین ۸۰ تا ۹۵ درصد، احتمال جهش بین نیم تا ۱ درصد و اندازه جمعیت بین ۲۰ تا ۳۰ در نظر گرفته می‌شود.آن­گاه به کروموزوم ‌های انتخاب شده با توجه به یک تابع برازش ، مقداری حقیقی که نشان دهنده ارزش آن­ها است تخصیص داده می‌شود و مراحل  الگوریتم­های ژنتیک  ادامه می‌یابد.

 انتخاب طبیعی

عمل حذف در شرایط  طبیعی باعث نابودی افرادی که سازگاری کمتری با محیط دارند می‌شود؛ به عبارت ساده‌تر نتیجه مبارزه بین جانداران باقی ماندن افراد سازگارتر می‌باشد. داروین معتقد بود که رقابت در میان افراد گونه‌های مختلف صورت گرفته و تنها آن عده که دارای صفات ممتازتری هستند قادر به ادامه زندگی خواهند بود و افرادی که نسبت به شرایط محیطی سازش ندارند از بین می‌روند، از این رو انتخاب طبیعی صورت گرفته و صفات نامطلوب افراد نامناسب به واسطه عدم امکان تولید مثل از بین میرود. این عمل در نسل‌های متمادی صورت پذیرفته که نتیجه آن پیدایش نسل‌هایی است که قادرند خود را بهتر با محیط زندگی هماهنگ سازند.  از لحاظ ژنتیکی، یک جمعیت فقط به گروهی از افراد اطلاق نمی‌شود، بلکه باید بین افراد این گروه زاد و ولد صورت گیرد. ژنتیک یک جمعیت نیز تنها به ساخت ژنتیکی افراد مربوط نیست بلکه انتقال ژن‌ها از نسلی به نسل دیگر را نیز شامل می‌شود. هرگاه جفت‌گیری میان افراد جمعیت واحدی به طور مداوم صورت پذیرد ژنها به سادگی میان افراد جمعیت مذکور توزیع خواهند شد. در نتیجه پس از مدتی کلیه اعضای جمعیت از تمام عوامل موروثی برخوردار می‌شوند. در اثر تولید مثل متوالی در نسل‌های متعدد هر یک از افراد سهمی در ساختار ژن‌ها خواهند داشت. در هر جمعیت بعضی مواقع بر اثر انواع برش و جهش ترکیبی از ژن‌های جدید بوجود می‌آید که در نتیجه پاره‌ای از افراد جمعیت، صفات تازه‌ای کسب می‌کنند، هرگاه این افراد به زندگی ادامه داده و تولید مثل نمایند ژن جدید به سایر افراد جمعیت نیز سرایت کرده و سرانجام پس از جفت‌گیری‌های متعدد این ژن میان عده‌ای و یا کلیه اعضای جمعیت توزیع خواهد شد.

 آشنایی با روش‏های انتخاب در الگوریتم‏ ژنتیک

ایده اصلی در روش‏های انتخاب این است که افراد بهتر بر افراد بدتر ترجیح داده شوند, که بهتر و بدتر بودن افراد توسط تابع برازندگی f تعریف می‏شود. روش‏های انتخاب متعددی برای استفاده در الگوریتم‏ ژنتیک پیشنهاد شده‏اند. یکی از ویژگی‏های خوب روش‏های انتخاب این است که این روش‏ها مستقل از نمایش افراد جمعیت هستند و در آنها تنها مقادیر برازندگی افراد در نظر گرفته می‏شود. در زیر برخی از روش‏های انتخاب متداول که در الگوریتم‏ ژنتیک مورد استفاده قرار گرفته‏اند, معرفی شده است.

نمونه‏ برداری به روش چرخ رولت

در این روش, به هر فرد قطع ه‏ای از یک چرخ رولت مدور اختصاص داده می‏شود. اندازه این قطعه متناسب با برازندگی آن فرد است. چرخ N بار چرخانده می‏شود که N تعداد افراد در جمعیت است. در هر چرخش, فرد زیر نشانگر چرخ انتخاب می‏شود و در مخزن والدین نسل بعد قرار می‏گیرد. این روش می‏تواند به صورت زیر پیاده‏سازی شود:

– نرخ انتظار کل افراد جمعیت را جمع کنید و حاصل آن را T بنامید.

– مراحل زیر را N بار تکرار کنید:

یک عدد تصادفی r بین ۰ و T  انتخاب کنید.

در میان افراد جمعیت بگردید و نرخ‏های انتظار آنها را با هم جمع کنید تا این که مجموع بزرگتر یا مساوی r شود. فردی که نرخ انتظارش باعث بیشتر شدن جمع از این حد می‏شود, به عنوان فرد برگزیده انتخاب می‏شود.

روش SUS

در نمونه‏ برداری به روش چرخ رولت, هنگامی که جمعیت‏ نسبتاً کوچک باشد, تعداد واقعی فرزندانی که به هر فرد نسبت داده می‏شود, اغلب از نرخ انتظار آن فرد دورتر است. به این دلیل, روش نمونه‏برداری متفاوتی توسط James Baker تحت عنوان روش SUS پیشنهاد شده است. در این روش, به جای N بار چرخاندن چرخ رولت تا N والد انتخاب شوند, چرخ یک بار چرخانده می‏شود, امّا از N اشاره‏گر فاصله داده شده به طور یکسان برای انتخاب N والد استفاده می‏شود.

 

انتخاب نخبگان

روش انتخاب نخبگان که اولین بار توسط De Jong مطرح شده است, به عنوان الحاقی به خیلی از روش‏های انتخاب محسوب می‏شود که GA را وادار می‏کند تا بهترین افراد را در هر نسل نگه دارد. چنین افرادی در صورتی که برای تولید مثل انتخاب نشوند یا توسط آمیزش و جهش خراب شوند, ممکن است از بین بروند. بسیاری از محققین دریافته‏اند که انتخاب نخبگان به میزان قابل ملاحظه‏ای کارایی GA را افزایش می‏دهد.

انتخاب تورنمنت

روش‏های انتخابی که تاکنون توصیف شدند, در هر نسل نیاز به دوبار عبور از میان جمعیت دارند:

یک بار برای محاسبه میانگین برازندگی و  یک بار هم برای محاسبه نرخ انتظار هر فرد.در این روش, دو فرد از جمعیت  به صورت تصادفی انتخاب می‏شوند. سپس, یک عدد تصادفی r بین ۰ و ۱ انتخاب می‏شود. اگر    r < k (که k یک پارامتر است, برای مثال ۷۵/۰) باشد, فرد برازنده‏تر و در غیر اینصورت فردی که برازندگی کمتری دارد, به عنوان والد انتخاب می‏شود. این دو سپس به جمعیت اولیه بازگردانده می‏شوند و دوباره در فرآیند انتخاب شرکت داده می‏شوند.

شرط پایان الگوریتم

در الگوریتم‌های تکاملی غالباً اجرای برنامه برای تعداد نسل‌های از پیش تعیین شده‌ای صورت می‌گیرد. اما شرط دیگری نیز برای پایان الگوریتم‌های ژنتیک توسط Grefenstette ارائه شده است که آن میزان پراکندگی بیت‌ها درون جمعیت می‌باشد (Bit Diversity) . این محک نشان دهنده میزان همگرا شدن کد اعضای جمعیت می‌باشد.

شرح کلی الگوریتم

ابتدا یـک جمعیت اولیه از افراد به‌طور اتفاقی و بدون در نظر گرفتن معیار خاصی انتخـاب می‌شود.برای تمامی کروموزوم ‌های (افراد) نسل صفر، مقدار برازش با توجه به تابع برازش که ممکن است بسیار سـاده یا پیچیده باشد تعیین می‌شود. سپس با مـکانیزم ­های مختلـف تعریف شده برای عملگر انتخاب، زیرمجموعه‌ای از جمعیت اولیه انتخاب خواهد شد. سپس روی این افراد انتخاب ‌شده عملیات  بُرش وجهش درصورت لزوم با توجه به صورت مساله اعمال خواهد شد. حال باید این افراد که مکانیزم  الگوریتمهای ژنتیک  در موردشان اعمال شده است، با افراد جمعیت اولیه (نسل صفر) از لحاظ مقدار برازش مقایسه شوند. (قطعاً توقع داریم که افراد نسل اول با توجه به یکبار اعمال  الگوریتمهای ژنتیک  روی آنان، از شایستگی بیشتری برخوردار باشند. اما الزاماً چنین نخواهد بـود). به‌هرحال افرادی باقی خواهندماند که بیشترین مقـدار برازش را داشته باشند. چـنین افرادی در مقام یـک مجموعه به عنوان جمعیت اولیه برای مرحله بعدی الگوریتم عمل خواهد کرد. هر مرحله تکرار الگوریتم یک نسل جدید را ایجاد می‌کند، که با توجه به اصلاحاتی که در آن صورت پذیرفته است، رو به سوی تکامل خواهد داشت.

جهت سفارش کدنویسی این الگوریتم در محیط متلب اینجا کلیک کنید