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

[ravegoat]

قبل از آن كه با نحوه ي تشكيل نسل بعد آشنا شويم، سوالي را مطرح مي كنيم:

" چه تعداد از جمعيت اوليه در توليد مثل شركت مي كنند؟ و چه تعداد از اين جمعيت اوليه دچار جهش مي شوند؟ "

براي پاسخ دادن به سوال فوق دو مفهوم را معرفي مي كنيم:
احتمال توليد مثل (Probability of Crossover يا P_c)
كميتي است كه احتمال شركت جمعيت اوليه در توليد مثل را تعيين مي كند. مقدار P_c بين 70% تا 95% است. اين به معني نيست كه فرضا" 70% از جمعيت اوليه در توليد مثل شركت مي كنند بلكه به اين معني است كه 70% احتمال دارد كه جمعيت در توليد مثل شركت كنند. به عبارتي ديگر ممكن است تمام جمعيت در زادولد شركت كنند و از طرفي هم ممكن است هيچ يك از كروموزوم ها در زادولد شركت نكنند.

سورس MATLAB اعمال احتمال توليد مثل در زاد ولد:

Pc=0.7;
for i=1:N/2
   a=rand;
   if a<=Pc
      %Do Crossover
   end
end

N تعداد جمعيت اوليه است.

احتمال جهش (Probability of Mutation يا P_m)
كميتي است كه احتمال جهش يافتن جمعيت اوليه را تعيين مي كند. مقدار P_m كوچك تر از 0.1 است. اين به اين معني است كه احتمال اين كه يك كروموزوم جهش يابد، كم تر از 10% است.

سورس MATLAB اعمال احتمال جهش در جهش يافتن:

Pm=0.1;
for i=1:N
   a=rand;
   if a<=Pm
      %Do Mutation
   end
end

N تعداد جمعيت اوليه است.


نحوه ي انتخاب نسل آينده:
فرض كنيم تعداد جمعيت اوليه برابر N، تعداد جمعيت حاصل از زادولد برابر P و تعداد جمعيت حاصل از جهش برابر Q باشد.

بقاي جمعيت:
اگر تعداد جمعيت اوليه N باشد، تعداد جمعيت نسل بعد نيز بايد N باشد.

براي تشكيل نسل جديد:

• اگر P>N باشد: با روش چرخ گردان، N كروموزوم را از جميعت حاصل از زادولد انتخاب مي كنيم كه اين N كروموزوم نسل بعد را تشكيل مي دهند.
• اگر P=N باشد: جميعت حاصل از زادولد همان جمعيت نسل بعد خواهد بود.
• اگر P<N باشد: جميعت حاصل از زادولد را به نسل بعد انتقال مي دهيم و براي جبران كمبود جمعيت جهت حفظ بقاي آن اين گونه عمل مي كنيم:
  
  • اگر Q>N-P باشد: با روش چرخ گردان،N-P كروموزوم را از جميعت حاصل از جهش انتخاب مي كنيم كه اين كروموزوم ها به علاوه ي كروموزوم هاي زادولد، نسل بعد را تشكيل مي دهند.
  • اگر Q=N-P باشد: تمام جميعت حاصل از جهش به علاوه ي كروموزوم هاي زادولد، نسل بعد را تشكيل مي دهند.
  • اگر Q<N-P باشد: تمام جميعت حاصل از جهش به علاوه ي كروموزوم هاي زادولد به نسل بعد منتقل مي شوند اما به دليل كمبود جمعيت بقاي آن حفظ نمي شود. لذا با روش چرخ گردان، N-P-Q كروموزوم را از جمعيت اوليه انتخاب مي كنيم تا اين كمبود جمعيت جبران شود و نسل بعد شكل گيرد.