遗传算法求解函数极值C语言代码

利用遗传算法求函数的极大值该函数有两个局部极大值点，分别是f (2.048,-2.048)=3897.7342和f (2.048,-2.048)=3905.9262，其中，后者为全局最大点。

可以分别用二进制编码和十进制编码遗传算法求函数极大值遗传算法二进制编码求函数极大值程序%Generic Algorithm for function f(x1,x2) optimumclear all;close all;%Parameters 参数Size=80; %群体大小G=100; %终止进化代数CodeL=10; %代码长度umax=2.048;umin=-2.048;E=round(rand(Size,2*CodeL)); %Initial Code 最初代码%Main Program 主程序for k=1:1:Gtime(k)=k;222212121(,)100()(1)2.048 2.048(1,2)i f x x x x x x i ⎧=-+-⎨-≤≤=⎩for s=1:1:Sizem=E(s,:);y1=0;y2=0; %X对应的十进制代码%Uncodingm1=m(1:1:CodeL);for i=1:1:CodeLy1=y1+m1(i)*2^(i-1); %将y1转换为十进制数endx1=(umax-umin)*y1/1023+umin;m2=m(CodeL+1:1:2*CodeL);for i=1:1:CodeLy2=y2+m2(i)*2^(i-1); %将y2转换为十进制数endx2=(umax-umin)*y2/1023+umin; %求x对应的十进制数F(s)=100*(x1^2-x2)^2+(1-x1)^2; %个体适应度函数endJi=1./F; %个体适应度函数的倒数%****** Step 1 : Evaluate BestJ ******BestJ(k)=min(Ji);fi=F; %Fitness Function 适应函数[Oderfi,Indexfi]=sort(fi); %Arranging fi small to biggerBestfi=Oderfi(Size); %Let Bestfi=max(fi)BestS=E(Indexfi(Size),:); %Let BestS=E(m), m is the Indexfi belong to max(fi) %最佳样本bfi(k)=Bestfi;%****** Step 2 : Select and Reproduct Operation******fi_sum=sum(fi);fi_Size=(Oderfi/fi_sum)*Size;fi_S=floor(fi_Size); %Selecting Bigger fi valuekk=1;for i=1:1:Sizefor j=1:1:fi_S(i) %Select and ReproduceTempE(kk,:)=E(Indexfi(i),:);kk=kk+1; %kk is used to reproduceendend%************ Step 3 : Crossover Operation ************pc=0.60; %交叉概率n=ceil(20*rand); %种群大小for i=1:2:(Size-1)temp=rand;if pc>temp %Crossover Conditionfor j=n:1:20TempE(i,j)=E(i+1,j); %交换E（i,j）和E(i+1,j)TempE(i+1,j)=E(i,j);endendendTempE(Size,:)=BestS;E=TempE;%************ Step 4: Mutation Operation ************** %pm=0.001; %变异概率%pm=0.001-[1:1:Size]*(0.001)/Size; %Bigger fi, smaller Pm %pm=0.0; %No mutationpm=0.1; %Big mutationfor i=1:1:Sizefor j=1:1:2*CodeLtemp=rand;if pm>temp %Mutation Conditionif TempE(i,j)==0TempE(i,j)=1;elseTempE(i,j)=0;endendendend%Guarantee TempPop(30,:) is the code belong to the best individual(max(fi)) TempE(Size,:)=BestS;E=TempE;endMax_Value=BestfiBestSx1x2figure(1);plot(time,BestJ); %目标函数和时间的坐标系xlabel('Times');ylabel('Best J');figure(2);plot(time,bfi);xlabel('times');ylabel('Best F');遗传算法十进制编码求函数极大值程序%Generic Algorithm for function f(x1,x2) optimumclear all;close all;%Parameters参数Size=80;G=100; %迭代次数CodeL=10; %编码长度umax=2.048;umin=-2.048;E=round(rand(Size,2*CodeL)); %Initial Code ？？？%Main Programfor k=1:1:Gtime(k)=k;for s=1:1:Sizem=E(s,:);y1=0;y2=0;%Uncodingm1=m(1:1:CodeL); %？？？for i=1:1:CodeLy1=y1+m1(i)*2^(i-1);endx1=(umax-umin)*y1/1023+umin;m2=m(CodeL+1:1:2*CodeL);for i=1:1:CodeLy2=y2+m2(i)*2^(i-1);endx2=(umax-umin)*y2/1023+umin;F(s)=100*(x1^2-x2)^2+(1-x1)^2;endJi=1./F;%****** Step 1 : Evaluate BestJ ****** BestJ(k)=min(Ji);fi=F; %Fitness Function[Oderfi,Indexfi]=sort(fi); %Arranging fi small to biggerBestfi=Oderfi(Size); %Let Bestfi=max(fi)BestS=E(Indexfi(Size),:); %Let BestS=E(m), m is the Indexfi belong to max(fi)bfi(k)=Bestfi;%****** Step 2 : Select and Reproduct Operation******fi_sum=sum(fi);fi_Size=(Oderfi/fi_sum)*Size;fi_S=floor(fi_Size); %Selecting Bigger fi valuekk=1;for i=1:1:Sizefor j=1:1:fi_S(i) %Select and ReproduceTempE(kk,:)=E(Indexfi(i),:);kk=kk+1; %kk is used to reproduceendend%************ Step 3 : Crossover Operation ************ pc=0.60;n=ceil(20*rand);for i=1:2:(Size-1)temp=rand;if pc>temp %Crossover Conditionfor j=n:1:20TempE(i,j)=E(i+1,j);TempE(i+1,j)=E(i,j);endendendTempE(Size,:)=BestS;E=TempE;%************ Step 4: Mutation Operation ************** %pm=0.001;%pm=0.001-[1:1:Size]*(0.001)/Size; %Bigger fi, smaller Pm%pm=0.0; %No mutationpm=0.1; %Big mutationfor i=1:1:Sizefor j=1:1:2*CodeLtemp=rand;if pm>temp %Mutation Conditionif TempE(i,j)==0TempE(i,j)=1;elseTempE(i,j)=0;endendendend%Guarantee TempPop(30,:) is the code belong to the best individual(max(fi)) TempE(Size,:)=BestS;E=TempE;endMax_Value=BestfiBestSx1x2figure(1);plot(time,BestJ);xlabel('Times');ylabel('Best J');figure(2);plot(time,bfi);xlabel('times');ylabel('Best F');思考：通过改变群体大小、终止进化代数G、交叉概率P c和变异概率P m，分析群体大小、终止进化代数、交叉概率和变异概率对优化效果的影响。

.专业整理 .C语言遗传算法代码以下为遗传算法的源代码，计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来，请自行选择适合的代码，使用时请略看完代码的注释，在需要更改的地方更改为自己需要的代码。

+++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++#include <stdio.h>#include<stdlib.h>#include<time.h>#include<math.h>#define POPSIZE 1000#define maximization 1#define minimization 2#define cmax 100#define cmin 0#define length1 20#define chromlength length1// 染色体长度//注意，你是求最大值还是求最小值.专业整理 .//变量的上下限的修改开始float min_x1=-2;//变量的下界float max_x1=-1;//变量的上界//变量的上下限的修改结束int popsize;// 种群大小int maxgeneration;// 最大世代数double pc;// 交叉率double pm;// 变异率struct individual{char chrom[chromlength+1];double value;double fitness;// 适应度};int generation;// 世代数int best_index;int worst_index;struct individual bestindividual;// 最佳个体.专业整理 . struct individual worstindividual; //最差个体struct individual currentbest;struct individual population[POPSIZE];//函数声明void generateinitialpopulation();void generatenextpopulation();void evaluatepopulation();long decodechromosome(char *,int,int);void calculateobjectvalue();void calculatefitnessvalue();void findbestandworstindividual();void performevolution();void selectoperator();void crossoveroperator();void mutationoperator();void input();void outputtextreport();void generateinitialpopulation( )// 种群初始化{int i,j;.专业整理 .for (i=0;i<popsize; i++){for( j=0;j<chromlength;j++){population[i].chrom[j]=(rand()%20<10)?'0':'1';}population[i].chrom[chromlength]='\0';}}void generatenextpopulation()// 生成下一代{selectoperator();crossoveroperator();mutationoperator();}void evaluatepopulation()// 评价个体，求最佳个体{calculateobjectvalue();calculatefitnessvalue();findbestandworstindividual();}long decodechromosome(char *string ,int point,int length) //给染色体解码{int i;long decimal=0;char*pointer;for(i=0,pointer=string+point;i<length;i++,pointer++)if(*pointer-'0'){decimal +=(long)pow(2,i);}return (decimal);}void calculateobjectvalue()// 计算函数值{int i;long temp1,temp2;double x1;for (i=0; i<popsize; i++){temp1=decodechromosome(population[i].chrom,0,length1);x1=(max_x1-min_x1)*temp1/(1024*1024-1)+min_x1;//目标函数修改开始population[i].value=(pow(x1,5)-3*x1-1)*(pow(x1,5)-3*x1-1);//目标函数修改结束}}void calculatefitnessvalue()//计算适应度{int i;double temp;for(i=0;i<popsize;i++){if(functionmode==maximization){if((population[i].value+cmin)>0.0){temp=cmin+population[i].value;}else{temp=0.0;}}else if (functionmode==minimization){if(population[i].value<cmax){temp=cmax-population[i].value;}else{ temp=0.0;}}population[i].fitness=temp;}}void findbestandworstindividual( ) //求最佳个体和最差个体{int i;double sum=0.0;bestindividual=population[0];worstindividual=population[0];.专业整理 .for (i=1;i<popsize; i++){if (population[i].fitness>bestindividual.fitness){bestindividual=population[i];best_index=i;}else if (population[i].fitness<worstindividual.fitness) {worstindividual=population[i];worst_index=i;}sum+=population[i].fitness;}if (generation==0){currentbest=bestindividual;}else{if(bestindividual.fitness>=currentbest.fitness){currentbest=bestindividual;}}}void performevolution() //演示评价结果{if (bestindividual.fitness>currentbest.fitness){ currentbest=population[best_index];}else{population[worst_index]=currentbest;}}void selectoperator() //比例选择算法{int i,index;double p,sum=0.0;double cfitness[POPSIZE];struct individual newpopulation[POPSIZE];for(i=0;i<popsize;i++){sum+=population[i].fitness;}for(i=0;i<popsize; i++){cfitness[i]=population[i].fitness/sum;}for(i=1;i<popsize; i++){cfitness[i]=cfitness[i-1]+cfitness[i];}for (i=0;i<popsize;i++){p=rand()%1000/1000.0;index=0;while (p>cfitness[index]){index++;}newpopulation[i]=population[index];}for(i=0;i<popsize; i++){population[i]=newpopulation[i];}}void crossoveroperator() //交叉算法{int i,j;int index[POPSIZE];int point,temp;double p;char ch;for (i=0;i<popsize;i++){index[i]=i;}for (i=0;i<popsize;i++){point=rand()%(popsize-i);temp=index[i];index[i]=index[point+i];index[point+i]=temp;}for (i=0;i<popsize-1;i+=2){p=rand()%1000/1000.0;if (p<pc){point=rand()%(chromlength-1)+1;for ( j=point; j<chromlength;j++){ch=population[index[i]].chrom[j];population[index[i]].chrom[j]=population[index[i+1]].chrom[j];population[index[i+1]].chrom[j]=ch;}}}}void mutationoperator() //变异操作{int i,j;double p;for (i=0;i<popsize;i++){for( j=0;j<chromlength;j++){p=rand()%1000/1000.0;if (p<pm){population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';}}}}void input() //数据输入{ //printf(" 初始化全局变量 :\n");//printf("种群大小 (50-500) ： ");//scanf("%d", &popsize);popsize=500;if((popsize%2) != 0){//printf( "种群大小已设置为偶数\n");popsize++;};//printf("最大世代数 (100-300) ： ");//scanf("%d", &maxgeneration); maxgeneration=200;//printf("交叉率 (0.2-0.99) ： ");//scanf("%f", &pc);pc=0.95;//printf("变异率 (0.001-0.1) ：");//scanf("%f", &pm);pm=0.03;}void outputtextreport()//数据输出{int i;double sum;double average;sum=0.0;for(i=0;i<popsize;i++){sum+=population[i].value;}average=sum/popsize;printf("当前世代=%d\n当前世代平均函数值=%f\n当前世代最优函数值=%f\n",generation,average,population[best_index].value);}void main()// 主函数{ int i;long temp1,temp2;double x1,x2;generation=0;input();generateinitialpopulation();evaluatepopulation();while(generation<maxgeneration){generation++;generatenextpopulation();evaluatepopulation();performevolution();outputtextreport();}printf("\n");printf("统计结果 :");printf("\n");//printf("最大函数值等于：%f\n",currentbest.fitness);printf(" 其染色体编码为：");for (i=0;i<chromlength;i++){printf("%c",currentbest.chrom[i]);}printf("\n");temp1=decodechromosome(currentbest.chrom,0,length1);x1=(max_x1-min_x1)*temp1/(1024*1024-1)+min_x1;printf("x1=%lf\n",x1);.专业整理 .//这是需要修改的地方printf(" 最优值等于：%f\n",(pow(x1,5)-3*x1-1)*(pow(x1,5)-3*x1-1));}+++++++++++++++++++++++++二元函数代码+++++++++++++++++++++++++++++++++++++++++#include <stdio.h>#include<stdlib.h>#include<time.h>#include<math.h>#define POPSIZE 500#define maximization 1#define minimization 2#define cmax 100#define cmin 0#define length1 20#define length2 20#define chromlength length1+length2// 染色体长度//-----------求最大还是最小值int functionmode=maximization;//-----------//-----------变量上下界float min_x1=0;float max_x1=3;float min_x2=1;float max_x2=5;//-----------int popsize;// 种群大小int maxgeneration;// 最大世代数double pc;// 交叉率double pm;// 变异率struct individual{char chrom[chromlength+1];double value;double fitness;// 适应度};int generation;// 世代数int best_index;int worst_index;struct individual bestindividual;// 最佳个体struct individual worstindividual; //最差个体struct individual currentbest;struct individual population[POPSIZE];//函数声明void generateinitialpopulation();void generatenextpopulation();void evaluatepopulation();long decodechromosome(char *,int,int);void calculateobjectvalue();void calculatefitnessvalue();void findbestandworstindividual();void performevolution();void selectoperator();void crossoveroperator();void mutationoperator();void input();void outputtextreport();void generateinitialpopulation( )// 种群初始化{int i,j;for (i=0;i<popsize; i++){for( j=0;j<chromlength;j++){population[i].chrom[j]=(rand()%40<20)?'0':'1';}population[i].chrom[chromlength]='\0';}}void generatenextpopulation()// 生成下一代{selectoperator();crossoveroperator();mutationoperator();}void evaluatepopulation()// 评价个体，求最佳个体{calculateobjectvalue();calculatefitnessvalue();findbestandworstindividual();}long decodechromosome(char *string ,int point,int length) //给染色体解码{int i;long decimal=0;char*pointer;for(i=0,pointer=string+point;i<length;i++,pointer++)if(*pointer-'0'){decimal +=(long)pow(2,i);}return (decimal);}void calculateobjectvalue()// 计算函数值{int i;long temp1,temp2;double x1,x2;for (i=0; i<popsize; i++){temp1=decodechromosome(population[i].chrom,0,length1);temp2=decodechromosome(population[i].chrom,length1,length2);x1=(max_x1-min_x1)*temp1/(1024*1024-1)+min_x1;x2=(max_x2-min_x2)*temp2/(1024*1024-1)+min_x2;//-----------函数population[i].value=x1*x1+sin(x1*x2)-x2*x2;//-----------}}void calculatefitnessvalue()//计算适应度{int i;double temp;for(i=0;i<popsize;i++){if(functionmode==maximization){if((population[i].value+cmin)>0.0){temp=cmin+population[i].value;}else{temp=0.0;}}else if (functionmode==minimization){if(population[i].value<cmax){temp=cmax-population[i].value;}else{ temp=0.0;}}population[i].fitness=temp;}}void findbestandworstindividual( ) //求最佳个体和最差个体{int i;double sum=0.0;bestindividual=population[0];worstindividual=population[0];for (i=1;i<popsize; i++){if (population[i].fitness>bestindividual.fitness){bestindividual=population[i];best_index=i;}else if (population[i].fitness<worstindividual.fitness){worstindividual=population[i];worst_index=i;}sum+=population[i].fitness;}if (generation==0){currentbest=bestindividual;}else{if(bestindividual.fitness>=currentbest.fitness){currentbest=bestindividual;}}}void performevolution() //演示评价结果{if (bestindividual.fitness>currentbest.fitness){currentbest=population[best_index];}else{population[worst_index]=currentbest;}}void selectoperator() //比例选择算法{int i,index;double p,sum=0.0;double cfitness[POPSIZE];struct individual newpopulation[POPSIZE];for(i=0;i<popsize;i++){sum+=population[i].fitness;}for(i=0;i<popsize; i++){cfitness[i]=population[i].fitness/sum;}for(i=1;i<popsize; i++){cfitness[i]=cfitness[i-1]+cfitness[i];}for (i=0;i<popsize;i++){p=rand()%1000/1000.0;index=0;while (p>cfitness[index]){index++;}newpopulation[i]=population[index];}for(i=0;i<popsize; i++){population[i]=newpopulation[i];}}void crossoveroperator() //交叉算法{int i,j;int index[POPSIZE];int point,temp;double p;char ch;for (i=0;i<popsize;i++){index[i]=i;}for (i=0;i<popsize;i++){point=rand()%(popsize-i);temp=index[i];index[i]=index[point+i];index[point+i]=temp;}for (i=0;i<popsize-1;i+=2){p=rand()%1000/1000.0;if (p<pc){point=rand()%(chromlength-1)+1;for ( j=point; j<chromlength;j++){ch=population[index[i]].chrom[j];population[index[i]].chrom[j]=population[index[i+1]].chrom[j];population[index[i+1]].chrom[j]=ch;}}}}void mutationoperator() //变异操作{int i,j;double p;for (i=0;i<popsize;i++){for( j=0;j<chromlength;j++){p=rand()%1000/1000.0;if (p<pm){population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';}}}}void input() //数据输入{ //printf(" 初始化全局变量 :\n");//printf("种群大小 (50-500) ： ");//scanf("%d", &popsize);popsize=200;if((popsize%2) != 0){//printf( "种群大小已设置为偶数\n");popsize++;};//printf("最大世代数 (100-300) ： ");//scanf("%d", &maxgeneration);maxgeneration=200;//printf("交叉率 (0.2-0.99)： ");//scanf("%f", &pc);pc=0.9;//printf("变异率 (0.001-0.1)：");//scanf("%f", &pm);pm=0.003;}void outputtextreport()//数据输出{int i;double sum;double average;sum=0.0;for(i=0;i<popsize;i++){sum+=population[i].value;}average=sum/popsize;printf("当前世代=%d\n当前世代平均函数值=%f\n当前世代最优函数值=%f\n",generation,average,population[best_index].value);}void main()// 主函数{ int i;long temp1,temp2;double x1,x2;generation=0;input();generateinitialpopulation();evaluatepopulation();while(generation<maxgeneration){generation++;generatenextpopulation();evaluatepopulation();performevolution();outputtextreport();}printf("\n");printf("统计结果 :");printf("\n");//printf("最大函数值等于：%f\n",currentbest.fitness);printf(" 其染色体编码为：");for (i=0;i<chromlength;i++){printf("%c",currentbest.chrom[i]);}printf("\n");temp1=decodechromosome(currentbest.chrom,0,length1);temp2=decodechromosome(currentbest.chrom,length1,length2);x1=(max_x1-min_x1)*temp1/(1024*1024-1)+min_x1;x2=(max_x2-min_x2)*temp2/(1024*1024-1)+min_x2;printf("x=%lf,y=%lf\n",x1,x2);//-----------修改函数printf(" 最大值 =%f\n",x1*x1+sin(x1*x2)-x2*x2);//-----------}。

遗传算法( GA , Genetic Algorithm ) ，也称进化算法。

遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。

因此在介绍遗传算法前有必要简单的介绍生物进化知识。

一.进化论知识作为遗传算法生物背景的介绍，下面内容了解即可：种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。

个体：组成种群的单个生物。

基因 ( Gene ) ：一个遗传因子。

染色体 ( Chromosome )：包含一组的基因。

生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。

适应度低的个体参与繁殖的机会比较少，后代就会越来越少。

遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。

简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。

那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。

二.遗传算法思想借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。

这样进化N代后就很有可能会进化出适应度函数值很高的个体。

举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。

这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。

编码：需要将问题的解编码成字符串的形式才能使用遗传算法。

/*本程序试用遗传算法来解决Rosenbrock函数的全局最大值计算问题：max f(x1,x2)=100(x1^2-x2^2)^2+(1-x1)^2s.t.-2.048≤xi≤2.048(i=1,2)*/#include<iostream>#include<time.h>#include<stdlib.h>#include<cmath>using namespace std;const int M=8,T=2;//M群体大小，pc交叉概率,pm变异概率,T终止代数const double pc=0.6,pm=0.01;struct population//定义群体结构{int x[20];double x1,x2;double fit;double sumfit;}p[M];void initial(population*);//初始化函数void evaluefitness(population*);//计算适应度void select(population*);//选择复制函数void crossover(population*);//交叉函数void mutation(population*);//变异函数void decoding(population*);//解码函数void print(population*);//显示函数int main()//遗传算法主函数{int gen=0;initial(&p[0]);//随机获得初始解cout<<"initialed!"<<endl;print(&p[0]);decoding(&p[0]);//先解码cout<<"decoded!"<<endl;print(&p[0]);evaluefitness(&p[0]);//计算适应值与累计适值cout<<"evalued!"<<endl;print(&p[0]);while(gen<=T){cout<<"gen="<<gen+1<<endl;select(&p[0]);decoding(&p[0]);evaluefitness(&p[0]);cout<<"selected!"<<endl;print(&p[0]);crossover(&p[0]);decoding(&p[0]);evaluefitness(&p[0]);cout<<"crossovered!"<<endl;print(&p[0]);mutation(&p[0]);decoding(&p[0]);evaluefitness(&p[0]);cout<<"mutated!"<<endl;print(&p[0]);gen++;}decoding(&p[0]);evaluefitness(&p[0]);cout<<"最后得出的满意解为:"<<endl;for(int i=0;i<M;i++)cout<<"x1:"<<p[i].x1<<"x2:"<<p[i].x2<<"值:"<<p[i].fit<<endl;return0;}/*****************************初始化函数*****************************/int rand01()//用于随机取0或1的函数{int r;float q;q=rand()/(RAND_MAX+0.0);if(q<0.5)r=0;else r=1;return r;}void initial(population*t)//群体初始化函数{int j;population*po;srand(time(0));for(po=t;po<t+M;po++)for(j=0;j<20;j++)(*po).x[j]=rand01();}/*************************计算适应值函数*********************************/ void evaluefitness(population*t)//计算适应值函数{double f,x1,x2,temp=0.0;population*po,*po2;for(po=t;po<t+M;po++){x1=(*po).x1;x2=(*po).x2;f=100.0*(x1*x1-x2*x2)*(x1*x1-x2*x2)+(1.0-x1)*(1.0-x1);(*po).fit=f;}for(po=t;po<t+M;po++)//计算累计适应值{for(po2=t;po2<=po;po2++)temp=temp+(*po2).fit;(*po).sumfit=temp;temp=0.0;}}/**************************选择复制函数********************************/ double randab(double a,double b)//在区间(a,b)内生成一个随机数{double c,r;c=b-a;r=a+c*rand()/(RAND_MAX+1.0);return r;}void select(population*t)//选择算子函数{int i=0;population pt[M],*po;double s;srand(time(0));while(i<M){s=randab((*t).sumfit,(*(t+M-1)).sumfit);for(po=t;po<t+M;po++){if((*po).sumfit>=s){pt[i]=(*po);break;}else continue;}i++;}for(i=0;i<M;i++)//将复制后数据pt[M]转入p[M] for(int j=0;j<20;j++)p[i].x[j]=pt[i].x[j];}/***************************交叉函数*******************************/ void crossover(population*t)//交叉算子函数{population*po;double q;//用于存一个0到1的随机数int d,e,tem[20];//d存放从1到19的一个随机整数，用来确定交叉的位置//e存放从0到M的一个随机且与当前P[i]中i不同的整数，用来确定交叉的对象srand(time(0));for(po=t;po<t+M/2;po++){q=rand()/(RAND_MAX+0.0);if(q<pc){for(int j=0;j<M;j++)//运算M次，避免产生群体中某个体与自己交叉的情况{e=rand()%M;//随机确定交叉对象if(t+e!=po)break;}//不能重复d=1+rand()%19;//随机确定交叉位置for(int i=d;i<20;i++){tem[i]=(*po).x[i];(*po).x[i]=(*(t+e)).x[i];(*(t+e)).x[i]=tem[i];}}else continue;}}/***************************变异函数*******************************/void mutation(population*t)//变异算子函数{double q;//q用来存放针对每一个基因座产生的[0，1]的随机数population*po;srand(time(0));for(po=t;po<t+M;po++){int i=0;while(i<20){q=rand()/(RAND_MAX+0.0);if(q<pm)(*po).x[i]=1-(*po).x[i];i++;}}}/***************************解码函数*******************************/void decoding(population*t)//解码函数{population*po;int temp,s1=0,s2=0;float m,n,dit;n=ldexp(1,10);//n=2^10dit=4.096/(n-1);//dit=(U(max)-U(min))/n-1for(po=t;po<t+M;po++){for(int i=0;i<10;i++){temp=ldexp((*po).x[i],i);s1=s1+temp;}m=-2.048+s1*dit;(*po).x1=m;s1=0;for(int j=10;j<20;j++){temp=ldexp((*po).x[j],j-10);s2=s2+temp;}m=-2.048+s2*dit;(*po).x2=m;s2=0;}}/*******************************显示函数**************************************/ void print(population*t){population*po;for(po=t;po<t+M;po++){for(int j=0;j<20;j++){cout<<(*po).x[j];if((j+1)%5==0)cout<<"";}cout<<endl;cout<<(*po).x1<<""<<(*po).x2<<""<<(*po).fit<<""<<(*po).sumfit<<endl;}}。

遗传算法的C语⾔实现（⼆）-----以求解TSP问题为例上⼀次我们使⽤遗传算法求解了⼀个较为复杂的多元⾮线性函数的极值问题，也基本了解了遗传算法的实现基本步骤。

这⼀次，我再以经典的TSP问题为例，更加深⼊地说明遗传算法中选择、交叉、变异等核⼼步骤的实现。

⽽且这⼀次解决的是离散型问题，上⼀次解决的是连续型问题，刚好形成对照。

⾸先介绍⼀下TSP问题。

TSP(traveling salesman problem,旅⾏商问题)是典型的NP完全问题，即其最坏情况下的时间复杂度随着问题规模的增⼤按指数⽅式增长，到⽬前为⽌还没有找到⼀个多项式时间的有效算法。

TSP问题可以描述为：已知n个城市之间的相互距离，某⼀旅⾏商从某⼀个城市出发，访问每个城市⼀次且仅⼀次，最后回到出发的城市，如何安排才能使其所⾛的路线最短。

换⾔之，就是寻找⼀条遍历n个城市的路径，或者说搜索⾃然⼦集X={1,2,...,n}(X的元素表⽰对n个城市的编号)的⼀个排列P(X)={V1,V2,....,Vn},使得Td=∑d(V i,V i+1)+d(V n,V1)取最⼩值，其中,d(V i,V i+1)表⽰城市V i到V i+1的距离。

TSP问题不仅仅是旅⾏商问题，其他许多NP完全问题也可以归结为TSP问题，如邮路问题，装配线上的螺母问题和产品的⽣产安排问题等等，也使得TSP问题的求解具有更加⼴泛的实际意义。

再来说针对TSP问题使⽤遗传算法的步骤。

（1）编码问题：由于这是⼀个离散型的问题，我们采⽤整数编码的⽅式，⽤1~n来表⽰n个城市，1~n的任意⼀个排列就构成了问题的⼀个解。

可以知道，对于n个城市的TSP问题，⼀共有n!种不同的路线。

(2)种群初始化：对于N个个体的种群，随机给出N个问题的解（相当于是染⾊体）作为初始种群。

这⾥具体采⽤的⽅法是：1,2，...,n作为第⼀个个体，然后2,3，..n分别与1交换位置得到n-1个解，从2开始，3,4,...,n分别与2交换位置得到n-2个解，依次类推。

遗传算法简述及代码详解声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。

遗传算法基本内容遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。

遗传学与遗传算法中的基础术语比较染色体：又可以叫做基因型个体(individuals)群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数量叫做群体大小。

初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。

适应度(fitness)：各个个体对环境的适应程度优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。

SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。

遗传算法的准备工作:1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。

前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。

非常重要的过程。

遗传算法基本过程为:1) 编码，创建初始群体2) 群体中个体适应度计算3) 评估适应度4) 根据适应度选择个体5) 被选择个体进行交叉繁殖6) 在繁殖的过程中引入变异机制7) 繁殖出新的群体，回到第二步实例一：（建议先看实例二）求 []30,0∈x 范围内的()210-=x y 的最小值1) 编码算法选择为"将x 转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。

计算智能作业三：遗传算法计算问题1.问题描述：求下述二元函数的最大值：222121),(m ax x x x x f +=S.t. }7,6,5,4,3,2,1{1∈x }7,6,5,4,3,2,1{2∈x2.程序结构：（1）变量：C ：是一个1*6数组，每个数组里面是一个6位二进制数，它是遗传算法中的染色体。

new_c:每一轮的新变量c 。

first_c:初始群体矩阵。

sur_value ：个体适应值的概率值，为0-1之间的数，所有概率值和为1。

survived ：经过选择运算后产生的个体基因型组合。

intersect_c ：经过交叉运算后产生的个体基因型组合。

mutation_c ：经过变异运算后产生的个体基因型组合。

f ：最后计算得到的最大值 （2）程序里面的方程function out = value_function( ci )：价值函数（自适应度函数），即222121),(x x x x f +=。

function [ sur_value ] = calc_value( c )：计算群体中每一个个体的适应度的值function survived = surviver( sur_value )：利用概率选择函数 function [ intersect_c ] = intersect( new_c )：交叉运算function [ mutation_c ,mutation_value] = mutation( intersect_c )：变异运算3.源程序（1）遗传算法的主程序主程序包括初始群体产生，最终结果展示，即各函数之间的调用关系。

个体编码遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为无符号二进制整数。

这个二进制整数位个体的基因型。

因为x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。

以下是一个简单的遗传算法的C语言代码示例：c#include <stdio.h>#include <stdlib.h>#include <time.h>#include <math.h>#define POPULATION_SIZE 100#define GENE_LENGTH 10#define MAX_GENERATIONS 1000#define MUTATION_RATE 0.01#define CROSSOVER_RATE 0.8typedef struct Individual {char genes[GENE_LENGTH];double fitness;} Individual;double calculate_fitness(Individual* individual) {// 计算适应度函数，这里使用简单的二进制字符串中1的个数作为适应度 int count = 0;for (int i = 0; i < GENE_LENGTH; i++) {if (individual->genes[i] == '1') {count++;}}return count;}void initialize_population(Individual* population) {// 初始化种群for (int i = 0; i < POPULATION_SIZE; i++) {for (int j = 0; j < GENE_LENGTH; j++) {population[i].genes[j] = rand() % 2 ? '0' : '1';}population[i].fitness = calculate_fitness(&population[i]); }}void selection(Individual* population, Individual* parents) {// 选择操作，采用轮盘赌算法选择两个父代个体double total_fitness = 0;for (int i = 0; i < POPULATION_SIZE; i++) {total_fitness += population[i].fitness;}double rand1 = rand() / (double)RAND_MAX * total_fitness;double rand2 = rand() / (double)RAND_MAX * total_fitness;double cumulative_fitness = 0;int parent1_index = -1, parent2_index = -1;for (int i = 0; i < POPULATION_SIZE; i++) {cumulative_fitness += population[i].fitness;if (rand1 < cumulative_fitness && parent1_index == -1) {parent1_index = i;}if (rand2 < cumulative_fitness && parent2_index == -1) {parent2_index = i;}}parents[0] = population[parent1_index];parents[1] = population[parent2_index];}void crossover(Individual* parents, Individual* offspring) {// 交叉操作，采用单点交叉算法生成两个子代个体int crossover_point = rand() % GENE_LENGTH;for (int i = 0; i < crossover_point; i++) {offspring[0].genes[i] = parents[0].genes[i];offspring[1].genes[i] = parents[1].genes[i];}for (int i = crossover_point; i < GENE_LENGTH; i++) {offspring[0].genes[i] = parents[1].genes[i];offspring[1].genes[i] = parents[0].genes[i];}offspring[0].fitness = calculate_fitness(&offspring[0]);offspring[1].fitness = calculate_fitness(&offspring[1]);}void mutation(Individual* individual) {// 变异操作，以一定概率翻转基因位上的值for (int i = 0; i < GENE_LENGTH; i++) {if (rand() / (double)RAND_MAX < MUTATION_RATE) {individual->genes[i] = individual->genes[i] == '0' ? '1' : '0'; }}individual->fitness = calculate_fitness(individual);}void replace(Individual* population, Individual* offspring) {// 替换操作，将两个子代个体中适应度更高的一个替换掉种群中适应度最低的一个个体int worst_index = -1;double worst_fitness = INFINITY;for (int i = 0; i < POPULATION_SIZE; i++) {if (population[i].fitness < worst_fitness) {worst_index = i;worst_fitness = population[i].fitness;}}if (offspring[0].fitness > worst_fitness || offspring[1].fitness > worst_fitness) {if (offspring[0].fitness > offspring[1].fitness) {population[worst_index] = offspring[0];} else {population[worst_index] = offspring[1];}}}。

此例程总共包含3个文件：main.c（主函数）；GA.c（包含3个所用函数）；GA.h（头文件），3个文件截图如下：用visual c++或者visual stutio创建工程，然后将上述3个文件包含进工程，编译运行即可。

亲测可行！！！3个文件代码分别如下：1、main.c：#include<iostream>#include"GA.h"using namespace std;/*******************************************************************GA demo求函数y=x*sin(10*pai*x)+2.0的最大值编码：浮点数,1位初始群体数：50变异概率：0.8进化代数：100取值范围：[0,4]变异步长：0.004注：因为是单数浮点数编码，所以未使用基因重组函数**********************************************************************/int main(){GenEngine genEngine(50,0.8,0.8,1,100,0,4);genEngine.OnStartGenAlg();getchar();}2、GA.c：#include<vector>#include<stdio.h>#include <stdlib.h>#include <time.h>#include<iostream>#include"GA.h"using namespace std;//srand((unsigned) time(NULL));double random(){double randNum;randNum=rand()*1.0/RAND_MAX;return randNum;}GenAlg::GenAlg(){}void GenAlg::init(int popsize, double MutRate, double CrossRate, int GenLenght,double LeftPoint,double RightPoint){popSize = popsize;mutationRate = MutRate;crossoverRate = CrossRate;chromoLength = GenLenght;totalFitness = 0;generation = 0;//fittestGenome = 0;bestFitness = 0.0;worstFitness = 99999999;averageFitness = 0;maxPerturbation=0.004;leftPoint=LeftPoint;rightPoint=RightPoint;//清空种群容器，以初始化vecPop.clear();for (int i=0; i<popSize; i++){//类的构造函数已经把适应性评分初始化为0vecPop.push_back(Genome());//把所有的基因编码初始化为函数区间内的随机数。

遗传算法C语言代码遗传算法C语言代码遗传算法C语言代码// GA.cpp : Defines the entry point for the console application.///*这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita S.Raghavan (University of North Carolina at Charlotte)修正。

代码保证尽可能少，实际上也不必查错。

对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。

注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。

该系统使用比率选择、精华模型、单点杂交和均匀变异。

如果用 Gaussian变异替换均匀变异，可能得到更好的效果。

代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。

读者可以从, 目录 coe/evol中的文件prog.c中获得。

要求输入的文件应该命名为‘gadata.txt’；系统产生的输出文件为‘galog.txt’。

输入的文件由几行组成：数目对应于变量数。

且每一行提供次序——对应于变量的上下界。

如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。

*/#include <stdio.h>#include <stdlib.h>#include <math.h>/* Change any of these parameters to match your needs *///请根据你的需要来修改以下参数#define POPSIZE 50 /* population size 种群大小*/#define MAXGENS 1000 /* max. number of generations 最大基因个数*/const int NVARS = 3; /* no. of problem variables 问题变量的个数*/#define PXOVER 0.8 /* probability of crossover 杂交概率*/#define PMUTATION 0.15 /* probability of mutation 变异概率*/#define TRUE 1#define FALSE 0int generation; /* current generation no. 当前基因个数*/int cur_best; /* best individual 最优个体*/FILE *galog; /* an output file 输出文件指针*/struct genotype /* genotype (GT), a member of the population 种群的一个基因的结构体类型*/{double gene[NVARS]; /* a string of variables 变量*/double fitness; /* GT's fitness 基因的适应度*/double upper[NVARS]; /* GT's variables upper bound 基因变量的上界*/double lower[NVARS]; /* GT's variables lower bound 基因变量的下界*/double rfitness; /* relative fitness 比较适应度*/double cfitness; /* cumulative fitness 积累适应度*/};struct genotype population[POPSIZE+1]; /* population 种群*/struct genotype newpopulation[POPSIZE+1]; /* new population; 新种群*//* replaces the old generation *///取代旧的基因/* Declaration of procedures used by this genetic algorithm *///以下是一些函数声明void initialize(void);double randval(double, double);void evaluate(void);void keep_the_best(void);void elitist(void);void select(void);void crossover(void);void Xover(int,int);void swap(double *, double *);void mutate(void);void report(void);/**************************************** ***********************//* Initialization function: Initializes the values of genes *//* within the variables bounds. It also initializes (to zero) *//* all fitness values for each member of the population. It *//* reads upper and lower bounds of each variable from the *//* input file `gadata.txt'. It randomlygenerates values *//* between these bounds for each gene of each genotype in the *//* population. The format of the input file `gadata.txt' is *//* var1_lower_bound var1_upper bound */ /* var2_lower_bound var2_upper bound ... */ /**************************************** ***********************/void initialize(void){FILE *infile;int i, j;double lbound, ubound;if ((infile = fopen("gadata.txt","r"))==NULL){fprintf(galog,"\nCannot open input file!\n");exit(1);}/* initialize variables within the bounds *///把输入文件的变量界限输入到基因结构体中for (i = 0; i < NVARS; i++){fscanf(infile, "%lf",&lbound);fscanf(infile, "%lf",&ubound);for (j = 0; j < POPSIZE; j++){population[j].fitness = 0;population[j].rfitness = 0;population[j].cfitness = 0;population[j].lower[i] = lbound;population[j].upper[i]= ubound;population[j].gene[i] = randval(population[j].lower[i],population[j].upper[i]);}}fclose(infile);}/**************************************** *******************//* Random value generator: Generates a value within bounds *//**************************************** *******************///随机数产生函数double randval(double low, double high) {double val;val = ((double)(rand()%1000)/1000.0)*(high - low) + low;return(val);}/*************************************************************//* Evaluation function: This takes a user defined function. *//* Each time this is changed, the code has to be recompiled. *//* The current function is: x[1]^2-x[1]*x[2]+x[3] *//**************************************** *********************///评价函数，可以由用户自定义，该函数取得每个基因的适应度void evaluate(void){int mem;int i;double x[NVARS+1];for (mem = 0; mem < POPSIZE; mem++){for (i = 0; i < NVARS; i++)x[i+1] = population[mem].gene[i];population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];}}/**************************************** ***********************//* Keep_the_best function: This function keeps track of the *//* best member of the population. Note that the last entry in *//* the array Population holds a copy of the best individual *//**************************************** ***********************///保存每次遗传后的最佳基因void keep_the_best(){int mem;int i;cur_best = 0;/* stores the index of the best individual*///保存最佳个体的索引for (mem = 0; mem < POPSIZE; mem++){if (population[mem].fitness > population[POPSIZE].fitness){cur_best = mem;population[POPSIZE].fitness = population[mem].fitness;}}/* once the best member in the population is found, copy the genes *///一旦找到种群的最佳个体，就拷贝他的基因for (i = 0; i < NVARS; i++)population[POPSIZE].gene[i] = population[cur_best].gene[i];}/**************************************** ************************//* Elitist function: The best member of the previous generation *//* is stored as the last in the array. If the best member of *//* the current generation is worse then the best member of the *//* previous generation, the latter one would replace the worst *//* member of the current population *//**************************************** ************************///搜寻杰出个体函数：找出最好和最坏的个体。

用遗传算法通过复制交叉过程循环求解函数f(x)=x^2在[0,31]区间上的最大值点x。

代码如下：using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Project2{class Class1{public int ff(int a){return a * a;}public int Max(int[] args){int s = 0;int m = args[0];for (int i = 0; i < args.Length; i++){if (m < args[i]){m = args[i];s = i;}}return s;}public int Min(int[] args){int s = 0;int m = args[0];for (int i = 0; i < args.Length; i++){if (m > args[i]){m = args[i];s = i;}}return s;}static void Main(String[] args){string[] A = new string[4];A[0] = "01101";A[1] = "11000";A[2] = "01000";A[3] = "10011";Class1 cl = new Class1();Random a = new Random();int[] x = new int[4];//存储x值float[] C = new float[4];//存储每个适配值所占比例int[] B = new int[4];//存储x对应的y值int k1 = 0;//交叉时所需的随机整数范围在0-4之间int k2 = 0;//交叉时所需的随机整数范围在0-4之间int max = 0;//适配值总最大的值在x中的下标int sum = 0;//所有适配值对应的函数值的总和int min = 0;//适配值总最小的值在x中的下标int t1 = 0;//初始最大值int ave1 = 0;//初始平均值int t2 = 0;//每次循环得出的最大值int ave2 = 0;//每次循环得出的平均值int smax = 20;//循环最大次数for (int l = 1; l < smax; l++){for (int i = 0; i < 4; i++){x[i] = Convert.ToInt32(A[i],2);//x[i] = Int32.Parse(A[i]);//怎么把二进制数转化为十进制数}for (int i = 0; i < 4; i++){B[i] = cl.ff(x[i]);//求出f(x)=x^2的值存入B中sum += B[i];}for (int i = 0; i < 4; i++){C[i] = B[i] / sum;}max =cl.Max(x);min = cl.Min(x);t2 = x[max];//用来记录每次循环的最大值ave2 = sum / 4;//用来记录每次循环的平均值if (t2 < t1 && ave2 < ave1){break;}else{t1 = t2;ave1 = ave2;}for (int i = 0; i < 4; i++) //输出每次循环的结果{System.Console.Write(x[i]);//System.Console.Write(' ');}System.Console.Write("\n");//换行A[min] = A[max];//适配值较小的被淘汰，由最大的取代k1 = a.Next(1,4);//从1-4之间选一个随机数k2 =a.Next(1,4);if (max + min != 3){string s1 = A[max].Substring(k1);//从第k个数开始获得后面的子串string s2 = A[min].Substring(k2);string s3 = A[3 - max].Substring(k1);string s4 = A[3 - min].Substring(k2);A[max] = A[max].Substring(0, k1) + s3;A[min] = A[min].Substring(0, k2) + s4;A[3 - max] = A[3 - max].Substring(0,k1) + s1;A[3 - min] = A[3 - min].Substring(0,k2) + s2;}elseif ((max > min) && (min + 1 == max))//max=2 min=1 {string s1 = A[max].Substring(k1);//从第k个数开始获得后面的子串string s2 = A[min].Substring(k2);string s3 = A[3].Substring(k1);string s4 = A[0].Substring(k2);A[max] = A[max].Substring(0,k1) + s3;A[min] = A[min].Substring(0,k2) + s4;A[3] = A[3].Substring(0,k1) + s1;A[3] = A[3].Substring(0,k2) + s2;}elseif((max < min) && (min == max + 1))//max=1 min=2 {string s1 = A[max].Substring(k1);//从第k 个数开始获得后面的子串string s2 = A[min].Substring(k2);string s3 = A[0].Substring(k1);string s4 = A[3].Substring(k2);A[max] = A[max].Substring(0,k1) + s3;A[min] = A[min].Substring(0,k2) + s4;A[0] = A[0].Substring(0,k1) + s1;A[3] = A[3].Substring(0,k2) + s2;}elseif ((max > min) && (max ==min + 3))//max=3 min=0{string s1 = A[max].Substring(k1);//从第k个数开始获得后面的子串string s2 = A[min].Substring(k2);string s3 = A[2].Substring(k1);string s4 = A[1].Substring(k2);A[max] = A[max].Substring(0,k1) + s3; A[min] = A[min].Substring(0,k2) + s4; A[2] = A[2].Substring(0,k1) + s1;A[1] = A[1].Substring(0,k2) + s2;}elseif ((max < min) && ( min==max +3 ))//max=0 min=3{string s1 =A[max].Substring(k1);//从第k个数开始获得后面的子串string s2 = A[min].Substring(k2);string s3 = A[1].Substring(k1);string s4 = A[2].Substring(k2); A[max] = A[max].Substring(0,k1) + s3;A[min] = A[min].Substring(0,k2) + s4;A[1] = A[1].Substring(0,k1) + s1;A[1] = A[1].Substring(0,k2) + s2; }}Console.WriteLine("最大值是={0}", t1);}}}输出如下：结论：由图可知每次循环结果不唯一。

include <stdio.h>#include<graphics.h>#include <math.h>#include "graph.c"/* 全局变量*/struct individual /* 个体*/{unsigned *chrom; /* 染色体*/double fitness; /* 个体适应度*/double varible; /* 个体对应的变量值*/int xsite; /* 交叉位置*/int parent[2]; /* 父个体*/int *utility; /* 特定数据指针变量*/};struct bestever /* 最佳个体*/{unsigned *chrom; /* 最佳个体染色体*/double fitness; /* 最佳个体适应度*/double varible; /* 最佳个体对应的变量值*/int generation; /* 最佳个体生成代*/};struct individual *oldpop; /* 当前代种群*/struct individual *newpop; /* 新一代种群*/struct bestever bestfit; /* 最佳个体*/double sumfitness; /* 种群中个体适应度累计*/double max; /* 种群中个体最大适应度*/double avg; /* 种群中个体平均适应度*/double min; /* 种群中个体最小适应度*/float pcross; /* 交叉概率*/float pmutation; /* 变异概率*/int popsize; /* 种群大小*/int lchrom; /* 染色体长度*/int chromsize; /* 存储一染色体所需字节数*/int gen; /* 当前世代数*/int maxgen; /* 最大世代数*/int run; /* 当前运行次数*/int maxruns; /* 总运行次数*/int printstrings; /* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出*/int nmutation; /* 当前代变异发生次数*/int ncross; /* 当前代交叉发生次数*//* 随机数发生器使用的静态变量*/static double oldrand[55];static int jrand;static double rndx2;static int rndcalcflag;/* 输出文件指针*/FILE *outfp ;/* 函数定义*/void advance_random();int flip(float);rnd(int, int);void randomize();double randomnormaldeviate();float randomperc(),rndreal(float,float);void warmup_random(float);void initialize(),initdata(),initpop();void initreport(),generation(),initmalloc();void freeall(),nomemory(char *),report();void writepop(),writechrom(unsigned *);void preselect();void statistics(struct individual *);void title(),repchar (FILE *,char *,int);void skip(FILE *,int);int select();void objfunc(struct individual *);int crossover (unsigned *, unsigned *, unsigned *, unsigned *); void mutation(unsigned *);void initialize() /* 遗传算法初始化*/{/* 键盘输入遗传算法参数*/initdata();/* 确定染色体的字节长度*/chromsize = (lchrom/(8*sizeof(unsigned)));if(lchrom%(8*sizeof(unsigned))) chromsize++;/*分配给全局数据结构空间*/initmalloc();/* 初始化随机数发生器*/randomize();/* 初始化全局计数变量和一些数值*/nmutation = 0;ncross = 0;bestfit.fitness = 0.0;bestfit.generation = 0;/* 初始化种群，并统计计算结果*/initpop();statistics(oldpop);initreport();}void initdata() /* 遗传算法参数输入*/{char answer[2];setcolor(9);disp_hz16("种群大小(20-100)：",100,150,20);gscanf(320,150,9,15,4,"%d", &popsize);if((popsize%2) != 0){fprintf(outfp, "种群大小已设置为偶数\n");popsize++;};setcolor(9);disp_hz16("染色体长度(8-40)：",100,180,20);gscanf(320,180,9,15,4,"%d", &lchrom);setcolor(9);disp_hz16("是否输出染色体编码(y/n)：",100,210,20);printstrings=1;gscanf(320,210,9,15,4,"%s", answer);if(strncmp(answer,"n",1) == 0) printstrings = 0;setcolor(9);disp_hz16("最大世代数(100-300)：",100,240,20);gscanf(320,240,9,15,4,"%d", &maxgen);setcolor(9);disp_hz16("交叉率(0.2-0.9)：",100,270,20);gscanf(320,270,9,15,5,"%f", &pcross);setcolor(9);disp_hz16("变异率(0.01-0.1)：",100,300,20);gscanf(320,300,9,15,5,"%f", &pmutation);}void initpop() /* 随机初始化种群*/{int j, j1, k, stop;unsigned mask = 1;for(j = 0; j < popsize; j++){for(k = 0; k < chromsize; k++){oldpop[j].chrom[k] = 0;if(k == (chromsize-1))stop = lchrom - (k*(8*sizeof(unsigned)));elsestop =8*sizeof(unsigned);for(j1 = 1; j1 <= stop; j1++){oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;if(flip(0.5))oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;}}oldpop[j].parent[0] = 0; /* 初始父个体信息*/oldpop[j].parent[1] = 0;oldpop[j].xsite = 0;objfunc(&(oldpop[j])); /* 计算初始适应度*/}}void initreport() /* 初始参数输出*/{void skip();skip(outfp,1);fprintf(outfp," 基本遗传算法参数\n");fprintf(outfp," -------------------------------------------------\n");fprintf(outfp," 种群大小(popsize) = %d\n",popsize);fprintf(outfp," 染色体长度(lchrom) = %d\n",lchrom);fprintf(outfp," 最大进化代数(maxgen) = %d\n",maxgen);fprintf(outfp," 交叉概率(pcross) = %f\n", pcross);fprintf(outfp," 变异概率(pmutation) = %f\n", pmutation);fprintf(outfp," -------------------------------------------------\n");skip(outfp,1);fflush(outfp);}void generation(){int mate1, mate2, jcross, j = 0;/* 每代运算前进行预选*/preselect();/* 选择, 交叉, 变异*/do{/* 挑选交叉配对*/mate1 = select();mate2 = select();/* 交叉和变异*/jcross = crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom);mutation(newpop[j].chrom);mutation(newpop[j+1].chrom);/* 解码, 计算适应度*/objfunc(&(newpop[j]));/*记录亲子关系和交叉位置*/newpop[j].parent[0] = mate1+1;newpop[j].xsite = jcross;newpop[j].parent[1] = mate2+1;objfunc(&(newpop[j+1]));newpop[j+1].parent[0] = mate1+1;newpop[j+1].xsite = jcross;newpop[j+1].parent[1] = mate2+1;j = j + 2;}while(j < (popsize-1));}void initmalloc() /*为全局数据变量分配空间*/ {unsigned nbytes;char *malloc();int j;/* 分配给当前代和新一代种群内存空间*/nbytes = popsize*sizeof(struct individual);if((oldpop = (struct individual *) malloc(nbytes)) == NULL)nomemory("oldpop");if((newpop = (struct individual *) malloc(nbytes)) == NULL)nomemory("newpop");/* 分配给染色体内存空间*/nbytes = chromsize*sizeof(unsigned);for(j = 0; j < popsize; j++){if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) nomemory("oldpop chromosomes");if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) nomemory("newpop chromosomes");}if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)nomemory("bestfit chromosome");}void freeall() /* 释放内存空间*/{int i;for(i = 0; i < popsize; i++){free(oldpop[i].chrom);free(newpop[i].chrom);}free(oldpop);free(newpop);free(bestfit.chrom);}void nomemory(string) /* 内存不足，退出*/char *string;{fprintf(outfp,"malloc: out of memory making %s!!\n",string);exit(-1);}void report() /* 输出种群统计结果*/{void repchar(), skip();void writepop(), writestats();repchar(outfp,"-",80);skip(outfp,1);if(printstrings == 1){repchar(outfp," ",((80-17)/2));fprintf(outfp,"模拟计算统计报告\n");fprintf(outfp, "世代数%3d", gen);repchar(outfp," ",(80-28));fprintf(outfp, "世代数%3d\n", (gen+1));fprintf(outfp,"个体染色体编码");repchar(outfp," ",lchrom-5);fprintf(outfp,"适应度父个体交叉位置");fprintf(outfp,"染色体编码");repchar(outfp," ",lchrom-5);fprintf(outfp,"适应度\n");repchar(outfp,"-",80);skip(outfp,1);writepop(outfp);repchar(outfp,"-",80);skip(outfp,1);}fprintf(outfp,"第%d 代统计: \n",gen);fprintf(outfp,"总交叉操作次数= %d, 总变异操作数= %d\n",ncross,nmutation);fprintf(outfp," 最小适应度：%f 最大适应度：%f 平均适应度%f\n", min,max,avg);fprintf(outfp," 迄今发现最佳个体=> 所在代数：%d ", bestfit.generation);fprintf(outfp," 适应度：%f 染色体：", bestfit.fitness);writechrom((&bestfit)->chrom);fprintf(outfp," 对应的变量值: %f", bestfit.varible);skip(outfp,1);repchar(outfp,"-",80);skip(outfp,1);}void writepop(){struct individual *pind;int j;for(j=0; j<popsize; j++){fprintf(outfp,"%3d) ",j+1);/* 当前代个体*/pind = &(oldpop[j]);writechrom(pind->chrom);fprintf(outfp," %8f | ", pind->fitness);/* 新一代个体*/pind = &(newpop[j]);fprintf(outfp,"(%2d,%2d) %2d ",pind->parent[0], pind->parent[1], pind->xsite);writechrom(pind->chrom);fprintf(outfp," %8f\n", pind->fitness);}}void writechrom(chrom) /* 输出染色体编码*/ unsigned *chrom;{int j, k, stop;unsigned mask = 1, tmp;for(k = 0; k < chromsize; k++){tmp = chrom[k];if(k == (chromsize-1))stop = lchrom - (k*(8*sizeof(unsigned)));elsestop =8*sizeof(unsigned);for(j = 0; j < stop; j++){if(tmp&mask)fprintf(outfp,"1");elsefprintf(outfp,"0");tmp = tmp>>1;}}}void preselect(){int j;sumfitness = 0;for(j = 0; j < popsize; j++) sumfitness += oldpop[j].fitness; }int select() /* 轮盘赌选择*/{extern float randomperc();float sum, pick;int i;pick = randomperc();sum = 0;if(sumfitness != 0){for(i = 0; (sum < pick) && (i < popsize); i++)sum += oldpop[i].fitness/sumfitness;}elsei = rnd(1,popsize);return(i-1);}void statistics(pop) /* 计算种群统计数据*/struct individual *pop;{int i, j;sumfitness = 0.0;min = pop[0].fitness;max = pop[0].fitness;/* 计算最大、最小和累计适应度*/for(j = 0; j < popsize; j++){sumfitness = sumfitness + pop[j].fitness;if(pop[j].fitness > max) max = pop[j].fitness;if(pop[j].fitness < min) min = pop[j].fitness;/* new global best-fit individual */if(pop[j].fitness > bestfit.fitness){for(i = 0; i < chromsize; i++)bestfit.chrom[i] = pop[j].chrom[i];bestfit.fitness = pop[j].fitness;bestfit.varible = pop[j].varible;bestfit.generation = gen;}}/* 计算平均适应度*/avg = sumfitness/popsize;}void title(){settextstyle(0,0,4);gprintf(110,15,4,0,"SGA Optimizer");setcolor(9);disp_hz24("基本遗传算法",220,60,25);}void repchar (outfp,ch,repcount)FILE *outfp;char *ch;int repcount;{int j;for (j = 1; j <= repcount; j++) fprintf(outfp,"%s", ch);}void skip(outfp,skipcount)FILE *outfp;int skipcount;{int j;for (j = 1; j <= skipcount; j++) fprintf(outfp,"\n");}void objfunc(critter) /* 计算适应度函数值*/ struct individual *critter;{unsigned mask=1;unsigned bitpos;unsigned tp;double pow(), bitpow ;int j, k, stop;critter->varible = 0.0;for(k = 0; k < chromsize; k++){if(k == (chromsize-1))stop = lchrom-(k*(8*sizeof(unsigned)));elsestop =8*sizeof(unsigned);tp = critter->chrom[k];for(j = 0; j < stop; j++){bitpos = j + (8*sizeof(unsigned))*k;if((tp&mask) == 1){bitpow = pow(2.0,(double) bitpos);critter->varible = critter->varible + bitpow;}tp = tp>>1;}}critter->varible =-1+critter->varible*3/(pow(2.0,(double)lchrom)-1);critter->fitness =critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;}void mutation(unsigned *child) /*变异操作*/{int j, k, stop;unsigned mask, temp = 1;for(k = 0; k < chromsize; k++){mask = 0;if(k == (chromsize-1))stop = lchrom - (k*(8*sizeof(unsigned)));elsestop = 8*sizeof(unsigned);for(j = 0; j < stop; j++){if(flip(pmutation)){mask = mask|(temp<<j);nmutation++;}}child[k] = child[k]^mask;}}int crossover (unsigned *parent1, unsigned *parent2, unsigned *child1, unsigned *child2) /* 由两个父个体交叉产生两个子个体*/{int j, jcross, k;unsigned mask, temp;if(flip(pcross)){jcross = rnd(1 ,(lchrom - 1));/* Cross between 1 and l-1 */ncross++;for(k = 1; k <= chromsize; k++){if(jcross >= (k*(8*sizeof(unsigned)))){child1[k-1] = parent1[k-1];child2[k-1] = parent2[k-1];}else if((jcross < (k*(8*sizeof(unsigned)))) && (jcross > ((k-1)*(8*sizeof(unsigned))))){mask = 1;for(j = 1; j <= (jcross-1-((k-1)*(8*sizeof(unsigned)))); j++){temp = 1;mask = mask<<1;mask = mask|temp;}child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);}else{child1[k-1] = parent2[k-1];child2[k-1] = parent1[k-1];}}}else{for(k = 0; k < chromsize; k++){child1[k] = parent1[k];child2[k] = parent2[k];}jcross = 0;}return(jcross);}void advance_random() /* 产生55个随机数*/{int j1;double new_random;for(j1 = 0; j1 < 24; j1++){new_random = oldrand[j1] - oldrand[j1+31];if(new_random < 0.0) new_random = new_random + 1.0;oldrand[j1] = new_random;}for(j1 = 24; j1 < 55; j1++){new_random = oldrand [j1] - oldrand [j1-24];if(new_random < 0.0) new_random = new_random + 1.0;oldrand[j1] = new_random;}}int flip(float prob) /* 以一定概率产生0或1 */{float randomperc();if(randomperc() <= prob)return(1);elsereturn(0);}void randomize() /* 设定随机数种子并初始化随机数发生器*/ {float randomseed;int j1;for(j1=0; j1<=54; j1++)oldrand[j1] = 0.0;jrand=0;do{setcolor(9);disp_hz16("随机数种子[0-1]:",100,330,20);gscanf(320,330,9,15,4,"%f", &randomseed);}while((randomseed < 0.0) || (randomseed > 1.0));warmup_random(randomseed);}double randomnormaldeviate() /* 产生随机标准差*/{double sqrt(), log(), sin(), cos();float randomperc();double t, rndx1;if(rndcalcflag){ rndx1 = sqrt(- 2.0*log((double) randomperc()));t = 6.2831853072 * (double) randomperc();rndx2 = rndx1 * sin(t);rndcalcflag = 0;return(rndx1 * cos(t));}else{rndcalcflag = 1;return(rndx2);}}float randomperc() /*与库函数random()作用相同, 产生[0,1]之间一个随机数*/{jrand++;if(jrand >= 55){jrand = 1;advance_random();}return((float) oldrand[jrand]);}int rnd(low, high) /*在整数low和high之间产生一个随机整数*/int low,high;{int i;float randomperc();if(low >= high)i = low;else{i = (randomperc() * (high - low + 1)) + low;if(i > high) i = high;}return(i);}void warmup_random(float random_seed) /* 初始化随机数发生器*/{int j1, ii;double new_random, prev_random;oldrand[54] = random_seed;new_random = 0.000000001;prev_random = random_seed;for(j1 = 1 ; j1 <= 54; j1++){ii = (21*j1)%54;oldrand[ii] = new_random;new_random = prev_random-new_random;if(new_random<0.0) new_random = new_random + 1.0;prev_random = oldrand[ii];}advance_random();advance_random();advance_random();jrand = 0;}main(argc,argv) /* 主程序*/int argc;char *argv[];{struct individual *temp;FILE *fopen();void title();char *malloc();if((outfp = fopen(argv[1],"w")) == NULL){fprintf(stderr,"Cannot open output file %s\n",argv[1]);exit(-1);}g_init();setcolor(9);title();disp_hz16("输入遗传算法执行次数(1-5):",100,120,20);gscanf(320,120,9,15,4,"%d",&maxruns);for(run=1; run<=maxruns; run++){initialize();for(gen=0; gen<maxgen; gen++){fprintf(outfp,"\n第%d / %d 次运行: 当前代为%d, 共%d 代\n", run,maxruns,gen,maxgen);/* 产生新一代*/generation();/* 计算新一代种群的适应度统计数据*/statistics(newpop);/* 输出新一代统计数据*/report();temp = oldpop;oldpop = newpop;newpop = temp;}freeall();}}。