SMS-EMOA.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Implements the SMS-EMOA.
5  *
6  * See Nicola Beume, Boris Naujoks, and Michael Emmerich.
7  * SMS-EMOA: Multiobjective selection based on dominated hypervolume.
8  * European Journal of Operational Research, 181(3):1653-1669, 2007.
9  *
10  *
11  *
12  * \author T.Voss
13  * \date 2010
14  *
15  *
16  * \par Copyright 1995-2017 Shark Development Team
17  *
18  * <BR><HR>
19  * This file is part of Shark.
20  * <http://shark-ml.org/>
21  *
22  * Shark is free software: you can redistribute it and/or modify
23  * it under the terms of the GNU Lesser General Public License as published
24  * by the Free Software Foundation, either version 3 of the License, or
25  * (at your option) any later version.
26  *
27  * Shark is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  *
32  * You should have received a copy of the GNU Lesser General Public License
33  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
34  *
35  */
36 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_SMS_EMOA_H
37 #define SHARK_ALGORITHMS_DIRECT_SEARCH_SMS_EMOA_H
38 
39 // MOO specific stuff
40 #include <shark/Algorithms/DirectSearch/Individual.h>
41 #include <shark/Algorithms/DirectSearch/Operators/Indicators/HypervolumeIndicator.h>
42 #include <shark/Algorithms/DirectSearch/Operators/Selection/TournamentSelection.h>
43 #include <shark/Algorithms/DirectSearch/Operators/Selection/IndicatorBasedSelection.h>
44 #include <shark/Algorithms/DirectSearch/Operators/Recombination/SimulatedBinaryCrossover.h>
45 #include <shark/Algorithms/DirectSearch/Operators/Mutation/PolynomialMutation.h>
46 #include <shark/Algorithms/DirectSearch/Operators/Evaluation/PenalizingEvaluator.h>
47 
48 #include <shark/Algorithms/AbstractMultiObjectiveOptimizer.h>
49 
50 namespace shark {
51 
52 /**
53 * \brief Implements the SMS-EMOA.
54 *
55 * Please see the following paper for further reference:
56 * - Beume, Naujoks, Emmerich.
57 * SMS-EMOA: Multiobjective selection based on dominated hypervolume.
58 * European Journal of Operational Research.
59 */
60 class SMSEMOA : public AbstractMultiObjectiveOptimizer<RealVector >{
61 public:
62  SMSEMOA(random::rng_type& rng = random::globalRng):mpe_rng(&rng) {
63  m_mu = 100;
64  m_mutator.m_nm = 20.0;
65  m_crossover.m_nc = 20.0;
66  m_crossoverProbability = 0.9;
67  this->m_features |= AbstractMultiObjectiveOptimizer<RealVector >::CAN_SOLVE_CONSTRAINED;
68  }
69 
70  std::string name() const {
71  return "SMSEMOA";
72  }
73 
74  /// \brief Returns the probability that crossover is applied.
75  double crossoverProbability()const{
76  return m_crossoverProbability;
77  }
78 
79  double nm()const{
80  return m_mutator.m_nm;
81  }
82 
83  double nc()const{
84  return m_crossover.m_nc;
85  }
86 
87  unsigned int mu()const{
88  return m_mu;
89  }
90 
91  unsigned int& mu(){
92  return m_mu;
93  }
94 
95  std::size_t numInitPoints() const{
96  return m_mu;
97  }
98 
99  HypervolumeIndicator& indicator(){
100  return m_selection.indicator();
101  }
102  HypervolumeIndicator const& indicator()const{
103  return m_selection.indicator();
104  }
105 
106  void read( InArchive & archive ){
107  archive & BOOST_SERIALIZATION_NVP( m_parents );
108  archive & BOOST_SERIALIZATION_NVP( m_mu );
109  archive & BOOST_SERIALIZATION_NVP( m_best );
110 
111  archive & BOOST_SERIALIZATION_NVP( m_selection );
112  archive & BOOST_SERIALIZATION_NVP( m_crossover );
113  archive & BOOST_SERIALIZATION_NVP( m_mutator );
114  archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
115  }
116  void write( OutArchive & archive ) const{
117  archive & BOOST_SERIALIZATION_NVP( m_parents );
118  archive & BOOST_SERIALIZATION_NVP( m_mu );
119  archive & BOOST_SERIALIZATION_NVP( m_best );
120 
121  archive & BOOST_SERIALIZATION_NVP( m_selection );
122  archive & BOOST_SERIALIZATION_NVP( m_crossover );
123  archive & BOOST_SERIALIZATION_NVP( m_mutator );
124  archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
125  }
126 
127  using AbstractMultiObjectiveOptimizer<RealVector >::init;
128  /**
129  * \brief Initializes the algorithm for the supplied objective function.
130  *
131  * \param [in] function The objective function.
132  * \param [in] initialSearchPoints A set of intiial search points.
133  */
134  void init(
135  ObjectiveFunctionType const& function,
136  std::vector<SearchPointType> const& initialSearchPoints
137  ){
138  checkFeatures(function);
139  std::vector<RealVector> values(initialSearchPoints.size());
140  for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
141  SHARK_RUNTIME_CHECK(function.isFeasible(initialSearchPoints[i]),"Starting point(s) not feasible");
142  values[i] = function.eval(initialSearchPoints[i]);
143  }
144 
145  std::size_t dim = function.numberOfVariables();
146  RealVector lowerBounds(dim, -1E20);
147  RealVector upperBounds(dim, 1E20);
148  if (function.hasConstraintHandler() && function.getConstraintHandler().isBoxConstrained()) {
149  typedef BoxConstraintHandler<SearchPointType> ConstraintHandler;
150  ConstraintHandler const& handler = static_cast<ConstraintHandler const&>(function.getConstraintHandler());
151 
152  lowerBounds = handler.lower();
153  upperBounds = handler.upper();
154  } else{
155  SHARK_RUNTIME_CHECK(
156  function.hasConstraintHandler() && !function.getConstraintHandler().isBoxConstrained(),
157  "Algorithm does only allow box constraints"
158  );
159  }
160  doInit(initialSearchPoints,values,lowerBounds, upperBounds,mu(),nm(),nc(),crossoverProbability());
161  }
162 
163  /**
164  * \brief Executes one iteration of the algorithm.
165  *
166  * \param [in] function The function to iterate upon.
167  */
168  void step( ObjectiveFunctionType const& function ) {
169  std::vector<IndividualType> offspring = generateOffspring();
170  PenalizingEvaluator penalizingEvaluator;
171  penalizingEvaluator( function, offspring.begin(), offspring.end() );
172  updatePopulation(offspring);
173  }
174 protected:
175  /// \brief The individual type of the SMS-EMOA.
176  typedef shark::Individual<RealVector,RealVector> IndividualType;
177 
178  void doInit(
179  std::vector<SearchPointType> const& initialSearchPoints,
180  std::vector<ResultType> const& functionValues,
181  RealVector const& lowerBounds,
182  RealVector const& upperBounds,
183  std::size_t mu,
184  double nm,
185  double nc,
186  double crossover_prob
187  ){
188  SIZE_CHECK(initialSearchPoints.size() > 0);
189  m_mu = mu;
190  m_mutator.m_nm = nm;
191  m_crossover.m_nc = nc;
192  m_crossoverProbability = crossover_prob;
193  m_best.resize( mu );
194  m_parents.resize( mu );
195  //if the number of supplied points is smaller than mu, fill everything in
196  std::size_t numPoints = 0;
197  if(initialSearchPoints.size()<=mu){
198  numPoints = initialSearchPoints.size();
199  for(std::size_t i = 0; i != numPoints; ++i){
200  m_parents[i].searchPoint() = initialSearchPoints[i];
201  m_parents[i].penalizedFitness() = functionValues[i];
202  m_parents[i].unpenalizedFitness() = functionValues[i];
203  }
204  }
205  //copy points randomly
206  for(std::size_t i = numPoints; i != mu; ++i){
207  std::size_t index = random::discrete(*mpe_rng, std::size_t(0),initialSearchPoints.size()-1);
208  m_parents[i].searchPoint() = initialSearchPoints[index];
209  m_parents[i].penalizedFitness() = functionValues[index];
210  m_parents[i].unpenalizedFitness() = functionValues[index];
211  }
212  //create initial mu best points
213  for(std::size_t i = 0; i != mu; ++i){
214  m_best[i].point = m_parents[i].searchPoint();
215  m_best[i].value = m_parents[i].unpenalizedFitness();
216  }
217  m_selection( m_parents, mu );
218 
219  m_crossover.init(lowerBounds,upperBounds);
220  m_mutator.init(lowerBounds,upperBounds);
221  }
222 
223  std::vector<IndividualType> generateOffspring()const{
224  std::vector<IndividualType> offspring(1);
225  offspring[0] = createOffspring(m_parents.begin(),m_parents.begin()+mu());
226  return offspring;
227  }
228 
229  void updatePopulation( std::vector<IndividualType> const& offspring) {
230  m_parents.push_back(offspring[0]);
231  m_selection( m_parents, mu());
232 
233  //if the individual got selected, insert it into the parent population
234  if(m_parents.back().selected()){
235  for(std::size_t i = 0; i != mu(); ++i){
236  if(!m_parents[i].selected()){
237  m_best[i].point = m_parents[mu()].searchPoint();
238  m_best[i].value = m_parents[mu()].unpenalizedFitness();
239  m_parents[i] = m_parents.back();
240  break;
241  }
242  }
243  }
244  m_parents.pop_back();
245  }
246 
247  std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
248 private:
249 
250  IndividualType createOffspring(
251  std::vector<IndividualType>::const_iterator begin,
252  std::vector<IndividualType>::const_iterator end
253  )const{
254  TournamentSelection< IndividualType::RankOrdering > selection;
255 
256  IndividualType mate1( *selection(*mpe_rng, begin, end ) );
257  IndividualType mate2( *selection(*mpe_rng, begin, end) );
258 
259  if( random::coinToss(*mpe_rng, m_crossoverProbability ) ) {
260  m_crossover(*mpe_rng, mate1, mate2 );
261  }
262 
263  if( random::coinToss(*mpe_rng,0.5) ) {
264  m_mutator(*mpe_rng, mate1 );
265  return mate1;
266  } else {
267  m_mutator(*mpe_rng, mate2 );
268  return mate2;
269  }
270  }
271 
272  unsigned int m_mu; ///< Size of parent generation
273 
274  IndicatorBasedSelection<HypervolumeIndicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
275  SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
276  PolynomialMutator m_mutator; ///< Mutation operator.
277 
278  double m_crossoverProbability; ///< Crossover probability.
279  random::rng_type* mpe_rng;
280 };
281 }
282 
283 
284 #endif