no-img

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


م
ن
و
آرنه وب | قالب رایگان وردپرس | افزونه وردپرس

ادامه مطلب

ZIP
مقاله معرفی الگوریتم ژنتیک – قسمت دوم
zip
آبان ۲۹, ۱۳۹۴

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


مقاله معرفی الگوریتم ژنتیک – قسمت دوم , article genetic algorithms part two

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

article genetic algorithms part two
article genetic algorithms part two

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

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

max و min : حد بالا و پایین شرایط مساله هستند .
۱۰۰۰۰ : دقت مساله را مشخص میکند . (تا چهار رقم اعشار)

یعنی برای هر متغیر به ۱۷ بیت نیاز است و در مجموع برای ایجاد یک کروموزوم دو متغیره به ۳۴ بیت .
حال باید جمعیت اولیه را ایجاد کنیم . برای این کار از اعداد Random استفاده میکنیم :

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

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

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

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

article genetic algorithms part two

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

حتما بخوانید :  مقاله کارآموزی در بانک کشاورزی

۱۳.۱۸۸۸- ۱۲.۱۶۶۹- ۸.۸۴۰۰- ۱۵.۳۴۷۹- ۷.۶۹۷۹- ۱۲.۲۶۵۳- ۱۱.۶۴۳۷- ۶.۵۲۶۲- ۱۱.۳۸۵۸- ۱۲.۴۹۰۷-

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

article genetic algorithms part two

بعد از اتمام آمیزش نوبت جهش است . برای این کار هم یک نرخ جهش انتخاب میکنیم برای این مثال مقدار ۰.۰۳ انتخاب کردم . سپس به ازای تمام بیتهای موجود عددی تصادفی تولید میکنیم و اگر مقدار عدد تصادفی کمتر از نرخ بود بیت متناظر را در جمعیت معکوس میکنیم . در این مثال مجموعا ۳۴۰ = ۳۴*۱۰ بیت (ژن) داریم و باید ۳۴۰ عدد تصادفی تولید کنیم . مثلا اگر عدد تصادفی بیت ۱۲ شد ۰.۰۲ باید مقدار بیت ۱۲ را معکوس کنیم .
بعد از جهش دوباره به اول حلقه برگشته . یعنی محاسبه x و سپس برازندگی و بعد انتخاب و چون تعدادی فرزند به جمعیت اضافه شده صدرصد انتخاب در بین بیش از ده کروموزوم صورت میگیرد .
در نهایت برای ۵بار اجرای مستقل و ۱۰۰۰بار اجرای الگوریتم جوابها به این شکل شد :

article genetic algorithms part two

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

حتما بخوانید :  دانلود پروژه ساخت آمپلی فایر ۳۰۰ وات

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

کلید واژه های مهم :

article genetic algorithms part two

download article genetic algorithms part two



درباره نویسنده

علیرضا نجاتی 602 نوشته در آرنه وب | قالب رایگان وردپرس | افزونه وردپرس دارد . مشاهده تمام نوشته های

دیدگاه ها


پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *