RealCodedNSGAII.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief IndicatorBasedRealCodedNSGAII.h
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_REAL_CODED_NSGA_II_H
33 #define SHARK_ALGORITHMS_DIRECT_SEARCH_REAL_CODED_NSGA_II_H
34 
35 #include <shark/Algorithms/AbstractMultiObjectiveOptimizer.h>
36 
37 #include <shark/Algorithms/DirectSearch/Individual.h>
38 
39 // MOO specific stuff
40 #include <shark/Algorithms/DirectSearch/Operators/Indicators/HypervolumeIndicator.h>
41 #include <shark/Algorithms/DirectSearch/Operators/Indicators/AdditiveEpsilonIndicator.h>
42 #include <shark/Algorithms/DirectSearch/Operators/Indicators/CrowdingDistance.h>
43 #include <shark/Algorithms/DirectSearch/Operators/Indicators/NSGA3Indicator.h>
44 #include <shark/Algorithms/DirectSearch/Operators/Selection/IndicatorBasedSelection.h>
45 #include <shark/Algorithms/DirectSearch/Operators/Selection/TournamentSelection.h>
46 #include <shark/Algorithms/DirectSearch/Operators/Recombination/SimulatedBinaryCrossover.h>
47 #include <shark/Algorithms/DirectSearch/Operators/Mutation/PolynomialMutation.h>
48 #include <shark/Algorithms/DirectSearch/Operators/Evaluation/PenalizingEvaluator.h>
49 
50 
51 namespace shark {
52 
53 /// \brief Implements the NSGA-II.
54 ///
55 /// Please see the following papers for further reference:
56 /// Deb, Agrawal, Pratap and Meyarivan.
57 /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
58 /// IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
59 template<typename Indicator>
60 class IndicatorBasedRealCodedNSGAII : public AbstractMultiObjectiveOptimizer<RealVector>{
61 public:
62 
63  /// \brief Default c'tor.
64  IndicatorBasedRealCodedNSGAII(random::rng_type& rng = random::globalRng):mpe_rng(&rng){
65  mu() = 100;
66  crossoverProbability() = 0.9;
67  nc() = 20.0;
68  nm() = 20.0;
69  this->m_features |= AbstractMultiObjectiveOptimizer<RealVector >::CAN_SOLVE_CONSTRAINED;
70  }
71 
72  std::string name() const {
73  return "RealCodedNSGAII";
74  }
75 
76  /// \brief Returns the probability that crossover is applied.
77  double crossoverProbability()const{
78  return m_crossoverProbability;
79  }
80  /// \brief Returns the probability that crossover is applied.
81  double& crossoverProbability(){
82  return m_crossoverProbability;
83  }
84 
85  /// \brief Returns the mutation variation strength parameter.
86  double nm()const{
87  return m_mutation.m_nm;
88  }
89  /// \brief Returns a reference to the mutation variation strength parameter.
90  double& nm(){
91  return m_mutation.m_nm;
92  }
93  /// \brief Returns the crossover variation strength parameter.
94  double nc()const{
95  return m_crossover.m_nc;
96  }
97  /// \brief Returns a reference to the crossover variation strength parameter.
98  double& nc(){
99  return m_crossover.m_nc;
100  }
101 
102  /// \brief Returns the number of elements in the front.
103  std::size_t mu()const{
104  return m_mu;
105  }
106  /// \brief Returns the number of elements in the front.
107  std::size_t& mu(){
108  return m_mu;
109  }
110 
111  /// \brief The number of points used for initialization of the algorithm.
112  std::size_t numInitPoints() const{
113  return m_mu;
114  }
115 
116  /// \brief Returns the indicator used.
117  Indicator& indicator(){
118  return m_selection.indicator();
119  }
120  /// \brief Returns the indicator used.
121  Indicator const& indicator()const{
122  return m_selection.indicator();
123  }
124 
125  void read( InArchive & archive ){
126  archive >> BOOST_SERIALIZATION_NVP(m_parents);
127  archive >> BOOST_SERIALIZATION_NVP(m_mu);
128  archive >> BOOST_SERIALIZATION_NVP(m_best);
129 
130  archive >> BOOST_SERIALIZATION_NVP(m_selection);
131  archive >> BOOST_SERIALIZATION_NVP(m_crossover);
132  archive >> BOOST_SERIALIZATION_NVP(m_mutation);
133  archive >> BOOST_SERIALIZATION_NVP(m_crossoverProbability);
134  }
135  void write( OutArchive & archive ) const{
136  archive << BOOST_SERIALIZATION_NVP(m_parents);
137  archive << BOOST_SERIALIZATION_NVP(m_mu);
138  archive << BOOST_SERIALIZATION_NVP(m_best);
139 
140  archive << BOOST_SERIALIZATION_NVP(m_selection);
141  archive << BOOST_SERIALIZATION_NVP(m_crossover);
142  archive << BOOST_SERIALIZATION_NVP(m_mutation);
143  archive << BOOST_SERIALIZATION_NVP(m_crossoverProbability);
144  }
145 
146  using AbstractMultiObjectiveOptimizer<RealVector >::init;
147 
148  /// \brief Initializes the algorithm for the supplied objective function.
149  ///
150  /// \param [in] function The objective function.
151  /// \param [in] initialSearchPoints A set of intiial search points.
152  void init(
153  ObjectiveFunctionType const& function,
154  std::vector<SearchPointType> const& initialSearchPoints
155  ){
156  checkFeatures(function);
157  std::vector<RealVector> values(initialSearchPoints.size());
158  for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
159  SHARK_RUNTIME_CHECK(function.isFeasible(initialSearchPoints[i]),"Starting point(s) not feasible");
160  values[i] = function.eval(initialSearchPoints[i]);
161  }
162 
163  std::size_t dim = function.numberOfVariables();
164  RealVector lowerBounds(dim, -1E20);
165  RealVector upperBounds(dim, 1E20);
166  if (function.hasConstraintHandler() && function.getConstraintHandler().isBoxConstrained()) {
167  typedef BoxConstraintHandler<SearchPointType> ConstraintHandler;
168  ConstraintHandler const& handler = static_cast<ConstraintHandler const&>(function.getConstraintHandler());
169 
170  lowerBounds = handler.lower();
171  upperBounds = handler.upper();
172  } else{
173  SHARK_RUNTIME_CHECK(
174  !function.isConstrained(), "Algorithm does only allow box constraints"
175  );
176  }
177 
178  doInit(initialSearchPoints,values,lowerBounds, upperBounds, mu(), nm(), nc(), crossoverProbability());
179  }
180 
181  /// \brief Executes one iteration of the algorithm.
182  ///
183  ///\param [in] function The function to iterate upon.
184  void step( ObjectiveFunctionType const& function ) {
185  std::vector<IndividualType> offspring = generateOffspring();
186  PenalizingEvaluator penalizingEvaluator;
187  penalizingEvaluator( function, offspring.begin(), offspring.end() );
188  updatePopulation(offspring);
189  }
190 protected:
191  /// \brief The individual type of the NSGA-II.
192  typedef shark::Individual<RealVector,RealVector> IndividualType;
193 
194  void doInit(
195  std::vector<SearchPointType> const& initialSearchPoints,
196  std::vector<ResultType> const& functionValues,
197  RealVector const& lowerBounds,
198  RealVector const& upperBounds,
199  std::size_t mu,
200  double nm,
201  double nc,
202  double crossover_prob
203  ){
204  SIZE_CHECK(initialSearchPoints.size() > 0);
205  m_mu = mu;
206  m_mutation.m_nm = nm;
207  m_crossover.m_nc = nc;
208  m_crossoverProbability = crossover_prob;
209  m_best.resize( mu );
210  m_parents.resize( mu );
211  //if the number of supplied points is smaller than mu, fill everything in
212  std::size_t numPoints = 0;
213  if(initialSearchPoints.size()<=mu){
214  numPoints = initialSearchPoints.size();
215  for(std::size_t i = 0; i != numPoints; ++i){
216  m_parents[i].searchPoint() = initialSearchPoints[i];
217  m_parents[i].penalizedFitness() = functionValues[i];
218  m_parents[i].unpenalizedFitness() = functionValues[i];
219  }
220  }
221  //copy points randomly
222  for(std::size_t i = numPoints; i != mu; ++i){
223  std::size_t index = random::discrete(*mpe_rng, std::size_t(0),initialSearchPoints.size()-1);
224  m_parents[i].searchPoint() = initialSearchPoints[index];
225  m_parents[i].penalizedFitness() = functionValues[index];
226  m_parents[i].unpenalizedFitness() = functionValues[index];
227  }
228  //create initial mu best points
229  for(std::size_t i = 0; i != mu; ++i){
230  m_best[i].point = m_parents[i].searchPoint();
231  m_best[i].value = m_parents[i].unpenalizedFitness();
232  }
233  m_crossover.init(lowerBounds,upperBounds);
234  m_mutation.init(lowerBounds,upperBounds);
235  indicator().init(functionValues.front().size(),mu,*mpe_rng);
236  m_selection( m_parents, mu );
237 
238 
239  }
240 
241  std::vector<IndividualType> generateOffspring()const{
242  TournamentSelection< IndividualType::RankOrdering > selection;
243  std::vector<IndividualType> offspring(mu());
244  selection(
245  *mpe_rng,
246  m_parents.begin(),
247  m_parents.end(),
248  offspring.begin(),
249  offspring.end()
250  );
251 
252  for( std::size_t i = 0; i < mu()-1; i+=2 ) {
253  if( random::coinToss(*mpe_rng, m_crossoverProbability ) ) {
254  m_crossover(*mpe_rng,offspring[i], offspring[i +1] );
255  }
256  }
257  for( std::size_t i = 0; i < mu(); i++ ) {
258  m_mutation(*mpe_rng, offspring[i] );
259  }
260  return offspring;
261  }
262 
263  void updatePopulation( std::vector<IndividualType> const& offspringVec) {
264  m_parents.insert(m_parents.end(),offspringVec.begin(),offspringVec.end());
265  m_selection( m_parents, mu());
266 
267  //partition the selected individuals to the front and remove the unselected ones
268  std::partition(m_parents.begin(), m_parents.end(), [](IndividualType const& ind){return ind.selected();});
269  m_parents.erase(m_parents.begin()+mu(),m_parents.end());
270 
271  //update solution set
272  for (std::size_t i = 0; i < mu(); i++) {
273  noalias(m_best[i].point) = m_parents[i].searchPoint();
274  m_best[i].value = m_parents[i].unpenalizedFitness();
275  }
276  }
277 
278  std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
279  random::rng_type* mpe_rng;
280 private:
281  std::size_t m_mu; ///< Size of parent generation
282 
283  IndicatorBasedSelection<Indicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
284 
285  SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
286  PolynomialMutator m_mutation; ///< Mutation operator.
287 
288  double m_crossoverProbability; ///< Crossover probability.
289 };
290 
291 typedef IndicatorBasedRealCodedNSGAII< HypervolumeIndicator > RealCodedNSGAII;
292 typedef IndicatorBasedRealCodedNSGAII< AdditiveEpsilonIndicator > EpsRealCodedNSGAII;
293 typedef IndicatorBasedRealCodedNSGAII< CrowdingDistance > CrowdingRealCodedNSGAII;
294 }
295 #endif