ga.cpp

遗传算法的经典程序

/**********************************************************************/
/*            基本遗传算法源代码           SGA.Cpp                    */
/*          河南工业大学计算机系      姬耀锋     2000年5月            */
/**********************************************************************/
#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 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 of 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 generation
struct individual worstindividual;       // worst 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();
}
}
/**********************************************************************/
/*                Function:Generate the first population              */
/*                            Variable:None                           */
/**********************************************************************/
void GenerateInitialPopulation(void)
{
int i,j;
randmize();
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 first generation                */
/*                            Variable:None                           */
/**********************************************************************/
void GenerateNextPopulation(void)
{
SelectionOperator();
CrossoverOperator();
MutationOperator();
}
/**********************************************************************/
/*    Function:Evaluate population according to certain population    */
/*                            Variable:None                           */
/**********************************************************************/
void EvaluatePopulation(void)
{
CalculateObjectValue();          // 计算目标函数值
CalculateFitnessValue();         // 计算适应度函数值
FindBestAndWorstIndividual();    // 发现最优和最差个体
}
/**********************************************************************/
/*   Function:To decode a binary chromosome into a decimal integer    */
/*                            Variable: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 (decimal0;
}
/**********************************************************************/
/*   Function:To calculate object value                               */
/*            Variable:None                                           */
/*   Note:The returned value may be plus,or minus.For different       */
/*   coding method,this value may be changed into"unsigned int"       */
/**********************************************************************/