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-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_REAL_CODED_NSGA_II_H
33 #define SHARK_ALGORITHMS_DIRECT_SEARCH_REAL_CODED_NSGA_II_H
34 
36 
38 
39 // MOO specific stuff
47 
48 
49 namespace shark {
50 
51 /**
52 * \brief Implements the NSGA-II.
53 *
54 * Please see the following papers for further reference:
55 * Deb, Agrawal, Pratap and Meyarivan.
56 * A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
57 * IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
58 */
59 template<typename Indicator>
61 private:
62  /**
63  * \brief The individual type of the NSGA-II.
64  */
66 
67  std::vector<Individual> m_pop; ///< Population of size \f$\mu + 1\f$.
68  std::size_t m_mu; ///< Size of parent generation
69 
70  IndicatorBasedSelection<Indicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
71 
72  PenalizingEvaluator m_evaluator; ///< Evaluation operator.
73  SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
74  PolynomialMutator m_mutator; ///< Mutation operator.
75 
76  double m_crossoverProbability; ///< Crossover probability.
77 public:
78 
79  /**
80  * \brief Default c'tor.
81  */
83  mu() = 100;
84  crossoverProbability() = 0.8;
85  nc() = 20.0;
86  nm() = 20.0;
88  }
89 
90  std::string name() const {
91  return "RealCodedNSGAII";
92  }
93 
94  /// \brief Returns the probability that crossover is applied.
95  double crossoverProbability()const{
96  return m_crossoverProbability;
97  }
98  /// \brief Returns the probability that crossover is applied.
100  return m_crossoverProbability;
101  }
102 
103  double nm()const{
104  return m_mutator.m_nm;
105  }
106  double& nm(){
107  return m_mutator.m_nm;
108  }
109 
110  double nc()const{
111  return m_crossover.m_nc;
112  }
113  double& nc(){
114  return m_crossover.m_nc;
115  }
116 
117  std::size_t mu()const{
118  return m_mu;
119  }
120  std::size_t& mu(){
121  return m_mu;
122  }
123 
124  /**
125  * \brief Stores/loads the algorithm's state.
126  * \tparam Archive The type of the archive.
127  * \param [in,out] archive The archive to use for loading/storing.
128  * \param [in] version Currently unused.
129  */
130  template<typename Archive>
131  void serialize( Archive & archive, const unsigned int version ) {
132  archive & m_pop;
133  archive & m_mu;
134  archive & m_best;
135 
136  archive & m_evaluator;
137  archive & m_crossover;
138  archive & m_mutator;
139 
140  archive & m_crossoverProbability;
141  }
142 
144  /**
145  * \brief Initializes the algorithm for the supplied objective function.
146  * \tparam ObjectiveFunction The type of the objective function,
147  * needs to adhere to the concept of an AbstractObjectiveFunction.
148  * \param [in] function The objective function
149  * \param [in] startingPoints Starting point to initialize the algorithm for.
150  */
151  void init(
152  ObjectiveFunctionType& function,
153  std::vector<SearchPointType> const& startingPoints
154  ){
155  checkFeatures(function);
156  function.init();
157 
158  //create parent set
159  m_pop.reserve( 2 * mu() );
160  m_pop.resize(mu());
161  m_best.resize(mu());
162  for(std::size_t i = 0; i != mu(); ++i){
163  m_pop[i].searchPoint()= function.proposeStartingPoint();
164  }
165  //evaluate initial parent set and create best front
166  m_evaluator( function, m_pop.begin(),m_pop.begin()+mu() );
167  m_selection( m_pop,m_mu );
168  for(std::size_t i = 0; i != mu(); ++i){
169  m_best[i].point = m_pop[i].searchPoint();
170  m_best[i].value = m_pop[i].unpenalizedFitness();
171  }
172  //make room for offspring
173  m_pop.resize(2*mu());
174 
175  m_crossover.init(function);
176  m_mutator.init(function);
177  }
178 
179  /**
180  * \brief Executes one iteration of the algorithm.
181  *
182  * \param [in] function The function to iterate upon.
183  */
184  void step( ObjectiveFunctionType const& function ) {
186 
187  matingSelection(
188  m_pop.begin(),
189  m_pop.begin() + mu(),
190  m_pop.begin() + mu(),
191  m_pop.end()
192  );
193 
194  for( std::size_t i = 1; i < mu(); i++ ) {
195  if( Rng::coinToss( 0.8 ) ) {
196  m_crossover( m_pop[mu() + i - 1], m_pop[mu() + i] );
197  }
198  }
199  for( std::size_t i = 0; i < mu(); i++ ) {
200  m_mutator( m_pop[mu() + i] );
201  }
202  m_evaluator( function, m_pop.begin()+mu(), m_pop.end() );
203  m_selection( m_pop, m_mu );
204 
205  std::partition( m_pop.begin(), m_pop.end(), Individual::IsSelected );
206 
207  for( std::size_t i = 0; i != mu(); ++i ) {
208  noalias(m_best[i].value) = m_pop[i].unpenalizedFitness();
209  noalias(m_best[i].point) = m_pop[i].searchPoint();
210  }
211  }
212 };
213 
216 }
217 #endif