一個簡單實用的遺傳算法c程序

一個簡單實用的遺傳算法c程序(轉(zhuǎn)載)C++2009-07-2823:09:03閱讀418評論0字號：大中小這是一個非常簡單的遺傳算法源代碼，是由 DenisCormier(NorthCarolinaStateUniversity)開發(fā)的，SitaS.Raghavan(UniversityofNorthCarolinaatCharlotte)修正。代碼保證盡可能少，實際上也不必查錯。 對一特定的應用修正此代碼， 用戶只需改變常數(shù)的定義并且定義評價函數(shù)”即可。注意代碼的設計是求最大值， 其中的目標函數(shù)只能取正值； 且函數(shù)值和個體的適應值之間沒有區(qū)別。 該系統(tǒng)使用比率選擇、精華模型、單點雜交和均勻變異。如果用Gaussian變異替換均勻變異，可能得到更好的效果。代碼沒有任何圖形，甚至也沒有屏幕輸出，主要是保證在平臺之間的高可移植性。 讀者可以從,目錄coe/evol中的文件prog.c中獲得。要求輸入的文件應該命名為 ，gadata.txt?;系統(tǒng)產(chǎn)生的輸出文件為,galog.txt?。輸入的文件由幾行組成：數(shù)目對應于變量數(shù)。且每一行提供次序 對應于變量的上下界。如第一行為第一個變量提供上下界，第二行為第二個變量提供上下界，等等。/**************************************************************************//*Thisisasimplegeneticalgorithmimplementationwherethe*/TOC\o"1-5"\h\z/*evaluationfunctiontakespositivevaluesonlyandthe *//*fitnessofanindividualisthesameasthevalueofthe *//*objectivefunction *//**************************************************************************/#include<stdio.h>#include<stdlib.h>#include<math.h>/*Changeanyoftheseparameterstomatchyourneeds*/#definePOPSIZE50 /*populationsize*/#definePOPSIZE50 /*populationsize*//*max.numberofgenerations*//*max.numberofgenerations*//*no.ofproblemvariables*//*probabilityofcrossover*//*probabilityofmutation*/#defineMAXGENS1000#defineNVARS3#definePXOVER0.8#definePMUTATION0.15#defineTRUE1#defineFALSE0intgeneration;intcur_best;FILE*galog;/*currentgenerationno.*//*bestindividual*//*anoutputfile*/structgenotype/*genotype(GT),amemberofthepopulation*/{doublegene[NVARS];/*astringofvariables 一個變量字符串 */doublefitness;/*GT'sfitness適應度*/doubleupper[NVARS];/*GT'svariablesupperbound 變量的上限*/doublelower[NVARS];/*GT'svariableslowerbound 變量的下限*/doublerfitness;/*relativefitness 相對適應度*/doublecfitness;/*cumulativefitness 累計適應度*/structgenotypepopulation[POPSIZE+1]; /*population*/structgenotypenewpopulation[POPSIZE+1];/*newpopulation;*//*replacesthe*//*oldgeneration*//*Declarationofproceduresusedbythisgeneticalgorithm*/voidinitialize(void);doublerandval(double,double);voidevaluate(void);voidkeep_the_best(void);voidelitist(void);voidselect(void);voidcrossover(void);voidXover(int,int);voidswap(double*,double*);voidmutate(void);voidreport(void);/***************************************************************/TOC\o"1-5"\h\z/*Initializationfunction:Initializesthevaluesofgenes *//*withinthevariablesbounds.Italsoinitializes(tozero) *//*allfitnessvaluesforeachmemberofthepopulation.It *//*readsupperandlowerboundsofeachvariablefromthe *//*inputfile'gadata.txt'.Itrandomlygeneratesvalues *//*betweentheseboundsforeachgeneofeachgenotypeinthe */*//*population.Theformatoftheinputfile'gadata.txt'is*//*var1_lower_boundvar1_upperbound *//*var2_lower_boundvar2_upperbound... *//***************************************************************/voidinitialize(void){FILE*infile;inti,j;doublelbound,ubound;if((infile=fopen("gadata.txt","r"))==NULL){fprintf(galog,"\nCannotopeninputfile!'n");exit(1);}/*initializevariableswithinthebounds*/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]=Ibound;population[j].upper[i]=ubound;population[j].gene[i]=randval(population[j].lower[i],population[j].upper[i]);}}fclose(infile);}/***********************************************************//*Randomvaluegenerator:Generatesavaluewithinbounds*//***********************************************************/doublerandval(doublelow,doublehigh){doubleval;val=((double)(rand()%1000)/1000.0)*(high-low)+low;return(val);}/*************************************************************/*//*Evaluationfunction:Thistakesauserdefinedfunction.*//*Eachtimethisischanged,thecodehastoberecompiled.*//*Thecurrentfunctionis: x[1F2-x[1]*x[2]+x[3] *//*************************************************************/voidevaluate(void){intmem;inti;doublex[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_bestfunction:Thisfunctionkeepstrackofthe *//*bestmemberofthepopulation.Notethatthelastentryin */*//*thearrayPopulationholdsacopyofthebestindividual

*/**********************************************************************************************************************voidkeep_the_best(){intmem;inti;cur_best=0;/*storestheindexofthebestindividual*/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:Thebestmemberofthepreviousgeneration*/*//*isstoredasthelastinthearray.Ifthebestmemberof*/*//*thecurrentgenerationisworsethenthebestmemberofthe*//*previousgeneration,thelatteronewouldreplacetheworst *//*memberofthecurrentpopulation *//****************************************************************/voidelitist(){inti;doublebest,worst; /*bestandworstfitnessvalues*/intbest_mem,worst_mem;/*indexesofthebestandworstmember*/best=population[O].fitness;worst=population[O].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;}}}/*ifbestindividualfromthenewpopulationisbetterthan*/*//*thebestindividualfromthepreviouspopulation,then

*/*//*copythebestfromthenewpopulation;elsereplacethe*//*worstindividualfromthecurrentpopulationwiththe *//*bestonefromthepreviousgeneration */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;}else{for(i=0;i<NVARS;i++)population[worst_mem].gene[i]=population[POPSIZE].gene[i];population[worst_mem].fitness=population[POPSIZE].fitness;}}********************************************************************************************************************/*Selectionfunction:Standardproportionalselectionfor *//*maximizationproblemsincorporatingelitistmodel-makes */*//*surethatthebestmembersurvives*/**********************************************************voidselect(void){intmem,i,j,k;doublesum=0;doublep;/*findtotalfitnessofthepopulation*/for(mem=0;mem<POPSIZE;mem++){sum+=population[mem].fitness;}/*calculaterelativefitness*/for(mem=0;mem<POPSIZE;mem++){population[mem].rfitness= population[mem].fitness/sum;}population[O].cfitness=population[O].rfitness;/*calculatecumulativefitness*/for(mem=1;mem<POPSIZE;mem++){population[mem].cfitness= population[mem-1].cfitness+population[mem].rfitness;/*finallyselectsurvivorsusingcumulativefitness.*/for(i=0;i<POPSIZE;i++){p=rand()%1000/1000.0;if(p<population[O].cfitness)newpopulation[i]=population[0];else{for(j=0;j<POPSIZE;j++)if(p>=population[j].cfitness&&

pvpopulation[j+1].cfitness)

newpopulation[i]=population[j+1];}}/*onceanewpopulationiscreated,copyitback*/for(i=0;i<POPSIZE;i++)population[i]=newpopulation[i];}/***************************************************************/*//*Crossoverselection:selectstwoparentsthattakepartin*/*//*thecrossover.Implementsasinglepointcrossover*//***************************************************************/voidcrossover(void)inti,mem,one;intfirst0;/*countofthenumberofmemberschosen*/intfirstdoublex;for(mem=0;mem<POPSIZE;++mem)x=rand()%1000/1000.0;if(x<PXOVER)++first;if(first%2==0)Xover(one,mem);elseone=mem;**********************************************************

/*Crossover:performscrossoverofthetwoselectedparents.*//************************************************************voidXover(intone,inttwo){inti;intpoint;/*crossoverpoint*//*selectcrossoverpoint*/if(NVARS>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]);}}/*************************************************************//*Swap:Aswapprocedurethathelpsinswapping2variables*/******************************************************************************************************************voidswap(double*x,double*y)doubletemp;temp=*x;*x=*y;*y=temp;/**************************************************************//*Mutation:Randomuniformmutation.Avariableselectedfor*/*/*//*mutationisreplacedbyarandomvaluebetweenlowerand/*upperboundsofthisvariable*/*//**************************************************************/voidmutate(void){inti,j;doublelbound,hbound;doublex;for(i=0;i<POPSIZE;i++)for(j=0;j<NVARS;j++){x=rand()%1000/1000.0;if(x<PMUTATION)doublesum; /*totalpopulationfitness*/doublesum; /*totalpopulationfitness*//*findtheboundsonthevariabletobemutated*/Ibound=population[i].lower[j];hbound=population[i].upper[j];population[i].gene[j]=randval(lbound,hbound);/***************************************************************//*Reportfunction:Reportsprogressofthesimulation.Data*//*dumpedintotheoutputfileareseparatedbycommas*//***************************************************************/voidreport(void)inti;doublebest_val;/*bestpopulationfitness*/doubleavg;/*avgpopulationfitness*/doublestddev;/*std.deviationofpopulationfitness*/doublesum_square;/*sumofsquareforstd.calc*/doublesquare_sum;/*squareofsumforstd.calc*/sum=0.0;sum_square=0.0;for(i=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,"\n%5d, %6.3f,%6.3f,%6.3f\n\n",generation,best_val,avg,stddev);}/**************************************************************//*Mainfunction:Eachgenerationinvolvesselectingthebest*//*members,performingcrossover&mutationandthen *//*evaluatingtheresultingpopulation,untiltheterminating*//*conditionis