ga.c

一个求函数最值得c程序

#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#include	<math.h>
#define		PI	3.14159265


/*
定义个体的数据结构，其中有一个字符串指针，里面是2个自变量x，y的字符串编码数据连在一起组成（0，1编码）,
实际上要动态分配32位，即x,y编码后各16位，即x,y的编码大小范围为0x0000到0xFFFF,0x0000对应-10，0xFFFF对应+10；
还有两个变量x，y以及此个体的适应度
*/

struct	population
	{char	*chrom;
	double	x,y,fitness;
	};

int			popsize,lchrom,gen,maxgen,maxpos,minpos;
long int	nmutation,ncross;
double		pcross,pmutation,sumfitness,avg,max,min,coef;
struct population	*oldpop,*newpop,*p1;

int 	select(void);
int 	crossover(char *farther1,char *farther2,int m);        /*用单点交叉算子进行交叉运算*/
int 	mutation(char ch);                                     /*用基本位变异算子进行变异运算*/
void 	generation(void);  /*进化产生下一代*/
double 	fitfunc(double x,double y);/*计算适应度，其实就是目标函数值*/
double 	decode(char *str,int sec);/*解码，sec取值1，2分别为对第一个（即x的编码数据）和第二个（即y的编码数据）进行解码，得到x和y的值*/
void 	statistics(struct population *pop);
int		flip(double);
void 	initialize(void);/*初始化，对第一代进行初始化*/
void 	*talloc(int size);/*动态分配内存*/

main()
{int	gen,k,j,oldmaxpos,valgen;
double	oldmax,valmax;
maxgen=500;	/*总共遗传500代*/	
popsize=100;/*共有100个个体*/		
lchrom=32;/*编码长度为32位，其中x，y各占16位*/
pcross=0.7;	/*交叉概率为0.7*/
pmutation=0.05;/*变异概率为0.05*/



/*动态分配内存，各给oldpop和newpop分配100个struct population单位的内存*/
oldpop=(struct population *)talloc(popsize*sizeof(struct population));
newpop=(struct population *)talloc(popsize*sizeof(struct population));
for(k=0;k<popsize;k++)
	{oldpop[k].chrom=(char *)talloc(lchrom*sizeof(char));
	newpop[k].chrom=(char *)talloc(lchrom*sizeof(char));
	}



/*初始化，产生第一代个体*/
initialize();		valmax=max;			valgen=0;


/*循环依次产生499代个体*/
for(gen=1;gen<=maxgen;gen++)
	{oldmax=max;		oldmaxpos=maxpos;
	generation();		statistics(newpop);
	if(max<oldmax)
		{for(j=0;j<lchrom;j++)
			newpop[minpos].chrom[j]=oldpop[oldmaxpos].chrom[j];
		newpop[minpos].x=oldpop[oldmaxpos].x;
		newpop[minpos].y=oldpop[oldmaxpos].y;
		newpop[minpos].fitness=oldpop[oldmaxpos].fitness;
		statistics(newpop);
		}
	printf("%d\t%lf  %lf  %lf  %ld  %ld\n",gen,max,avg,min,ncross,nmutation);
	p1=oldpop;	oldpop=newpop;	newpop=p1;
	if(valmax<max)	{valmax=max;	valgen=gen;}
	}



/*把之前动态分配的内存释放掉，防止内存泄露*/
for(k=0;k<popsize;k++)
	{free(oldpop[k].chrom);		free(newpop[k].chrom);}
free(newpop);		free(oldpop);
printf("\nMax val=%lf find in gen=%d\n",valmax,valgen);
return 0;
}


/*此函数产生下一代，每次由随机选出两个产生两个下一代个体，总共循环popsize/2=50次*/
void generation(void)
{int	j,mate1,mate2;
for(j=0;j<popsize;j=j+2)
	{mate1=select();	mate2=select();
	crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
	newpop[j].x=decode(newpop[j].chrom,1);
	newpop[j].y=decode(newpop[j].chrom,2);
	newpop[j].fitness=fitfunc(newpop[j].x,newpop[j].y);
	newpop[j+1].x=decode(newpop[j+1].chrom,1);
	newpop[j+1].y=decode(newpop[j+1].chrom,2);
	newpop[j+1].fitness=fitfunc(newpop[j+1].x,newpop[j+1].y);
	}
}


/*此函数采取的是有退还随机选择方式，得到能进入下一代的个体的下标*/
int select()
{int   j;
double stand,psum;
psum=0;		stand=sumfitness*rand()/RAND_MAX ;
for(j=0;j<popsize;j++)
	{psum+=oldpop[j].fitness;
	if(psum>stand)	break;
	}
return(j--);
}



/*采取单点交叉的方式，将两个个体的某位(随机产生)之前的码互换*/
int crossover(char *farther1,char *farther2,int m)
{int j,k;
if(1==flip(pcross))	{k=rand()/RAND_MAX*(lchrom-1);	ncross=ncross+1;}
	else	k=lchrom;
if(k!=lchrom)
	{for(j=0;j<k;j++)
		{newpop[m].chrom[j]=mutation(farther1[j]);
		newpop[m+1].chrom[j]=mutation(farther2[j]);
		}
	for(j=k;j<lchrom;j++)
		{newpop[m].chrom[j]=mutation(farther2[j]);
		newpop[m+1].chrom[j]=mutation(farther1[j]);
		}
	}
else
	{for(j=0;j<lchrom;j++)
		{newpop[m].chrom[j]=mutation(farther1[j]);
		newpop[m+1].chrom[j]=mutation(farther2[j]);
		}
	}
return(1);
}




/*用基本位变异算子进行变异运算,有pmutation=5%的概率的可能性产生变异，变异的结果是那一位取反*/
int mutation(char ch)
{if(1==flip(pmutation))
	{nmutation++;
	if(ch==1)	ch=0;
		else ch=1;
	}
if(ch==1)	return(1);
	else	return(0);
}



/*初始化，对第一代进行初始化，得到一系列初始值*/
void initialize(void)
{int	j,i;
nmutation=0;	ncross=0;	coef=pow(2.0,(lchrom/2))-1.0;	srand( (unsigned)time( NULL ) );
for(j=0;j<popsize;j++)
	{for(i=0;i<lchrom;i++)	oldpop[j].chrom[i]=rand()/RAND_MAX*2;
	oldpop[j].x=decode(oldpop[j].chrom,1);
	oldpop[j].y=decode(oldpop[j].chrom,2);
	oldpop[j].fitness=fitfunc(oldpop[j].x,oldpop[j].y);
	}
statistics(oldpop);
printf("pop=%d  lchrom=%d  maxgen=%d  pcross=%lf  pmutation=%lf\n\n",
		popsize,lchrom,maxgen,pcross,pmutation);
printf("Gen\tMaxFit\tAveFit\tMinFit\tnCross\tnMutation\n");
printf("0\t%lf  %lf  %lf  %ld  %ld\n",max,avg,min,ncross,nmutation);
}



/*对某一代的各个个体的数据进行统计，得到那一代的平均的适应度、最大适应度、最大适应度对应的下标、最小适应度、最小适应度对应的下标*/
void statistics(struct population *pop)
{int j;
sumfitness=pop[0].fitness;
min=pop[0].fitness;     minpos=0;
max=pop[0].fitness;		maxpos=0;
for(j=1;j<popsize;j++)
	{sumfitness=sumfitness+pop[j].fitness;
	if(pop[j].fitness>max)	{max=pop[j].fitness;	maxpos=j;}
	if(pop[j].fitness<min)	{min=pop[j].fitness;	minpos=j;}
	}
avg=sumfitness/popsize;
}



/*解码函数，给定输入的编码字符串和要解码的段(0，1，0对应x，1对应y)解出相应的x或者y来，返回的double值在-10和10之间*/
double decode(char *str,int sec)
{int j;
double bin,conv,t;
conv=0;  	bin=1;
if(sec==1)
	{for(j=lchrom/2-1;j>=0;j--)
		{if(str[j]==1)	conv=conv+bin;
		bin=bin*2;
		}
	}
else if(sec==2)
	{for(j=lchrom-1;j>=lchrom/2;j--)
		{if(str[j]==1)	conv=conv+bin;
		bin=bin*2;
		}
	}
else printf("Wrong Parameter!!!");
t=conv*20/coef-10;
return(t);
}



/*计算计算适应度，其实就是目标函数值，即给定x和y的值，求出z的值*/
double fitfunc(double x,double y)
{double z;

double t1,t2;
t1=((x+5)*(x+5)+(y+5)*(y+5))/10;
t2=((x-5)*(x-5)+(y-5)*(y-5))/20;
z=0.9*exp(-t1)+0.99996*exp(-t2);
//*//////////////////////////
return(z);
}

int flip(double prob)
{double tmp;
tmp=(double)rand()/RAND_MAX;
if(tmp<=prob)	return(1);
return(0);
}




/*分配内存的函数*/
void * talloc(int size)
{void * ptr;
if(NULL==(ptr=malloc(size)))
	{printf("ERROR ! not enough memory .\n\n");		exit(1);}
return ptr;
}