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-2015 Shark Development Team
17  *
18  * <BR><HR>
19  * This file is part of Shark.
20  * <http://image.diku.dk/shark/>
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
47 
49 
50 #include <boost/foreach.hpp>
51 
52 namespace shark {
53 
54 /**
55 * \brief Implements the SMS-EMOA.
56 *
57 * Please see the following paper for further reference:
58 * - Beume, Naujoks, Emmerich.
59 * SMS-EMOA: Multiobjective selection based on dominated hypervolume.
60 * European Journal of Operational Research.
61 */
62 class SMSEMOA : public AbstractMultiObjectiveOptimizer<RealVector >{
63 private:
64  /// \brief The individual type of the SMS-EMOA.
66 public:
67  SMSEMOA() {
68  mu() = 100;
69  crossoverProbability() = 0.9;
70  nc() = 20.0;
71  nm() = 20.0;
73  }
74 
75  std::string name() const {
76  return "SMSEMOA";
77  }
78 
79  /// \brief Returns the probability that crossover is applied.
80  double crossoverProbability()const{
81  return m_crossoverProbability;
82  }
83  /// \brief Returns the probability that crossover is applied.
85  return m_crossoverProbability;
86  }
87 
88  double nm()const{
89  return m_mutator.m_nm;
90  }
91  double& nm(){
92  return m_mutator.m_nm;
93  }
94 
95  double nc()const{
96  return m_crossover.m_nc;
97  }
98  double& nc(){
99  return m_crossover.m_nc;
100  }
101 
102  unsigned int mu()const{
103  return m_mu;
104  }
105  unsigned int& mu(){
106  return m_mu;
107  }
108 
109  /**
110  * \brief Stores/loads the algorithm's state.
111  * \tparam Archive The type of the archive.
112  * \param [in,out] archive The archive to use for loading/storing.
113  * \param [in] version Currently unused.
114  */
115  template<typename Archive>
116  void serialize( Archive & archive, const unsigned int version ) {
117  archive & BOOST_SERIALIZATION_NVP( m_pop );
118  archive & BOOST_SERIALIZATION_NVP(m_mu);
119  archive & BOOST_SERIALIZATION_NVP(m_best);
120 
121  archive & BOOST_SERIALIZATION_NVP( m_evaluator );
122  archive & BOOST_SERIALIZATION_NVP( m_selection );
123  archive & BOOST_SERIALIZATION_NVP( m_crossover );
124  archive & BOOST_SERIALIZATION_NVP( m_mutator );
125  archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
126  }
127 
129  /**
130  * \brief Initializes the algorithm for the supplied objective function.
131  *
132  * \param [in] function The objective function.
133  * \param [in] startingPoints A set of intiial search points.
134  */
135  void init(
136  ObjectiveFunctionType& function,
137  std::vector<SearchPointType> const& startingPoints
138  ){
139  checkFeatures(function);
140  function.init();
141 
142  m_pop.resize( mu() + 1 );
143  m_best.resize(mu());
144  for(std::size_t i = 0; i != mu(); ++i){
145  m_pop[i].age()=0;
146  m_pop[i].searchPoint() = function.proposeStartingPoint();
147  m_evaluator( function, m_pop[i] );
148  m_best[i].point = m_pop[i].searchPoint();
149  m_best[i].value = m_pop[i].unpenalizedFitness();
150  }
151  m_selection( m_pop, m_mu );
152  m_crossover.init(function);
153  m_mutator.init(function);
154  }
155 
156  /**
157  * \brief Executes one iteration of the algorithm.
158  *
159  * \param [in] function The function to iterate upon.
160  */
161  void step( ObjectiveFunctionType const& function ) {
163 
164  Individual mate1( *selection( m_pop.begin(), m_pop.begin() + mu() ) );
165  Individual mate2( *selection( m_pop.begin(), m_pop.begin() + mu() ) );
166 
167  if( Rng::coinToss( m_crossoverProbability ) ) {
168  m_crossover( mate1, mate2 );
169  }
170 
171  if( Rng::coinToss() ) {
172  m_mutator( mate1 );
173  m_pop.back() = mate1;
174  } else {
175  m_mutator( mate2 );
176  m_pop.back() = mate2;
177  }
178 
179  m_evaluator( function, m_pop.back() );
180  m_selection( m_pop, m_mu );
181 
182  //if the individual got selected, insert it into the parent population
183  if(m_pop.back().selected()){
184  for(std::size_t i = 0; i != mu(); ++i){
185  if(!m_pop[i].selected()){
186  m_best[i].point = m_pop[mu()].searchPoint();
187  m_best[i].value = m_pop[mu()].unpenalizedFitness();
188  m_pop[i] = m_pop.back();
189  break;
190  }
191  }
192  }
193  }
194 private:
195 
196  std::vector<Individual> m_pop; ///< Population of size \f$\mu + 1\f$.
197  unsigned int m_mu; ///< Size of parent generation
198 
199  PenalizingEvaluator m_evaluator; ///< Evaluation operator.
200  IndicatorBasedSelection<HypervolumeIndicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
201  SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
202  PolynomialMutator m_mutator; ///< Mutation operator.
203 
204  double m_crossoverProbability; ///< Crossover probability.
205 };
206 }
207 
208 
209 #endif