使用遗传算法求解函数最大值.docx
- 文档编号:7536297
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:16
- 大小:77.90KB
使用遗传算法求解函数最大值.docx
《使用遗传算法求解函数最大值.docx》由会员分享,可在线阅读,更多相关《使用遗传算法求解函数最大值.docx(16页珍藏版)》请在冰点文库上搜索。
使用遗传算法求解函数最大值
使用遗传算法求解函数最大值
题目
使用遗传算法求解函数
在及y的最大值。
解答
算法
使用遗传算法进行求解,篇末所附源代码中带有算法的详细注释。
算法中涉及不同的参
数,参数的取值需要根据实际情况进行设定,下面运行时将给出不同参数的结果对比。
H遥礙厌繇数
intM=209f//
constintlen=//每个个伐的樂色依的长度’占一半
constintcrossnum•4;//交叉擾作时吝点交叉的交叉点个数
constintmaxGtneration*1&O00;//最大进化优数
constdoubleprobCross=0.85;//交叉柢率
ccrsldejtlep^cb'-.utaticn=3.15j//变异探率
定义整体算法的结束条件为,当种群进化次数达到maxGeneration时停止,此时种群中
的最优解即作为算法的最终输出。
//酬iBtg
for(intg=g { 设种群规模为N,首先是随机产生N个个体,实验中定义了类型Chromosome表示一个个体,并且在默认构造函数中即进行了随机的操作。 “初螂■七种群 for(liTt1=0;i group[i]=Ch■'ci'iOGcrrrQi 然后程序进行若干次的迭代,在每次迭代过程中,进行选择、交叉及变异三个操作。 一选择操作 首先计算当前每个个体的适应度函数值,这里的适应度函数即为所要求的优化函数,然后归一化求得每个个体选中的概率,然后用轮盘赌的方法以允许重复的方式选择选择N个 个体,即为选择之后的群体。 Evoidsele匚t(匚h■"onosorrie-[m)cn]) //计算毎 doublefitnessValfniKC]; fitnessVal[i]=fitness(^[i]^J sum4=fitnessVali]; probfi]■fitnessVal[i]/sun; for(irrti=0;ivM;i++)double士Lim二0; ■for(irrti=0;i fop(inti=0;i€M;i++)H随机选攝住细5^种群 intseLectld[msnJ; ■for(inti=1;i { H便用笙盘赌算法询环t doublerandNum=randomOlO;intj; ^ar(j=9;j if(randNum {selectld[i]三j;break^ if(j=・m-1)selectTd[l]=j;} //把种詩更新为新选擇的个建集含 for(int£=9;i t«>Group[l]=「oup[i];group[i]=temGroup[selectl 但实验时发现结果不好,经过仔细研究之后发现,这里在x、y取某些值的时候,目标 函数计算出来的适应值可能会出现负值,这时如果按照把每个个体的适应值除以适应值的总 总和也可能出现负值,如果归一对实验结果造成影响。 对于这保证得到的适应值为正数,然 和的进行归一化的话会出现问题,因为个体可能出现负值, 化的时候除以了一个负值,选择时就会选择一些不良的个体,个问题,我把适应度函数定为目标函数的函数值加一个正数, 后再进行一般的归一化和选择的操作。 实验结果表明,之前的实验结果很不稳定,修正后的结果比较稳定,趋于最大值。 //适应度函数■为童免负值.把目标函勒Lt■正散Fdoublefitne55(const匚nroiriosotrc&c) doublex,y; decode(c,y); returnf(x,y)+5; 交叉操作 首先是根据交叉概率probCross选择要交叉的个体进行交叉。 H限据交叉槪車进行交叉 ■for(inti.=%pre=-1;i ( if(randomSlf) { if(pre==-1)pre=i; else{crossover(group[prc]group[i]);pre=-1; } } } 这里根据交叉参数crossnum进行多点交叉,首先随机生成交叉点位置,允许交叉点重合,两个重合的交叉点效果互相抵消,相当于没有交叉点,然后根据交叉点进行交叉操作,得到新的个体。 "交叉擾ft.使用券点交叉 ^voidcrossovertChrcmoio『亡gcljChromoscmeAc2) { //生威交叉点位置.井排宮 intcrosspointfinxn]; for^inti-Q;i scrt(亡rosspflint^er-05i|M£nt+trassnjffl): boolflag=9; for^inti■0jj-i ( IffIflag) if(i--cro55point[j]) { □H如果若干个交叉点重合.則效果叠町 .//偶数个交叉点效果於于没有交叉点 while^j j++;flag=Iflag; } 三变异操作 首先是根据变异概率probMutation选择要变异的个体。 n根据变异概率遊行变异 for(inti=1 iftrandom01() Evoidnutatuffc) I n随机选择THS齐翻转 inti=rand()驚len^ Fc.g[i]-! c.g[i]- 经过一定的进化之后得到最终种群,从中选择最优的个体即可得到最终的结果。 I//获取WftStt朋 -intgetOptimal(ch-ctics[tnxn]jdoublu&k.double>tdoublu&^1) { H计亘适应值.遍帀得刹最优值井逬齐解冯 doublefitn€55Val[mKTi]j for(inti=0;i fortinti-1;1 if(fltne£sval[i]>fitnes£Val[Ld]) id=i; decode^_roup[id],x, ■jal=f(xty); returniti: 运行结果 借助matlab软件,我们可以知道该函数在该定义域下的图像为 6B数Xxx*sinp*y)-ty*cos(p^)的團像 以下设置不同的参数值进行对比试验: 表1不同参数的对比实验 N len crossnum maxGeneration probCross probMutate 实验一 实验二 1 10 10 4 1000 0.85 0.15 2.61433204 2.74697117 2 50 10 4 5000 0.85 0.15 2.87176512 2.88383150 3 200 20 4 5000 0.85 0.15 2.89202745 2.89307359 4 200 30 4 10000 0.85 0.15 2.89440656 2.88852551 5 200 30 5 10000 0.8 0.2 2.88806821 2.89165073 6 300 40 4 100000 0.85 0.15 2.89363739 2.89445359 以上我们主要对种群规模N,个体染色体长度len,迭代次数maxGeneration进行比较。 可以看出,随着种群规模的增大,染色体长度的增长,迭代次数的增加,算法得到的结果越来越精确。 当参数规模达到一定程度时,再增加参数的值会明显地增加程序运行时间,但却 不一定能明显改善解的质量,反而可能因为一些随机因数而产生质量更差的解,如第6组实 验一所示。 同时也大概比较了一下多点交叉的交叉点个数crossnum,交叉概率probCross,变异概 率probMutate等参数,由于参数太多,这里没有一一进行控制变量的比较。 大致估算可知, 交叉概率及交叉点的个数影响交叉操作产生新个体的质量,过多的交叉及变化过大的交叉可 能会产生不好的结果,而过多的变异也应该会造成算法的不稳定。 下面给出以上几个实验结果的实验截图,其中到现在为止结果最好的一个为: (3lflC: Window? \syiterr,32\cnn 岡数在点"上盹酣1龙£,1柑刃砒阳7》取得最大值洱-曲44阳阴(Pv-ess: anytocontInue.... 其余若干个为: 59C: \Windovw5Vy5terri32\ciTtd.exe |團数在点"書四19盟1.-豊-: 32910阿“取得最才-直: 2-89202745? ftnyk耳yto(? ont久nuu■・・. [ZBC: Wi 超数在点"・S8193970.i.32785034>®得最HPressanykeytocontinuE・・・. 大值 EBCAWindowAsysterm32\cmd.exe 函数在点"翦942£叮也: L-J2g399GG〉取得最大值-仙酊2551 PressanykeytocontiniAe---— 算法改进 以上实验得到的最好结果仍然是差强人意,这里对算法做一个小的优化,即添加防止种群退化的操作。 记录当前位置所得到的最优值及对应的个体,每次更新种群之后,计算新种群的最优值,如果最优值变差了,则把之前较优的个体替换进新种群,防止种群退化;否则 更新最优值。 "防止硯g化 doubletenval; intbestld=getOptimalCgroupj』temval); if(temval "如柔新种群的最优值变差・把较优的个体詡奂进新种群group[bestId]■best匚; } ^lse { "如果新种群的最优値变好”則更新最优值记录best€-group[bestld])bestval=temvalj } 改进之后的效果如下所示,显然比之前更优,且实验结果显示对于前面对比实验中的参数值,这里只需要较小的参数(如迭代次数只需2000次)值即可稳定收敛到此最大值,可 知改进非常有效。 [SBC: \Wind□ws\sy$tem3Acmd.exe 国数在点①罔252541-32&£07即〉取得最大直2.*94471酊Pressanytocontinue.... 增加输出精度之后为,于是得到最优的结果为2.894471354862841 固C: \Wind£w$\yy: 5tEm? 2\£[mileM 画数在点".S82&19531250Q00,1,32&507568359375>©^^X值;养胡£47135朝E2841Pressan^keytocontinue・・・. 源代码 改进后的源代码如下: #include #include #include #include #include usingnamespacestd; //程序欲分配内存的数组大小 constintmxn=10000;//最大的种群规模 constintmxlen=1000; //最大的染色体长度 //遗传算法关键参数 //种群的个体数 const intN=200; const intlen=30; // 每个个体的染色体的长度,x和y各占一半 const int crossnum =4;// 交叉操作时多点交叉的交叉点个数 constdoubleprobCross=0.85;//交叉概率 constdoubleprobMutation=0.15;//变异概率 //个体的染色体类 classChromosome {] public: boolg[mxlen]; //二进制编码的编码数组 Chromosome() //默认构造函数,构造随机染色体 { for(inti=( );i g[i]=rand()%2; } Chromosome(const Chromosome&c) //拷贝构造函数,进行深复制 { for(inti=0 );i g[i]=c.g[i]; } voidoperator=( constChromosome& c)//重载=号,进行深复制 { for(inti=0 );i g[i]=c.g[i]; } }; double bestval; //记录当前所得的最优值 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 doublesum=0; for(inti=0;i sum+=fitnessVal[i]; doubleprob[mxn]; for(inti=0;i prob[i]=fitnessVal[i]/sum; //随机选择N个个体组成新种群 intselectId[mxn]; for(inti=1;i prob[i]+=prob[i-1]; for(inti=0;i { //使用轮盘赌算法选择个体 double randNum=random01(); intj; for (j= 0;j { if (randNum { selectId[i]=j; break } } if(j==N-1) selectId[i]=j; } //把种群更新为新选择的个体集合 for(inti=0;i for(inti=0;i } //交叉操作,使用多点交叉 voidcrossoverChromosome&c1,Chromosome&c2) { //生成交叉点位置,并排序 intcrosspoint[mxn]; for(inti=0;i sort(crosspoint,crosspoint+crossnum); //进行交叉 boolflag=0; for(int i=0,j= 0;i i++) { if (! flag) swap(cl.g[i], c2.g[i]); if (i==crosspoint[j]) { //如果若干个交叉点重合,则效果叠加 //偶数个交叉点效果相当于没有交叉点 while(j //变异操作 voidmutate(Chromosome&c) { //随机选择一位进行翻转 inti=rand()%len; c.g[i]=! c.g[i]; } //获取种群最优个体 intgetOptimal(Chromosomegroup[mxn],double&x,double&y,double&val){」 //计算适应值,遍历得到最优值并进行解码 doublefitnessVal[mxn]; intid=0; for(inti=1;i if (fitnessVal[i]>fitnessVal[id]) id=i; decode( group[id],x,y); val=f( x,y); return id; } //遗传算法总代码 voidGA(double&x,double&y,double&val) { // 初始化种群 for (inti=0 ;i group[i]= Chromosome(); // bestC=group[getOptimal(group,x,y,bestval)]; //控制进化代数 for(intg=0;g { //选择操作 select(group); //根据交叉概率进行交叉 for(inti=0,pre=-1;i { if(random01() { if(pre==-1) pre=i; else { crossover(group[pre],group[i]); pre=-1; } } } //根据变异概率进行变异 for(inti=0;i if(random01() mutate(group[i]); //防止种群退化 doubletemval; intbestId=getOptimal(group,x,y,temval); if(temval //如果新种群的最优值变好,则更新最优值记录bestC=group[bestld]; bestval=temval; } } //获取最优值 getOptimal(group,x,y,val); }intmain() { srand(time(0)); doublex,y,maxval; GA(x,y,maxval); < cout<<"函数在点("<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 使用 遗传 算法 求解 函数 最大值