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-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
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>
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  */
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  */
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 
145  /**
146  * \brief Initializes the algorithm for the supplied objective function and the initial mean p.
147  */
149 
150  /**
151  * \brief Inits the Cross Entropy, only with the objective function
152  */
154 
155  /**
156  * \brief Initializes the algorithm for the supplied objective function.
157  */
159  ObjectiveFunctionType& function,
160  SearchPointType const& initialSearchPoint,
161  unsigned int populationSize,
162  unsigned int selectionSize,
163  RealVector initialSigma
164  );
165 
166  /**
167  * \brief Executes one iteration of the algorithm.
168  */
169  SHARK_EXPORT_SYMBOL void step(ObjectiveFunctionType const& function);
170 
171  /** \brief Access the current variance. */
172  RealVector const& variance() const {
173  return m_variance;
174  }
175 
176  /** \brief Set the variance to a vector */
177  void setVariance(RealVector variance) {
178  assert(variance.size() == m_variance.size());
180  }
181 
182  /** \brief Set all variance values */
183  void setVariance(double variance){
184  m_variance = blas::repeat(variance,m_variance.size());
185  }
186 
187  /** \brief Access the current population mean. */
188  RealVector const& mean() const {
189  return m_mean;
190  }
191 
192  /**
193  * \brief Returns the size of the parent population.
194  */
195  unsigned int selectionSize() const {
196  return m_selectionSize;
197  }
198 
199  /**
200  * \brief Returns a mutable reference to the size of the parent population.
201  */
202  unsigned int& selectionSize(){
203  return m_selectionSize;
204  }
205 
206  /**
207  * \brief Returns a immutable reference to the size of the population.
208  */
209  unsigned int populationSize()const{
210  return m_populationSize;
211  }
212 
213  /**
214  * \brief Returns a mutable reference to the size of the population.
215  */
216  unsigned int & populationSize(){
217  return m_populationSize;
218  }
219 
220  /**
221  * \brief Set the noise type from a raw pointer.
222  */
223  void setNoiseType( INoiseType* noiseType ) {
224  m_noise.reset();
225  m_noise = boost::shared_ptr<INoiseType> (noiseType);
226  }
227 
228  /**
229  * \brief Get an immutable reference to Noise Type.
230  */
231  const INoiseType &getNoiseType( ) const {
232  return *m_noise.get();
233  }
234 
235 
236  protected:
237  /**
238  * \brief Updates the strategy parameters based on the supplied parent population.
239  */
241 
242  std::size_t m_numberOfVariables; ///< Stores the dimensionality of the search space.
243  unsigned int m_selectionSize; ///< Number of vectors chosen when updating distribution parameters.
244  unsigned int m_populationSize; ///< Number of vectors sampled in a generation.
245 
246  RealVector m_variance; ///< Variance for sample parameters.
247 
248 
249  RealVector m_mean; ///< The mean of the population.
250 
251  unsigned m_counter; ///< Counter for generations.
252 
253  Normal< Rng::rng_type > m_distribution; ///< Normal distribution.
254  StrongNoisePtr m_noise; ///< Noise type to apply in the update of distribution parameters.
255  };
256 }
257 
258 #endif