بایگانی برچسب برای: میوتیشن

به عنوان یک قانون کلی که در مقالهOptimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors  به آن اشاره شده (لینک مقاله در انتها آورده شده) اندازه جمعیت به تعداد ژن ها بستگی دارد. بنابراین ۹ ژن  به ۱۶ کروموزوم نیاز دارد و ۱۶ ژن به ۳۲ کروموزوم. معمولا با انتخاب اندازه حمعیتی معادل با ۱٫۵ تا ۲ برابر تعداد ژن ها شروع می شود تا به ماکزیمم اندازه جمعیت ۱۰۰ برسیم.

برای فضاهای حالت پیچیده احتمال crossover بالاتر (بیش از ۰٫۵) به جستجو در ابتدای کار کمک می کند. با این وجود در ادامه باید به مقادیری نزدیک به ۰٫۱ یا ۰٫۲ کاهش یابد. احتمال میوتیشن باید پایین نگه داشته شود (۰٫۰۱ – ۰٫۱). در غیر اینصورت همگرایی بی دلیل به تعویق می افتد.

پس برای مسائل مختلف و نحوه پیاده سازی مختلف الگوریتم ها تنظیم پارامترها متفاوت است و نمی توان به یک روال خاص در رابطه با کوچک یا بزرگ در نظر گرفتن جمعیت یا احتمالات میوتیشن و crossover اکتفا کرد. و بهترین راه تنظیم این پارامترها معمولا سعی و خطا و بازی با پارامترهاست.

ولی به عنوان یک قانون کلی:

اگر احتمال میوتیشن بسیار کوچک باشد: جمعیت بیش از حد زود همگرا می شود

اگر احتمال crossover بسیار بزرگ باشد: جمعیت هیچ گاه همگرا نمی شود

در ادامه الگوریتم مورد استفاده برای مسئله ۸ وزیر بارها وبارها با پارامترهای مختلف اجرا شده است تا بهترین پارامترها در نظر گرفته شود.

به این صورت عمل شده است که از آنجایی که تعداد ژن ها برابر با ۸ است ابتدا از ۱٫۵ برابر آن یعنی ۱۲ شروع شده است. یعنی مقدار جمعیت برای بار اول برابر با ۱۲ قرار داده شده است. تعداد نسل ها برابر با تعداد تکرار است. تعداد نسل را نصف تعداد جمعیت قرار می دهیم و از احتمال میویتش ۰٫۰۱ و احتمال crossover 0.5 استفاده می کنیم. لینک دانلود مرجع کد برنامه در انتها آورده شده است.

همان طور که مشاهده می شود نتیجه خوب نیست

تغییر تعداد جمعیت به دو برابر تعداد ژن ها:

هنوز به فیتنس ۲۸ یعنی تعداد برخوردهای ۰ نرسیده ایم.

در محله بعدی تکرار افزایش می یابد:

حال برای مقایسه مقدار crossover افزایش می یابد:

در این حالت هم به global maximum نرسیدیم و در دام بهینه محلی افتادیم.

مقدار crossover را مجددا کمتر کرده و مقدار میوتیشن را کمی افزایش می دهم:

نتیجه بدتر شد. مجددا به حالت قبل بر می گردانیم:

مشاهده می شود این بار نتیجه از بار قبل که با همین مقادیر اجرا شد بهتر است. چون الگوریتم ژنتیک احتمالاتی است هر بار اجرای آن نتیجه متفاوتی دارد. مثلا ژنی که برای میوتیشن انتخاب می شود تغییر می کند و کروموزوم حاصل در نسل بعدی نتیجه را تغییر می دهد.

در مرحله بعد تعداد جمعیت را به ۲۰ افزایش میدهیم:

نتیجه تغییر چندانی ندارد.

همان طور که در شکل بالا مشاهده می شود اندازه نسل نیز افزایش یافت ولی تغییر چندانی حاصل نشد.

به نظر می رسد تعداد جمعیت باید تغییر زیادی داشته باشد تا نتیجه بیشتر تغییر کند:

در این مرحله تعداد جمعیت را برابر با تعداد ژنها به توان ۲ در نظر می گیریم (در تحقیقی ثابت شده بهتر است همواره جمعیت بیشتر از دوبرابر تعداد ژنها باشد که این طور که از نتایج مشخص است این روش خوبی است).

حال می توان میتویشن و crossover را تغییر داد:

کاهش crossover در این حالت نتیجه را خراب کرد

در حالت فوق میوتیشن کمی افزایش داده شد

در حالت فوق جمعیت و تکرار را افزایش می دهیم که ابتدا به دو راه حل بهینه می رسد و البته سرعت اجرا بسیار کند می باشد ولی بعد از افزایش میوتیشن تعداد راه حل های بهینه افزایش پیدا کرده و سرعت کندتر می شود. یعنی هزینه اجرایی بالا می رود.

در تصویر فوق به علت قرار دادن یک عدد بزرگ برای میوتیشن فقط یک جواب بهینه پیدا کرد و سریع در دام بهینه های محلی افتاد.

در تصویر فوق مشاهده می شود که به علت قرار گیری عدد بزرگ در crossover به هیچ وجه همگرا نمی شود

تا کنون بهترین حالتی که مشاهده شد تصویر فوق است. که با در نظر گرفتن جمعیت نرمال ۱۰۰ ، تعداد تکرار نصف جمعیت یعنی ۵۰ و مقدار احتمال میوتیشن ۰,۰۱ و crossover برابر با ۰٫۰۷ به ۶ جواب بهینه رسیدیم. یعنی ۶ کروموزومی پیدا شدند که فیتنس ۲۸ و ماکزیمم دارند.

اجرای ۸ وزیر در متلب:

در کد زیر که با الهام از الگوریتم تپه نوردی نوشته شده پس از اجرا برای جمعیت برابر با ۱۰۰۰ و تعداد تکراری برابر با ۱۰۰ به ۲۰ جواب بهینه رسیدیم. در اینجا نیز تنظیم پارامترها دست شما است و می توان به جواب بهتری رسید


pop=1000;                                         %total population always

gen=100;                                           %total generations

n=8;

max_fitness=(((n-1)*n)/2);

initpop=zeros(pop,n);                            %initial population

pop_fitness=zeros(pop,1);                        %population fitness matrix

pop_fitness_sorted=zeros(pop,1);                 %for sorted fitness

fitness_temp=0;                                  %fitness temporary variable used in fitness loops between k and j

actual_pop_temp=zeros(1,n);

actual_pop_sorted=zeros(pop,n);

z=0;                                             %temporary variable used for simplicity

s=1;

w=0;

solution=zeros(1000,n);                           % solution matrix

cross_over_temp_mat=zeros(pop/2,n);              %cross-over variables

cross_over_ready_pop=zeros(pop,n);

cross_over_pop_final=zeros(pop,n);

cross_over_point=0;

cross_over_pop_temp_one=zeros(1,n);

cross_over_pop_temp_two=zeros(1,n);

cross_over_pop_temp_adjust=0;

cross_over_child_two_flipped=zeros(1,n);

cross_over_child_one=zeros(1,n);

cross_over_child_two=zeros(1,n);

mutation_temp_one=0;                             %mutation variables

mutation_temp_two=0;

mutation_temp_data=0;

for i=1:pop

initpop(i,:)=randperm(n);   %random initial population –indicates queen position on board

end;

actual_pop=initpop;                                 %duplication for working on this variable and keeping initial population intact

%generations loop

for q=1:gen

%for one generation

for i = 1:pop

fitness_temp=0;

%fitness calculation loop

for k=1:(n-1)                                               %calculates fitness by position manipulation

for j=k+1:n                                         %queen movements have been covered using j and k manipulation

z=abs(actual_pop(i,k)-actual_pop(i,j));          % for example   : when one queen is at (3,1)–(row,column)

if (ne(z,0)&& ne(z,(j-k)))                      %                next queens cant be at {(2,2),(3,2),(4,2) } {(1,3),(3,3),(5,3)}

fitness_temp=fitness_temp+1;               %                now you can observe that subtraction of each queen position and next

end                                             %                column queen position tells us a lot of information.

end                                                 %                remember the actual pop contains queen position dont confuse them with ‘i’ & ‘j’

end

pop_fitness(i,1)=fitness_temp;

end

%sort for individuals with good fitness

pop_fitness_sorted=pop_fitness;

actual_pop_sorted=actual_pop;

for i=1:(pop-1)

for j=i+1:pop

if(pop_fitness_sorted(i,1)<pop_fitness_sorted(j,1))

fitness_temp=pop_fitness_sorted(i,1);

pop_fitness_sorted(i,1)=pop_fitness_sorted(j,1);

pop_fitness_sorted(j,1)=fitness_temp;

actual_pop_temp(1,:)=actual_pop_sorted(i,:);

actual_pop_sorted(i,:)=actual_pop_sorted(j,:);

actual_pop_sorted(j,:)=actual_pop_temp(1,:);

end

end

end

% for unique solution gathering

%specified a vector of 100 rows ‘n’ columns

for i=1:pop

if(pop_fitness_sorted(i,1)==max_fitness)

for j=1:s

if actual_pop_sorted(i,:)==solution(j,:)

w=w+1;

else

w=w;

end

end

if w==0

solution(s,:)=actual_pop_sorted(i,:);

s=s+1;

else

continue;

end

end

w=0;

end

%selection

for i=1:(pop/2)

cross_over_temp_mat(i,:)=actual_pop_sorted(i,:);

end

cross_over_ready_pop=repmat(cross_over_temp_mat,2,1);

cross_over_pop_final=cross_over_ready_pop;

%cross over part begins

%for detail explaination cross over logic refer to the pdf attached

%logic—get random crossover point–then cross over at that point

%if two same values of rows in one individual..then adjust crossover

%according to the logic give in the pdf

while 1,

cross_over_point=floor(n*rand(1));

if cross_over_point~=0

break;

end

end

i=1;

while i<(pop-1),

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

%for child one

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_one(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_one(1,j)=cross_over_pop_temp_two(1,j);

end

%for child two

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_two(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_two(1,j)=cross_over_pop_temp_two(1,j);

end

cross_over_pop_final(i,:)=cross_over_child_one(1,:);

cross_over_child_two_flipped=wrev(cross_over_child_two);                 %flipped

cross_over_pop_final(i+1,:)=cross_over_child_two_flipped(1,:);

i=i+2;

end

%mutation introduced

%mutation occours  :at every 5th individual..swapping of two random

%                   column values(that is queen positions)

i=5;

while i<pop,

mutation_temp_one=floor(rand(1)*n/2);

mutation_temp_two=floor(2*(rand(1)*n/2));

if (mutation_temp_one==0 || mutation_temp_two==0)

continue;

else

mutation_temp_data=cross_over_pop_final(i,mutation_temp_one);

cross_over_pop_final(i,mutation_temp_one)=cross_over_pop_final(i,mutation_temp_two);

cross_over_pop_final(i,mutation_temp_two)=mutation_temp_data;

end

i=i+5;

end

i=0;

actual_pop=cross_over_pop_final;%the most important statement for my code

end

f=figure(‘Position’,[50 100 1000 600]);

cnames = {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’10’,’11’,’12’};

rnames = {‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’};

t = uitable(‘Parent’,f,’Data’,solution,’ColumnName’,cnames,…

‘RowName’,rnames,’Position’,[10 100 1000 500]);

 
 

با تغییر جمعیت به ۱۰۰ و تکرار به ۵۰:

به ۳ جواب بهینه رسیدیم:

با اجرای کد زیر ۹۲ کروموزوم به عنوان خروجی برگردانده می شود یعنی ۸ وزیر ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.


function queen

clc;

counter = 0;

n = 8;

board = zeros(1,n);

[board,counter] = back(1, board,counter);

fprintf(‘Solution count: %d\n’,counter);

%%

function value =  isSolution(board)

for  i = 1:length(board)

for  j = (i+1): length(board)

if abs(board(i) – board(j)) == abs(i-j)

value = false;

return;

end

end

end

value = true;

%%

function [board,counter] =  back(depth, board,counter)

if  (depth == length(board)+1) && isSolution(board)

counter = counter + 1;

disp(board);

end

if ( depth <= length(board))

for  i = 1:length(board)

if ~any(board==i)

board(1,depth) = i;

[~,counter] = back(depth+1, board,counter);

end

end

end

 

بخشی از جواب ها بصورت زیر است:

۱     ۵     ۸     ۶     ۳     ۷     ۲     ۴

۱     ۶     ۸     ۳     ۷     ۴     ۲     ۵

۱     ۷     ۴     ۶     ۸     ۲     ۵     ۳

۱     ۷     ۵     ۸     ۲     ۴     ۶     ۳

۲     ۴     ۶     ۸     ۳     ۱     ۷     ۵

۲     ۷     ۵     ۸     ۱     ۴     ۶     ۳

۲     ۸     ۶     ۱     ۳     ۵     ۷     ۴

۳     ۱     ۷     ۵     ۸     ۲     ۴     ۶

۳     ۵     ۲     ۸     ۱     ۷     ۴     ۶

۳     ۵     ۲     ۸     ۶     ۴     ۷     ۱

۳     ۵     ۷     ۱     ۴     ۲     ۸     ۶

۳     ۵     ۸     ۴     ۱     ۷     ۲     ۶

۳     ۶     ۲     ۵     ۸     ۱     ۷     ۴

۳     ۶     ۲     ۷     ۱     ۴     ۸     ۵

۳     ۶     ۲     ۷     ۵     ۱     ۸     ۴

۳     ۶     ۴     ۱     ۸     ۵     ۷     ۲

۳     ۶     ۴     ۲     ۸     ۵     ۷     ۱

۳     ۶     ۸     ۱     ۴     ۷     ۵     ۲

۳     ۶     ۸     ۱     ۵     ۷     ۲     ۴

۳     ۶     ۸     ۲     ۴     ۱     ۷     ۵

۳     ۷     ۲     ۸     ۵     ۱     ۴

Solution count: 92

منبع

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

فانکش استفاده از میوتیشن برای نسل فعلی:

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

همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.

کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.

(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)

در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.

در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.

تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.

در کد c# مورد استفاده :

class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.

class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.

struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.

class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.

class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.

متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.

توابع:


private List<chromosome> GetInitialPopulation(int population)

{

List<chromosome> initPop = new List<chromosome>();

GeneticAlgo RandomGen = new GeneticAlgo();

for (int i = 0; i < population; i++)

{

List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});

Chromosome chromosome = new Chromosome();

chromosome.genes = new int[8];

for (int j = 0; j < 8; j++)

{

int geneIndex = (int)(RandomGen.GetRandomVal

(۰,genes.Count-1)+0.5);//randomly select a gene

chromosome.genes[j] = genes[geneIndex];

genes.RemoveAt(geneIndex);//remove selected gene

}

initPop.Add(chromosome);

}

return initPop;

}

 

تابع فوق اندازه جمعیت را به صورت پارامتر می گیرد و لیستی از کروموزوم هایی که دربردارنده ژن های تولید شده تصادفی هستند را بر می گرداند. مقدار ژن ها بصورت تصادفی از لیستی که شامل اعداد ۰ تا ۷ است انتخاب می شود. در حین اینکه مقادیر از لیست انتخاب می شوند، مقادیر انتخاب شده پاک می شوند تا از تکراری شدن ژن ها در کروموزوم جلوگیری شود. اندازه لیست مساوی با اندازه جمعیت است. پس از ایجاد جمعیت اولیه با استفاده از این تابع، لیست کروموزوم هایی که برمیگرداند به تابع DoMating داده می شود.


public void DoMating(ref List<Chromosome> initPopulation,

int generations, double probCrossver, double probMutation)

{

int totalFitness = 0;

CalcFitness(ref initPopulation, ref totalFitness);

for (int generation = 0; generation < generations; generation++)

{

PrepareRuletteWheel(ref initPopulation,totalFitness);

Crossover(ref initPopulation, probCrossver);

Mutate(ref initPopulation, probMutation);

CalcFitness(ref initPopulation, ref totalFitness);

if (initPopulation[initPopulation.Count – 1].fitness == 28)

break;

if (progress != null)

{

progress(generation + 1);

}

}

initPopulation.Sort(new FitnessComparator());

}
 

این تابع لیست کروموزوم ها را به عنوان جمعیت اولیه ، تعداد نسل هایی که می خواهیم در الگوریتم پخش شوند، احتمال crossover و احتمال mutation را به عنوان پارامتر می گیرد. مسئولیت این تابع هندل کردن پخش جمعیت به نسل مورد نیاز با فراخوانی توابع CalcFitness،PrepareRuletteWheel،CrossoverوMutate است.

 

public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)

{

int collisions = 0;

totalFitness = 0;

for (int k = 0; k < chromosome.Count; k++)

{

for (int i = 0; i < chromosome[k].genes.Length – 1; i++)

{

int x = i;

int y = chromosome[k].genes[i];

for (int j = i + 1; j < chromosome[k].genes.Length; j++)

{

if (Math.Abs(j – x) == Math.Abs

(chromosome[k].genes[j] – y))

collisions++;

}

}

Chromosome temp = chromosome[k];

temp.fitness = MAX_FIT – collisions;

chromosome[k] = temp;

totalFitness += chromosome[k].fitness;

collisions = 0;

}

}

این تابع فیتنس هر کروموزوم را اندازه می گیرد و fitness value را به مشخصه fitness  هر کروموزوم تخصیص می دهد. فیتنس با محاسبه تعداد برخوردها و کم کردن آن از ماکزیمم تعداد برخورد ها محاسبه می کند. در این کد فیتنس تابعی است که هرچه مقدارش بیشتر باشد بهتر است. علاوه بر محاسبه فیتنس هر کروموزوم، این تابع می تواند فیتنس کلی جمعیت را نیز محاسبه کند زیرا در مرحله بعدی برای محسابه نرخ فیتنس هر کروموزوم به آن نیاز داریم.


private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)

{

int currentTotalFitness=0;

for (int i = 0; i < parents.Count; i++)

{

currentTotalFitness += parents[i].fitness;

Chromosome temp = parents[i];

temp.cumAvgFitness = currentTotalFitness / (double)total;

parents[i] = temp;

}

}

rulette wheel که بر مبنای فیتنس کروموزوم است برای انتخاب والدین برای جفت گیری برای ایجاد نسل جدید استفاده می شود. این تابع مسئول آماده سازی rulette wheel بوده و لیستی از کروموزوم ها را به عنوان جمعیت فعلی و فیتنس کلی جمعیت می گیرد. این تابع نرخ فیتنس هر کروموزوم تا فیتنس کلی را محاسبه می کند سپس مجموع آن را برای اختصاص به مشخصه cumAvgFitness  کروموزوم محاسبه می کند.

با تابع RuletteWheel می توان احتمال انتخاب را بر اساس نرخ فیتنس تعیین کرد. با این روش کروموزم هایی با fitness value بالاتر احتمال بیشتری برای انتخاب در ساخت نسل بعدی دارند در حالی که کروموزم هایی با fitness value پایین تر با احتمال کمتری شرکت داده می شوند


public void Crossover(ref List<Chromosome> parents, double probability)

{

List<Chromosome> offspring = new List<Chromosome>();

for (int i = 0; i < parents.Count; i++)

{

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains

(parentX.genes[k]))//instead of

//deleting the similar genes

//from parents select the

//next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains

(parentY.genes[k]))//instead of

//deleting the similar genes from

//parents select the next

//non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

else //else the chance is to clone

{

Chromosome parentX = AssayRuletteWheel(parents);

offspring.Add(parentX);

}

}

while (offspring.Count > parents.Count)

{

offspring.RemoveAt((int)GetRandomVal(0, offspring.Count – 1));

}

parents = offspring;

}

 

تابع فوق مسئول انجام عمل cross over است. تابع لیستی از کروموزم ها را به عنوان جمعیت فعلی و احتمال crossover را به عنوان پارامتر می گیرد. تابع Assay(int probability) با احتمال داده شده true بر می گرداند بنابراین با احتمال crossover برای تعیین اینکه عملیات crossover است یا cloning استفاده می شود.

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains(parentX.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains(parentY.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

این بخش از کد مسئول crossover دو پرنت parentX  و parentY می باشد. به منظور ایجاد فرزند، ژنها از دو والدین با احتمال ۰٫۵ انتخاب می شوند در حالیکه از تکرار ژنها در کروموزوم ها اجتناب می شود. در عملیات cloning یکی از والدین مستقیما به نسل بعدی آورده می شود.


public void Mutate(ref List&amp;lt;Chromosome&amp;gt; parents, double probability)

{

List&amp;lt;Chromosome&amp;gt; offsprings = new List&amp;lt;Chromosome&amp;gt;();

for (int i = 0; i &amp;lt; parents.Count; i++)

{

Chromosome offspring = parents[i];

for (int mutatePosition = 0; mutatePosition &amp;lt; 8; mutatePosition++)

{

if (Assay(probability)) //if the chance is to mutate

{

int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);

if (newGeneIndex&amp;gt;=mutatePosition)

{

newGeneIndex += 1;

}

int swapTemp = offspring.genes[mutatePosition];

offspring.genes[mutatePosition] =

offspring.genes[newGeneIndex];

offspring.genes[newGeneIndex] = swapTemp;

}

}

offsprings.Add(offspring);

}

parents = offsprings;

}
 

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

زمانی که به یک راه حل می رسیم آرایه ژن های کروموزومی که شامل راه حل هستند را میتوان به پراپرتی به نام Genes  در کلاس Board اختصاص داد.

این برنامه این امکان را می دهد که اندازه جمعیت، تعداد نسل ها، احتمال crossover و احتمال mutation را مشخص کنید.

تمام کروموزوم های نسل آخر در جدول نشان داده می شوند و بهترین نتیجه در صفحه شطرنج گرافیکی نمایش داده می شود.

هیچ محدودیتی برای تعداد نسل ها وجود ندارد تازمانی که از ماکزیمم مقداری که یک متغیر اینتیجر می تواند بگیرد بیشتر نشود. از آنجایی که این الگوریتم بر اساس فرایند احتمالاتی است نمی توان همیشه انتظار پاسخ صحیح را داشت. به عبارت دیگر از آنجایی که این روش احتمالاتی است می توان با تکرار اجرای آن به راه حل های مختلفی دست یافت.

این سوال ها سالها مطرح بوده است که بین crossover و mutation کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده این است که هر کدام نقش مخصوص خود را دارد. در حالت کلی بهتر است از هر دو استفاده شود. میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover   استفاده کند کار نخواهد کرد. Crossover خاصیت جستجوگرانه و یا explorative دارد. میتواند با انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. Mutation خاصیت گسترشی و یا  exploitive  دارد. میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد.  Crossoverاطلاعات والدین را ترکیب میکند درحالیکه mutation  میتواند اطلاعات جدیدی اضافه نماید. رسیدن به یک پاسخ بهینه در mutation شانسی است.

نتایج اجرای این الگوریتم نشان می دهد که جمعیت عامل بسیاری مهمی بوده و تاثیر زیادی دارد و crossover probability و mutation rate تاثیر غیر قابل انکاری بر اجرای الگوریتم ژنتیک دارند زیرا با هر بار تغییر در هر یک از این پارامترها نتایج به شدت تغییر می کند. در حقیقت نحوه انتخاب اپراتورهای GA یک تریدآف بین همگرایی سریع تر و حفظ قابلیت اکتشافی بودن الگوریتم (برای جلوگیری از همگرایی اشتباه) است. Crossover پارامتری است که به تنظیم رفتار الگوریتم ژنتیک کمک می کند. کم کردن احتمال crossover باعث می شود در نسل بعدی افراد بیشتری بدون تغییر باقی بمانند. بسته به مسئله کاهش یا افزایش مقدار احتمال crossover می تواند تاثیر مثبت یا منفی داشته باشد.

پس از اجراهای متوالی الگوریتم می توان دید که هیچ جوابی وجود ندارد گه به طور قطع بتوان گفت از بقیه بهتر است و بتوان گفت که مقدار تنظیم شده برای پارامترهای الگوریتم ژنتیک در این حالت از همه بهتر است. این بهترین مقادیر به عوامل زیادی وابسته هستند. برای مثال اگر الگوریتم شما generational است میخواهید احتمالی را برای این در نظر بگیرید که برخی از والدین بدون تغییر باقی بمانند. در غیر اینصورت برخی راه حل های خوب را از دست خواهید داد. بنابراین بهتر است crossover rate را نزدیک به ۰٫۷ تنظیم کرد. برخی از الگوریتم ها نیز هستند که به طور کامل به mutation وابسته اند و برای آنها crossover rate مساوی با ۰ در نظر گرفته می شود. اگر crossover probability برابر با ۱۰۰درصد باشد همه فرزندان توسط crossover ایجاد می شوند. اگر ۰ درصد باشد همه نسل جدید کپی دقیقی از کروموزوم فعلی جمعیت قدیمی است ولی به این معنی نیست که نسل جدید دقیقا همان نسل قبلی است.

انتخاب اپراتورهای الگوریتم توازنی میان سرعت و دقت همگرایی است یعنی exploration در مقابل exploitation.

اینطور که گفته شده بهتر است mutation بین ۰٫۰۱۵ تا ۰٫۰۲ باشد. چرا؟

Exploration یعنی جستجوی فضای حالت در حد امکان در حالی که exploitation یعنی تمرکز بر یک نقطه که امیدواریم global optimum باشد.

در GA اپراتورهای mutation اغلب برای exploration و اپراتور های Crossover اغلب برای exploitation یعنی هدایت جمعیت به سوی همگرایی به یک راه حل خوب استفاده می شوند. در نتیجه وقتی Crossover سعی در همگرایی به یک نقطه مشخص دارد mutation سعی خود را می کند که همگرایی صورت نگیرد و فضای بیشتری کاوش شود.

در ابتدای فرایند جستجو ترجیح ما بر این است که جستجوی بیشتری به منظور اکتشاف فضا صورت گیرد. از طرف دیگر در انتهای فرایند جستجو exploitations بیشتری ترجیح داده می شود که همگرایی جمعیت به سمت global optimum تضمین شود. تنها یک استثناء وجود دارد؛ زمانی که جمعیت به سمت بهینه محلی همگرا می شود اگر بتوانیم باید پراکندگی حمیت را افزایش دهیم تا فضای بیشتری جستجو شود و در دام بهینه محلی نیفتد. با توجه به این نکته mutation rate بالا باعث افزایش احتمال جستجوی فضای بیشتری از فضای جستجو می شود با این حال از همگرایی جمعیت به یک جواب بهینه جلوگیری می کند. از طرف دیگر اگر mutation rate خیلی کوچک باشد باعث همگرایی زودهنگام و نارس می شود و به حای رسیدن به global optimum در دام بهینه محلی گرفتار می شود.مقداری که انتخاب می شود به ماهیت مسئله و نحوه پیاده سازی الگوریتم بستگی دارد. پس mutation rate های بسیار بالا از همگرایی الگوریتم جلوگیری کرده و رسیدن به راه حل بهینه را تضمین نمی کنند. بنابراین عاقلانه تر این است که از mutation rate های کوچک تر استفاده شود. مقدار کوچک برای mutation rate تضمین می کند که میوتیشن های زیادی در آن واحد اتفاق نیفتد ولی این نیز به تعداد ژن های موجود در هر کروموزوم از جمعیت بستگی دارد. بهتر این است که با مقادیر کم شروع کرده و به تدریج آنها را افزایش داد و کارایی هر یک را بررسی کرد مثلا به ترتیب: ۰٫۰۰۱، ۰٫۰۱، ۰٫۰۵، ۰٫۱، ۰٫۲ و … . در رابطه با جستجو در فضای حالت در مقایسه با mutation rate بالاتر، جمعیت بزرگتر ترجیح داده می شود.

در مقابل استفاده از mutation rate مناسب منجر به رسیدن سریع به نتایج خوب می شود و استفاده از mutation rate های بیش از حد کوچک فرایند را بسیار کند می کند زیرا کوناگونی را کم کرده و در نهایت ممکن است حتی همگرایی به درستی صورت نگیرد. mutation rate های بسیار بزرگ نیز همگرا شدن را بسیار سخت می کنند زیرا باعث می شوند جواب صحیح به راحتی از دست برود. بهترین راه تغییر تدریجی mutation rate است. مثلا به عنوان راه حل دیگر می توان با mutation rate های بزرگ شروع کرد تا گوناگونی بیشتری تزریق کرده از افتادن در دام بهینه محلی جلوگیری کرد سپس با انتها رسیدن الگوریتم یعنی تکرار آخر، این مقدار را کاهش داده و بهترین راهکار پیدا شود.

Exploitation = (crossover +  انتخاب بر اساس فیتنس) ما را به جواب بهینه نهایی می رساند.

این طور گفته می شود که اندازه جمعیت کوچکتر سرعت همگرایی بیشتری به الگوریتم می دهد ولی الگوریتم راحتتر در بهینه محلی گرفتار می شود. احتیاط بر این است که از جمعیت های بیش از حد کوچک استفاده نشود. معمولا به احتمال crossover و mutation بسیار بزرگ نیاز نخواهید داشت و جمعیتی با اندازه متوسط مناسب است.

است.
مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4