مقدمه ای بر الگوریتم ژنتیک - Artificial Intelligence

A162 · ۰۴-۱۰-۱۳۸۷, ۰۲:۲۷ بعد از ظهر

ممنون از شما !
بسيار جالب بود
حالا چطور اون معادله اولي كه فرموديد رو ميشه به اين روش حل كرد؟
با تشكر دوباره

**Siavash** · ۰۵-۲۲-۱۳۸۷, ۰۲:۰۶ قبل از ظهر

سوال خیلی خوبیه!
فرض کنید می خوایم اون معادلرو حل بکنیم.
یک راه اینه که مثلا یک متغیر رو مقدارش رو صفر قرار بدیم و 0.1 0.1 به اون اضافه کنیم و هر بار جواب رو توی معادله قرار بدیم تا یک جواب نزدیک به دست بیاریم. این کار اولین روشی هست که شاید به ذهن هر کسی برسه. ولی مشکلات زیادی داره. اولا لزوما به جواب نمی رسه. چون ممکنه 0.1 خیلی مقدار بزرگی نسبت به جواب باشه یا مثلا جواب منفی باشه.

راه بعدی استفاده از روش های مختلف محاسبات عددی معمول هست. مثل تکرار ساده یا روش نیوتن یا ... این روش ها روش های خوبی هستند نسبت به روش قبل. اما خیلی وقت ها این روش ها همگرا نمیشن. یا توی یک اکسترمم نسبی میفتن!

روشی که می خوایم بگیم خیلی وقت ها از این دو روش بهتر هست همین الگوریتم ژنتیک هست! اما چطوری؟
خوب تو این روش اول یک تابع سلامت یا Fitness Function تعریف می شه. این تابع سلامت هر کروموزوم رو تعیین می کنه. بعد روش Cross over و Mutation رو باید انتخاب کنیم و جمعیت اولیرو تولید می کنیم.
در آموزش بالا من ساده ترین نوع و در واقع روش کلاسیک تولید جمعیت اولیه و Crossover و Mutation رو گفتم.
حالا می خوام نوع دیگه ای از اون رو معرفی کنم. این بار جای اینکه اعداد باینری رو به عنوان جمعیت اولیه در نظر بگیریم، کلی اعداد حقیقی تولید می کنیم به عنوان جمعیت اولیه. مثلا 100، -10.5، 57.2 و ...
خوب حالا سوال پیش میاد پس عملیات Crossover و Mutation چطور خواهند بود؟
باز هم روش های مختلفی هستند. ما ساده ترینش رو انتخاب می کنیم. یعنی به عنوان عملیات Crossover از دو کروموزوم پدر و مادر میانگین می گیریم و به عنوان عملیات Mutation بعضی اوقات عدد رو با یک درصد کمی از خودش جمع یا تفریق می کنیم.

كد:

X^2 + e^X + 3*sin(X) + int(-X^X) / X = 12

خوب حالا شروع می کنیم به بررسی فرآیند حل اون معادله. اول همونطوری که گفتم یک جمعیت اولیه داریم. مقدار هر کدوم از کروموزوم های جمعیت اولیرو به جای X در سمت چپ معادله قرار می دیم. این مقدار باید در نهایت 12 بشه (سمت راست معادله).
پس تابع سلامت رو این طور تعریف می کنیم: تفاضل جواب بدست اومده از قرار دادن کرومزوم های جمعیت اولیه در سمت چپ معادله منهای عدد 12.
پس یعنی اگر تابع سلامت 0 بشه ما دقیقا به جواب رسیدیم. برای تمام کروموزوم ها مقدار سلامتیشون رو بدست میاریم. از بین سالم ترین کرومزوم ها (یعنی کرومزوم هایی که مقدار تابع سلامتشون بیشتر به صفر نزدیکه)، تعدادی انتخاب می کنیم. این کرومزوم ها روشون عملیات Crossover و Mutation انجام میشه. یعنی با انتخاب دو به دو ی اون ها و میانگین گرفتن یک جمعیت جدید ایجاد میشه! به این روش انتخاب، انتخاب Elite ها یا بهترین ها در هر مرحله میگن. روش های دیگری هم برای قسمت انتخاب وجود داره.
حالا یک جمعیت کروموزوم های جدید داریم و مجددا عملیات تکرار می شه تا بالاخره یکی از کروموزوم ها مقدار تابع سلامتش تا حدی که ما می خوایم به 0 نزدیک بشه، مثلا 0.0001
شاید به نظر کمی عجیب بیاد که این روش واقعا بتونه معادلرو حل کنه. اما این روش که مثل اکثر روش های بهینه سازی دیگه بر مبنای آزمایش و خطا هست در بعضی مواقع بسیار زودتر ما رو به نتیجه ی مورد نظر می رسونه. کافیه امتحان کنید.