遗传算法用于函数优化

遗传算法用于函数优化遗传算法用于函数优化求解一、实验目的本实验要求在掌握遗传算法的基本思想、原理和算法流程的基础上，能够针对指定的单变量优化目标函数，设计相应的遗传算法优化程序，并求得全局最优解。二、实验要求针对目标函数21(1),[0,2]yxx，设计利用遗传算法进行优化求解的程序，绘制迭代过程中最优解的变化情况，并分别改变算法中的编码位数、种群规模、交叉和变异概率，分析这些变量对算法精度及收敛性的影响。三、实验步骤1、初始化种群，确定种群规模M=20，编码位数n=5和编码机制(二进制编码)；初始化种群：E=round(rand(M,n))；每个编码对应的二进制数值：(1)2iiiyyiy为第i位二进制代码；二进制数y转换为十进制数x：maxminmin*21nxxxyx；2、根据给定的目标函数，计算各个种群的适应度值；3、采用轮盘选择法对种群进行选择复制；4、设定交叉概率为0.9，进行遗传操作（交叉）；5、设定变异概率0.05，进行遗传操作（变异）；6、产生下一代种群，与终止条件比较，不满足返回到步骤2直到满足条件退出。算法的流程如图7.1所示。NY结束输出结果迭代次数达上限？开始初始化种群（编码）计算适应度函数交叉、变异选择、复制达到系统指标？图7.1算法流程图四、实验结果及分析我们采用遗传算法来寻求目标函数的最大值。初始化样本个数为20个，编码位数为5位，采用二进制编码，交叉概率为0.9，变异概率为0.05，最大迭代次数为1000次，初始样本随机选择，当父代与子代间适应度变化小于0.001时，达到系统指标。MATLAB模拟运行输出迭代种群的平均适应度变化、种群的最优解与最差解，绘出图像（见图1），计算运行时间的平均值（见表1），由表可知，平均运行时间约为0.65秒左右，速度较快。由图可知，前期平均适应度是不断上升的，到达一定程度后即平均适应度在0.9以上后，就基本处于波动平衡状态。通过对遗传算法的分析，这是因为种群内的所有个体几乎都已经接近最优值，上升空间比较小，且由于有变异的可能性，所以平均适应度在后期处于波动状态。由图可发现，每代的最大值都差不多，几乎都是1，但每代的最小值的变化就比较多了，但从趋势可以基本看出，最小值在逐渐变大，向最大值靠拢。因为要找的最优解是最大值，所以在迭代过程中，最小值淘汰几率最大，它的基因难以遗传下来，因此最小值会逐渐变大。图1表1次数第一次第二次第三次第四次第五次平均时间（s）0.7000.6210.6220.5980.6690.642最大值10.99610.99610.99610.99610.99688最小值0.85940.80860.85940.80860.33980.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.5700.6540.6110.5900.5890.6028最大值0.96480.96480.93750.99610.90230.9531最小值0.96480.80860.93750.98440.90230.91952图3表3次数（M=200）第一次第二次第三次第四次第五次平均时间（s）0.7360.6800.7980.7980.7150.7454最大值111111最小值0.12110.23440.5273000.17656初始种群的规模为20，降低交叉的概率为0.4，其他参数不变，多次运行程序，观察结果（见图4，表4）。对比交叉概率为0.9的情况（见图1，表1），发现种群平均适应度的变化曲线没有太大差别，都是波动上升的，所用时间差别也不大，都为0.64s左右，最终获得的最大值也差别不大，唯一差别较大的是最终获得的最小值，交叉概率低的最小值大于交叉概率高的最小值。这是因为子代是由父代中适应度高的个体进行交叉变异而来，变异概率极低（0.05），可忽略，当交叉概率低时，子代个体基本是由父代中适应度高的个体（即目标函数值大的个体）复制粘贴而来，所以最终获得的最小值比较大，而交叉概率高时，子代个体多是由父代优秀个体交叉变换而来，可能会使某些子代适应度稍微降低，某些又稍微升高，所以相比交叉概率低的时候，最终获得的最小值比较小。图4表4次数第一次第二次第三次第四次第五次平均时间（s）0.6480.6200.6700.6210.6440.6406最大值0.99610.98440.99610.984410.9922最小值0.93750.85940.93750.85940.85940.89064初始种群的规模为20，交叉的概率为0.9，变异概率增加至0.5，其他参数不变，多次运行程序，观察结果（见图5，表5）。由图5发现，平均适应度一直处于在0.7和0.9之间上下剧烈波动的情况，没有不断上升的趋势，说明变异几率太大，导致种群无法收敛于一个稳定的最佳状态，由表5可知，改变变异概率对运行时间，最终能达到的最大值影响不大，但影响了最小值，因为变异的概率高，所以种群不断地有适应度极低的变异个体出现，所以最终的最小值较小，但也导致了种群无法收敛的情况。由此可知，变异概率不能太大，不然种群无法收敛到最优解附近。图5表5次数第一次第二次第三次第四次第五次平均时间（s）0.6690.6150.6320.6230.6480.6374最大值0.99610.99611110.99844最小值0.12110.121100.33980.33980.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发现，运行的平均时间都差不多，都是0.6s多，每次运行最终获得的最大值也差不多，但最小值就差别较大。当编码位数较少时，最小值较小，编码位数较多时，最小值较大。这是因为当编码位数少时，目标函数y=1-(x-1)^2的x取值就比较有限，比如编码位数为3时，x最多只能在0到2之间均匀取8个数，而当编码位数为8时，能最多取256个数，取的数越多，个体与个体间的最小差异就越小，因此编码位数多时，平均适应度的波动会比较小，且最终达到的整体平均适应度相对较高，最终最小值也比较大。而编码位数少时正好相反。但对比编码位数分别为5和8的情况，我们发现编码位数也不是越多越好，它们最终达到的最大值基本相似，适应度曲线也相似，由此可知道，编码位数到达一定程度后不会再对平均适应度造成很大影响，而编码位数少时，对我们来说，复杂程度也比较低，所以编码位数选择适中较好。图6表6次数第一次第二次第三次第四次第五次平均时间（s）0.6390.6530.5990.6000.6080.6198最大值110.9375110.9875最小值0.75000.93750.937500.43750.65625图7表7次数第一次第二次第三次第四次第五次平均时间（s）0.6420.6340.6260.6520.6220.6352最大值0.99700.99980.99700.99950.98020.9947最小值0.96770.94130.84120.97800.83500.91264通过实验对比分析发现，种群规模是影响适应度及最终获得的最优解的一个重要因素，当种群规模大时，适应度曲线的上升程度比较平缓，且获得的最优值更接近实际的最优解。另外，变异概率不能过大，否则适应度曲线没有上升的趋势，一直处于波动状态，种群无法收敛于最优解附近。编码位数不宜过少，不然适应度曲线波动较大，不那么容易收敛，最终达到的整体适应度较低，编码位数也不应过多，适中最好。五、MATLAB编程代码functiongenetic1%遗传算法%目标函数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=[];%存相应的十进制%-------------求适应度----------------------------------forj=1:M%二进制转十进制e=0;fori=1:ne=E(j,i)+e*2;end%e=e/16;%使x在【0，2】之间e=e/128;%使x在【0，2】之间x=[x;e];endy=1-(x-1).^2;%目标函数%y_y=[y_y,y];ysum=0;forj=1:M%求和ysum=y(j,1)+ysum;endparent_adptability=y./ysum;%父代的适应度parent_ave=ysum/M;%父代的目标函数平均值adptability=[adptability;parent_ave];y_max=[y_max;max(y)];y_min=[y_min;min(y)];%----------------end---------------------------------%------------遗传算法--------------------------------fork=1:times%--------------选择------------------------y_E=rand(M,1);%随机数M个y_distributeProbability=[];forj=1:M%概率分区【0，1】y_probability=0;fori=1: