mutationswapsubtreeop.cpp

来自「非常好的进化算法EC 实现平台 可以实现多种算法 GA GP」· C++ 代码 · 共 478 行 · 第 1/2 页

        lN2OffN1 = lContext1.getSystem().getRandomizer().rollInteger(1, lSubTreeSizeN1-1);
        lNode2 = lNode1 + lN2OffN1;
      }

      // Choosing the third node, any node in lNode2's subtree.
      unsigned int lSubTreeSizeN2 = (*lTreeClone1)[lNode2].mSubTreeSize;
      unsigned int lN3OffN2 =
        lContext1.getSystem().getRandomizer().rollInteger(1, lSubTreeSizeN2-1);

      // Ok, now we can exchange the subtrees.

      // New value of lNode1 and lNode2 for the second exchange.
      unsigned int lNode3Exch2 = lNode1 + lN3OffN2;
      unsigned int lNode1Exch2 = lNode2;

      // New value of lNode1 and lNode2 for the third exchange.
      unsigned int lNode2Exch3 = lNode1 + lN3OffN2 + lN2OffN1;
      unsigned int lNode3Exch3 = lNode2;
 
      // First exchange.
      lTreeClone1->setContextToNode(lNode1, lContext1);
      lTreeClone2->setContextToNode(lNode2, *lContextHdl2);
      exchangeSubTrees(*lTreeClone1, lNode1, lContext1,
                       *lTreeClone2, lNode2, *lContextHdl2);

      // Second exchange.
      lTreeClone1->setContextToNode(lNode3Exch2, lContext1);
      lTreeClone2->setContextToNode(lNode1Exch2, *lContextHdl2);
      exchangeSubTrees(*lTreeClone1, lNode3Exch2, lContext1,
                       *lTreeClone2, lNode1Exch2, *lContextHdl2);

      // Third exchange.
      lTreeClone1->setContextToNode(lNode2Exch3, lContext1);
      lTreeClone2->setContextToNode(lNode3Exch3, *lContextHdl2);
      exchangeSubTrees(*lTreeClone1, lNode2Exch3, lContext1,
                       *lTreeClone2, lNode3Exch3, *lContextHdl2);

      // Checking if the tree depth is respected. If not, start again.
      if(lTreeClone1->getTreeDepth() > lMaxTreeDepth) {
        Beagle_LogVerboseM(
          lContext1.getSystem().getLogger(),
          "mutation", "Beagle::GP::MutationSwapSubtreeOp",
          "Tree maximum depth exceeded. GP swap subtree mutation invalid."
        );
        continue;
      }

      lGPIndiv[lChoosenTree] = lTreeClone1;
      Beagle_LogVerboseM(
        lContext1.getSystem().getLogger(),
        "mutation", "Beagle::GP::MutationSwapSubtreeOp",
        "GP swap subtree mutation valid"
      );
      lMatingDone = true;
      break;   // The swap subtree mutation is valid.
    }

    // lMutationType is false -> external mutation
    else {

      // Deterniming the minimal node index to use.
      unsigned int lMinNodeIndex = 0;
      for(; lTreeClone1->size() == ((*lTreeClone1)[lMinNodeIndex].mSubTreeSize+lMinNodeIndex);
          ++lMinNodeIndex) {
        if(lMinNodeIndex == (lTreeClone1->size()-1)) continue; // Can't do anything with linear tree.
      }

      // Change lNode1 if less than minimum node index.
      if(lNode1 < lMinNodeIndex)
        lNode1 = lContext1.getSystem().getRandomizer().rollInteger(lMinNodeIndex,
                                                                   lTreeClone1->size()-1);

      // Choosing second swap subtree mutation point.
      std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> > lValidN2;
      for(unsigned int i=lMinNodeIndex; i<lTreeClone1->size(); ++i) {
        if((i>=lNode1) && (i<lNode1+(*lTreeClone1)[lNode1].mSubTreeSize)) continue;
        else if((lNode1>=i) && (lNode1<(i+(*lTreeClone1)[i].mSubTreeSize))) continue;
        else lValidN2.push_back(i);
      }
      unsigned int lNode2 =
        lValidN2[lContext1.getSystem().getRandomizer().rollInteger(0, lValidN2.size()-1)];

      Beagle_LogVerboseM(
        lContext1.getSystem().getLogger(),
        "mutation", "Beagle::GP::MutationSwapSubtreeOp",
        string("Trying an external swap subtree mutation of the ")+uint2ordinal(lNode1+1)+
        string(" node with the subtree to the ")+uint2ordinal(lNode2+1)+
        string(" node")
      );

      // Ok, now we can exchange the subtrees.

      // New value of lNode1 and lNode2 for the second exchange.
      unsigned int lNode1Exch2 = lNode1;
      unsigned int lNode2Exch2 = lNode2;
      if(lNode1 < lNode2) {
        lNode2Exch2 += (*lTreeClone1)[lNode2].mSubTreeSize;
        lNode2Exch2 -= (*lTreeClone1)[lNode1].mSubTreeSize;
      }
      else {
        lNode1Exch2 += (*lTreeClone1)[lNode1].mSubTreeSize;
        lNode1Exch2 -= (*lTreeClone1)[lNode2].mSubTreeSize;
      }

      // First exchange.
      lTreeClone1->setContextToNode(lNode1, lContext1);
      lTreeClone2->setContextToNode(lNode2, *lContextHdl2);
      exchangeSubTrees(*lTreeClone1, lNode1, lContext1,
                       *lTreeClone2, lNode2, *lContextHdl2);

      // Second exchange.
      lTreeClone1->setContextToNode(lNode2Exch2, lContext1);
      lTreeClone2->setContextToNode(lNode1Exch2, *lContextHdl2);
      exchangeSubTrees(*lTreeClone1, lNode2Exch2, lContext1,
                       *lTreeClone2, lNode1Exch2, *lContextHdl2);

      // Checking if the tree depth is respected. If not, start again.
      if(lTreeClone1->getTreeDepth() > lMaxTreeDepth) {
        Beagle_LogVerboseM(
          lContext1.getSystem().getLogger(),
          "mutation", "Beagle::GP::MutationSwapSubtreeOp",
          "Tree maximum depth exceeded. GP swap subtree mutation invalid."
        );
        continue;
      }

      lGPIndiv[lChoosenTree] = lTreeClone1;
      Beagle_LogVerboseM(
        lContext1.getSystem().getLogger(),
        "mutation", "Beagle::GP::MutationSwapSubtreeOp",
        "GP swap subtree mutation valid"
      );
      lMatingDone = true;
      break;   // The swap subtree mutation is valid.
    }
  }

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

  if(lMatingDone) {
    Beagle_LogDebugM(
      lContext1.getSystem().getLogger(),
      "mutation", "Beagle::GP::MutationSwapSubtreeOp",
      string("Individual after swap subtree mutation: ")+
      lGPIndiv.serialize()
    );
  }
  else {
    Beagle_LogVerboseM(
      lContext1.getSystem().getLogger(),
      "mutation", "Beagle::GP::MutationSwapSubtreeOp",
      "No GP swap subtree mutation done"
    );
  }

  return lMatingDone;
  Beagle_StackTraceEndM("bool GP::MutationSwapSubtreeOp::mutate(Beagle::Individual& ioIndividual, Beagle::Context& ioContext)");
}


/*!
 *  \brief  Exchange two GP trees on given points.
 *  \param  ioTree1 First tree to mate.
 *  \param  inNode1 Node index of the swap subtree first point.
 *  \param  ioContext1 Evolutionary context relatively to the first tree.
 *  \param  ioTree2 Second tree to mate.
 *  \param  inNode2 Node index of the swap subtree second point.
 *  \param  ioContext2 Evolutionary context relatively to the second tree.
 */
void GP::MutationSwapSubtreeOp::exchangeSubTrees(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::MutationSwapSubtreeOp::exchangeSubTrees(GP::Tree& ioTree1, unsigned int inNode1, GP::Context& ioContext1, GP::Tree& ioTree2, unsigned int inNode2, GP::Context& ioContext2)");
}


/*!
 *  \brief Read a mutation operator from XML subtree.
 *  \param inIter XML iterator to use to read crossover operator.
 *  \param inOpMap Operator map to use to read crossover operator.
 */
void GP::MutationSwapSubtreeOp::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 mMutationPbReadName = inIter->getAttribute("mutationpb").c_str();
  if(mMutationPbReadName.empty() == false) mMutationPbName = mMutationPbReadName;  
  string mDistribPbReadName = inIter->getAttribute("distrpb").c_str();
  if(mDistribPbReadName.empty() == false) mDistribPbName = mDistribPbReadName;
  Beagle_StackTraceEndM("void GP::MutationSwapSubtreeOp::readWithMap(PACC::XML::ConstIterator inIter, OperatorMap& inOpMap)");
}


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