modulecompressop.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/ModuleCompressOp.cpp
 *  \brief  Implementation of ModuleCompressOp.
 *  \author Matthew Walker <[e-mail]>
 *  \author Christian Gagne <[e-mail]>
 *  $Revision: 1.6 $
 *  $Date: 2005/10/04 16:25:10 $
 */

#include "beagle/GP.hpp"

using namespace Beagle;


/*!
 *  \brief Construct an compress operator for evolutionary module acquisition.
 *  \param inName Name of the operator.
 */
GP::ModuleCompressOp::ModuleCompressOp(Beagle::string inName) :
  Operator(inName)
{ }


/*!
 *  \brief Initialize GP compress operator for evolutionary module acquisition.
 *  \param ioSystem Evolutionary system.
 */
void GP::ModuleCompressOp::initialize(Beagle::System& ioSystem) 
{
  Beagle_StackTraceBeginM();
  Beagle::Operator::initialize(ioSystem);

  if(ioSystem.getRegister().isRegistered("gp.ema.modulename")) {
    mModulePrimitName = castHandleT<String>(ioSystem.getRegister()["gp.ema.modulename"]);
  } else {
    mModulePrimitName = new String("MODULE");
    Register::Description lDescription(
      "Module primitive name for EMA",
      "String",
      "MODULE",
      "Name of the GP primitive to use as module reference in the GP trees"
    );
    ioSystem.getRegister().addEntry("gp.ema.modulename", mModulePrimitName, lDescription);
  }

  if(ioSystem.getRegister().isRegistered("gp.ema.maxmodules")) {
    mMaxModulesVectorSize = castHandleT<UInt>(ioSystem.getRegister()["gp.ema.maxmodules"]);
  } else {
    mMaxModulesVectorSize = new UInt(25);
    Register::Description lDescription(
      "Maximum allowed modules",
      "UInt",
      "25",
      "Maximum number of allowed modules for evolutionary module acquisition"
    );
    ioSystem.getRegister().addEntry("gp.ema.maxmodules", mMaxModulesVectorSize, lDescription);
  }

  if(ioSystem.getRegister().isRegistered("gp.ema.maxargs")) {
    mMaxModulesArgs = castHandleT<UInt>(ioSystem.getRegister()["gp.ema.maxargs"]);
  } else {
    mMaxModulesArgs = new UInt(4);
    Register::Description lDescription(
      "Max. number of module arguments",
      "UInt",
      "4",
      "Maximum number of allowed arguments to each module for evolutionary module acquisition"
    );
    ioSystem.getRegister().addEntry("gp.ema.maxargs", mMaxModulesArgs, lDescription);
  }

  if(ioSystem.getRegister().isRegistered("gp.ema.compresspb")) {
    mCompressProba = castHandleT<Float>(ioSystem.getRegister()["gp.ema.compresspb"]);
  } else {
    mCompressProba = new Float(0.2f);
    Register::Description lDescription(
      "Probability of an individual being compressed",
      "Float",
      "0.2",
      string("Probability of an individual being compress. Expansion randomly selects a ")+
      string("subtree, create a module from it and change the subtree for a reference to ")+
      string("the module.")
    );
    ioSystem.getRegister().addEntry("gp.ema.compresspb", mCompressProba, lDescription);
  }
  Beagle_StackTraceEndM("void GP::ModuleCompressOp::initialize(Beagle::System& ioSystem) ");
}


/*!
 *  \brief Clean-up the module vector component from unused modules.
 *  \param ioVivarium Vivarium which is tested for module usage.
 *  \param ioContext Evolutionary context.
 */
void GP::ModuleCompressOp::cleanup(GP::Vivarium& ioVivarium, GP::Context& ioContext)
{
  Beagle_StackTraceBeginM();
  ModuleVectorComponent::Handle lModuleVectorComponent =
    castHandleT<ModuleVectorComponent>(ioContext.getSystem().getComponent("ModuleVector"));
  if(lModuleVectorComponent==NULL) {
    throw Beagle_RunTimeExceptionM(string("GP system is not configured with a module vector. ")+
      string("Consider adding a GP::ModuleVectorComponent object to the system."));
  }

  // Loop over the population and hall-of-fames for unused modules.
  const string lModuleName = mModulePrimitName->getWrappedValue();
  std::vector< bool,BEAGLE_STLALLOCATOR<bool> > lModuleUtilization(lModuleVectorComponent->size(), false);
  for(unsigned int i=0; i<ioVivarium.size(); ++i) {
    if(ioVivarium[i]==NULL) continue;
    GP::Deme& lDeme = *ioVivarium[i];
    for(unsigned int j=0; j<lDeme.size(); ++j) {
      if(lDeme[j]==NULL) continue;
      GP::Individual& lIndividual = *lDeme[j];
      for(unsigned int k=0; k<lIndividual.size(); ++k) {
        if(lIndividual[k]==NULL) continue;
        GP::Tree& lTree = *lIndividual[k];
        for(unsigned int l=0; l<lTree.size(); ++l) {
          if(lTree[l].mPrimitive->getName() == lModuleName) {
            GP::Module::Handle lModule = castHandleT<GP::Module>(lTree[l].mPrimitive);
            lModuleUtilization[lModule->getIndex()] = true;
          }
        }
      }
    }
    HallOfFame& lHoFDeme = lDeme.getHallOfFame();
    for(unsigned int j=0; j<lHoFDeme.size(); ++j) {
      if(lHoFDeme[j].mIndividual==NULL) continue;
      GP::Individual& lIndividual = castObjectT<GP::Individual&>(*lHoFDeme[j].mIndividual);
      for(unsigned int k=0; k<lIndividual.size(); ++k) {
        if(lIndividual[k]==NULL) continue;
        GP::Tree& lTree = *lIndividual[k];
        for(unsigned int l=0; l<lTree.size(); ++l) {
          if(lTree[l].mPrimitive->getName() == lModuleName) {
            GP::Module::Handle lModule = castHandleT<GP::Module>(lTree[l].mPrimitive);
            lModuleUtilization[lModule->getIndex()] = true;
          }
        }
      }
    }
  }
  HallOfFame& lHoFViva = ioVivarium.getHallOfFame();
  for(unsigned int j=0; j<lHoFViva.size(); ++j) {
    if(lHoFViva[j].mIndividual==NULL) continue;
    GP::Individual& lIndividual = castObjectT<GP::Individual&>(*lHoFViva[j].mIndividual);
    for(unsigned int k=0; k<lIndividual.size(); ++k) {
      if(lIndividual[k]==NULL) continue;
      GP::Tree& lTree = *lIndividual[k];
      for(unsigned int l=0; l<lTree.size(); ++l) {
        if(lTree[l].mPrimitive->getName() == lModuleName) {
          GP::Module::Handle lModule = castHandleT<GP::Module>(lTree[l].mPrimitive);
          lModuleUtilization[lModule->getIndex()] = true;
        }
      }
    }
  }

  // Remove unused modules from module vector.
  for(unsigned int i=0; i<lModuleUtilization.size(); ++i) {
    if(lModuleUtilization[i] == false) (*lModuleVectorComponent)[i] = NULL;
  }
  Beagle_StackTraceEndM("void GP::ModuleCompressOp::cleanup(GP::Vivarium& ioVivarium, GP::Context& ioContext)");
}


/*!
 *  \brief Compress tree into the given module.
 *  \param inModuleIndex Index of the module to create from compression.
 *  \param ioTree Tree to compress.
 *  \param ioContext Evolutionary context.
 *  \return Whether or not the tree has been compressed by modularization.
 */
bool GP::ModuleCompressOp::compress(unsigned int inModuleIndex,
                                    GP::Tree& ioTree,
                                    GP::Context& ioContext)
{
  Beagle_StackTraceBeginM();
  // Get candidates for compression.
  std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> > lCandidates;
  listCompressionCandidates(lCandidates, 0, ioTree);
  if(lCandidates.size() == 0) return false;

  // Log tree before compression.
  Beagle_LogDebugM(  
    ioContext.getSystem().getLogger(),
    "EMA", "ModuleCompressOp",
    string("Tree before compression: ")+
    ioTree.serialize()
  );

  // Select the node to be the module and its argument.
  const unsigned int lNodeToCompress =
    lCandidates[ioContext.getSystem().getRandomizer().rollInteger(0, lCandidates.size()-1)];
  std::set< unsigned int,std::less<unsigned int>,BEAGLE_STLALLOCATOR<unsigned int> > lSelectedArgs;
  const unsigned int lNodeToCompressSubTreeSize = ioTree[lNodeToCompress].mSubTreeSize;
  std::list< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> > lPossibleArgs;
  for(unsigned int i=1; i<lNodeToCompressSubTreeSize; ++i) {
    lPossibleArgs.push_back(lNodeToCompress+i);
  }
  unsigned int lNbPossibleArgs = (lNodeToCompressSubTreeSize-1);
  const unsigned int lNbArgs =
    ioContext.getSystem().getRandomizer().rollInteger(1, mMaxModulesArgs->getWrappedValue());
  for(unsigned int i=0; (i<lNbArgs) && (lNbPossibleArgs>0); ++i) {
    const unsigned int lRNDValue =
      ioContext.getSystem().getRandomizer().rollInteger(0, (lNbPossibleArgs-1));
    unsigned int lArgIndex = 0;
    unsigned int lCounter=0;
    for(std::list< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >::iterator lIter=lPossibleArgs.begin(); 
        lIter!=lPossibleArgs.end(); ++lIter) {
      if(lCounter++ == lRNDValue) {
        lArgIndex = *lIter;
        break;
      }
    }
    lSelectedArgs.insert(lArgIndex);
    const unsigned int lArgSubTreeSize = ioTree[lArgIndex].mSubTreeSize;
    for(std::list< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >::iterator lIter=lPossibleArgs.begin();
        lIter!=lPossibleArgs.end();) {
      // Nodes that are parents to the selected argument, remove only direct parents.
      if((*lIter) < lArgIndex) {
        if(((*lIter)+ioTree[*lIter].mSubTreeSize) > lArgIndex) {
          std::list< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >::iterator lEraseIter = lIter;