遗传算法并行源程序

//THBGFSHFGBCVXNCH#defineWIN32_LEAN_AND_MEAN#include<stdio.h>#include<tchar.h>#include<stdlib.h>#include<malloc.h>#include<math.h>#include<iostream>#include<mpi.h>#include<windows.h>#pragmacomment(lib,"Wininet.lib")#pragmacomment(lib,"mpi.lib")#pragmacomment(lib,"cxx.lib")#definePOPSIZE6#defineMAXGENS10#defineNVARS3#definePXOVER0.8#definePMUTATION0.15#defineTRUE1#defineFALSE0//从Windows头中排除极少使用的资料/*群体大小，其实就是基因总数*//*进化代数*//*问题变量数，即基因的长度*//*交叉概率*//*变异概率*/intgeneration;intcur_best;FILE*galog;/*记录当前已经进化的代数*//*最优个体*//*日志文件*//*基因类型*/structgenotype{doublegene[NVARS];doubleupper[NVARS];doublelower[NVARS];doublefitness;doublerfitness;doublecfitness;};structgenotypepopulation[POPSIZE+1];/*种群*/structgenotypenewpopulation[POPSIZE+1];/*新种群*/voidinitialize(void);doublerandval(double,double);voidkeep_the_best(void);voidelitist(void);voidselect(void);voidcrossover(void);/*染色体字符串*//*每个基于的上界*//*每个基因的下界*//*个体适应度*//*相对适应度*//*累积适应度*//*种群初始化函数*//*随机函数*//*寻找最优个体*//*保持最优*//*选择算子*//*交叉算子*/voidXover(int,int);/*交叉操作*/voidswap(double*,double*);/*交换*/voidevaluate(void);/*个体适应度评价*/voidworker(genotype*,int)/*从处理器操作，突变和适应度评价*/voidreport(void);/*记录*//**************************************************************初始化基因值，适应值。从gadata.txt中读入每个变量的上下限，然后随机产生。**************************************************************/voidinitialize(void){FILE*infile;inti,j;doublelbound,ubound;if((infile=fopen(”gadata.txt”,”r”))==NULL){fprintf(galog,"\nCannotopeninputfile!\n");exit(1);}for(i=0;i<NVARS;i++)//nvars==3,问题变量数{fscanf(infile,"%lf",&lbound);fscanf(infile,"%lf",&ubound);for(j=0;j<POPSIZE;j++)//50{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);}/***********************************************************/*//*在上下界间产生一个数/***********************************************************/doublerandval(doublelow,doublehigh){doubleval;val=((double)(rand()%1000)/1000.0)*(high-low)+low;return(val);}/***************************************************************//*Keep_the_bestfunction:保持对最优个体的追踪*//***************************************************************/voidkeep_the_best()//将最优的值放在最后一个空位上{intmem;inti;cur_best=0;/*最优个体索引*/for(mem=0;mem<POPSIZE;mem++){*/if(population[mem].fitness>population[POPSIZE].fitness){cur_best=mem;population[POPSIZE].fitness=population[mem].fitness;}}/*oncethebestmemberinthepopulationisfound,copythegenes*/for(i=0;i<NVARS;i++)population[POPSIZE].gene[i]=population[cur_best].gene[i];}/****************************************************************//*Elitistfunction:如果这一代的最好值比上一代的*//*差，那么用上一代的最好值替代本代的最差值*//****************************************************************/voidelitist(){inti;doublebest,worst;/*bestandworstfitnessvalues*/intbest_mem,worst_mem;/*indexesofthebestandworstmember*/best=population[0].fitness;worst=population[0].fitness;for(i=0;i<POPSIZE-1;++i)//找出最好和最坏的适应度{if(population[i].fitness>population[i+1].fitness){if(population[i].fitness>=best){best=population[i].fitness;best_mem=i;}if(population[i+1].fitness<=worst){worst=population[i+1].fitness;worst_mem=i+1;}}else{if(population[i].fitness<=worst){worst=population[i].fitness;worst_mem=i;}if(population[i+1].fitness>=best){best=population[i+1].fitness;best_mem=i+1;}}}/*如果新一代种群中的最优个体比前一代的最优个体好，*//*best取此值，反之用上一代最优个体取代当前代的最差个体。*/if(best>=population[POPSIZE].fitness){for(i=0;i<NVARS;i++)population[POPSIZE].gene[i]=population[best_mem].gene[i];population[POPSIZE].fitness=population[best_mem].fitness;}elsefor(i=0;i<NVARS;i++)population[worst_mem].gene[i]=population[POPSIZE].gene[i];population[worst_mem].fitness=population[POPSIZE].fitness;}}/*************************************************************************//*Selectionfunction:适者生存通过适应度大小筛选，适*//*应度越大，出现的次数越多(会有重复)*//*************************************************************************/voidselect(void)//{intmem,i,j,k=0;doublesum=0;doublep;/*计算适应度总和*/for(mem=0;mem<POPSIZE;mem++){sum+=population[mem].fitness;}/*计算相对适应度，有点像概率密度*/for(mem=0;mem<POPSIZE;mem++){population[mem].rfitness=population[mem].fitness/sum;}/*计算累计适应度，有点像分布函数*/population[0].cfitness=population[0].rfitness;for(mem=1;mem<POPSIZE;mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;}/*使用累计适应度确定幸存者，落在哪个概率区域就选择相应的概率区域上的染色体*/for(i=0;i<POPSIZE;i++){p=rand()%1000/1000.0;if(p<population[0].cfitness)newpopulation[i]=population]。];//选择else{for(j=0;j<POPSIZE;j++)if(p>=population[j].cfitness&&p<population[j+1].cfitness)newpopulation[i]=population[j+1];//选择}}/*确定全部的幸存者后，拷贝回population完成选择*/for(i=0;i<POPSIZE;i++)population[i]=newpopulation[i];}/***************************************************************//*Crossoverselection:单随机点交叉，前后两个*//*个体交叉，得到两个新的个体，原来的个体消失*/3/***************************************************************/voidcrossover(void){inti=0,mem,one;intfirst=0;/*countofthenumberofmemberschosen*/doublex;for(mem=0;mem<POPSIZE;++mem)x=rand()%1000/1000.0;if(x<PXOVER){++first;if(first%2==0)Xover(one,mem);else〃按交叉概率进行交叉〃相邻的两个交叉one=mem;}}}/**************************************************************//*Crossover:交叉操作*//**************************************************************/voidXover(intone,inttwo){inti;intpoint;/*crossoverpoint*//*selectcrossoverpoint*/if(NVARS>1){〃等于1时就没有交叉的必要if(NVARS==2)point=1;elsepoint=(rand()%(NVARS-1))+1;for(i=0;i<point;i++)swap(&population[one].gene[i],&population[two].gene[i]);3/*************************************************************//*Swap:互换*//*************************************************************/voidswap(double*x,double*y){doubletemp;temp=*x;*x=*y;*y=temp;doublebest_val;doubleavg;doublestddev;doublesum_square;doublesquare_sum;doublesum;种群中最高适应度值*//*种群中最高适应度值*//*平均适应度值*//*标准方差*//*平方的总数*//*总数的平方*/标准方差*/平方的总数*/总数的平方*//*适应度值总和doublebest_val;doubleavg;doublestddev;doublesum_square;doublesquare_sum;doublesum;种群中最高适应度值*//*种群中最高适应度值*//*平均适应度值*//*标准方差*//*平方的总数*//*总数的平方*/标准方差*/平方的总数*/总数的平方*//*适应度值总和*/适应度值总和*/for(i=0;i<NVARS;i++)x[i+1]=population[mem].gene[i];population[mem].fitness=x[1]*x[1]+x[2]*x[2]+x[3]*x[3];//计算得到适应度voidreport(void){forfor(inti=0;isum=0.0;sum_square=0.0;for(inti=0;i<POPSIZE;i++){sum+=population[i].fitness;sum_square+=population[i].fitness*population[i].fitness;}avg=sum/(double)POPSIZE;square_sum=avg*avg*POPSIZE;stddev=sqrt((sum_square-square_sum)/(POPSIZE-1));best_val=population[POPSIZE].fitness;fprintf(galog,"%5d\t\t%6.3f\t%6.3f\t%6.3f\n",generation,best_val,avg,stddev);printf("%5d\t\t%6.3f\t%6.3f\t%6.3f\n",generation,best_val,avg,stddev);voidworker(genotype*subpopulation,intmysize)/*突变和适应度评价操作*/{doublelbound,hbound;doublex;for(inti=0;i<mysize;i++){for(intj=0;j<NVARS;j++){

x=rand()%1000/1000.0;if(x<PMUTATION){lbound=subpopulation->lower[j];hbound=subpopulation->upper[j];subpopulation[i].gene[j]=randval(lbound,hbound);}}}//end变异〃适应度评价intmem;doublexchorm[NVARS+1];for(mem=0;mem<mysize;mem++){for(inti=0;i<NVARS;i++)xchorm[i+1]=subpopulation[mem].gene[i];subpopulation[mem].fitness=(xchorm[1]*xchorm[1])+(xchorm[1]*xchorm[2])+xchorm[3]*xchorm[3];//计算得到适应度F1}//end适应度评价}/****************************************************************//*主函数*//****************************************************************/voidmain(intargc,char*argv[]){intmyid,numprocs,mysize;inti,j;doublestarttime,endtime;MPI_Statusstatus;MPI_Requestrequest;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&myid);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);if(numprocs>1)mysize=POPSIZE/(numprocs-1);//每个从处理器上应该分配的个体数elseif(numprocs==1)mysize=POPSIZE;genotype*subpopulation=(genotype*)malloc(mysize*sizeof(genotype));if(!subpopulation){printf("不能获得%d个大小的空间\n",mysize);MPI_Abort(MPI_COMM_WORLD,1);}//自定义数据类型MPI_Datatypemystruct;intblocklens[6];MPI_Aintindices[6];MPI_Datatypeold_types[6];/各块中数据个数blocklens[0]=ARS;blocklens[1]=ARS;blocklens[2]=ARS;blocklens[3]=1;blocklens[4]=1;blocklens[5]=1;/数据类型for(i=0;i<6;i++)old_types[i]=MPI_DOUBLE;/求地址和相对偏移MPI_Address(&population->gene,&indices[0]);MPI_Address(&population->upper,&indices[1]);MPI_Address(&population->lower,&indices[2]);MPI_Address(&population->fitness,&indices[3]);MPI_Address(&population->rfitness,&indices[4]);MPI_Address(&population->cfitness,&indices[5]);indices[5]=indices[5]-indices[0];indices[4]=indices[4]-indices[0];indices[3]=indices[3]-indices[0];indices[2]=indices[2]-indices[0];indices[1]=indices[1]-indices[0];indices[0]=0;MPI_Type_struct(6,blocklens,indices,old_types,&mys生成新®的/i/pi数据类型MPI_Type_commit(&mystruct);/输出表头，初始化，初步测评，初步寻优if(myid==0){starttime=MPI_Wtime();if((galog=fopen(〃galog.txt〃，〃w〃))==NULL)exit(1);fprintf(galog,"generation\tbest\t\taverage\tstandard、/);fprintf(galog,"number\tvalue\t\tfitness\tdeviation'/);generation=0;initialize编;g/evaluate。适应度评价函数keep_the_best(寻找到最优的染色体，并将之放置在群体的最后一个空位上}/开始进化while(generation<MAXGENS)generation++;if(myid==0)//master{select();〃选择适应度高的个体crossover();//交叉，交叉率为80%//分配数据，处理后回收数据for(i=1;i<=numprocs-1;i++)〃发送{for(j=0;j<mysize;j++)〃复制，其中mysize表示每一个处理区分配到的个体数subpopulation。]=population[mysize*(i-1)+j];/*for(j=0;j<mysize;j++)printf("\n发％£%f%f%f",subpopulation[j].fitness,subpopulation[j].gene[0],subpopulation[j].gene[1],subpopulation[j].gene[2]);*/MPI_Ssend(subpopulation,mysize,mystruct,i,1,MPI_COMM_WORLD);/分配}for(i=1;i<=numprocs-1;i++)//接收{MPI_Recv(subpopulation,mysize,mystruc