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

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

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

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

 

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

انواع دسته بندی های الگوریتم های فراابتکاری و جایگاه الگوریتم ژنتیک:

در هر مسئله به خصوص در فضای مسئله بزرگ عملیات جستجو بسیار مهم می باشد. در شکل2 انواع دسته بندی های جستجو آورده شده است. همان طور که مشخص گردیده است جایگاه الگوریتم ژنتیک زیر مجموعه ای از جستجوهای تصادفی هدایت شده می باشد.

شکل2: جایگاه الگوریتم ژنتیک در انواع مختلف تکنیک های جستجو

الگوریتم های فراابتکاری را می توان براساس معیارهای مختلفی دسته بندی کرد:

1.     دسته بندی براساس الگوریتم های الهام گرفته از طبیعت یا الهام نگرفته از طبیعت

همان طور که در شکل3 در این دسته بندی نشان داده شده است الگوریتم ژنتیک با توجه به اینکه از نظریه تکامل داروین برای رشد جمعیت انسانی الهام گرفته است بنابراین جزو دسته الهام گرفته ها از طبیعت محسوب می گردد.

شکل3: جایگاه الگوریتم ژنتیک در دسته الهام گرفته شده یا نشده از طبیعت

2.     دسته بندی الگوریتم های جستجوی نقطه ای تنها یا مبتنی بر جمعیت

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

 

شکل4 : جایگاه الگوریتم ژنتیک در دسته نقطه تنها یا مبتنی بر جمعیت

3.     دسته بندی براساس الگوریتم های مبتنی بر حافظه یا بدون حافظه

در شکل 5 انواع دسته بندی الگوریتم ها براساس حافظه دار یا بدون حافظه بودن نشان داده شده است.

شکل 5: دسته بندی الگوریتم های فراابتکاری از نظر نیاز داشتن به حافظه

4.     دسته بندی انواع الگوریتم از نظر دقیق یا تقریبی بودن

در این نوع دسته بندی همان طور که در شکل 6 نشان داده شده است الگوریتم ها یا به روش دقیق یا به صورت تقریبی حل می شوند.

شکل 6: انواع روش های حل مسئله به روش دقیق یا تقریبی

 [1]: Omid Bozorg‐Haddad, Mohammad Solgi, Hugo A. Loaiciga,” Meta‐Heuristic and Evolutionary Algorithms for Engineering Optimization”, Wiley,2017.

[2]: Introduction to Evolutionary Algorithms, Felix Streichert, University of Tuebingen.