ga.cpp

遗传算法的函数优化sga

#include<stdlib.h>
#include<stdio.h>
#include<float.h>
#include<time.h>
#include<math.h>
#include<conio.h>
//#include<graphics.h> 
#define maxpop 100
#define maxstring 64
struct pp
{int chrom[3][maxstring];
double fitness;
double x[3];
unsigned int parent1,parent2,xsite;
};
struct pp *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,minpp,jrand;
float pcross,seed,rj[maxpop],pmutation;
double sumfitness,coef,max,min,avg,oldrand[maxpop];
double objfunc(double *a);
void statistics(struct pp *pop);
int select();
int flip(float b);
int crossover(int parent1[3][maxstring],int parent2[3][maxstring],int k5);
int mutation(int ch);
void generation();
void initialize();
void report(int c);
void initpop();
void initdata();
void initreport();
double decode(int *pp);
double random1();
void randomize1();
/*SGA主程序*/
void main()
{
double oldmax;
int oldmaxpp;
unsigned int i,k,j;
if(!(oldpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
{printf("memory request failed!\n");
exit(0);}
if(!(newpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
{printf("memory request failed!\n");
exit(0);}
if(!(p1=(struct pp*)malloc(sizeof(struct pp))))
{printf("memory request failed!\n");
exit(0);}
for(k=0;k<maxpop;k++)
for(i=0;i<3;i++)
oldpop[k].chrom[i][0]='\0';
for(k=0;k<maxpop;k++)
for(i=0;i<3;i++)
newpop[k].chrom[i][0]='\0';
gen=0;
initialize();
//clear;
p1=newpop;
newpop=oldpop;
statistics(newpop);
report(gen);
newpop=p1;
getch();
do{gen=gen+1;
  srand(time(0));
  oldmax=max;
  oldmaxpp=maxpp;
  generation();
  statistics(newpop);
  if(max<oldmax)
  {for(i=0;i<3;i++)
    for(j=0;j<lchrom;j++)
       newpop[minpp].chrom[i][j]=oldpop[oldmaxpp].chrom[i][j];      /*精英保留策略*/
        newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
        statistics(newpop);
  }
   //report(gen);
   p1=oldpop;
   oldpop=newpop;
   newpop=p1;
   //getch();                   /*分代显示*/
}while(gen<maxgen);
report(gen);
free(p1);
free(oldpop);
free(newpop);
exit(0);
}
/*个体适应度计算*/
double objfunc(double *x1)
{int i;
double y1,y;
y=0.00;
for(i=0;i<3;i++)
{y1=x1[i]*x1[i];
y=y+y1;
}
//y1=x1[0]*x1[0]+x1[1]*x1[1];
//y=pow(y1,0.25)*(sin(2500*pow(y1,0.2))+1);
return y;
}
/*群体适应度统计*/
void statistics(pp *pop)
{unsigned int j;
sumfitness=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
for(j=1;j<popsize;j++)
{sumfitness=sumfitness+pop[j].fitness;
if(pop[j].fitness>max)
{max=pop[j].fitness;
maxpp=j;
}
if(pop[j].fitness<min)
{min=pop[j].fitness;
minpp=j;
}
} 
avg=sumfitness/(double)popsize;
}
/*群体更新*/
void generation()
{unsigned int j,mate1,mate2;
int i;
j=0;
do{
	mate1=select();
	mate2=select();
	crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
	for(i=0;i<3;i++)
		newpop[j].x[i]=5.12*decode(newpop[j].chrom[i]);
	newpop[j].fitness=objfunc(newpop[j].x);
	newpop[j].parent1=mate1;
	newpop[j].parent2=mate2;
	newpop[j].xsite=jcross;
	for(i=0;i<3;i++)
		newpop[j+1].x[i]=5.12*decode(newpop[j+1].chrom[i]);
	newpop[j+1].fitness=objfunc(newpop[j+1].x);
	newpop[j+1].parent1=mate1;
	newpop[j+1].parent2=mate2;
	newpop[j+1].xsite=jcross;
	j=j+2;
}while(j<popsize);
}
/*延时*/
pause()
{int j,j1;
int x1;
x1=0;
for(j=1;j<=25;j++)
{for(j1=1;j1<2;j1++) x1=x1+1;
}
return x1;
}
/*初始化*/
void initialize()
{initdata();
coef=pow(2.00,lchrom-1)-1.0;
initpop();
statistics(oldpop);
initreport();
}
/*译码*/
double decode(int *pp)
{int j;
double tt1;
double tt;
tt1=1.0;
tt=0.0;
for(j=lchrom-1;j>0;j--)
{if(pp[j]) 
tt=tt+tt1;
tt1=2.0*tt1;
}
if(!pp[0])
tt=tt/coef;
else 
tt=(tt-coef)/coef;
return tt;
}
/*控制参数输入*/
void initdata()
{
//clear;
printf("******* SGA DATA ENTRY AND INITIALIZATION *******\n");
printf("\n");
printf("enter population size--------->");scanf("%d",&popsize);
printf("enter chromosome length------->");scanf("%d",&lchrom);
printf("enter max.generations--------->");scanf("%d",&maxgen);
printf("enter crossover probability--->");scanf("%f",&pcross);
printf("enter mutation probability---->");scanf("%f",&pmutation);
//clear;
srand(time(0));
randomize1();
nmutation=0;
ncross=0;
}
/*初始化信息输出*/
void initreport()
{
printf("  A simple generic algorithm -sga\n");
printf("  ALL rights reserved\n");
printf("population size (popsize) =%d\n",popsize);
printf("Chromosome length (lchrom) =%d\n",lchrom);
printf("maximum # of generation(maxgen) =%d\n",maxgen);
printf("crossover probability(pmutation) =%f\n",pcross);
printf("mutation probability(pmutation) =%f\n",pmutation);
printf("-----------------------------------------\n");
printf("\n");
printf("initial population maximum fitness = %f\n",max);
printf("initial population average fitness = %f\n",avg);
printf("initial population minimum fitness = %f\n",min);
printf("initial population sum of fitness  =%f\n",sumfitness);
}
/*选择操作*/
int select()
{double rand1,partsum;
unsigned int j;
partsum=0.0;
j=0;
rand1=random1()*sumfitness;
do
{partsum=partsum+oldpop[j].fitness;
j=j+1;
}while((partsum<rand1)&&(j<popsize));
return j-1;
}
/*变异操作*/
int mutation(int ch)
{int mutate;
mutate=flip(pmutation);
if(mutate)
{nmutation=nmutation+1;
if(ch) ch=0;
else ch=1;
}
if(ch) ch=0;
else ch=1;
if(ch) 
return 1;
else 
return 0;
}
/*生成初始群体*/
void initpop()
{unsigned int j,j1,i;
srand(time(0));
for(j=0;j<popsize;j++)
{for(i=0;i<3;i++)
{for(j1=0;j1<lchrom;j1++)
oldpop[j].chrom[i][j1]=rand()%2;
oldpop[j].x[i]=5.12*decode(oldpop[j].chrom[i]);
}
oldpop[j].fitness=objfunc(oldpop[j].x);
oldpop[j].parent1=0;
oldpop[j].parent2=0;
oldpop[j].xsite=0;
}
}
/*交叉操作*/
int crossover(int parent1[3][maxstring],int parent2[3][maxstring],int k5)
{unsigned int i,j,j1;
int char1[3*maxstring],char2[3*maxstring];
if(flip(pcross))
{jcross=rand()%(3*lchrom);
}
else jcross=3*lchrom;
if(jcross!=3*lchrom)
{
for(j=0;j<3;j++)
for(j1=0;j1<lchrom;j1++)
{i=j*lchrom+j1;
if(i<jcross)
{char1[i]=mutation(parent1[j][j1]);
char2[i]=mutation(parent2[j][j1]);
}
if(i>=jcross&&i<3*lchrom)
{char1[i]=mutation(parent2[j][j1]);
char2[i]=mutation(parent1[j][j1]);
}
}
}
else
{
	for(j=0;j<3;j++)
		for(j1=0;j1<lchrom;j1++)
		{char1[j*lchrom+j1]=mutation(parent1[j][j1]);
		char2[j*lchrom+j1]=mutation(parent2[j][j1]);
		}
}
for(j=0;j<3;j++)
for(j1=0;j1<lchrom;j1++)
{newpop[k5].chrom[j][j1]=char1[j*lchrom+j1];
newpop[k5+1].chrom[j][j1]=char2[j*lchrom+j1];
}
return 1;
}
/*重启动随机数发生器*/
void randomize1()
{unsigned int i;
srand(time(0));
for(i=0;i<popsize;i++)
oldrand[i]=double(1+rand()%30001)/30001.00;
jrand=0;
}
/*随机数发生器*/
double random1()
{jrand=jrand+1;
if(jrand>=popsize)
{jrand=0;
randomize1();
}
return oldrand[jrand];
}
/*贝努利实验*/
int flip(float probability)
{float ppp;
ppp=float((1+rand()%20001)/20001);
if(ppp<=probability) return 1;
return 0;
}
/*数据输出*/
void report(int gen)
{unsigned int k,j,i;
for(j=0;j<79;j++)
printf("*");
printf("\n");
printf("          population report\n");
printf("             generation %3d\n",gen);
printf("# parents xsite string x fitness");
printf("\n");
for(j=0;j<79;j++)
printf("+");
printf("\n");
for(j=0;j<popsize;j++)
{printf("%2d,%2d  ",j,newpop[j].parent1);
printf("%2d,%2d  ",newpop[j].parent2,newpop[j].xsite);
for(i=0;i<3;i++)
{printf("%12.2f  ",newpop[j].x[i]);
for(k=0;k<lchrom;k++)
printf("%d",newpop[j].chrom[i][k]);
}
printf("%  6.4f -NEW.\n",newpop[j].fitness);
} 
for(k=0;k<79;k++) printf("*");
printf("\n");
printf("RESULT GEN:%3d ",gen);
printf("AVG= %8.4f MIN= %8.4f MAX= %8.4f\n",avg,min,max);
printf("ncross= %4d nmutation= %4d\n",ncross,nmutation);
}