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  * <http://shark-ml.org/>
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 
37 namespace shark {
38 
39 /**
40 * \brief Models a CMAChromosomeof the elitist (MO-)CMA-ES that encodes strategy parameters.
41 */
42 struct CMAChromosome{
43  enum IndividualSuccess{
44  Successful = 1,
45  Unsuccessful = 2,
46  Failure = 3
47  };
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  */
100  void updateAsOffspring() {
101  m_successProbability = (1 - m_stepSizeLearningRate) * m_successProbability + m_stepSizeLearningRate;
102  m_stepSize *= ::exp( 1./m_stepSizeDampingFactor * (m_successProbability - m_targetSuccessProbability) / (1-m_targetSuccessProbability) );
103 
104  double evolutionpathUpdateWeight=m_evolutionPathLearningRate * ( 2.-m_evolutionPathLearningRate );
105  if( m_successProbability < m_successThreshold ) {
106  m_evolutionPath *= 1 - m_evolutionPathLearningRate;
107  noalias(m_evolutionPath) += std::sqrt( evolutionpathUpdateWeight ) * m_lastStep;
108  rankOneUpdate(1 - m_covarianceMatrixLearningRate,m_covarianceMatrixLearningRate,m_evolutionPath);
109  } else {
110  roundUpdate();
111  }
112  }
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  }
169 private:
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