gatsp.cpp

游戏开发人工智能技术-AI.Techniques.for.Game.Programming

	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
    //make sure baby1 and baby2 are assigned some cities first!
    baby1 = mum;
    baby2 = dad;
    
		return;
	}

  //initialize the babies with minus values so we can tell which positions
  //have been filled later in the algorithm
  baby1.assign(mum.size(), -1);
  baby2.assign(mum.size(), -1);

  int l = baby2.size();

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

    //next city
    Pos += RandInt(1, mum.size()-Pos);
  }
  
  //now we have chosen some cities it's time to copy the selected cities
  //over into the offspring in the same position.
  for (int pos=0; pos<positions.size(); ++pos)
  {
    //baby1 receives from mum
    baby1[positions[pos]] = mum[positions[pos]];

    //baby2 receives from dad
    baby2[positions[pos]] = dad[positions[pos]];
  }

  //fill in the blanks. First create two position markers so we know
  //whereabouts we are in baby1 and baby2
  int c1 = 0, c2 = 0;

  for (pos=0; pos<mum.size(); ++pos)
  {   
    //advance position marker until we reach a free position
    //in baby2
    while( (baby2[c2] > -1) && (c2 < mum.size()))
    {
      ++c2;
    }
    
    //baby2 gets the next city from mum which is not already
    //present
    if ( (!TestNumber(baby2, mum[pos])) )
    {
      baby2[c2] = mum[pos]; 
    }

    //now do the same for baby1
    while((baby1[c1] > -1) && (c1 < mum.size()))
    {      
      ++c1;
    }
    
    //baby1 gets the next city from dad which is not already
    //present
    if ( (!TestNumber(baby1, dad[pos])) )
    {
      baby1[c1] = dad[pos];
    }     
  }
}
//--------------------- Crossover ----------------------------------------
//
//  simple switch statement to perform crossover based on the selected
//  CrossoverType, type
//------------------------------------------------------------------------
void CgaTSP::Crossover(const vector<int>	&mum, 
							         const vector<int>	&dad, 
							         vector<int>        &baby1, 
							         vector<int>        &baby2,
                       CrossoverType      type)
{
  //perform crossover based on type
  switch(type)
  {
  case OBX:

    CrossoverOBX(mum, dad, baby1, baby2);

    break;

  case PMX:

    CrossoverPMX(mum, dad, baby1, baby2);

    break;

  case PBX:

    CrossoverPBX(mum, dad, baby1, baby2);

    break;


  default: break;

  }//end switch
}

//-----------------------CreateStartingPopulation()------------------------
//
//	clears any existing population, fills a vector with a random population
//	of genomes and resets appropriate member variables
//-------------------------------------------------------------------------
void CgaTSP::CreateStartingPopulation()
{
	//make sure the vector of genomes is empty before we
	//start
	m_vecPopulation.clear();
	
	//create a new population of random genomes
	for (int i=0; i<m_iPopSize; ++i)
	{
		m_vecPopulation.push_back(SGenome(m_iChromoLength));
	}

	//make sure variables are initialised correctly
	m_iGeneration	        = 0;
	m_dShortestRoute      = 9999999;
	m_dBestFitness	      = 0;
	m_dWorstFitness       = 9999999;
	m_dAverageFitness     = 0;
	m_iFittestGenome      = 0;
	m_bStarted			      = false;
  m_dBoltzmannTemp      = NUM_CITIES * 2;

}
//-----------------------------------Run-----------------------------------
//
//	This is the function that initializes a new population and sets the
//  ga running 
//------------------------------------------------------------------------
void CgaTSP::Run(HWND hwnd)
{
	//The first thing we have to do is create a random population
	//of genomes
	CreateStartingPopulation();

	m_bStarted = true;

}
//-------------------------Reset()------------------------------
//
//	resets all the relevant variables ready for a new generation
//--------------------------------------------------------------
void CgaTSP::Reset()
{
	//just make the shortest route some excessively large distance
	m_dShortestRoute	= 999999999;
	m_dLongestRoute		= 0;
	m_dTotalFitness		= 0;
	m_dBestFitness		= 0;
	m_dWorstFitness		= 9999999;
	m_dAverageFitness	= 0;
	m_bSorted			    = false;
  m_dSigma          = 1;
}

//------------------------Epoch-------------------------------
//
//	creates a new population of genomes using the selection,
//	mutation and crossover operators
//------------------------------------------------------------
void CgaTSP::Epoch()
{

	//first we reset variables and calculate the fitness of each genome
	Reset();
	
	CalculatePopulationsFitness();

	//if we have found a solution exit
	if ((m_dShortestRoute <= m_pMap->BestPossibleRoute()))
	{
		m_bStarted = false;
		
		return;
	}	

  //perform the appropriate fitness scaling
  FitnessScaleSwitch();

  //if sigma is zero (either set in sigma scaling or in CalculateBestWorstAv
  //then the population are identical and we should stop the run
  if (m_dSigma == 0)
  {
    m_bStarted = false;

    return;
  }
	
	//create a temporary vector for the new population
	vector<SGenome> vecNewPop;
	
  if (m_bElitism)
  {
	  //Now to add a little elitism we shall add in some copies of the
	  //fittest genomes
	  const int CopiesToAdd = 2;
	  const int NBest		  = 4;
	  
	  //make sure we add an EVEN number or the roulette wheel
	  //sampling will crash
	  if (!(CopiesToAdd * NBest % 2))
	  {
		  GrabNBest(NBest, CopiesToAdd, vecNewPop);
	  }
  }

  //SUS selection selects the entire population all at once so we have to
  //handle the epoch slightly differently if SUS is chosen
  if(m_SelectionType != SUS)
  {
	  //now create the remainder of the population
	  while (vecNewPop.size() != m_iPopSize)
	  {
	  
		  SGenome mum, dad;
    
      //switch on selection method
      switch(m_SelectionType)
      {
      case ROULETTE:
  
        //grab two parents dependent on the selection method
		    mum = RouletteWheelSelection();
		    dad = RouletteWheelSelection();

        break;

      case TOURNAMENT:

        mum = TournamentSelection(NUM_TO_COMPARE);
	      dad = TournamentSelection(NUM_TO_COMPARE);

        break;

      case ALT_TOURNAMENT:
 
        mum = AlternativeTournamentSelection();
	      dad = AlternativeTournamentSelection();

        break;
      }

		  //create 2 children
		  SGenome baby1, baby2;
		  
		  //Breed them
      Crossover(mum.vecCities,
                dad.vecCities,
                baby1.vecCities,
                baby2.vecCities,
                m_CrossoverType);

		  //and mutate them
		  Mutate(baby1.vecCities, m_MutationType);
		  Mutate(baby2.vecCities, m_MutationType);

		  //add them to new population
		  vecNewPop.push_back(baby1);
		  vecNewPop.push_back(baby2);
	  }
  }

  //SUS selection
  else
  {
    //select all the individuals
    vector<SGenome> vecSampledPop;

    SUSSelection(vecSampledPop);

    //step through the newly sampled population and apply crossover
    //and mutation operators
    for (int gen=0; gen<vecSampledPop.size(); gen+=2)
    {
      SGenome baby1, baby2;
      
      Crossover(vecSampledPop[gen].vecCities,
                vecSampledPop[gen+1].vecCities,
                baby1.vecCities,
                baby2.vecCities,
                m_CrossoverType);

      Mutate(baby1.vecCities, m_MutationType);
      Mutate(baby2.vecCities, m_MutationType);

      vecNewPop.push_back(baby1);
      vecNewPop.push_back(baby2);      

    }
   
  }

	//copy into next generation
	m_vecPopulation = vecNewPop;

	//increment generation counter
	++m_iGeneration;
}

//-------------------------------Render-------------------------------
//
//	This function does all the drawing and textual output. Called from
// the winproc when it receives a WM_PAINT msg
//--------------------------------------------------------------------
void CgaTSP::Render(HDC surface, int cx, int cy)const
{

		//draw all the cities
	for (int city_num = 0; city_num < m_pMap->m_vecCityCoOrds.size(); ++city_num)
	{
		int x = (int)m_pMap->m_vecCityCoOrds[city_num].x;
		int y = (int)m_pMap->m_vecCityCoOrds[city_num].y;
		
		Ellipse(surface, x-CITY_SIZE, y+CITY_SIZE, x+CITY_SIZE, y-CITY_SIZE);
	}
	
	//draw the fittest route so far
	vector<int> route = m_vecPopulation[m_iFittestGenome].vecCities;
	
	//only display the routes if we are in a run
	if (m_iGeneration != 0)
	{ 
		MoveToEx(surface, (int)m_pMap->m_vecCityCoOrds[route[0]].x, (int)m_pMap->m_vecCityCoOrds[route[0]].y, NULL);
		
		for (int i=1; i<route.size(); ++i)
		{
			int CityX = (int)m_pMap->m_vecCityCoOrds[route[i]].x;
			int CityY = (int)m_pMap->m_vecCityCoOrds[route[i]].y;
			
			LineTo(surface, CityX, CityY);
			
			//draw the numbers representing the order the cities are visited.
			//No point drawing them after about a 100 cities as the display
			//just becomes confused
			if (NUM_CITIES < 100)
			{
				string CityNumber = itos(i);
			
				TextOut(surface, CityX, CityY, CityNumber.c_str(), CityNumber.size());
			}
		}

		//now draw the line from the last city visited back to the starting point
		LineTo(surface, (int)m_pMap->m_vecCityCoOrds[route[0]].x, (int)m_pMap->m_vecCityCoOrds[route[0]].y);
	}	
	
	//print stats
	string sGen = itos(m_iGeneration);
	sGen = "Generation: " + sGen;
	TextOut(surface, 5, cy - 20, sGen.c_str(), sGen.size());


	if (!m_bStarted)
	{
		string Start = "Press Return to start a new run";

		TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_str(), Start.size());

    if (m_dSigma == 0)
    {
      string s = "Premature Convergence!";

      TextOut(surface, cx-40 - (Start.size() * 3), cy-20, s.c_str(), s.size());
    }
	}

	else

	{
		string Start = "Space to stop";
		
		TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_str(), Start.size());
	}	

 

  //render the current Boltzmann temperature if applicable
  if (m_ScaleType == BOLTZMANN)
  {
    string s = "Boltzmann Temp: " + ftos(m_dBoltzmannTemp);
    TextOut(surface, 400, 5, s.c_str(), s.size());
  }
    
}