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

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

اسلاید 1 :

الگوريتم هاي ژنتيك

اسلاید 2 :

مروري بر مطالب
مقدمه و تاريخچه
روند الگوريتمهاي ژنتيك
مزايا و معايب الگوريتمهاي ژنتيك
پارامترهاي كنترل
حل TSP با استفاده از GA
جمعبندي

اسلاید 3 :

مقدمه و تاريخچه
GA بعنوان دستهاي از الگوريتمهاي تكاملي
ابداع توسط آقاي John Holland در سال 1975 در ميشيگان
شبيهسازي روند GA بر اساس روند تكاملي طبيعت
پايهگذاري بر اساس نظريه آقاي چارلز داروين
روشي براي جستجو در فضاهاي بزرگ
كاربرد در مسائل بهينهسازي

اسلاید 4 :

مقدمه:

الگوریتم ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کند.

الگوریتم ژنتیک یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند.

الگوریتم ژنتیک برای مسائل جستجو و بهینه سازی بکار برده می شود.

هنگامی كه لغت تنازع بقا به كار میرود اغلب بار ارزشی منفی آن به ذهن میآید. شاید همزمان قانون جنگل به ذهن برسد و حكم بقای قویتر!

طبیعت مناسب ترینها (Fittest) را انتخاب می كند نه بهترینها.

اسلاید 5 :

قانون انتخاب طبیعی:

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

طبیعت با بهره گیری از یك روش بسیار ساده(حذف تدریجی گونههای نامناسب و در عین حال تكثیر بالاتر گونه های بهینه) توانسته است دائما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد. البته این روش به تنهایی برای رسیدن به تکامل کافی نیست(حد اقل در مورد آنچه که در طبیعت وجود دارد). وجود فرآیندی به نام "جهش (Mutation)" نیز لازم است.

اسلاید 6 :

الگوریتم های ژنتیک و تنازع بقا :
قانون انتخاب طبیعی :
تنها گونه هایی از یک جمعیت ادامه نسل می دهند که بهترین خصوصیت را داشته باشند.

تکامل طبیعی :
جستجوی کورکورانه (تصادف)+بقای قوی تر

اسلاید 7 :

الگوریتم های ژنتیک با توجه به نظریه داروین در مورد تکامل جان گرفتند.

اسلاید 8 :

مقایسه روش های کلاسیک ریاضیات با الگوریتم ژنتیک:

روشهای كلاسیك ریاضیات دارای دو اشكال اساسی هستند:

اغلب این روشها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه كلی در نظر می گیرند
روشهای ریاضی بهینهسازی اغلب منجر به یك فرمول یا دستورالعمل خاص برای حل هر مسئله میشوند. در حالی كه روشهای هوشمند دستورالعملهایی هستند كه به صورت كلی میتوانند در حل هر مسئلهای به كار گرفته شوند. این نكته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.

اسلاید 10 :

معرفی اجمالی GA:
از الگوریتم ژنتیک در مسائل جستجو و بهینه سازی استفاده می گردد.
ابتدا یک نسل اولیه ایجاد می گردد(بصورت تصادفی) که در واقع کروموزوم های اولیه هستند. هر یک از این کروموزوم ها جوابی(به عبارت صحیح تر شبه جواب) برای مسئله هستند.
اما جواب اصلی که ما به دنبال آن هستیم نیستند. سپس پدیده جهش(با احتمال خیلی کم) ممکن است رخ دهد. در نهایت کروموزموم ها از نظر امتیاز رتبه بندی می گردند(انتخاب تابعی مناسب برای تعیین امتیاز بسیار مهم است).

اسلاید 11 :

ادامه الگوریتم
برخی کروموزوم ها با هم ترکیب شده و نسل بعد را بوجود می آورند(احتمال انتخاب کروموزوم های با امتیاز بالاتر، بیشتر است، اما در عین حال احتمال انتخاب شدن برای تمام کروموزوم ها،حتی کرموزوم های با کمترین امتیاز، وجود دارد.).
نسل بوجود آمده به کروموزوم های قبلی اضافه می شود و فرآیند دوباره تکرار می شود. این مراحل آنقدر تکرار می شود که در کروموزوم های تولید شده کروموزومی وجود داشته باشد که جواب مسئله(مینیمم یا ماکزیمم) باشد.

اسلاید 12 :

الگوریتم ژنتیک :
1 – شروع الگوریتم با یک جمعیت متشکل از n فرد تصادفی که هر کدام کروموزمی به طول L دارند.
2 – محاسبه Fitness برای هر فرد.
3 – انتخاب دو فرد براساس بالاتر بودن Fitness .
4 – اعمال Crossover و تولد بچه ها از والدین.
5 – اعمال Mutation با احتمال P برای هر بیت.
6 – قرار دادن بچه های متولد شده داخل یک مجموعه ، به عنوان نسل جدید.
7 – تغییر دادن جمعیت اولیه همراه ورود نسل جدید .
8 – رفتن به گام 2 .

اسلاید 13 :

Population
(Chromosomes)
روند اجرايي الگوريتم هاي ژنتيك

اسلاید 14 :

توليد جمعيت اوليه
اولين گام در پيادهسازي هر الگوريتم ژنتيكي
جمعيتي از كروموزومها
هر كروموزوم بيانگر يك جواب براي مسئله
نمايش هر كروموزوم بصورت يك رشته بطول L
ايجاد كروموزومها بصورت نمونههاي تصادفي از فضاي جستجو

اسلاید 15 :

Population
(Chromosomes)

اسلاید 16 :

Binary Encoding
Permutation Encoding
Value Encoding
Tree Encoding
روشهاي انكدينگ مسئله( Encoding )

اسلاید 17 :

Binary Encoding
متداولترين روش بدليل سادگي
كروموزومها بصورت مجموعهاي از 0 و 1
انكدينگ مسئله كولهپشتي ماكزيمم با اين روش
نمونهاي از كروموزومهاي توليدي

اسلاید 18 :

Permutation Encoding
كاربرد براي مسائلي كه جواب در آنها ترتيبي از اشيا است
مكان قرار گرفتن هر شي مهم است
انكدينگ فروشنده دورهگرد ( TSP )
نمونهاي از كروموزومهاي توليدي

اسلاید 19 :

Population
(Chromosomes)
Evaluation
(fitness)

اسلاید 20 :

يكتا بودن تابع ارزيابي براي هر مسئله
بررسي هر كروموزوم
توجه به محدوديتهاي موجود در مسئله
نسبت دادن يك مقدار به هر كروموزوم با نام برازندگي (Fitness)
Fitness = ميزان خوبي يك كروموزوم
Fitness = فاصله باقيمانده تا جواب نهايي
ارزيابي Evaluation) )