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 public:
64  SMSEMOA(DefaultRngType& rng = Rng::globalRng):mpe_rng(&rng) {
65  m_mu = 100;
66  m_mutator.m_nm = 20.0;
67  m_crossover.m_nc = 20.0;
68  m_crossoverProbability = 0.9;
70  }
71 
72  std::string name() const {
73  return "SMSEMOA";
74  }
75 
76  /// \brief Returns the probability that crossover is applied.
77  double crossoverProbability()const{
78  return m_crossoverProbability;
79  }
80 
81  double nm()const{
82  return m_mutator.m_nm;
83  }
84 
85  double nc()const{
86  return m_crossover.m_nc;
87  }
88 
89  unsigned int mu()const{
90  return m_mu;
91  }
92 
93  unsigned int& mu(){
94  return m_mu;
95  }
96 
97  void read( InArchive & archive ){
98  archive & BOOST_SERIALIZATION_NVP( m_parents );
99  archive & BOOST_SERIALIZATION_NVP( m_mu );
100  archive & BOOST_SERIALIZATION_NVP( m_best );
101 
102  archive & BOOST_SERIALIZATION_NVP( m_selection );
103  archive & BOOST_SERIALIZATION_NVP( m_crossover );
104  archive & BOOST_SERIALIZATION_NVP( m_mutator );
105  archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
106  }
107  void write( OutArchive & archive ) const{
108  archive & BOOST_SERIALIZATION_NVP( m_parents );
109  archive & BOOST_SERIALIZATION_NVP( m_mu );
110  archive & BOOST_SERIALIZATION_NVP( m_best );
111 
112  archive & BOOST_SERIALIZATION_NVP( m_selection );
113  archive & BOOST_SERIALIZATION_NVP( m_crossover );
114  archive & BOOST_SERIALIZATION_NVP( m_mutator );
115  archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
116  }
117 
119  /**
120  * \brief Initializes the algorithm for the supplied objective function.
121  *
122  * \param [in] function The objective function.
123  * \param [in] initialSearchPoints A set of intiial search points.
124  */
125  void init(
126  ObjectiveFunctionType& function,
127  std::vector<SearchPointType> const& initialSearchPoints
128  ){
129  checkFeatures(function);
130  std::vector<RealVector> values(initialSearchPoints.size());
131  for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
132  if(!function.isFeasible(initialSearchPoints[i]))
133  throw SHARKEXCEPTION("[SMS-EMOA::init] starting point(s) not feasible");
134  values[i] = function.eval(initialSearchPoints[i]);
135  }
136 
137  std::size_t dim = function.numberOfVariables();
138  RealVector lowerBounds(dim, -1E20);
139  RealVector upperBounds(dim, 1E20);
140  if (function.hasConstraintHandler() && function.getConstraintHandler().isBoxConstrained()) {
141  typedef BoxConstraintHandler<SearchPointType> ConstraintHandler;
142  ConstraintHandler const& handler = static_cast<ConstraintHandler const&>(function.getConstraintHandler());
143 
144  lowerBounds = handler.lower();
145  upperBounds = handler.upper();
146  } else{
147  throw SHARKEXCEPTION("[SMS-EMOA::init] Algorithm does only allow box constraints");
148  }
149  doInit(initialSearchPoints,values,lowerBounds, upperBounds,mu(),nm(),nc(),crossoverProbability());
150  }
151 
152  /**
153  * \brief Executes one iteration of the algorithm.
154  *
155  * \param [in] function The function to iterate upon.
156  */
157  void step( ObjectiveFunctionType const& function ) {
158  std::vector<IndividualType> offspring = generateOffspring();
159  PenalizingEvaluator penalizingEvaluator;
160  penalizingEvaluator( function, offspring.begin(), offspring.end() );
161  updatePopulation(offspring);
162  }
163 protected:
164  /// \brief The individual type of the SMS-EMOA.
166 
167  void doInit(
168  std::vector<SearchPointType> const& initialSearchPoints,
169  std::vector<ResultType> const& functionValues,
170  RealVector const& lowerBounds,
171  RealVector const& upperBounds,
172  std::size_t mu,
173  double nm,
174  double nc,
175  double crossover_prob
176  ){
177  SIZE_CHECK(initialSearchPoints.size() > 0);
178  m_mu = mu;
179  m_mutator.m_nm = nm;
180  m_crossover.m_nc = nc;
181  m_crossoverProbability = crossover_prob;
182  m_best.resize( mu );
183  m_parents.resize( mu );
184  //if the number of supplied points is smaller than mu, fill everything in
185  std::size_t numPoints = 0;
186  if(initialSearchPoints.size()<=mu){
187  numPoints = initialSearchPoints.size();
188  for(std::size_t i = 0; i != numPoints; ++i){
189  m_parents[i].searchPoint() = initialSearchPoints[i];
190  m_parents[i].penalizedFitness() = functionValues[i];
191  m_parents[i].unpenalizedFitness() = functionValues[i];
192  }
193  }
194  //copy points randomly
195  for(std::size_t i = numPoints; i != mu; ++i){
196  std::size_t index = discrete(*mpe_rng,0,initialSearchPoints.size()-1);
197  m_parents[i].searchPoint() = initialSearchPoints[index];
198  m_parents[i].penalizedFitness() = functionValues[index];
199  m_parents[i].unpenalizedFitness() = functionValues[index];
200  }
201  //create initial mu best points
202  for(std::size_t i = 0; i != mu; ++i){
203  m_best[i].point = m_parents[i].searchPoint();
204  m_best[i].value = m_parents[i].unpenalizedFitness();
205  }
206  m_selection( m_parents, mu );
207 
208  m_crossover.init(lowerBounds,upperBounds);
209  m_mutator.init(lowerBounds,upperBounds);
210  }
211 
212  std::vector<IndividualType> generateOffspring()const{
213  std::vector<IndividualType> offspring(1);
214  offspring[0] = createOffspring(m_parents.begin(),m_parents.begin()+mu());
215  return offspring;
216  }
217 
218  void updatePopulation( std::vector<IndividualType> const& offspring) {
219  m_parents.push_back(offspring[0]);
220  m_selection( m_parents, mu());
221 
222  //if the individual got selected, insert it into the parent population
223  if(m_parents.back().selected()){
224  for(std::size_t i = 0; i != mu(); ++i){
225  if(!m_parents[i].selected()){
226  m_best[i].point = m_parents[mu()].searchPoint();
227  m_best[i].value = m_parents[mu()].unpenalizedFitness();
228  m_parents[i] = m_parents.back();
229  break;
230  }
231  }
232  }
233  m_parents.pop_back();
234  }
235 
236  std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
237 private:
238 
239  IndividualType createOffspring(
240  std::vector<IndividualType>::const_iterator begin,
241  std::vector<IndividualType>::const_iterator end
242  )const{
244 
245  IndividualType mate1( *selection(*mpe_rng, begin, end ) );
246  IndividualType mate2( *selection(*mpe_rng, begin, end) );
247 
248  if( coinToss(*mpe_rng, m_crossoverProbability ) ) {
249  m_crossover(*mpe_rng, mate1, mate2 );
250  }
251 
252  if( coinToss(*mpe_rng,0.5) ) {
253  m_mutator(*mpe_rng, mate1 );
254  return mate1;
255  } else {
256  m_mutator(*mpe_rng, mate2 );
257  return mate2;
258  }
259  }
260 
261  unsigned int m_mu; ///< Size of parent generation
262 
263  IndicatorBasedSelection<HypervolumeIndicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
264  SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
265  PolynomialMutator m_mutator; ///< Mutation operator.
266 
267  double m_crossoverProbability; ///< Crossover probability.
268  DefaultRngType* mpe_rng;
269 };
270 }
271 
272 
273 #endif