تا %60 تخفیف خرید برای 5 نفر با صدور مدرک فقط تا
00 00 00
در توسینسو تدریس کنید

الگوریتم ژنتیک چیست ؟ معرفی 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 اجرا جوابهایی با دقت بالا ایجاد کردند .

#آشنایی_با_الگوریتم_ژنتیک #پیاده_سازی_الگوریتم_ژنتیک #حل_تمرین_طراحی_الگوریتم #مفاهیم_الگوریتم_ژنتیک #معرفی_الگوریتم_ژنتیک #آموزش_تصویری_طراحی_الگوریتم #الگوریتم_ژنتیک_چیست #الگوریتم_ژنتیک
نظر شما
برای ارسال نظر باید وارد شوید.
0 نظر

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

افرادی که این مطلب را خواندند مطالب زیر را هم خوانده اند