genalg.cpp

与本人上次上传的类别一样

// GenAlg.cpp: implementation of the CGenAlg class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "GA_TSP.h"
#include "GenAlg.h"
#include <math.h>
#include "ExternFile.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//returns a random integer between x and y
inline int	  RandInt(int x,int y) {return rand()%(y-x+1)+x;}

//returns a random float between zero and 1
inline double RandFloat()		   {return (rand())/(RAND_MAX+1.0);}

//returns a random float in the range -1 < n < 1
inline double RandomClamped()	   {return RandFloat() - RandFloat();}

bool operator<(CGenome& lhs, CGenome& rhs)
{
	return (lhs.dFitness < rhs.dFitness);
}


//类的构造函数
CGenAlg::CGenAlg()				 
{
}


void CGenAlg::init(int popsize, double MutRate, double CrossRate, int GenLenght)
{
	m_iPopSize = popsize;
	m_dMutationRate = MutRate;
	m_dCrossoverRate = CrossRate;
	m_iChromoLength = GenLenght;
	m_dTotalFitness = 0;
	m_cGeneration = 0;
	m_iFittestGenome = 0;
	m_dBestFitness = 0;
	m_dWorstFitness = 99999999;
	m_dAverageFitness = 0;
	//清空种群容器，以初始化
	m_vecPop.clear();
	for (int i=0; i<m_iPopSize; i++)
	{	
		//类的构造函数已经把适应性评分初始化为0
		m_vecPop.push_back(CGenome(CreateNewGenome(),0));
	}
}

vector <int> CGenAlg::CreateNewGenome()
{
	//srand( (unsigned)time( NULL ) );

	vector <int> NewGenome;
	vector <int> TempGenome;
	for(int i = 0;i < m_iChromoLength;i++)
	{
		TempGenome.push_back(i);
	}
	for(i = 0;i < m_iChromoLength;i++)
	{
		//create an iterator for us to work with
		vector<int>::iterator curPos;
		
		//choose a gene to move
		curPos = TempGenome.begin() + RandInt(0, TempGenome.size()-1);
		
		NewGenome.push_back(*curPos);

		//remove from the chromosome
		TempGenome.erase(curPos);
	}
	return NewGenome;
}

//基因突变函数
void CGenAlg::Mutate(vector<double> &chromo)
{
	//遵循预定的突变概率,对基因进行突变
	for (int i=0; i<chromo.size(); ++i)
	{
		//如果发生突变的话
		if (RandFloat() < m_dMutationRate)
		{
			//使该权值增加或者减少一个很小的数值
//			chromo[i] += (RandomClamped() * g_dMaxPerturbation);

		}
	}
}

//--------------------------MutateIM------------------------------
//
//	Chooses a random gene and inserts displaced back into the
//	chromosome
//-----------------------------------------------------------------
void CGenAlg::MutateIM(vector<int> &chromo)
{
	//return dependent upon mutation rate
	if (RandFloat() > m_dMutationRate) return;

	//create an iterator for us to work with
	vector<int>::iterator curPos;

	//choose a gene to move
	int x = chromo.size();
	curPos = chromo.begin() + RandInt(0, chromo.size()-1);

	//keep a note of the genes value
	int CityNumber = *curPos;

	//remove from the chromosome
	chromo.erase(curPos);

	//move the iterator to the insertion location
	curPos = chromo.begin() + RandInt(0, chromo.size()-1);

	chromo.insert(curPos, CityNumber);
}


CGenome CGenAlg::GetChromoRoulette()
{
	//这个函数需要排序
	if (!m_ifSorted)
	{
		sort(m_vecPop.begin(), m_vecPop.end());

		m_ifSorted = 1;
	}

	//产生一个0到人口总适应性评分的随机数.
	int i = (int)((RandFloat() * 0.8) * m_iPopSize);

	//这个将承载转盘所指向的那个基因.
	CGenome TheChosenOne = m_vecPop[i];

	return TheChosenOne;
}

//---------------------------- TournamentSelection -----------------
//
//  performs standard tournament selection given a number of genomes to
//  sample from each try.
//------------------------------------------------------------------------
CGenome CGenAlg::TournamentSelection(int N)
{
  double BestFitnessSoFar = 0;
  
  int ChosenOne = 0;

  //Select N members from the population at random testing against 
  //the best found so far
  for (int i=0; i<N; ++i)
  {
    int ThisTry = RandInt(0, m_iPopSize-1);

    if (m_vecPop[ThisTry].dFitness < BestFitnessSoFar)
    {
      ChosenOne = ThisTry;

      BestFitnessSoFar = m_vecPop[ThisTry].dFitness;
    }
  }

  //return the champion
  return m_vecPop[ChosenOne];
}

/*
//轮盘赌函数
CGenome CGenAlg::GetChromoRoulette()
{
	//产生一个0到人口总适应性评分总和之间的随机数.
	//中m_dTotalFitness记录了整个种群的适应性分数总和)
	double Slice = (RandFloat()) * m_dTotalFitness;

	//这个基因将承载转盘所选出来的那个个体.
	CGenome TheChosenOne;
	
	//累计适应性分数的和.
	double FitnessSoFar = 0;

	for (int i=0; i<m_iPopSize; ++i)
	{
		FitnessSoFar += m_vecPop[i].dFitness;
		
		//防止负数太多
		TheChosenOne = m_vecPop[0];

		//如果累计分数大于随机数,就选择此时的基因.
		if (FitnessSoFar >= Slice)
		{
			TheChosenOne = m_vecPop[i];
			break;
		}
	}
	//返回转盘选出来的个体基因
	return TheChosenOne;
}
*/

void CGenAlg::Crossover(const vector<double> &mum,
                        const vector<double> &dad,
                        vector<double>       &baby1,
                        vector<double>       &baby2)
{
	//当交叉没有发生或者父母基因组是同一条的时候,只要以父方的基因作为后代就行了
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
		baby1 = mum;
		baby2 = dad;

		return;
	}
	
	//确定交叉的长度
	int cp = RandInt(0, m_iChromoLength - 1);

	//产生子代
	for (int i=0; i<cp; ++i)
	{
		baby1.push_back(mum[i]);
		baby2.push_back(dad[i]);
	}

	for (i=cp; i<mum.size(); ++i)
	{
		baby1.push_back(dad[i]);
		baby2.push_back(mum[i]);
	}
	
	return;
}
/*
//-------------------------CrossoverOBX---------------------------------
//
// Order Based operator as described in Chapter 5
//-------------------------------------------------------------------
void CGenAlg::CrossoverOBX(	const vector<int>	&mum, 
							              const vector<int>	&dad, 
							              vector<int>			&baby1, 
							              vector<int>			&baby2)
{
  baby1 = mum;
	baby2 = dad;
	
	//just return dependent on the crossover rate or if the
	//chromosomes are the same.
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
		return;
	}
 
  //holds the chosen cities
  vector<int> tempCities;

  //holds the positions of the chosen cities
  vector<int> positions;

  //first city position
  int Pos = RandInt(0, mum.size()-2);

  //keep adding random cities until we can add no more
  //record the positions as we go
  while (Pos < mum.size())
  {
    positions.push_back(Pos);

    tempCities.push_back(mum[Pos]);

    //next city
    Pos += RandInt(1, mum.size()-Pos);
  }

  //so now we have n amount of cities from mum in the tempCities
  //vector we can impose their order in dad.
  int cPos = 0;

  for (int cit=0; cit<baby2.size(); ++cit)
  {
    for (int i=0; i<tempCities.size(); ++i)
    {
      if (baby2[cit]==tempCities[i])
      {
         baby2[cit] = tempCities[cPos];

         ++cPos;

         break;
      }
    }
  }

   //now vice versa
  tempCities.clear();
  cPos = 0;

  //first grab the cities from the same positions in dad
  for(int i=0; i<positions.size(); ++i)
  {
    tempCities.push_back(dad[positions[i]]);
  }

  //and impose their order in mum
  for (cit=0; cit<baby1.size(); ++cit)
  {
    for (int i=0; i<tempCities.size(); ++i)
    {
      if (baby1[cit]==tempCities[i])
      {
         baby1[cit] = tempCities[cPos];

         ++cPos;

         break;
      }
    }
  }    
}
*/

//-------------------------CrossoverOBX---------------------------------
//
// Order Based operator as described in Chapter 5
//-------------------------------------------------------------------
void CGenAlg::CrossoverOBX(	const vector<int>	&mum, 
							              const vector<int>	&dad, 
							              vector<int>			&baby1, 
							              vector<int>			&baby2)
{	
	baby1 = mum;
	baby2 = dad;

	//just return dependent on the crossover rate or if the
	//chromosomes are the same.
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
		return;
	}

/*