/**********************************************************************//*基于基本遗传算法的自适应遗传优化算法函数最优化SGA_AUTO.C*//*AFunctionOptimizerusingSimpleGeneticAlgorithm*//*developedfromthePascalSGAcodepresentedbyDavidE.Goldberg*/
/*华南理工大学电子与信息学院苏勇2004年4月*//**********************************************************************/#include
#include
/*全局变量*/
structindividual
{
unsigned*chrom;
doublefitness;
doublevarible;
intxsite;
intparent[2];
int*utility;
};
structbestever
{
unsigned*chrom;
doublefitness;
doublevarible;
intgeneration;
};
structindividual*oldpop;
structindividual*newpop;
structbesteverbestfit;
doublesumfitness;
doublemax;
doubleavg;
doublemin;
floatpcross;
floatpmutation;
intpopsize;
intlchrom;
intchromsize;
intgen;
intmaxgen;
intrun;
intmaxruns;
intprintstrings;
*/
intnmutation;/*个体*//*染色体*//*个体适应度*//*个体对应的变量值*//*交叉位置*//*父个体*//*特定数据指针变量*//*最佳个体*//*最佳个体染色体*//*最佳个体适应度*//*最佳个体对应的变量值*//*最佳个体生成代*//*当前代种群*//*新一代种群*//*最佳个体*//*种群中个体适应度累计*//*种群中个体最大适应度*//*种群中个体平均适应度*//*种群中个体最小适应度*//*交叉概率*//*变异概率*//*种群大小*//*染色体长度*//*存储一染色体所需字节数*//*当前世代数*//*最大世代数*//*当前运行次数*//*总运行次数*//*输出染色体编码的判断，0--不输出,1--输出/*当前代变异发生次数*/
intncross;/*当前代交叉发生次数*/
floatpc1;
floatpc2;
floatpm1;
floatpm2;
inttemp_mate1;
inttemp_mate2;
/*随机数发生器使用的静态变量*/
staticdoubleoldrand[55];
staticintjrand;
staticdoublerndx2;
staticintrndcalcflag;
/*输出文件指针*/
FILE*outfp;
/*函数定义*/
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()/*遗传算法初始化*/
{
/*键盘输入遗传算法参数*/
initdata();
/*确定染色体的字节长度*/
chromsize=(lchrom/(8*sizeof(unsigned)));
if(lchrom%(8*sizeof(unsigned)))chromsize++;
/*分配给全局数据结构空间*/
initmalloc();
/*初始化随机数发生器*/
randomize();
/*初始化全局计数变量和一些数值*/
nmutation=0;
ncross=0;
bestfit.fitness=0.0;
bestfit.generation=0;
/*初始化种群，并统计计算结果*/
initpop();
statistics(oldpop);
initreport();
}
voidinitdata()/*遗传算法参数输入*/
{
charanswer[2];
popsize=30;
if((popsize%2)!=0)
{
fprintf(outfp,"种群大小已设置为偶数\n");
popsize++;
};
lchrom=22;
printstrings=1;
maxgen=150;
pcross=0.8;
pc1=0.8;
pc2=0.6;
pmutation=0.05;
pm1=0.05;
pm2=0.005;
}
voidinitpop()/*随机初始化种群*/
{
intj,j1,k,stop;
unsignedmask=1;
for(j=0;j
{
for(k=0;k
{
oldpop[j].chrom[k]=0;
if(k==(chromsize-1))
stop=lchrom-(k*(8*sizeof(unsigned)));
else
stop=8*sizeof(unsigned);
for(j1=1;j1
{
oldpop[j].chrom[k]=oldpop[j].chrom[k]
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].xsite=0;
objfunc(&(oldpop[j]));
}
}
voidinitreport()/*初始参数输出*/
{
voidskip();
skip(outfp,1);
fprintf(outfp,"基本遗传算法参数\n");
fprintf(outfp,"-------------------------------------------------\n");
fprintf(outfp,"种群大小(popsize)=%d\n",popsize);
fprintf(outfp,"染色体长度(lchrom)=%d\n",lchrom);
fprintf(outfp,"最大进化代数(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;
/*每代运算前进行预选*/
preselect();
/*选择,交叉,变异*/
do
{
/*挑选交叉配对*/
mate1=select();
temp_mate1=mate1;
mate2=select();/*初始父个体信息*//*计算初始适应度*/
temp_mate2=mate2;
/*交叉和变异*/
jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
/*自适应变异概率*/
if(gen!=0)
{
if(newpop[j].fitness>=avg)
pmutation=pm1-(pm1-pm2)*(max-newpop[j].fitness)/(max-avg);
else
pmutation=pm1;
}
mutation(newpop[j].chrom);
if(gen!=0)
{
if(newpop[j+1].fitness>=avg)
pmutation=pm1-(pm1-pm2)*(max-newpop[j+1].fitness)/(max-avg);
else
pmutation=pm1;
}
mutation(newpop[j+1].chrom);
/*解码,计算适应度*/
objfunc(&(newpop[j]));
/*记录亲子关系和交叉位置*/
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
}
voidinitmalloc()/*为全局数据变量分配空间*/
{
unsignednbytes;
char*malloc();
intj;
/*分配给当前代和新一代种群内存空间*/
nbytes=popsize*sizeof(structindividual);
if((oldpop=(structindividual*)malloc(nbytes))==NULL)
nomemory("oldpop");
if((newpop=(structindividual*)malloc(nbytes))==NULL)
nomemory("newpop");
/*分配给染色体内存空间*/
nbytes=chromsize*sizeof(unsigned);
for(j=0;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()/*释放内存空间*/
{
inti;
for(i=0;i
{
free(oldpop[i].chrom);
free(newpop[i].chrom);
}
free(oldpop);
free(newpop);
free(bestfit.chrom);
}
voidnomemory(string)/*内存不足，退出*/
char*string;
{
fprintf(outfp,"malloc:outofmemorymaking%s!!\n",string);
exit(-1);
}
voidreport()/*输出种群统计结果*/
{
voidrepchar(),skip();
voidwritepop(),writestats();
repchar(outfp,"-",80);
skip(outfp,1);
if(printstrings==1)
{
repchar(outfp,"",((80-17)/2));
fprintf(outfp,"模拟计算统计报告\n");
fprintf(outfp,"世代数%3d",gen);
repchar(outfp,"",(80-28));
fprintf(outfp,"世代数%3d\n",(gen+1));
fprintf(outfp,"个体染色体编码");
repchar(outfp,"",lchrom-5);
fprintf(outfp,"适应度父个体交叉位置");
fprintf(outfp,"染色体编码");
repchar(outfp,"",lchrom-5);
fprintf(outfp,"适应度\n");
repchar(outfp,"-",80);
skip(outfp,1);
writepop(outfp);
repchar(outfp,"-",80);
skip(outfp,1);
}
fprintf(outfp,"第%d代统计:\n",gen);
fprintf(outfp,"总交叉操作次数=%d,总变异操作数=%d\n",ncross,nmutation);
fprintf(outfp,"最小适应度：%f最大适应度：%f平均适应度%f\n",min,max,avg);fprintf(outfp,"迄今发现最佳个体=>所在代数：%d",bestfit.generation);fprintf(outfp,"适应度：%f染色体：",bestfit.fitness);
writechrom((&bestfit)->chrom);
fprintf(outfp,"对应的变量值:%f",bestfit.varible);
skip(outfp,1);
repchar(outfp,"-",80);
skip(outfp,1);
}
voidwritepop()
{
structindividual*pind;
intj;
for(j=0;j
{
fprintf(outfp,"%3d)",j+1);
/*当前代个体*/
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
{
tmp=chrom[k];
if(k==(chromsize-1))
stop=lchrom-(k*(8*sizeof(unsigned)));
else
stop=8*sizeof(unsigned);
for(j=0;j
{
if(tmp&mask)
fprintf(outfp,"1");
else
fprintf(outfp,"0");
tmp=tmp>>1;
}
}
}
voidpreselect()
{
intj;
sumfitness=0;
for(j=0;j
intselect()
{
externfloatrandomperc();
floatsum,pick;
inti;
pick=randomperc();
sum=0;/*轮盘赌选择*/
if(sumfitness!=0)
{
for(i=0;(sum
sum+=oldpop[i].fitness/sumfitness;
}
else
i=rnd(1,popsize);
return(i-1);
}
voidstatistics(pop)/*计算种群统计数据*/
structindividual*pop;
{
inti,j;
sumfitness=0.0;
min=pop[0].fitness;
max=pop[0].fitness;
/*计算最大、最小和累计适应度*/
for(j=0;j
{
sumfitness=sumfitness+pop[j].fitness;
if(pop[j].fitness>max)max=pop[j].fitness;
if(pop[j].fitness
/*newglobalbest-fitindividual*/
if(pop[j].fitness>bestfit.fitness)
{
for(i=0;i
bestfit.chrom[i]=pop[j].chrom[i];
bestfit.fitness=pop[j].fitness;
bestfit.varible=pop[j].varible;
bestfit.generation=gen;
}
}
/*计算平均适应度*/
avg=sumfitness/popsize;
}
voidtitle()
{
printf("SGAOptimizerJean.Timex\n");
}
voidrepchar(outfp,ch,repcount)
FILE*outfp;
char*ch;
intrepcount;
{
intj;
for(j=1;j
}
voidskip(outfp,skipcount)
FILE*outfp;
intskipcount;
{
intj;
for(j=1;j
}
voidobjfunc(critter)/*计算适应度函数值*/structindividual*critter;
{
unsignedmask=1;
unsignedbitpos;
unsignedtp;
doublepow(),bitpow;
intj,k,stop;
critter->varible=0.0;
for(k=0;k
{
if(k==(chromsize-1))
stop=lchrom-(k*(8*sizeof(unsigned)));
else
stop=8*sizeof(unsigned);
tp=critter->chrom[k];
for(j=0;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;
}
void
{mutation(unsigned*child)/*变异操作*/
intj,k,stop;
unsignedmask,temp=1;
for(k=0;k
{
mask=0;
if(k==(chromsize-1))
stop=lchrom-(k*(8*sizeof(unsigned)));
else
stop=8*sizeof(unsigned);
for(j=0;j
{
if(flip(pmutation))
{
mask=mask|(temp
nmutation++;
}
}
child[k]=child[k]^mask;
}
}
intcrossover(unsigned*parent1,unsigned*parent2,unsigned*child1,unsigned*child2)/*由两个父个体交叉产生两个子个体*/
{
intj,jcross,k;
unsignedmask,temp;
/*//////////////////////自适应交叉概率*/
doublefp_fitness=0;
if(gen!=0)
{
if(oldpop[temp_mate1].fitness>=oldpop[temp_mate2].fitness)
fp_fitness=oldpop[temp_mate1].fitness;
else
fp_fitness=oldpop[temp_mate2].fitness;
if(fp_fitness>=avg)
pcross=pc1-(pc1-pc2)*(fp_fitness-avg)/(max-avg);
else
pcross=pc2;
}
/*///////////////////////////////////*/
if(flip(pcross))
{
jcross=rnd(1,(lchrom-1));/*Crossbetween1andl-1*/
ncross++;
for(k=1;k
{
if(jcross>=(k*(8*sizeof(unsigned))))
{
child1[k-1]=parent1[k-1];
child2[k-1]=parent2[k-1];
}
elseif((jcross
((k-1)*(8*sizeof(unsigned)))))
{
mask=1;
for(j=1;j
{
temp=1;
mask=mask
mask=mask|temp;
}
child1[k-1]=(parent1[k-1]&mask)|(parent2[k-1]&(~mask));
child2[k-1]=(parent1[k-1]&(~mask))|(parent2[k-1]&mask);
}
else
{
child1[k-1]=parent2[k-1];
child2[k-1]=parent1[k-1];
}
}
}
else
{
for(k=0;k
{
child1[k]=parent1[k];
child2[k]=parent2[k];
}
jcross=0;
}
return(jcross);
}
voidadvance_random()/*产生55个随机数*/(jcross>
{
intj1;
doublenew_random;
for(j1=0;j1
{
new_random=oldrand[j1]-oldrand[j1+31];
if(new_random
oldrand[j1]=new_random;
}
for(j1=24;j1
{
new_random=oldrand[j1]-oldrand[j1-24];
if(new_random
oldrand[j1]=new_random;
}
}
intflip(floatprob)/*以一定概率产生0或1*/
{
floatrandomperc();
if(randomperc()
return(1);
else
return(0);
}
voidrandomize()/*设定随机数种子并初始化随机数发生器*/
{
floatrandomseed;
intj1;
for(j1=0;j1
oldrand[j1]=0.0;
jrand=0;
randomseed=0.5;
warmup_random(randomseed);
}
doublerandomnormaldeviate()/*产生随机标准差*/
{
doublesqrt(),log(),sin(),cos();
floatrandomperc();
doublet,rndx1;
if(rndcalcflag)
{rndx1=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()/*与库函数random()作用相同,产生[0,1]之间一个随机数*/{
jrand++;
if(jrand>=55)
{
jrand=1;
advance_random();
}
return((float)oldrand[jrand]);
}
intrnd(low,high)/*在整数low和high之间产生一个随机整数*/
intlow,high;
{
inti;
floatrandomperc();
if(low>=high)
i=low;
else
{
i=(randomperc()*(high-low+1))+low;
if(i>high)i=high;
}
return(i);
}
voidwarmup_random(floatrandom_seed)
{
intj1,ii;
doublenew_random,prev_random;/*初始化随机数发生器*/
oldrand[54]=random_seed;
new_random=0.000000001;
prev_random=random_seed;
for(j1=1;j1
{
ii=(21*j1)%54;
oldrand[ii]=new_random;
new_random=prev_random-new_random;
if(new_random
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()
argv[1]="output.txt";
if((outfp=fopen(argv[1],"w"))==NULL)
{
fprintf(stderr,"Cannotopenoutputfile%s\n",argv[1]);
exit(-1);
}
title();
maxruns=10;
for(run=1;run
{
initialize();
for(gen=0;gen
{
fprintf(outfp,"\n第%d/%d次运行:当前代为
run,maxruns,gen,maxgen);
/*产生新一代*/
generation();%d,共%d代\n",
/*计算新一代种群的适应度统计数据*/
statistics(newpop);
/*输出新一代统计数据*/
report();
temp=oldpop;
oldpop=newpop;
newpop=temp;
}
freeall();
}
}
/*****************************************************************本程序是实现了模拟退火算法**********利用模拟退火算法,求出某函数的最小小值**********编写者:张庆贤******
***************************************************************/#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#include"math.h"
/********************************
定义常量
********************************/
#defineMAX_TP20000000//最高温度
#defineMIN_TP1//控制的最低温度
#defineLENGTH0.01//步长,各个函数不一样,
#defineBK0.1//B常数
#defineAF0.95//温度变化速率
#definedebuge1//调试信息的控制
/***********************************
目标函数
************************************/
doublefun(doublex)
{
inta,b,c;
a=-4;
b=-8;
c=-12;
return(a*x*x+b*x+c);
}
/***********************************************
模拟退火算法
************************************************/doublesa()
{
doubleold_x,new_x;//变量
doubletempt=MAX_TP;
doubleold_eg,new_eg;//能量函数
doubledx;//符号
//随机的产生一个初试值
old_x=(double)(rand()%2);
old_eg=fun(old_x);
/*************************
逐渐降温的过程
**************************/
while(tempt>MIN_TP)
{
dx=(double)(rand()%3);
if(dx>1.5)
dx=1;
else
dx=-1;
//length=(float(rand()%30))/60;
//做调试的时候用的输出
//cout
//***************************
new_x=(double)(old_x+dx*LENGTH);
new_eg=fun(new_x);
if((old_eg-new_eg)
{
old_x=new_x;
old_eg=new_eg;
}
else
{
doublerd=(double)(rand()%100);
doublep;
/**************************************
在本程序中有加0.8有一定的理论依据
**************************************/
rd=rd/100+0.8;
p=exp(-(old_eg-new_eg)/(BK*tempt));
//**************************************
#ifdebuge
cout
#endifrd="
//*****************************************if(p>rd)
{
//接受不正常情况下的扰动
old_x=new_x;
old_eg=new_eg;
}
else
{
}
}
/************************************
降温
************************************/if(old_x!=new_x)
{
tempt=tempt*AF;
}
//**************************************#ifdebuge
cout
cout
#endif
//***************************************
}
return(old_x);
}
voidmain()
{
doublea;
a=sa();
cout
cout}