遗传算法用于函数优化

遗传算法用于函数优化求解
一、实验目的
本实验要求在掌握遗传算法的基本 思想、原理和算法流程的基础上，能够针
对指定的单变量优化目标函数，设计相应的遗传算法优化程序， 并求得全局最优
解。
二、实验要求
2
y?1?(x?1),x?[0,2 ]
，设计利用遗传算法进行优化求解的程针对目标函数
序，绘制迭代过程中最优解的变化情况， 并分别改变算法中的编码位数、种群规
模、交叉和变异概率，分析这些变量对算法精度及收敛性的影响。
三、实验步骤
1、初始化种群，确定种群规模M=20，编码位数n=5 和编码机制(二进制编
码)；
初始化种群：E = round(rand(M,n))；
每个编码对应的二进制数值：
y?
?
y
i
?2
(i ?1)
i

y
i
为第i位二进制代码；
二进制数y转换 为十进制数x：
x?
x
max
?x
min
*y?x
min
2
n
?1
；
2、根据给定的目标函数，计算各个种群的适应度值；
3、采用轮盘选择法对种群进行选择复制；
4、设定交叉概率为0.9，进行遗传操作（交叉）；
5、设定变异概率0.05，进行遗传操作（变异）；
6、产生下一代种群，与终止条件比较，不满足返回到步骤2直到满足条件
退出。
算法的流程如图7.1所示。

计算适应度函数
开始
初始化种群（编码）
选择、复制
交叉、变异
Y
达到系统指标？
N
迭代次数达上限？
输出结果
结束
图7.1 算法流程图
四、实验结果及分析
我们采用遗传算法来寻求目标函数的最大值。初始化样本个数为20个， 编
码位数为5位，采用二进制编码，交叉概率为0.9，变异概率为0.05，最大迭代
次数为 1000次，初始样本随机选择，当父代与子代间适应度变化小于0.001时，
达到系统指标。MAT LAB模拟运行输出迭代种群的平均适应度变化、种群的最优
解与最差解，绘出图像（见图1），计算运 行时间的平均值（见表1），由表可知，
平均运行时间约为0.65秒左右，速度较快。由图可知，前期 平均适应度是不断
上升的，到达一定程度后即平均适应度在0.9以上后，就基本处于波动平衡状态。< /p>

通过对遗传算法的分析，这是因为种群内的所有个体几乎都已经接近最优值，上
升 空间比较小，且由于有变异的可能性，所以平均适应度在后期处于波动状态。
由图可发现，每代的最大值 都差不多，几乎都是1，但每代的最小值的变化就比
较多了，但从趋势可以基本看出，最小值在逐渐变大 ，向最大值靠拢。因为要找
的最优解是最大值，所以在迭代过程中，最小值淘汰几率最大，它的基因难以 遗
传下来，因此最小值会逐渐变大。

图 1
表 1
次数
时间（s）
最大值
最小值
第一次
0.700
1
0.8594
第二次
0.621
0.9961
0.8086
第三次
0.622
0.9961
0.8594
第四次
0.598
0.9961
0.8086
第五次
0.669
0.9961
0.3398
平均
0.642
0.99688
0.73516

改变初始种群的规模，其他参数不变，多次运行程序，观察初始种 群规模大
小对此算法的影响。图2为种群规模为10时，种群适应度的变化及每代最大值
和最小 值，由图可看到，平均适应度大的趋势是上升的，虽然过程中有些因为变
异引起的曲折，每代的最大值基 本相似，但最小值是近似地随着平均适应度的曲
线变化的，可以推测，最小值影响了平均适应度。表2是 种群规模为10时，其

每次运行时间和得到的最终最大值最小值，由表可见，运行平均时 间为0.6s左
右，最终获得的最大值和最小值差距极小，且获得最大值与实际目标函数的最大
值差距较大。图3与表3为种群规模为200时的情况，从图中可发现，平均适应
度上升较缓，波动较小 ，且每代最大值最小值差距较大，又由表3可看出，其运
行时间为0.75s左右，每次运行最终最大值 几乎都为1，最小值接近0，与目标
函数的最大值基本相同。对比种群规模分别为10(图2，表2)， 20（图1，表1），
200（图3，表3），可以发现，种群规模越大，平均适应度的波动越小，上升 坡
度越平缓，且最终获得的最大值和最小值的差别越大，最大值越接近目标函数的
实际最大值。 由此可分析出，当种群规模小时，单个个体的基因对整个群体的适
应度影响比较大，因此只有当整个群体 中适应度最差的个体也达到一个较高适应
度后，才达到系统标准（这一代与上一代的平均适应度差小于0 .001），退出循
环，而这样，最终的最小值就会接近最大值，种群内部每个个体的差别很小，最大值很难达到目标函数的最大值。而当种群规模大时，单个个体的基因对整个群
体的适应度就没有那 么大的影响，只要大多数个体的基因达到较高适应度，就能
够满足系统标准，退出循环，因此每次迭代的 最高适应度的个体与最低适应度的
个体几乎可以共存，最终获得的最大值几乎就是目标函数的最大值，最 小值也接
近目标函数的小的值。

图 2

表 2
次数
（M=10）
第一次
时间（s）
最大值
最小值

0.570
0.9648
0.9648
第二次
0.654
0.9648
0.8086
第三次
0.611
0.9375
0.9375
第四次
0.590
0.9961
0.9844
第五次
0.589
0.9023
0.9023
平均
0.6028
0.9531
0.91952

图 3
表 3
次数
（M=200）
第一次
时间（s）
最大值
最小值

0.736
1
0.1211
第二次
0.680
1
0.2344
第三次
0.798
1
0.5273
第四次
0.798
1
0
第五次
0.715
1
0
平均
0.7454
1
0.17656
初始种群 的规模为20，降低交叉的概率为0.4，其他参数不变，多次运行程
序，观察结果（见图4，表4）。 对比交叉概率为0.9的情况（见图1，表1），发
现种群平均适应度的变化曲线没有太大差别，都是波 动上升的，所用时间差别也
不大，都为0.64s左右，最终获得的最大值也差别不大，唯一差别较大的 是最终
获得的最小值，交叉概率低的最小值大于交叉概率高的最小值。这是因为子代是
由父代中 适应度高的个体进行交叉变异而来，变异概率极低（0.05），可忽略，
当交叉概率低时，子代个体基 本是由父代中适应度高的个体（即目标函数值大的

个体）复制粘贴而来，所以最终获得的 最小值比较大，而交叉概率高时，子代个
体多是由父代优秀个体交叉变换而来，可能会使某些子代适应度 稍微降低，某些
又稍微升高，所以相比交叉概率低的时候，最终获得的最小值比较小。

图 4
表 4
次数
时间（s）
最大值
最小值

第一次
0.648
0.9961
0.9375
第二次
0.620
0.9844
0.8594
第三次
0.670
0.9961
0.9375
第四次
0.621
0.9844
0.8594
第五次
0.644
1
0.8594
平均
0.6406
0.9922
0.89064
初始种群的规模为20，交叉的概率为0.9，变异概率增加至0.5，其他 参数
不变，多次运行程序，观察结果（见图5，表5）。由图5发现，平均适应度一直
处于在0 .7和0.9之间上下剧烈波动的情况，没有不断上升的趋势，说明变异几
率太大，导致种群无法收敛于 一个稳定的最佳状态，由表5可知，改变变异概率
对运行时间，最终能达到的最大值影响不大，但影响了 最小值，因为变异的概率
高，所以种群不断地有适应度极低的变异个体出现，所以最终的最小值较小，但
也导致了种群无法收敛的情况。由此可知，变异概率不能太大，不然种群无法收
敛到最优解附近 。

图 5
表 5
次数
时间（s）
最大值
最小值

第一次
0.669
0.9961
0.1211
第二次
0.615
0.9961
0.1211
第三次
0.632
1
0
第四次
0.623
1
0.3398
第五次
0.648
1
0.3398
平均
0.6374
0.99844
0.18436
初始种群的规模为20，交叉的概率为0.9，变异概率为0.05，改变编 码位数
分别为8位、5位、3位，其他参数不变，多次运行程序，观察结果（见图6，表6，
图 7，表7）。图6及表6是编码位数为3位时的情况，图1及表1的编码位数为5位，
图7及表7是编码 位数为8位时的情况。由图6、图1、图7的平均适应度对比发现，
虽然适应度曲线基本是上升趋势，但 编码位数为3时，波动较大，而编码位数为5
和8时，适应度曲线相似，波动都较小。对比每代的最大值 最小值发现，最小值
对波动的影响都比较大。由表6、表1、表7发现，运行的平均时间都差不多，都< br>是0.6s多，每次运行最终获得的最大值也差不多，但最小值就差别较大。当编码
位数较少时， 最小值较小，编码位数较多时，最小值较大。这是因为当编码位数
少时，目标函数y=1-(x-1)^ 2的x取值就比较有限，比如编码位数为3时，x最多只
能在0到2之间均匀取8个数，而当编码位数为 8时，能最多取256个数，取的数越

多，个体与个体间的最小差异就越小，因此编码位 数多时，平均适应度的波动会
比较小，且最终达到的整体平均适应度相对较高，最终最小值也比较大。而 编码
位数少时正好相反。但对比编码位数分别为5和8的情况，我们发现编码位数也
不是越多越 好，它们最终达到的最大值基本相似，适应度曲线也相似，由此可知
道，编码位数到达一定程度后不会再 对平均适应度造成很大影响，而编码位数少
时，对我们来说，复杂程度也比较低，所以编码位数选择适中 较好。

图 6
表 6
次数
时间（s）
最大值
最小值
第一次
0.639
1
0.7500
第二次
0.653
1
0.9375
第三次
0.599
0.9375
0.9375
第四次
0.600
1
0
第五次
0.608
1
0 .4375
平均
0.6198
0.9875
0.65625

图 7
表 7
次数
时间（s）
最大值
最小值

第一次
0.642
0.9970
0.9677
第二次
0.634
0.9998
0.9413
第三次
0.626
0.9970
0.8412
第四次
0.652
0.9995
0.9780
第五次
0.622
0.9802
0.8350
平均
0.6352
0.9947
0.91264
通过实验对比分析发现，种群规模是影响适应度及最终获得的最优解的一个< br>重要因素，当种群规模大时，适应度曲线的上升程度比较平缓，且获得的最优值
更接近实际的最优 解。另外，变异概率不能过大，否则适应度曲线没有上升的趋
势，一直处于波动状态，种群无法收敛于最 优解附近。编码位数不宜过少，不然
适应度曲线波动较大，不那么容易收敛，最终达到的整体适应度较低 ，编码位数
也不应过多，适中最好。
五、MATLAB编程代码

function genetic1
%遗传算法
%目标函数y=1-(x-1)^2;
M=20; %种群规模
%n=5; %编码位数
n=8; %编码位数

p_crossover=0.9; %交叉概率
p_mutation=0.05; %变异概率
parent_adptability=[]; %父代种群适应度
children_adptability=[]; %子代种群适应度
variance_adptability=0; %适应度变化
adptability=[]; %每次迭代适应度
times=1000; %最大迭代次数
time=0; %实际迭代次数
y_sum=[];
y_min=[];
y_max=[];
%y_y=[];
E = round(rand(M,n));%初始化种群
x=[]; %存相应的十进制
%-------------求适应 度----------------------------------
for j=1:M %二进制转十进制
e=0;
for i=1:n
e=E(j,i)+e*2;
end
%e=e16; %使x在【0，2】之间
e=e128; %使x在【0，2】之间
x=[x;e];
end
y=1-(x-1).^2; %目标函数
%y_y=[y_y,y];
ysum=0;
for j=1:M %求和
ysum=y(j,1)+ysum;
end
parent_adptability=;%父代的适应度
parent_ave=ysumM; %父代的目标函数平均值
adptability=[adptability;parent_ave];
y_max=[y_max;max(y)];
y_min=[y_min;min(y)];
%----------------end ---------------------------------
%----------- -遗传算法--------------------------------
for k=1:times
%--------------选择------------------------
y_E = rand(M,1); %随机数M个
y_distributeProbability=[];
for j=1:M %概率分区【0，1】
y_probability=0;
for i=1:j

y_probability=parent_adptability(i,1)+ y_probability;
end

y_d istributeProbability=[y_distributeProbability;y_pr obability];
end
%y_distributeProbability
E_new=[];
for j=1:M %选择个体
for i=1:M
if y_E(j,1)<=y_distributeProbability(i,1)
E_new=[E_new;E(i,:)];
break;
end
end
end
%--------------交叉变异------------------------
E_new_new=[]; %子代
k=(n-0)p_mutation;
for j=1:M2
a=rand(1);
b1=rand(1);
b2=rand(1);
if a>p_crossover %交叉
E_new_new=[E_new_new;E_new(j,:);E_new(j+M2,:)];
continue;
else
A=E_new(j,:);
E_new(j+M2,:);
E_new(j,1:2)=E_new(j+M2,1:2);
E_new(j+M2,1:2)=A(1,1:2);
E_new(j,:);
E_new(j+M2,:);
E_new_new=[E_new_new;E_new(j,:);E_new(j+M2,:)];
end
if(b1>p_mutation) %变异

else
b1=floor(b1*k)+1;
if(E_new_new(j,b1)==0)
E_new_new(j,b1)=1;
else
E_new_new(j,b1)=0;
end
end

if(b2>p_mutation)
;
else
b2=floor(b2*k)+1;
if(E_new_new(j+1,b2)==0)
E_new_new(j+1,b2)=1;
else
E_new_new(j+1,b2)=0;
end
end

end
%-------------求适应度------- ---------------------------
x=[];
for j=1:M %二进制转十进制
e=0;
for i=1:n
e=E_new_new(j,i)+e*2;
end
%e=e16;
e=e128; %使x在【0，2】之间
x=[x;e];
end
y=1-(x-1).^2;
ysum=0;
for j=1:M %求和
ysum=y(j,1)+ysum;
end
children_adptability=;%子代适应度
children_ave=ysumM; %子代目标函数平均值
adptability=[adptability;children_ave];
y_max=[y_max;max(y)];
y_min=[y_min;min(y)];
%----------------退出条件及下次 迭代准备---------------------
variance_adptability=abs(children_ave- parent_ave);%两代的变化率
if variance_adptability<0.001 %退出条件
break;
end
parent_adptability=children_adptability;
parent_ave=children_ave;
time=time+1;
E=E_new_new;
%plot(x,y,'c.');%画分类结果图
end

time1=1:time+2;
subplot(2,1,1)
plot(time1,adptability);%画平均适应度折线图
grid on;
title('平均适应度折线图');
xlabel('迭代次数');
ylabel('平均适应度');
x=1:M;
subplot(2,1,2)
plot(time1,y_max,'r*',time1,y_min,'b*')
legend('最大值','最小值')
title('每代最大值最小值散点图');
xlabel('代数');
ylabel('y=1-(x-1)^2');
max(y)
min(y)