HypervolumeIndicator.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Calculates the hypervolume covered by a front of non-dominated points.
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_DIRECTSEARCH_INDICATORS_HYPERVOLUMEINDICATOR_H
33 #define SHARK_ALGORITHMS_DIRECTSEARCH_INDICATORS_HYPERVOLUMEINDICATOR_H
34 
35 #include <shark/Core/Exception.h>
36 #include <shark/Core/OpenMP.h>
38 
39 #include <algorithm>
40 #include <vector>
41 #include <numeric>
42 
43 namespace shark {
44 
45 /// \brief Calculates the hypervolume covered by a front of non-dominated points.
46 ///
47 /// If given, the Indicator uses a provided reference value that can be set via setReference.
48 /// Otherwise, it is computed from the data by using the maximum value in the set. As this usually
49 /// gives 0 contribution to the extremum points (i.e. the ones with best function value), those
50 /// points are skipped when computing the contribution (i.e. extremum points are never selected).
51 /// Note, that for boundary points that are not extrema, this does not hold and they are selected.
52 ///
53 /// for problems with many objectives, an approximative algorithm can be used.
55  /// \brief Determines the point contributing the least hypervolume to the overall front of points.
56  ///
57  /// \param [in] front pareto front of points
58  template<typename ParetoFrontType, typename ParetoArchive>
59  std::size_t leastContributor( ParetoFrontType const& front, ParetoArchive const& /*archive*/)const{
60  HypervolumeContribution algorithm;
61  if(m_reference.size() != 0)
62  return m_algorithm.smallest(front,1,m_reference)[0].value;
63  else
64  return m_algorithm.smallest(front,1)[0].value;
65  }
66 
67  template<typename ParetoFrontType, typename ParetoArchive>
68  std::vector<std::size_t> leastContributors( ParetoFrontType const& front, ParetoArchive const& archive, std::size_t K)const{
69  std::vector<std::size_t> indices;
70  std::vector<RealVector> points(front.begin(),front.end());
71  std::vector<std::size_t> activeIndices(points.size());
72  std::iota(activeIndices.begin(),activeIndices.end(),0);
73  for(std::size_t k=0; k != K; ++k){
74  std::size_t index = leastContributor(points,archive);
75 
76  points.erase(points.begin()+index);
77  indices.push_back(activeIndices[index]);
78  activeIndices.erase(activeIndices.begin()+index);
79  }
80  return indices;
81  }
82 
83  template<class random>
84  void init(std::size_t /*numOfObjectives*/, std::size_t /*mu*/, random& /*rng*/){}
85 
86  /// \brief Sets the reference point.
87  ///
88  /// If no point is set, it is estimated from the current front and the extremum points are never selected.
89  void setReference(RealVector const& newReference){
90  m_reference = newReference;
91  }
92 
93  /// \brief Whether the approximtive algorithm should be used on large problems
95  m_algorithm.useApproximation(useApproximation);
96  }
97 
98  ///\brief Error bound for the approximative algorithm
99  double approximationEpsilon()const{
100  return m_algorithm.approximationEpsilon();
101  }
102  ///\brief Error bound for the approximative algorithm
104  return m_algorithm.approximationEpsilon();
105  }
106 
107  ///\brief Error probability for the approximative algorithm
108  double approximationDelta()const{
109  return m_algorithm.approximationDelta();
110  }
111 
112  ///\brief Error probability for the approximative algorithm
114  return m_algorithm.approximationDelta();
115  }
116 
117  template<typename Archive>
118  void serialize( Archive & archive, const unsigned int version ) {
119  archive & BOOST_SERIALIZATION_NVP( m_reference );
120  archive & BOOST_SERIALIZATION_NVP( m_algorithm );
121  }
122 
123 private:
124  RealVector m_reference;
125  HypervolumeContribution m_algorithm;
126 };
127 }
128 
129 #endif