به عنوان یک قانون کلی که در مقاله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
![{\displaystyle \min _{\mathbf {w} ,b,{\boldsymbol {\alpha }}}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b140ef307512ccbafd34429bf40ee6523eac03a)
![{\displaystyle \min _{\mathbf {w} ,b}\max _{\boldsymbol {\alpha }}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c411ce7bd4a910dba7b0a5a0ee3191146665dec1)
.jpg){kind=small}
.jpg){kind=small}
.jpg){kind=small}
.jpg){kind=small}
تشکیل شوند که هر کدام از uiها، عباتی تجزیه ناپذیر است. مانند ” تا حدی سرد “، که در مجموع به 4 دسته زیر تقسیم می شود:.jpg)
