ga.cpp

经过改进的遗传算法的VC源代码。经测试算法有效可行。

//本程序利用直接编码，用于渐近衰减模型
//f(x,y)=0.5-(pow(sin(sqrt(x*x+y*y)),2)-0.5)/pow((1+0.001*(x*x+y*y)),2)参数的估算


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <ctype.h>
//#include <values.h>
#include <string.h>


//定义控制参数

#define POPSIZE  150     //定义种群的大小
#define NVARS   2       //定义参数的个数
//#define PXOVER   0.9    //定义交叉率
//#define PMUTATION  0.15 //定义突变率


typedef  struct     //定义基因，种群中的一个个体
{
	double  chrom[NVARS];      //变量串(本例中是a,b,c三参数)
	double lsquare;        //个体的评价度,存放的是评价函数的返回值，即误差平方和的大小
	double r;             //个体的相关系数
	int  fitness;     //相关适应度
}individual;


static double pc,pm1,pm2;

static individual newpop[POPSIZE+1];  //新种群
static individual oldpop[POPSIZE+1];  //老种群
static int location[POPSIZE+1];     //排序后的个体的位置


static int gen;      //当前代数
static int maxgen;  //最大代数
static int change=0; //适应性没有改进的代数
  


static double a[NVARS],b[NVARS];     //变量的上下限  a[]下限，b[]上限


static double  maxlsquare=-1.0e10,minlsquare=1.0e50;//,fx; 




//随机数发生器的宏定义

#define rdint(i)   (rand()%(int)(i))
#define rdft()  ((double)rdint(16384)/(16383.0))
#define rnd(a,b)  (rdint((int)(b)-(int)(a)+1)+(int)(a))



//评估函数：使用到用户定义的衰减模型,每次如果被改变则要重新编译，当前所用的模型是f(x)=a-b*c^x
//返回值是误差的平方和，显然返回值越大则表示评价的结果越差

double  evaluate(double *prms)  //参数为个体基因中的参数串charm[]
{
	//int i; 
	double x, serr=0.0;

        x=sqrt(prms[0]*prms[0]+prms[1]*prms[1]);
	serr=0.5-(pow(sin(x),2)-0.5)/pow((1+0.001*(prms[0]*prms[0]+prms[1]*prms[1])),2);
	
	
	return (serr);
}





//用于确定数组选择区域函数，通过快速排序法实现，（二分法排序,升序）

void quick_sort(double *item,int left,int right,int *locat)  
      //item：需排序的数组，left：数组的下标下界， 
	  //right：数组的下标上界，locat：数组中各元素在原数组中的位置
{
    double fa,fb;
    int i,j,k;

	i=left;j=right;
	fa=item[(left+right)/2];

	do{

		while((item[i]<fa)&&(i<right))i++;
		while((fa<item[j])&&(j>left))j--;


		if(i<=j)
		{
			fb=item[i];
			item[i]=item[j];
			item[j]=fb;

			k=locat[i];
			locat[i]=locat[j];
			locat[j]=k;

			i++;j--;
		}

	}while(i<=j);
	if(left<j) quick_sort(item,left,j,locat);
	if(i<right)quick_sort(item,i,right,locat);
}


//用于确定在种群中的个体选择位置和规格化适应度的函数

void normalfitness(individual *pop)  //参数是种群数组newpop[]等
{
	double fit[POPSIZE];
	int i;

	for(i=0;i<POPSIZE;i++)
	{
		fit[i]=pop[i].lsquare;  //个体的适应性 
		location[i]=i;
	}

	quick_sort(fit,0,POPSIZE-1,location);   //按适应度由小到大排序

	for(i=0;i<POPSIZE;i++)
		pop[location[i]].fitness=2*(i+1);   //重新计算适应度，计算后原先适应度大的将变小
	                                       //因初始适应度是用评价函数的返回值表示的，而评价函数返回的是误差，
	                                       //故原先的适应度大的表示实际误差大，实际的适应性较差
	                                        //规格化运算后，适应度的值正比地 反映了该个体的适应程度
}


//初始化种群的函数，用随机生成的数初始化参数a，b，c；
//用评估函数的返回值作为个体的适应度，同时规格化适应度确定个体的选择位置


void initpop(void)
{
	int i,j;
   //double fx,bt;
	
	double m;

	for(i=0;i<POPSIZE;i++)
	{
		for(j=0;j<NVARS;j++)
		{
			m=rdft();
			oldpop[i].chrom[j]=a[j]+m*(b[j]-a[j]);  //个体中的参数a，b，c随即生成
	//	printf("\nmmmmmmm=%lf\n",m);
		}
			

		
	    oldpop[i].lsquare=evaluate(oldpop[i].chrom);//用评估函数的返回值作为个体的适应度
		oldpop[i].fitness=0;
        //oldpop[i].r=cal_coeff(oldpop[i].chrom);//
	
	}
	normalfitness(oldpop);//确定个体的选择位置和规格化适应度
	oldpop[POPSIZE]=oldpop[location[POPSIZE-1]];
}



//选择函数：采用赌盘选择方法

int select(individual *pop)
{ 
	double rand1;
	int partsum=0;
	int i=0;
	rand1=rdft()*POPSIZE*(POPSIZE+1);
   
	//printf("rand1=%lf\n",rand1);
	
	for(i=0;(rand1>=partsum);i++)
		partsum+=pop[i].fitness;//部分和是基因适应度的和
    // printf("sum=%d",partsum);
	return (i-1);
}


//突变：

double mutate(int i)
{
	return a[i]+rdft()*(b[i]-a[i]);//产生参数上下限内的随机数
}


//交叉和突变函数：数学交叉

void xover(double *parent1,double *parent2,double *child1,double *child2)
    //参数为个体基因中的参数串charm[]
{
	double alpha;
//	double bt;
	int i;

 
	for(i=0;i<NVARS;i++)
	{
		alpha=rdft();
		
		child1[i]=alpha*parent1[i]+(1-alpha)*parent2[i];
		child2[i]=alpha*parent2[i]+(1-alpha)*parent1[i];

		if(rdft()<pm1)
			child1[i]=mutate(i);
		if(rdft()<pm2)
			child2[i]=mutate(i);

	}


//printf("\nbt=%lf,pm=%lf\n",bt,pm);
//	printf("\nalpha=%lf",alpha);

}


//初始化函数：

void initialize(void)     //void initialize(int argc,char *argv[])
{
//	int i;

	
//	FILE * datafp;  //实验参数文件指针
	srand(time(NULL));   //初始化随机函数发生器
	
	
	printf("非线性参数进化评估器\n");
	





//	printf("\n输入最大代数：");
//	scanf("%d",&maxgen);


	printf("G-代数  U-没有改变的代数");
	printf("ERR-最小平方误差 r-相关系数\n\n");
	printf("输入参数的下限和上限\n");
	  
/*	for(i=0;i<NVARS;i++)
	{
		printf("\r 参数%d下限=",i);
		scanf("%lf",&a[i]);
		printf("\r 参数%d上限=",i);
		scanf("%lf",&b[i]);
	}*/
a[0]=-100;
a[1]=-100;
b[0]=100;
b[1]=100;
	location[POPSIZE]=POPSIZE;

	initpop();        //初始化种群


}


//重组函数：通过选择、交叉和变异由老的一代产生新的一代

void  recombine(void)
{
	int i=0,ii;
	int mate1,mate2;
    double fit,fitmax,fitave,fit1,fitsum=0.0;

  maxlsquare=-1.0e10;
   minlsquare=1.0e50;

	
	for(ii=0;ii<POPSIZE;ii++)
	{
		if(maxlsquare<oldpop[ii].lsquare) maxlsquare=oldpop[ii].lsquare;
	    if(minlsquare>oldpop[ii].lsquare) minlsquare=oldpop[ii].lsquare;
        fitsum+=oldpop[ii].lsquare;
		
	}


//printf("fitsum=%lf\n",fitsum);


	fitmax=maxlsquare;
	fitave=fitsum/POPSIZE;
	//printf("fitave=%lf\n", fitave);

	while(i<POPSIZE){

		//从老一代中选择两个双亲
	

		mate1=select(oldpop);
		do
		{
			mate2=select(oldpop);
		}while(mate1==mate2);

        fit1=(oldpop[mate1].lsquare>oldpop[mate2].lsquare)
			 ?oldpop[mate1].lsquare:oldpop[mate2].lsquare;
      
		
	//	printf("fit1=%lf   oldpop[mate1]=%lf   oldpop[mate2]=%lf\n",
	 //    fit1,oldpop[mate1].lsquare,oldpop[mate2].lsquare);


        if(fit1>=fitave)
		{
			pc=1.0*(fitmax-fit1)/(fitmax-fitave);
		}
		else
			pc=1.0;



        fit=oldpop[mate1].lsquare;
		if(fit>=fitave)
		{
			pm1=0.5*(fitmax-fit)/(fitmax-fitave);
		}
		else
			pm1=0.5;


        fit=oldpop[mate2].lsquare;
		if(fit>=fitave)
		{
			pm2=0.5*(fitmax-fit)/(fitmax-fitave);
		}
		else
			pm2=0.5;
            
        //    printf("pc=%lf    pm1=%lf    pm2=%lf\n",pc,pm1,pm2);

		
         //对选择的个体进行交叉和突变操作

		if(rdft()<pc)
		{
			xover(oldpop[mate1].chrom,oldpop[mate2].chrom,
				newpop[i].chrom,newpop[i+1].chrom);
	    
			newpop[i].lsquare=evaluate(newpop[i].chrom);//fx;
            newpop[i+1].lsquare=evaluate(newpop[i+1].chrom);//fx;	
	
		}
		else
		{
			newpop[i]=oldpop[mate1];
			newpop[i+1]=oldpop[mate2];
		}

		i+=2;
	   
//printf("\nbt=%lf\n",bt);
       //printf("\npc=%lf\n",pc);
	
	//printf("\ni=%d\n",i);
	}



//在新的种群中随机选择一个个体，若它比原种群中最好的个体好，则替代它，否则不做改变

	i=rnd(0,POPSIZE-1);
//	printf("\ni=%d\n",i);
//printf( "\niiiiiiiiiii=%d\n",i);
//	printf("\noldpop[POPSIZE].lsquare=%lf\n",oldpop[POPSIZE].lsquare);
	if(newpop[i].lsquare<oldpop[POPSIZE].lsquare)
		newpop[i]=oldpop[POPSIZE];
	
//	printf("\n######################################################################\n");



	normalfitness(newpop);     //确定个体在种群中的选择位置和规格化适应度

	//printf("\n&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&\n");


	//如果新的种群中的最好的个体比过去的种群中的最好的个体好，
//就从新的种群中拷贝这个最好的否则用过去的种群中的最好的个体替代当前的最好个体
//注意：这个最好的个体不包括直接进化产生的


	if(newpop[location[POPSIZE-1]].lsquare>oldpop[POPSIZE].lsquare)
	{
		newpop[POPSIZE]=newpop[location[POPSIZE-1]];
		change=0;
	}
	else
	{
		newpop[POPSIZE]=oldpop[POPSIZE];
		change++;
	}



}




void report(int gen)   //结果报告
{
	int i;
	printf("\rG=%3d U=%2d ",gen,change);
    printf("max=%lf min=%lf pc=%lf pm1=%lf  pm2=%lf ",maxlsquare,minlsquare,pc,pm1,pm2); 
	for(i=0;i<NVARS;i++)
		printf("par%d=%lf  ",i,newpop[POPSIZE].chrom[i]);

	printf("err=%lf\n",newpop[POPSIZE].lsquare);

	//printf("\n************************************************************************\n");

}



//主函数：


void main(void)      //void main(int argc,char *argv[])
{
	int i;
//	long key;
	gen=0;

	initialize();     //initialize(argc,argv);
//printf("\n\n%lf\n\n",maxlsquare);
//	for(gen=1;gen<=maxgen;gen++)
do	{
	gen++;	
/*	if(change==50)
	{change=0;
	pm=0.15;}*/
	recombine();
		report(gen);
//printf("\nbt=%lf,     pc=%lf,         pm=%lf\n",bt,pc,pm);
		//拷贝新种群到老种群
		for(i=0;i<=POPSIZE;i++)
			oldpop[i]=newpop[i];
	}while(maxlsquare<0.9999);

//	free(datax);
//	free(datay);

}