遺傳算法并行源程序

//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頭中排除極少使用的資料/*群體大小，其實(shí)就是基因總數(shù)*//*進(jìn)化代數(shù)*//*問題變量數(shù)，即基因的長度*//*交叉概率*//*變異概率*/intgeneration;intcur_best;FILE*galog;/*記錄當(dāng)前已經(jīng)進(jìn)化的代數(shù)*//*最優(yōu)個(gè)體*//*日志文件*//*基因類型*/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);/*染色體字符串*//*每個(gè)基于的上界*//*每個(gè)基因的下界*//*個(gè)體適應(yīng)度*//*相對(duì)適應(yīng)度*//*累積適應(yīng)度*//*種群初始化函數(shù)*//*隨機(jī)函數(shù)*//*尋找最優(yōu)個(gè)體*//*保持最優(yōu)*//*選擇算子*//*交叉算子*/voidXover(int,int);/*交叉操作*/voidswap(double*,double*);/*交換*/voidevaluate(void);/*個(gè)體適應(yīng)度評(píng)價(jià)*/voidworker(genotype*,int)/*從處理器操作，突變和適應(yīng)度評(píng)價(jià)*/voidreport(void);/*記錄*//**************************************************************初始化基因值，適應(yīng)值。從gadata.txt中讀入每個(gè)變量的上下限，然后隨機(jī)產(chǎn)生。**************************************************************/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,問題變量數(shù){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);}/***********************************************************/*//*在上下界間產(chǎn)生一個(gè)數(shù)/***********************************************************/doublerandval(doublelow,doublehigh){doubleval;val=((double)(rand()%1000)/1000.0)*(high-low)+low;return(val);}/***************************************************************//*Keep_the_bestfunction:保持對(duì)最優(yōu)個(gè)體的追蹤*//***************************************************************/voidkeep_the_best()//將最優(yōu)的值放在最后一個(gè)空位上{intmem;inti;cur_best=0;/*最優(yōu)個(gè)體索引*/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)//找出最好和最壞的適應(yīng)度{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;}}}/*如果新一代種群中的最優(yōu)個(gè)體比前一代的最優(yōu)個(gè)體好，*//*best取此值，反之用上一代最優(yōu)個(gè)體取代當(dāng)前代的最差個(gè)體。*/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:適者生存通過適應(yīng)度大小篩選，適*//*應(yīng)度越大，出現(xiàn)的次數(shù)越多(會(huì)有重復(fù))*//*************************************************************************/voidselect(void)//{intmem,i,j,k=0;doublesum=0;doublep;/*計(jì)算適應(yīng)度總和*/for(mem=0;mem<POPSIZE;mem++){sum+=population[mem].fitness;}/*計(jì)算相對(duì)適應(yīng)度，有點(diǎn)像概率密度*/for(mem=0;mem<POPSIZE;mem++){population[mem].rfitness=population[mem].fitness/sum;}/*計(jì)算累計(jì)適應(yīng)度，有點(diǎn)像分布函數(shù)*/population[0].cfitness=population[0].rfitness;for(mem=1;mem<POPSIZE;mem++){population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;}/*使用累計(jì)適應(yīng)度確定幸存者，落在哪個(gè)概率區(qū)域就選擇相應(yīng)的概率區(qū)域上的染色體*/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:單隨機(jī)點(diǎn)交叉，前后兩個(gè)*//*個(gè)體交叉，得到兩個(gè)新的個(gè)體，原來的個(gè)體消失*/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〃按交叉概率進(jìn)行交叉〃相鄰的兩個(gè)交叉one=mem;}}}/**************************************************************//*Crossover:交叉操作*//**************************************************************/voidXover(intone,inttwo){inti;intpoint;/*crossoverpoint*//*selectcrossoverpoint*/if(NVARS>1){〃等于1時(shí)就沒有交叉的必要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;種群中最高適應(yīng)度值*//*種群中最高適應(yīng)度值*//*平均適應(yīng)度值*//*標(biāo)準(zhǔn)方差*//*平方的總數(shù)*//*總數(shù)的平方*/標(biāo)準(zhǔn)方差*/平方的總數(shù)*/總數(shù)的平方*//*適應(yīng)度值總和doublebest_val;doubleavg;doublestddev;doublesum_square;doublesquare_sum;doublesum;種群中最高適應(yīng)度值*//*種群中最高適應(yīng)度值*//*平均適應(yīng)度值*//*標(biāo)準(zhǔn)方差*//*平方的總數(shù)*//*總數(shù)的平方*/標(biāo)準(zhǔn)方差*/平方的總數(shù)*/總數(shù)的平方*//*適應(yīng)度值總和*/適應(yīng)度值總和*/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];//計(jì)算得到適應(yīng)度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)/*突變和適應(yīng)度評(píng)價(jià)操作*/{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變異〃適應(yīng)度評(píng)價(jià)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];//計(jì)算得到適應(yīng)度F1}//end適應(yīng)度評(píng)價(jià)}/****************************************************************//*主函數(shù)*//****************************************************************/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);//每個(gè)從處理器上應(yīng)該分配的個(gè)體數(shù)elseif(numprocs==1)mysize=POPSIZE;genotype*subpopulation=(genotype*)malloc(mysize*sizeof(genotype));if(!subpopulation){printf("不能獲得%d個(gè)大小的空間\n",mysize);MPI_Abort(MPI_COMM_WORLD,1);}//自定義數(shù)據(jù)類型MPI_Datatypemystruct;intblocklens[6];MPI_Aintindices[6];MPI_Datatypeold_types[6];/各塊中數(shù)據(jù)個(gè)數(shù)blocklens[0]=ARS;blocklens[1]=ARS;blocklens[2]=ARS;blocklens[3]=1;blocklens[4]=1;blocklens[5]=1;/數(shù)據(jù)類型for(i=0;i<6;i++)old_types[i]=MPI_DOUBLE;/求地址和相對(duì)偏移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數(shù)據(jù)類型MPI_Type_commit(&mystruct);/輸出表頭，初始化，初步測評(píng)，初步尋優(yōu)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。適應(yīng)度評(píng)價(jià)函數(shù)keep_the_best(尋找到最優(yōu)的染色體，并將之放置在群體的最后一個(gè)空位上}/開始進(jìn)化while(generation<MAXGENS)generation++;if(myid==0)//master{select();〃選擇適應(yīng)度高的個(gè)體crossover();//交叉，交叉率為80%//分配數(shù)據(jù)，處理后回收數(shù)據(jù)for(i=1;i<=numprocs-1;i++)〃發(fā)送{for(j=0;j<mysize;j++)〃復(fù)制，其中mysize表示每一個(gè)處理區(qū)分配到的個(gè)體數(shù)subpopulation。]=population[mysize*(i-1)+j];/*for(j=0;j<mysize;j++)printf("\n發(fā)％￡%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++)//接收{(diào)MPI_Recv(subpopulation,mysize,mystruc