gas.txt

c++的标准遗传算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


/**************************************
      The Definition of Constant
**************************************/
#define POPSIZE            500    //population size
#define MAXIMIZATION       1      //maximization flag
#define MINIMIZATION       2      //minimization flag


/********** The Definition of User Data*****************/
#define Cmax       100     //certain maximal value
#define Cmin         0     //certain minimal value
#define LENGTH1     10     //the chromosome length of 1st variable
#define LENGTH2     10     //the chromosome length of 2nd varialbe
#define CHROMLENGTH LENGTH1+LENGTH2     //total length of chromosome

int FunctionModel=MAXIMIZATION;     //optimization type
int PopSize=80;           //Population size
int MaxGeneration=200;    //max numble of generation
double Pc=0.6;           //Probability of crossover
double Pm=0.0001;       //Probability of mutation 



/****************************************
    The Definition of Data Structure
*****************************************/
struct individual         //data structure of individual
{
	char chrom  [CHROMLENGTH+1];        //a string of code represention individual
		
	double value;       //object value of this individual
	double fitness;     //fitness value of this individual
};


/******************************************
     The Definition of Global Variables
*****************************************/
int generation;       //number of generation
int best_index;       //index of best individual
int worst_index;      //index of worst individual
struct individual       //best individual of current generation
       bestindividual;      
struct individual       //worst individual of current generation
       worstindividual;
struct individual currentbest;     //best individual by now
struct individual population
       [POPSIZE];                 //population


/**************************************************
        Declaration of Prototype
************************************************/
void GenerateInitialPopulation(void);
void GenerateNextPopulation(void);
void EvaluatePopulation(void);
long DecodeChromosome(char*,int,int);
void CalculateObjectValue(void);
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossoverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);


/***********  Main program  **********/

void main(void)
{
	GenerateInitialPopulation();
	EvaluatePopulation();
	while (generation<MaxGeneration)
	{
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();	

	}
} 



/**** Function: Generate the first population***/
void GenerateInitialPopulation(void)
{
	int i,j;
	randomize();
	for(i=0;i<PopSize;i++)
	{
		for(j=0;j<CHROMLENGTH;j++)
		{
			population[i].chrom[j]=(random(10)<5)?'0':'1';
		}
		population[i].chrom[CHROMLENGTH]='\0';
	}
}


/****** Function: Initialize the first generation ******/
void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();

}


/**** Function: Evaluate population according to certain formula. ****/
void EvaluatePopulation(void)
{
	CalculateObjectValue();       //calculate object value
	CalculateFitnessValue();      //calculate fitness value
	FindBestAndWorstIndividual();    //find the best and worst individual
}


/***** Function: To decode a binary chromosome into a decimal integer 
  the returned value may be plus,or minus. For different coding method, the value
  may be changed int "unsigned int"*********/
long DecodeChromosome(char *string,int point, int length)
{
	int i;
	long decimal=0l;
	char *pointer;
	for(i=0,pointer=string+point;i<length;i++,point++)
	{
		decimal+=(*pointer-'0')<<(length-1-i);
	}
	return(decimal);
}



/*****  Function: To calculate object value

NOTE:For different proble,user must change these code.
     This example is dealing with Rosenbrock function.
	 Rosenbrock function is defined as:
	 f(x1,x2)=100*(x1**2-x2)**2+(1-x1)**2
	 Its maximal value is:
	 f(-2.048,-2.048)=3905.926227
*********************************************/
void CalculateObjectValue(void)
{
	int i;
	long temp1,temp2;
	double x1,x2;

// Rosenbrock function
	for(i=0;i<PopSize;i++)
	{
		temp1=DecodeChromosome(population[i].chrom,0,LENGTH1);
		temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2);
		x1=4.096*temp1/1023.0-2.048;
		x2=4.096*temp2/1023.0-2.048;
		population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
	}
}



/*********** Function: To calculate fitness value. *********/
void CalculateFitnessValue(void)
{
	int i;
	double temp;

	for (i=0;i<PopSize;i++)
	{
		if(FunctionModel==MAXIMIZATION)    //maximization
		{
			if((population[i].value+Cmin)>0.0)
			{temp=Cmin+population[i].value;}
			else {temp=0.0;}
		}
		else if(FunctionModel==MINIMIZATION) //minimization
		{
			if(population[i].value<Cmax)
			{temp=Cmax-population[i].value;}
			else {temp=0.0;}	
		}
		population[i].fitness=temp;
	}
}


/****To Find out the best individual so far current genetation. ****/
void FindBestAndWorstIndividual(void)
{
	int i;
	double sum=0.0;

//find out the best and worst individual of this genetion
	bestindividual=population[0];
	worstindividual=population[0];
	for(i=1;i<PopSize;i++)
	{
		if(population[i].fitness>bestindividual.fitness)
		{
			bestindividual=population[i];
		    best_index=i;}
		else if(population[i].fitness<worstindividual.fitness)
		{
			worstindividual=population[i];
			worst_index=i;   
		}
		sum+=population[i].fitness;
	}

//find out the best individual so far
	if(generation==0)    //initialize the best individual
	{
       currentbest=bestindividual;
	}
	else
	{
		if(bestindividual.fitness>currentbest.fitness)
		{currentbest=bestindividual;}
	}
}


/******** Function: To perform evolution operation based on elitise model
                    Elitist model is to replace the worst individual of this
					genetation by the current best one.
*************/
void PerformEvolution(void)
{
	if(bestindividual.fitness>currentbest.fitness)
	{
		currentbest=population[best_index];
	}
	else
	{
		population[worst_index]=currentbest;
	}
}



/******** Function: To reproduce a chromosome bu proprotional selcetion. *********/
void SelectionOperator(void)
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];    //cumulative fitness value
	struct individual newpopulation[POPSIZE];

// caculate relative fitness
	for(i=0;i<PopSize;i++)
	{
		sum+=population[i].fitness;
	}
	for(i=0;i<PopSize;i++)
	{
		cfitness[i]=population[i].fitness/sum;
	}
//calculate fitness
	for(i=1;i<PopSize;i++)
	{
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}

//selection operation
	for(i=0;i<PopSize;i++)
	{
		p=rand()%1000/1000.0;
		index=0;
		while(p>cfitness[index])
		{
			index++;
		}
		newpopulation[i]=population[index];
	}

	for(i=0;i<PopSize;i++)
	{
		population[i]=newpopulation[i];
	}
}



/******* Function: Crossover two chromosome by means of one-point crosssover ********/
void CrossoverOperator(void)
{
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;

//make a pair of individual randomly
	for(i=0;i<PopSize;i++)
	{
		index[i]=i;
	}
	for(i=0;i<PopSize;i++)
	{
		point=random(PopSize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}

//one-point crossover operation
	for(i=0;i<PopSize-1;i+=2)
	{
         p=rand()%1000/1000.0;
		 if(p<Pc)
		 {
			 point=random(CHROMLENGTH-1)+1;
			 for(j=point;j<CHROMLENGTH;j++)
			 {
				 ch=population[index[i]].chrom[j];
				 population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
				 population[index[i+1]].chrom[j]=ch;
			 }
		 }
	}
}


/*********  Function: Mutation of a chromosom ***********/
void MutationOperator(void)
{
	int i,j;
	double p;

//bit mutation
	for(i=0;i<PopSize;i++)
	{
		for(j=0;j<CHROMLENGTH;j++)
		{
			p=rand()%1000/1000.0;
			if(p<Pm)
			{
				population[i].chrom=(population[i].chrom[j]=='0')?'1':'0';
			}
		}
	}
   
}


//********* Function: Output the results of current population.********/
void OutputTextReport(void)
{
	int i;
	double sum;         //temporary sum
	double average;      //average of population object value

//calculate average object value
	sum=0.0;
	for(i=0;i<PopSize;i++)
	{
		sum+=population[i].value;
	}
	average=sum/PopSize;

//print results of this population
	printf("gen=%d,avg=%f,best=%f,",generation,average,currentbest.value);
	for(i=0;i<CHROMLENGTH;i++)
	{
		printf("%c",currentbest.chrom[i]);
	}
	printf("\n");

}