به عنوان یک قانون کلی که در مقاله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)&amp;amp;&amp;amp; 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’ &amp;amp; ‘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)&amp;lt;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&amp;lt;(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&amp;lt;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) &amp;amp;&amp;amp; isSolution(board)

counter = counter + 1;

disp(board);

end

if ( depth &amp;lt;= 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

بایگانی برچسب برای: Solution count

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

منبع

تلفن های تماس:

ساعات کاری

پیوند ها :

محصولات :