پاورپوینت الگوریتم های تکاملی (الگوریتم ژنتیک)

بخشی از پاورپوینت

اسلاید 2 :

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

اسلاید 3 :

فهرست
مقدمه
تاریخچه
تعاریف
مرحل الگوریتم ژنتیک
روشهای نمایش
روشهای انتخاب
روشهای تغییر (اپراتورهای ژنتیکی)
مثال
مزایا
معایب
چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک
کاربرد هاي الگوريتم ژنتيک در پزشكي
منابع

اسلاید 4 :

مقدمه
قانون انتخاب طبيعي بدين صورت است كه تنها گونههايي از يك جمعيت ادامه نسل ميدهند كه بهترين خصوصيات را داشته باشند و آنهايي كه اين خصوصيات را نداشته باشند به تدريج و در طي زمان از بين ميروند.
انتخاب درست ترین ها نه بهترین ها

اسلاید 5 :

تاریخچه
الگوريتم هاي ژنتيك با توجه به نظريه داروين در مورد تكامل شكل گرفتند.
محاسبات تکاملي درسال 1960 به وسيله ي شخصي به نام Rechenberg مرسوم شد
در دهه هفتاد ميلادي دانشمندي از دانشگاه ميشيگان به نام جان هلند ايده اصلی استفاده از الگوريتم ژنتيك را در بهينهسازيهاي مهندسي مطرح كرد
در سال 1992 John Koza از ژنتيک الگوريتم در برنامه اي استفاده کرد که کارهاي مشخصي انجام مي داد Koza نام اين روش را Genetic Programming (GP) گذاشت .

اسلاید 6 :

تعاریف
الگوريتم ژنتيک (يا GA) يک تکنيک برنامه نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده ميکند.
ژن : به هر خصوصیت ژنتیکی یک ژن گفته می شود مثل رنگ چشم، طول قد، رنگ مو و .
کروموزوم : به مجموعه ژنها که شامل اطلاعات ژنتیکی میباشد گفته میشود.
جمعیت (colony): به مجموعه کروموزومها گفته میشود.
تابع تناسب ) : ( Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد

اسلاید 7 :

مراحل الگوریتم ژنتیک
اصول كار الگوريتم ژنتيك به صورت روند زير ارائه مي گردد

گام 1 – كد گذاري
گام 2 – انتخاب تصادفي جمعيت اوليه از مجموعه پاسخ ها
گام 3 – محاسبه ميزان سازگاري گروه پاسخ با تابع هدف
( Fitness )
گام 4 – ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش)
گام 5 – تكرار مراحل سوم و چهارم تا هنگامي كه جواب نهايي همگرا گردد

اسلاید 8 :

روشهای نمایش ژنومها (کدکردن)
استفاده از رشته های باینری
کدکردن راه حل ها در آرايه اي از اعداد صحيح يا اعشاري
استفاده از يک رشته حروف،که هر حرف نمايش دهنده يک خصوصيت از راه حل است
برنامه نويسي ژنتيک (Genetic programming)

اسلاید 9 :

روشهای انتخاب

روش Elitist
روش Roulette
روش Scaling
روش Tournament

اسلاید 10 :

اپراتورهای ژنتیکی Crossover :
اپراتور Crossover با استفاده از دو رشته والد دو رشته فرزند بوجود می آورد.
برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود.
انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود
single-point crossover
Two-point crossover
Uniform crossover
برای تعیین محل بیتهای کپی شونده از یک رشته به نام Crossover Mask استفاده میشود.

اسلاید 11 :

Single-point crossover
یک نقطه تصادفی در طول رشته انتخاب میشود.
والدین در این نقطه به دوقسمت میشوند.
هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید.
Crossover Mask: 11111000000
Parents
Children

اسلاید 12 :

روشهای دیگر Crossover
Two-point crossover
Uniform crossover
Crossover Mask: 00111110000
Crossover Mask: 10011010011
بیتها بصورت یکنواخت از والدین انتخاب میشوند
Parents
Parents
Children
Children

اسلاید 13 :

اپراتورهای ژنتیکی Mutation :
اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد.
با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
معمولا mutation بعد از انجام crossover اعمال میشود.
Parent
Child

اسلاید 14 :

مثال
ما يک مربع 3*3 داريم که مي خواهيم اعدادي بين 1تا15 را در اين مربع قرار دهيم به طوري که جمع اعداد در هر سطرو ستون برابر 24 شود.

اسلاید 15 :

ادامه مثال
گام اول :کدگذاری با استفاده از روش باینری و چون اين اعداد مقادير بين 0تا15 دارند مي توان آنها را با 4 بيت يا ژن داده نمايش داد
گام دوم : ايجاد کردن يک نسل ابتدايي براي شروع کار است که شامل تعدادي ژنوم تصادفي است

اسلاید 16 :

ادامه مثال
گام 3 – محاسبه ميزان سازگاري گروه پاسخ با تابع هدف ( Fitness )
هرچقدر که اعداد ما به جواب نزديکتر باشند عدد تناسب بزرگتر خواهد شد.

اسلاید 17 :

ادامه مثال
گام 4 – ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش).
بهترين روش براي تابع انتخاب(Fitness) در اين مسئله روشي به نام رولت(Roulette) است.اول يک عدد تصادفي بين 0 وعدد تناسب نسل قبلي انتخاب مي شود. تابع انتخاب به صورت زير خواهد بود

اسلاید 18 :

مزايا
عمومي بودن
هزينه قابل قبول
قابل تفسير بودن جوابها
پيشنهاد چندين جواب به صورت همزمان
موازي بودن الگوريتم

اسلاید 19 :

معايب
عدم ضمانت همگرايي به جواب بهينه در زمان محدود
ضعف تئوري
نياز به تنظيم پارامترها
كند بودن

اسلاید 20 :

چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک
توپولوژي هاي شبکه هاي کامپيوتي توزيع شده.
بهينه سازي ساختار ملکولي شِميايي (شيمي)
مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna
مهندسي نرم افزار
بازي هاي کامپيوتري
مهندسي مواد
مهندسي سيستم
رباتيک(Robotics)
تشخيص الگوو استخراج داده(Data mining)
آموزش شبکه هاي عصبي مصنوعي
ياددهي رفتار به رباتها با GA .
يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک
درك زبان محاوره اي و يا خواندن متون