基本遺傳算法的C++語言實(shí)現(xiàn)

3/********************************************************************//*基于基本遺傳算法的函數(shù)最優(yōu)化SGA.C*//*AFunctionOptimizerusingSimpleGeneticAlgorithm*//*developedfromthePascalSGAcodepresentedbyDavidE.Goldberg*//********************************************************************/#include<stdio.h>#include<math.h>/*全局變量*/structindividual{unsigned*chrom;doublefitness;doublevarible;intxsite;intparent[2];/*個體*//*染色體*//*個體適應(yīng)度*//*個體對應(yīng)的變量值*//*交叉位置*//*父個體*/int*utility;i?/*特定數(shù)據(jù)指針變量*/},structbestever{unsigned*chrom;doublefitness;doublevarible;intgeneration;i./*最佳個體*//*最佳個體染色體*//*最佳個體適應(yīng)度*//*最佳個體對應(yīng)的變量值*//*最佳個體生成代*/},structindividual*oldpop;structindividual*newpop;structbesteverbestfit;doublesumfitness;doublemax;doubleavg;doublemin;floatpcross;floatpmutation;intpopsize;intlchrom;intchromsize;intgen;/*當(dāng)前代種群*//*新一代種群*//*最佳個體*//*種群中個體適應(yīng)度累計*//*種群中個體最大適應(yīng)度*//*種群中個體平均適應(yīng)度*//*種群中個體最小適應(yīng)度*//*交叉概率*//*變異概率*//*種群大小*//*染色體長度*//*存儲一染色體所需字節(jié)數(shù)*//*當(dāng)前世代數(shù)*/intmaxgen;intrun;intmaxruns;intprintstrings;*/intnmutation;intncross;/*最大世代數(shù)*//*當(dāng)前運(yùn)行次數(shù)*//*總運(yùn)行次數(shù)*//*輸出染色體編碼的判斷，0--不輸出，1-/*當(dāng)前代變異發(fā)生次數(shù)*//*當(dāng)前代交叉發(fā)生次數(shù)*/輸出/*隨機(jī)數(shù)發(fā)生器使用的靜態(tài)變量*/staticdoubleoldrand[55];staticintjrand;staticdoublerndx2;staticintrndcalcflag;/*輸出文件指針*/FILE*outfp;/*函數(shù)定義*/voidadvance_random();intflip(float);rnd(int,int);voidrandomize();doublerandomnormaldeviate();floatrandomperc(),rndreal(float,float);voidwarmup_random(float);voidinitialize(),initdata(),initpop();voidinitreport(),generation(),initmalloc();voidfreeall(),nomemory(char*),report();voidwritepop(),writechrom(unsigned*);voidpreselect();voidstatistics(structindividual*);voidtitle(),repchar(FILE*,char*,int);voidskip(FILE*,int);intselect();voidobjfunc(structindividual*);intcrossover(unsigned*,unsigned*,unsigned*,unsigned*);voidmutation(unsigned*);voidinitialize()/*遺傳算法初始化*/{/*鍵盤輸入遺傳算法參數(shù)*/initdata();/*確定染色體的字節(jié)長度*/chromsize=(lchrom/(8*sizeof(unsigned)));if(lchrom%(8*sizeof(unsigned)))chromsize++;/*分配給全局?jǐn)?shù)據(jù)結(jié)構(gòu)空間*/initmalloc();/*初始化隨機(jī)數(shù)發(fā)生器*/randomize();/*初始化全局計數(shù)變量和一些數(shù)值*/nmutation=0;ncross=0;bestfit.fitness=0.0;bestfit.generation=0;/*初始化種群，并統(tǒng)計計算結(jié)果*/initpop();statistics(oldpop);initreport();}voidinitdata()/*遺傳算法參數(shù)輸入*/{charanswer[2];popsize=30;if((popsize%2)!=0){fprintf(outfW^^大小已設(shè)置為偶數(shù)\n");popsize++;};lchrom=22;printstrings=1;maxgen=150;pcross=0.8;pmutation=0.005;}voidinitpop()/*隨機(jī)初始化種群*/{intj,j1,k,stop;unsignedmask=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].xsiteoldpop[j].parent[1]=0;oldpop[j].xsite=0;objfunc(&(oldpop[j]));}}voidinitreport()/*初始參數(shù)輸出*/{voidskip();skip(outfp,1);fprintf(outfp,"基本遺傳算法參數(shù)\n");fprintf(outfp,"\n");fprintf(outfp,"種群大小(popsize)=%d\n",popsize);fprintf(outfp,"染色體長度(lchrom)=%d\n",lchrom);fprintf(outfp,"最大進(jìn)化代數(shù)(maxgen)=%d\n",maxgen);fprintf(outfp,"交叉概率(pcross)=%f\n",pcross);fprintf(outfp,"變異概率(pmutation)=%f\n",pmutation);fprintf(outfp,"\n");skip(outfp,1);fflush(outfp);}voidgeneration(){intmate1,mate2,jcross,j=0;/*每代運(yùn)算前進(jìn)行預(yù)選*/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);/*解碼，計算適應(yīng)度*/objfunc(&(newpop[j]));/*記錄親子關(guān)系和交叉位置*/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));}voidinitmalloc()/*為全局?jǐn)?shù)據(jù)變量分配空間*/{unsignednbytes;char*malloc();intj;/*分配給當(dāng)前代和新一代種群內(nèi)存空間*/nbytes=popsize*sizeof(structindividual);if((oldpop=(structindividual*)malloc(nbytes))==NULL)nomemory("oldpop");if((newpop=(structindividual*)malloc(nbytes))==NULL)nomemory("newpop");/*分配給染色體內(nèi)存空間*/nbytes=chromsize*sizeof(unsigned);for(j=0;j<popsize;j++){if((oldpop[j].chrom=(unsigned*)malloc(nbytes))==NULL)nomemory("oldpopchromosomes");if((newpop[j].chrom=(unsigned*)malloc(nbytes))==NULL)nomemory("newpopchromosomes");}if((bestfit.chrom=(unsigned*)malloc(nbytes))==NULL)nomemory("bestfitchromosome");}voidfreeall()/*釋放內(nèi)存空間*/{inti;for(i=0;i<popsize;i++){free(oldpop[i].chrom);free(newpop[i].chrom);}free(oldpop);free(newpop);free(bestfit.chrom);}voidnomemory(string)/*內(nèi)存不足，退出*/char*string;{fprintf(outfp,"malloc:outofmemorymaking%s!!\n",string);exit(-1);}voidreport()/*輸出種群統(tǒng)計結(jié)果*/{voidrepchar(),skip();voidwritepop(),writestats();repchar(outfp,"-",80);skip(outfp,1);if(printstrings==1){repchar(outfp,"",((80-17)/2));fprintf(outfp,"模擬計算統(tǒng)計報告\n");fprintf(outfp,”世代數(shù)%3d",gen);repchar(outfp,"",(80-28));fprintf(outfp,”世代數(shù)%3d\n",(gen+1));fprintf(outfp,"個體染色體編碼”)；repchar(outfp,"",lchrom-5);fprintf(outfp,"適應(yīng)度父個體交叉位置");fprintf(outfp,"染色體編碼");repchar(outfp,"",lchrom-5);fprintf(outfp,"適應(yīng)度\n");repchar(outfp,"-",80);skip(outfp,1);writepop(outfp);repchar(outfp,"-",80);skip(outfp,1);}fprintf(outfp,"第%d代統(tǒng)計:\n",gen);fprintf(outfp,"總交叉操作次數(shù)=%d,總變異操作數(shù)=%d\n",ncross,nmutation);fprintf(outfp,"最小適應(yīng)度：%f最大適應(yīng)度：%f平均適應(yīng)度%f\n",min,max,avg);fprintf(outfp,"迄今發(fā)現(xiàn)最佳個體=>所在代數(shù)：%d",bestfit.generation);fprintf(outfp,"適應(yīng)度：%f染色體：",bestfit.fitness);writechrom((&bestfit)->chrom);fprintf(outfp,"對應(yīng)的變量值:%f",bestfit.varible);skip(outfp,1);repchar(outfp,"-",80);skip(outfp,1);}voidwritepop(){structindividual*pind;intj;for(j=0;j<popsize;j++){fprintf(outfp,"%3d),j+1);/*當(dāng)前代個體*/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);}}voidwritechrom(chrom)/*輸出染色體編碼*/unsigned*chrom;{intj,k,stop;unsignedmask=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;voidpreselect(){intj；sumfitness=0;for(j=0;j<popsize;j++)sumfitness+=oldpop[j].fitness;}intselect()/*輪盤賭選擇*/{externfloatrandomperc();floatsum,pick;inti;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);}voidstatistics(p/*)計算種群統(tǒng)計數(shù)據(jù)*/structindividual*pop;{inti,j;sumfitness=0.0;min=pop[0].fitness;max=pop[0].fitness;/*計算最大、最小和累計適應(yīng)度*/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;/*newglobalbest-fitindividual*/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;}}/*計算平均適應(yīng)度*/avg=sumfitness/popsize;}voidtitle(){printf("SGAOptimizerJean.Timex\n");}voidrepchar(outfp,ch,repcount)FILE*outfp;char*ch;intrepcount;{intj;for(j=1;j<=repcount;j++)fprintf(outfp,"%s”,ch);}voidskip(outfp,skipcount)FILE*outfp;intskipcount;{intj;for(j=1;j<=skipcount;j++)fprintf(outfp,"\n");}voidobjfunc(critter)/*計算適應(yīng)度函數(shù)值*/structindividual*critter;{unsignedmask=1;unsignedbitpos;unsignedtp;doublepow(),bitpow;intj,k,stop;critter->varible=0.0;for(k=0;k<chromsize;k++){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;}voidmutation(unsigned*child)/*變異操作*/{intj,k,stop;unsignedmask,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=maskl(temp<<j);nmutation++;}}child[k]=child[k]Amask;}}intcrossover(unsigned*parent1,unsigned*parent2,unsigned*child1,unsigned*child2)/*由兩個父個體交叉產(chǎn)生兩個子個體*/intj,jcross,k;unsignedmask,temp;if(flip(pcross)){jcross=rnd(1,(lchrom-1));/*Crossbetween1andl-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];}elseif((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=maskltemp;}child1[k-1]=(parent1[k-1]&mask)l(parent2[k-1]&(?mask));child2[k-1]=(parent1[k-1]&(?mask))l(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);voidadvance_random()/*產(chǎn)生55個隨機(jī)數(shù)*/{intj1;doublenew_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;}}intflip(floatprob)/*以一定概率產(chǎn)生0或1*/{floatrandomperc();if(randomperc()<=prob)return(1);elsereturn(0);}voidrandomize()/*設(shè)定隨機(jī)數(shù)種子并初始化隨機(jī)數(shù)發(fā)生器*/{floatrandomseed;intj1;for(j1=0;j1<=54;j1++)oldrand[j1]=0.0;jrand=0;randomseed=0.5;warmup_random(randomseed);}doublerandomnormaldeviate()/*產(chǎn)生隨機(jī)標(biāo)準(zhǔn)差*/{doublesqrt(),log(),sin(),cos();floatrandomperc();

doublet,rndxl;if(rndcalcflag)(rndxl=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);}}floatrandomperc()/*與庫函數(shù)random()作用相同，產(chǎn)生[0,1]之間一個隨機(jī)數(shù)*/{jrand++;if(jrand>=55){jrand=1;advance_random();}return((float)oldrand[jrand]);}intrnd(low,high)/*在整數(shù)low和high之間產(chǎn)生一個隨機(jī)整數(shù)*/intlow,high;{inti;floatrandomperc();if(low>=high)i=low;else{i=(randomperc()*(high-low+1))+low;if(i>high)i=high;}return(i);/*初始化隨機(jī)數(shù)發(fā)生器*/}voidwarmup_random(floatrandom_seed){/*初始化隨機(jī)數(shù)發(fā)生器*/intj1,ii;doublenew_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)/*主程序*/intargc;char*argv[];{structindividual*temp;FILE*fopen();voidtitle();char*malloc();if((outfp=fopen(argv[1],"w"))==NULL){fprintf(stderr,"Cannotopenoutputfile%s\n",argv[1]);exit(-1);}title();maxruns=10;for(run=1;run<=maxruns;run++){initialize();for(gen=0;gen<maxgen;gen++){fprintf(outfp,"\n第%d/%d次運(yùn)行：當(dāng)前代為%d,共%d代\n”,run,maxruns,gen,maxgen);/*產(chǎn)生新一代*/

generation();/*計算新一代種群的適應(yīng)度統(tǒng)計數(shù)據(jù)*/statistics(newpop);/*輸出新一代統(tǒng)計數(shù)據(jù)*/report();temp=oldpop;oldpop=newpop;newpop=temp;}freeall();}}v?.A燙蕭?..…|AA./********************************************************************//*基于基本遺傳算法的函數(shù)最優(yōu)化SGA.C*//*AFunctionOptimizerusingSimpleGeneticAlgorithm*//*developedfromthePascalSGAcodepresentedbyDavidE.Goldberg*//*華南理工大學(xué)電子與信息學(xué)院劉世楷2004年5月*/3/********************************************************************/#include<stdio.h>#include<stdio.h>#include<math.h>/*全局變量*/structindividual{unsigned*chrom;doublefitness;doublevarible;intxsite;intparent[2];int*utility;}*oldpop;structbestever{unsigned*chrom;doublefitness;doublevarible;intgeneration;};/*當(dāng)前代種群*/structindividual*newpop;structbesteverbestfit;doublesumfitness;doublemax;/*個體*//*染色體*//*個體適應(yīng)度*//*個體對應(yīng)的變量值*//*交叉位置*//*父個體*//*特定數(shù)據(jù)指針變量*//*最佳個體*//*最佳個體染色體*//*最佳個體適應(yīng)度*//*最佳個體對應(yīng)的變量值*//*最佳個體生成代*//*新一代種群*//*最佳個體*//*種群中個體適應(yīng)度累計*//*種群中個體最大適應(yīng)度*/doubleavg;/*種群中個體平均適應(yīng)度*/doublemin;/*種群中個體最小適應(yīng)度*/floatpcross;/*交叉概率*/floatpmutation;/*變異概率*/intpopsize;/*種群大小*/intlchrom;/*染色體長度*/intchromsize;/*存儲一染色體所需字節(jié)數(shù)*/intgen;/*當(dāng)前世代數(shù)*/intmaxgen;/*最大世代數(shù)*/intrun;/*當(dāng)前運(yùn)彳丁次數(shù)*/intmaxruns;/*總運(yùn)行次數(shù)*/intprintstrings;/*輸出染色體編碼的判斷，0--不輸出，1--輸出*/intnmutation;/*當(dāng)前代變異發(fā)生次數(shù)*/intncross;/*當(dāng)前代交叉發(fā)生次數(shù)*//*隨機(jī)數(shù)發(fā)生器使用的靜態(tài)變量*/staticdoubleoldrand[55];staticintjrand;staticdoublerndx2;staticintrndcalcflag;/*輸出文件指針*/FILE*outfp;/*函數(shù)定義*/voidadvance_random();intflip(float);rnd(int,int);voidrandomize();doublerandomnormaldeviate();floatrandomperc(),rndreal(float,float);voidwarmup_random(float);voidinitialize(),initdata(),initpop();voidinitreport(),generation(),initmalloc();voidfreeall(),nomemory(char*),report();voidwritepop(),writechrom(unsigned*);voidpreselect();voidstatistics(structindividual*);voidtitle(),repchar(FILE*,char*,int);voidskip(FILE*,int);intselect();voidobjfunc(structindividual*);intcrossover(unsigned*,unsigned*,unsigned*,unsigned*);voidmutation(unsigned*);voidinitialize()/*遺傳算法初始化*/{/*鍵盤輸入遺傳算法參數(shù)*/initdata();/*確定染色體的字節(jié)長度*/chromsize=(lchrom/(8*sizeof(unsigned)));if(lchrom%(8*sizeof(unsigned)))chromsize++;/*分配給全局?jǐn)?shù)據(jù)結(jié)構(gòu)空間*/initmalloc();/*初始化隨機(jī)數(shù)發(fā)生器*/randomize();/*初始化全局計數(shù)變量和一些數(shù)值*/nmutation=0;ncross=0;bestfit.fitness=0.0;bestfit.generation=0;/*初始化種群，并統(tǒng)計計算結(jié)果*/initpop();statistics(oldpop);initreport();}voidinitdata()/*遺傳算法參數(shù)輸入*/{charanswer[2];popsize=30;if((popsize%2)!=0){fprintf(outfp,"種群大小已設(shè)置為偶數(shù)\n");popsize++;};lchrom=22;printstrings=1;maxgen=150;pcross=0.8;pmutation=0.005;}voidinitpop()/*隨機(jī)初始化種群*/{intj,j1,k,stop;unsignedmask=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]lmask;}}oldpop[j].parent[0]=0;/*初始父個體信息*/oldpop[j].parent[1]=0;oldpop[j].xsite=0;objfunc(&(oldpop[j]));/*計算初始適應(yīng)度*/}}voidinitreport()/*初始參數(shù)輸出*/{voidskip();skip(outfp,1);fprintf(outfp,"基本遺傳算法參數(shù)\n");fprintf(outfp,"\n");fprintf(outfp,"種群大小(popsize)=%d\n",popsize);fprintf(outfp,"染色體長度(lchrom)=%d\n",lchrom);fprintf(outfp,"最大進(jìn)化代數(shù)(maxgen)=%d\n",maxgen);fprintf(outfp,"交叉概率(pcross)=%f\n",pcross);fprintf(outfp,"變異概率(pmutation)=%f\n",pmutation);fprintf(outfp,"\n");skip(outfp,1);fflush(outfp);}voidgeneration(){intmate1,mate2,jcross,j=0;/*每代運(yùn)算前進(jìn)行預(yù)選*/preselect();/*選擇，交叉，變異*/do/*挑選交叉配對*/matel=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);/*解碼，計算適應(yīng)度*/objfunc(&(newpop[j]));/*記錄親子關(guān)系和交叉位置*/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));}voidinitmalloc()/*為全局?jǐn)?shù)據(jù)變量分配空間*/{unsignednbytes;char*malloc();intj;/*分配給當(dāng)前代和新一代種群內(nèi)存空間*/nbytes=popsize*sizeof(structindividual);if((oldpop=(structindividual*)malloc(nbytes))==NULL)nomemory("oldpop");if((newpop=(structindividual*)malloc(nbytes))==NULL)nomemory("newpop");/*分配給染色體內(nèi)存空間*/nbytes=chromsize*sizeof(unsigned);for(j=0;j<popsize;j++){if((oldpop[j].chrom=(unsigned*)malloc(nbytes))==