همانطور که در شکل بالا مشاهده می کنید شمای کلی از نحوهٔ عملکرد این الگوریتم را به شما نشان میدهد در ادامه به تعریف و انواع و کابرد این الگوریتم در مسائل می پردازیم.
فرق این مقاله با مقالههای مشابه با این موضوع در این میباشد که در این جا از نگاه کاربردی به الگوریتم های ژنتیکی نگاه شده است و از این منظر در این مقاله به چند نمونه کاربرد این تکنیک در مسائل معروف اشاره شده است. در این مقاله در ابتدا به جایگاه الگوریتم های ژنتیکی و کاربرد آن ها در علم هوش مصنوعی می پردازیم و سپس به توضیح این الگوریتم و انواع آن و همچنین به نحوهٔ نمایش آن می پردازیم. همچنین در انتها به چند منبع برای نمونههای کد باز(Open Source) اشاره می کنیم که خوانندگان در صورت علاقه به کار عملی این الگوریتم را به صورت عملی اجرا کنند تا با عملکرد آن آشنا شوند.
روش جستجوی تکاملی
روش های جستجوی ناآگاهانه ، اگاهانه و متاهیوریستیک برای حل مسائل هوش مصنوعی بسیار کارآمد میباشند. همچنین می دانیم که در مورد مسائل بهینه سازی اغلب روش های آگاهانه و ناآگاهانه جوابگوی نیاز ما نخواهند بود. چرا که بیشتر مسائل بهینه سازی در رده مسائل NP قرار دارند. بنابراین نیاز به روش جستجوی دیگری داریم که بتواند در فضای حالت مسائل NP به طرف جواب بهینه سراسری حرکت کند. بدین منظور روش های جستجوی متاهیوریستیک را مطرح می کنیم,این روش های جستجو میتوانند به سمت بهینگی های سراسری مسئله حرکت کنند. در کنار روش های جستجوی متاهیوریستیکی ، روش های جستجوی دیگری نیز وجود دارند که به روش های تکاملی معروفند. در ادامه با این نوع الگوریتم بیشتر آشنا می شویم.(لازم به ذکر است که در نگاه کاربردی به الگوریتم های ژنتیکی, اولین قدم در فهم آن, تفهیم الگوریتم های تکامل و تفاوت آن با دیگر الگوریتم های مشابه است.)
نظریه داروین
بر اساس [[نظریه داروین]] نسل هایی که از ویژگی های و خصوصیات برتری نسبت به نسل های دیگر برخوردارند شانس بیشتری نیز برای بقا و تکثیر خواهند داشت و ویژگی ها و خصوصیات برتر آنها به نسل های بعدی آنان نیز منتقل خواهد شد. همچنین بخش دوم نظریه داروین بیان میکند که هنگام تکثیر یک ارگان فرزند ، به تصادف رویدادهایی اتفاق می افتد که موجب تغییر خصوصیات ارگان فرزند میشود و در صورتی که این تغییر فایدهای برای ارگان فرزند داشته باشد موجب افزایش احتمال بقای آن ارگان فرزند خواهد شد. در محاسبات کامپیوتری ، بر اساس این نظریه داروین روش هایی برای مسائل بهینه سازی مطرح شدند که همه این روش ها از پردازش تکاملی در طبیعت نشات گرفته اند. ما نیز به این روش های جستجو ، الگوریتم های جستجوی تکاملی می گوییم.
انواع مختلف الگوریتم های تکاملی
انواع مختلف الگوریتم های تکاملی که تا بحال مطرح شده اند، به شرح زیر میباشد :
Genetic Algorithm
Genetic Programming
Evolutionary Strategies
Evolutionary Programming
Differential Evolution
Cultural Evolution
Co-evolution
در ادامه قصد داریم بحث خود را بر روی الگوریتم های ژنتیکی سوق دهیم.
الگوریتم ژنتیک
الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده آن برگرفته از طبیعت میباشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند . به عنوان مثال میتوان به مسئله فروشنده دوره گرد اشاره کرد.(در ادامه با این مسئله و حل آن بیشتر آشنا می شویم) در طبیعت از ترکیب کروموزوم های بهتر ، نسل های بهتری پدید میآیند . در این بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی میدهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل میکند .
منابع
An introduction to genetic algorithms by Melanie Mitchell - Computers - 1998 - 209 pages
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
Genetic Algorithms in Search, Optimization, and Machine Learning by David E. Goldberg (very useful)
Holland, John H (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor
Koza, John (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press. ISBN 0-262-11170-5
Michalewicz, Zbigniew (1999), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag.
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely a