gatsp.cpp

使用遗传算法解决tsp问题,vc++6.0实现

  for (int i=0; i<N; ++i)
  {
    int ThisTry = RandInt(0, m_iPopSize-1);

    if (m_vecPopulation[ThisTry].dFitness > BestFitnessSoFar)
    {
      ChosenOne = ThisTry;

      BestFitnessSoFar = m_vecPopulation[ThisTry].dFitness;
    }
  }

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

//-------------------------- AlternativeTournamentSelection---------------
//
//  variation of tournament selection described in chapter 5 of the book
//------------------------------------------------------------------------
SGenome& CgaTSP::AlternativeTournamentSelection()
{
  //allocate two indexes into the population
  int g1 = RandInt(0, m_vecPopulation.size()-1);
  int g2 = RandInt(0, m_vecPopulation.size()-1);

  //make sure they are different
  while(g1 == g2)
  {
    g2 = RandInt(0, m_vecPopulation.size()-1);
  }

  //grab a random number between 0 and 1
  float Rand = RandFloat();

  //now return the chosen individual based on CTOURNAMENT
  if(Rand < CTOURNAMENT)
  {
    //return the fitter of the two
    if (m_vecPopulation[g1].dFitness > m_vecPopulation[g2].dFitness)
    {
      return m_vecPopulation[g1];
    }
    else
    {
      return m_vecPopulation[g2];
    }
  }

  else
  {
    //return the weaker
    if (m_vecPopulation[g1].dFitness < m_vecPopulation[g2].dFitness)
    {
      return m_vecPopulation[g1];
    }
    else
    {
      return m_vecPopulation[g2];
    }
  }
}

//-----------------------------ChooseSection----------------------------
//
//	given a max span size and a min span size, this will calculate a 
//  random beginning and end point within the span. Used mainly in 
//  mutation and crossover operators
//----------------------------------------------------------------------
void ChooseSection(int       &beg,
                   int       &end,
                   const int max_span,
                   const int min_span)
{
	
	beg = RandInt(0, max_span-min_span);
	
	end = beg;
	
	//find an end
	while (end <= beg)
	{
		end = RandInt(0, max_span);
	}
}
//---------------------------MutateEM-----------------------------
//
//	Mutates the chromosome by choosing two random genes and swapping
//	their position.
//-----------------------------------------------------------------
void CgaTSP::MutateEM(vector<int> &chromo)
{
	//return dependent upon mutation rate
	if (RandFloat() > m_dMutationRate) return;

	//choose first gene
	int pos1 = RandInt(0, chromo.size()-1);

	//choose second
	int pos2 = pos1;

	while (pos1 == pos2)
	{
		pos2 = RandInt(0, chromo.size()-1);
	}

	//swap their positions
	swap(chromo[pos1], chromo[pos2]);
}

//--------------------------MutateIM------------------------------
//
//	Chooses a random gene and inserts displaced back into the
//	chromosome
//-----------------------------------------------------------------
void CgaTSP::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
	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);
}
//------------------------MutateSM--------------------------------
//
//	chooses a random start and point then scrambles the genes 
//	between them
//----------------------------------------------------------------
void CgaTSP::MutateSM(vector<int> &chromo)
{
	//return dependent upon mutation rate
	if (RandFloat() > m_dMutationRate) return;

	//first we choose a section of the chromosome
	const int MinSpanSize = 3;

	//these will hold the beginning and end points of the span
  int beg, end;

	ChooseSection(beg, end, chromo.size()-1, MinSpanSize);

	int span = end - beg;

	//now we just swap randomly chosen genes with the beg/end
	//range a few times to scramble them
	int NumberOfSwapsRqd = span;

	while(--NumberOfSwapsRqd)
	{
		vector<int>::iterator gene1 = chromo.begin();
		vector<int>::iterator gene2 = chromo.begin();

		//choose two loci within the range
		advance(gene1, beg + RandInt(0, span));
		advance(gene2, beg + RandInt(0, span));

		//exchange them
		swap(*gene1, *gene2);
		
	}//repeat
}

//-------------------------MutateDM-------------------------------------
//
//	Select two random points, grab the chunk of chromosome between them 
//	and then insert it back into the chromosome in a random position 
//	displaced from the original.
//----------------------------------------------------------------------
void CgaTSP::MutateDM(vector<int> &chromo)
{
	//return dependent upon mutation rate
	if (RandFloat() > m_dMutationRate) return;

	//first we choose a section of the chromosome
	const int MinSpanSize = 3;
	
	//these will hold the beginning and end points of the span
  int beg, end;
	
	ChooseSection(beg, end, chromo.size()-1, MinSpanSize);

	//setup iterators for our beg/end points
	vector<int>::iterator SectionStart = chromo.begin() + beg;
	vector<int>::iterator SectionEnd   = chromo.begin() + end;

	//hold on to the section we are moving
	vector<int> TheSection;
	TheSection.assign(SectionStart, SectionEnd);

	//erase from current position
	chromo.erase(SectionStart, SectionEnd);

	//move an iterator to a random insertion location
	vector<int>::iterator curPos;
	curPos = chromo.begin() + RandInt(0, chromo.size()-1);

	//re-insert the section
	chromo.insert(curPos, TheSection.begin(), TheSection.end());
	
}

//---------------------------Mutate-----------------------------
//
//	feeds the chromo into the correct mutation function according
//	to its type
//--------------------------------------------------------------
void CgaTSP::Mutate(vector<int> &chromo, MutationType &type)
{
	switch (type)
	{
	case EM:

		MutateEM(chromo);
		
		break;

	case SM:

		MutateSM(chromo);

		break;

	case IM:

		MutateIM(chromo);
		
		break;

  case DM:

		MutateDM(chromo);
		
		break;

	default: break;
	}//end switch
}

//-------------------------CrossoverPMX---------------------------------
//
// crossover operator based on 'partially matched crossover' as 
// defined in the text
//-------------------------------------------------------------------
void CgaTSP::CrossoverPMX(	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;
	}

	//first we choose a section of the chromosome
	int beg = RandInt(0, mum.size()-2);
	
	int end = beg;
	
	//find an end
	while (end <= beg)
	{
		end = RandInt(0, mum.size()-1);
	}

	//now we iterate through the matched pairs of genes from beg
	//to end swapping the places in each child
	vector<int>::iterator posGene1, posGene2;

	for (int pos = beg; pos < end+1; ++pos)
	{
		//these are the genes we want to swap
		int gene1 = mum[pos];
		int gene2 = dad[pos];

		if (gene1 != gene2)
		{
			//find and swap them in baby1
			posGene1 = find(baby1.begin(), baby1.end(), gene1);
			posGene2 = find(baby1.begin(), baby1.end(), gene2);

			swap(*posGene1, *posGene2);

			//and in baby2
			posGene1 = find(baby2.begin(), baby2.end(), gene1);
			posGene2 = find(baby2.begin(), baby2.end(), gene2);
			
			swap(*posGene1, *posGene2);
		}
		
	}//next pair
}	

//-------------------------CrossoverOBX---------------------------------
//
// Order Based operator as described in Chapter 5
//-------------------------------------------------------------------
void CgaTSP::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;
      }
    }
  }    
}

//----------------------- CrossoverPBX -----------------------------------
//
//  Position Based Crossover as described in Chapter 5
//------------------------------------------------------------------------
void CgaTSP::CrossoverPBX(	const vector<int>	&mum, 
							              const vector<int>	&dad, 
							              vector<int>			&baby1, 
							              vector<int>			&baby2)
{	
	//Return dependent on the crossover rate or if the
	//chromosomes are the same.