CrossEntropyMethod.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  * \brief Implements the Cross Entropy Algorithm.
5  *
6  * Christophe Thiery, Bruno Scherrer. Improvements on Learning Tetris with Cross Entropy.
7  * International Computer Games Association Journal, ICGA, 2009, 32. <inria-00418930>
8  *
9  *
10  * \author Jens Holm, Mathias Petræus and Mark Wulff
11  * \date January 2016
12  *
13  * \par Copyright 1995-2017 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://shark-ml.org/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 //===========================================================================
34 
35 
36 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_CROSSENTROPY_H
37 #define SHARK_ALGORITHMS_DIRECT_SEARCH_CROSSENTROPY_H
38 
39 #include <shark/Core/DLLSupport.h>
40 #include <shark/Algorithms/AbstractSingleObjectiveOptimizer.h>
41 #include <shark/Core/Random.h>
42 #include <shark/Algorithms/DirectSearch/Individual.h>
43 
44 #include <boost/shared_ptr.hpp>
45 
46 namespace shark {
47 
48  /**
49  * \brief Implements the Cross Entropy Method.
50  *
51  * This class implements the noisy cross entropy method
52  * as descibed in the following article.
53  *
54  * Christophe Thiery, Bruno Scherrer. Improvements on Learning Tetris with Cross Entropy.
55  * International Computer Games Association Journal, ICGA, 2009, 32. <inria-00418930>
56  *
57  * The algorithm aims to minimize an objective function through stochastic search.
58  * It works iteratively until a certain stopping criteria is met. At each
59  * iteration, it samples a number of vectors from a Gaussian distribution
60  * and evaluates each of these against the supplied objective function.
61  * Based on the return value from the objective function, a subset of the
62  * the best ranked vectors are chosen to update the search parameters
63  * of the next generation.
64  *
65  * The mean of the Gaussian distribution is set to the centroid of the best ranked
66  * vectors, and the variance is set to the variance of the best ranked
67  * vectors in each individual dimension.
68  *
69  */
70  class CrossEntropyMethod : public AbstractSingleObjectiveOptimizer<RealVector >
71  {
72  public:
73 
74  /**
75  * \brief Interface class for noise type.
76  */
77  class INoiseType {
78  public:
79  virtual double noiseValue (int t) const { return 0.0; };
80  virtual std::string name() const { return std::string("Default noise of 0"); }
81  };
82 
83  /**
84  * \brief Smart pointer for noise type.
85  */
86  typedef boost::shared_ptr<INoiseType> StrongNoisePtr;
87 
88  /**
89  * \brief Constant noise term z_t = noise.
90  */
91  class ConstantNoise : public INoiseType {
92  public:
93  ConstantNoise ( double noise ) { m_noise = noise; };
94  virtual double noiseValue (int t) const { return std::max(m_noise, 0.0); }
95  virtual std::string name() const {
96  std::stringstream ss;
97  ss << "z(t) = " << m_noise;
98  return std::string(ss.str());
99  }
100  private:
101  double m_noise;
102  };
103 
104  /**
105  * \brief Linear noise term z_t = a + t / b.
106  */
107  class LinearNoise : public INoiseType {
108  public:
109  LinearNoise ( double a, double b ) { m_a = a; m_b = b; };
110  virtual double noiseValue (int t) const { return std::max(m_a + (t * m_b), 0.0); }
111  virtual std::string name() const {
112  std::stringstream ss;
113  std::string sign = (m_b < 0.0 ? " - " : " + ");
114  ss << "z(t) = " << m_a << sign << "t * " << std::abs(m_b);
115  return std::string(ss.str());
116  }
117  private:
118  double m_a, m_b;
119  };
120 
121 
122  /**
123  * \brief Default c'tor.
124  */
125  SHARK_EXPORT_SYMBOL CrossEntropyMethod();
126 
127  /// \brief From INameable: return the class name.
128  std::string name() const
129  { return "Cross Entropy Method"; }
130 
131  /**
132  * \brief Sets default value for Population size.
133  */
134  SHARK_EXPORT_SYMBOL static unsigned suggestPopulationSize( ) ;
135 
136  /**
137  * \brief Calculates selection size for the supplied population size.
138  */
139  SHARK_EXPORT_SYMBOL static unsigned suggestSelectionSize( unsigned int populationSize ) ;
140 
141  void read( InArchive & archive );
142  void write( OutArchive & archive ) const;
143 
144  using AbstractSingleObjectiveOptimizer<RealVector >::init;
145  /**
146  * \brief Initializes the algorithm for the supplied objective function and the initial mean p.
147  */
148  SHARK_EXPORT_SYMBOL void init( ObjectiveFunctionType const& function, SearchPointType const& p);
149 
150  /**
151  * \brief Initializes the algorithm for the supplied objective function.
152  */
153  SHARK_EXPORT_SYMBOL void init(
154  ObjectiveFunctionType const& function,
155  SearchPointType const& initialSearchPoint,
156  unsigned int populationSize,
157  unsigned int selectionSize,
158  RealVector initialSigma
159  );
160 
161  /**
162  * \brief Executes one iteration of the algorithm.
163  */
164  SHARK_EXPORT_SYMBOL void step(ObjectiveFunctionType const& function);
165 
166  /** \brief Access the current variance. */
167  RealVector const& variance() const {
168  return m_variance;
169  }
170 
171  /** \brief Set the variance to a vector */
172  void setVariance(RealVector variance) {
173  assert(variance.size() == m_variance.size());
174  m_variance = variance;
175  }
176 
177  /** \brief Set all variance values */
178  void setVariance(double variance){
179  m_variance = blas::repeat(variance,m_variance.size());
180  }
181 
182  /** \brief Access the current population mean. */
183  RealVector const& mean() const {
184  return m_mean;
185  }
186 
187  /**
188  * \brief Returns the size of the parent population.
189  */
190  unsigned int selectionSize() const {
191  return m_selectionSize;
192  }
193 
194  /**
195  * \brief Returns a mutable reference to the size of the parent population.
196  */
197  unsigned int& selectionSize(){
198  return m_selectionSize;
199  }
200 
201  /**
202  * \brief Returns a immutable reference to the size of the population.
203  */
204  unsigned int populationSize()const{
205  return m_populationSize;
206  }
207 
208  /**
209  * \brief Returns a mutable reference to the size of the population.
210  */
211  unsigned int & populationSize(){
212  return m_populationSize;
213  }
214 
215  /**
216  * \brief Set the noise type from a raw pointer.
217  */
218  void setNoiseType( INoiseType* noiseType ) {
219  m_noise.reset();
220  m_noise = boost::shared_ptr<INoiseType> (noiseType);
221  }
222 
223  /**
224  * \brief Get an immutable reference to Noise Type.
225  */
226  const INoiseType &getNoiseType( ) const {
227  return *m_noise.get();
228  }
229 
230 
231  protected:
232  typedef Individual<RealVector, double, RealVector> IndividualType;
233  /**
234  * \brief Updates the strategy parameters based on the supplied parent population.
235  */
236  SHARK_EXPORT_SYMBOL void updateStrategyParameters( std::vector< IndividualType > const& parents ) ;
237 
238  std::size_t m_numberOfVariables; ///< Stores the dimensionality of the search space.
239  unsigned int m_selectionSize; ///< Number of vectors chosen when updating distribution parameters.
240  unsigned int m_populationSize; ///< Number of vectors sampled in a generation.
241 
242  RealVector m_variance; ///< Variance for sample parameters.
243 
244 
245  RealVector m_mean; ///< The mean of the population.
246 
247  unsigned m_counter; ///< Counter for generations.
248 
249  StrongNoisePtr m_noise; ///< Noise type to apply in the update of distribution parameters.
250  };
251 }
252 
253 #endif