进化算法程序
进化算法作业
1 全局优化问题 (1)min
f 1(x )=4x 12-2. 1x 14+
1624x 1+x 1x 2-4x 2+4x 2 3
s . t . -5≤x i ≤5,i =1, 2 此问题的全局最优值f min =-1.0316。
一.程序
(1)主函数: main.m clear all; clc;
popsize=60; %种群规模
chromlength=34; %二进制编码,编码精度为0.0001,所以串长l 为17 pc=0.7; %杂交概率 pm=0.1; %变异概率 t=0; %进化代数初始为0
pop=initpop(popsize,chromlength); %随机产生初始种群 while t
[objvalue]=calobjvalue(pop); %计算目标函数值
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[bestindividual,bestfit]=best(pop,fitvalue); %求出群体中适应度最大的个体及其适应度值
x11=decodechrom(bestindividual,1,14); %将二进制数转换为十进制数 x22=decodechrom(bestindividual,15,14);
x1(t)=-5+10*x11/(pow2(14)-1); %将二值域中的数转换为变量域的数 x2(t)=-5+10*x22/(pow2(14)-1);
y(t)=4*x1(t)^2-2.1*x1(t)^4+1/3*x1(t)^6+x1(t)*x2(t)-4*x2(t)^2+4*x2(t)^4; %计算最佳个体的目标函数值
[newpop1]=selection(pop,fitvalue); %选择算子 [newpop2]=crossover(newpop1,pc); %交叉算子 [newpop3]=mutation(newpop2,pm); %变异算子 objvalue1=calobjvalue(newpop3(1,:)); if objvalue1>y(t)
newpop3(1,:)=bestindividual; %保留最佳个体 end
pop=newpop3; %产生新种群 end
y; %每代的最佳目标函数值
x1; %每代的最佳目标函数值对应的自变量
[gy,k]=min(y) %gy为全局最优值,k 为最优值对应的进化代数 gx1=x1(k) %全局最优值对应的自变量 gx2=x2(k)
plot(y) %最优值收敛曲线 title('收敛性曲线'); xlabel('进化代数'); ylabel('函数值');
axis([0,500,-1.5,1.5]);
(2)初始种群:initpop.m
function pop=initpop(popsize,chromlength)
pop=round(rand(popsize,chromlength)); %rand随机产生[0,1]区间的一个小数,rand 四舍五入取整 end
(3)计算目标函数值::calobjvalue.m function [objvalue] =calobjvalue( pop ) temp1=decodechrom(pop,1,14); temp2=decodechrom(pop,15,14);
x1=-5+(10*temp1)/(pow2(14)-1); %将二值域中的数转化为变量域中的数 x2=-5+(10*temp2)/(pow2(14)-1);
objvalue=4*x1.^2-2.1*x1.^4+1/3*x1.^6+x1.*x2-4*x2.^2+4*x2.^4; %计算目标函数 end
a .二进制转换为十进制:decodechrom.m function temp=decodechrom(pop,spoint,length )
pop1=pop(:,spoint:spoint+length-1); %按变量个数分组转换,spoint 为起始点,length 为一个变量的长度
temp=decodebinary(pop1); end
b .求二进制串对应的十进制数:decodebinary.m function temp =decodebinary( pop)
[px,py]=size(pop); %求pop 行数和列数 for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i); end
temp=sum(pop1,2); %每一行求和 end
(4)计算个体适应度:calfitvalue.m function fitvalue= calfitvalue( objvalue ) fitvalue=1./(1+exp(objvalue));
(5)种群中最大适应度个体及其值:best.m
function [bestindividual,bestfit] = best(pop,fitvalue ) [px,py]=size(pop);
bestindividual=pop(1,:); bestfit=fitvalue(1); for i=2:px;
if fitvalue>bestfit
bestindividual=pop(i,:); best=fitvalue(i); end end end
(6)选择算子:selection.m
function [newpop1]=selection(pop,fitvalue) totalfit=sum(fitvalue); %适应度和
ps=fitvalue./totalfit; %单个个体被选择的概率 pss=cumsum(ps); %前几项累积和 [px,py]=size(pop);
ms=sort(rand(px,1)); %随机产生px 个0,1之间的数,并按升序排列 fitin=1; newin=1;
while newin
if(ms(newin)
newpop1(newin,:)=pop(fitin,:); newin=newin+1; else
fitin=fitin+1; end end end
(7)交叉算子:crossover.m
function [newpop2] = crossover( pop,pc ) [px,py]=size(pop);
newpop2=ones(size(pop)); for i=1:2:px-1 if rand
cpoint=round(rand*py); %随机产生一个交叉位
newpop2(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)]; %交换相邻两个个体交叉位之后的基因
newpop2(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];
else
nwepop2(i,:)=pop(i,:);
newpop2(i+1,:)=pop(i+1,:); end end end
(8)变异算子:mutation.m
function [newpop3] = mutation( pop,pm ) [px,py]=size(pop); newpop3=pop; for i=1:px
if(rand
mpoint=round(rand*py); %随机产生一个变异位 if mpoint
if (newpop3(i,mpoint)==0) %变为等为基因 newpop3(i,mpoint)=1; else
newpop3(i,mpoint)=0; end end
end end
二.独立运行程序30次的结果
最好目标函数值:-1.0316 最差目标函数值:-0.9751 平均目标函数值:-0.9914 标准方差:0.0286
三.最好的一次结果
最好解:x1=0.0919 x2=-0.7126
最好值:-1.0316
运行结果及收敛性曲线如下图:
运行结果 收敛性曲线
(2)min f 2(x )=(x 2-
5. 1251⎫⎛2
x +x -6) +101- ⎪cos (x 1)+10 121
π4π⎝8π⎭
s . t . -5≤x i ≤5,i =1, 2 此问题的全局最优值f min =0.398。
一.程序
(1)主函数: main.m clear all; clc
popsize=40; %种群规模
chromlength=28; %二进制编码,编码精度为0.001,所以串长l 为14 pc=0.8; %杂交概率 pm=0.2; %变异概率 t=0;
pop=initpop(popsize,chromlength); %随机产生初始种群 while t
[objvalue]=calobjvalue(pop); %计算目标函数值
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[bestindividual,bestfit]=best(pop,fitvalue); %求出群体中适应度最大的个体及其适应度值
x11=decodechrom(bestindividual,1,14); %将二进制数转换为十进制数 x22=decodechrom(bestindividual,15,14);
x1(t)=-5+10*x11/(pow2(14)-1); %将二值域中的数转换为变量域的数 x2(t)=-5+10*x22/(pow2(14)-1);
y(t)=(x2(t)-5.1/(4*pi*pi).*x1(t).^2+5/pi.*x1(t)-6).^2+10.*(1-1/(8*pi)).*cos(x1(t))+10; %计算最佳个体的目标函数值
[newpop1]=selection(pop,fitvalue); %选择算子 [newpop2]=crossover(newpop1,pc); %杂交算子 [newpop3]=mutation(newpop2,pm); %变异算子 objvalue1=calobjvalue(newpop3(1,:)); if objvalue1>y(t)
newpop3(1,:)=bestindividual; %保留最佳个体 end
pop=newpop3; %产生新种群 end
y; %每代的最佳目标函数值
x1; %每代的最佳目标函数值对应的自变量 x2;
[gy,k]=min(y); %全局最优值 gy=vpa(gy,3) %设置输出精度
gx1=x1(k); %全局最优值对应的自变量 x1=vpa(gx1,4) gx2=x2(k); x2=vpa(gx2,4)
plot(y) %最优值收敛曲线 title('收敛性曲线'); xlabel('进化代数'); ylabel('函数值'); axis([0,500,0.2,1.5]);
(2)初始种群:initpop.m
function pop=initpop(popsize,chromlength)
pop=round(rand(popsize,chromlength)); %rand随机产生[0,1]区间的一个小数,rand 四舍五入取整 end
(3)计算目标函数值::calobjvalue.m function [objvalue] =calobjvalue( pop ) temp1=decodechrom(pop,1,14); temp2=decodechrom(pop,15,14);
x1=-5+(10*temp1)/(pow2(14)-1); %将二值域中的数转化为变量域中的数 x2=-5+(10*temp2)/(pow2(14)-1);
objvalue=(x2-5.1/(4*pi*pi).*x1.^2+5/pi.*x1-6).^2+10.*(1-1/(8*pi)).*cos(x1)+10; end
a .二进制转换为十进制:decodechrom.m
function temp=decodechrom(pop,spoint,length )
pop1=pop(:,spoint:spoint+length-1); %按变量个数分组转换,spoint 为起始点,length 为一个变量的长度
temp=decodebinary(pop1); end
b .求二进制串对应的十进制数:decodebinary.m function temp =decodebinary( pop)
[px,py]=size(pop); %求pop 行数和列数 for i=1:py
pop1(:,i)=2.^(py-i).*pop(:,i); end
temp=sum(pop1,2); %每一行求和 end
(4)计算个体适应度:calfitvalue.m function fitvalue= calfitvalue( objvalue ) fitvalue=1./(1+exp(objvalue)); end
(5)种群中最大适应度个体及其值:best.m
function [bestindividual,bestfit] = best(pop,fitvalue ) [px,py]=size(pop);
bestindividual=pop(1,:); bestfit=fitvalue(1); for i=2:px;
if fitvalue>bestfit
bestindividual=pop(i,:); best=fitvalue(i); end end end
(6)选择算子:selection.m
function [newpop1]=selection(pop,fitvalue) totalfit=sum(fitvalue); %适应度和
ps=fitvalue./totalfit; %单个个体被选择的概率 pss=cumsum(ps); %前几项累积和 [px,py]=size(pop);
ms=sort(rand(px,1)); %随机产生px 个0,1之间的数,并按升序排列 fitin=1; newin=1;
while newin
if(ms(newin)
newpop1(newin,:)=pop(fitin,:); newin=newin+1; else
fitin=fitin+1; end end end
(7)交叉算子:crossover.m
function [newpop2] = crossover( pop,pc ) [px,py]=size(pop);
newpop2=ones(size(pop)); for i=1:2:px-1 if rand
cpoint=round(rand*py); %随机产生一个交叉位
newpop2(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)]; %交换相邻两个个体交叉位之后的基因
newpop2(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)]; else
nwepop2(i,:)=pop(i,:);
newpop2(i+1,:)=pop(i+1,:); end end end
(8)变异算子:mutation.m
function [newpop3] = mutation( pop,pm ) [px,py]=size(pop); newpop3=pop; for i=1:px
if(rand
mpoint=round(rand*py); %随机产生一个变异位 if mpoint
if (newpop3(i,mpoint)==0) %变为等为基因 newpop3(i,mpoint)=1; else
newpop3(i,mpoint)=0; end end
end end
二.独立运行程序30次的结果
最好目标函数值:0.398 最差目标函数值:0.445
平均目标函数值:0.403 标准方差:1.886e-004
三.最好的一次结果
最好解:x1=3.145 x2=2.265 最好值:0.398
运行结果及收敛性曲线如下图:
运行结果 收敛性曲线
(3)min f 3(x )=
∑x
i =1
10
2i
s . t . -100≤x i ≤100,i =1, 2, , 10
此问题的全局最优值f min =0。
本题采用十进制编码方式,与二进制编码方式相比较,效率不如二进制,但程序相比简单一些。多次运行,自变量去平均值可得到最好结果。 一.程序
(1)主函数: main.m clear all; clc
popsize=40; %种群规模
chromlength=10; %变量个数,十进制编码 pc=0.8; %杂交概率 pm=0.1; %变异概率 t=0; %进化代数
pop=initpop(popsize,chromlength); %初始种群 while t
[objvalue]=calobjvalue(pop); %计算目标函数值
fitvalue=calfitvalue(objvalue); %计算群体中每个个体的适应度
[bestindividual,bestfit]=best(pop,fitvalue); %计算最佳个体的目标函数值 x(t,:)=bestindividual;
y(t)=sum(x(t,:).*x(t,:)); %每代最优解的值 [newpop1]=selection(pop,fitvalue); %选择算法 [newpop2]=crossover(newpop1,pc); %交叉算法 [newpop3]=mutation(newpop2,pm); %变异算法 objvalue1=calobjvalue(newpop3(1,:)); if objvalue1>y(t)
newpop3(1,:)=bestindividual; %保留最佳个体 end
pop=newpop3; %产生新种群 end
y; %每代的最佳目标函数值
x; %每代的最佳目标函数值对应的自变量
[gy,k]=min(y) %gy为全局最优值,k 为最优值对应的进化代数 x=x(k,:) %全局最优值对应的自变量 plot(y) %最优值收敛曲线 title('收敛性曲线'); xlabel('进化代数'); ylabel('函数值'); axis([0,5000,0,1]);
(2)初始种群:initpop.m
function pop=initpop(popsize,chromlength)
pop=-100+200.*rand(popsize,chromlength); %随机产生[-100,100]之间的数 end
(3)计算目标函数值::calobjvalue.m function [objvalue] =calobjvalue( pop ) [px,py]=size(pop); for i=1:py
x(:,i)=pop(:,i); end
objvalue=sum(x.*x,2); end
(4)计算个体适应度:calfitvalue.m function fitvalue= calfitvalue( objvalue ) fitvalue=1./objvalue; end
(5)种群中最大适应度个体及其值:best.m
function [bestindividual,bestfit] = best(pop,fitvalue ) [px,py]=size(pop);
bestindividual=pop(1,:); bestfit=fitvalue(1); for i=2:px;
if fitvalue>bestfit
bestindividual=pop(i,:); best=fitvalue(i); end end end
(6)选择算子:selection.m
function [newpop1]=selection(pop,fitvalue) totalfit=sum(fitvalue); %适应度和 if(fitvalue==0) newpop1=pop; else
ps=fitvalue./totalfit; %单个个体被选择的概率 pss=cumsum(ps); %前几项累积和 [px,py]=size(pop);
ms=sort(rand(px,1)); %随机产生px 个[0,1]之间的数,并按升序排列 fitin=1; newin=1;
while newin
if(ms(newin)
newpop1(newin,:)=pop(fitin,:); newin=newin+1; else
fitin=fitin+1; end end
end end
(7)交叉算子:crossover.m
function [newpop2] = crossover( pop,pc ) [px,py]=size(pop);
newpop2=ones(size(pop)); for i=1:2:px-1 for j=1:py
if rand
newpop2(i,j)=a*pop(i,j)+(1-a)*pop(i+1,j); %算数交叉 newpop2(i+1,j)=a*pop(i+1,j)+(1-a)*pop(i,j); else
newpop2(i,j)=pop(i,j);
newpop2(i+1,j)=pop(i+1,j); end end end end
(8)变异算子:mutation.m
function [newpop3] = mutation( pop,pm ) [px,py]=size(pop); newpop3=pop;
for i=1:px %每一个点以概率pm 变为等为基因 for j=1:py
if(rand
r=-100+200*rand; while(r==pop(i,j))
r=-100+200*rand; end
newpop3(i,j)=r; else
newpop3(i,j)=pop(i,j); end end end
二.独立运行程序30次的结果
最好目标函数值:0.0020 最差目标函数值:0.0120
平均目标函数值:0.0073 标准方差:6.3099e-006
三.最好的一次结果
最好解:x1=0.0034 x2=-0.0184 x3=-0.0080 x4=0.0156 x5=-0.0127 x6=0.0000 x7=-0.0234 x8=0.0131 x9=0.0079 x10=0.0208 最好值:0.0020
运行结果及收敛性曲线如下图:
运行结果 收敛性曲线
2 组合优化问题 多背包问题
max f (x )=cx
x
s .. t Ax ≤b
x =[x 1, x 2, , x n ]
x i ∈{0,1},i =1,2, , n
测试算例:n =15
c =[100, 220, 90, 400, 300, 400, 205, 120, 160, 580, 400, 140, 100, 1300, 650];
T
⎡8
⎢8⎢⎢3⎢⎢5⎢5A =⎢
⎢5⎢0⎢⎢3⎢3⎢⎢⎣3
[1**********]0⎤
[***********][**************]⎥⎥[***********]205⎥
⎥
[***********]6113025⎥[***********]21173025⎥
⎥
[***********]21173525⎥[***********]0⎥
⎥
[***********]1210020⎥[***********]181811020⎥
⎥
[***********]201812020⎥⎦
[***********]
b =[550, 700, 130, 240, 280, 310, 110, 205, 260, 275].
T
最优值为: 4015
一.程序
(1)主函数: main.m clear all; clc
c=[100 220 90 400 300 400 205 120 160 580 400 140 100 1300 650]; A=[8 24 13 80 70 80 45 15 28 90 130 32 20 120 40 8 44 13 100 100 90 75 25 28 120 130 32 40 160 40 3 6 4 20 20 30 8 3 12 14 40 6 3 20 5 5 9 6 40 30 40 16 5 18 24 60 16 11 30 25 5 11 7 50 40 40 19 7 18 29 70 21 17 30 25 5 11 7 55 40 40 21 9 18 29 70 21 17 30 25 0 0 1 10 4 10 0 6 0 6 32 3 0 70 10
3 4 5 20 14 20 6 12 10 18 42 9 12 100 20 3 6 9 30 29 20 12 12 10 30 42 18 18 110 20 3 8 9 35 29 20 16 15 10 30 42 20 18 120 20]; b=[550;700;130;240;280;310;110;205;260;275]; popsize=20; %种群规模 chromlength=15; %变量个数 pc=0.9; %杂交概率 pm=0.2; %变异概率 t=0;
pop=initpop(popsize,chromlength); %随机产生初始种群 while t
pop=repair(pop,A,b,c); %修补算子,修补不满足约束的解 [objvalue]=calobjvalue(pop,c); %计算目标函数值 fitvalue=calfitvalue(objvalue); %计算适应度
[bestindividual,bestfit]=best(pop,fitvalue); %最近个体及其适应度值 x(t,:)=bestindividual; %最佳个体
y(t)=sum(c.*bestindividual); %计算最佳个体的目标函数值 [newpop1]=selection(pop,fitvalue); %选择算子 [newpop2]=crossover(newpop1,pc); %交叉算子 [newpop3]=mutation(newpop2,pm); %变异算子 objvalue1=calobjvalue(newpop3(1,:),c); if objvalue1
newpop3(1,:)=bestindividual; %保留最佳个体 end
if t>1&&y(t)
y(t)=y(t-1); %保证每代结果递增
end
pop=newpop3; %产生新种群 end
y; %每代的最佳目标函数值 [gy,k]=max(y) %全局最优解
x=x(k,:) %全局最优解对应的自变量 plot(y) %收敛曲线 title('收敛性曲线'); xlabel('进化代数'); ylabel('函数值');
axis([0,500,3000,4200]);
(2)初始种群:initpop.m
function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); end
(3)修补算子 repair.m
unction pop= repair(pop,A,b,c) [px,py]=size(pop); [m,n]=size(A); for k=1:px for i=1:m for j=1:n
if(pop(k,j)==1)
t(i,j)=b(i)*c(j)/A(i,j); %计算每一个放入背包中的物资的利润密度 else
t(i,j)=Inf; %未放入背包的物资利润密度为无穷 end end end
for i=1:m
while(sum(A(i,:).*pop(k,:))>b(i)) %判断每一约束,当不满足约束时,将该背包中利润密度最小的物资拿出
[ty,I]=min(t(i,:)); pop(k,I)=0; t(i,I)=Inf; end end end end
(4)计算目标函数值::calobjvalue.m function [objvalue] =calobjvalue( pop,c)
[px,py]=size(pop); for i=1:px
objvalue(i)=sum(c.*pop(i,:)); end end
(5)计算个体适应度:calfitvalue.m function fitvalue= calfitvalue( objvalue ) fitvalue=objvalue; end
(6)种群中最大适应度个体及其值:best.m
function [bestindividual,bestfit] = best(pop,fitvalue ) [px,py]=size(pop);
bestindividual=pop(1,:); bestfit=fitvalue(1); for i=2:px;
if fitvalue>bestfit
bestindividual=pop(i,:); best=fitvalue(i); end end end
(7)选择算子:selection.m
function [newpop1]=selection(pop,fitvalue) totalfit=sum(fitvalue); %适应度和
ps=fitvalue./totalfit; %单个个体被选择的概率 pss=cumsum(ps); %前几项累积和 [px,py]=size(pop);
ms=sort(rand(px,1)); %随机产生px 个0,1之间的数,并按升序排列 fitin=1; newin=1;
while newin
if(ms(newin)
newpop1(newin,:)=pop(fitin,:); newin=newin+1; else
fitin=fitin+1; end end end
(8)交叉算子:crossover.m
function [newpop2] = crossover( pop,pc ) [px,py]=size(pop);
newpop2=ones(size(pop)); for i=1:2:px-1 if rand
cpoint=round(rand*py); %随机产生一个交叉位
newpop2(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)]; %交换相邻两个个体交叉位之后的基因
newpop2(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)]; else
nwepop2(i,:)=pop(i,:);
newpop2(i+1,:)=pop(i+1,:); end end end
(9)变异算子:mutation.m
function [newpop3] = mutation( pop,pm ) [px,py]=size(pop); newpop3=pop;
for i=1:px %每一位都以概率pm 产生变异 for j=1:py
if(rand
if (newpop3(i,j)==0) newpop3(i,j)=1; else
newpop3(i,j)=0; end end end
end end
二.独立运行程序30次的结果
最好目标函数值:4015 最差目标函数值:3995 平均目标函数值:4012.7 标准方差:25.4023
三.最好的一次结果
最好解:x=[**************] 最好值:4015
运行结果和收敛性曲线如下图:
运行结果
收敛性曲线