sga.c

基本遗传算法的c程序源代码

#include<stdio.h>
#include<malloc.h>
#include<graphics.h>
#include<math.h>

/*全局变量*/
struct individual
{
unsigned *chrom;
double fitness;
double varible;
int xsite;
int parent[2];
int *utility;
};
struct bestever
{
unsigned *chrom;
double fitness;
double varible;
int generation;
};
struct individual *oldpop;
struct individual *newpop;
struct bestever bestfit;
double sumfitness;
double max;
double avg;
double min;
float pcross;
float pmutation;
int popsize;
int lchrom;
int chromsize;
int gen;
int maxgen;
int run;
int maxruns;
int printstrings;
int nmutation;
int ncross;

/*随机数发生器使用的静态变量*/
static double oldrand[55];
static int jrand;
static double rndx2;
static int rndcalcflag;
/*输出文件指针*/
FILE *outfp;
/*函数定义*/
void advance_random();
int flip(float);
int rnd(int,int);
void randomize();
double randomnormaldeviate();
float randomperc();
float rndreal(float,float);
void warmup_random(float);
void initialize(),initdata(),initpop();
void initreport(),generation(),initmalloc();
void freeall(),nomemory(char*),report();
void writepop(),writechrom(unsigned *);
void preselect();
void statistics(struct individual*);
void title(),repchar(FILE *,char *,int);
void skip(FILE *,int);
int select();
void objfunc(struct individual *);
int crossover(unsigned *,unsigned *,unsigned *,unsigned *);
void mutation(unsigned *);

/*遗传算法初始化*/
void initialize()
{
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();
}

/*遗传算法参数输入*/
void initdata()
{
char answer[2];
printf("种群大小(20-100):");
scanf("%d",&popsize);
if((popsize%2)!=0)
{
fprintf(outfp,"种群大小已设置为偶数\n");
popsize++;
};
printf("染色体长度(8-40):");
scanf("%d",&lchrom);
printf("是否输出染色体编码(y/n):");
scanf("%s",answer);
getchar();
printstrings=1;
if(strncmp(answer,"n",1)==0) printstrings=0;
printf("最大世代数(100-300):");
scanf("%d",&maxgen);
printf("交叉率(0.2-0.9):");
scanf("%f",&pcross);
printf("变异率(0.01-0.1):");
scanf("%f",&pmutation);
}

/*随机初始化种群*/
void initpop()
{
int j,j1,k,stop;
unsigned mask=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));
else stop=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].xsite=0;
objfunc(&(oldpop[j]));
}
}

/*初始参数输出*/
void initreport()
{
void skip();
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);
}

void generation()
{
int mate1,mate2,jcross,j=0;
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);
objfunc(&(newpop[j]));
newpop[j].parent[0]=mate1+1;
newpop[j].parent[1]=mate2+1;
newpop[j].xsite=jcross;
objfunc(&(newpop[j+1]));
newpop[j+1].parent[0]=mate1+1;
newpop[j+1].parent[1]=mate2+1;
newpop[j].xsite=jcross;
j=j+2;
}
while(j<(popsize-1));
}

/*为全局数据变量分配空间*/
void initmalloc()
{
unsigned nbytes;

int j;
nbytes=popsize*sizeof(struct individual);
if((oldpop=(struct individual *)malloc(nbytes))==NULL)
nomemory("oldpop");
if((newpop=(struct individual *)malloc(nbytes))==NULL)
nomemory("newpop");
nbytes=chromsize*sizeof(unsigned);
for(j=0;j<popsize;j++)
{
if((oldpop[j].chrom=(unsigned *)malloc(nbytes))==NULL)
nomemory("oldpop chromosomes");
if((newpop[j].chrom=(unsigned *)malloc(nbytes))==NULL)
nomemory("newpop chromosomes");
}
if((bestfit.chrom=(unsigned *)malloc(nbytes))==NULL)
nomemory("bestfit chromosome");
}

/*释放内存空间*/
void freeall()
{
int i;
for(i=0;i<popsize;i++)
{free(oldpop[i].chrom);
 free(newpop[i].chrom);
}
free(oldpop);
free(newpop);
free(bestfit.chrom);
}

/*内存不足,退出*/
void nomemory(char *string)
{
fprintf(outfp,"malloc:out of memory making %s!!\n",string);
exit(-1);
}

/*输出种群统计结果*/
void report()
{
void repchar(),skip();
void writepop(),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+1);
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);
}

void writepop()
{
struct individual *pind;
int j;
for(j=0;j<popsize;j++)
{
fprintf(outfp,"%3d ",j+1);
pind=&(oldpop[j]);
writechrom(pind->chrom);
fprintf(outfp," %8f",pind->varible);
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);
}
}

/*输出染色体编码*/
void writechrom(unsigned *chrom)
{int j,k,stop;
unsigned mask=1,tmp;
for(k=0;k<chromsize;k++)
{
tmp=chrom[k];
if(k==(chromsize-1))
stop=lchrom-(k*8*sizeof(unsigned));
else stop=8*sizeof(unsigned);
for(j=0;j<stop;j++)
{
if(tmp&mask)  fprintf(outfp,"1");
else fprintf(outfp,"0");
tmp=tmp>>1;
}
}
}

void preselect()
{
int j;
sumfitness=0;
for(j=0;j<popsize;j++) sumfitness+=oldpop[j].fitness;
}

/*轮盘赌选择*/
int select()
{
extern float randomperc();
float sum,pick;
int i;
pick=randomperc();
sum=0;
if(sumfitness!=0)
{
for(i=0;(sum<pick)&&(i<popsize);i++)
sum+=oldpop[i].fitness/sumfitness;
}
else  i=rnd(1,popsize);
return(i-1);
}

/*计算种群统计数据*/
void statistics(struct individual *pop)
{
int i,j;
sumfitness=0.0;
min=pop[0].fitness;
max=pop[0].fitness;
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;
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;
}
}
avg=sumfitness/popsize;
}

void title()
{
printf("SGA Optimizer\n");
printf("基本遗传算法\n");
}

void repchar(FILE *outfp,char *ch,int repcount)
{int j;
for(j=1;j<=repcount;j++) fprintf(outfp,"%s",ch);
}

void skip(FILE *outfp,int skipcount)
{
int j;
for(j=1;j<=skipcount;j++) fprintf(outfp,"\n");
}

/*计算适应度函数值*/
void objfunc(struct individual *critter)
{
unsigned mask=1;
unsigned bitpos;
unsigned tp;
double pow(),bitpow;
int j,k,stop;
critter->varible=0.0;
for(k=0;k<chromsize;k++)
{
if(k==(chromsize-1)) stop=lchrom-k*8*sizeof(unsigned);
else stop=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.0+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)
{
int j,k,stop;
unsigned mask,temp=1;
for(k=0;k<chromsize;k++)
{
mask=0;
if(k==(chromsize-1)) stop=lchrom-k*8*sizeof(unsigned);
else k=8*sizeof(unsigned);
for(j=0;j<stop;j++)
{
if(flip(pmutation))
{mask=mask|(temp<<j);
nmutation++;
}
child[k]=child[k]^mask;
}
}
}

/*由两个父个体交叉产生两个子个体*/
int crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2)
{
int j,jcross,k;
unsigned mask,temp;
if(flip(pcross))
{
jcross=rnd(1,(lchrom-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];
}
else if((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=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<chromsize;k++)
{child1[k]=parent1[k];
 child2[k]=parent2[k];
}
jcross=0;
}
return(jcross);
}

/*产生55个随机数*/
void advance_random()
{
int j1;
double new_random;
for(j1=0;j1<24;j1++)
{
new_random=oldrand[j1]-oldrand[j1+31];
if(new_random<0.0) 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+=1.0;
oldrand[j1]=new_random;
}
}

/*以一定概率产生0或1*/
int flip(float prob)
{
float randomperc();
if(randomperc()<=prob) return(1);
else return(0);
}

/*设定随机数种子并初始化随机数发生器*/
void randomize()
{
float randomseed;
int j1;
for(j1=0;j1<=54;j1++) oldrand[j1]=0.0;
jrand=0;
do
{
printf("随机数种子[0-1]:");
scanf("%f",&randomseed);
}
while((randomseed<0.0)||(randomseed>1.0));
warmup_random(randomseed);
}

/*产生随机标准差*/
double randomnormaldeviate()
{
double sqrt(),log(),sin(),cos();
float randomperc();
double t,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);
}
}

/*与库函数random()作用相同，产生[0,1]之间一个随机数*/
float randomperc()
{
jrand++;
if(jrand>=55)
{jrand=1;
advance_random();
}
return((float)oldrand[jrand]);
}

/*在整数low和high之间产生一个随机整数*/
int rnd(int low,int high)
{
int i;
float randomperc();
if(low>=high) i=low;
else
{i=(randomperc()*(high-low+1))+low;
 if(i>high) i=high;
}
return(i);
}

/*初始化随机数发生器*/
void warmup_random(float random_seed)
{
int j1,ii;
double new_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+=1.0;
 prev_random=oldrand[ii];
}
advance_random();
advance_random();
advance_random();
jrand=0;
}

/*主程序*/
void main()
{
struct individual *temp;
FILE *fopen();
void title();

if((outfp=fopen("file1","w"))==NULL)
{fprintf(stderr,"Cannot open output file\n");
 exit(-1);
}

title();
printf("输入遗传算法执行次数(1-5):");
scanf("%d",&maxruns);
for(run=1;run<=maxruns;run++)
{
initialize();
for(gen=0;gen<maxgen;gen++)
{fprintf(outfp,"\n第%d/%d次运行：当前代为%d，共%d代\n",run,maxruns,gen,maxgen);
 generation();
 statistics(newpop);
 report();

 oldpop=newpop;

}
freeall();
}
}