samplega.cpp

VC++编写的简单遗传算法

/******************************************************************
**               Sample Genetic Algorithm                        **
**                     Version   0.1                             **
******************************************************************/

#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           **
**(For different problem,there are some different**
**************************************************/
#define Cmax             100               // certain maximal value
#define Cmin             0                 // certain minimum value
#define LENGTH1          10                // the chromosome length of 1st variable
#define LENGTH2          10                // the chromosome length of 2nd variable 
#define CHROMLENGTH      LENGTH1+LENGTH2   // total length of chromosome
int     FunctionMode = MAXIMIZATION;       // optimization type
int     PopSize = 80;                      // population   size 
int     MaxGeneration = 200;               // max. number of generation
double  Pc = 0.6;                          // probability of crossover
double  Pm = 0.001;                        // probability of mutation

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

/************************************************
**     The Definition of Globle Variables      **
************************************************/
int generation;                         // number of generation
int best_index;                         // index of best individual
int worst_index;                        // index of wrost individual
struct individual  bestindividual;      // best individual of current generation
struct individual  worstindividual;     // wrost individual of current generation
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)
{
	generation=0;
	GenerateInitialPopulation();
	EvaluatePopulation();
	while (generation < MaxGeneration)
	{
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();
	}
}

/************************************************
**   Functino: Generate the first population   **
**            Variables: None                  **
************************************************/
void GenerateInitialPopulation(void)
{
	int i, j;

	//randomize();
	for (i=0; i<PopSize; i++)
	{
		for (j=0; j<CHROMLENGTH; j++)
			population[i].chrom[j]=(rand()%10<5)?'0':'1';
	}
	population[i].chrom[CHROMLENGTH]='\0';
}

/************************************************
**   Functino: Initial the first generation    **
**            Variables: None                  **
************************************************/
void GenerateNextPopulation(void)
{
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}

/*****************************************************************
** Functino: Evaluate population according to certain formula   **
**                        Variables: None                       **
*****************************************************************/
void EvaluatePopulation(void)
{
	CalculateObjectValue();
	CalculateFitnessValue();
	FindBestAndWorstIndividual();
}

/************************************************
**   Functino: To decode a binary chromosome   **
**             into a decimal integer          **
**   Variables: None                           **
**   Note: The returned value may be plus, or  **
**         minus. For different coding method, **
**         this value may be changed into      **
**             "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++, pointer++)
	{
		decimal += (*pointer-'0')<<(length-1-i);
	}
	return (decimal);
}

/************************************************
**   Functino: To calculate object value       **
**   Variables: None                           **
**   Note: For different problem, user must    **
**         change these code. This example is  **
**         dealing with Rosenbrock function.   **
**         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);
	}
}

/************************************************
**   Functino: To calculate the fitness value  **
**            Variables: None                  **
************************************************/
void CalculateFitnessValue(void)
{
	int i;
	double temp;

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

/************************************************
**   Functino: To find out the best individual **
**             so far current generation.      **
**   Variables: None                           **
************************************************/
void FindBestAndWorstIndividual(void)
{
	int i;
	double sum=0.0;

	// find out the best and wrost individual of this generation
	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;
	}
}

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

/************************************************
**   Functino: To reproduce a chromosome by    **
**             proportional selection.         **
**   Variables: None                           **
************************************************/
void SelectionOperator(void)
{
	int i, index;
	double p, sum=0.0;
	double cfitness[POPSIZE]; // cumulative fitness value
	struct individual newpopulation[POPSIZE];

	// calculate 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 cumulative fitness
	for (i=1; i<PopSize; i++)
		cfitness[i] = cfitness[i-1]+cfitness[i];

	// selection operation
	for (i=0; i<PopSize; i++)
	{
		/* Seed the random-number generator with current time so that
		 * the numbers will be different every time we run.
		*/
		//srand( (unsigned)time(NULL) );
		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];
}

/************************************************
**   Functino: Crossover two chromosome by     **
**            means of one-point crossover     **
**   Variables: None                           **
************************************************/
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 = rand()%(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;
			point = rand()%(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;
			}
		}
	}
}

/************************************************
**   Functino: Mutation of a chromosome.       **
**   Variables: None                           **
************************************************/
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[j]=(population[i].chrom[j]=='0')?'1':'0';
		}
	}
}

/************************************************
**   Functino: Output the results of current   **
**             population.                     **
**   Variables: None                           **
************************************************/
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);
	printf("chromosome=");
	for (i=0; i<CHROMLENGTH; i++)
		printf("%c", currentbest.chrom[i]);
	printf("\n");
}