/* * Open BEAGLE * Copyright (C) 2001-2004 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/GA/src/MuWCommaLambdaCMAFltVecOp.cpp * \brief Source code of class MuWCommaLambdaCMAFltVecOp. * \author Christian Gagne * \author Marc Parizeau * $Revision: 1.11 $ * $Date: 2005/10/04 16:25:09 $ */ #include "beagle/GA.hpp" #include #include #include #include using namespace Beagle; /*! * \brief Build CMA-ES (Mu_W+Lambda) replacement strategy operator. * \param inLMRatioName Lamda over Mu parameter name used in the register. * \param inName Name of the CMA-ES (Mu_W+Lambda) operator. */ GA::MuWCommaLambdaCMAFltVecOp::MuWCommaLambdaCMAFltVecOp(Beagle::string inLMRatioName, Beagle::string inName) : MuCommaLambdaOp(inLMRatioName,inName) { } /*! * \brief Initialize the operator. * \param ioSystem Reference to the evolutionary system. */ void GA::MuWCommaLambdaCMAFltVecOp::initialize(System& ioSystem) { Beagle_StackTraceBeginM(); MuCommaLambdaOp::initialize(ioSystem); if(ioSystem.getRegister().isRegistered("ga.cmaes.b")) { mB = castHandleT(ioSystem.getRegister()["ga.cmaes.b"]); } else { mB = new Matrix; Register::Description lDescription( "CMA-ES B matrix", "Matrix", "", "CMA-ES B matrix containing the covariance matrix eigenvectors." ); ioSystem.getRegister().addEntry("ga.cmaes.b", mB, lDescription); } if(ioSystem.getRegister().isRegistered("ga.cmaes.d")) { mD = castHandleT(ioSystem.getRegister()["ga.cmaes.d"]); } else { mD = new Vector; Register::Description lDescription( "CMA-ES D vector", "Vector", "", "CMA-ES D vector containing the square root of the covariance matrix eigenvalues." ); ioSystem.getRegister().addEntry("ga.cmaes.d", mD, lDescription); } if(ioSystem.getRegister().isRegistered("ga.cmaes.pc")) { mPC = castHandleT(ioSystem.getRegister()["ga.cmaes.pc"]); } else { mPC = new Vector; Register::Description lDescription( "CMA-ES p_c vector", "Vector", "", "CMA-ES p_c vector containing the covariance matrix evolution path." ); ioSystem.getRegister().addEntry("ga.cmaes.pc", mPC, lDescription); } if(ioSystem.getRegister().isRegistered("ga.cmaes.ps")) { mPS = castHandleT(ioSystem.getRegister()["ga.cmaes.ps"]); } else { mPS = new Vector; Register::Description lDescription( "CMA-ES p_s vector", "Vector", "", "CMA-ES p_s vector containing the sigma value evolution path." ); ioSystem.getRegister().addEntry("ga.cmaes.ps", mPS, lDescription); } if(ioSystem.getRegister().isRegistered("ga.cmaes.sigma")) { mSigma = castHandleT(ioSystem.getRegister()["ga.cmaes.sigma"]); } else { mSigma = new Double(0.5); Register::Description lDescription( "CMA-ES sigma value", "Double", "0.5", "CMA-ES sigma value moduling the mutation step size." ); ioSystem.getRegister().addEntry("ga.cmaes.sigma", mSigma, lDescription); } if(ioSystem.getRegister().isRegistered("ga.cmaes.xmean")) { mXmean = castHandleT(ioSystem.getRegister()["ga.cmaes.xmean"]); } else { mXmean = new Vector; Register::Description lDescription( "CMA-ES mean vector", "Vector", "", "CMA-ES mean vector containing the average individual." ); ioSystem.getRegister().addEntry("ga.cmaes.xmean", mXmean, lDescription); } if(ioSystem.getRegister().isRegistered("ga.float.maxvalue")) { mMaxValue = castHandleT(ioSystem.getRegister()["ga.float.maxvalue"]); } else { mMaxValue = new DoubleArray(1,DBL_MAX); std::ostringstream lOSS; lOSS << "Maximum values assigned to vector's floats. "; lOSS << "Value can be a scalar, which limit the value for all float "; lOSS << "vector parameters, or a vector which limit the value for the parameters "; lOSS << "individually. If the maximum value is smaller than the "; lOSS << "float vector size, the limit used for the last values of the float vector "; lOSS << "is equal to the last value of the maximum value vector."; Register::Description lDescription( "Maximum vector values", "DoubleArray", dbl2str(DBL_MAX), lOSS.str().c_str() ); ioSystem.getRegister().addEntry("ga.float.maxvalue", mMaxValue, lDescription); } if(ioSystem.getRegister().isRegistered("ga.float.minvalue")) { mMinValue = castHandleT(ioSystem.getRegister()["ga.float.minvalue"]); } else { mMinValue = new DoubleArray(1,DBL_MIN); std::ostringstream lOSS; lOSS << "Minimum values assigned to vector's floats. "; lOSS << "Value can be a scalar, which limit the value for all float "; lOSS << "vector parameters, or a vector which limit the value for the parameters "; lOSS << "individually. If the minimum value is smaller than the "; lOSS << "float vector size, the limit used for the last values of the float vector "; lOSS << "is equal to the last value of the minimum value vector."; Register::Description lDescription( "Minimum values", "DoubleArray", dbl2str(DBL_MIN), lOSS.str().c_str() ); ioSystem.getRegister().addEntry("ga.float.minvalue", mMinValue, lDescription); } Beagle_StackTraceEndM("void GA::MuWCommaLambdaCMAFltVecOp::initialize(System& ioSystem)"); } /*! * \brief Apply the CMA-ES (Mu_W+Lambda) replacement strategy operation on a deme. * \param ioDeme Reference to the deme on which the operation takes place. * \param ioContext Evolutionary context of the operation. * \throw Beagle::ValidationException If a parameter is missing or have a bad value. * \throw Beagle::AssertException If an invalid condition appears. * * This routine is mostly inspired from matlab routine purecmaes.m and the document * "The CMA Evolution Strategy: A Tutorial" (October 15, 2004), both * from Nikolaus Hansen. * See http://www.bionik.tu-berlin.de/user/niko/cmaes_inmatlab.html */ void GA::MuWCommaLambdaCMAFltVecOp::operate(Deme& ioDeme, Context& ioContext) { Beagle_StackTraceBeginM(); // Get real popsize and size of float vectors from register. UIntArray::Handle lPopSize; if(ioContext.getSystem().getRegister().isRegistered("ec.pop.size")) { lPopSize = castHandleT(ioContext.getSystem().getRegister()["ec.pop.size"]); } else { std::ostringstream lOSS; lOSS << "Population size parameter \"ec.pop.size\" is not found in register!"; throw ValidationException(lOSS.str().c_str()); } const unsigned int lDemeSize = (*lPopSize)[ioContext.getDemeIndex()]; UInt::Handle lFloatVectorSize; if(ioContext.getSystem().getRegister().isRegistered("ga.init.vectorsize")) { lFloatVectorSize = castHandleT(ioContext.getSystem().getRegister()["ga.init.vectorsize"]); } else { std::ostringstream lOSS; lOSS << "GA::MuWCommaLambdaCMAFltVecOp must be used in fixed-lenght float vector "; lOSS << "individuals. Parameter \"ga.init.vectorsize\" is not in register, "; lOSS << "while it is needed to set initial size of the different CMA-ES matrices "; lOSS << "and vectors."; throw ValidationException(lOSS.str().c_str()); } const unsigned int lN=lFloatVectorSize->getWrappedValue(); // Compute weights and effective mu Vector lWeight(lDemeSize, std::log(double(lDemeSize+1))); double lSumWeight=0.0; double lMuEff=0.0; for(unsigned int i=0; igetWrappedValue() >= 1.0, mLMRatioName, "The LM ratio must be higher or equal to 1.0."); Beagle_ValidateParameterM(mElitismKeepSize->getWrappedValue() <= ioDeme.size(), "ec.elite.keepsize", "The elistism keepsize must be less than the deme size!"); Beagle_LogTraceM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", string("Using CMA-ES (mu_w,lambda) replacement strategy to process the ")+ uint2ordinal(ioContext.getDemeIndex()+1)+" deme" ); Beagle_LogObjectM( ioContext.getSystem().getLogger(), Logger::eTrace, "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", (*this) ); // Create weighted mean individual. std::sort(ioDeme.begin(), ioDeme.end(), IsMorePointerPredicate()); Individual::Handle lMeanInd = castHandleT(ioDeme.getTypeAlloc()->allocate()); lMeanInd->resize(1); GA::FloatVector::Handle lMeanFloatVec = castHandleT((*lMeanInd)[0]); lMeanFloatVec->resize(lN, 0.0); for(unsigned int i=0; isize()==1); GA::FloatVector::Handle lVecI = castHandleT((*ioDeme[i])[0]); Beagle_AssertM(lVecI->size()==lN); for(unsigned int j=0; jresize(lN); for(unsigned int i=0; i lRoulette; buildRoulette(lRoulette, ioContext); // Keep best individuals if elitism is used const unsigned int lElitismKS=mElitismKeepSize->getWrappedValue(); if(lElitismKS > 0) { Individual::Bag lBestInd; std::make_heap(ioDeme.begin(), ioDeme.end(), IsLessPointerPredicate()); for(unsigned int i=0; igetWrappedValue()*double(lDemeSize)); Individual::Bag lBagWithMeanInd; lBagWithMeanInd.push_back(lMeanInd); for(unsigned int i=0; igetNextSibling(); Beagle_NonNullPointerAssertM(lSelectedBreeder); Beagle_NonNullPointerAssertM(lSelectedBreeder->getBreederOp()); Individual::Handle lBredIndiv = lSelectedBreeder->getBreederOp()->breed(lBagWithMeanInd, lSelectedBreeder->getFirstChild(), ioContext); Beagle_NonNullPointerAssertM(lBredIndiv); ioDeme.push_back(lBredIndiv); } // Check if all individuals have known fitness. for(unsigned int i=0; igetFitness()==NULL) || (ioDeme[i]->getFitness()->isValid()==false)) return; } } // Keep mu best children Beagle_AssertM(ioDeme.size() > lDemeSize); std::sort(ioDeme.begin(), ioDeme.end(), IsMorePointerPredicate()); ioDeme.resize(lDemeSize); // Log messages Beagle_LogTraceM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", "Updating covariance matrix, sigma, and cumulation paths of CMA-ES." ); // Compute some constants const double lCC = 4.0 / (double(lN) + 4.0); const double lCS = (lMuEff+2.0) / (double(lN)+lMuEff+3.0); const double lMuCov = lMuEff; double lCCov = (((2.0*lMuEff)-1.0) / ((double(lN)+2.0)*(double(lN)+2.0)) + (2.0*lMuEff)); lCCov = ((1.0/lMuCov) * (2.0/((double(lN)+1.414)*(double(lN)+1.414)))) + ((1.0-(1.0/lMuCov)) * minOf(1.0,lCCov)); double lDamps = std::sqrt((lMuEff-1.0) / (double(lN)+1.0)) - 1.0; lDamps = 1.0 + (2.0*maxOf(0.0,lDamps)) + lCS; const double lChiN = std::sqrt(double(lN)) * (1.0 - (0.25/double(lN)) + (1.0/(21.0*double(lN)*double(lN)))); // Compute new xmean Vector lXmean_new(lN, 0.0); for(unsigned int i=0; i((*ioDeme[i])[0]); for(unsigned int j=0; jgetWrappedValue(); Vector lZmean(lN,0.0); for(unsigned int i=0; itranspose(lBt); lZmean = lBt * lZmean; for(unsigned int i=0; imultiply((Matrix&)lBZm, lZmean); lBZm *= std::sqrt(lCS * (2.0-lCS) * lMuEff); (*mPS) *= (1.0-lCS); (*mPS) += lBZm; double lPSnorm = 0.0; for(unsigned int i=0; isize(); ++i) lPSnorm += ((*mPS)[i] * (*mPS)[i]); lPSnorm = std::sqrt(lPSnorm); const double lHLeft = lPSnorm / std::sqrt(1.0-std::pow(1.0-lCS, 2.0*double(ioContext.getGeneration()+1))); const double lHRight = (1.5+(1.0/(double(lN)-0.5))) * lChiN; const bool lHSig = (lHLeftgetWrappedValue() *= std::exp((lCS/lDamps) * ((lPSnorm/lChiN)-1.0)); // Adapt covariance matrix C Matrix lBDt; lBD.transpose(lBDt); Matrix lC; lBD.multiply(lC, lBDt); Matrix lR1Upd; // Rank one update mPC->transpose(lR1Upd); lR1Upd = (*mPC) * lR1Upd; if(lHSig==false) { Matrix lCmod = lC; lCmod *= lCC * (2.0 - lCC); lR1Upd += lCmod; } lR1Upd *= (lCCov / lMuCov); Matrix lRMuUpd(lN,lN,0.0); // Rank Mu update for(unsigned int i=0; i((*ioDeme[i])[0]); Vector lX_I(lVecI->size()); for(unsigned int j=0; jsize(); ++j) lX_I[j] = (*lVecI)[j]; lX_I -= (*mXmean); lX_I *= (1.0 / lSigma); Matrix lX_It; lX_I.transpose(lX_It); lX_It *= lWeight[i]; lRMuUpd += (lX_I * lX_It); } lRMuUpd *= (lCCov * (1.0 - (1.0/lMuCov))); lC *= (1.0-lCCov); // Attenuate old matrix lC += lR1Upd; // Add rank one update lC += lRMuUpd; // Add rank mu update // Update B and D from C for(unsigned int i=1; igetMax(); double lMinD = (*mD)[0]; for(unsigned int i=1; isize(); ++i) { lMinD = ((*mD)[i] < lMinD) ? (*mD)[i] : lMinD; } if(lMaxD > (1e14*lMinD)) (*mD) += ((lMaxD/1e14)-lMinD); // Adjust D as standard deviation for(unsigned int i=0; iserialize() ); Beagle_LogTraceM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", string("CMA-ES updated D vector (standard deviations): ")+mD->serialize() ); Beagle_LogTraceM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", string("CMA-ES updated sigma: ")+mSigma->serialize() ); Beagle_LogVerboseM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", string("CMA-ES updated p_c vector (covariance cumulation path): ")+mPC->serialize() ); Beagle_LogVerboseM( ioContext.getSystem().getLogger(), "replacement-strategy", "Beagle::GA::MuWCommaLambdaCMAFltVecOp", string("CMA-ES updated p_s vector (sigma cumulation path): ")+mPS->serialize() ); Beagle_StackTraceEndM("void GA::MuWCommaLambdaCMAFltVecOp::operate(Deme& ioDeme, Context& ioContext)"); } /*! * \brief Post-initialization hook. * \param ioSystem Reference to the evolutionary system. * \throw Beagle::ValidationException If a parameter is invalid. */ void GA::MuWCommaLambdaCMAFltVecOp::postInit(System& ioSystem) { Beagle_StackTraceBeginM(); MuCommaLambdaOp::postInit(ioSystem); UInt::Handle lFloatVectorSize; if(ioSystem.getRegister().isRegistered("ga.init.vectorsize")) { lFloatVectorSize = castHandleT(ioSystem.getRegister()["ga.init.vectorsize"]); } else { std::ostringstream lOSS; lOSS << "GA::MuWCommaLambdaCMAFltVecOp must be used in fixed-lenght float vector "; lOSS << "individuals. Parameter \"ga.init.vectorsize\" is not in register, "; lOSS << "while it is needed to set initial size of the different CMA-ES matrices "; lOSS << "and vectors."; throw ValidationException(lOSS.str().c_str()); } const unsigned int lN=lFloatVectorSize->getWrappedValue(); if((mB->getRows()==0) && (mB->getCols()==0)) mB->setIdentity(lN); else if((mB->getRows()!=mB->getCols()) || (mB->getRows()!=lN)) { std::ostringstream lOSS; lOSS << "Matrix B given by parameter \"ga.cmaes.b\" must be square "; lOSS << "and with a number of rows (and columns) equals to the size "; lOSS << "of the float vector individuals."; throw ValidationException(lOSS.str().c_str()); } if(mD->size()==0) { mD->resize(lN); for(unsigned int i=0; isize()!=lN) { std::ostringstream lOSS; lOSS << "Vector D given by parameter \"ga.cmaes.d\" must have a size "; lOSS << "equals to the size of the float vector individuals."; throw ValidationException(lOSS.str().c_str()); } if(mPC->size()==0) { mPC->resize(lN); for(unsigned int i=0; igetRows()!=lN) { std::ostringstream lOSS; lOSS << "Cumulation path vector p_c given by parameter \"ga.cmaes.pc\" "; lOSS << "must have the the size of the float vector individuals."; throw ValidationException(lOSS.str().c_str()); } if(mPS->size()==0) { mPS->resize(lN); for(unsigned int i=0; igetRows()!=lN) { std::ostringstream lOSS; lOSS << "Cumulation path vector p_s given by parameter \"ga.cmaes.ps\" "; lOSS << "must have the the size of the float vector individuals."; throw ValidationException(lOSS.str().c_str()); } Beagle_StackTraceEndM("void GA::MuWCommaLambdaCMAFltVecOp::postInit(System& ioSystem)"); }