unitsga.cpp

一个求函数极值的遗传算法程序

/***************************************
*      Simple Genetic Algorithm        *
*      韩荣苍 于电子科技大学 2004.12   *
***************************************/
#include   <stdio.h>
#include   <stdlib.h>
#include   <time.h>
/************************************
*    The Definition of Constant     *
************************************/
#define    POPSIZE       500
#define    MAXIMIZATION  1
#define    MINIMIZATION  2
/*****************************************************
*   The Defination 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           
#define    LENGTH2       10
#define    CHROMLENGTH   LENGTH1+LENGTH2
int       FunctionMode=MAXIMIZATION;      //optimization type
int       PopSize=80;                     //群体规模
int       MaxGeneration=200;              //最大进化代数
double    Pc=0.6;                         //交叉概率
double    Pm=0.001;                       //变异概率
/*************************************
*  The Definition of Data Structure  *
*************************************/
struct individual                       //data structure of individual
{
char     chrom[CHROMLENGTH+1];         //个体的编码串
double   value;                        //个体的目标函数值
double   fitness;                      //个体的适应度函数值
};
/***************************************
*   The Definition of Global Varibles  *
***************************************/
int    generation;                      //进化代数    
int    best_index;                      //index best individual
int    worst_index;                     
struct individual bestindividual;       //当前代最优个体
struct individual worstindividual;      //当前代最差个体
struct individual currentbest;          //最终的最优个体
struct individual population[POPSIZE];  //群体
/**************************************
*   Definition 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();
      }
getch();
}
/*********************************************
*    Function:Generate the first population. *
*              Variable:None.                *
*********************************************/
void GenerateInitialPopulation(void)
{
 int i,j;

randomize();
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 the first generation.  *
*                 Variabale:None               *
***********************************************/
void GenerateNextPopulation(void)
{
void CrossoverOperator();
void MutationOperator();
void OutputTextReport();
}
/*****************************************************************
*    Function:Evaluate population according to certain formula.  *
*           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(decimal);
}
/************************************************************
* Function: To calculate object value.                      *
* Variable:None.                                            *
*    Note:For differen 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*x2-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)
      {
       if((population[i].value+Cmin)>0.0)
         {temp=Cmin+population[i].value;}
       else{temp=0.0;}
      }
   else if(FunctionMode==MAXIMIZATION)
           {
           if (population[i].value<Cmax) 
              {temp=Cmax-population[i].value;}
           else{temp=0.0;}
           }
   population[i].fitness=temp;
  }
}
/**********************************************************************
*   Fuction: 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];
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;}
   } 
}
/***********************************************************************
*  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=0;i<PopSize;i++)
   {cfitness[i]=cfitness[i-1]+cfitness[i];}

//selection operation
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];}
}
/**********************************************************************
*  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);
    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;
       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;
           }
      }
    }
}
/****************************************
*  Function:Mutation of hromosome.      *
*  Variable:None.                       *
****************************************/
void mutationOperation(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';
            }
         }
     }
}
/******************************************************
*  Function:Output the result of current population.  *
*  Variable:None.                                     *
******************************************************/
void OutputTextReport(void)
{
int i;
double sum;
double average;

//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");
}