CMA.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Implements the most recent version of the non-elitist CMA-ES.
6  *
7  * Hansen, N. The CMA Evolution Startegy: A Tutorial, June 28, 2011
8  * and the eqation numbers refer to this publication (retrieved April 2014).
9  *
10  *
11  * \author Thomas Voss and Christian Igel
12  * \date April 2014
13  *
14  * \par Copyright 1995-2015 Shark Development Team
15  *
16  * <BR><HR>
17  * This file is part of Shark.
18  * <http://image.diku.dk/shark/>
19  *
20  * Shark is free software: you can redistribute it and/or modify
21  * it under the terms of the GNU Lesser General Public License as published
22  * by the Free Software Foundation, either version 3 of the License, or
23  * (at your option) any later version.
24  *
25  * Shark is distributed in the hope that it will be useful,
26  * but WITHOUT ANY WARRANTY; without even the implied warranty of
27  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28  * GNU Lesser General Public License for more details.
29  *
30  * You should have received a copy of the GNU Lesser General Public License
31  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
32  *
33  */
34 //===========================================================================
35 
36 
37 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_H
38 #define SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_H
39 
40 #include <shark/Core/DLLSupport.h>
44 
45 
46 namespace shark {
47 /**
48 * \brief Implements the CMA-ES.
49 *
50 * The algorithm is described in
51 *
52 * Hansen, N., S. Kern (2004). Evaluating the CMA Evolution Strategy
53 * on Multimodal Test Functions. In Proceedings of the Eighth
54 * International Conference on Parallel Problem Solving from Nature
55 * (PPSN VIII), pp. 282-291, LNCS, Springer-Verlag
56 */
57 class CMA : public AbstractSingleObjectiveOptimizer<RealVector >
58 {
59 public:
60  /**
61  * \brief Models the recombination type.
62  */
64  EQUAL = 0,
65  LINEAR = 1,
67  };
68 
69  /**
70  * \brief Default c'tor.
71  */
72  SHARK_EXPORT_SYMBOL CMA(DefaultRngType& rng = Rng::globalRng);
73 
74  /// \brief From INameable: return the class name.
75  std::string name() const
76  { return "CMA-ES"; }
77 
78  /**
79  * \brief Calculates the center of gravity of the given population \f$ \in \mathbb{R}^d\f$.
80  *
81  *
82  */
83  template<typename Container, typename Extractor>
84  RealVector weightedSum( const Container & container, const RealVector & weights, const Extractor & e ) {
85 
86  RealVector result( m_numberOfVariables, 0. );
87 
88  for( std::size_t j = 0; j < container.size(); j++ )
89  result += weights( j ) * e( container[j] );
90 
91  return( result );
92  }
93 
94  /**
95  * \brief Calculates lambda for the supplied dimensionality n.
96  */
97  SHARK_EXPORT_SYMBOL static std::size_t suggestLambda( std::size_t dimension ) ;
98 
99  /**
100  * \brief Calculates mu for the supplied lambda and the recombination strategy.
101  */
102  SHARK_EXPORT_SYMBOL static std::size_t suggestMu( std::size_t lambda, RecombinationType recomb = SUPERLINEAR ) ;
103 
104  SHARK_EXPORT_SYMBOL void read( InArchive & archive );
105  SHARK_EXPORT_SYMBOL void write( OutArchive & archive ) const;
106 
108  /**
109  * \brief Initializes the algorithm for the supplied objective function.
110  */
112 
113  /**
114  * \brief Initializes the algorithm for the supplied objective function.
115  */
117  ObjectiveFunctionType& function,
118  SearchPointType const& initialSearchPoint,
119  std::size_t lambda,
120  std::size_t mu,
121  double initialSigma,
122  const boost::optional< RealMatrix > & initialCovarianceMatrix = boost::optional< RealMatrix >()
123  );
124 
125  /**
126  * \brief Executes one iteration of the algorithm.
127  */
128  SHARK_EXPORT_SYMBOL void step(ObjectiveFunctionType const& function);
129 
130  /// \brief sets the initial step length sigma
131  ///
132  /// It is by default <=0 which means that sigma =1/sqrt(numVariables)
133  void setInitialSigma(double initSigma){
134  m_initSigma = initSigma;
135  }
136 
137  /** \brief Accesses the current step size. */
138  double sigma() const {
139  return m_sigma;
140  }
141 
142  /** \brief Accesses the current population mean. */
143  RealVector const& mean() const {
144  return m_mean;
145  }
146 
147  /** \brief Accesses the current weighting vector. */
148  RealVector const& weights() const {
149  return m_weights;
150  }
151 
152  /** \brief Accesses the evolution path for the covariance matrix update. */
153  RealVector const& evolutionPath() const {
154  return m_evolutionPathC;
155  }
156 
157  /** \brief Accesses the evolution path for the step size update. */
158  RealVector const& evolutionPathSigma() const {
159  return m_evolutionPathSigma;
160  }
161 
162  /** \brief Accesses the covariance matrix of the normal distribution used for generating offspring individuals. */
163  RealMatrix const& covarianceMatrix() const {
164  return m_mutationDistribution.covarianceMatrix();
165  }
166 
167  /**
168  * \brief Accesses the recombination type.
169  */
171  return m_recombinationType;
172  }
173 
174  /**
175  * \brief Returns a mutable reference to the recombination type.
176  */
178  return m_recombinationType;
179  }
180 
181  /**
182  * \brief Returns a const reference tothe lower bound on sigma times smalles eigenvalue.
183  */
184  const double & lowerBound() const {
185  return m_lowerBound;
186  }
187 
188  /**
189  * \brief Returns the size of the parent population \f$\mu\f$.
190  */
191  std::size_t mu() const {
192  return m_mu;
193  }
194 
195  /// \brief Sets the number of selected samples
196  void setMu(std::size_t mu){
197  m_mu = mu;
198  m_userSetMu = true;
199  }
200  /// \brief Sets the number of sampled points
201  void setLambda(std::size_t lambda){
202  m_lambda = lambda;
203  m_userSetLambda = true;
204  }
205 
206  /**
207  * \brief Returns a immutable reference to the size of the offspring population \f$\mu\f$.
208  */
209  std::size_t lambda()const{
210  return m_lambda;
211  }
212 
213  /**
214  * \brief Returns eigenvectors of covariance matrix (not considering step size)
215  */
216  RealMatrix const& eigenVectors() const {
217  return m_mutationDistribution.eigenVectors();
218  }
219 
220  /**
221  * \brief Returns a eigenvectors of covariance matrix (not considering step size)
222  */
223  RealVector const& eigenValues() const {
224  return m_mutationDistribution.eigenValues();
225  }
226 
227  /**
228  * \brief Returns condition of covariance matrix
229  */
230  double condition() const {
231  RealVector const& eigenValues = m_mutationDistribution.eigenValues();
232  return max(eigenValues)/min(eigenValues);
233  }
234 
235 
236 protected:
237  /// \brief The type of individual used for the CMA
239 
240  /// \brief Samples lambda individuals from the search distribution
241  SHARK_EXPORT_SYMBOL std::vector<IndividualType> generateOffspring( ) const;
242 
243  /// \brief Updates the strategy parameters based on the supplied offspring population.
244  SHARK_EXPORT_SYMBOL void updatePopulation( std::vector<IndividualType > const& offspring ) ;
245 
247  std::vector<SearchPointType> const& points,
248  std::vector<ResultType> const& functionValues,
249  std::size_t lambda,
250  std::size_t mu,
251  double initialSigma
252  );
253 private:
254 
255  std::size_t m_numberOfVariables; ///< Stores the dimensionality of the search space.
256  std::size_t m_mu; ///< The size of the parent population.
257  std::size_t m_lambda; ///< The size of the offspring population, needs to be larger than mu.
258 
259  bool m_userSetMu; /// <The user set a value via setMu, do not overwrite with default
260  bool m_userSetLambda; /// <The user set a value via setMu, do not overwrite with default
261  double m_initSigma; ///< use provided initial value of sigma<=0 =>algorithm chooses
262 
263  RecombinationType m_recombinationType; ///< Stores the recombination type.
264 
265 
266  double m_sigma;
267  double m_cC;
268  double m_c1;
269  double m_cMu;
270  double m_cSigma;
271  double m_dSigma;
272  double m_muEff;
273 
274  double m_lowerBound;
275 
276  RealVector m_mean;
277  RealVector m_weights;
278 
279  RealVector m_evolutionPathC;
280  RealVector m_evolutionPathSigma;
281 
282  std::size_t m_counter; ///< counter for generations
283 
284  MultiVariateNormalDistribution m_mutationDistribution;
285  DefaultRngType* mpe_rng;
286 };
287 }
288 
289 #endif