مقدمه‌ای بر الگوریتم های ژنتیک

مقدمه‌ای بر الگوریتم های ژنتیک :
الگوریتم ژنتیک (Genetic Algorithm -GA) یک تکنیک بهینه سازی بر اساس جستجو می‌باشد که بر اصول ژنتیک و انتخاب طبیعی(Natural Selection) پایه گذاری شده است.این تکنیک به کرات برای یافتن راه حل بهینه یا نزدیک به بهینه مورد استفاده قرار می‌گیرد تا بدین وسیله مسائل مشکلی که ممکن است توسط روشهای دیگر در زمان طولانی حل شوند را در یک زمان مناسب و بهینه حل نماید.اغلب اوقات از این تکنیک در پژوهش ها و یادگیری ماشین برای حل مسائل بهینه سازی (optimization problems مسائلی که در آن بهترین راه حل از میان همه راه حل‌های ممکن یافت می شود)استفاده می‌شود
مقدمه ای بر بهینه سازی :

بهینه سازی پروسه‌ ساخت یک چیز بهتر است.در هر پروسه ، یک مجموعه از ورودی ها داریم و یک مجموعه از خروجی ها که در شکل زیر نشان داده شده‌اند

بهینه سازی به پیدا کردن مقادیری از ورودی ها اطلاق می‌شود به نحوی که بهترین مقادیر خروجی را بدست بیاوریم. تعریف بهترین از مسائله به مسائله دیگر متفاوت است اما در اصطلاح ریاضیات به حداکثر رساند یا به حداقل رساندن یک یا چند تابع هدف از طریق تغییر دادن پارامتر های ورودی اطلاق می‌شود.یک مجموعه از همه راه حل‌های ممکن یا مقادیر ورودی می‌تواند فضای جستجو را تکشیل دهد.در این فضای جستجو یک نقطه یا یک مجموعه از نقاط که راه حل بهینه را فراهم می‌کنند پنهان شده‌اند. وظیفه نهایی بهینه سازی پیدا کردن نقطه یا مجموعه‌ای از نقاط در فضای جستجو است.
الگوریتم های ژنتیک چه هستند ؟
طبیعت همیشه یک منبع بزرگ از الهام برای همه نسل بشر بوده است.الگوریتم های ژنتیک الگوریتم هایی بر اساس جستجو هستند که بر پایه مفهوم انتخاب طبیعی و ژنتیک پایه گذاری شده است.الگوریتم های ژنتیک زیر مجموعه‌ای از یک شاخه بسیار بزرگ‌تر از محاسبات که معروف به محاسبات تکاملی (Evolutionary Computation) است می‌باشند.الگوریتم های ژنتیک بوسیله John Holان وی در دانشگاه میشیگان توسعه داده شد و از این الگوریتم ها برای حل مسائل مختلف بهینه سازی با درجه بالایی از موفقیت استفاده شده است.
در الگوریتم های ژنتیک یک مخزن یا مجموعه از راه حل‌های ممکن برای مسائله داده شده داریم.این راه حل‌ها تحت عملیات های نوترکیبی (recombination) و جهش(mutation) شبیه آنچه در ژنتیک طبیعی رخ می‌دهد ، فرزندان جدیدی تولید می‌کنند.این پروسه در نسل های مختلف تکرار می‌شود.به هر فرد ( یا راه حل کاندید) یک مقدار متناسب اختصاص داده می شود( بر اساس مقدار تابع هدف آن) و افراد شاخص شانس بالاتری برای زاد و ولد و تولید افراد شاخص تر دارند. این در‌واقع تعریف تئوری داروین است که معتقد به بقای نسل اصلحتر می‌باشد.در این روش بهترین افراد یا راه حل‌ها در نسل های ایجاد شده استخراج می‌شوند.این کار تا رسیدن به یک معیار توقف ادامه می‌یابد.الگوریتم های ژنتیک به اندازه کافی در طبیعت تصادفی هستند، اما آن‌ها عمل‌کرد خیلی بهتری از جستجوی محلی تصادفی دارند( که در آن ما فقط راه حل‌های تصادفی مختلف را مورد برآورد قرار می‌دهیم).

مزایای الگوریتم های ژنتیک :
الگوریتم های ژنتیک دارای مزیت‌های متعددی هستند که آن‌ها را فوق‌العاده محبوب و مورد استفاده نموده است

•     نیاز به هیچ اطلاعات فرعی ( مشتق شده) نیست .که ممکن است برای اغلب مسائل دنیای واقعی در دسترس نباشد.
•     قابلیت‌های بسیار خوب برای موازی سازی دارد
•     هر دو تابع های گسسته و پیوسته را بهینه سازی می نماید و همچنین مسائل چند هدفه را ( multi-objective)0
•     لیستی از راه حل‌های خوب را بجای یک راه حل یکتا تهیه می‌کنند
•     همیشه یک راه حل برای مسائل دارند در طول زمان بهتر می‌شود
•     هنگامی که فضای جستجو بسیار بزرگ است و تعداد زیادی از پارامتر ها در مسائله درگیر هستند مفید هستند

محدودیت‌های الگوریتم های ژنتیک :
شبیه هر تکنیک دیگری الگوریتم های ژنتیک از یکسری محدودیت‌ها رنج می‌برند که شامل موارد زیر است :

•     الگوریتم های ژنتیک برای همه مسائل مناسب نیستند مخصوصاً آن دسته از مسائلی که ساده هستند و اطلاعات مشتق شده (derivative information) برای آن‌ها موجود باشد
•     مقدار متناسب ( مناسب) مکرراً محاسبه می‌شود که ممکن است برای بعضی از مسائل محاسباتی پر هزینه و گران باشد
•     تصادفی بودن باعث می‌شود که هیچ تضمینی برای بهینه بودن یا کیفیت راه حل وجود نداشته باشد
•     اگر درست اجرا نشود الگوریتم ژنتیک ممکن است که یک راه حل بهینه را بوجود نیاورد.

انگیزه برای استفاده از الگوریتم های ژنتیک :
الگوریتم های ژنتیک این توان را دارند که راه حل‌هایی به اندازه کافی سریع و به اندازه کافی خوب فراهم کنند.این ویژگی‌ها باعث می‌شود که الگوریتم های ژنتیک برای استفاده در حل مسائل مربوط به بهینه سازی جذاب باشند.دلایلی مورد نیاز بودن الگوریتم های ژنتیک به شرح ذیل می‌باشد :
حل مسائل مشکل
در علوم کامپیوتری ، مجموعه‌ای از مسائل موجود است که در دسته NP-Hard قرار می گیرند.و این بدان معناست که حتی قوی‌ترین سیستم‌های محاسبه ای برای حل این مسائل نیازی صرف زمان خیلی طلانی دارند ( حتی سالها).در چنین سناریوهایی یک ابزار ثابت شده و خوب برای فراهم نمودن یک راه حل نزدیک به بهینه در یک مدت زمان کوتاه است.
شکست روش‌های مبتنی بر گرادیان.
روش‌های محاسبه قدیمی با شروع در یک نقطه تصادفی و حرکت در یک جهت از گرادیان تا رسید به بالاترین مکان کار می کنند.این تکنیک برای توابع هدفی که تنها یک نقطه اوج دارند مثل تابع هزینه در رگرسیون خطی.اما در اغلط موقعیت های دنیای واقعی با مسائل خیلی پیچیده‌ای سر و کار داریم که به landscapes (منظره ها) معروف هستند ، که از تعدادی زیادی قله و دره ساخته شده اند.که باعث می‌شوند متد های قدیمی که شرح داده شده در مواجه با آن موفق نباشند. این متدها از گرایش ذاتی به گیر افتادن در نقطه قله مطلوب محلی رنج می برند.این مطلب در شکل زیر نمایش داده شده است :


بدست آوردن راه حل خوب با سرعت مناسب
برخی از مسائل مشکل مثل مسائله فروشنده دوره‌گرد (Travelling Salesperson Problem -TSP) دارای کاربرد در دنیای واقعی هستند.مثل پیدا کردن مسیر و طراحی VLSI .حالا فرض کنید که شما از سیستم ناوبری GPS استفاده می‌کنید و برای محاسبه مسیر بهینه از مبداء به مقصد چند دقیقه ( یا حتی چند ساعت) صرف می‌کنید . تأخیر در اینگونه برنامه‌های کاربردی در دنیای واقعی پذیرفتی نیست پس ش یک راه حل به اندازه کافی خوب راه حلی است که به اندازه کافی هم سریع باشد