遗传算法的c语言程序

信息与计算科学1150420009李存建遗传算法一需求分析1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048=x1,x2=2.048作适应度函数求最大适应度即为函数的最大值二概要设计1．程序流程图2．类型定义intpopsize;//种群大小intmaxgeneration;//最大世代数开始Gen=0编码随机产生M个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制复制的个体添入新群体中交叉后添入新群体中变异后添入新群体中j=j+1j=j+2j=j+1Gen=Gen+1输出结果终止YNYYYNNNpcpmdoublepc;//交叉率doublepm;//变异率structindividual{charchrom[chromlength+1];doublevalue;doublefitness;//适应度};intgeneration;//世代数intbest_index;intworst_index;structindividualbestindividual;//最佳个体structindividualworstindividual;//最差个体structindividualcurrentbest;structindividualpopulation[POPSIZE];3．函数声明voidgenerateinitialpopulation();voidgeneratenextpopulation();voidevaluatepopulation();longdecodechromosome(char*,int,int);voidcalculateobjectvalue();voidcalculatefitnessvalue();voidfindbestandworstindividual();voidperformevolution();voidselectoperator();voidcrossoveroperator();voidmutationoperator();voidinput();voidoutputtextreport();4．程序的各函数的简单算法说明如下：（1）．voidgenerateinitialpopulation()和voidinput()初始化种群和遗传算法参数。input()函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。（2）voidcalculateobjectvalue();计算适应度函数值。根据给定的变量用适应度函数计算然后返回适度值。（3）选择函数selectoperator()在函数selectoperator()中首先用rand()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在；显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。（4）染色体交叉函数crossoveroperator()这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色体的交叉位的后面部分交叉即可；若大于交叉概率，则进行简单的染色体复制即可。（5）染色体变异函数mutation()变异是针对染色体字符变异的，而不是对个体而言，即个体变异的概率是一样。随机产生比较概率，若小于变异概率，则1变为0，0变为1，同时变异次数加1。（6）longdecodechromosome(char*,int,int)本函数是染色体解码函数，它将以数组形式存储的二进制数转成十进制数，然后才能用适应度函数计算。（7）voidfindbestandworstindividual()本函数是求最大适应度个体的，每一代的所有个体都要和初始的最佳比较，如果大于就赋给最佳。（8）voidoutputtextreport()输出种群统计结果输出每一代的种群的最大适应度和平均适应度，最后输出全局最大值三运行环境本程序的开发工具是VC++，在VC++下运行。四源代码#includestdio.h#includestdlib.h#includetime.h#includemath.h#definePOPSIZE500#definemaximization1#defineminimization2#definecmax100#definecmin0#definelength110#definelength210#definechromlengthlength1+length2//染色体长度intfunctionmode=maximization;intpopsize;//种群大小intmaxgeneration;//最大世代数doublepc;//交叉率doublepm;//变异率structindividual{charchrom[chromlength+1];doublevalue;doublefitness;//适应度};intgeneration;//世代数intbest_index;intworst_index;structindividualbestindividual;//最佳个体structindividualworstindividual;//最差个体structindividualcurrentbest;structindividualpopulation[POPSIZE];//函数声明voidgenerateinitialpopulation();voidgeneratenextpopulation();voidevaluatepopulation();longdecodechromosome(char*,int,int);voidcalculateobjectvalue();voidcalculatefitnessvalue();voidfindbestandworstindividual();voidperformevolution();voidselectoperator();voidcrossoveroperator();voidmutationoperator();voidinput();voidoutputtextreport();voidgenerateinitialpopulation()//种群初始化{inti,j;for(i=0;ipopsize;i++){for(j=0;jchromlength;j++){population[i].chrom[j]=(rand()%105)?'0':'1';}population[i].chrom[chromlength]='\0';}}voidgeneratenextpopulation()//生成下一代{selectoperator();crossoveroperator();mutationoperator();}voidevaluatepopulation()//评价个体，求最佳个体{calculateobjectvalue();calculatefitnessvalue();findbestandworstindividual();}longdecodechromosome(char*string,intpoint,intlength)//给染色体解码{inti;longdecimal=0;char*pointer;for(i=0,pointer=string+point;ilength;i++,pointer++)if(*pointer-'0'){decimal+=(long)pow(2,i);}return(decimal);}voidcalculateobjectvalue()//计算函数值{inti;longtemp1,temp2;doublex1,x2;for(i=0;ipopsize;i++){temp1=decodechromosome(population[i].chrom,0,length1);temp2=decodechromosome(population[i].chrom,length1,length2);x1=4.096*temp1/1023.0-2.048;x2=4.096*temp2/1023.0-2.048;population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);}}voidcalculatefitnessvalue()//计算适应度{inti;doubletemp;for(i=0;ipopsize;i++){if(functionmode==maximization){if((population[i].value+cmin)0.0){temp=cmin+population[i].value;}else{temp=0.0;}}elseif(functionmode==minimization){if(population[i].valuecmax){temp=cmax-population[i].value;}else{temp=0.0;}}population[i].fitness=temp;}}voidfindbestandworstindividual()//求最佳个体和最差个体{inti;doublesum=0.0;bestindividual=population[0];worstindividual=population[0];for(i=1;ipopsize;i++){if(population[i].fitnessbestindividual.fitness){bestindividual=population[i];best_index=i;}elseif(population[i].fitnessworstindividual.fitness){worstindividual=population[i];worst_index=i;}sum+=population[i].fitness;}if(generation==0){currentbest=bestindividual;}else{if(bestindividual.fitness=currentbest.fitness){currentbest=bestindividual;}}}voidperformevolution()//演示评价结果{if(bestindividual.fitnesscurrentbest.fitness){currentbest=population[best_index];}else{population[worst_index]=currentbest;}}voidselectoperator()//比例选择算法{inti,index;doublep,sum=0.0;doublecfitness[POPSIZE];structindividualnewpopulation[POPSIZE];for(i=0;ipopsize;i++){sum+=pop