1
الگوریتم ژنتیک
الگوریتم ژنتیک
تهیه کنندگان :
استاد مربوطه :
2
مقدمه
محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی استفاده از این روش در بهینه سازی و حل مسائل، بسیار گسترش یافته است. الگوریتم ژنتیک یکی از زیر مجموعه های محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک یکی از زیر مجموعه های هوش مصنوعی می باشد.
الگوریتم ژنتیک را می توان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می کند .الگوریتم ژنتیک برروی یکسری از جواب های مساله، به امید بدست آوردن جوابهای بهتر، قانون بقای بهترین را اعمال می کند. در هر نسل به کمک فرآیند، انتخابی متناسب با ارزش جواب ها و تولیدمثل جوابهای انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده اند، تقریب های بهتری از جواب نهایی بدست می آید. این فرایند باعث می شود که نسلهای جدید با شرایط مساله سازگارتر باشد.
3
تاریخچه
در سال 1992 جان کورا( john koza ) از الگوریتم ژنتیک ( GA ) برای حل و بهینه سازی مسائل مهندسی پیشرفته استفاده کردو توانست برای اولین بار الگوریتم ژنتیک را به زبان کامپیوتر درآورد و برای آن یک زبان برنامه نویسی ابداع کند که به این روش برنامه نویسی ، برنامه نویسی ژنتیک ( GP ) گویند و نرم افزاری که توسط وی ابداع گردید هم اکنون نیز این نرم افزار کاربرد زیادی در حل مسائل مهندسی پیداکرده است .
تاریخچه بیولوژیکی
بدن هر موجود زنده ای زنده ای از سلول تشکیل یافته است و هر سلول هم از کروموزوم تشکیل شده است .کروموزومها نیز از رشته های DNA تشکیل یافته اند . کروموزومها هم از ژن تشکیل یافته اند و به هر بلوک DNA یک ژن می گویند و هر ژن نیز از یک پروتئین خاص و منحصر به فرد تشکیل یافته است . و به مجوعه از ژنها یک ( Genome ) می گویند .
4
ساختار الگوریتمهای ژنتیکی
به طور کلی الگوریتمهای ژنتیکی از اجزاء زیر تشکیل میشوند:
1- کروموزوم (Chromosome)
در الگوریتمهای ژنتیکی, هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راهحل ممکن برای مسئله مورد نظر است. خود کروموزومها (راه حلها) از تعداد ثابتی ژن (Gene) متغیر تشکیل میشوند. برای نمایش کروموزومها، معمولاً از کدگذاریهای دودویی (رشتههای بیتی) استفاده میشود.
2- جمعیت (Population)
مجموعهای از کروموزومها، یک جمعیت را تشکیل میدهند. با تاثیر عملگرهای ژنتیکی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشکیل میشود.
3- تابع برازندگی (Fitness Function)
به منظور حل هر مسئله با استفاده از الگوریتمهای ژنتیکی، ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم، این تابع عددی غیر منفی را برمیگرداند که نشان دهنده شایستگی آن کروموزوم است.
5
عملگرهای الگوریتم ژنتیک
در الگوریتمهای ژنتیکی، در طی مرحله تولید مثل ازعملگرهای ژنتیکی استفاده میشود. با تاثیر این عملگرها بر روی یک جمعیت، نسل بعدی آن جمعیت تولید میشود. عملگرهای انتخاب ، آمیزش و جهش معمولاً بیشترین کاربرد را در الگوریتمهای ژنتیکی دارند.
1- عملگر انتخاب (Selection ):
این عملگر از بین کروموزومهای موجود در یک جمعیت، تعدادی کروموزوم را برای تولید مثل انتخاب میکند. کروموزومهای برازندهتر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند.
6
عملگرهای الگوریتم ژنتیک
روش های انتخاب :
: Elitist Selection (انتخاب نخبگان)
مناسب ترین عضو هر اجتماع انتخاب می شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
نمونهبرداری به روش چرخ رولت : در این روش، به هر فرد قطعهای از یک چرخ رولت مدور اختصاص داده میشود. اندازه این قطعه متناسب با برازندگی آن فرد است. چرخ N بار چرخانده میشود که N تعداد افراد در جمعیت است. در هر چرخش، فرد زیر نشانگر چرخ انتخاب میشود و در مخزن والدین نسل بعد قرار میگیرد. این روش میتواند به صورت زیر پیادهسازی شود:
1- نرخ انتظار کل افراد جمعیت را جمع کنید و حاصل آن را T بنامید.
2- مراحل زیر را N بار تکرار کنید:
یک عدد تصادفی r بین 0 و T انتخاب کنید.
در میان افراد جمعیت بگردید و نرخهای انتظار( مقدار شایستگی) آنها را با هم جمع کنید تا این که مجموع بزرگتر یا مساوی r شود. فردی که نرخ انتظارش باعث بیشتر شدن جمع از این حد میشود، به عنوان فرد برگزیده انتخاب میشود.
نحوه ارزیابی شایستگی در چرخ رولت
7
عملگرهای الگوریتم ژنتیک
Tournament Selection (انتخاب تورنومنت) :
یک زیر مجموعه از صفات یک جامعه انتخاب می شوند و اعضای آن مجموعه با هم رقابت می کنند و سرانجام فقط یک صفت از هر زیر گروه برای تولید انتخاب می شوند.
2- عملگرآمیزش(Crossover ):
در جریان عمل آمیزش به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.
هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب می کنیم .
ژن های مابعد آن نقطه از کروموزوم ها را جابجا می کنیم .
8
عملگرهای الگوریتم ژنتیک
تلفیق تک نقطه ای (Single Point Crossover)
اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن برش تک نقطه ای می گویند.
تلفیق بدین صورت انجام می گیرد که حاصل ترکیب کروموزوم های پدر و مادر می باشد. روش تولید مثل نیز بدین صورت است که ابتدا بصورت تصادفی ، نقطه ای که قرار است تولید مثل از آنجا آغاز گردد، انتخاب می شود. سپس اعداد بعد از آن به ترتیب از بیت های کروموزوم های پدر و مادر قرار می گیرد که در شکل زیر نیز نشان داده شده است.
در شکل بالا کروموزوم های 1 و2 در نقش والدین هستند. و حاصل تولید مثل آنها در رشته هائی بنام Offspring ذخیره شده است. دقت شود که علامت "|" مربوط به نقطه شروع تولید مثل می باشد و در رشته های Offspring اعدادی که بعد از نقطه شروع تولید مثل قرار می گیرند مربوط به کروموزومهای مربوط به خود می باشند. بطوریکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کروموزوم 1 و اعداد بعد از نقطه شروع تولید مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع تولید مثل مربوط به کروموزوم 2 می باشند.
9
عملگرهای الگوریتم ژنتیک
روش ادغام دو نقطه ای((Two-point CrossOver :
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
تلفیق نقطه ای (Multipoint Crossover) :
می توانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطه ای می گویند.
تلفیق جامع (Uniform Crossover) :
اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع می گوئیم. مثال)
10
عملگرهای الگوریتم ژنتیک
عملگر جهش (Mutation ):
پس از اتمام عمل آمیزش، عملگر جهش بر روی کروموزومها اثر داده میشود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر میدهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل میکند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار میدهد. پس از اتمام عمل جهش، کروموزومهای تولید شده به عنوان نسل جدید شناخته شده و برای دور بعد اجرای الگوریتم ارسال میشوند.
11
عملگرهای الگوریتم ژنتیک
روند کلی الگوریتمهای ژنتیکی
قبل از این که یک الگوریتم ژنتیکی بتواند اجرا شود، ابتدا باید کدگذاری (یا نمایش) مناسبی برای مسئله مورد نظر پیدا شود. معمولی ترین شیوه نمایش کروموزومها در الگوریتم ژنتیک به شکل رشته های دودویی است. هر متغیر تصمیم گیری به صورت دودویی در آمده و سپس با کنار هم قرار گرفتن این متغیرها کروموزوم ایجاد میشود .گرچه این روش گسترده ترین شیوه کدگذاری است اما شیوه های دیگری مثل نمایش با اعداد حقیقی در حال گسترش هستند. همچنین یک تابع برازندگی نیز باید ابداع شود تا به هر راه حل کدگذاری شده ارزشی را نسبت دهد. در طی اجرا، والدین برای تولید مثل انتخاب میشوند و با استفاده از عملگرهای آمیزش و جهش با هم ترکیب میشوند تا فرزندان جدیدی تولید کنند. این فرآیند چندین بار تکرار میشود تا نسل بعدی جمعیت تولید شود. سپس این جمعیت بررسی میشود و در صورتی که ضوابط همگرایی رآورده شوند, فرآیند فوق خاتمه مییابد.
12
کد برنامه مجازی الگوریتم ژنتیک ساده
13
فلوچارت الگوریتم ژنتیک ساده
فلوچارت برنامه مجازی الگوریتم ژنتیک ساده
14
روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک :
شروع(Start ) : تولید تصادفی یک جمعیت(Population ) که شامل تعداد زیادی کروموزم(روشهای حل مسئله است) می باشد.
صحت و درستی(Fitness ): ارزیابی صحت برای تابع f(x) به ازائ هر کروموزوم x درجمعیت.
روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک
نحوه ارزیابی تابع شایستگی در چرخ رولت
15
ایجاد یک جمعیت جدید(New Population ): تولید یک جمعیت جدید با انجام تمامی زیر گروههای زیر تا آنکه یک جمعیت جدید ایجاد گردد.
انتخاب(Selection ):انتخاب کروموزومهای پدر و مادر از جمعیت قبلی با توجه به صحت و درستی آن (Fitness ). بطوریکه هر چه Fitnees بهتر باشد (دقت جواب در همگرائی بیشتر باشد) شانس بیشتری برای انتخاب دارد.
تولید مثل(Crossover ): انجام زادو ولد و ایجاد یک نسل جدید.
جهش(Mutation ): مشخص شدن مکان فرزند تولید شده در کروموزوم
پذیرش(Accepting ): جا دادن فرزند جدید در داخل جمعیت.
جایگزینی(Replace ): جایگزینی جمعیت جدید به جای جمعیت قبلی و مورد استفاده قرار دادن جمعیت جدید در مراحل بعدی الگوریتم
امتحان: (Test ): اگر شرائط مطلوب در حل مسئله ارضا شد اعلام میکنیم که به بهترین جواب رسیده ایم و از الگوریتم خارج می شویم در غیر این صورت به مرحله 2 یعنی Fitneess میرویم و دوباره همین روند را تکرار می کنیم.
روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک
16
شرط پایان الگوریتم
چون الگوریتم های ژنتیک بر پایه تولید و تست می باشند، جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیارهای دیگری را برای شرط خاتمه در نظر می گیریم:
1- تعداد مشخصی نسل: می توانیم شرط خاتمه را مثلاً 100 دور چرخش حلقه اصلی برنامه قرار دهیم.
2- عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالی
3- بهترین شایستگی جمعیت تا یک زمان خاصی تغییری نکند.
شرایط دیگری نیز می توانیم تعریف کنیم و همچنین می توانیم ترکیبی از موارد فوق را به عنوان شرط خاتمه به کار ببندیم.
شرط پایان الگوریتم
17
یک مثال ساده:
ما یک مربع 3*3 داریم که می خواهیم اعدادی بین 1تا15 را در این مربع قرار دهیم به طوری که جمع اعداد در هر سطرو ستون برابر 24 شود.
یک مثال ساده
این مسئله تا حدودی پیچیده است. ممکن است یک انسان بتواند آن را در مدت زمانی مشخص حل کند ولی هیچ گاه یک کامپیوتر نخواهد توانست آن را در مدت زمان کوتاهی با استفاده از اعداد تصادفی حل کند. ولی الگوریتم ژنتیک می تواند این مشکل را حل کند.
18
نسل اول
اولین گام ایجاد کردن یک نسل ابتدایی برای شروع کار است که شامل تعدادی ژنوم تصادفی است. این ژنوم ها به صورت باینری(0و1) نشان داده می شوند. اول یکسری عدد به صورت تصادفی تولید می شوند. هر ژنوم یا کروموزوم شامل اطلاعاتی برای هر 9 جای خالی است .چون این اعداد مقادیر بین 0تا15 دارند می توان آنها را با 4 بیت یا ژن داده نمایش داد. پس هر ژنوم شامل 36 بیت است.
یک نمونه ژنوم می تواند به شکل زیر باشد:
یک مثال ساده
حالاباید به هر ژنوم در مجموعه یک عدد تناسب(Fitness) بنابر تاثیر آن در حل مسئله نسبت داد. فرآیند وروش محاسبه این عدد برای هر مسئله فرق می کند.انتخاب الگوی مناسب برای مسئله مشکلترین و حساسترین بخش در حل مسئله ژنتیک است. دراین مثال ما اعداد را در مکان هایشان جایگذاری می کنیم و بررسی می کنیم که چقدر با جواب اصلی فاصله دارند.
19
مقادیر معادل عبارتند از 33و25و26و24و21و39. واضح است که این مقادیر مسئله را حل نمی کنند. پس باید مقادیر تناسب را برای این ژنوم محاسبه کرد. برای این کار ابتدا فاصله هرمجموع را از 24 محاسبه کرده، سپس معکوس مجموع تفاضل آنها را محاسبه می کنیم .
یک مثال ساده
20
بنابراین درجه تناسب برای این ژنوم تقریباً برابر 0.033 است. هرچقدر که اعداد ما به جواب نزدیکتر باشند عدد تناسب بزرگتر خواهد شد. اما اگر مخرج ما برابر 0شود چه اتفاقی می افتد؟ دراین صورت همه اعداد ما برابر 24 شده اند وما به جواب رسیده ایم.
یک مثال ساده
21
نسل بعدی: دو ژنوم (کروموزوم) به طور تصادفی برای تولید نسل بعدی انتخاب می شوند. این اصلی ترین بخش الگوریتم ژنتیک است
که از 3 مرحله تشکیل شده:
1- انتخاب
دو ژنوم به طور تصادفی از نسل قبل انتخاب می شوند.این ژنوم ها دارای اعداد تناسب بزرگتری هستند و بعضی صفات آنها به نسل بعدی منتقل می شوند. این بدین معنی است که عدد تناسب در حال افزایش خواهد بود.
بهترین روش برای تابع انتخاب(Fitness) در این مسئله روشی به نام رولت(Roulette) است. اول یک عدد تصادفی بین 0 وعدد تناسب نسل قبلی انتخاب می شود.
یک مثال ساده
22
تلفیق(Crossover)
حالا دو ژنوم بخشی از ژنهایشان را برای ایجاد نسل بعدی اهدا می کنند. اگر آنها تغییر پیدا نکنند همانطور بی تغییر به نسل بعدی منتقل خواهند شد.درجه Crossover نشان دهنده این است که هر چند وقت یکبار ژنوم ها تغییر پیدا خواهند کرد و این عدد باید در حدود 65-85% باشد.
عملگر تغییر در ژنوم های باینری مثال ما با انتخاب یک مکان تصادفی در ژنوم برای تغییر آغاز می شود. بخش اول ژنهای پدر و بخش دوم ژنهای مادر با هم ترکیب می شوند(و بالعکس) تا2 فرزند تولید شوند. در زیریک عمل تغییر را می بینیم.
یک مثال ساده
23
جهش(Mutation)
قبل از این که ژنوم ها در نسل بعدی قرار بگیرند،احتمال دارد دچار جهش یا تغییر ناگهانی شوند شوند.جهش یک تغییر ناگهانی در ژن است. در ژنهای باینری این تغییر به معنای تغییر یک بیت از 0به 1 یا از 1 به 0 است. درجه جهش نشان دهنده احتمال بروز جهش در یک ژن است و تقریباً بین 1-5% برای ژنهای باینری و 5-20%برای ژنهای عددی است.
این روند تا تولید نسل های متعددی ادامه می یابد تا در نهایت به جواب برسیم.
یک مثال ساده
24
برخی از کاربرد الگوریتمهای ژنتیکی
توپولوژی های شبکه های کامپیوتی توزیع شده.
بهینه سازی ساختار ملکولی شِمیایی (شیمی)
مهندسی برق برای ساخت آنتنهای Crooked-Wire Genetic Antenna
مهندسی نرم افزار
بازی های کامپیوتری
مهندسی مواد
مهندسی سیستم
رباتیک (Robotics)
تشخیص الگوو استخراج داده (Data mining)
حل مسئله فروشنده دوره گرد
آموزش شبکه های عصبی مصنوعی
یاددهی رفتار به رباتها با GA .
یادگیری قوانین فازی با استفاده از الگویتم های ژنتیک.
برخی از کاربرد الگوریتمهای ژنتیکی
25
26
ازتوجه شما سپاسگزارم