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

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

جدول هم ارزی مفاهیم بیولوژیکی و عناصر GA

نمودار گردشی فرآیند یک الگوریتم تکاملی

فرایند تولید تا زمانی که جواب مورد نظر به دست آید ادامه می یابد(اغلب جمعیت بصورت تصادفی تولید می شود)

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

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

Encoding: این مرحله شاید مشکل ترین مرحله حل مساله به روش الگوریتم ژنتیک باشد الگوریتم ژنتیک به جای آنکه بر روی پارامترها یا متغیر های مساله کار کند، با شکل کد شده آن ها سر و کار دارد. 3 یکی از روش های کد کردن، کد کردن دودویی می باشد که در آن هدف تبدیل جواب مساله به رشته ای از اعداد باینری (در مبنای 2) است.

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

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

Mutation: جهش نیز عملگری است که جواب های ممکن دیگری را ایجاد می کند در الگوریتم ژنتیک بعد از اینکه یک عضو در جمعیت جدید بوجود آمد، هر ژن آن با احتمال جهش، جهش میابد. در جهش ممکن است ژنی از مجموعه ژن های جمعیت حذف شود یا ژنی که تا حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و بسته به نوع کد گذاری روش های متفاوت جهش استفاده می شود.

Decoding :عکس عمل encoding است. در این مرحله بعد از اینکه الگوریتم ها بهترین جواب را برای مساله ارائه کردند الزم است عکس عمل رمزگذاری روی جوابها یا همان عمل رمزگشایی اعمال شود تا بتوانیم نسخه واقعی جواب را به وضوح در دست داشته باشیم.

در شکل زیر فلوچارت الگوریتم ژنتیک نشان داده شده است که مراحل اجرای آن را بیان می کند