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  */
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  void read( InArchive & archive );
105  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 Accesses the current step size. */
131  double sigma() const {
132  return m_sigma;
133  }
134 
135  /** \brief Accesses the current step size. */
136  void setSigma(double sigma) {
137  m_sigma = sigma;
138  }
139 
140 
141  /** \brief Accesses the current population mean. */
142  RealVector const& mean() const {
143  return m_mean;
144  }
145 
146  /** \brief Accesses the current weighting vector. */
147  RealVector const& weights() const {
148  return m_weights;
149  }
150 
151  /** \brief Accesses the evolution path for the covariance matrix update. */
152  RealVector const& evolutionPath() const {
153  return m_evolutionPathC;
154  }
155 
156  /** \brief Accesses the evolution path for the step size update. */
157  RealVector const& evolutionPathSigma() const {
158  return m_evolutionPathSigma;
159  }
160 
161  /** \brief Accesses the covariance matrix of the normal distribution used for generating offspring individuals. */
162  RealMatrix const& covarianceMatrix() const {
164  }
165 
166  /**
167  * \brief Accesses the recombination type.
168  */
170  return m_recombinationType;
171  }
172 
173  /**
174  * \brief Returns a mutable reference to the recombination type.
175  */
177  return m_recombinationType;
178  }
179 
180  /**
181  * \brief Returns a const reference tothe lower bound on sigma times smalles eigenvalue.
182  */
183  const double & lowerBound() const {
184  return m_lowerBound;
185  }
186 
187  /**
188  * \brief Returns a mutable reference to the lower bound on sigma times smalles eigenvalue.
189  */
190  double& lowerBound() {
191  return m_lowerBound;
192  }
193 
194  /**
195  * \brief Returns the size of the parent population \f$\mu\f$.
196  */
197  std::size_t mu() const {
198  return m_mu;
199  }
200 
201  /**
202  * \brief Returns a mutabl rference to the size of the parent population \f$\mu\f$.
203  */
204  std::size_t& mu(){
205  return m_mu;
206  }
207 
208  /**
209  * \brief Returns a immutable reference to the size of the offspring population \f$\mu\f$.
210  */
211  std::size_t lambda()const{
212  return m_lambda;
213  }
214 
215  /**
216  * \brief Returns a mutable reference to the size of the offspring population \f$\mu\f$.
217  */
218  std::size_t & lambda(){
219  return m_lambda;
220  }
221 
222  /**
223  * \brief Returns eigenvectors of covariance matrix (not considering step size)
224  */
225  RealMatrix const& eigenVectors() const {
227  }
228 
229  /**
230  * \brief Returns a eigenvectors of covariance matrix (not considering step size)
231  */
232  RealVector const& eigenValues() const {
234  }
235 
236  /**
237  * \brief Returns condition of covariance matrix
238  */
239  double condition() const {
240  RealVector const& eigenValues = m_mutationDistribution.eigenValues();
241  return max(eigenValues)/min(eigenValues);
242  }
243 
244 
245  protected:
246  /**
247  * \brief Updates the strategy parameters based on the supplied offspring population.
248  */
250 
251  std::size_t m_numberOfVariables; ///< Stores the dimensionality of the search space.
252  std::size_t m_mu; ///< The size of the parent population.
253  std::size_t m_lambda; ///< The size of the offspring population, needs to be larger than mu.
254 
255  RecombinationType m_recombinationType; ///< Stores the recombination type.
256 
257  double m_sigma;
258  double m_cC;
259  double m_c1;
260  double m_cMu;
261  double m_cSigma;
262  double m_dSigma;
263  double m_muEff;
264 
265  double m_lowerBound;
266 
267  RealVector m_mean;
268  RealVector m_weights;
269 
270  RealVector m_evolutionPathC;
272 
273  std::size_t m_counter; ///< counter for generations
274 
276  };
277 }
278 
279 #endif