sga.cpp

遗传算法的好代码

#include <string>
#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <math.h>

#include <iomanip.h> 

using namespace std;

#define PCROSSOVER       0.8
#define PMUTATION        0.01
#define POPSIZE          20
#define LENGTH           8
#define MAXGEN	         100
#define RANDOM_NUM       (float)(rand() & RAND_MAX) /(float)RAND_MAX 

#define lbound  2
#define ubound  5 

///////////////////Individual Structure////////////////////////////////// 
typedef struct Individual 
{
    string	bits;  

	float	fitness;
    float   rfitness;
    float   cfitness; 
	Individual(): bits(""), fitness(0.0f){};
};
float TotalFitness=0.0f;
int curBest=0; 
///////////////////////Function Prototype////////////////////////////////////
void    Initialize(Individual* Population); 

string  GenerateIndividuals(int length);

float    BinToDec(string bits);

float   EvaluateFitness(Individual *Pop);

Individual  Roulette(Individual* Population);

void Mutate(Individual *indivi);
//void    Mutate(string &bits);
void Crossover(Individual *dad, Individual *mom);
//void    Crossover(string &dad, string &mom);
void KeepTheBest(Individual *Pop);

void    Elitist(Individual* Population);
void    Report(Individual pop[]);

//////////////////////////Main()//////////////////////////////////////////
int main()
{
    srand((int)time(NULL));
    int curGen=0; 
    
    Individual temp[POPSIZE];//定义一个临时存储空间存储将要放入新群体的个体 
		  
    Individual Population[POPSIZE];
    Initialize(Population);
    
    while(curGen<MAXGEN)
    {  
       EvaluateFitness(Population); 
       
       Individual dad, mom; 
       int i=0; 
       while(i<POPSIZE) 
	   {
	      dad=Roulette(Population); 
          do{
             mom = Roulette(Population);
          }while(dad.bits==mom.bits);
          Crossover(&dad,&mom); 
          Mutate(&dad);
		  Mutate(&mom);
		  temp[i++]=dad;
          temp[i++]=mom; 
       }
       
       //将后代个体放入新群体中 
       for (i=0; i<POPSIZE; i++)
	      Population[i] = temp[i];
       EvaluateFitness(Population); 
       Elitist(Population); 
       Report(Population); 
       KeepTheBest(Population); 
       curGen++; 
    }
    
    cout<<endl;
    cout<<Population[curBest].fitness<<endl; 
	int x; 
	cout<<"please input a number"<<endl; 
	cin>>x; 
	return 0; 
}//main 


//////////////////////////////Function Definition////////////////////////////////// 

//----------------GenerateIndividuals------------------------------------------------- 
string	GenerateIndividuals(int length)
{
	string bits;

	for (int i=0; i<length; i++)
	{
		if (RANDOM_NUM < 0.5f)

			bits += "1";

		else

			bits += "0";
	}
    //cout<<bits<<endl;//调试 
	return bits;
}

//---------------------------------Binary To Decimal--------------------------------------
float BinToDec(string bits)
{
	int val			 = 0;
	int value_to_add = 1;

	for (int i = bits.length(); i > 0; i--)
	{		
		if (bits.at(i-1) == '1')

			val += value_to_add;

		value_to_add *= 2;
	
	}//next bit

	return 	(float)lbound+(ubound-lbound)*val/15.0; //15要通过程序计算得  
}

//-------------------------Initialize Population------------------------------------------ 
void  Initialize(Individual* Population)
{
     //随机生成初始种群  
	 int i; 
	 for (i=0; i<POPSIZE; i++)
	 {
	   Population[i].bits = GenerateIndividuals(LENGTH);
	   Population[i].fitness = 0.0f;
	 }
     return; 
}

//--------------------------Evaluate Fitness------------------------------------------- 
float EvaluateFitness(Individual *Pop)
{
    TotalFitness =0; 
    // 计算个体的适应值 
    for (int i=0; i<POPSIZE; i++)
	    Pop[i].fitness = 12 - BinToDec(Pop[i].bits);
    
    //群体总适应值
    for (int i=0; i<POPSIZE; i++)
        TotalFitness += Pop[i].fitness;    
    
    //计算个体相对适应值 
    if(TotalFitness==0) exit(0);
    else
    for (int i=0; i<POPSIZE; i++)    
        Pop[i].rfitness = Pop[i].fitness/TotalFitness;//需要处理除数为0的情况 
    
    //计算个体累积适应值 
    Pop[0].cfitness = Pop[0].rfitness; 
	for (int i=1;i<POPSIZE;i++)
        Pop[i].cfitness = Pop[i].rfitness + Pop[i-1].cfitness;	 
}


//---------------通过轮盘选择策略从旧群体中获取两个个体 ------------------------
Individual  Roulette(Individual* Population)
{
    for (int i=0; i<POPSIZE; i++)
	{
		if (Population[i].cfitness>RANDOM_NUM) 
			return Population[i];
	}
}

//---------------------------------- Crossover ---------------------------------------
void Crossover(Individual *dad, Individual *mom)
{
  if (RANDOM_NUM < PCROSSOVER)
  {
    //产生一个随机交叉点 
    int crossover = (int) (RANDOM_NUM * LENGTH);

    string t1 = (*dad).bits.substr(0, crossover) + (*mom).bits.substr(crossover, LENGTH);
    string t2 = (*dad).bits.substr(0, crossover) + (*mom).bits.substr(crossover, LENGTH);

    (*dad).bits = t1; (*mom).bits = t2;				  
  }
}

//------------------------------------Mutate---------------------------------------
void Mutate(Individual *indivi)
{
	for (int i=0; i<(*indivi).bits.length(); i++)
	{
		if (RANDOM_NUM < PMUTATION)
		{
			if ((*indivi).bits.at(i) == '1')
				(*indivi).bits.at(i) = '0';
			else
				(*indivi).bits.at(i) = '1';
		}
	}

	return;
}

//-------------------记录下最好的个体（其适应值即为所求的最优值）-------------- 
void KeepTheBest(Individual *Pop)
{
  int i;
  curBest=0;
  for(i=0;i<POPSIZE;i++)
  {
    if(Pop[i].fitness>Pop[POPSIZE].fitness)
    { 
      curBest=i;
      Pop[POPSIZE].fitness=Pop[i].fitness;
    }
    Pop[POPSIZE]=Pop[curBest];
  }
} 

//------------------------------实施精英策略------------------------------------- 
void  Elitist(Individual* Pop)
{
    int i;
    float best,worst;
    int bestIndex,worstIndex;
    best=Pop[0].fitness;
    worst=Pop[0].fitness;
    for (i = 0; i < POPSIZE - 1; ++i)
    {
      if(Pop[i].fitness > Pop[i+1].fitness)
      {      
        if (Pop[i].fitness >= best)
        {
            best = Pop[i].fitness;
            bestIndex = i;
         }
         if (Pop[i+1].fitness <= worst)
         {
            worst = Pop[i+1].fitness;
            worstIndex = i + 1;
         }
       }
       else
       {
          if (Pop[i].fitness <= worst)
          {
              worst = Pop[i].fitness;
              worstIndex = i;
           }
           if (Pop[i+1].fitness >= best)
           {
              best = Pop[i+1].fitness;
              bestIndex = i + 1;
            }
        }
      }

//若新群体的最好个体比前一代的最好个体还好，则新群体的个体放入POPSIZE单元中； 
//否则用前一代的最佳个体置换当前群体的最坏个体
    if (best >= Pop[POPSIZE].fitness)
    {
       Pop[POPSIZE] = Pop[bestIndex];
    }
    else
    {
       Pop[worstIndex] = Pop[POPSIZE];
    } 
}

//-------------------Print Information of Generations------------------------
void Report(Individual pop[])
{
    cout<<"TotalFitness is  "<<TotalFitness<<endl; 
	cout.setf(ios::left,ios::adjustfield);
    cout.fill(' ');
    cout<<setw(11)<<"String";
    cout<<setw(10)<<"Fitness";
    cout<<setw(18)<<"RelativeFitness";
    cout<<setw(20)<<"CumulativeFitness"<<endl; 
    cout.setf(ios::right,ios::adjustfield); 
    for(int i=0;i<POPSIZE;i++)
    {
       cout<<setw(13)<<pop[i].bits;
       cout<<setw(10)<<pop[i].fitness;
       cout<<setw(18)<<pop[i].rfitness;
       cout<<setw(20)<<pop[i].cfitness<<endl; 
    }
    return; 
}