ga.cpp

遗传算法源程序 开发环境:C++ 简要说明:遗传算法源程序

#include <float.h>
//#include <alloc.h>
#include <conio.h>
//#include "bios.h"




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


#define maxpop 100
#define maxstring 64
typedef struct  {   unsigned char chrom[maxstring];
            double x,fitness;
			   unsigned char parent1,parent2,xsite;
}pp;
static pp *oldpop,*newpop,*p1;
  int popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,minpp,jrand;
double pcross,pmutation,sumfitness,avg,max,min,seed,rj[maxpop],oldrand[maxpop];
double coef;


ofstream file;
ofstream cross_trace;

double objfunc(double);
void statistics(pp );
int select();
int flip(double);
void crossover(   unsigned char * ,   unsigned char* ,int);
int mutation(  int);
void generation();
void initialize();
void report(int);
void initpop();
void initdata();
void initreport();
double decode(   unsigned char*);
double random1();
void randomize1();



double objfunc(double x1)
{
	double y;
	y=3.1415926*x1;
	y=sin(2.0*y);
	return (y*y);
}

void statistics(pp * 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/(double)popsize;
}

void generation()
{
	  int j,mate1,mate2;
	j=0;
	do{
		mate1=select();
		mate2=select();
		crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
		newpop[j].x=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=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()
{
	printf("--------------------------------------------\n");
	printf("A Simple Genetic Algorithm-SGA\n");
	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);
	pcross=0.8;
	
	printf("Enter mutation probability-->");
//	scanf("%f",&pmutation);
     pmutation=0.08;
//   randomize();
	randomize1();
	nmutation=0;
	ncross=0;
}

void initreport()
{

	printf("------------------------------------------\n");
	printf("  A Simple Genetic Algorithm -SGA\n");
	printf("\n");
	printf(" Population size(popsize) = %d\n",popsize);
	printf(" Chromosome length(lchrom) = %d\n",lchrom);
	printf(" Maximun # of generation(maxgen) = %d\n",maxgen);
	printf(" Crossover probability(pcross) = %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);
    //pause();

}

void initpop()
{
	int j,j1;
//	randomize();
    srand( (unsigned)time( NULL ) ); 
	for(j=0;j<popsize;j++)
	{
		for(j1=0;j1<lchrom;j1++)
			oldpop[j].chrom[j1]=int(rand()*100)%2;
	//	printf("\n\n%ud\n\n",oldpop[j].chrom[j1]);
		oldpop[j].x=decode(oldpop[j].chrom);
		oldpop[j].fitness=objfunc(oldpop[j].x);
		oldpop[j].parent1=0;
		oldpop[j].parent2=0;
		oldpop[j].xsite=0;
	}
}

void initialize()
{
	initdata();
	coef=pow(2.00,lchrom)-1.0;
	initpop();
	statistics(oldpop);
	initreport();
}

void report(int gen)
{
	int k,j;
	for(j=0;j<79;j++){
		printf("*");
		file<<"*";
	}
		
	printf("\n");
	file<<endl;
	printf("              Population Report\n");
	file<<"              Population Report\n";
	printf("              Generation %3d\n",gen);
	file<<"              Generation "<<gen<<endl;
	printf("# parents xsite   string        x      fitness");
	file<<"# parents xsite         string                x               fitness\n";
	printf("\n");
	for(j=0;j<79;j++){
		printf("+");
		file<<"+";
	}
	printf("\n");
	file<<endl;
	for(j=0;j<popsize;j++)
	{
		printf("%2d)(%2d ,",j,newpop[j].parent1);
		file<<j<<")"<<"("<<newpop[j].parent1<<" ";
		printf("%2d) %2d",newpop[j].parent2,newpop[j].xsite);
		file<<newpop[j].parent2<<")    "<<newpop[j].xsite<<"   ";
		for(k=0;k<lchrom;k++){
			printf("%d",newpop[j].chrom[k]);
			file<<newpop[j].chrom[k];
		}
		printf("  %12.1f",newpop[j].x);
		file<<"      "<<newpop[j].x;
		printf(" %6.4f-New.\n",newpop[j].fitness);
		file<<"   "<<newpop[j].fitness<<endl;
	}

	for(k=0;k<79;k++)
	{
		printf("*");
		file<<"*";
	}
	printf("\n");
//	file<<endl;
	printf("RESULT:GEN:%3d",gen);
//	file<<"RESULT:GEN:"<<gen;
	printf("\nAVG= %8.4f MIN= %8.4f MAX= %8.4f\n",avg,min,max);
//	file<<endl<<"AVG="<<avg<<"  "<<"MIN="<<min<<"  "<<"MAX="<<max<<"  "<<endl;
	printf("\nncross= %4d nmutation= %4d\n",ncross,nmutation);
//	file<<endl<<"ncross="<<ncross<<"  "<<"nmutation="<<nmutation<<"  "<<endl<<endl;
}

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

int pause()
{
	int j,j1;
	int x1;
	x1=0;
	for(j=1;j<=25;j++)
	{
		for(j1=1;j1<2;j1++)
			x1++;
	}
	return x1;
}

int select()
{
	double rand1,partsum;
	int j;
	partsum=0.0;
	j=0;
	rand1=random1()*sumfitness;
	do{
		partsum+=oldpop[j].fitness;
		j++;
	}while((partsum<rand1) && (j<popsize));
	return j-1;
}

int mutation(  int ch)
{
	int mutate;
	mutate=flip(pmutation);
	if(mutate)
	{
		nmutation++;
		if(ch)ch=0;
		else
			ch=1;
	}
	if(ch)
		return 1;
	else 
		return 0;
}

void crossover(   unsigned char *parent1,   unsigned char parent2[],int k5)
{
//	srand( (unsigned)time( NULL ) ); 
	int j;
	if(flip(pcross))
	{
	//	srand( (unsigned)time( NULL ) );
		jcross=rand()%lchrom;
		ncross=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<jcross;j++)
		{
			newpop[k5].chrom[j]=mutation(parent1[j]);
			newpop[k5+1].chrom[j]=mutation(parent2[j]);
		
		}
	}
}

void randomize1()//double* oldrand,  int lchrom,  int& jrand)
{
	int i;
	double jj;
//	randomize();
	srand( (unsigned)time( NULL ) ); 
	for(i=0;i<lchrom;i++)
		
	{jj=rand();
	jj=jj/32767.0;
	oldrand[i]=jj;}
	jrand=0;
}

double random1()
{
	jrand++;
	if(jrand>=lchrom)
	{
		jrand=0;
		randomize1();
	}
	return oldrand[jrand];
}

int flip(double probability)
{
	double ppp;
// 	srand( (unsigned)time( NULL ) ); 
	ppp=rand()/32767.0;
    if(fabs(probability-pcross)<1e-10)
		cross_trace<<"rand: "<<ppp<<"   pcross: "<<pcross<<endl;
	if(ppp<=probability)return 1;
	else return 0;
}
	
 
/* SGA主程序 */
void main(void)
{
	long int gen,k,j;
	double oldmax;
	int oldmaxpp;
/*	file.open("c:\\result.txt",ios::out);
	if(file==NULL)
		return;
	cross_trace.open("c:\\cross-trace.txt",ios::out);
	if(cross_trace==NULL)
		return;*/
	if (!(oldpop=(pp *)malloc(maxpop *sizeof(pp))))
	{printf("memory request failed!\n");exit(0);}
	if (!(newpop=(pp *)malloc(maxpop *sizeof(pp))))
	{printf("memory request failed!\n");exit(0);}
//	if (!(p1=(pp *)malloc(maxpop *sizeof(pp))))
//	{printf("memory request failed!\n");exit(0);}
	for(k=0;k<maxpop;k++) oldpop[k].chrom[0]='\0';
	for(k=0;k<maxpop;k++) newpop[k].chrom[0]='\0';
	gen=0;
	initialize();
//	clrscr();
	p1=newpop;
	newpop=oldpop;
	statistics(newpop);
	report(gen);
	newpop=p1;
//	getch();
	do {
		gen=gen+1;
//		randomize();
		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;
//		getch();
	}while(gen<maxgen);
	file.close();
    cross_trace.close();
	free(oldpop);
	free(newpop);
	exit(0);
}