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-2015 Shark Development Team
13  *
14  * <BR><HR>
15  * This file is part of Shark.
16  * <http://image.diku.dk/shark/>
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
42 
43 
45 
46 #include <boost/foreach.hpp>
47 
48 namespace shark {
49 
50 /**
51  * \brief Implements the generational MO-CMA-ES.
52  *
53  * Please see the following papers for further reference:
54  * - Igel, Suttorp and Hansen. Steady-state Selection and Efficient Covariance Matrix Update in the Multi-Objective CMA-ES.
55  * - Voß, Hansen and Igel. Improved Step Size Adaptation for the MO-CMA-ES.
56  */
57 template<typename Indicator>
59 public:
60 
64  };
65 
66  std::vector<CMAIndividual<RealVector> > m_pop; ///< Population of size \f$\mu+\mu\f$.
67  std::size_t m_mu;///< Size of parent generation
68 
69  shark::PenalizingEvaluator m_evaluator; ///< Evaluation operator.
70  IndicatorBasedSelection< Indicator > m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
71 
72  NotionOfSuccess m_notionOfSuccess; ///< Flag for deciding whether the improved step-size adaptation shall be used.
75 
76  /**
77  * \brief Default c'tor.
78  */
80  m_individualSuccessThreshold = 0.44;
81  initialSigma() = 1.0;
82  constrainedPenaltyFactor() = 1E-6;
83  mu() = 100;
86 
87  }
88 
89  /**
90  * \brief Returns the name of the algorithm.
91  */
92  std::string name() const {
93  return "MOCMA";
94  }
95 
96  std::size_t mu()const{
97  return m_mu;
98  }
99  std::size_t& mu(){
100  return m_mu;
101  }
102 
103  double initialSigma()const{
104  return m_initialSigma;
105  }
106  double& initialSigma(){
107  return m_initialSigma;
108  }
109 
110  /// \brief Returns the penalty factor for an individual that is outside the feasible area.
111  ///
112  /// The value is multiplied with the distance to the nearest feasible point.
114  return m_evaluator.m_penaltyFactor;
115  }
116 
117  /// \brief Returns a reference to the penalty factor for an individual that is outside the feasible area.
118  ///
119  /// The value is multiplied with the distance to the nearest feasible point.
121  return m_evaluator.m_penaltyFactor;
122  }
123 
125  return m_notionOfSuccess;
126  }
128  return m_notionOfSuccess;
129  }
130 
131  /**
132  * \brief Stores/loads the algorithm's state.
133  * \tparam Archive The type of the archive.
134  * \param [in,out] archive The archive to use for loading/storing.
135  * \param [in] version Currently unused.
136  */
137  template<typename Archive>
138  void serialize(Archive &archive, const unsigned int version) {
139  archive & BOOST_SERIALIZATION_NVP(m_pop);
140  archive & BOOST_SERIALIZATION_NVP(m_mu);
141  archive & BOOST_SERIALIZATION_NVP(m_best);
142  archive & BOOST_SERIALIZATION_NVP(m_evaluator);
143  archive & BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
144  archive & BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
145  archive & BOOST_SERIALIZATION_NVP(m_initialSigma);
146  }
147 
149  /**
150  * \brief Initializes the algorithm for the supplied objective function.
151  * \tparam ObjectiveFunction The type of the objective function,
152  * needs to adhere to the concept of an AbstractObjectiveFunction.
153  * \param [in] function The objective function.
154  * \param [in] startingPoints A set of intiial search points.
155  */
156  void init(
157  ObjectiveFunctionType& function,
158  std::vector<SearchPointType> const& startingPoints
159  ){
160  checkFeatures(function);
161  function.init();
162 
163  m_pop.resize(2 * mu());
164  m_best.resize(mu());
165  std::size_t noVariables = function.numberOfVariables();
166 
167  for(std::size_t i = 0; i != mu(); ++i){
168  CMAIndividual<RealVector> individual(noVariables,m_individualSuccessThreshold,m_initialSigma);
169  individual.searchPoint() = function.proposeStartingPoint();
170  m_pop[i] = individual;
171  }
172  //valuate and create first front
173  m_evaluator(function, m_pop.begin(),m_pop.begin()+mu());
174  for(std::size_t i = 0; i != mu(); ++i){
175  m_best[i].point = m_pop[i].searchPoint();
176  m_best[i].value = m_pop[i].unpenalizedFitness();
177  }
178  }
179 
180  /**
181  * \brief Executes one iteration of the algorithm.
182  *
183  * \param [in] function The function to iterate upon.
184  */
185  void step( ObjectiveFunctionType const& function ) {
186 
187  //generate new offspring, evaluate and select
188  for (std::size_t i = 0; i < mu(); i++) {
189  m_pop[mu()+i] = m_pop[i];
190  m_pop[mu()+i].mutate();
191  }
192  m_evaluator(function, m_pop.begin()+mu(),m_pop.end());
193  m_selection(m_pop,m_mu);
194 
195  //determine from the selection which parent-offspring pair has been successfull
196  for (std::size_t i = 0; i < mu(); i++) {
198  //new update: an offspring is successfull if it is selected
199  if ( m_notionOfSuccess == PopulationBased && m_pop[mu()+i].selected()) {
200  m_pop[mu()+i].updateAsOffspring();
201  offspringSuccess = CMAChromosome::Successful;
202  }
203  //old update: an offspring is successfull if it is better than its parent
204  else if ( m_notionOfSuccess == IndividualBased && m_pop[mu()+i].selected() && m_pop[mu()+i].rank() <= m_pop[i].rank()) {
205  m_pop[mu()+i].updateAsOffspring();
206  offspringSuccess = CMAChromosome::Successful;
207  }
208  if(m_pop[i].selected())
209  m_pop[i].updateAsParent(offspringSuccess);
210  }
211 
212  //partition the selected individuals to the front
213  std::partition(m_pop.begin(), m_pop.end(),CMAIndividual<RealVector>::IsSelected);
214 
215  //update individuals and generate solution set
216  for (std::size_t i = 0; i < mu(); i++) {
217  noalias(m_best[i].point) = m_pop[i].searchPoint();
218  m_best[i].value = m_pop[i].unpenalizedFitness();
219  }
220  };
221 
222 };
223 
227 
228 }
229 
230 #endif