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

روش‌های مختلفی برای حل مسائل بهینه سازی وجود دارد. این روش هارا می‌توان به دو دسته کلی تقسیم کرد:

روش‌های کلاسیک ریاضی:

در این روش‌ها مشتق تابع را برابر صفر قرار داده و نقاط بیشینه و کمینه را محاسبه می‌کنیم. این روش‌ها برای توابعی که دارای متغیر‌های زیاد یا نقاط بیشینه و کمینه زیاد باشد مناسب نمی‌باشد، زیرا اغلب این روش‌ها نقطه بهینه محلی (Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند مانند شکل زیر:

روش‌های مبتنی بر جستجو:

در این روش‌ها نقاطی از محدوده جستجو بطور تصادفی انتخاب و تست می‌شوند و سپس با روش‌های مختلفی به سمت نقاط بهینه حرکت می‌کنیم. یکی از این روش‌ها الگوریتم ژنتیک است که با الهام گیری از تئوری تکامل و اصول ژنتیک به جستجوی راه حل مناسب برای مسائل می‌پردازد. بدین منظور ابتدا چندین پاسخ تصادفی برای مسئله مورد نظر تولید شده و در مراحل بعدی این پاسخ‌های ابتدائی با استفاده از اصول ژنتیک به تکامل رسیده و به پاسخ مناسب تبدیل می‌شود.
به طور کلی، الگوریتم ژنتیک از اجزاء زیر تشکیل می‏ شود:

کروموزوم:

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



جمعیت:

مجموعه‏‌ای از کروموزوم ‏ها یک جمعیت (P) را تشکیل می ‏دهند. با تاثیر عملگر‌های ژنتیکی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشکیل می‏ شود.

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

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

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

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

عملگر انتخاب (Selection):

این عملگر از بین کروموزوم‏‌های موجود در یک جمعیت، تعدادی کروموزوم را برای تولید مثل انتخاب می‏ کند. کروموزوم ‏های برازنده‏‌تر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند. حتما باید بهترین کروموزوم برای نسل بعد انتخاب شود.



یکی از روش‌های انتخاب، انتخاب به روش چرخ رولت می‌باشد. در این روش، به هر فرد قطعه‏‌ای از یک چرخ رولت مدور اختصاص داده می‏ شود. اندازه این قطعه متناسب با برازندگی آن فرد است. چرخ P. بار چرخانده می‏ شود که P. تعداد افراد در جمعیت است. در هر چرخش، فرد زیر نشانگر چرخ انتخاب می‏ شود و در مخزن والدین نسل بعد قرار می‏ گیرد.




عملگر آمیزش (Crossover):
در جریان عمل تلفیق به صورت اتفاقی بخش‌هایی از کروموزوم‌ها با یکدیگر تعویض می‌شوند. این موضوع باعث می‌شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. هدف تولید فرزند جدید می‌باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند. این عملگر را با Pc نمایش می‌دهند و مثلا اگر Pc=۰.۸ و تعداد جمعیت کروموزوم‌ها ۱۰۰ باشد تعداد آمیزش‌ها برابر است با ۸۰ بار.
روش کار بدین صورت است که دو کروموزوم انتخاب می‌شوند و سپس با یکی از روش‌های زیر عمل تلفیق انجام می‌شود:

تلفیق تک نقطه‌ای (Single Point Crossover):

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



روش ادغام دو نقطه‌ای (Two-point Crossover):

در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می‌کنیم.



تلفیق جامع (Uniform Crossover):

اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع می‌گوئیم.



عملگر جهش (Mutation):
پس از اتمام عمل آمیزش، عملگر جهش بر روی کروموزوم‏ها اثر داده می‏شود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر می‏ دهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل می‏ کند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار می‏ دهد. این عملگر را با Pm نشان می‌دهند و مثلا اگر Pm=۰.۰۱ و طول هر کروموزوم ۵۰۰ و تعداد جمعیت ۱۰۰ باشد تعداد جهش‌ها برابر است با ۵۰۰ بار.



پس از اتمام عمل جهش، کروموزوم‏‌های تولید شده به عنوان نسل جدید شناخته شده و برای دور بعد اجرای الگوریتم ارسال می‏ شوند. اگر از کد دسیمال استفاده می‌شود باید تعداد آمیزش‌ها بیشتر باشد و اگر از کد باینری استفاده می‌شود باید تعداد جهش‌ها بیشتر شود. باید توجه داشت که پس از هر بار آمیزش و جهش نباید کروموزوم از ناحیه جستجو خارج شود.
روند کلی الگوریتم ژنتیک را در شکل زیر می‌توانید ببینید:



چون که الگوریتم‌های ژنتیک بر پایه تولید و تست می‌باشند، جواب مساله مشخص نیست و نمی‌دانیم که کدامیک از جواب‌های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیار‌های دیگری را برای شرط خاتمه در نظر می‌گیریم:

تعداد مشخصی نسل: می‌توانیم شرط خاتمه را مثلاً ۱۰۰ دور چرخش حلقه اصلی برنامه قرار دهیم.
عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالی
بهترین شایستگی جمعیت تا یک زمان خاصی تغییری نکند