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-2015 Shark Development Team
13  *
14  * <BR><HR>
15  * This file is part of Shark.
16  * <http://image.diku.dk/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 
36 
37 namespace shark {
38 
39 /**
40 * \brief Models a CMAChromosomeof the elitist (MO-)CMA-ES that encodes strategy parameters.
41 */
46  Failure = 3
47  };
48  MultiVariateNormalDistributionCholesky m_mutationDistribution; ///< Models the search distribution using a cholsky matrix
49  //~ RealMatrix m_inverseCholesky;///< inverse cholesky matrix
50 
51  RealVector m_evolutionPath; ///< Low-pass filtered accumulation of successful mutative steps.
52  RealVector m_lastStep; ///< The most recent mutative step.
53  RealVector m_lastZ; ///< The sample from N(0,I) that produced the last step.
54 
55  double m_stepSize; ///< The step-size used to scale the normally-distributed mutative steps. Dynamically adapted during the run.
56  double m_stepSizeDampingFactor; ///< Damping factor \f$d\f$ used in the step-size update procedure.
57  double m_stepSizeLearningRate; ///< The learning rate for the step-size.
58  double m_successProbability; ///< Current success probability of this parameter set.
59  double m_targetSuccessProbability; ///< Target success probability, close \f$ \frac{1}{5}\f$.
60  double m_evolutionPathLearningRate; ///< Learning rate (constant) for updating the evolution path.
61  double m_covarianceMatrixLearningRate; ///< Learning rate (constant) for updating the covariance matrix.
62  double m_covarianceMatrixUnlearningRate; ///< Learning rate (constant) for unlearning unsuccessful directions from the covariance matrix.
63 
64  double m_successThreshold; ///< Success threshold \f$p_{\text{thresh}}\f$ for cutting off evolution path updates.
65 
68  std::size_t searchSpaceDimension,
69  double successThreshold,
70  double initialStepSize
71  )
72  : m_mutationDistribution(true)//we do a triangular cholesky factorisation
73  , m_stepSize( initialStepSize )
74  , m_covarianceMatrixLearningRate( 0 )
75  , m_successThreshold(successThreshold)
76  {
77  m_mutationDistribution.resize( searchSpaceDimension );
78  //~ m_inverseCholesky = blas::identity_matrix<double>( searchSpaceDimension );
79  m_evolutionPath.resize( searchSpaceDimension );
80  m_lastStep.resize( searchSpaceDimension );
81  m_lastZ.resize( searchSpaceDimension );
82 
83  m_targetSuccessProbability = 1.0 / ( 5.0 + 1/2.0 );
84  m_successProbability = m_targetSuccessProbability;
85  m_stepSizeDampingFactor = 1.0 + searchSpaceDimension / 2.;
86  m_stepSizeLearningRate = m_targetSuccessProbability/ (2. + m_targetSuccessProbability );
87  m_evolutionPathLearningRate = 2.0 / (2.0 + searchSpaceDimension);
88  m_covarianceMatrixLearningRate = 2.0 / (sqr(searchSpaceDimension) + 6.);
89  m_covarianceMatrixUnlearningRate = 0.4/( std::pow(searchSpaceDimension, 1.6 )+1. );
90  }
91 
92  /**
93  * \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.
94  *
95  * Updates strategy parameters according to:
96  * \f{align*}
97  * \bar{p}_{\text{succ}} & \leftarrow & (1-c_p)\bar{p}_{\text{succ}} + c_p \\
98  * \sigma & \leftarrow & \sigma \cdot e^{\frac{1}{d}\frac{\bar{p}_{\text{succ}} - p^{\text{target}}_{\text{succ}}}{1-p^{\text{target}}_{\text{succ}}}}\\
99  * \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}} \\
100  * \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)
101  * \f}
102  */
104  m_successProbability = (1 - m_stepSizeLearningRate) * m_successProbability + m_stepSizeLearningRate;
105  m_stepSize *= ::exp( 1./m_stepSizeDampingFactor * (m_successProbability - m_targetSuccessProbability) / (1-m_targetSuccessProbability) );
106 
107  double evolutionpathUpdateWeight=m_evolutionPathLearningRate * ( 2.-m_evolutionPathLearningRate );
108  if( m_successProbability < m_successThreshold ) {
109  m_evolutionPath *= 1 - m_evolutionPathLearningRate;
110  noalias(m_evolutionPath) += std::sqrt( evolutionpathUpdateWeight ) * m_lastStep;
111  rankOneUpdate(1 - m_covarianceMatrixLearningRate,m_covarianceMatrixLearningRate,m_evolutionPath);
112  } else {
113  roundUpdate();
114  }
115  }
116 
117  /**
118  * \brief Updates a \f$(\mu+1)\f$-MO-CMA-ES chromosome of a parent individual.
119  *
120  * This is called when the parent individual survived the last selection process. The update process depends now on how the offspring fares:
121  * It can be successful, unsuccesful or a complete failure.
122  *
123  * 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
124  * purged from the Covariance matrix to make this offspring less likely.
125  */
126  void updateAsParent(IndividualSuccess offspringSuccess) {
127  m_successProbability = (1 - m_stepSizeLearningRate) * m_successProbability + m_stepSizeLearningRate * (offspringSuccess == Successful);
128  m_stepSize *= ::exp( 1./m_stepSizeDampingFactor * (m_successProbability - m_targetSuccessProbability) / (1-m_targetSuccessProbability) );
129 
130  if(offspringSuccess != Failure) return;
131 
132  if( m_successProbability < m_successThreshold ) {
133  //check whether the step is admissible with the proposed update weight
134  double stepNormSqr = norm_sqr( m_lastZ );
135  double rate = m_covarianceMatrixUnlearningRate;
136 
137  if( stepNormSqr > 1 && 1 < m_covarianceMatrixUnlearningRate*(2*stepNormSqr-1) ){
138  rate = 1.0/(2*stepNormSqr-1);//make the update shorter
139  //~ return; //better be safe for now
140  }
141  rankOneUpdate(1+rate,-rate,m_lastStep);
142  } else {
143  roundUpdate();
144  }
145  }
146 
147  /**
148  * \brief Serializes the CMAChromosometo the supplied archive.
149  * \tparam Archive The type of the archive the CMAChromosomeshall be serialized to.
150  * \param [in,out] archive The archive to serialize to.
151  * \param [in] version Version information (optional and not used here).
152  */
153  template<typename Archive>
154  void serialize( Archive & archive, const unsigned int version ) {
155 
156  archive & BOOST_SERIALIZATION_NVP( m_mutationDistribution );
157  //~ archive & BOOST_SERIALIZATION_NVP( m_inverseCholesky );
158 
159  archive & BOOST_SERIALIZATION_NVP( m_evolutionPath );
160  archive & BOOST_SERIALIZATION_NVP( m_lastStep );
161 
162  archive & BOOST_SERIALIZATION_NVP( m_stepSize );
163  archive & BOOST_SERIALIZATION_NVP( m_stepSizeDampingFactor );
164  archive & BOOST_SERIALIZATION_NVP( m_stepSizeLearningRate );
165  archive & BOOST_SERIALIZATION_NVP( m_successProbability );
166  archive & BOOST_SERIALIZATION_NVP( m_targetSuccessProbability );
167  archive & BOOST_SERIALIZATION_NVP( m_evolutionPathLearningRate );
168  archive & BOOST_SERIALIZATION_NVP( m_covarianceMatrixLearningRate );
169  archive & BOOST_SERIALIZATION_NVP( m_covarianceMatrixUnlearningRate );
170  }
171 private:
172 
173  /// \brief Performs a rank one update to the cholesky factor.
174  ///
175  /// This also requries an update of the inverse cholesky factor, that is the only reason, it exists.
176  void rankOneUpdate(double alpha, double beta, RealVector const& v){
177  m_mutationDistribution.rankOneUpdate(alpha,beta,v);
178  }
179 
180  /// \brief Performs an update step which makes the distribution more round
181  ///
182  /// This is called, when the distribution is too successful as this indicates that the step size
183  /// in some direction is too small to be useful
184  void roundUpdate(){
185  double evolutionpathUpdateWeight = m_evolutionPathLearningRate * ( 2.-m_evolutionPathLearningRate );
186  m_evolutionPath *= 1 - m_evolutionPathLearningRate;
187  rankOneUpdate(
188  1 - m_covarianceMatrixLearningRate+evolutionpathUpdateWeight,
189  m_covarianceMatrixLearningRate,
190  m_evolutionPath
191  );
192  }
193 };
194 }
195 
196 #endif