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