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-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_DIRECTSEARCH_HYPERVOLUMEINDICATOR_H
33 #define SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUMEINDICATOR_H
34 
35 #include <shark/Core/Exception.h>
36 #include <shark/Core/OpenMP.h>
38 #include <shark/LinAlg/Base.h>
39 
40 #include <algorithm>
41 #include <vector>
42 
43 namespace shark {
44 
45 /**
46 * \brief Calculates the hypervolume covered by a front of non-dominated points.
47 */
49 public:
50 
51  /**
52  * \brief Calculates the volume of a hyperfront using a reference point
53  *
54  * \param [in,out] extractor Extractor instance that maps elements of the front to \f$\mathbb{R}^d\f$.
55  * \param [in] front pareto front of points to calculate the hypervolume for.
56  * \param [in] referencePoint reference for measuring the hypervolume
57  */
58  template<typename Extractor, typename ParetoFrontType, typename VectorType>
59  double operator()( Extractor const& extractor, ParetoFrontType const& front, VectorType const& referencePoint) {
60 
61  if(front.empty()) return 0;
62 
63  return (m_hv( extractor, front, referencePoint) );
64  }
65 
66  /**
67  * \brief Executes the algorithm and calls to an instance of HypervolumeCalculator.
68  *
69  * This version uses the reference point estimated by the last call to updateInternals.
70  *
71  * \param [in] extractor Extractor instance that maps elements of the front to \f$\mathbb{R}^d\f$.
72  * \param [in] front front of points to calculate the hypervolume for.
73  */
74  template<typename Extractor, typename ParetoFrontType>
75  double operator()( Extractor const& extractor, ParetoFrontType const& front) {
76  return (*this)( extractor, front, m_reference);
77  }
78 
79  /**
80  * \brief Determines the individual contributing the least to the front it belongs to.
81  *
82  * \param [in] extractor Maps the individuals to the objective space.
83  * \param [in] front The front of non-dominated individuals.
84  * \param [in] referencePoint reference for measuring the hypervolume
85  */
86  template<typename Extractor, typename ParetoFrontType, typename VectorType>
87  std::size_t leastContributor( Extractor const& extractor, ParetoFrontType const& front, VectorType const& referencePoint)
88  {
89  std::vector<double> indicatorValues( front.size() );
90  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( front.size() ); i++ ) {
91 
92  HypervolumeIndicator ind(*this);
93 
94  ParetoFrontType copy( front );
95  copy.erase( copy.begin() + i );
96 
97  indicatorValues[i] = ind( extractor, copy,referencePoint);
98  std::cout<<i<<" "<<indicatorValues[i]<<std::endl;
99  }
100 
101  std::vector<double>::iterator it = std::max_element( indicatorValues.begin(), indicatorValues.end() );
102 
103  return std::distance( indicatorValues.begin(), it );
104  }
105 
106  /**
107  * \brief Determines the point contributing the least hypervolume to the overall front of points.
108  *
109  * This version uses the reference point estimated by the last call to updateInternals.
110  *
111  * \param [in] extractor Extracts point information from front elements.
112  * \param [in] front pareto front of points
113  */
114  template<typename Extractor, typename ParetoFrontType>
115  std::size_t leastContributor( Extractor const& extractor, ParetoFrontType const& front)
116  {
117  return leastContributor(extractor,front,m_reference);
118  }
119 
120  /// \brief Updates the internal variables of the indicator using a whole population.
121  ///
122  /// Calculates the reference point of the volume from the population
123  /// using the maximum value in every dimension+1
124  /// \param extractor Extracts point information from set.
125  /// \param set The set of points.
126  template<typename Extractor, typename PointSet>
127  void updateInternals(Extractor const& extractor, PointSet const& set){
128  m_reference.clear();
129  if(set.empty()) return;
130 
131  //calculate reference point
132  std::size_t noObjectives = extractor(set[0]).size();
133  m_reference.resize(noObjectives);
134  m_reference.clear();
135 
136  for( unsigned int i = 0; i < set.size(); i++ )
137  noalias(m_reference) = max(m_reference, extractor(set[i]));
138 
139  noalias(m_reference) += 1.0;
140  }
141 
142  /**
143  * \brief Serializes/Deserializes the state of the indicator to the supplied archive.
144  * \tparam Archive Archive type, needs to be a model of a boost::serialization archive.
145  * \param [in,out] archive Archive to store to/load from.
146  * \param [in] version Currently unused.
147  */
148  template<typename Archive>
149  void serialize( Archive & archive, const unsigned int version ) {
150  archive & BOOST_SERIALIZATION_NVP( m_hv );
151  archive & BOOST_SERIALIZATION_NVP( m_reference );
152  }
153 
155  RealVector m_reference;
156 };
157 }
158 
159 #endif