简单遗传算法实例

#include<stdio.h> #include<stdlib.h> #include<time.h> #include<math.h> #define POPSIZE 500 //种群的大小 #define CHROMLENGTH 8 //染色体的长度 int iPopSize;//种群的大小 int iMaxGeneration;//最大世代数 double pc=0.0;//交叉率 double pm=0.0;// struct Individual { int Chrom[CHROMLENGTH];//染色体的二进制表达形式 double dValue;//染色体的值 double dFitness;//染色体的适应值 }; int iGeneration;//当前执行的世代数 int iBestIndex;//最好的染色体索引序号 int iWorstIndex;//最差的染色体索引序号 struct Individual BestIndividual;//最佳染色体个体 struct Individual WorstIndividual;//最差染色体个体 struct Individual CurrentBest;//当前最好的染色体个体 struct Individual Population[POPSIZE];//种群数组 //函数声明 void GenerateInitialPopulation();//初始化当代种群 void GenerateNextPopulation();//产生下一代种群 void EvaluatePopulation();//评价种群 void CalculatePopulation();//计算种群适应度 double DecodeChromosome(int,int);//染色体解码 void FindBestAndWorstIndividual();//寻找最好和最坏的染色体 void PerformEvolution();//进行演变进化 void SelectOperator();//选择操作 void CrossoverOperator();//交换操作 void MutationOperator();//变异操作 void Input();//输入接口 void OutPutTextReport();//输出文字报告 //种群初始化,为每个染色体赋值随机的编码 void GenerateInitialPopulation() { int t,m; srand((unsigned)time(NULL));//产生随机数的种子 for(int i=0;i<iPopSize;i++) { for(int j=0;j<CHROMLENGTH;j++) { t=rand(); //Population[i].Chrom[j]=(t%10<5)?0:1;//为染色体中的每个基因赋值0或1 m=t%10; if(m<5) { Population[i].Chrom[j]=0; } else { Population[i].Chrom[j]=1; } } } } //生成下一代 void GenerateNextPopulation() { SelectOperator(); CrossoverOperator(); MutationOperator(); } //评价种群，计算种群的适应度，找到最好、最差的染色体 void EvaluatePopulation() { CalculatePopulation();//计算种群个体的适应度 FindBestAndWorstIndividual();//找到最好和最差的染色体个体 } //计算染色体个体适应值和适应度 void CalculatePopulation() { printf("正在计算种群的适应度...!"); for(int i=0;i<iPopSize;i++) { double temp; temp=DecodeChromosome(i,CHROMLENGTH);//计算个体适应值 Population[i].dValue =(double)temp; Population[i].dFitness =Population[i].dValue*Population[i].dValue; } } //给染色体编码,既二进制转换为十进制，进而获得其值value double DecodeChromosome(int pop_index,int length ) { int i=0; double decimal=0; for(i=0;i<length;i++) { decimal+=Population[pop_index].Chrom [i]*pow(2,i);//二进制转换为十进制 } return (decimal); } //求最佳最差个体 void FindBestAndWorstIndividual() { int i; double sum=0.0; BestIndividual=Population[0]; WorstIndividual=Population[0]; for(i=1;i<iPopSize;i++) { if(Population[i].dFitness >BestIndividual.dFitness )//依次比较选出最佳的个体 { BestIndividual=Population[i]; iBestIndex=i; } else if(Population[i].dFitness <WorstIndividual.dFitness )//依次比较，选出最差个体 { WorstIndividual=Population[i]; iWorstIndex=i; } sum+=Population[i].dFitness ;//sum存放种群的总适应值 } if(iGeneration==0) { CurrentBest=BestIndividual;//第一代最好的暂时存放在currentbest } else { if(BestIndividual.dFitness>=CurrentBest.dFitness)//选出以往几代中最好的放到CurrentBest { CurrentBest=BestIndividual; } } } ///////////演示评价结果？？？？？？？？？ void PerformEvolution() { if(BestIndividual.dFitness >CurrentBest.dFitness) { CurrentBest=Population[iBestIndex]; } else { Population[iWorstIndex]=CurrentBest; } } void SelectOperator()//比例选择算法 { int i,index; double p,sum=0.0;//p存放随机概率，sum存放个体实行率和累计适应率 double cfitness[POPSIZE];//当代种群染色体个体的适应率 struct Individual NewPopulation[POPSIZE];//新种群 srand((unsigned)time(NULL)); for(i=0;i<iPopSize;i++) { sum+=Population[i].dFitness ;//sum存放种群适应值总和 } for(i=0;i<iPopSize;i++) { cfitness[i]=Population[i].dFitness/sum;//cfitness得到每个个体自身适应率 } for(i=1;i<iPopSize;i++) { cfitness[i]=cfitness[i-1]+cfitness[i];//得到每个个体与之前所有个体的累计适应率 } for(i=0;i<iPopSize;i++)//实现轮盘赌算法,执行iPopSize次 { p=rand()%1000/1000.0;//得到千分位的小数????????每次循环是否p的值都不同 index=0; while(p>cfitness[index]) { index++; } NewPopulation[i]=Population[index];//选出的个体组成新一代 } } //交叉算法 void CrossoverOperator() { int i,j; int index[POPSIZE]; int point,temp; double p; srand((unsigned)time(NULL)); for(i=0;i<iPopSize;i++)//初始化index数组 { index[i]=i; } for(i=0;i<iPopSize;i++)//对数组序号进行随机交换，打乱染色体的顺序，这样交换时选择的index[i+1]其实是随机选择的 { point=rand()%(iPopSize-i); temp=index[i]; index[i]=index[point+i]; index[point+i]=temp; } for(i=0;i<iPopSize-1;i+=2) { p=rand()%1000/1000.0; if(p<pc) //单点交叉算法，？？？？？？？为什么要进行判断 { point=rand()%(CHROMLENGTH-1)+1; for(j=point;j<CHROMLENGTH;j++) { temp=Population[index[i]].Chrom [j]; Population[index[i]].Chrom [j]=Population[index[i+1]].Chrom [j]; Population[index[i+1]].Chrom [j]=temp; } } } } //变异操作 void MutationOperator() { int i,j; double p; srand((unsigned)time(NULL)); for(i=0;i<iPopSize;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",&iPopSize);//输入种群大小，必须是偶数 iPopSize=50; if((iPopSize%2)!=0) { printf(" 种群大小已设置为偶数\n"); iPopSize++; } printf(" 最大世代数（100-300）：");//输入最大世代数 //scanf("%d",&iMaxGeneration); iMaxGeneration=300; printf(" 交叉率（0.2-0.99）：");//输入交叉率 //scanf("%lf",&pc); pc=0.5; printf(" 变异率（0.001-0.1）:");//输入变异率 //scanf("%lf",&pm); pm=0.01; } //数据输出 void OutPutTextReport() { int i; double sum; double average; sum=0.0; for(i=0;i<iPopSize;i++) { sum+=Population[i].dValue ; } average=sum/iPopSize; printf("当前世代=%d\n当前世代染色体平均值=%f\n当前世代染色体最高值=%f\n",iGeneration,average,Population[iBestIndex].dValue ); } void main() { int i; srand((unsigned)time(NULL)); printf("本程序为求函数y=x*x的最大值\n"); iGeneration=0; Input();//初始化种群大小，交叉率，变异率，最大世代数 printf("iPopSize %d;iMaxGeneration %d;pc %f;pm%f\n\n",iPopSize,iMaxGeneration,pc,pm); GenerateInitialPopulation();//产生初始化种群，为每个染色体赋值随机的编码 EvaluatePopulation();//评价当前种群，计算种群的适应度，找到最好、最差的染色体 while(iGeneration<iMaxGeneration) { iGeneration++; GenerateNextPopulation();//生成下一代种群 EvaluatePopulation();//进行子代进化 //PerformEvolution();//进行子代进化 OutPutTextReport(); } printf("\n"); printf(" 统计结果： "); printf("\n"); printf("最大函数值等于：%f\n",CurrentBest.dFitness ); printf("其染色体编码为："); for(i=0;i<CHROMLENGTH;i++) printf("%d",CurrentBest.Chrom [i]); }