modulecompressop.cpp

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

          ++lIter;
          lPossibleArgs.erase(lEraseIter);
          --lNbPossibleArgs;
        }
        else ++lIter;
      }
      // Remove selected argument and nodes in its subtree.
      else if((*lIter) < (lArgIndex+lArgSubTreeSize)) {
        std::list< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >::iterator lEraseIter = lIter;
        ++lIter;
        lPossibleArgs.erase(lEraseIter);
        --lNbPossibleArgs;
      }
      // We are over last node of the selected argument subtree, we can stop iterating.
      else break;
    }
  }
  Beagle_LogVerboseM(
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleCompressOp",
    string("Compressing the subtree of the ")+uint2ordinal(lNodeToCompress+1)+
    string(" node of tree as the  ")+uint2ordinal(inModuleIndex+1)+
    string(" module")
  );

  // Create the module.
  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."));
  }
  (*lModuleVectorComponent)[inModuleIndex] =
    castHandleT<GP::Tree>(ioContext.getIndividual().getTypeAlloc()->allocate());
  GP::Tree& lModule = *(*lModuleVectorComponent)[inModuleIndex];
  lModule.setPrimitiveSetIndex(ioTree.getPrimitiveSetIndex());
  const unsigned int lNbArgsSelected = lSelectedArgs.size();
  lModule.setNumberArguments(lNbArgsSelected);

  // Get a reference to the module and argument primitives.
  GP::PrimitiveSet& lPrimitSet = ioTree.getPrimitiveSet(ioContext);
  GP::Module::Handle lModPrimit =
    castHandleT<GP::Module>(lPrimitSet.getPrimitiveByName(mModulePrimitName->getWrappedValue()));
  if(lModPrimit == NULL) {
    std::ostringstream lOSS;
    lOSS << "Used primitive set of actual tree (index: " << ioTree.getPrimitiveSetIndex();
    lOSS << ") doesn't have a module primitive of name \"" << mModulePrimitName->getWrappedValue();
    lOSS << "\", as specified in parameter \"gp.ema.modulename\".";
    throw Beagle_RunTimeExceptionM(lOSS.str().c_str());
  }
  GP::Argument::Handle lArgPrimit =
    castHandleT<GP::Argument>(lPrimitSet.getPrimitiveByName(lModPrimit->getArgsName()));
  if(lArgPrimit == NULL) {
    std::ostringstream lOSS;
    lOSS << "Used primitive set of actual tree (index: " << ioTree.getPrimitiveSetIndex();
    lOSS << ") doesn't have a argument primitive of name \"" << lModPrimit->getArgsName();
    lOSS << "\", as specified by the module primitive \"" << lModPrimit->getName();
    lOSS << "\".";
    throw Beagle_RunTimeExceptionM(lOSS.str().c_str());
  }

  // Create new compressed tree and module tree.
  GP::Tree::Handle lNewTree =
    castHandleT<GP::Tree>(ioContext.getIndividual().getTypeAlloc()->allocate());
  Primitive::Handle lNewModPrimit = lModPrimit->generateInvoker(inModuleIndex,
                                                                lModPrimit->getName(),
                                                                lModPrimit->getArgsName(),
                                                                ioContext);
  lNewTree->push_back(GP::Node(lNewModPrimit));
  unsigned int lArgIndex=0;
  for(unsigned int i=0; i<lNodeToCompressSubTreeSize; ++i) {
    const unsigned int lChildIndex = i+lNodeToCompress;
    if(lSelectedArgs.find(lChildIndex)==lSelectedArgs.end()) lModule.push_back(ioTree[lChildIndex]);
    else {
      lModule.push_back(GP::Node(lArgPrimit->generateArgument(lArgIndex++)));
      const unsigned int lLastSubTreeIndex = i+ioTree[lChildIndex].mSubTreeSize;
      while(i<lLastSubTreeIndex) {
        lNewTree->push_back(ioTree[lNodeToCompress+i]);
        if((i+1) == lLastSubTreeIndex) break;
        else ++i;
      }
      Beagle_AssertM(i<lNodeToCompressSubTreeSize);
    }
  }
  Beagle_AssertM(lArgIndex == lNbArgsSelected);
  lModule.fixSubTreeSize();
  ioTree.erase(ioTree.begin()+lNodeToCompress,
               ioTree.begin()+lNodeToCompress+lNodeToCompressSubTreeSize);
  ioTree.insert(ioTree.begin()+lNodeToCompress, lNewTree->begin(), lNewTree->end());
  ioTree.fixSubTreeSize();

  // Log the module and compressed tree generated.
  Beagle_LogDebugM(  
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleCompressOp",
    string("New module generated is: ")+lModule.serialize()
  );
  Beagle_LogDebugM(  
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleCompressOp",
    string("Tree after compression: ")+
    ioTree.serialize()
  );

  return true;
  Beagle_StackTraceEndM("bool GP::ModuleCompressOp::compress(unsigned int inModuleIndex, GP::Tree& ioTree, GP::Context& ioContext)");
}


/*!
 *  \brief Recursive function used to list possible candidates in actual tree for module creation.
 *  \param outCandidates List of candidates in actual tree.
 *  \param inNodeIndex Node index in the GP tree for which the method is called.
 *  \param inTree Tree to get the candidates for compression.
 *  \return True is there was existing modules in subtree, false if not.
 */
bool GP::ModuleCompressOp::listCompressionCandidates(
  std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >& outCandidates,
  unsigned int inNodeIndex,
  const GP::Tree& inTree) const
{
  Beagle_StackTraceBeginM();
  const unsigned int lNbArgs = inTree[inNodeIndex].mPrimitive->getNumberArguments();
  bool lModulesInSubTrees =
    (inTree[inNodeIndex].mPrimitive->getName() == mModulePrimitName->getWrappedValue());
  unsigned int lChildIndex = inNodeIndex+1;
  for(unsigned int i=0; i<lNbArgs; ++i) {
    if(listCompressionCandidates(outCandidates,lChildIndex,inTree)) lModulesInSubTrees = true;
    lChildIndex += inTree[lChildIndex].mSubTreeSize;
  }
  if((lNbArgs>0) && (lModulesInSubTrees==false)) outCandidates.push_back(inNodeIndex);
  return lModulesInSubTrees;
  Beagle_StackTraceEndM("bool GP::ModuleCompressOp::listCompressionCandidates(std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> >& outCandidates, unsigned int inNodeIndex, const GP::Tree& inTree) const");
}


/*!
 *  \brief Apply compression operator to the deme.
 *  \param ioDeme Deme to apply compression on.
 *  \param ioContext Evolutionary context.
 */
void GP::ModuleCompressOp::operate(Beagle::Deme& ioDeme, Beagle::Context& ioContext)
{
  Beagle_StackTraceBeginM();
  GP::Deme&    lGPDeme    = castObjectT<GP::Deme&>(ioDeme);
  GP::Context& lGPContext = castObjectT<GP::Context&>(ioContext);

  Beagle_LogTraceM(
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleCompressOp",
    string("Creating modules of the ")+
    uint2ordinal(ioContext.getDemeIndex()+1)+" deme"
  );
  if(mCompressProba->getWrappedValue()==0.0) return;

  // Cleaning up module vector once at each generation.
  if(ioContext.getDemeIndex()==0) {
    Beagle_LogVerboseM(
    ioContext.getSystem().getLogger(),
      "EMA", "GP::ModuleCompressOp",
      string("Cleaning up the module vector component of unused modules before ")+
      string("apply compression")
    );
    cleanup(lGPContext.getVivarium(), lGPContext);
  }

  const float lCompressPb = mCompressProba->getWrappedValue();
  Beagle_LogVerboseM(
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleCompressOp",
    string("Creating modules with probability ")+
    dbl2str(lCompressPb)
  );

  // Generate list of available modules.
  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."));
  }
  std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> > lEmptyModules;
  for(unsigned int i=lModuleVectorComponent->size(); i>0; --i) {
    if((*lModuleVectorComponent)[i-1] == NULL) lEmptyModules.push_back(i-1);
  }
  const unsigned int lMaxModuleVecSize = mMaxModulesVectorSize->getWrappedValue();
  if(lEmptyModules.empty() && (lModuleVectorComponent->size()>=lMaxModuleVecSize)) return;

  GP::Individual::Handle lOldIndividualHandle = lGPContext.getIndividualHandle();
  unsigned int lOldIndividualIndex = lGPContext.getIndividualIndex();
  GP::Tree::Handle lOldGenotypeHandle = lGPContext.getGenotypeHandle();
  unsigned int lOldGenotypeIndex = lGPContext.getGenotypeIndex();

  // Apply compression operation
  std::vector< unsigned int,BEAGLE_STLALLOCATOR<unsigned int> > lIndivIndex(lGPDeme.size());
  for(unsigned int i=0; i<lIndivIndex.size(); ++i) lIndivIndex[i] = i;
  std::random_shuffle(lIndivIndex.begin(), lIndivIndex.end(), ioContext.getSystem().getRandomizer());
  for(unsigned int i=0; i<lIndivIndex.size(); ++i) {
    if(lEmptyModules.empty() && (lModuleVectorComponent->size()>=lMaxModuleVecSize)) break;
    if(ioContext.getSystem().getRandomizer().rollUniform() <= lCompressPb) {
      unsigned int lNewModIndex = 0;
      if(lEmptyModules.empty()) {
        if(lModuleVectorComponent->size()>=lMaxModuleVecSize) break;
        lNewModIndex = lModuleVectorComponent->size();
        lModuleVectorComponent->add(NULL);
      }
      else {
        lNewModIndex = lEmptyModules.back();
        lEmptyModules.pop_back();
      }
      unsigned int lNbNodesIndiv = 0;
      GP::Individual& lCompressedIndiv = *lGPDeme[lIndivIndex[i]];
      for(unsigned int j=0; j<lCompressedIndiv.size(); ++j) {
        lNbNodesIndiv += lCompressedIndiv[j]->size();
      }
      if(lNbNodesIndiv == 0) continue;
      unsigned int lNodeIndex = 
        lGPContext.getSystem().getRandomizer().rollInteger(0, (lNbNodesIndiv-1));
      unsigned int lTreeIndex = 0;
      for(; lNodeIndex>=lCompressedIndiv[lTreeIndex]->size(); ++lTreeIndex) {
        lNodeIndex -= lCompressedIndiv[lTreeIndex]->size();
      }
      Beagle_AssertM(lTreeIndex < lCompressedIndiv.size());
      if(lCompressedIndiv[lTreeIndex]->size() < 2) continue;
      lGPContext.setGenotypeHandle(lCompressedIndiv[lTreeIndex]);
      lGPContext.setGenotypeIndex(lTreeIndex);
      lGPContext.setIndividualHandle(lGPDeme[lIndivIndex[i]]);
      lGPContext.setIndividualIndex(lIndivIndex[i]);
      bool lCompressCompleted = compress(lNewModIndex, *lCompressedIndiv[lTreeIndex], lGPContext);
      if(lCompressCompleted==false) lEmptyModules.push_back(lNewModIndex);
    }
  }

  lGPContext.setGenotypeHandle(lOldGenotypeHandle);
  lGPContext.setGenotypeIndex(lOldGenotypeIndex);
  lGPContext.setIndividualHandle(lOldIndividualHandle);
  lGPContext.setIndividualIndex(lOldIndividualIndex);

  Beagle_LogObjectDebugM(
    ioContext.getSystem().getLogger(),
    "EMA", "GP::ModuleExpandOp",
    *(ioContext.getSystem().getComponent("ModuleVector"))
  );
  Beagle_StackTraceEndM("void GP::ModuleCompressOp::operate(Beagle::Deme& ioDeme, Beagle::Context& ioContext)");
}