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

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

اسلاید 1: Genetik algoritmالگوریتم ژنتیک

اسلاید 2: یکی از زیر شاخه های SOFT COMPITING الگوریتم ژنتیک GA است که تکامل طبیعی موجودات را الگو قرار می دهد.ؤنتیک الگوریتم از جمله روشهایی هستند که برای حل مسایل NP به کار می روند. آنها الگوریتم های تصادفی هستند که بر اساس پدیده طبیعی وراثت ژنتیک عمل می کنند.الگوریتم مبتنی بر تکرار است و اصول اولیه آن از عم ژنتیک اقتباس گردیده است.در مسایل متنوعی نظیر بهینه سازی ، شناسایی و کنترل سیستم ، پردازش تصویر و مسایل ترکیبی و آزمایش شبکه عصبی به کار می رود.الگوریتم ژنتیک چیست ؟

اسلاید 3: ساختار الگوریتم1- این الگوریتم با رشته بیتی کار می کند.2- در هر تکرار چند نقطه از فضای جستجو را در نظر می گیرد.نکات مهم :شرایط جمعیت در رسیدن به جواب بسیار تأثیر گذار است. با توجه به پارامترهای تصادفی حتی در صورت استفاده جمعیت اولیه یکسان ممکن است جوابها یکسان نباشد.تابع ارزش در این الگوریتم اهمیت زیادی دارد.

اسلاید 4: فناوری الگوریتماین الگوریتم روش قدرتمندی را برای توسعه اکتشافی مسائل بهینه سازی ترکیبی مقیاس بزرگ فراهم آورده است. الگوریتم ژنتیک مسئله را به صورت مجموعه ای از رشته ها که شامل ذرات ریز هستند کدگذاری می کند ، پس برای تحریک فرایند تکامل تدریجی تغییراتی را بر روی رشته ها اعمال می دارد.

اسلاید 5: الگوریتم ژنتیک در دنیای کامپیوترجهت استفاده در برنامه ها ابتدا باید راه حل بیابید تا حالات جواب مسئله خود را به صورت کد شده در قالب رشته ای از اعداد صحیح یا به صورت رشته ای از بیت ها نشان دهید مثل 0111011001 مثال :

اسلاید 6: شرایط خاتمه الگوریتمبه تعداد ثابتی از نسل ها برسیمبودجه اختصاصی (پول/زمان) تمام شود.یک فرد (فرزند پیدا شود که کمترین ملاک را برآورده کند.نتایج بهتری حاصل شود.

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

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

اسلاید 9: همان گونه که در شکل پیداست این الگوریتم سه بخش اساسی دارد که عبارتند از الگوریتم کلونی مورچگان ،الگوریتم ژنتیک و قسمت تبادل جوابها.

اسلاید 10: تبادل جوابهاساختار الگوریتم ترکیبی به گونه ای طراحی شده است که هر دو الگوریتم به صورت موازی به حل مسئله می پردازد تا به شرط توقف که با loop نشان داده شده است ، برسند. در این زمان الگوریتم مورچگان به تعداد m مورچه و الگوریتم ژنتیک به تعدا M جواب اولیه ایجاد کرده اند و به مقدار EC% از جوابها بین دو الگوریتم مبادله می شوند.پس از مبادله جوابها عمل تطبیق جوابها در دو الگوریتم صورت می گیرد، بدین صورت که جوابهای الگوریتم مورچگان وارد نسل جاری جمعیت الگوریتم ژنتیک شده و جوابهای الگوریتم ژنتیک وارد مرحله قبل از فرومون ریزی کلی می شوند.پس از این مرحله الگوریتم مجددا حل مسئله فروشنده دوره گرد را ادامه می دهد تا به شرط توقف برسد.

اسلاید 11:

اسلاید 12:

اسلاید 13: نمایی کلی از روش GAهمان طور که دیدید در هر نسل به تعداد نسل قبل ما فرزند خواهیم داشت.این فرزندان از طریق روشOver Cross ایجاد می شوند.در این روش مکان مورد نظر به طور random انتخاب می شود.ولی تعداد Chromosome هایی که در cross over شرکت می کنند بر اساس یک احتمال(Cross Over Rate) 0.6<Pc<0.7انتخاب می شوند.در اینجا چند روش معروف Cross Over را نشان میدهیم:روش ادغام تک نقطه ای(Single-Sight Cross Over)روش ادغام دو نقطه ای(Two-point Cross Over)روش ادغام چند نقطه ای(Multi-point Cross Over)

اسلاید 14: روش ادغام تک نقطه ای(Single-Sight Cross Over)در این روش یک مکان تصادفی در طول رشته انتخاب می شود و gene ها از این مکان به بعد جابجا میشوند.

اسلاید 15: روش ادغام دو نقطه ای((Two-point Cross Overدر این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.روش ادغام چند نقطه ای(Multi-point Cross Over)

اسلاید 16: شبه کد

اسلاید 17: آخرین نکات!این نکته بسیار مهم است که همیشه مقدار میانگین Fitness از نسلی به نسل بعد یا ثابت می ماند یا افزایش میابد و نهایت به یک عدد همگرا می شود و حول آن عدد با میزان واریانس کمی نوسان می کند!توجه به فاکتورهای اساسی که در پیاده سازی GA مهم است:نحوه نمایش.اندازه ی جمعیت و نرخ جهش.روشهای انتخاب و حذف.عملگرهای ادغام و جهش.شرط خاتمه.

اسلاید 18: مزایای GAفهم آسان.مجزا بودن.پشتیبانی از بهینه سازی چند تابعی.مناسب برای محیط های نویزی.همیشه یک جواب داریم که با گذشت زمان بهتر می شود.امکان استفاده به صورت موازی.روشهای مختلفی برای افزایش سرعت و پیشرفت الگوریتم وجود دارد.بهره برداری ساده از جواب قبلی.انعطاف پذیر برای کاریرد های ترکیبی.

اسلاید 19: پایان