#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++)