sga_1.cpp

以VisualC++6.0控制台实现的遗传算法

// SGA_1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

//Simple Genetic Algorithm   
#include <stdio.h> 

#include <math.h>
#include <iostream>
using   namespace   std; 
#include <cstdlib> 
#include <ctime>

// 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 difference. ) 
#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 d Data Structure 
struct individual // data structure of 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 Global Variables
int generation; // number of generation 
int best_index; // index of best individual 
int worst_index; // index of worst individual
struct individual bestindividual; //best individual of current gentration
struct individual worstindividual; //worst individual of current gentration
struct individual currentbest; //best individual by now 
struct individual population[POPSIZE]; //population

//Declaration of Prototype 
void GeneratellInitialPopulation(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 . 
int main( int argc, char* argv[])
{
	generation = 0;
	GeneratellInitialPopulation();
	EvaluatePopulation();
	while(generation<MaxGeneration)
	{
		generation++;
		GenerateNextPopulation();
		EvaluatePopulation();
		PerformEvolution();
		OutputTextReport();
	}
	return 0;
}

void GeneratellInitialPopulation()
{
	int i,j;
//	randomize( );
	srand((unsigned)time(0)); 
	for (i = 0; i< PopSize; i ++)
	{
	//	for (i = 0; j < CHROMLENGTH; j++)
		for (j = 0; j < CHROMLENGTH; j++)
		{
//			population [ i ] . chrom [ j ]=(random(10)<5)? '0': '1';
			population [ i ] . chrom [ j ]=(rand()%10 <5)? '0': '1';
		}
		population [i].chrom [ CHROMLENGTH]='\0';
	}
}

void GenerateNextPopulation (void) 
{
	SelectionOperator ( ); 
	CrossoverOperator ( ); 
	MutationOperator ();
}

void EvaluatePopulation (void)
{ 
	CalculateObjectValue ( ); // calculate object value 
	CalculateFitnessValue (); // calculate fitness value 
	FindBestAndWorstIndividual(); // find the best and worst individual 
}

long DecodeChromosome (char * string, int point, int length)
{
	int i;
	long decimal=0L;
	char * pointer;
	pointer = string + point;
	for( i = 0 /*, pointer = string + point*/; i < length; i++ /*,pointer++*/)
	{
		decimal += (*pointer- '0' )<< (length-1-i);
		pointer++;
	}
	return (decimal);
}

//this example is dealing with Rosenbrock function.
//it is defined as:
//f(x1,x2)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1)
void CalculateObjectValue()
{
	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); 
	} 
}

void CalculateFitnessValue()
{
	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;
}

void FindBestAndWorstIndividual()
{
	int i;
	double sum=0.0;
	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;
	}
	if(generation==0)
	{
		currentbest=bestindividual;
	}
	else
	{
		if(bestindividual.fitness>currentbest.fitness) currentbest=bestindividual;
	}
}


void PerformEvolution()
{
	if(bestindividual.fitness>currentbest.fitness) currentbest=population[best_index];
	else population[worst_index]=currentbest;
}

void SelectionOperator()
{
	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;
	for(i=0;i<PopSize;i++) cfitness[i]=cfitness[i-1]+cfitness[i];
	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];
}


void CrossoverOperator()
{
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;

	for(i=0;i<PopSize;i++) index[i]=i;
	for(i=0;i<PopSize;i++) 
	{
//		point=random(PopSize-i);
		point=rand()%(PopSize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}

	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; 
			}
		}
	}
}


void MutationOperator()
{
	int i,j;
	double p;
	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';
		}
	}
}

void OutputTextReport()
{
	int i;
	double sum;
	double average;
	sum=0.0;
	for(i=0;i<PopSize;i++) sum+=population[i].value;
	average=sum/PopSize;

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