genotype.cpp

游戏开发人工智能技术 很好的一本书 讲解游戏中的人工智能技术 希望大家喜欢 ps 英文原版

                        CInnovation &innovations,
                        int          NumTrysToFindOldLink)
{
  //just return dependent on mutation rate
  if (RandFloat() > MutationRate) return;
  
  //if a valid link is found into which to insert the new neuron
  //this value is set to true.
  bool bDone = false;

  //this will hold the index into m_vecLinks of the chosen link gene
  int  ChosenLink = 0;

  //first a link is chosen to split. If the genome is small the code makes 
  //sure one of the older links is split to ensure a chaining effect does
  //not occur. Here, if the genome contains less than 5 hidden neurons it
  //is considered to be too small to select a link at random
  const int SizeThreshold = m_iNumInputs + m_iNumOutPuts + 5;
  
  if (m_vecLinks.size() < SizeThreshold)
  {    
    while(NumTrysToFindOldLink--)
    {
      //choose a link with a bias towards the older links in the genome 
      ChosenLink = RandInt(0, NumGenes()-1-(int)sqrt(NumGenes()));

      //make sure the link is enabled and that it is not a recurrent link 
      //or has a bias input
      int FromNeuron = m_vecLinks[ChosenLink].FromNeuron;
    
      if ( (m_vecLinks[ChosenLink].bEnabled)    && 
           (!m_vecLinks[ChosenLink].bRecurrent) &&
           (m_vecNeurons[GetElementPos(FromNeuron)].NeuronType != bias)) 
       {
          bDone = true;

          NumTrysToFindOldLink = 0;
        }
    }

    if (!bDone)
    {
      //failed to find a decent link
      return;
    }
  }

  else
  {
    //the genome is of sufficient size for any link to be acceptable
    while (!bDone)
    {
      ChosenLink = RandInt(0, NumGenes()-1);

      //make sure the link is enabled and that it is not a recurrent link 
      //or has a BIAS input
      int FromNeuron = m_vecLinks[ChosenLink].FromNeuron;
    
      if ( (m_vecLinks[ChosenLink].bEnabled) && 
           (!m_vecLinks[ChosenLink].bRecurrent) &&
           (m_vecNeurons[GetElementPos(FromNeuron)].NeuronType != bias)) 
      {
        bDone = true;
      }
    }
  }
  
  //disable this gene
  m_vecLinks[ChosenLink].bEnabled = false;

  //grab the weight from the gene (we want to use this for the weight of
  //one of the new links so that the split does not disturb anything the 
  //NN may have already learned...
  double OriginalWeight = m_vecLinks[ChosenLink].dWeight;

  //identify the neurons this link connects
  int from =  m_vecLinks[ChosenLink].FromNeuron;
  int to   =  m_vecLinks[ChosenLink].ToNeuron;

  //calculate the depth and width of the new neuron. We can use the depth
  //to see if the link feeds backwards or forwards
  double NewDepth = (m_vecNeurons[GetElementPos(from)].dSplitY + 
                     m_vecNeurons[GetElementPos(to)].dSplitY) /2;

  double NewWidth = (m_vecNeurons[GetElementPos(from)].dSplitX + 
                     m_vecNeurons[GetElementPos(to)].dSplitX) /2;

  //Now to see if this innovation has been created previously by
  //another member of the population
  int id = innovations.CheckInnovation(from,
                                       to,
                                       new_neuron);

  
  
  /*it is possible for NEAT to repeatedly do the following:
  
      1. Find a link. Lets say we choose link 1 to 5
      2. Disable the link,
      3. Add a new neuron and two new links
      4. The link disabled in Step 2 maybe re-enabled when this genome
         is recombined with a genome that has that link enabled.
      5  etc etc

  Therefore, this function must check to see if a neuron ID is already 
  being used. If it is then the function creates a new innovation
  for the neuron. */
  if (id >= 0)
  {
    int NeuronID = innovations.GetNeuronID(id);

    if (AlreadyHaveThisNeuronID(NeuronID))
    {
      id = -1;
    }
  }

  if (id < 0)
  {
    //add the innovation for the new neuron
    int NewNeuronID = innovations.CreateNewInnovation(from,
                                                      to,
                                                      new_neuron,
                                                      hidden,
                                                      NewWidth,
                                                      NewDepth);
    
    //create the new neuron gene and add it.
    m_vecNeurons.push_back(SNeuronGene(hidden,
                                       NewNeuronID,
                                       NewDepth,
                                       NewWidth));
		
    //Two new link innovations are required, one for each of the 
    //new links created when this gene is split.

    //-----------------------------------first link

    //get the next innovation ID
    int idLink1 = innovations.NextNumber();
		
    //create the new innovation
    innovations.CreateNewInnovation(from,
                                    NewNeuronID,
                                    new_link);

    //create the new link gene
    SLinkGene link1(from,
                        NewNeuronID,
                        true,
                        idLink1,
                        1.0);

    m_vecLinks.push_back(link1);

    //-----------------------------------second link

    //get the next innovation ID
    int idLink2 = innovations.NextNumber();
		
    //create the new innovation
    innovations.CreateNewInnovation(NewNeuronID,
                                    to,
                                    new_link);
		
    //create the new gene
    SLinkGene link2(NewNeuronID,
                        to,
                        true,
                        idLink2,
                        OriginalWeight);
    
    m_vecLinks.push_back(link2);
  }

  else
  {
    //this innovation has already been created so grab the relevant neuron 
    //and link info from the innovation database
    int NewNeuronID = innovations.GetNeuronID(id);
		
    //get the innovation IDs for the two new link genes.
    int idLink1 = innovations.CheckInnovation(from, NewNeuronID, new_link);
    int idLink2 = innovations.CheckInnovation(NewNeuronID, to, new_link);

    //this should never happen because the innovations *should* have already 
    //occurred
    if ( (idLink1 < 0) || (idLink2 < 0) )
    {
      MessageBox(NULL, "Error in CGenome::AddNeuron", "Problem!", MB_OK);
			
      return;
    }

    //now we need to create 2 new genes to represent the new links
    SLinkGene link1(from, NewNeuronID, true, idLink1, 1.0);
    SLinkGene link2(NewNeuronID, to, true, idLink2, OriginalWeight);

    m_vecLinks.push_back(link1);
    m_vecLinks.push_back(link2);

    //create the new neuron
    SNeuronGene NewNeuron(hidden, NewNeuronID, NewDepth, NewWidth);
		
    //and add it
    m_vecNeurons.push_back(NewNeuron);		
  }

  return;
}


//--------------------------- AlreadyHaveThisNeuronID ----------------------
// 
// tests to see if the parameter is equal to any existing neuron ID's. 
// Returns true if this is the case.
//------------------------------------------------------------------------
bool CGenome::AlreadyHaveThisNeuronID(const int ID)
{
  for (int n=0; n<m_vecNeurons.size(); ++n)
  {
    if (ID == m_vecNeurons[n].iID)
    {
      return true;
    }
  }

  return false;
}
//------------------------------- MutateWeights---------------------------
//	Iterates through the genes and purturbs the weights given a 
//  probability mut_rate.
//
//	prob_new_mut is the chance that a weight may get replaced by a
//  completely new weight.
//
//	dMaxPertubation is the maximum perturbation to be applied.
//
//	type is the type of random number algorithm we use
//------------------------------------------------------------------------
void CGenome::MutateWeights(double mut_rate,
                            double prob_new_mut,
                            double MaxPertubation)
{
	for (int cGen=0; cGen<m_vecLinks.size(); ++cGen)
	{
		//do we mutate this gene?
		if (RandFloat() < mut_rate)
		{
			//do we change the weight to a completely new weight?
			if (RandFloat() < prob_new_mut)
			{
				//change the weight using the random distribtion defined by 'type'
				m_vecLinks[cGen].dWeight = RandomClamped();
			}

			else
			{
				//perturb the weight
				m_vecLinks[cGen].dWeight += RandomClamped() * MaxPertubation;                                            
			}
		}
	}

	return;
}

void CGenome::MutateActivationResponse(double mut_rate,
                                       double MaxPertubation)
{
  for (int cGen=0; cGen<m_vecNeurons.size(); ++cGen)
  {
    if (RandFloat() < mut_rate)
    {
      m_vecNeurons[cGen].dActivationResponse += RandomClamped() * MaxPertubation;
    }
  }
}
//------------------------- GetCompatibilityScore ------------------------
//
//  this function returns a score based on the compatibility of this
//  genome with the passed genome
//------------------------------------------------------------------------
double CGenome::GetCompatibilityScore(const CGenome &genome)
{
  //travel down the length of each genome counting the number of 
  //disjoint genes, the number of excess genes and the number of
  //matched genes
  double	NumDisjoint = 0;
  double	NumExcess   = 0; 
  double	NumMatched  = 0;

  //this records the summed difference of weights in matched genes
  double	WeightDifference = 0;

  //position holders for each genome. They are incremented as we
  //step down each genomes length.
  int g1 = 0;
  int g2 = 0;

  while ( (g1 < m_vecLinks.size()-1) || (g2 < genome.m_vecLinks.size()-1) )
  {
    //we've reached the end of genome1 but not genome2 so increment
    //the excess score
    if (g1 == m_vecLinks.size()-1)
    {
      ++g2;
      ++NumExcess;

      continue;
    }

    //and vice versa
    if (g2 == genome.m_vecLinks.size()-1)
    {
      ++g1;
      ++NumExcess;
      
      continue;
    }
		
    //get innovation numbers for each gene at this point
    int id1 = m_vecLinks[g1].InnovationID;
    int id2 = genome.m_vecLinks[g2].InnovationID;

    //innovation numbers are identical so increase the matched score
    if (id1 == id2)
    {
      ++g1;
      ++g2;
      ++NumMatched;

      //get the weight difference between these two genes
      WeightDifference += fabs(m_vecLinks[g1].dWeight - genome.m_vecLinks[g2].dWeight);
    }

    //innovation numbers are different so increment the disjoint score
    if (id1 < id2)
    {
      ++NumDisjoint;
      ++g1;
    }
    
    if (id1 > id2)
    {
      ++NumDisjoint;
      ++g2;
    }
		
  }//end while

  //get the length of the longest genome
  int longest = genome.NumGenes();
  
  if (NumGenes() > longest)
  {
    longest = NumGenes();
  }

  //these are multipliers used to tweak the final score.
  const double mDisjoint = 1;
  const double mExcess   = 1;
  const double mMatched  = 0.4;
	
  //finally calculate the scores 
  double score = (mExcess * NumExcess/(double)longest) + 
                 (mDisjoint * NumDisjoint/(double)longest) + 
                 (mMatched * WeightDifference / NumMatched);

    
  return score;
}

//--------------------------- SortGenes ----------------------------------
//
//  does exactly that
//------------------------------------------------------------------------
void CGenome::SortGenes()
{
  sort (m_vecLinks.begin(), m_vecLinks.end());
}