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

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

• الگوریتم­های ژنتیک ترتیبی

این الگوریتم­ها بر روی جمعیتی از رشته­ها و یا به طور کلی بر روی ساختارهای دلخواهی از راه­حل­های آزمایشی عمل می­ کنند. در این الگوریتم از هر رشته تحت عنوان یک فرد یاد می­ شود و هر فرد دارای یک یا چند کروموزوم و یک مقدار شایستگی است. معمولاً هر فرد تنها از  یک کروموزوم تشکیل می­ شود که این کروموزوم شامل مجموعه ­ای از پارامترها تحت عنوان ژن می­باشد.

• الگوریتم­های ژنتیک موازی[۱]

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

• الگوریتم­های ژنتیک هیبرید

بر خلاف سایر روش­های بهینه­سازی الگوریتم ژنتیک این نوع الگوریتم همگرایی را تضمین می­ کند، البته هیچ تضمینی وجود ندارد که الگوریتم به راه­حل بهینه همگرا شده باشد و ممکن است الگوریتم به نقاط بهینه­ محلی متوقف شده باشد.

• الگوریتم­های ژنتیک خود­سازمان[۲]

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

 

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

• الگوریتم­های ژنتیک خود­سازمان یکپارچه­شده[۳]

عملگرهای ژنتیکی در این نوع از الگریتم­ها می­توانند یگانه، دوگانه یا چندگانه باشند. مشکل اصلی یافتن مقدار بهینه نسبت به استفاده از این عملگرها در حین اجرای الگریتم می­باشد.

• الگوریتم ژنتیک آشفته

هدف از توسعه الگوریتم­های ژنتیک آشفته ایجاد تابع شایستگی به صورت جمع چندین زیر تابع مستقل می­باشد. هر یک از زیر تابع­ها بر روی چند مکان هندسی تعریف شده ­اند که این مکان­ها سطح فریب را در فریبنده­ترین زیر تابع تخمین می­زند.

• الگوریتم­های ژنتیکی زایشی[۴]

این الگوریتم­ها فرزندان جدید را با توجه به جمعیت حاضر و با بهره گرفتن از عملگرهای ژنتیک تولید می­ کند و به این ترتیب جمعیت جدید ایجادشده جایگزین جمعیت فعلی می­ شود. معمولاً در عملیات جایگزینی مربوط به روش زایشی در هر تکرار کل جمعیت حاضر با جمعیت جدید جایگزین می­گردد.

• الگوریتم­های ژنتیک حالت دائمی[۵]

در این روش عموماً در هر گام زمانی، فقط یک عضو جدید به جمعیت جدید اضافه می­ شود. استراتژی جایگزینی تعیین می­ کند که کدام یک از اعضای جمعیت باید با عضو جدید جایگزین گردد (کیا، ۱۳۹۱).

 

۲-۲-۴-۲- مزایای الگوریتم­های ژنتیک

• • با متغیرهای پیوسته و هم گسسته می ­تواند عمل بهینه­سازی را انجام دهد.
  • نیازی به محاسبه مشتق توابع ندارد.
  • به طور همزمان می ­تواند تمامی ناحیه وسیع تابع هزینه را جستجو کند.
  • قابل اجرا از طریق کامپیوتر­های موازی است.
  • توابع هزینه­ای که بسیار پیچیده باشند نیز از این طریق قابل بهینه­سازی می­باشند و الگوریتم در اکسترمم محلی به دام نمی­افتد.
  • قادر است تا متغیرها را کدبندی نموده و بهینه­سازی را با متغیر­های کدبندی شده انجام دهد، کد­­بندی سرعت همگرایی الگوریتم را افزایش می­دهد.
  • این الگوریتم توانایی کار کردن با داده ­های عددی تولید شده و داده ­های تجربی را علاوه بر توابع تحلیلی دارد.
  • فرایند ارائه ­شده توسط الگوریتم­های ژنتیک برروی فضایی از مجموعه نمایندگان با همان فضای کروموزوم­ها اعمال می­گردند بر روی خود فضای راه­حل­ها.
  • الگوریتم­های ژنتیکی از قوانین انتقالی احتمالی به جای قوانین انتقالی قطعی استفاده می­ کند.
  • تنها ملاک ارزیابی و سنجش میزان شایستگی هر راه­حل توسط الگوریتم­های ژنتیک، مقدار تابع شایستگی آن در فضای کروموزو­ها می­باشد و نه معیارهای مورد نظر در سطح فضای راه­حل­ها.
  • برای حل برخی از مسائل رده NP-hard نیز استفاده می­ شود.

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

 

۲-۲-۴-۳- محدودیت­های الگوریتم ژنتیک

یک مشکل چگونگی نوشتن عملگر Fitness است که منجر به بهترین راه­حل برای مسئله شود. اگر این کارکرد برازش به خوبی و قوی انتخاب نشوند ممکن است باعث شود که راه­حلی برای مسئله پیدا نکنیم یا مسئله­ای دیگر را به اشتباه حل کنیم. به علاوه برای انتخاب مناسب برای Fitness، پارامترهای دیگری مثل اندازه جمعیت، نرخ جهش و ترکیب و قدرت و نوع انتخاب هم باید مورد توجه قرار گیرند.

مشکل دیگر، که آن را نارس می­نامیم، این است که اگر یک ژنوم که فاصله­اش با سایر ژنوم­های نسلش زیاد باشد و خیلی زود دیده شود ممکن است محدودیت ایجاد کند و راه را به سوی جواب بهینه محلی سوق دهد. این اتفاق معمولاً در جمعیت­های کم اتفاق می­افتد، روش­های Rank، Scaling، Tournament selection بر این مشکل غلبه می­ کنند.

 

۲-۲-۴-۴- استراتژی­ های برخورد با محدودیت­های الگوریتم ژنتیک

بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت­های مسئله می­باشد، زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم ژنتیک باعث تولید کروموزوم­های غیر موجه می­ شود. در ادامه به چند تکنیک معمول جهت مواجهه با محدودیت­ها اشاره می­ شود:

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

یک روش برای جلوگیری از تولید کروموزوم غیر موجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم تولید شده نیز موجه باشد. در این حالت یک سری مشکلات وجود دارد. مثلا پیدا کردن عملگری که دارای شرط فوق باشد بسیار دشوار بوده و از مسئله ای به مسئله دیگر متفاوت می­باشد.

استراتژی ردی

در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیر موجه بودن حذف می­گردد. این روش بسیار ساده و کارا می­باشد.

استراتژی اصلاحی

در این روش به جای اینکه کروموزوم غیر موجه حذف گردد تبدیل به یک کروموزوم موجه می­ شود. این روش نیز مانند روش اول به مسئله وابسته بوده و یافتن فرایند اصلاح گاهی بسیار پیچیده می­باشد.

استراتژی جریمه­ای

در این روش بر خلاف سه روش قبل که از ورود جواب­های غیر موجه جلوگیری می­کردند، جواب غیر موجه با احتمال کم امکان حضور می­یابند. سه روش فوق دارای این عیب بودند که به هیچ نقطه­ای بیرون از فضای موجه توجه نمی­کردند، اما در بعضی مسائل بهینه­سازی، جواب­های غیر­موجه درصد زیادی از جمعیت را اشغال می­ کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت­گیر و مشکل باشد.

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

مسئله اصلی چگونگی انتخاب یک مقدار مناسب برای مقدار جریمه می­باشد تا در حل مسائل به ما کمک نماید. نکته­ای که در روش جریمه وجود دارد این است که یک جواب غیر­موجه به سادگی حذف نمی­ شود، زیرا ممکن است در ژن­های آن اطلاعات مفیدی وجود داشته باشد که با اندکی تغییر به جواب بهینه تبدیل شوند.

 

۲-۲-۴-۵- بهبود الگوریتم ژنتیک

برای بهبود الگوریتم ژنتیک می­توانیم تغییرات زیر را اعمال کنیم:

• استفاده از بهینه­گر محلی
• تغییر پارامترهایی از قبیل تغییر جمعیت اولیه، نرخ جهش و کسر ادغام (ترکیب)
• تغییر الگوریتم ژنتیک باینری به پیوسته و بالعکس

 

۲-۲-۴-۶- چند نمونه از کاربرد­های الگوریتم ژنتیک

• نرم­افزارهای شناسایی چهره (شناسایی چهره با بهره گرفتن از تصویر ثبت شده. در این روش، شناسایی چهره بر اساس فاصله اجزای چهره و ویژگی­های محلی و هندسی صورت می­گیرد که تغییرات ناشی از گیم، تغییرات نور، افزایش سن کم­ترین تاثیر را خواهد داشت. همچنین گراف­ها برای چهره­ های جدید با بهره گرفتن از الگوریتم­های ژنتیک ساخته شده و با بهره گرفتن از یک تابع تشابه، قابل مقایسه با یکدیگر هستند که این امرتاثیر بسزایی در افزایش سرعت شناسایی خواهد داشت).
• توپولوژی­های شبکه ­های کامپیوتری توزیع شده
• بهینه­سازی ساختار مولکولی شیمیایی

 

• مهندسی برق برای ساخت آنتن­های برق
• مهندسی نرم­افزار
• بازی­های کامپیوتری
• مهندسی مواد
• مهندسی سیستم
• رباتیک
• تشخیص الگو و استخراج داده
• حل مسئله فروشنده دوره­گرد
• آموزش شبکه ­های عصبی مصنوعی
• یاددهی رفتار با رباتها
• یادگیری قوانین فازی با بهره گرفتن از الگوریتم ژنتیک

[۱] - PGA

[۲] - AGA

[۳] - IAGA