遺傳演算法程式實作

遺傳演算法程式實作



主程式GA
function [fmax,favg,x_best,y_best] = GA

Npopsiz = 100; %族群大小 最佳30~200
Pcross = 0.95; % 交配率 最佳0.5~1.0
Pmutate = 0.05; % 突變率 最佳0.001~0.05
Ngene =10; % 基因個數
Nitraton = 100; % 演化代數

U = genpop(Npopsiz,Ngene); % 亂數產生起始族群
[fit,X,Y] = fitness(U,Npopsiz); % 編碼計算最適函數

for k = 1 : Nitraton,
%保留最佳兩個其餘運算
[fitsort,index] = sort(fit);
U = U(index,:);
U_best = U(Npopsiz-1:Npopsiz,:);
U(1:2,:) = genpop(2,Ngene);
U_op = U(1:Npopsiz-2,:);

% Basic three operations: selection, crossover, and mutation
SelectU = selt(U_op,fitsort(1:Npopsiz-2),Npopsiz-2); % 複製
CrossoverU = cross(SelectU,Pcross,Npopsiz-2,Ngene); % 交配
MutationU = mute(CrossoverU,Pmutate,Npopsiz-2,Ngene); % 突變

% Replacement strategy
U = [U_best;MutationU]; % 合併
[fit,X,Y] = fitness(U,Npopsiz); % 再次編碼計算最適函數

[fmax(k), ind ] = max(fit); % find maximal fitness in kth iteration
x_best(k) = X( ind ); % pick up the best X value
y_best(k) = Y( ind ); % pick up the best Y value
favg(k) = mean(fit); % find average fitness in kth iteration
end;
[fit,Real_X,Real_Y] = fitness(U,Npopsiz);
X=max(Real_X)
Y=max(Real_Y)

x_best = x_best(Nitraton); % the latest chromosome is the best cause of the incresing curve of fmax
y_best = y_best(Nitraton);
figure;
r = 1 : Nitraton;
plot(r,fmax,'r',r,favg,'b:');
end;
副程式 genpop 亂數產生起始值 %改寫範例 向量寫法
function [U] = genpop(Npopsiz,Ngene)

U = round(rand(Npopsiz,Ngene)); %改寫範例 隨機產生0~1起始值
end
副程式 fitness 編碼計算最適參數解
function [fit,Real_X,Real_Y] = fitness(U,Npopsiz)

X = U(:,1:5); Y = U(:,6:10); %將矩陣分成前半部x與後半部y

% 編碼產生(100,1)個0
De_X = zeros(Npopsiz,1); De_Y = zeros(Npopsiz,1);


for i = 5 : -1 : 1,
De_X = 2 ^ (5 - i) * X(:,i) + De_X; % 將x轉成十進制
De_Y = 2 ^ (5 - i) * Y(:,i) + De_Y; % 將y轉成十進制
end;

Real_X = 10 * De_X .* 0.0313; %介於正負0~10之間
Real_Y = 10 * De_Y .* 0.0313;

% 求最適參數解
fit = - [ Real_X .* sin(4 * Real_X) + 1.1 * Real_Y .* sin(2 * Real_Y)]';
副程式 cross 複製
function [SelectU] = selt(U,fit,Npopsiz)

Good_U = U(round(Npopsiz/4*3):Npopsiz,:);
Good_fit = fit(round(Npopsiz/4*3):Npopsiz);
m = length(Good_fit);

p = Good_fit ./ sum(Good_fit); %輪盤法
cumup = cumsum(p);

for i = 1 : Npopsiz,
for j = 1 : m,
if rand <= cumup(j), SelectU(i,:) = Good_U(j,:); break; end; end; end; ================================================================== 副程式 cross 交配 %改寫範例 多點交配 function [CrossoverU] = cross(SelectU,Pcross,Npopsiz,Ngene) SelectU = SelectU(randperm(Npopsiz),:); %隨機排列 CrossoverU = SelectU; for i = 1 : 2 : Npopsiz, point1 = ceil(rand * (Ngene - 6)); % 產生4個交配區間 point2 = ceil(rand * (Ngene - 6)); point3 = point1+(Ngene/2); point4 = point2+(Ngene/2); pt = sort([point1 point2 point3 point4]); %改寫範例 多點交配 CrossU(i,:) = [SelectU(i,1:pt(1)) SelectU(i+1,pt(1)+1:pt(2)) SelectU(i,pt(2)+1:pt(3)) SelectU(i+1,pt(3)+1:pt(4)) SelectU(i,pt(4)+1:Ngene)]; CrossU(i+1,:) = [SelectU(i+1,1:pt(1)) SelectU(i,pt(1)+1:pt(2)) SelectU(i+1,pt(2)+1:pt(3)) SelectU(i,pt(3)+1:pt(4)) SelectU(i+1,pt(4)+1:Ngene)]; [fit_prnt,A,B] = fitness(SelectU(i:i+1,:),2); %產生父代 [fit_son,A,B] = fitness(CrossU(i:i+1,:),1); %產生子代 if sum(fit_son)/2 > sum(fit_prnt)/2,
CrossoverU(i,:) = CrossU(i,:);
CrossoverU(i+1,:) = CrossU(i+1,:);
end;

end;
副程式 mute 突變
function [MutationU] = mute(CrossoverU,Pmutate,Npopsiz,Ngene)

MutationU = CrossoverU;

for i = 1 : Npopsiz,
for j = 1 : Ngene,
if rand <= Pmutate,
MutationU(i,j) = abs(MutationU(i,j) -1);
end;
end;
end