CrowdingDistance.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Algorithm selecting points based on their crowding distance
5  *
6  * \author O.Krause
7  * \date 2017
8  *
9  *
10  * \par Copyright 1995-2017 Shark Development Team
11  *
12  * <BR><HR>
13  * This file is part of Shark.
14  * <http://shark-ml.org/>
15  *
16  * Shark is free software: you can redistribute it and/or modify
17  * it under the terms of the GNU Lesser General Public License as published
18  * by the Free Software Foundation, either version 3 of the License, or
19  * (at your option) any later version.
20  *
21  * Shark is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24  * GNU Lesser General Public License for more details.
25  *
26  * You should have received a copy of the GNU Lesser General Public License
27  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
28  *
29  */
30 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_INDICATORS_CROWDING_DISTANCE_H
31 #define SHARK_ALGORITHMS_DIRECTSEARCH_INDICATORS_CROWDING_DISTANCE_H
32 
33 #include <shark/LinAlg/Base.h>
34 #include <limits>
35 
36 namespace shark {
37 
38 /// \brief Implements the Crowding Distance of a pareto front
39 ///
40 /// The Crowding distance is an estimate of the perimeter of the cuboid formed by
41 /// using the nearest neighbors of a given point as the vertices.
42 /// The point with the smallest crowding distance is removed from the set.
43 ///
44 /// See the following reference for further details:
45 /// Deb, Kalyanmoy, et al. "A fast and elitist multiobjective genetic algorithm: NSGA-II."
46 /// IEEE transactions on evolutionary computation 6.2 (2002): 182-197.
48  /// \brief Selects the point with the smallest crowding distance
49  ///
50  /// Crowding distance is computed wrt the union of the set front and the archive of points dominating the front
51  template<typename ParetofrontType, typename ParetoArchive>
52  std::size_t leastContributor(ParetofrontType const& front, ParetoArchive const& archive)const{
53  if(front.size() < 2)
54  return 0;
55  std::size_t numDims = front[0].size();
56  double keep = std::numeric_limits<double>::max();
57  //compute the crowding distance
58  std::vector<double> distances(front.size(),0.0);
59  std::vector<KeyValuePair<double, unsigned int > > order(front.size() + archive.size());
60  for( std::size_t i = 0; i != numDims; ++i ) {
61  //create a joint set of front and archive
62  for( std::size_t j = 0; j != front.size(); ++j ) {
63  order[j].key = front[j][i];
64  order[j].value = j;
65  }
66  for( std::size_t j = 0; j != archive.size(); ++j ) {
67  order[j+front.size()].key = archive[j][i];
68  order[j+front.size()].value = j+front.size();
69  }
70  //order to obtain neighbours
71  std::sort(order.begin(),order.end());
72 
73  //check if we have to keep points because they are on the boundary
74  if(order.front().value < front.size())
75  distances[order.front().value] = keep;
76  if(order.back().value < front.size())
77  distances[order.back().value] = keep;
78  double normalizer = order.back().key - order.front().key;
79  for( std::size_t j = 1; j != order.size()-1; ++j ) {
80  std::size_t index = order[j].value;
81  //skip points which are part of the archive or which we want to keep
82  if (index >= front.size() || distances[index] == keep)
83  continue;
84 
85  //compute crowding distance
86  distances[index] += (order[j+1].key - order[j-1].key)/normalizer;
87  }
88  }
89 
90  //get index of point with least crowding distance
91  return std::min_element(distances.begin(), distances.end()) - distances.begin();
92  }
93 
94  template<typename ParetoFrontType, typename ParetoArchive>
95  std::vector<std::size_t> leastContributors( ParetoFrontType const& front, ParetoArchive const& archive, std::size_t K)const{
96  std::vector<std::size_t> indices;
97  std::vector<RealVector> points(front.begin(),front.end());
98  std::vector<std::size_t> activeIndices(points.size());
99  std::iota(activeIndices.begin(),activeIndices.end(),0);
100  for(std::size_t k=0; k != K; ++k){
101  std::size_t index = leastContributor(points,archive);
102 
103  points.erase(points.begin()+index);
104  indices.push_back(activeIndices[index]);
105  activeIndices.erase(activeIndices.begin()+index);
106  }
107  return indices;
108  }
109 
110  template<class random>
111  void init(std::size_t /*numOfObjectives*/, std::size_t /*mu*/, random& /*rng*/){}
112 
113  template<typename Archive>
114  void serialize( Archive &, const unsigned int ) {}
115 };
116 
117 }
118 
119 #endif