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

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

الگوریتم‌های ژنتیک (Genetic algorithm) تکنیک جستجو در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی مدل، ریاضی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکاملی است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت، جهش زیست‌شناسی و اصول انتخابی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌شود. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در مدل‌سازی الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حل‌ها تبدیل می‌شود سپس راه حل‌ها به عنوان کاندیداها توسط تابع برازش یا تابع برازندگی (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. به‌طور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند که این الگوریتم‌ها از بخش‌های تابع برازش، نمایش، انتخاب و تغییر تشکیل می‌شوند.

مقدمه

بسیاری از اختراعات بشری از طبیعت الهام گرفته شده‌اند. «شبکه‌های عصبی مصنوعی» (ANN | Artificial Neural Network) نمونه بارز چنین ابداعاتی هستند. یکی دیگر از چنین ابداعاتی، توسعه ایده الگوریتم ژنتیک است. الگوریتم‌های ژنتیک، با «شبیه‌سازی» (Simulating) فرایند تکامل در طبیعت، با هدف یافتن بهترین جواب ممکن برای یک مسأله، به جستجو در «فضای جواب‌های کاندید» (Candidate Solution Space) می‌پردازند. در فرایند جستجو برای یافتن جواب بهینه، ابتدا مجموعه یا جمعیتی از جواب‌های ابتدایی تولید می‌شود. سپس، در «نسل‌های» (Generations) متوالی، مجموعه‌ای از جواب‌های تغییر یافته تولید می‌شوند (در هر نسل از الگوریتم ژنتیک، تغییرات خاصی در ژن‌های کروموزوم‌های تشکیل دهنده جمعیت ایجاد می‌شود). جواب‌های اولیه معمولا به شکلی تغییر می‌کنند که در هر نسل، جمعیت جواب‌ها به سمت جواب بهینه «همگرا» (Converge) می‌شوند.

یکی از مهم‌ترین ویژگی‌های الگوریتم ژنتیک، کدبندی متغیرهای لازم برای توصیف مسأله است.

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

الگوریتم‌های ژنتیک، الگوریتم‌های جستجو هستند که بر پایه مفاهیم انتخاب طبیعی و ژنتیک موجودات زنده بنا نهاده شده‌اند. الگوریتم‌های ژنتیک پدیده آمده‌اند تا برخی از فرایندهای مشاهده شده در «تکامل طبیعی» (Natural Evolution) را از طریق الگوریتم‌های کامپیوتری شبیه‌سازی کنند. فرایندهایی که بر اساس انجام عملیات روی کروموزوم‌ها (سیستم‌های ارگانیک جهت کدبندی کردن ساختار ژنتیکی موجودات زنده) شکل گرفته‌اند.

همانطور که پیش از این نیز اشاره شد، الگوریتم‌های ژنتیک در زیر مجموعه الگوریتم‌های جستجو قرار می‌‌گیرند. با این حال، تفاوت‌های بسیار اساسی با دیگر الگوریتم‌های جستجو دارند. الگوریتم‌های ژنتیک به جای اینکه به طور مستقیم با مقادیر پارامترهای مسأله سروکار داشته باشند، با نمایشی کدبندی شده از مجموعه پارامترهای مسأله کار می‌کنند و جمعیتی متشکل از نقاط در یک فضای جستجو را برای یافتن جواب‌های مسأله جستجو می‌کنند. همچنین، بدون اینکه از اطلاعات «گرادیان» (Gradient) مرتبط با «تابع هدف» (Objective Function) مسأله اطلاعی داشته باشند، تابع هدف مسأله را بهینه‌سازی می‌کنند.

در الگوریتم‌های ژنتیک برای «گذار» (Transition) از یک حالت در فضای مسأله به حالت دیگر، از مکانیزم‌های «احتمالی» (Probabilistic) استفاده می‌شود؛ در حالی که در الگوریتم‌های جستجوی مرسوم، از اطلاعات گرادیان مرتبط با تابع هدف مسأله برای چنین کاری استفاده می‌شود. چنین ویژگی مهمی در الگوریتم‌های ژنتیک، آن‌ها را تبدیل به الگوریتم‌های جستجوی «همه منظوره» (General purpose) کرده است. همچنین، از الگوریتم‌های ژنتیک برای جستجوی فضاهای جستجوی نامنظم و بی‌قاعده استفاده می‌شود. به طور کلی، از الگوریتم‌های ژنتیک برای حل مسأله در کاربردهایی نظیر بهینه‌سازی توابع، «تخمین پارامتر» (Parameter Estimation) و «یادگیری ماشین» (Machine Learning) استفاده می‌شود.