crossoverop.cpp

非常好的进化算法EC 实现平台 可以实现多种算法 GA GP

/*
 *  Open BEAGLE
 *  Copyright (C) 2001-2005 by Christian Gagne and Marc Parizeau
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  Contact:
 *  Laboratoire de Vision et Systemes Numeriques
 *  Departement de genie electrique et de genie informatique
 *  Universite Laval, Quebec, Canada, G1K 7P4
 *  http://vision.gel.ulaval.ca
 *
 */

/*!
 *  \file   beagle/GP/src/CrossoverOp.cpp
 *  \brief  Source code of class GP::CrossoverOp.
 *  \author Christian Gagne
 *  \author Marc Parizeau
 *  $Revision: 1.12 $
 *  $Date: 2005/10/04 16:25:10 $
 */

#include "beagle/GP.hpp"

#include <algorithm>
#include <string>

using namespace Beagle;


/*!
 *  \brief Construct a GP crossover operator.
 *  \param inMatingPbName Individual mating probability parameter name used in register.
 *  \param inDistribPbName Distribution probability parameter name used in register.
 *  \param inName Name of the operator.
 */
GP::CrossoverOp::CrossoverOp(Beagle::string inMatingPbName,
                             Beagle::string inDistribPbName,
                             Beagle::string inName) :
  Beagle::CrossoverOp(inMatingPbName, inName),
  mDistribPbName(inDistribPbName)
{ }


/*!
 *  \brief Initialize the GP crossover operator.
 *  \param ioSystem System of the evolution.
 */
void GP::CrossoverOp::initialize(Beagle::System& ioSystem)
{
  Beagle_StackTraceBeginM();
  Beagle::CrossoverOp::initialize(ioSystem);
  if(ioSystem.getRegister().isRegistered(mMatingProbaName)) {
    ioSystem.getRegister().deleteEntry(mMatingProbaName);
  }

  if(ioSystem.getRegister().isRegistered(mMatingProbaName)) {
    mMatingProba = castHandleT<Float>(ioSystem.getRegister()[mMatingProbaName]);
  } else {
    mMatingProba = new Float(float(0.9));
    Register::Description lDescription(
      "Individual crossover probability",
      "Float",
      "0.9",
      "Individual crossover probability at each generation."
    );
    ioSystem.getRegister().addEntry(mMatingProbaName, mMatingProba, lDescription);
  }

  if(ioSystem.getRegister().isRegistered(mDistribPbName)) {
    mDistributionProba = castHandleT<Float>(ioSystem.getRegister()[mDistribPbName]);
  } else {
    mDistributionProba = new Float(float(0.9));
    string lLongDescrip = "Probability that a crossover point is a branch ";
    lLongDescrip += "(node with sub-trees). Value of 1.0 means that all crossover points are ";
    lLongDescrip += "branches, and value of 0.0 means that all crossover points are leaves.";
    Register::Description lDescription(
      "Crossover distribution prob.",
      "Float",
      "0.9",
      lLongDescrip
    );
    ioSystem.getRegister().addEntry(mDistribPbName, mDistributionProba, lDescription);
  }

  if(ioSystem.getRegister().isRegistered("gp.tree.maxdepth")) {
    mMaxTreeDepth = castHandleT<UInt>(ioSystem.getRegister()["gp.tree.maxdepth"]);
  } else {
    mMaxTreeDepth = new UInt(17);
    Register::Description lDescription(
      "Maximum tree depth",
      "UInt",
      "17",
      "Maximum allowed depth for the trees."
    );
    ioSystem.getRegister().addEntry("gp.tree.maxdepth", mMaxTreeDepth, lDescription);
  }

  if(ioSystem.getRegister().isRegistered("gp.try")) {
    mNumberAttempts = castHandleT<UInt>(ioSystem.getRegister()["gp.try"]);
  } else {
    mNumberAttempts = new UInt(2);
    string lLongDescrip = "Maximum number of attempts to modify a GP tree in a genetic ";
    lLongDescrip += "operation. As there is topological constraints on GP trees (i.e. tree ";
    lLongDescrip += "depth limit), it is often necessary to try a genetic operation several times.";
    Register::Description lDescription(
      "Max number of attempts",
      "UInt",
      "2",
      lLongDescrip
    );
    ioSystem.getRegister().addEntry("gp.try", mNumberAttempts, lDescription);
  }
  Beagle_StackTraceEndM("void GP::CrossoverOp::initialize(Beagle::System& ioSystem)");
}


/*!
 *  \brief Mate two GP individuals for a crossover.
 *  \param ioIndiv1   First individual to mate.
 *  \param ioContext1 Evolutionary context of the first individual.
 *  \param ioIndiv2   Second individual to mate.
 *  \param ioContext2 Evolutionary context of the second individual.
 *  \return True if the individuals are effectively mated, false if not.
 */
bool GP::CrossoverOp::mate(Beagle::Individual& ioIndiv1, Beagle::Context& ioContext1,
                           Beagle::Individual& ioIndiv2, Beagle::Context& ioContext2)
{
  Beagle_StackTraceBeginM();
  // Initial parameters checks
  Beagle_AssertM(ioIndiv1.size() > 0);
  Beagle_AssertM(ioIndiv1.size() == ioIndiv2.size());
  Beagle_ValidateParameterM(mNumberAttempts->getWrappedValue()>0,"gp.try",">0");

  // Cast method arguments.
  GP::Individual& lIndiv1   = castObjectT<GP::Individual&>(ioIndiv1);
  GP::Individual& lIndiv2   = castObjectT<GP::Individual&>(ioIndiv2);
  GP::Context&    lContext1 = castObjectT<GP::Context&>(ioContext1);
  GP::Context&    lContext2 = castObjectT<GP::Context&>(ioContext2);

  // Get parameters in local values, with the total number of nodes of an individual.
  bool             lMatingDone     = false;
  float            lDistrProba     = mDistributionProba->getWrappedValue();
  unsigned int     lMaxTreeDepth   = mMaxTreeDepth->getWrappedValue();
  GP::Tree::Handle lOldTreeHandle1 = lContext1.getGenotypeHandle();
  unsigned int     lOldTreeIndex1  = lContext1.getGenotypeIndex();
  GP::Tree::Handle lOldTreeHandle2 = lContext2.getGenotypeHandle();
  unsigned int     lOldTreeIndex2  = lContext2.getGenotypeIndex();
  unsigned int     lSizeIndiv1     = 0;
  for(unsigned int i=0; i<lIndiv1.size(); i++) lSizeIndiv1 += lIndiv1[i]->size();

  Beagle_LogDebugM(  
    ioContext1.getSystem().getLogger(),
    "crossover", "Beagle::GP::CrossoverOp",
    string("First individual to mate (before GP crossover): ")+
    lIndiv1.serialize()
  );
  Beagle_LogDebugM(
    ioContext1.getSystem().getLogger(),
    "crossover", "Beagle::GP::CrossoverOp",
    string("Second individual to mate (before GP crossover): ")+
    lIndiv2.serialize()
  );

  // Crossover loop. Try the given number of attempts to mate two individuals.
  for(unsigned int lAttempt=0; lAttempt<mNumberAttempts->getWrappedValue(); lAttempt++) {

     // Choose a node in all the individual node.
    unsigned int lChoosenNode1 =
      lContext1.getSystem().getRandomizer().rollInteger(0, lSizeIndiv1-1);

    // Get the tree in which the choosen node is. Change the global node index to the tree's index.
    unsigned int lChoosenTree1 = 0;
    for(; lChoosenTree1<lIndiv1.size(); lChoosenTree1++) {
      if(lChoosenNode1 < lIndiv1[lChoosenTree1]->size()) break;
      Beagle_AssertM(lChoosenNode1 >= lIndiv1[lChoosenTree1]->size());
      lChoosenNode1 -= lIndiv1[lChoosenTree1]->size();
    }
    Beagle_AssertM(lChoosenTree1 < lIndiv1.size());

    // Choose a type of node (branch or leaf) following the distribution probability and change the
    // node for another node of the same tree if the types mismatch.
    GP::Tree& lTree1 = *lIndiv1[lChoosenTree1];
    const unsigned int lPrimitiveSetIndex1 = lTree1.getPrimitiveSetIndex();
    if(lTree1.size() > 1) {
      bool lTypeNode1 =
        (lContext1.getSystem().getRandomizer().rollUniform(0.0, 1.0) < lDistrProba);
      while((lTree1[lChoosenNode1].mPrimitive->getNumberArguments() != 0) != lTypeNode1) {
        lChoosenNode1 = lContext1.getSystem().getRandomizer().rollInteger(0, lTree1.size()-1);
      }
    }

    // Choose a node in the second individual from a tree with the same primitive set index.
    unsigned int lSizeIndiv2 = 0;