CMSA.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Implements the CMSA.
6  *
7  * The algorithm is described in
8  *
9  * H. G. Beyer, B. Sendhoff (2008).
10  * Covariance Matrix Adaptation Revisited: The CMSA Evolution Strategy
11  * In Proceedings of the Tenth International Conference on Parallel Problem Solving from Nature
12  * (PPSN X), pp. 123-132, LNCS, Springer-Verlag
13  *
14  * \par Copyright (c) 1998-2008:
15  * Institut für Neuroinformatik
16  *
17  * \author -
18  * \date -
19  *
20  *
21  * \par Copyright 1995-2015 Shark Development Team
22  *
23  * <BR><HR>
24  * This file is part of Shark.
25  * <http://image.diku.dk/shark/>
26  *
27  * Shark is free software: you can redistribute it and/or modify
28  * it under the terms of the GNU Lesser General Public License as published
29  * by the Free Software Foundation, either version 3 of the License, or
30  * (at your option) any later version.
31  *
32  * Shark is distributed in the hope that it will be useful,
33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
35  * GNU Lesser General Public License for more details.
36  *
37  * You should have received a copy of the GNU Lesser General Public License
38  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
39  *
40  */
41 //===========================================================================
42 
43 
44 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_CMSA_H
45 #define SHARK_ALGORITHMS_DIRECTSEARCH_CMSA_H
46 
47 #include <shark/Core/DLLSupport.h>
51 
52 
53 namespace shark {
54 /**
55 * \brief Implements the CMSA.
56 *
57 * The algorithm is described in
58 *
59 * H. G. Beyer, B. Sendhoff (2008).
60 * Covariance Matrix Adaptation Revisited: The CMSA Evolution Strategy
61 * In Proceedings of the Tenth International Conference on Parallel Problem Solving from Nature
62 * (PPSN X), pp. 123-132, LNCS, Springer-Verlag
63 */
64 class CMSA : public AbstractSingleObjectiveOptimizer<RealVector > {
65  /** \cond */
66 
67  struct LightChromosome {
68  RealVector step;
69  double sigma;
70  };
71  /** \endcond */
72 public:
73 
74  /// \brief Default c'tor.
75  CMSA(DefaultRngType& rng = Rng::globalRng)
76  : m_mu( 100 )
77  , m_lambda( 200 )
78  , m_userSetMu(false)
79  ,m_userSetLambda(false)
80  , m_initSigma(-1)
81  , mpe_rng(&rng){
83  }
84 
85  /// \brief From INameable: return the class name.
86  std::string name() const
87  { return "CMSA"; }
88 
89  /// \brief Calculates the center of gravity of the given population \f$ \in \mathbb{R}^d\f$.
90  template<typename Container, typename Extractor>
91  RealVector cog( const Container & container, const Extractor & e ) {
92 
93  RealVector result( m_numberOfVariables, 0. );
94 
95  for( std::size_t j = 0; j < container.size(); j++ )
96  result += 1./m_mu * e( container[j] );
97 
98  return result;
99  }
100 
101  SHARK_EXPORT_SYMBOL void read( InArchive & archive );
102  SHARK_EXPORT_SYMBOL void write( OutArchive & archive ) const;
103 
105 
106  /// \brief Initializes the algorithm for the supplied objective function.
108 
109  /**
110  * \brief Initializes the algorithm for the supplied objective function.
111  */
113  ObjectiveFunctionType& function,
114  SearchPointType const& initialSearchPoint,
115  std::size_t lambda,
116  std::size_t mu,
117  double initialSigma,
118  const boost::optional< RealMatrix > & initialCovarianceMatrix = boost::optional< RealMatrix >()
119  );
120 
121  /// \brief Executes one iteration of the algorithm.
122  SHARK_EXPORT_SYMBOL void step(ObjectiveFunctionType const& function);
123 
124  /// \brief sets the initial step length sigma
125  ///
126  /// It is by default <=0 which means that sigma =1/sqrt(numVariables)
127  void setInitialSigma(double initSigma){
128  m_initSigma = initSigma;
129  }
130 
131  /// \brief Sets the number of selected samples
132  void setMu(std::size_t mu){
133  m_mu = mu;
134  m_userSetMu = true;
135  }
136  /// \brief Sets the number of sampled points
137  void setLambda(std::size_t lambda){
138  m_lambda = lambda;
139  m_userSetLambda = true;
140  }
141  /// \brief Accesses the size of the parent population.
142  std::size_t mu() const {
143  return m_mu;
144  }
145 
146  /// \brief Accesses the size of the offspring population.
147  std::size_t lambda() const {
148  return m_lambda;
149  }
150 protected:
151  /// \brief The type of individual used by the CMSA
153 
154  /// \brief Samples lambda individuals from the search distribution
155  SHARK_EXPORT_SYMBOL std::vector<IndividualType> generateOffspring( ) const;
156 
157  /// \brief Updates the strategy parameters based on the supplied offspring population.
158  SHARK_EXPORT_SYMBOL void updatePopulation( std::vector< IndividualType > const& offspring );
159 
160  /// \brief Initializes the internal data structures of the CMSA
162  std::vector<SearchPointType> const& points,
163  std::vector<ResultType> const& functionValues,
164  std::size_t lambda,
165  std::size_t mu,
166  double initialSigma
167  );
168 private:
169  std::size_t m_numberOfVariables; ///< Stores the dimensionality of the search space.
170  std::size_t m_mu; ///< The size of the parent population.
171  std::size_t m_lambda; ///< The size of the offspring population, needs to be larger than mu.
172 
173  bool m_userSetMu; /// <The user set a value via setMu, do not overwrite with default
174  bool m_userSetLambda; /// <The user set a value via setMu, do not overwrite with default
175  double m_initSigma; ///< The initial step size
176 
177  double m_sigma; ///< The current step size.
178  double m_cSigma;
179  double m_cC; ///< Constant for adapting the covariance matrix.
180 
181  RealVector m_mean; ///< The current cog of the population.
182 
183  MultiVariateNormalDistribution m_mutationDistribution; ///< Multi-variate normal mutation distribution.
184  DefaultRngType* mpe_rng;
185 };
186 }
187 
188 #endif