Chromosome.h
Go to the documentation of this file.
1/*!
2 *
3 *
4 * \brief CMAChromosomeof the CMA-ES.
5 *
6 *
7 *
8 * \author T.Voss, T. Glasmachers, O.Krause
9 * \date 2010-2011
10 *
11 *
12 * \par Copyright 1995-2017 Shark Development Team
13 *
14 * <BR><HR>
15 * This file is part of Shark.
16 * <https://shark-ml.github.io/Shark/>
17 *
18 * Shark is free software: you can redistribute it and/or modify
19 * it under the terms of the GNU Lesser General Public License as published
20 * by the Free Software Foundation, either version 3 of the License, or
21 * (at your option) any later version.
22 *
23 * Shark is distributed in the hope that it will be useful,
24 * but WITHOUT ANY WARRANTY; without even the implied warranty of
25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 * GNU Lesser General Public License for more details.
27 *
28 * You should have received a copy of the GNU Lesser General Public License
29 * along with Shark. If not, see <http://www.gnu.org/licenses/>.
30 *
31 */
32#ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_CHROMOSOME_H
33#define SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_CHROMOSOME_H
34
35#include <shark/Statistics/Distributions/MultiVariateNormalDistribution.h>
36
37namespace shark {
38
39/**
40* \brief Models a CMAChromosomeof the elitist (MO-)CMA-ES that encodes strategy parameters.
41*/
42struct CMAChromosome{
48 MultiVariateNormalDistributionCholesky m_mutationDistribution; ///< Models the search distribution using a cholsky matrix
49
50 RealVector m_evolutionPath; ///< Low-pass filtered accumulation of successful mutative steps.
51 RealVector m_lastStep; ///< The most recent mutative step.
52 RealVector m_lastZ; ///< The sample from N(0,I) that produced the last step.
53
54 double m_stepSize; ///< The step-size used to scale the normally-distributed mutative steps. Dynamically adapted during the run.
55 double m_stepSizeDampingFactor; ///< Damping factor \f$d\f$ used in the step-size update procedure.
56 double m_stepSizeLearningRate; ///< The learning rate for the step-size.
57 double m_successProbability; ///< Current success probability of this parameter set.
58 double m_targetSuccessProbability; ///< Target success probability, close \f$ \frac{1}{5}\f$.
59 double m_evolutionPathLearningRate; ///< Learning rate (constant) for updating the evolution path.
60 double m_covarianceMatrixLearningRate; ///< Learning rate (constant) for updating the covariance matrix.
61 double m_covarianceMatrixUnlearningRate; ///< Learning rate (constant) for unlearning unsuccessful directions from the covariance matrix.
62
63 double m_successThreshold; ///< Success threshold \f$p_{\text{thresh}}\f$ for cutting off evolution path updates.
64
65 CMAChromosome(){}
66 CMAChromosome(
67 std::size_t searchSpaceDimension,
68 double successThreshold,
69 double initialStepSize
70 )
71 : m_stepSize( initialStepSize )
72 , m_covarianceMatrixLearningRate( 0 )
73 , m_successThreshold(successThreshold)
74 {
75 m_mutationDistribution.resize( searchSpaceDimension );
76 m_evolutionPath.resize( searchSpaceDimension );
77 m_lastStep.resize( searchSpaceDimension );
78 m_lastZ.resize( searchSpaceDimension );
79
80 m_targetSuccessProbability = 1.0 / ( 5.0 + 1/2.0 );
81 m_successProbability = m_targetSuccessProbability;
82 m_stepSizeDampingFactor = 1.0 + searchSpaceDimension / 2.;
83 m_stepSizeLearningRate = m_targetSuccessProbability/ (2. + m_targetSuccessProbability );
84 m_evolutionPathLearningRate = 2.0 / (2.0 + searchSpaceDimension);
85 m_covarianceMatrixLearningRate = 2.0 / (sqr(searchSpaceDimension) + 6.);
86 m_covarianceMatrixUnlearningRate = 0.4/( std::pow(searchSpaceDimension, 1.6 )+1. );
87 }
88
89 /**
90 * \brief Updates a \f$(\mu+1)\f$-MO-CMA-ES chromosome of an successful offspring individual. It is assumed that unsuccessful individuals are not selected for future mutation.
91 *
92 * Updates strategy parameters according to:
93 * \f{align*}
94 * \bar{p}_{\text{succ}} & \leftarrow & (1-c_p)\bar{p}_{\text{succ}} + c_p \\
95 * \sigma & \leftarrow & \sigma \cdot e^{\frac{1}{d}\frac{\bar{p}_{\text{succ}} - p^{\text{target}}_{\text{succ}}}{1-p^{\text{target}}_{\text{succ}}}}\\
96 * \vec{p}_c & \leftarrow & (1-c_c) \vec{p}_c + \mathbb{1}_{\bar{p}_{\text{succ}} < p_{\text{thresh}}} \sqrt{c_c (2 - c_c)} \vec{x}_{\text{step}} \\
97 * \vec{C} & \leftarrow & (1-c_{\text{cov}}) \vec{C} + c_{\text{cov}} \left( \vec{p}_c \vec{p}_c^T + \mathbb{1}_{\bar{p}_{\text{succ}} \geq p_{\text{thresh}}} c_c (2 - c_c) \vec{C} \right)
98 * \f}
99 */
113
114 /**
115 * \brief Updates a \f$(\mu+1)\f$-MO-CMA-ES chromosome of a parent individual.
116 *
117 * This is called when the parent individual survived the last selection process. The update process depends now on how the offspring fares:
118 * It can be successful, unsuccesful or a complete failure.
119 *
120 * Based on whether it is succesful or not, the global stepsize is adapted as for the child. In the case of a failure the direction of that individual is actively
121 * purged from the Covariance matrix to make this offspring less likely.
122 */
123 void updateAsParent(IndividualSuccess offspringSuccess) {
124 m_successProbability = (1 - m_stepSizeLearningRate) * m_successProbability + m_stepSizeLearningRate * (offspringSuccess == Successful);
125 m_stepSize *= ::exp( 1./m_stepSizeDampingFactor * (m_successProbability - m_targetSuccessProbability) / (1-m_targetSuccessProbability) );
126
127 if(offspringSuccess != Failure) return;
128
129 if( m_successProbability < m_successThreshold ) {
130 //check whether the step is admissible with the proposed update weight
131 double stepNormSqr = norm_sqr( m_lastZ );
132 double rate = m_covarianceMatrixUnlearningRate;
133
134 if( stepNormSqr > 1 && 1 < m_covarianceMatrixUnlearningRate*(2*stepNormSqr-1) ){
135 rate = 1.0/(2*stepNormSqr-1);//make the update shorter
136 //~ return; //better be safe for now
137 }
138 rankOneUpdate(1+rate,-rate,m_lastStep);
139 } else {
140 roundUpdate();
141 }
142 }
143
144 /**
145 * \brief Serializes the CMAChromosometo the supplied archive.
146 * \tparam Archive The type of the archive the CMAChromosomeshall be serialized to.
147 * \param [in,out] archive The archive to serialize to.
148 * \param [in] version Version information (optional and not used here).
149 */
150 template<typename Archive>
151 void serialize( Archive & archive, const unsigned int version ) {
152
153 archive & BOOST_SERIALIZATION_NVP( m_mutationDistribution );
154 //~ archive & BOOST_SERIALIZATION_NVP( m_inverseCholesky );
155
156 archive & BOOST_SERIALIZATION_NVP( m_evolutionPath );
157 archive & BOOST_SERIALIZATION_NVP( m_lastStep );
158
159 archive & BOOST_SERIALIZATION_NVP( m_stepSize );
160 archive & BOOST_SERIALIZATION_NVP( m_stepSizeDampingFactor );
161 archive & BOOST_SERIALIZATION_NVP( m_stepSizeLearningRate );
162 archive & BOOST_SERIALIZATION_NVP( m_successProbability );
163 archive & BOOST_SERIALIZATION_NVP( m_targetSuccessProbability );
164 archive & BOOST_SERIALIZATION_NVP( m_successThreshold);
165 archive & BOOST_SERIALIZATION_NVP( m_evolutionPathLearningRate );
166 archive & BOOST_SERIALIZATION_NVP( m_covarianceMatrixLearningRate );
167 archive & BOOST_SERIALIZATION_NVP( m_covarianceMatrixUnlearningRate );
168 }
169private:
170
171 /// \brief Performs a rank one update to the cholesky factor.
172 ///
173 /// This also requries an update of the inverse cholesky factor, that is the only reason, it exists.
174 void rankOneUpdate(double alpha, double beta, RealVector const& v){
175 m_mutationDistribution.rankOneUpdate(alpha,beta,v);
176 }
177
178 /// \brief Performs an update step which makes the distribution more round
179 ///
180 /// This is called, when the distribution is too successful as this indicates that the step size
181 /// in some direction is too small to be useful
182 void roundUpdate(){
183 double evolutionpathUpdateWeight = m_evolutionPathLearningRate * ( 2.-m_evolutionPathLearningRate );
184 m_evolutionPath *= 1 - m_evolutionPathLearningRate;
185 rankOneUpdate(
186 1 - m_covarianceMatrixLearningRate+evolutionpathUpdateWeight,
187 m_covarianceMatrixLearningRate,
188 m_evolutionPath
189 );
190 }
191};
192}
193
194#endif