FastNonDominatedSort.h
Go to the documentation of this file.
1 /*!
2  * \brief Implements the fast nondominated sort algorithm for pareto front calculation
3  *
4  * \author T.Voss, O. Krause
5  * \date 2015
6  *
7  *
8  * \par Copyright 1995-2015 Shark Development Team
9  *
10  * <BR><HR>
11  * This file is part of Shark.
12  * <http://image.diku.dk/shark/>
13  *
14  * Shark is free software: you can redistribute it and/or modify
15  * it under the terms of the GNU Lesser General Public License as published
16  * by the Free Software Foundation, either version 3 of the License, or
17  * (at your option) any later version.
18  *
19  * Shark is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU Lesser General Public License for more details.
23  *
24  * You should have received a copy of the GNU Lesser General Public License
25  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
26  *
27  */
28 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_FASTNONDOMINATEDSORT_H
29 #define SHARK_ALGORITHMS_DIRECTSEARCH_FASTNONDOMINATEDSORT_H
30 
33 #include <vector>
34 
35 namespace shark {
36 
37 /**
38  * \brief Implements the well-known non-dominated sorting algorithm.
39  *
40  * Assembles subsets/fronts of mututally non-dominating individuals.
41  * Afterwards every individual is assigned a rank by pop[i].rank() = fronNumber.
42  * The front of dominating points has the value 1.
43  *
44  * The algorithm is dscribed in Deb et al,
45  * A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
46  * IEEE Transactions on Evolutionary Computation, 2002
47  *
48  * \tparam Extractor returning the fitness vector of an individual
49  */
50 template<typename Extractor>
52 
53  /**
54  * \brief Executes the algorithm.
55  *
56  * Afterwards every individual is assigned a rank by pop[i].rank() = fronNumber.
57  * The front of dominating points has the value 1.
58  *
59  * \param pop [in,out] Population to subdivide into fronts of non-dominated individuals.
60  */
61  template<typename PopulationType>
62  void operator()(PopulationType &pop) {
63 
64  //dominance relation
66 
67  //stors for the i-th point which points are dominated by i
68  std::vector<std::vector<std::size_t> > s(pop.size());
69  //stores for every point how many points are dominating it
70  std::vector<std::size_t> numberOfDominatingPoints(pop.size(), 0);
71  //stores initially the front of non-dominated points
72  std::vector<std::size_t> front;
73 
74  for (std::size_t i = 0; i < pop.size(); i++) {
75  //check which points j are dominated by i and add them to s[i]
76  //also increment n[j] for every i dominating j
77  for (std::size_t j = 0; j < pop.size(); j++) {
78  if (i == j)
79  continue;
80 
81  int domination = pdc(pop[i], pop[j]);
82  if ( domination > 1)//pop[i]> pop[j]
83  s[i].push_back(j);
84  else if (domination < -1)//pop[i]< pop[j]
85  numberOfDominatingPoints[i]++;
86  }
87  //all non-dominated points form the first front
88  if (numberOfDominatingPoints[i] == 0){
89  front.push_back(i);
90  pop[i].rank() = 1;//non-dominated points have rank 1
91  }
92  }
93  //find subsequent fronts.
94  unsigned frontCounter = 2;
95  std::vector<std::size_t> nextFront;
96 
97  //as long as we can find fronts
98  //visit all points of the last front found and remove them from the
99  //set. All points which are not dominated anymore form the next front
100  while (!front.empty()) {
101  //visit all points of the current front and remove them
102  // if any point is not dominated, it is part the next front.
103  for(std::size_t element = 0; element != front.size(); ++element) {
104  //visit all points dominated by the element
105  std::vector<std::size_t> const& dominatedPoints = s[front[element]];
106  for (std::size_t j = 0; j != dominatedPoints.size(); ++j){
107  std::size_t point = dominatedPoints[j];
108  numberOfDominatingPoints[point]--;
109  // if no more points are dominating this, add to the next front.
110  if (numberOfDominatingPoints[point] == 0){
111  nextFront.push_back(point);
112  pop[point].rank() = frontCounter;
113  }
114  }
115  }
116 
117  //make the new found front the current
118  front.swap(nextFront);
119  nextFront.clear();
120  frontCounter++;
121  }
122  }
123 };
124 
125 /** \brief Default fast non-dominated sorting based on the Pareto-dominance relation. */
127 
128 }
129 #endif