gplib_breed.cpp

遗传规划算法 智能算法：遗传规划

// *****************
// GPLIB_breed.cpp
// Breeding functions
// Colin Frayn
// December 2006
// *****************

// GPLib v2.0, A Genetic programming Library for C++
// Copyright (C) 2006  Colin Frayn
// 
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#include "GPLib.h"

extern GPLIB_Environment *GPLIB_Env;

// Breed the next generation
void GPLIB_Environment::Breed(void) {
  int n,loc,i,iEntityCount = (int)Entitylist.size();
  IntVector elite;
  float sc;
  GPLIB_Entity e;
  vector<GPLIB_Entity> NextGen;
  int Survivors, Mutants, Warped, NewRandom;

  Survivors = ((iEntityCount * SurvivalFract) / 100); // Number of survivors
  Mutants   = ((iEntityCount * MutantFract) / 100);   // Number of mutants
  Warped    = ((iEntityCount * WarpedFract) / 100);   // Number of strong mutants
  NewRandom = ((iEntityCount * RandomFract) / 100);   // Number of new random individuals

  // Clear the next generation
  NextGen.clear();

  if (bVerbose) fprintf(stdout,"[G] Breeding   ");
  
  // Always ensure that the fittest elite survive
  elite.insert(elite.begin(),EliteCount,-1);
  for (n=0; n<iEntityCount; n++) {
    sc = Entitylist[n].GetScore();
    if (GPLIB_NotANumber(sc)) continue;
    // Try to insert this score in the elite list
    loc = EliteCount-1;
    while (loc>=0) {
      if (elite[loc]>=0 && Entitylist[elite[loc]].GetScore() > sc) break;
      loc--;
    } 
    
    // If we found a position in the elite list then shift down the elites
    // below this position, and insert the new entry.
    if (++loc<EliteCount) {
      for (i=EliteCount-1;i>loc;i--) elite[i] = elite[i-1];
      elite[loc] = n;      
    }
  }

  // Copy over the surviving elite individuals
  for (n=0; n<EliteCount; n++) {  
    if (elite[n] == -1) break;
    NextGen.push_back(Entitylist[elite[n]]);
  }

  // Next select which individuals survive by right.
  for ( ; n<Survivors ; n++) {
    NextGen.push_back(Entitylist[TournamentSelect()]);
    // Print out this entity count
    if (bPrintProgress) PrintProgress(n+1);    
  }
  
  // Fill up the remaining spaces by mutants and crossovers

  // Create mutants
  for ( ; n<Survivors+Mutants; n++) {
    NextGen.push_back(Entitylist[TournamentSelect()]);
    NextGen[n].Mutate();    
    // Print out this entity count
    if (bPrintProgress) PrintProgress(n+1);
  }
  
  // Create strong mutants
  for ( ; n<Survivors+Mutants+Warped; n++) {
    NextGen.push_back(Entitylist[TournamentSelect()]);
    NextGen[n].StrongMutate();    
    // Print out this entity count
    if (bPrintProgress) PrintProgress(n+1);
  }

  // Create new random individuals
  for ( ; n<Survivors+Mutants+Warped+NewRandom; n++) {
    e.GenerateRandomSubtree();
    NextGen.push_back(e);
    // Print out this entity count
    if (bPrintProgress) PrintProgress(n+1);
  }  

  // Finally crossover
  for ( ; n<iEntityCount ; n++) {
    e.GenerateOffspring(&Entitylist[TournamentSelect()],&Entitylist[TournamentSelect()]);    
    NextGen.push_back(e);
    // Print out this entity count
    if (bPrintProgress) PrintProgress(n+1);
  }

  // Now copy over the next generation
  Entitylist.clear();
  for (n=0;n<(int)NextGen.size();n++) Entitylist.push_back(NextGen[n]);
  NextGen.clear();
  elite.clear();

  // OK we've finished
  if (bVerbose) fprintf(stdout,"\n");
}


// Tournament Select one individual
int GPLIB_Environment::TournamentSelect(void) {
  int best=0,t,ind;

  for (t=1;t<TournamentSize;t++) {
    ind = Random((int)Entitylist.size());
    if (GPLIB_NotANumber(Entitylist[ind].GetScore())) continue;
    if (GPLIB_NotANumber(Entitylist[best].GetScore()) || Entitylist[ind].GetScore() > Entitylist[best].GetScore()) {
      best = ind;
    }
  }
  return best;
}