crossoverop.cpp

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

    for(unsigned int i=0; i<lIndiv2.size(); i++) {
      if(lIndiv2[i]->getPrimitiveSetIndex() == lPrimitiveSetIndex1) {
        lSizeIndiv2 += lIndiv2[i]->size();
      }
    }

    // Check to see that there is at least one node that can be selected
    if(lSizeIndiv2==0) {
      Beagle_LogVerboseM(
        ioContext1.getSystem().getLogger(),
        "crossover", "Beagle::GP::CrossoverConstrainedOp",
        string("Crossover attempt failed:  The tree chosen from the first individual has a primitive set index of ")+
        uint2str(lPrimitiveSetIndex1)+
        string(" and there are no trees in the second individual with that primitive set index")
      );
      continue;
    }

    // Choose a node in the second individual
    unsigned int lChoosenNode2 = lContext2.getSystem().getRandomizer().rollInteger(0, lSizeIndiv2-1);

    // Find which tree the choosen node is in.
    unsigned int lChoosenTree2 = 0;
    for(; lChoosenTree2<lIndiv2.size(); lChoosenTree2++) {
      if(lIndiv2[lChoosenTree2]->getPrimitiveSetIndex() == lPrimitiveSetIndex1) {
        if(lChoosenNode2 < lIndiv2[lChoosenTree2]->size()) break;
        Beagle_AssertM(lChoosenNode2 >= lIndiv2[lChoosenTree2]->size());
        lChoosenNode2 -= lIndiv2[lChoosenTree2]->size();
      }
    }
    Beagle_AssertM(lChoosenTree2 < lIndiv2.size());
    GP::Tree& lTree2 = *lIndiv2[lChoosenTree2];

    // 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.
    if(lTree2.size() > 1) {
      bool lTypeNode2 =
        (lContext2.getSystem().getRandomizer().rollUniform(0.0, 1.0) < lDistrProba);
      while((lTree2[lChoosenNode2].mPrimitive->getNumberArguments() != 0) != lTypeNode2) {
        lChoosenNode2 = lContext2.getSystem().getRandomizer().rollInteger(0, lTree2.size()-1);
      }
    }

    // Set the first context to the node of the first tree.
    // Check if depth is ok. Do a new crossover attempt if not.
    lTree1.setContextToNode(lChoosenNode1, lContext1);
    unsigned int lNewDepthTree1 =
      lContext1.getCallStackSize() + lTree2.getTreeDepth(lChoosenNode2) - 1;
    if(lNewDepthTree1 > lMaxTreeDepth) {
      Beagle_LogVerboseM(
        ioContext1.getSystem().getLogger(),
        "crossover", "Beagle::GP::CrossoverConstrainedOp",
        string("Crossover attempt failed because the depth of the resulting tree in the ")+
        string("first individual would exceed the depth constraint")
      );
      continue;
    }

    // Set the first context to the node of the second tree.
    // Check if depth is ok. Do a new crossover attempt if not.
    lTree2.setContextToNode(lChoosenNode2, lContext2);
    unsigned int lNewDepthTree2 =
      lContext2.getCallStackSize() + lTree1.getTreeDepth(lChoosenNode1) - 1;
    if(lNewDepthTree2 > lMaxTreeDepth) {
      Beagle_LogVerboseM(
        ioContext1.getSystem().getLogger(),
        "crossover", "Beagle::GP::CrossoverConstrainedOp",
        string("Crossover attempt failed because the depth of the resulting tree in the ")+
        string("second individual would exceed the depth constraint")
      );
      continue;
    }

    // Mate the trees.
    Beagle_LogVerboseM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      string("Trying to mate the ")+uint2ordinal(lChoosenTree1+1)+
      string(" tree of the first individual with the ")+uint2ordinal(lChoosenTree2+1)+
      string(" tree of the second individual")
    );
    Beagle_LogVerboseM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      string("Trying to exchange the ")+uint2ordinal(lChoosenNode1+1)+
      string(" node of the first tree with the ")+uint2ordinal(lChoosenNode2+1)+
      string(" node of the second tree")
    );

    mateTrees(lTree1, lChoosenNode1, lContext1, lTree2, lChoosenNode2, lContext2);

    lMatingDone = true;
    Beagle_LogVerboseM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      "GP crossover valid"
    );
    break;   // The crossover is valid.
  }

  // Replace the contexts.
  lContext1.setGenotypeHandle(lOldTreeHandle1);
  lContext1.setGenotypeIndex(lOldTreeIndex1);
  lContext2.setGenotypeHandle(lOldTreeHandle2);
  lContext2.setGenotypeIndex(lOldTreeIndex2);

  if(lMatingDone) {
    Beagle_LogDebugM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      string("First individual mated (after GP crossover): ")+
      lIndiv1.serialize()
    );
    Beagle_LogDebugM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      string("Second individual mated (after GP crossover): ")+
      lIndiv2.serialize()
    );
  }
  else {
    Beagle_LogVerboseM(
      ioContext1.getSystem().getLogger(),
      "crossover", "Beagle::GP::CrossoverOp",
      "No GP crossover done"
    );
  }

  return lMatingDone;
  Beagle_StackTraceEndM("bool GP::CrossoverOp::mate(Beagle::Individual& ioIndiv1, Beagle::Context& ioContext1, Beagle::Individual& ioIndiv2, Beagle::Context& ioContext2)");
}


/*!
 *  \brief  Mate two GP trees on given points.
 *  \param  ioTree1 First tree to mate.
 *  \param  inNode1 Node index of the croosover point in the first tree to mate.
 *  \param  ioContext1 Evolutionary context relatively to the first tree.
 *  \param  ioTree2 Second tree to mate.
 *  \param  inNode2 Node index of the croosover point in the second tree to mate.
 *  \param  ioContext2 Evolutionary context relatively to the second tree.
 */
void GP::CrossoverOp::mateTrees(GP::Tree& ioTree1, unsigned int inNode1, GP::Context& ioContext1,
                                GP::Tree& ioTree2, unsigned int inNode2, GP::Context& ioContext2)
{
  Beagle_StackTraceBeginM();
  Beagle_AssertM(&ioTree1 != &ioTree2);
  unsigned int lSwapSize1 = ioTree1[inNode1].mSubTreeSize;
  unsigned int lSwapSize2 = ioTree2[inNode2].mSubTreeSize;
  if(lSwapSize1 <= lSwapSize2) {
    std::swap_ranges(ioTree1.begin()+inNode1, ioTree1.begin()+inNode1+lSwapSize1, ioTree2.begin()+inNode2);
    ioTree1.insert(ioTree1.begin()+inNode1+lSwapSize1,
                   ioTree2.begin()+inNode2+lSwapSize1,
                   ioTree2.begin()+inNode2+lSwapSize2);
    ioTree2.erase(ioTree2.begin()+inNode2+lSwapSize1, ioTree2.begin()+inNode2+lSwapSize2);
  }
  else {
    std::swap_ranges(ioTree1.begin()+inNode1, ioTree1.begin()+inNode1+lSwapSize2, ioTree2.begin()+inNode2);
    ioTree2.insert(ioTree2.begin()+inNode2+lSwapSize2,
                   ioTree1.begin()+inNode1+lSwapSize2,
                   ioTree1.begin()+inNode1+lSwapSize1);
    ioTree1.erase(ioTree1.begin()+inNode1+lSwapSize2, ioTree1.begin()+inNode1+lSwapSize1);
  }
  int lDiffSize = lSwapSize1 - lSwapSize2;
  for(unsigned int i=0; i<(ioContext1.getCallStackSize()-1); i++)
    ioTree1[ioContext1.getCallStackElement(i)].mSubTreeSize -= lDiffSize;
  for(unsigned int j=0; j<(ioContext2.getCallStackSize()-1); j++)
    ioTree2[ioContext2.getCallStackElement(j)].mSubTreeSize += lDiffSize;
  Beagle_StackTraceEndM("void GP::CrossoverOp::mateTrees(GP::Tree& ioTree1, unsigned int inNode1, GP::Context& ioContext1, GP::Tree& ioTree2, unsigned int inNode2, GP::Context& ioContext2)");
}


/*!
 *  \brief Read a crossover operator for XML subtree.
 *  \param inIter XML iterator to use to read crossover operator.
 *  \param inOpMap Operator map to use to read crossover operator.
 */
void GP::CrossoverOp::readWithMap(PACC::XML::ConstIterator inIter, OperatorMap& inOpMap)
{
  Beagle_StackTraceBeginM();
  if((inIter->getType()!=PACC::XML::eData) || (inIter->getValue()!=getName().c_str())) {
    std::ostringstream lOSS;
    lOSS << "tag <" << getName() << "> expected!" << std::flush;
    throw Beagle_IOExceptionNodeM(*inIter, lOSS.str().c_str());
  }
  string mMatingProbaReadName = inIter->getAttribute("matingpb").c_str();
  if(mMatingProbaReadName.empty() == false) mMatingProbaName = mMatingProbaReadName;
  string mDistribPbReadName = inIter->getAttribute("distrpb").c_str();
  if(mDistribPbReadName.empty() == false) mDistribPbName = mDistribPbReadName;
  Beagle_StackTraceEndM("void GP::CrossoverOp::readWithMap(PACC::XML::ConstIterator inIter, OperatorMap& inOpMap)");
}


/*!
 *  \brief Write crossover operator into XML streamer.
 *  \param ioStreamer XML streamer to write crossover operator into.
 *  \param inIndent Whether XML output should be indented.
 */
void GP::CrossoverOp::writeContent(PACC::XML::Streamer& ioStreamer, bool inIndent) const
{
  Beagle_StackTraceBeginM();
  Beagle::CrossoverOp::writeContent(ioStreamer, inIndent);
  ioStreamer.insertAttribute("distrpb", mDistribPbName);
  Beagle_StackTraceEndM("void GP::CrossoverOp::writeContent(PACC::XML::Streamer& ioStreamer, bool inIndent) const");
}