tree.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/Tree.cpp
 *  \brief  Implementation of the type GP::Tree.
 *  \author Christian Gagne
 *  \author Marc Parizeau
 *  $Revision: 1.30 $
 *  $Date: 2005/10/04 09:32:52 $
 */

#include "beagle/GP.hpp"

#include <algorithm>

using namespace Beagle;


/*!
 *  \brief Construct a GP node.
 *  \param inPrimitive Handle to the primitive refered by the node.
 *  \param inSubTreeSize Sub-tree size, including actual node.
 */
GP::Node::Node(GP::Primitive::Handle inPrimitive, unsigned int inSubTreeSize) :
  mPrimitive(inPrimitive),
  mSubTreeSize(inSubTreeSize)
{ }


/*!
 *  \brief Compare equality of two GP tree's nodes.
 *  \param inRightNode Right node to be compare to.
 *  \return True if nodes are identical, false if not.
 */
bool GP::Node::operator==(const GP::Node& inRightNode) const
{
  Beagle_StackTraceBeginM();
  return (mPrimitive == inRightNode.mPrimitive) && (mSubTreeSize == inRightNode.mSubTreeSize);
  Beagle_StackTraceEndM("bool GP::Node::operator==(const GP::Node& inRightNode) const");
}


/*!
 *  \brief Construct a GP tree of the size given.
 *  \param inSize Size of the tree.
 *  \param inPrimitiveSetIndex Index of the primitive set associated to the current GP tree.
 *  \param inNumberArguments Number of ADF arguments of the GP tree.
 */
GP::Tree::Tree(unsigned int inSize,
               unsigned int inPrimitiveSetIndex,
               unsigned int inNumberArguments) :
#ifdef BEAGLE_HAVE_RTTI
  std::vector< Node,BEAGLE_STLALLOCATOR<Node> >(inSize),
  mPrimitiveSetIndex(inPrimitiveSetIndex),
  mNumberArguments(inNumberArguments),
  mRootType(NULL)
#else // BEAGLE_HAVE_RTTI
  std::vector< Node,BEAGLE_STLALLOCATOR<Node> >(inSize),
  mPrimitiveSetIndex(inPrimitiveSetIndex),
  mNumberArguments(inNumberArguments)
#endif // BEAGLE_HAVE_RTTI
{ }


/*!
 *  \brief Fixes the 'mSubTreeSize' field of the subtree starting at
 *    inNodeIndex.  (Defaults to fixing the entire tree.)
 *  \param inNodeIndex The first node of the subtree to fix.
 *  \return The size of the fixed subtree
 */
unsigned int GP::Tree::fixSubTreeSize(unsigned int inNodeIndex)
{
  Beagle_StackTraceBeginM();
  // Check if this is a terminal
  const unsigned int lNumArgs = 
    (*this)[inNodeIndex].mPrimitive->getNumberArguments();
  if(lNumArgs==0) {
    // This is a terminal
    (*this)[inNodeIndex].mSubTreeSize = 1;
    return 1;
  }
  else {
    // This is a branch
    // Loop through the args, correcting each of those
    unsigned int lSubTreeSize = 1;
    unsigned int lNodeIndex = inNodeIndex+1;
    for(unsigned int i=0; i<lNumArgs; i++) {
      const unsigned int lThisSubTreeSize = fixSubTreeSize(lNodeIndex);
      lSubTreeSize += lThisSubTreeSize;
      lNodeIndex += lThisSubTreeSize;
    }
    (*this)[inNodeIndex].mSubTreeSize = lSubTreeSize;
    return lSubTreeSize;
  }
  Beagle_StackTraceEndM("unsigned int GP::Tree::fixSubTreeSize(unsigned int inNodeIndex)");
}


/*!
 *  \brief Convenient method to obtain this tree's PrimitiveSet.
 *  \param ioContext Context on which to operate.
 *  \return Primitive set for this tree
 */
GP::PrimitiveSet& GP::Tree::getPrimitiveSet(GP::Context& ioContext) const
{
  Beagle_StackTraceBeginM();
  Beagle_AssertM(mPrimitiveSetIndex < ioContext.getSystem().getPrimitiveSuperSet().size());
  return *(ioContext.getSystem().getPrimitiveSuperSet()[mPrimitiveSetIndex]);
  Beagle_StackTraceEndM("GP::PrimitiveSet& GP::Tree::getPrimitiveSet(GP::Context& ioContext) const");
}


#ifdef BEAGLE_HAVE_RTTI

/*!
 *  \brief Get desired type as tree root.
 *  \param ioContext Evolutionary context.
 *  \return Tree root desired type.
 */
const std::type_info* GP::Tree::getRootType(GP::Context& ioContext) const
{
  Beagle_StackTraceBeginM();
  if(mRootType == NULL)
    return ioContext.getSystem().getPrimitiveSuperSet()[mPrimitiveSetIndex]->getRootType();
  return mRootType;
  Beagle_StackTraceEndM("const std::type_info* GP::Tree::getRootType(GP::Context& ioContext) const");
}

#endif // BEAGLE_HAVE_RTTI


/*!
 *  \brief Return number of nodes of GP tree.
 *  \return Number of nodes of GP tree.
 */
unsigned int GP::Tree::getSize() const
{
  Beagle_StackTraceBeginM();
  return size();
  Beagle_StackTraceEndM("unsigned int GP::Tree::getSize() const");
}


/*!
 *  \brief Get the maximum depth of a sub-tree.
 *  \param inNodeIndex Index of the node root to the sub-tree.
 *  \return Depth to the given sub-tree.
 *  \throw Beagle::AssertException If the node index given is to out-of-bound.
 */
unsigned int GP::Tree::getTreeDepth(unsigned int inNodeIndex) const
{
  Beagle_StackTraceBeginM();
  // Check if there aren't any nodes in the tree
  if(size()==0) return 0;

  Beagle_BoundCheckAssertM(inNodeIndex, 0, size()-1);
  unsigned int lDepth = 1;
  unsigned int lChildNodeIndex = inNodeIndex + 1;
  for(unsigned int i=0; i<(*this)[inNodeIndex].mPrimitive->getNumberArguments(); i++) {
    unsigned int lChildDepth = getTreeDepth(lChildNodeIndex);
    lDepth = maxOf<unsigned int>(lDepth, lChildDepth+1);
    lChildNodeIndex += (*this)[lChildNodeIndex].mSubTreeSize;
  }
  return lDepth;
  Beagle_StackTraceEndM("unsigned int GP::Tree::getTreeDepth(unsigned int inNodeIndex) const");
}


/*!
 *  \brief Interpret the GP tree.
 *  \param outResult Datum containing the result of the interpretation.
 *  \param ioContext GP evolutionary context.
 *  \throw Beagle::ObjectException When tree is empty or not in contextual individual.
 *  \throw Beagle::AssertException When the contextual individual is a NULL pointer.
 *  \throw Beagle::GP::MaxNodesExecutionException If number of nodes execution is more than allowed.
 *  \throw Beagle::GP::MaxTimeExecutionException If elapsed execution time is more than allowed.
 */
void GP::Tree::interpret(GP::Datum& outResult, GP::Context& ioContext)
{
  Beagle_StackTraceBeginM();
  if(empty()) throw Beagle_ObjectExceptionM("Could not interpret, tree is empty!");
  GP::Individual::Handle lIndiv = ioContext.getIndividualHandle();
  if(lIndiv == NULL) 
    throw Beagle_RunTimeExceptionM(string("GP::Tree::interpret(): The handle to the current ")+
      string("individual is NULL. This handle is obtained from the Context. The most likely ")+
      string("cause of this error is that the Context has not been set correctly. Consider ")+
      string("Context::setIndividualHandle()."));

  // Check that this tree is part of the individual specified in the Context  
  unsigned int lTreeIndex = 0;
  for(; lTreeIndex < lIndiv->size(); lTreeIndex++) {
    if(this == (*lIndiv)[lTreeIndex].getPointer()) break;
  }
  if(lTreeIndex == lIndiv->size())
    throw Beagle_ObjectExceptionM("Interpreted tree is not in the actual individual of the context!");

  Tree::Handle lOldTreeHandle = ioContext.getGenotypeHandle();
  unsigned int lOldTreeIndex  = ioContext.getGenotypeIndex();
  ioContext.setGenotypeIndex(lTreeIndex);
  ioContext.setGenotypeHandle(Handle(this));
  Beagle_LogVerboseM(
    ioContext.getSystem().getLogger(),
    "gptree", "Beagle::GP::Tree",
    string("Interpreting the ")+uint2ordinal(lTreeIndex+1)+
    string(" tree of the ")+uint2ordinal(ioContext.getIndividualIndex()+1)+
    string(" individual")
  );
  Beagle_LogDebugM(
    ioContext.getSystem().getLogger(),
    "gptree", "Beagle::GP::Tree",
    string("The tree is: ")+ioContext.getGenotype().serialize()
  );
  Beagle_LogDebugM(
    ioContext.getSystem().getLogger(),
    "gptree", "Beagle::GP::Tree",
    string("Executing the tree root node \"")+
    (*this)[0].mPrimitive->getName()+"\""
  );
  ioContext.setNodesExecutionCount(0);
  ioContext.incrementNodesExecuted();
  ioContext.getExecutionTimer().reset();  
  ioContext.pushCallStack(0);
  (*this)[0].mPrimitive->execute(outResult, ioContext);
  ioContext.popCallStack();
  ioContext.checkExecutionTime();
  Beagle_LogDebugM(
    ioContext.getSystem().getLogger(),
    "gptree", "Beagle::GP::Tree",
    string("Result of executing the ")+uint2ordinal(ioContext.getGenotypeIndex()+1)+string(" tree: ")+outResult.serialize()
  );
  ioContext.setGenotypeIndex(lOldTreeIndex);
  ioContext.setGenotypeHandle(lOldTreeHandle);
  Beagle_StackTraceEndM("void GP::Tree::interpret(GP::Datum& outResult, GP::Context& ioContext)");
}


/*!
 *  \brief Compare the equality of two GP trees.
 *  \param inRightObj Right tree to be compare to tha actual one.
 *  \return True if the trees are identical, false if not.
 */
bool GP::Tree::isEqual(const Object& inRightObj) const
{
  Beagle_StackTraceBeginM();
  const GP::Tree& lRightTree = castObjectT<const GP::Tree&>(inRightObj);
  if(size() != lRightTree.size()) return false;
  return std::equal(begin(), end(), lRightTree.begin());
  Beagle_StackTraceEndM("bool GP::Tree::isEqual(const Object& inRightObj) const");
}