ga.cpp

遗传算法

#include <float.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include<iostream.h>
#include<stdio.h>
#define randomize() srand(time(NULL))
#define DEFPOPSIZ 50	//default pop size, value domain:	[2,200]
#define DEFCHRLEN 22	//default chrom length:				[2,63]
#define DEFMAXGEN 100	//default max generation:			[1,65535]
#define DEFPC 0.25	//default crossover probability:		[0.0,1.0]
#define DEFPM 0.01	//default mutation probability:			[0.0,1.0]
#define maxpop 100
#define maxstring 64

typedef struct pp
{
	unsigned chrom[maxstring];
	float x,fitness;
	unsigned  parent1,parent2,xsite;
}POP;


POP *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,minpp,jrand;
float pcross,pmutation,sumfitness,avg,max,min,seed,rj[maxpop],oldrand[maxpop];
double coef;
float objfunct(float);
void statistics(POP *pop);
int select();
int flip(float);
int crossover(unsigned *parent1,unsigned  *parent2,int k5);
int mutation(unsigned ch);
void generation();
void initialize();
void report(int gen);
void initpop();
void initdata();
void initreport();
float decode(unsigned *pp);
float randoml();
void randomizel();
pause();

/*GA 主程序*/
void main()
{
	long int gen,k,j;
	float oldmax;
	int oldmaxpp;
	gen=0;
	initialize();
	system("cls"); 
	p1=newpop;
	newpop=oldpop;
	statistics(newpop);
	report(gen);
	newpop=p1;
	getchar();
	do
	{
		gen=gen+1;
		oldmax=max;
		oldmaxpp=maxpp;
		generation();
		statistics(newpop);
		if (max<oldmax)
		{for (j=0;j<lchrom;j++)
		newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
		newpop[minpp].x=oldpop[oldmaxpp].x;
		newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
		statistics(newpop);
		}
		report(gen);
		p1=oldpop;
		oldpop=newpop;
		newpop=p1;
		getchar();
	}while (gen<maxgen);
		exit(0);
	
}

/*个体适应度计算*/
float objfunc(float x1)
{
	float y;
	y=3.1415926*x1;
	y=sin(2.0*y);
	return y*y;
}

/*群体适应度统计*/
void statistics(POP *pop)
{
	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/(float)popsize;
}

/*群体更新*/
void generation()
{
	unsigned int j,mate1,mate2;
	j=0;
	do
	{
		mate1=select();
		mate2=select();
		crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
		newpop[j].x=(float)decode(newpop[j].chrom);
		newpop[j].fitness=objfunc(newpop[j].x);
		newpop[j].parent1=mate1;
		newpop[j].parent2=mate2;
		newpop[j].xsite=jcross;
		newpop[j+1].x=(float)decode(newpop[j+1].chrom);
		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);
}

/*控制参数输入*/
void initdata()
{
	unsigned i;
	printf("Please Input Population Size(2-200)(Default:%u):",DEFPOPSIZ);
	scanf("%u",&popsize);
	printf("Please Input Chromosome Length(2-63)(Default:%u):",DEFCHRLEN);
	scanf("%u",&lchrom);
	printf("Please Input Max Generation(1-65535)(Default:%u):",DEFMAXGEN);
	scanf("%u",&maxgen);
	printf("Please Input Crossover Probability(0.0-1.0)(Default:%f):",DEFPC );
	scanf("%f",&pcross);
	printf("Please Input Mutation Probability(0.0-1.0)(Default:%f):",DEFPM);
	scanf("%f",&pmutation);
	gen=0;
	ncross=0;
	nmutation=0;
	srand((unsigned)time(NULL));
	randomizel();
	
	if(!(oldpop=(POP *)malloc(popsize*sizeof(POP))))
	{
		printf("Allocate Memory Failed !");
		exit(1);
	}
	if(!(newpop=(POP *)malloc(popsize*sizeof(POP))))
	{
		printf("Allocate Memory Failed !");
		exit(1);
	}
}
/*初始化信息输出*/
void initreport()
{	
	
	FILE *fp;
	
	printf("                         Genetic Algorithm - GA\n");
	printf("________________________________________________________________________________\n");
	printf("    GA Parameters:\n");
	printf("Population Size(nPopSize) = %u\n",popsize);
	printf("Chromosome Length(nChromLen) = %u\n",lchrom);
	printf("Maximum of Generation(nMaxGen) = %u\n",maxgen);
	printf("Crossover Probability(fPc) = %f\n",pcross);
	printf("Mutation Probability(fPm) = %f\n",pmutation);
	printf("________________________________________________________________________________\n");
	printf("Initial Population Average Fitness = %f\n",avg);
	printf("Initial Population Max Fitness = %f\n",max);
	printf("Initial Population Min Fitness = %f\n",min);
	printf("Initial Population Sum Fitness = %f\n",sumfitness);
	printf("________________________________________________________________________________\n");
	
	if((fp=fopen("GAReport.txt","w"))==NULL)
	{
		printf("Cannot Open File for Report!");
		exit(2);
	}
	
	fprintf(fp,"                     Genetic Algorithm - GA\n");
	fprintf(fp,"________________________________________________________________________________\n");
	fprintf(fp,"     Parameters:\n");
	fprintf(fp,"Population Size(nPopSize) = %u\n",popsize);
	fprintf(fp,"Chromosome Length(nChromLen) = %u\n",lchrom);
	fprintf(fp,"Maximum of Generation(nMaxGen) = %u\n",maxgen);
	fprintf(fp,"Crossover Probability(fPc) = %f\n",pcross);
	fprintf(fp,"Mutation Probability(fPm) = %f\n",pmutation);
	fprintf(fp,"________________________________________________________________________________\n");
	fprintf(fp,"Initial Population Average Fitness = %f\n",avg);
	fprintf(fp,"Initial Population Max Fitness = %f\n",max);
	fprintf(fp,"Initial Population Min Fitness = %f\n",min);
	fprintf(fp,"Initial Population Sum Fitness = %f\n",sumfitness);
	fprintf(fp,"________________________________________________________________________________\n");
	
	fclose(fp);
	pause();
	
	
}
/*生成初始群体*/
void initpop()
{
	int j,j1;
	randomize();
	for(j=0;j<popsize;j++)
	{
		for(j1=0;j1<lchrom;j1++)
		oldpop[j].chrom[j1]=(int)(2.0/(float)RAND_MAX*rand());
		oldpop[j].x=(float)decode(oldpop[j].chrom);
		oldpop[j].fitness=objfunc(oldpop[j].x);
		oldpop[j].parent1=0;
		oldpop[j].parent2=0;
	}
}
/*初始化*/
void initialize()
{
	initdata();
	coef=pow(2.00,lchrom)-1.0;
	initpop();
	statistics(oldpop);
	initreport();
}

/*数据输出*/
void report (int gen)
{
	unsigned i,j;
	FILE *fp;
	if((fp=fopen("GAReport.txt","a"))==NULL)
	{
		printf("Cannot Open File for Report!");
		exit(2);
	}
	printf("    Population Report:\n");
	printf("Generation: %d\n",gen);
	printf("Indiv  Parents   xsite    x        Fitness     String\n");
	
	fprintf(fp,"    Population Report:\n");
	fprintf(fp,"Generation: %d\n",gen);
	fprintf(fp,"Indiv  Parents   xsite    x        Fitness     String\n");
	
	for(i=0;i<popsize;i++)
	{
		printf("%3u>: (%3u,%3u)   %2u %10.4f %10.4f     ",
			i,newpop[i].parent1,newpop[i].parent2,
			newpop[i].xsite,newpop[i].x,newpop[i].fitness);
		fprintf(fp,"%3u>: (%3u,%3u)   %2u %10.4f %10.4f     ",
			i,newpop[i].parent1,newpop[i].parent2,
			newpop[i].xsite,newpop[i].x,newpop[i].fitness);
		for(j=0;j<lchrom;j++)
		{
			printf("%d",newpop[i].chrom[j]);
			fprintf(fp,"%d",newpop[i].chrom[j]);
		}
		printf("\n");
		fprintf(fp,"\n");
	}
	
	printf("________________________________________________________________________________\n");
	printf("    Result:\n");
	printf("Generation Calculated(nGen) = %u\n",gen);
	printf("Average Fitness = %8.4f\n",avg);
	printf("Max Fitness = %f\n",max);
	printf("Min Fitness = %f\n",min);
	printf("Crossover Num = %u\n",ncross);
	printf("Mutate Num = %u\n",nmutation);
	printf("________________________________________________________________________________\n");
	
	fprintf(fp,"________________________________________________________________________________\n");
	fprintf(fp,"    Result:\n");
	fprintf(fp,"Generation Calculated(nGen) = %u\n",gen);
	fprintf(fp,"Average Fitness = %8.4f\n",avg);
	fprintf(fp,"Max Fitness = %f\n",max);
	fprintf(fp,"Min Fitness = %f\n",min);
	fprintf(fp,"Crossover Num = %u\n",ncross);
	fprintf(fp,"Mutate Num = %u\n",nmutation);
	fprintf(fp,"________________________________________________________________________________\n");
	
	fclose(fp);
	system("pause");
}

/*译码*/
float decode (unsigned  *pp)
{
	int j;
	float tt=0.0,tt1=1.0;
	for(j=lchrom-1;j>-1;j--)
	{if (pp[j]) tt+=tt1;
	tt1=2.0*tt1;
	}
	tt/=coef;
	return tt;
}


/*选择操作*/
int select()
{
	double randl,partsum=0;
	int j=0;
	randl=randoml()*sumfitness;
	do
	{
		partsum+=oldpop[j].fitness;
		j=j+1;
	}while ((partsum<randl)&&(j<popsize));
	return j-1;
}

/*变异操作*/
int mutation(unsigned ch)
{
	int mutate;
	mutate=flip(pmutation);
	if(mutate)
	{nmutation+=1;
	if(ch) ch=0;
	else ch=1;
	}
	if(ch) return 1;
	else return 0;
}

/*交叉操作*/
int crossover(unsigned  *parent1,unsigned  *parent2,int k5)
{
	int j;
	if(flip(pcross))
	{
	jcross=rand()%(lchrom-1);
	ncross+=1;
	}
	else 
		jcross=lchrom;
	if (jcross!=lchrom)
	{
		for (j=0;j<jcross;j++)
		{
			newpop[k5].chrom[j]=mutation(parent1[j]);
			newpop[k5+1].chrom[j]=mutation(parent2[j]);
		}
		for (j=0;j<lchrom;j++)
		{	newpop[k5].chrom[j]=mutation(parent2[j]);
		newpop[k5+1].chrom[j]=mutation(parent1[j]);
		}
	}
	else 
	{
		for (j=0;j<lchrom;j++)
		{
			newpop[k5].chrom[j]=mutation(parent1[j]);
			newpop[k5+1].chrom[j]=mutation(parent2[j]);
		}
	}
	return 1;
}

/*重启动随机数发生器*/
void randomizel()
{
	int i;
	randomize();
	for(i=0;i<lchrom;i++)
		oldrand[i]=(float)(rand()/(float)RAND_MAX);
	jrand=0;
}

/*随机数发生器*/
float randoml()
{
	jrand++;
	if (jrand>=lchrom)
	{
		jrand=0;
		randomizel();
	}
	return oldrand[jrand];
}

/*贝努力试验*/
int flip(float probability)
{ 
	float ppp;
	ppp=(float)(rand()/(float)RAND_MAX);
	if(ppp<=probability) return 1;
	return 0;
}

/*延时*/
pause()
{
	int j,j1,x1=0;
	for(j=1;j<=25;j++)
	{

		x1++;
	}
	return x1;
}