/************************************************************
*周明,孙树栋.遗传算法原理及应用.国防工业吃出版社.北京,1999*
* *
*附录一 基本遗传算法源程序 *
*************************************************************/
/************************************************************
* Simple Genetic Algrithm *
* Version 1.0 *
* Programmed by Jim Zhou,1994.12. *
************************************************************/
#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 som 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 2st 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[21]; //a string of code representing individual
double value; //object value of this individual
double fitness;
};
/************************************************************
* 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 mian ()
{
generation = 0;
GenerateInitialPopulation ();
EvaluatePopulation ();
while (generation < MaxGeneration)
{
generation++;
GenerateNextPopulation ();
EvaluatePopulation ();
PerformEvolution ();
OutputTextReport ();
}
}
/************************************************************
* Function: Generate the fist population *
* Variable: None. *
************************************************************/
void GenerateInitialPopulation (void)
{
int i,j;
//randomize();
for (i=0;i<PopSize;i++)
{
for(j=0;j<20;j++)
{
//population[i].chrom[j]= (random (10)<5)?'0':'1';
}
population[i].chrom[20] = '\0';
}
}
/************************************************************
* Function: Initialize the fist generation *
* Variable: None. *
************************************************************/
void GenerateNextPopulation (void)
{
SelectionOperator ();
CrossoverOperator ();
MutationOperator ();
}
/************************************************************
* Function: Evaluate population according to certain fomula.*
* Variable: None. *
************************************************************/
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. *
* Variable: None. *
* Note: The returned value may be plus, or minus. *
* For different codding 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);
}
/************************************************************
* Function: To calculate object value. *
* Variable: None. *
* Note: For different problem, 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. *
* Variable: None. *
************************************************************/
void CalculateFitnessValue (void)
{
int i;
double temp;
for (i=0; i<PopSize; i++)
{
if (FunctionMode == MAXIMIZATION) //maximization
{
if ((population[i].value+Cmin)>0.0)
{
temp = Cmin + population[i].value;
}
else
{
temp = 0