در توسینسو تدریس کنید

و

با دانش خود درآمد کسب کنید

الگوریتم ژنتیک چیست ؟ معرفی Genetic Algorithm قسمت 2

بسم رب الحسین ، با سلام خدمت دوستان عزیز ITPRO ، سری قبل الگوریتم ژنتیک رو معرفی کردیم و با پارامترهای مورد نیاز آشنا شدیم . در این قسمت میخوام با یک مثال به توضیح بیتر این الگوریتم بپردازم :

صورت سوال : پیدا کردن مقدار بیشینه تابع زیر با دو متغیر (دو بعدی)


معرفی الگوریتم ژنتیک - قسمت دوم

برای شروع کار باید تابع محاسبه Fitness ( برازندگی ) را مشخص کنیم که در اینجا همان تابع صورت سوال میباشد . چرا که هدف بیشینه سازی این تابع میشد و مقدار آن مشخص کننده جواب مساله است .مرحله بعد مشخص کردن تعداد بیتهای مورد نیاز برای ساختن کروموزوم هاست . از فرمول زیر تعدا بیتها برای یک متغیر مشخص میشود و در نهایت طول کروموزوم برابر است با حاصل این فرمول ضرب در ابعاد مساله :

bitOfPerX=((max-min))*10000;
bitOfPerX=ceil(log2(bitOfPerX));
bitNum=bitOfPerX*n;

max و min : حد بالا و پایین شرایط مساله هستند .10000 : دقت مساله را مشخص میکند . (تا چهار رقم اعشار) یعنی برای هر متغیر به 17 بیت نیاز است و در مجموع برای ایجاد یک کروموزوم دو متغیره به 34 بیت . حال باید جمعیت اولیه را ایجاد کنیم . برای این کار از اعداد Random استفاده میکنیم :

v=round(unifrnd(0,1,[10 bitNum]));

ماتریس جمعیت ما است که با این دستور یک ماتریس 34*10 ایجاد شده . یعنی 10 کروموزوم 34 بیتی v خب تا اینجا مراحل اولیه انجام شده حالا باید کروموزوم ها برای انتخاب ، آمیزش و جهش وارد حلقه اصلی برنامه شوند . میزان اجرای الوریتم یک امر تجربی است من برای این برنامه الگوریتم را هزار بار اجرا کردم . حال باید مقادیر reeal این متغیر ها را پیدا کنیم برای این کار از فرمول زیر استفاده میکنیم :

vx= min + decimal(substring) * ( max-min)/(2^bitNum-1)

مقدار متغیر ها برای مرحله اول :

معرفی الگوریتم ژنتیک - قسمت دوم

بعد از محاسبه x ها باید مقدار برازندگی هر یک را مشخص کنیم . یعنی با ازای هر کروموزوم که شامل دو متغیر است مقدار تابع را مشخص میکنیم

13.1888- 12.1669- 8.8400- 15.3479- 7.6979- 12.2653- 11.6437- 6.5262- 11.3858- 12.4907-

در مقاله قبلی برای انتخاب چرخه رولت را معرفی کردیم اما اینجا از روشی به نام Tournament Selection استفاده میکنیم . به این شکل که دو کروموزوم به تصادف انتخاب شده و یکی از آنها برای مرحله بعد انتخاب میشود . با شروع برنامه جمعیت اولیه 10 میباشد و از بین این ده تا ده کروموزوم انتخاب میشود اما در مراحل بعدی که فرزندان به جمعیت اضافه میشوند انتخاب از بین کروموزوم های بیشتری صورت میگردد و 10 تا انتخاب میشوند .بعد از انتخاب 10 کروموزوم نوبت Crossover است . برای این کار یک نرخ آمیزش انتخاب میکنیم . مثلا در این مثال من 0.35 را انتخاب کردم و به ازای هر کروموزوم یک عدد تصادفی بین 0 و 1 تولید میکنیم اگر عدد کوچکتر از نرخ آمیزش بود کروموزوم برای آمیزش انتخاب میشود . در نهایت از هر زوج والد انتخاب شده دو فرزند تولید شده و به جمعیت اضافه میشوند .برای آمیزش روشهای مختلفی وجود دارد در اینجا از Uniform Crossover استفاده کردیم به این شکل که یک بردار تصادفی با اعداد صفر و یک به اندازه طول کروموزوم ایجاد کرده (Crossover Mask) و هر بیتی از این بردار که صفر بود جای بیتهای متناظر آن در والدین با هم جابجا میشوند . به مثال زیر توجه کنید :

معرفی الگوریتم ژنتیک - قسمت دوم

بعد از اتمام آمیزش نوبت جهش است . برای این کار هم یک نرخ جهش انتخاب میکنیم برای این مثال مقدار 0.03 انتخاب کردم . سپس به ازای تمام بیتهای موجود عددی تصادفی تولید میکنیم و اگر مقدار عدد تصادفی کمتر از نرخ بود بیت متناظر را در جمعیت معکوس میکنیم . در این مثال مجموعا 340 = 34*10 بیت (ژن) داریم و باید 340 عدد تصادفی تولید کنیم . مثلا اگر عدد تصادفی بیت 12 شد 0.02 باید مقدار بیت 12 را معکوس کنیم .بعد از جهش دوباره به اول حلقه برگشته . یعنی محاسبه x و سپس برازندگی و بعد انتخاب و چون تعدادی فرزند به جمعیت اضافه شده صدرصد انتخاب در بین بیش از ده کروموزوم صورت میگیرد . در نهایت برای 5بار اجرای مستقل و 1000بار اجرای الگوریتم جوابها به این شکل شد :

معرفی الگوریتم ژنتیک - قسمت دوم

همانطور که میبینیم هر 5 اجرا جوابهایی با دقت بالا ایجاد کردند .

#آشنایی_با_الگوریتم_ژنتیک #پیاده_سازی_الگوریتم_ژنتیک #حل_تمرین_طراحی_الگوریتم #مفاهیم_الگوریتم_ژنتیک #معرفی_الگوریتم_ژنتیک #آموزش_تصویری_طراحی_الگوریتم #الگوریتم_ژنتیک_چیست #الگوریتم_ژنتیک
عنوان
1 الگوریتم ژنتیک چیست ؟ معرفی Genetic Algorithm قسمت 1 رایگان
2 الگوریتم ژنتیک چیست ؟ معرفی Genetic Algorithm قسمت 2 رایگان
زمان و قیمت کل 0″ 0
0 نظر

هیچ نظری ارسال نشده است! اولین نظر برای این مطلب را شما ارسال کنید...

نظر شما
برای ارسال نظر باید وارد شوید.
از سرتاسر توسینسو
تنظیمات حریم خصوصی
تائید صرفنظر
×

تو می تونی بهترین نتیجه رو تضمینی با بهترین های ایران بدست بیاری ، پس مقایسه کن و بعد خرید کن : فقط توی جشنواره تابستانه می تونی امروز ارزونتر از فردا خرید کنی ....