بخشی از پاورپوینت
اسلاید 1 :
الگوریتم ژنتیک
- بر مبنای اصول انتخاب طبیعی داروین.
- یک تکنیک برنامه نویسی که از تکامل ژنتیکی
به عنوان یک الگوی حل استفاده می کند.
- برای مسایل جستجو و بهینه سازی استفاده
می شود.
- توسط جان هولند در سال 1975 در دانشگاه میشیگان ارائه شد.
اسلاید 2 :
طبقه بندی تکنیک های جستجو
اسلاید 3 :
قانون انتخاب طبیعی داروین
بدین صورت است که تنها گونه هایی از یک جمعیت ادامه نسل می دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می روند .
مثلا فرض کنید گونه خاصی از افراد هوش بسیار بیشتری از بقیه افراد یک جامعه دارند .در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود . حال اگر این خصوصیت ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد این گونه افراد بیشتر خواهد بود . اگر همین روند را ادامه دهیم خواهید دید که در طی نسل های متوالی دائما جامعه نمونه ما با هوش تر می شود بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائما در حال افزایش است .
اسلاید 4 :
بدین ترتیب می توان دید که طبیعت با بهره گیری از یک روش بسیار ساده یعنی حذف تدریجی گونه های نامناسب و در عین حال تکثیر گونه های بهینه توانسته دائما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد .
Reproduction
Competition
Selection
Survive
اسلاید 5 :
زمينه بيولوژيکی
تمام ارگانيسم های زنده شامل سلول ها هستند. در هر سلول قسمت های مشابهی از کروموزوم ها (Chromosomes) وجود دارند. کروموزوم ها شامل ژن ها (Genes) و بلوکهای DNA هستند. هر ژن ( يا دسته ای از ژنها) ويژگی ای )برای مثال رنگ چشم ها( را رمزگذاری
می کند. در واقع يک کروموزوم بصورت زنجيره ای از ژنها قابل تصور است.
اسلاید 6 :
ژنها ( خصيصه ها ) می توانند از والدين به فرزندان انتقال يابند. مثلاً ممکن است فرزند رنگ چشم را از يکی از والدين ( مثلاً مادر ) و طول قد را از ديگری ( مثلاً پدر) به ارث ببرد.شکل زیر نمايشی از اين موضوع میباشد .
اسلاید 7 :
روند کلی بهینه سازی و حل مسایل در الگوریتم ژنتیک
1 – شروع (Start) :
تولید تصادفی یک جمعیت (population) که شامل تعداد زیادی کروموزم است .
2 – صحت و درستی (Fitness) :
ارزیابی صحت برای تابع f (x) به ازای هر کروموزم x در جمعیت می باشد .
اسلاید 8 :
3- ایجاد یک جمعیت جدید (New Population ) :
تولید یک جمعیت جدید با انجام تمامی زیر گروه های زیر تا آنکه یک جمعیت جدید ایجاد گردد .
3-1 : انتخاب (Selection ) :
انتخاب کروموزم های پدر و مادر از جمعیت قبلی با توجه به صحت و درستی آن ( Fitness ) به طوریکه هر چه Fitness بهتر باشد یعنی دقت جواب در همگرایی بیشتر باشد شانس بیشتری برای انتخاب دارد .
اسلاید 9 :
انواع انتخاب
1 - روش چرخ رولت ( Roulette Wheel )
2 - روش بولترزمن ( Boltzman )
3 - روش مسابقه ای ( Tournament )
4 - روش منظم و پشت سر هم (Rank )
5 - روش حالت پایدار (Steady State )
6 - روش الیتیسم (Elitism )
معمولا این دو روش استفاده می شود
اسلاید 10 :
3-2 : تولید مثل (Crossover ) :
انجام زاد و ولد و ایجاد یک نسل جدید .
هدف : ساختن دو و یا چند كروموزوم با استفاده از ترکیب کردن.
انواع معمول : یک نقطه, دو نقطه ، چند نقطه ای ،یکنواخت .
اسلاید 11 :
تولید مثل یک نقطه ای :
اسلاید 12 :
تولید مثل دو نقطه ای :
اسلاید 13 :
تولید مثل چند نقطه ای :
اسلاید 14 :
تولید مثل یکنواخت :
اسلاید 15 :
3-3 : جهش (Mutation ) :
مشخص شدن مکان فرزند تولید شده در کروموزوم .
هدف: داشتن تنوع و گوناگونی در جمعیت.
بررسی زیر فضاها و راه حلهای جدید.
تصوری از اینکه راه حل جدید بهتر یا بدتر است وجود ندارد.
اسلاید 17 :
3-4 :پذیرش ( Accepting ):
جا دادن فرزند جدید در داخل جمعیت .
4 – جایگزینی ( Replace ) :
جایگزینی جمعیت جدید به جای جمعیت قبلی و مورد استفاده قرار دادن جمعیت جدید در مراحل بعدی الگوریتم می باشد .
5 – امتحان ( Test ) :
اگر شرایط مطلوب در حل مسئله ایجاد شد اعلام می کنیم که به بهترین جواب رسیده ایم و از الگوریتم خارج می شویم در غیر اینصورت به مرحله 2 یعنی Fitness می رویم و دوباره همین روند را تکرار می کنیم .
اسلاید 18 :
نمودار گردشی یک ژنتیک الگوریتم
انتخاب (Selection )
تولید مثل جهش
Crossover mutation
Reproduction
جایگزینی Replacement
اسلاید 19 :
شماتیک الگوریتم ژنتیک
Start
Create initial , random population of organisms
Evaluate fitness for each organism
Optimal or good solution found ?
Reproduce and kill organisms
Mutate organism
End
YES
