实验五：遗传算法求解函数最值问题实验

..实验五：遗传算法求解函数最值问题实验实验目的使用遗传算法求解函数

在及y的最大值。实验容使用遗传算法进展求解，篇末所附源代码中带有算法的详细注释。算法中涉及不同的参数，参数的取值需要根据实际情况进展设定，下面运行时将给出不同参数的结果比照。定义整体算法的完毕条件为，当种群进化次数到达maxGeneration时停顿，此时种群中的最优解即作为算法的最终输出。设种群规模为N，首先是随机产生N个个体，实验中定义了类型Chromosome表示一个个体，并且在默认构造函数中即进展了随机的操作。然后程序进展假设干次的迭代，在每次迭代过程中，进展选择、穿插及变异三个操作。1.选择操作首先计算当前每个个体的适应度函数值，这里的适应度函数即为所要求的优化函数，然后归一化求得每个个体选中的概率，然后用轮盘赌的方法以允许重复的方式选择选择N个个体，即为选择之后的群体。但实验时发现结果不好，经过仔细研究之后发现，这里在x、y取某些值的时候，目标函数计算出来的适应值可能会出现负值，这时如果按照把每个个体的适应值除以适应值的总和的进展归一化的话会出现问题，因为个体可能出现负值，总和也可能出现负值，如果归一化的时候除以了一个负值，选择时就会选择一些不良的个体，对实验结果造成影响。对于这个问题，我把适应度函数定为目标函数的函数值加一个正数，保证得到的适应值为正数，然后再进展一般的归一化和选择的操作。实验结果说明，之前的实验结果很不稳定，修正后的结果比拟稳定，趋于最大值。2.穿插操作首先是根据穿插概率probCross选择要穿插的个体进展穿插。 这里根据穿插参数crossnum进展多点穿插，首先随机生成穿插点位置，允许穿插点重合，两个重合的穿插点效果互相抵消，相当于没有穿插点，然后根据穿插点进展穿插操作，得到新的个体。3.变异操作首先是根据变异概率probMutation选择要变异的个体。变异时先随机生成变异的位置，然后把改位的01值翻转。经过一定的进化之后得到最终种群，从中选择最优的个体即可得到最终的结果。4.运行结果借助matlab软件，我们可以知道该函数在该定义域下的图像为:以下设置不同的参数值进展比照试验：表1不同参数的比照实验NlencrossnummaxGenerationprobCrossprobMutate实验一实验二11010410000.850.152.614332042.7469711725010450000.850.152.871765122.88383150320020450000.850.152.892027452.893073594200304100000.850.152.894406562.888525515200305100000.80.22.888068212.8916507363004041000000.850.152.893637392.89445359以上我们主要对种群规模N，个体染色体长度len，迭代次数maxGeneration进展比拟。可以看出，随着种群规模的增大，染色体长度的增长，迭代次数的增加，算法得到的结果越来越准确。当参数规模到达一定程度时，再增加参数的值会明显地增加程序运行时间，但却不一定能明显改善解的质量，反而可能因为一些随机因数而产生质量更差的解，如第6组实验一所示。同时也大概比拟了一下多点穿插的穿插点个数crossnum，穿插概率probCross，变异概率probMutate等参数，由于参数太多，这里没有一一进展控制变量的比拟。大致估算可知，穿插概率及穿插点的个数影响穿插操作产生新个体的质量，过多的穿插及变化过大的穿插可能会产生不好的结果，而过多的变异也应该会造成算法的不稳定。下面给出以上几个实验结果的实验截图，其中到现在为止结果最好的一个为：其余假设干个为：5.实验代码改良后的源代码如下：#include<iostream>#include<iomanip>#include<algorithm>#include<cmath>#include<ctime>usingnamespacestd;//程序欲分配存的数组大小constintmxn=10000; //最大的种群规模constintmxlen=1000; //最大的染色体长度//遗传算法关键参数constintN=200; //种群的个体数constintlen=30; //每个个体的染色体的长度，x和y各占一半constintcrossnum=4; //穿插操作时多点穿插的穿插点个数constintmaxGeneration=2000; //最大进化代数constdoubleprobCross=0.85; //穿插概率constdoubleprobMutation=0.15; //变异概率//个体的染色体类classChromosome{public: boolg[mxlen]; //二进制编码的编码数组 Chromosome() //默认构造函数，构造随机染色体 { for(inti=0;i<len;i++) g[i]=rand()%2; } Chromosome(constChromosome&c) //拷贝构造函数，进展深复制 { for(inti=0;i<len;i++) g[i]=c.g[i]; } voidoperator=(constChromosome&c) //重载=号，进展深复制 { for(inti=0;i<len;i++) g[i]=c.g[i]; }};doublebestval; //记录当前所得的最优值ChromosomebestC; //记录当前最优值对应的个体染色体Chromosomegroup[mxn],temGroup[mxn]; //个体的种群，辅助数组//目标函数doublef(doublex,doubley){ returnx*sin(6*y)+y*cos(8*x);}//解码函数，从染色体得到x和y的值voiddecode(constChromosome&c,double&x,double&y){ doublenum=pow(2.0,len/2.0); inttem=0; for(inti=len-1,q=1;i>=len/2;i--) tem+=c.g[i]*q,q=q*2; y=1+(2-1)/num*tem; tem=0; for(inti=len/2-1,q=1;i>=0;i--) tem+=c.g[i]*q,q=q*2; x=1+(2-1)/num*tem;}//适应度函数，为防止负值，把目标函数加一个正数doublefitness(constChromosome&c){ doublex,y; decode(c,x,y); returnf(x,y)+5;}//辅助函数，生成0-1之间的随机小数doubleinlinerandom01(){ returnrand()%10000/10000.0;}//选择操作voidselect(Chromosomegroup[mxn]){ //计算每个个体的选择概率 doublefitnessVal[mxn]; for(inti=0;i<N;i++) fitnessVal[i]=fitness(group[i]); doublesum=0; for(inti=0;i<N;i++) sum+=fitnessVal[i]; doubleprob[mxn]; for(inti=0;i<N;i++) prob[i]=fitnessVal[i]/sum; //随机选择N个个体组成新种群 intselectId[mxn]; for(inti=1;i<N;i++) prob[i]+=prob[i-1]; for(inti=0;i<N;i++) { //使用轮盘赌算法选择个体 doublerandNum=random01(); intj; for(j=0;j<N-1;j++) { if(randNum<prob[j]) { selectId[i]=j; break; } } if(j==N-1) selectId[i]=j; } //把种群更新为新选择的个体集合 for(inti=0;i<N;i++) temGroup[i]=group[i]; for(inti=0;i<N;i++) group[i]=temGroup[selectId[i]];}//穿插操作，使用多点穿插voidcrossover(Chromosome&c1,Chromosome&c2){ //生成穿插点位置，并排序 intcrosspoint[mxn]; for(inti=0;i<crossnum;i++) crosspoint[i]=rand()%len; sort(crosspoint,crosspoint+crossnum); //进展穿插 boolflag=0; for(inti=0,j=0;i<len;i++) { if(!flag) swap(c1.g[i],c2.g[i]); if(i==crosspoint[j]) { //如果假设干个穿插点重合，那么效果叠加 //偶数个穿插点效果相当于没有穿插点 while(j<crossnum&&i==crosspoint[j]) { j++; flag=!flag; } } }}//变异操作voidmutate(Chromosome&c){ //随机选择一位进展翻转 inti=rand()%len; c.g[i]=!c.g[i];}//获取种群最优个体intgetOptimal(Chromosomegroup[mxn],double&x,double&y,double&val){ //计算适应值，遍历得到最优值并进展解码 doublefitnessVal[mxn]; for(inti=0;i<N;i++) fitnessVal[i]=fitness(group[i]); intid=0; for(inti=1;i<N;i++) if(fitnessVal[i]>fitnessVal[id]) id=i; decode(group[id],x,y); val=f(x,y); returnid;}//遗传算法总代码voidGA(double&x,double&y,double&val){ //初始化种群 for(inti=0;i<N;i++) group[i]=Chromosome(); // bestC=group[getOptimal(group,x,y,bestval)]; //控制进化代数 for(intg=0;g<maxGeneration;g++) { //选择操作 select(group); //根据穿插概率进展穿插 for(inti=0,pre=-1;i<N;i++) { if(random01()<probCross) { if(pre==-1) pre=i; else { crossover(group[pre],group[i]); pre=-1; } } } //根据变异概率进展变异 for(inti=0;i<N;i++) if(random01()<probMutation) mutate(group[i]); //防止种群退化 doubletemval; intbestId=getOptimal(group,x,y,temval); if(temval<bestval) { //如果新种群的最优值变差，把较优的个体替换进新种群 group[bestId]=bestC; } else { //如果新种群的最优值变好，那么更新最优值记录 bestC=group[bestId]; bestval =temval; } } //获取最优值 getOptimal(group,x,y,val);}intmain(){ srand(time(0)); doublex,y,maxval; GA(x,y,maxval); cout<<"函数在点("<<fixed<<setprecision(15)<<x<<","