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

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

اسلاید 1 :

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

اسلاید 2 :

الگوریتم ژنتیک
الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است.
این روش در سال 1970 توسط John Holland معرفی گردید
این روشها با نام Evolutionary Algorithms نیز خوانده میشوند.

اسلاید 3 :

ایده کلی
یک GA برای حل یک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند.
هر یک از این راه حلها با استفاده از یک “ تابع تناسب” مورد ارزیابی قرار میگیرد.
آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی میشوند. که اینکار باعث تکامل راه حلها میگردد.
بدین ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب برسد
در صورت انتخاب صحیح پارامترها، این روش میتواند بسیار موثر عمل نماید.

اسلاید 4 :

فضای فرضیه
الگوریتم ژنتیک بجای جستجوی فرضیه های general-to specific و یا simple to complex فرضیه ها ی جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد.
در هرمرحله مجموعه ای از فرضیه ها که جمعیت (population) نامیده میشوند از طریق جایگزینی بخشی از جمعیت فعلی با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست میآید.

اسلاید 5 :

ویژگیها
الگوریتم های ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند بکار گرفته شود.
همچنین در مسایلی با فضای فرضیه پیچیده که تاثیر اجزا آن در فرضیه کلی ناشناخته باشند میتوان از GA برای جستجو استفاده نمود.
برای discrete optimizationبسیار مورد استفاده قرار میگیرد.
الگوریتم های ژنتیک را میتوان براحتی بصورت موازی اجرا نمود از اینرو میتوان کامپیوترهای ارزان قیمت تری را بصورت موازی مورد استفاده قرار داد.
امکان به تله افتادن این الگوریتم در مینیمم محلی کمتر از سایر روشهاست.
از لحاظ محاسباتی پرهزینه هستند.
تضمینی برای رسیدن به جواب بهینه وجود ندارد.

اسلاید 6 :

Parallelization of Genetic Programming
در سال 1999 شرکت Genetic Programming Inc. یک کامپیوتر موازی با 1000 گره هر یک شامل کامپیوتر های P2, 350 MHZ برای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد.

اسلاید 7 :

کاربر دها
کاربرد الگوریتم های ژنتیک بسیار زیاد میباشد
optimization,
automatic programming,
machine learning,
economics,
operations research,
ecology,
studies of evolution and learning, and
social systems

اسلاید 8 :

زیر شاخه های EA
روش های EA به دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند:
Genetic Algorithms (GAs)
در این روش راه حل یک مسئله بصورت یک bit string نشان داده میشود.
Genetic Programming (GP)
این روش به تولید expression trees که در زبانهای برنامه نویسی مثل lisp مورد استفاده هستند میپردازد بدین ترتیب میتوان برنامه هائی ساخت که قابل اجرا باشند.

اسلاید 9 :

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

اسلاید 10 :

پارامترهای GA
یک الگوریتم GA دارای پارامترهای زیر است:
GA(Fitness,Fitness_threshold,p,r,m)
: Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد
: Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
: p تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
:r در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند
:m نرخ mutation

اسلاید 11 :

الگورتیم
: Initializeجمعیت را با تعداد p فرضیه بطور تصادفی مقدار دهی اولیه کنید.
: Evaluateبرای هر فرضیه h در p مقدار تابع Fitness(h) را محاسبه نمائید.
تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد کنید.
فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.

اسلاید 12 :

مراحل ایجاد یک جمعیت جدید بصورت زیر است:
: selectتعداد(1-r)p فرضیه از میان P انتخاب و بهPs اضافه کنید. احتمال انتخاب یک فرضیهhi از میانP عبارت است از:

P(hi) = Fitness (hi) / Σj Fitness (hj)



: Crossoverبا استفاده از احتمال بدست آمده توسط رابطه فوق، تعداد(rp)/2 زوج فرضیه از میان P انتخاب و با استفاده از اپراتورCrossover دو فرزند از آنان ایجاد کنید. فرزندان را به Ps اضافه کنید.
: Mutateتعداد m درصد از اعضا Ps را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید
P Ps :Update
برای هر فرضیه h در P مقدار تابع Fitness را محاسبه کنید
نحوه ایجاد جمعیت جدید
هر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد.

اسلاید 13 :

نمایش فرضیه ها
در الگوریتم ژنتیک معمولا فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد.
: Phenotype به مقادیر یا راه حلهای واقعی گفته میشود.
: Genotypeبه مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده GA قرار میگیرند.
باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست آورده شود.

اسلاید 14 :

مثال: نمایش قوانین If-then rules
برای نمایش مقادیر یک ویژگی نظیر Outlook که دارای سه مقدار Sunny, Overcast ,Rain است میتوان از رشته ای با طول 3 بیت استفاده نمود
100 -> Outlook = Sunny
011-> Outlook = Overcast  Rain
برای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم:


به همین ترتیب کل یک قانون if- then را میتوان با پشت سر هم قرار دادن بیت های قسمت های شرط و نتیجه ایجاد نمود:
Outlook Wind
011 10
IF Wind = Strong THEN PlayTennis = No
Outlook WindPlayTennis
111 10 0
 bit string: 11110

اسلاید 15 :

نمایش فرضیه ها: ملاحظات
ممکن است ترکیب بعضی از بیت ها منجر به فرضیه های بی معنی گردد. برای پرهیز از چنین وضعیتی:
میتوان از روش انکدینگ دیگری استفاده نمود.
اپراتورهای ژنتیکی را طوری تعیین نمود که چنین حالتهائی را حذف نمایند
میتوان به این فرضیه ها مقدار fitness خیلی کمی نسبت داد.

اسلاید 16 :

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

اسلاید 17 :

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

اسلاید 18 :

روشهای دیگر Crossover
Two-point crossover

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

اسلاید 19 :

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

اسلاید 20 :

این سوال ها سالها مطرح بوده است:
کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟

پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده:
بستگی به صورت مسئله دارد
در حالت کلی بهتر است از هر دو استفاده شود
هر کدام نقش مخصوص خود را دارد
میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover استفاده کند کار نخواهد کرد