الگوريتم ژنتيك (GA)

[ravegoat]

انتخاب (Selection)
عملگري هست كه نحوه ي شركت جمعيت ها براي تشكيل نسل هاي بعد را تعيين مي كند. از ديد بهينه سازي عملگر انتخاب بايد نسلي را تشكيل دهد كه جمعيت آن اطلاعات ارزشنمند تر و بهينه تري را نسبت به نسل قبلي داشته باشد. دو روش متداول در انتخاب عبارت اند از:

1. چرخ گردان (Roulette Wheel)
2. تورنومنت (Tournament)

روش چرخ گردان (Roulette Wheel)
در اين روش يك دايره يا ديسك داريم كه هر كروموزوم با توجه به برازندگي (Fitness) اي كه دارد بخشي از اين دايره (Circular Sector) را به خود اختصاص مي دهد به گونه اي كه مجموع سكتور هاي هر كروموزوم يك دايره ي كامل را تشكيل مي دهد. يك اشاره گر وجود دارد كه بر محيط اين دايره مماس است. زماني كه اين دايره را حول مركز آن بچرخانيم، دايره مي چرخد و پس از مدتي مي ايستد. در اين حالت اشاره گر به يكي از اين بخش هاي تعيين شده روي دايره اشاره مي كند. چون هر يك از بخش ها (سكتور) بيان گر يك كروموزوم است، اشاره گر در واقع يك كروموزوم را انتخاب مي كند.
شكل زير چرخ گردان مربوط به مثال پست قبل (تعيين مقدار مقاومت الكتريكي مدار) را نشان مي دهد:

RW.PNG

خط قرمز رنگ همان اشاره گر است كه كروموزومي با برازندگي 40% را انتخاب كرده است. واضح است كه هر چه يك كرموزوم برتر باشد، احتمال انتخاب آن بيش تر خواهد بود.
حال بياييم سورس MATLAB اين روش را نيز بنويسيم:

fitness=[0.1,0.17,0.27,0.13,0.2,0.4];
f1=cumsum(fintness);
a=rand;
for i=1:(size(f1,2)-1)
   if a>=f1(i) && a<=f1(i+1)
      selectedpop=pop(i,:);
      break
   end
end

در كد بالا آرايه ي fintness شامل مقادير برازندگي كروموزوم ها است. ماتريس pop جمعيت اوليه ي كروموزوم ها و ماتريس selectedpop جمعيت انتخاب شده است.


روش تورنومنت (Tournament)
اين روش به گونه هاي مختلف اجرا مي شود؛ از جمله شكل 2 Plus يا 4 Plus .
در روش 2 Plus از جمعيت اوليه، چهار كروموزوم به شكل تصادفي انتخاب مي شوند. كروموزوم هاي انتخابي اول و دوم از نظر مقدار برازندگي با هم مقايسه مي شوند و كروموزومي كه برتر باشد به مرحله ي بعد مي رود. همين مقايسه روي كروموزوم هاي انتخابي سوم و چهارم صورت مي گيرد تا كرموزوم برتر شناسايي شود. حال دو كروموزوم برتر داريم كه آن دو را نيز از نظر برازندگي با هم مقايسه مي كنيم. كروموزوم برتر كروموزومي خواهد بود كه به نسل بعد خواهد رفت:

1|1|0|0|1|1|0|1

1|1|0|0|1|1|0|1 برتر

1|1|1|0|1|1|0|1

1|1|0|0|1|1|0|1 برترين

0|0|0|0|1|1|1|1

1|1|0|0|0|1|0|0 برتر

1|1|0|0|0|1|0|0

روش 4 Plus هم به شكل مشابه اجرا مي شود با اين تفاوت كه در قدم اول 8 كروموزوم از جمعيت اوليه به شكل تصادفي انتخاب مي شوند.