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

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

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

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

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

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

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

جمعيت:

مجموعه‏ اي از كروموزوم ‏ها يك جمعيت (P) را تشكيل مي ‏دهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت،جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‏ شود.
تابع برازندگي:

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

عملگرهاي الگوریتم ژنتيك:

در الگوريتم‏ ژنتيك،در طي مرحله توليد مثل ازعملگرهاي ژنتيكي استفاده مي‏ شود. با تاثير اين عملگرها بر روي يك جمعيت،نسل بعدي آن جمعيت توليد مي‏ شود. عملگرهاي انتخاب،آميزش و جهش معمولاً بيشترين كاربرد را در الگوريتم‏ ژنتيك دارند.
عملگر انتخاب (Selection):

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

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

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

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

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

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

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

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

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

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

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

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

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