cga.cpp

演化神经网络拓扑结构编写的扫雷机器人程序

  //iterate through each genome and speciate
  for (int gen=0; gen<m_vecGenomes.size(); ++gen)
  {
    //calculate its compatibility score with each species leader. If
    //compatible add to species. If not, create a new species
    for (int spc=0; spc<m_vecSpecies.size(); ++spc)
    {
      double compatibility = m_vecGenomes[gen].GetCompatibilityScore(m_vecSpecies[spc].Leader());

      //if this individual is similar to this species add to species
      if (compatibility <= CParams::dCompatibilityThreshold)
      {
        m_vecSpecies[spc].AddMember(m_vecGenomes[gen]);

        //let the genome know which species it's in
        m_vecGenomes[gen].SetSpecies(m_vecSpecies[spc].ID());

        bAdded = true;

        break;
      }
    }
    
    if (!bAdded)
    {
      //we have not found a compatible species so let's create a new one
      m_vecSpecies.push_back(CSpecies(m_vecGenomes[gen], m_iNextSpeciesID++));
    }

    bAdded = false;
  }

  //now all the genomes have been assigned a species the fitness scores 
  //need to be adjusted to take into account sharing and species age.
  AdjustSpeciesFitnesses();
  
  //calculate new adjusted total & average fitness for the population
  for (gen=0; gen<m_vecGenomes.size(); ++gen)
  {   
     m_dTotFitAdj += m_vecGenomes[gen].GetAdjFitness();
  }

  m_dAvFitAdj = m_dTotFitAdj/m_vecGenomes.size();

  //calculate how many offspring each member of the population
  //should spawn
  for (gen=0; gen<m_vecGenomes.size(); ++gen)
  {   
     double ToSpawn = m_vecGenomes[gen].GetAdjFitness() / m_dAvFitAdj;

     m_vecGenomes[gen].SetAmountToSpawn(ToSpawn);
  }

  //iterate through all the species and calculate how many offspring
  //each species should spawn
  for (int spc=0; spc<m_vecSpecies.size(); ++spc)
  {
    m_vecSpecies[spc].CalculateSpawnAmount();
  }
}


//--------------------------- TournamentSelection ------------------------
//
//------------------------------------------------------------------------
CGenome Cga::TournamentSelection(const int NumComparisons)
{
   double BestFitnessSoFar = 0;
  
   int ChosenOne = 0;

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

     if (m_vecGenomes[ThisTry].Fitness() > BestFitnessSoFar)
     {
       ChosenOne = ThisTry;

       BestFitnessSoFar = m_vecGenomes[ThisTry].Fitness();
     }
   }

   //return the champion
   return m_vecGenomes[ChosenOne];
}
                                 
//-----------------------------------Crossover----------------------------
//	
//------------------------------------------------------------------------
CGenome Cga::Crossover(CGenome& mum, CGenome& dad)
{

  //helps make the code clearer
  enum parent_type{MUM, DAD,};
  
  //first, calculate the genome we will using the disjoint/excess
  //genes from. This is the fittest genome.
  parent_type best;

  //if they are of equal fitness use the shorter (because we want to keep
  //the networks as small as possible)
  if (mum.Fitness() == dad.Fitness())
  {
    //if they are of equal fitness and length just choose one at
    //random
    if (mum.NumGenes() == dad.NumGenes())
    {
      best = (parent_type)RandInt(0, 1);
    }

    else
    {
      if (mum.NumGenes() < dad.NumGenes())
      {
        best = MUM;
      }
		  
      else
      {
        best = DAD;
      }
    }
  }

  else 
  {
    if (mum.Fitness() > dad.Fitness())
    {
      best = MUM;
    }

    else
    {
      best = DAD;
    }
  }

  //these vectors will hold the offspring's nodes and genes
  vector<SNeuronGene>  BabyNeurons;
  vector<SLinkGene>    BabyGenes;

  //temporary vector to store all added node IDs
  vector<int> vecNeurons;

  //create iterators so we can step through each parents genes and set
  //them to the first gene of each parent
  vector<SLinkGene>::iterator curMum = mum.StartOfGenes();
  vector<SLinkGene>::iterator curDad = dad.StartOfGenes();

  //this will hold a copy of the gene we wish to add at each step
  SLinkGene SelectedGene;

  //step through each parents genes until we reach the end of both
  while (!((curMum == mum.EndOfGenes()) && (curDad == dad.EndOfGenes())))
  {
	
    //the end of mum's genes have been reached
    if ((curMum == mum.EndOfGenes())&&(curDad != dad.EndOfGenes()))
    {
      //if dad is fittest
      if (best == DAD)
      {
        //add dads genes
        SelectedGene = *curDad;
      }

      //move onto dad's next gene
      ++curDad;
    }

    //the end of dads's genes have been reached
    else if ( (curDad == dad.EndOfGenes()) && (curMum != mum.EndOfGenes()))
    {
      //if mum is fittest
      if (best == MUM)
      {
        //add mums genes
        SelectedGene = *curMum;
      }
			
      //move onto mum's next gene
      ++curMum;
    }

    //if mums innovation number is less than dads
    else if (curMum->InnovationID < curDad->InnovationID)
    {
      //if mum is fittest add gene
      if (best == MUM)
      {
        SelectedGene = *curMum;
      }

      //move onto mum's next gene
      ++curMum;
    }

    //if dads innovation number is less than mums
    else if (curDad->InnovationID < curMum->InnovationID)
    {
      //if dad is fittest add gene
      if (best = DAD)
      {
        SelectedGene = *curDad;
      }

      //move onto dad's next gene
      ++curDad;
    }

    //if innovation numbers are the same
    else if (curDad->InnovationID == curMum->InnovationID)
    {
      //grab a gene from either parent
      if (RandFloat() < 0.5f)
      {
        SelectedGene = *curMum;
      }

      else
      {
        SelectedGene = *curDad;
      }

      //move onto next gene of each parent
      ++curMum;
      ++curDad;
    }
	
    //add the selected gene if not already added
    if (BabyGenes.size() == 0)
    {
      BabyGenes.push_back(SelectedGene);
    }

    else
    {
      if (BabyGenes[BabyGenes.size()-1].InnovationID !=
          SelectedGene.InnovationID)
      {
        BabyGenes.push_back(SelectedGene);
      }
    }   

    //Check if we already have the nodes referred to in SelectedGene.
    //If not, they need to be added.		
    AddNeuronID(SelectedGene.FromNeuron, vecNeurons);
    AddNeuronID(SelectedGene.ToNeuron, vecNeurons);
		
  }//end while

  //now create the required nodes. First sort them into order
  sort(vecNeurons.begin(), vecNeurons.end());
  
  for (int i=0; i<vecNeurons.size(); i++)
  {
    BabyNeurons.push_back(m_pInnovation->CreateNeuronFromID(vecNeurons[i]));
  }

  //finally, create the genome
  CGenome babyGenome(m_iNextGenomeID++,
                     BabyNeurons,
                     BabyGenes,
                     mum.NumInputs(),
                     mum.NumOutputs());

  return babyGenome;
}


//--------------------------- ResetAndKill -------------------------------
//
//  This function resets some values ready for the next epoch, kills off
//  all the phenotypes and any poorly performing species.
//------------------------------------------------------------------------
void Cga::ResetAndKill()
{
  m_dTotFitAdj = 0;
  m_dAvFitAdj  = 0;

  //purge the species
  vector<CSpecies>::iterator curSp = m_vecSpecies.begin();

  while (curSp != m_vecSpecies.end())
  {
    curSp->Purge();

    //kill off species if not improving and if not the species which contains 
    //the best genome found so far
    if ( (curSp->GensNoImprovement() > CParams::iNumGensAllowedNoImprovement) &&
         (curSp->BestFitness() < m_dBestEverFitness) )
    {
     curSp = m_vecSpecies.erase(curSp);
     --curSp;
    }

    ++curSp;
  }

  //we can also delete the phenotypes
  for (int gen=0; gen<m_vecGenomes.size(); ++gen)
  {
    m_vecGenomes[gen].DeletePhenotype();
  }
}

//------------------------------- Split ----------------------------------
//
//  this function is used to create a lookup table that is used to
//  calculate the depth of the network. 
//------------------------------------------------------------------------
vector<SplitDepth> Cga::Split(double low, double high, int depth)
{
  static vector<SplitDepth> vecSplits;

  double span = high-low;

  vecSplits.push_back(SplitDepth(low + span/2, depth+1));

  if (depth > 6)
  {
    return vecSplits;
  }

  else
  {
    Split(low, low+span/2, depth+1);
    Split(low+span/2, high, depth+1);

    return vecSplits;
  }
}

//--------------------------- RenderSpeciesInfo --------------------------
//
//  does what it says on the tin 
//------------------------------------------------------------------------
void Cga::RenderSpeciesInfo(HDC &surface, RECT db)
{
  if (m_vecSpecies.size() < 1) return;
  
  int numColours = 255/m_vecSpecies.size();

  double SlicePerSweeper = (double)(db.right-db.left)/(double)(CParams::iNumSweepers-1);

  double left = db.left;

  //now draw a different colored rectangle for each species
  for (int spc=0; spc<m_vecSpecies.size(); ++spc)
  {

     //choose a brush to draw with
     HBRUSH PieBrush = CreateSolidBrush(RGB(numColours*spc, 255, 255 - numColours*spc));

     HBRUSH OldBrush = (HBRUSH)SelectObject(surface, PieBrush);
     
     if (spc == m_vecSpecies.size()-1)
     {
       Rectangle(surface, 
                  left,
                  db.top,
                  db.right,
                  db.bottom);
     }

     else
     {
       Rectangle(surface, 
                  left,
                  db.top,
                  left+SlicePerSweeper*m_vecSpecies[spc].NumMembers(),
                  db.bottom);
     }

     left += SlicePerSweeper * m_vecSpecies[spc].NumMembers();

     SelectObject(surface, OldBrush);
     DeleteObject(PieBrush);

     //display best performing species stats in the same color as displayed
     //in the distribution bar
     if ( m_vecSpecies[spc].BestFitness() == m_dBestEverFitness)
     {
       string s = "Best Species ID: " + itos(m_vecSpecies[spc].ID());
       TextOut(surface, 5, db.top - 80, s.c_str(), s.size());
       
       s = "Species Age: " + itos(m_vecSpecies[spc].Age());          
       TextOut(surface, 5, db.top - 60, s.c_str(), s.size());

       s = "Gens no improvement: " + itos(m_vecSpecies[spc].GensNoImprovement());
       TextOut(surface, 5, db.top - 40, s.c_str(), s.size());
     }
  }
  
  string s = "Species Distribution Bar";
	TextOut(surface, 5, db.top - 20, s.c_str(), s.size());
}