MOCMA.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Implements the generational Multi-objective Covariance Matrix Adapation ES.
5  *
6  *
7  *
8  * \author T.Voss
9  * \date 2010
10  *
11  *
12  * \par Copyright 1995-2017 Shark Development Team
13  *
14  * <BR><HR>
15  * This file is part of Shark.
16  * <http://shark-ml.org/>
17  *
18  * Shark is free software: you can redistribute it and/or modify
19  * it under the terms of the GNU Lesser General Public License as published
20  * by the Free Software Foundation, either version 3 of the License, or
21  * (at your option) any later version.
22  *
23  * Shark is distributed in the hope that it will be useful,
24  * but WITHOUT ANY WARRANTY; without even the implied warranty of
25  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26  * GNU Lesser General Public License for more details.
27  *
28  * You should have received a copy of the GNU Lesser General Public License
29  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
30  *
31  */
32 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_MOCMA
33 #define SHARK_ALGORITHMS_DIRECT_SEARCH_MOCMA
34 
35 // MOO specific stuff
36 #include <shark/Algorithms/DirectSearch/Operators/Indicators/HypervolumeIndicator.h>
37 #include <shark/Algorithms/DirectSearch/Operators/Indicators/AdditiveEpsilonIndicator.h>
38 #include <shark/Algorithms/DirectSearch/Operators/Selection/IndicatorBasedSelection.h>
39 #include <shark/Algorithms/DirectSearch/Operators/Evaluation/PenalizingEvaluator.h>
40 #include <shark/Algorithms/DirectSearch/CMA/CMAIndividual.h>
41 
42 
43 #include <shark/Algorithms/AbstractMultiObjectiveOptimizer.h>
44 
45 namespace shark {
46 
47 /**
48  * \brief Implements the generational MO-CMA-ES.
49  *
50  * Please see the following papers for further reference:
51  * - Igel, Suttorp and Hansen. Steady-state Selection and Efficient Covariance Matrix Update in the Multi-Objective CMA-ES.
52  * - Voß, Hansen and Igel. Improved Step Size Adaptation for the MO-CMA-ES.
53  */
54 template<typename Indicator=HypervolumeIndicator>
55 class IndicatorBasedMOCMA : public AbstractMultiObjectiveOptimizer<RealVector >{
56 public:
57  enum NotionOfSuccess{
58  IndividualBased,
59  PopulationBased
60  };
61 public:
62 
63  IndicatorBasedMOCMA(random::rng_type& rng= random::globalRng):mpe_rng(&rng) {
64  m_individualSuccessThreshold = 0.44;
65  initialSigma() = 1.0;
66  mu() = 100;
67  notionOfSuccess() = PopulationBased;
68  this->m_features |= AbstractMultiObjectiveOptimizer<RealVector >::CAN_SOLVE_CONSTRAINED;
69  }
70 
71  /**
72  * \brief Returns the name of the algorithm.
73  */
74  std::string name() const {
75  return "MOCMA";
76  }
77 
78  std::size_t mu()const{
79  return m_mu;
80  }
81  std::size_t& mu(){
82  return m_mu;
83  }
84 
85  /// \brief The number of points used for initialization of the algorithm.
86  std::size_t numInitPoints() const{
87  return m_mu;
88  }
89 
90  double initialSigma()const{
91  return m_initialSigma;
92  }
93  double& initialSigma(){
94  return m_initialSigma;
95  }
96 
97  NotionOfSuccess notionOfSuccess()const{
98  return m_notionOfSuccess;
99  }
100  NotionOfSuccess& notionOfSuccess(){
101  return m_notionOfSuccess;
102  }
103  void read( InArchive & archive ){
104  archive >> BOOST_SERIALIZATION_NVP(m_parents);
105  archive >> BOOST_SERIALIZATION_NVP(m_mu);
106  archive >> BOOST_SERIALIZATION_NVP(m_best);
107 
108  archive >> BOOST_SERIALIZATION_NVP(m_selection);
109  archive >> BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
110  archive >> BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
111  archive >> BOOST_SERIALIZATION_NVP(m_initialSigma);
112  }
113  void write( OutArchive & archive ) const{
114  archive << BOOST_SERIALIZATION_NVP(m_parents);
115  archive << BOOST_SERIALIZATION_NVP(m_mu);
116  archive << BOOST_SERIALIZATION_NVP(m_best);
117 
118  archive << BOOST_SERIALIZATION_NVP(m_selection);
119  archive << BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
120  archive << BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
121  archive << BOOST_SERIALIZATION_NVP(m_initialSigma);
122  }
123 
124  using AbstractMultiObjectiveOptimizer<RealVector >::init;
125  /**
126  * \brief Initializes the algorithm for the supplied objective function.
127  *
128  * \param [in] function The objective function.
129  * \param [in] initialSearchPoints A set of intiial search points.
130  */
131  void init(
132  ObjectiveFunctionType const& function,
133  std::vector<SearchPointType> const& initialSearchPoints
134  ){
135  checkFeatures(function);
136  std::vector<RealVector> values(initialSearchPoints.size());
137  for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
138  SHARK_RUNTIME_CHECK(function.isFeasible(initialSearchPoints[i]),"Starting point(s) not feasible");
139  values[i] = function.eval(initialSearchPoints[i]);
140  }
141  this->doInit(initialSearchPoints,values,mu(),initialSigma() );
142  }
143 
144  /**
145  * \brief Executes one iteration of the algorithm.
146  *
147  * \param [in] function The function to iterate upon.
148  */
149  void step( ObjectiveFunctionType const& function ) {
150  std::vector<IndividualType> offspring = generateOffspring();
151  PenalizingEvaluator penalizingEvaluator;
152  penalizingEvaluator( function, offspring.begin(), offspring.end() );
153  updatePopulation(offspring);
154  }
155 
156  Indicator& indicator(){
157  return m_selection.indicator();
158  }
159  Indicator const& indicator()const{
160  return m_selection.indicator();
161  }
162 protected:
163  /// \brief The individual type of the SteadyState-MOCMA.
164  typedef CMAIndividual<RealVector> IndividualType;
165 
166  void doInit(
167  std::vector<SearchPointType> const& initialSearchPoints,
168  std::vector<ResultType> const& functionValues,
169  std::size_t mu,
170  double initialSigma
171  ){
172  SIZE_CHECK(initialSearchPoints.size() > 0);
173  m_mu = mu;
174  m_initialSigma = initialSigma;
175 
176  m_best.resize( mu );
177  m_parents.resize( mu );
178  std::size_t noVariables = initialSearchPoints[0].size();
179 
180  //if the number of supplied points is smaller than mu, fill everything in
181  std::size_t numPoints = 0;
182  if(initialSearchPoints.size()<=mu){
183  numPoints = initialSearchPoints.size();
184  for(std::size_t i = 0; i != numPoints; ++i){
185  m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
186  m_parents[i].searchPoint() = initialSearchPoints[i];
187  m_parents[i].penalizedFitness() = functionValues[i];
188  m_parents[i].unpenalizedFitness() = functionValues[i];
189  }
190  }
191  //copy points randomly
192  for(std::size_t i = numPoints; i != mu; ++i){
193  std::size_t index = random::discrete(*mpe_rng,std::size_t(0),initialSearchPoints.size()-1);
194  m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
195  m_parents[i].searchPoint() = initialSearchPoints[index];
196  m_parents[i].penalizedFitness() = functionValues[index];
197  m_parents[i].unpenalizedFitness() = functionValues[index];
198  }
199  //create initial mu best points
200  for(std::size_t i = 0; i != mu; ++i){
201  m_best[i].point = m_parents[i].searchPoint();
202  m_best[i].value = m_parents[i].unpenalizedFitness();
203  }
204 
205  indicator().init(functionValues.front().size(),mu,*mpe_rng);
206  }
207 
208  std::vector<IndividualType> generateOffspring()const{
209  std::vector<IndividualType> offspring(mu());
210  for(std::size_t i = 0; i != mu(); ++i){
211  std::size_t parentId = i;
212  offspring[i] = m_parents[parentId];
213  offspring[i].mutate(*mpe_rng);
214  offspring[i].parent() = parentId;
215  }
216  return offspring;
217  }
218 
219  void updatePopulation( std::vector<IndividualType> const& offspringVec) {
220  m_parents.insert(m_parents.end(),offspringVec.begin(),offspringVec.end());
221  m_selection( m_parents, mu());
222 
223  //determine from the selection which parent-offspring pair has been successful
224  for (std::size_t i = 0; i < mu(); i++) {
225  CMAChromosome::IndividualSuccess offspringSuccess = CMAChromosome::Unsuccessful;
226  //new update: an offspring is successful if it is selected
227  if ( m_notionOfSuccess == PopulationBased && m_parents[mu()+i].selected()) {
228  m_parents[mu()+i].updateAsOffspring();
229  offspringSuccess = CMAChromosome::Successful;
230  }
231  //old update: an offspring is successfull if it is better than its parent
232  else if ( m_notionOfSuccess == IndividualBased && m_parents[mu()+i].selected() && m_parents[mu()+i].rank() <= m_parents[i].rank()) {
233  m_parents[mu()+i].updateAsOffspring();
234  offspringSuccess = CMAChromosome::Successful;
235  }
236  if(m_parents[i].selected())
237  m_parents[i].updateAsParent(offspringSuccess);
238  }
239 
240  //partition the selected individuals to the front and remove the unselected ones
241  std::partition(m_parents.begin(), m_parents.end(),[](IndividualType const& ind){return ind.selected();});
242  m_parents.erase(m_parents.begin()+mu(),m_parents.end());
243 
244  //update solution set
245  for (std::size_t i = 0; i < mu(); i++) {
246  noalias(m_best[i].point) = m_parents[i].searchPoint();
247  m_best[i].value = m_parents[i].unpenalizedFitness();
248  }
249  }
250 
251  std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
252 
253 private:
254  std::size_t m_mu; ///< Size of parent population
255 
256  IndicatorBasedSelection<Indicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
257 
258  NotionOfSuccess m_notionOfSuccess; ///< Flag for deciding whether the improved step-size adaptation shall be used.
259  double m_individualSuccessThreshold;
260  double m_initialSigma;
261  random::rng_type* mpe_rng;
262 };
263 
264 typedef IndicatorBasedMOCMA< HypervolumeIndicator > MOCMA;
265 typedef IndicatorBasedMOCMA< AdditiveEpsilonIndicator > EpsilonMOCMA;
266 
267 }
268 
269 #endif