sga.c

基本遗传算法的C语言源程序。（遗传算法的应用范围极其广泛

/************************************************************
*周明，孙树栋.遗传算法原理及应用.国防工业吃出版社.北京，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.0;
      }
    }
  else if (FunctionMode == MINIMIZATION)  //minimization
    {
    if (population[i].value < Cmax)
      {
      temp = Cmax-population[i].value;
      }
    else 
      {
      temp = 0.0;
      }
    }
  population[i].fitness = temp;   
  }
}
/************************************************************
*         Function: To Find out the best individual so      *     
*                   far current generation.                 *                  
*         Variable: None.                                   *                  
************************************************************/
void FindBestAndWorstIndividual (void)
{
int i;
double sum = 0.0;
 
//find out the best and worst individual of this generation 
bestindividual = 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 generation by the current   *     
*            best one.                                      *      
*  Variable: None.                                          *      
************************************************************/
void PerformEvolution (void)
{
if (bestindividual.fitness > currentbest.fitness)
  {
  currentbest = population[best_index];
  }
else
  {
  population[worst_index] = currentbest;
  }
}
/************************************************************
*  Function: To reproduce a chromosome by                   *
*            proportional selection.                        *      
*  Variable: 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++)
  {
  //p=rand () %1000/1000.0;
	p=100;
  index = 0;
  while (p > cfitness[index])
    {
    index++;
    }
  newpopulation[i] = population[index];
  }

}

/************************************************************
*  Function: Crossover two chromosome by means              *     
*            of one-point crossover.                        *      
*  Variable: 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 = random(PopSize-i);
point=0;
  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=100;
 // p=rand () %1000/1000.0;
  if (p<Pc)
    {
   // point = random (20 -1 ) +1;
    for (j = point; j < 20; 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 chromosome.                     *     
*  Variable: None.                                          *      
************************************************************/
void MutationOperator (void)
{
int i,j;
double p;

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

}

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

//caculate 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<20; i++)
  {
  printf ("%c", currentbest.chrom[i]);
  
  }
printf ("\n");
}