AdditiveEpsilonIndicator.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Calculates the additive approximation quality of a Pareto-front
5  * approximation.
6  *
7  *
8  *
9  * \author T.Voss, O.Krause
10  * \date 2010-2014
11  *
12  *
13  * \par Copyright 1995-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_INDICATORS_ADDITIVE_EPSILON_INDICATOR_H
34 #define SHARK_ALGORITHMS_DIRECT_SEARCH_INDICATORS_ADDITIVE_EPSILON_INDICATOR_H
35 
36 #include <shark/LinAlg/Base.h>
37 #include <shark/LinAlg/Base.h>
38 #include <shark/Core/OpenMP.h>
39 
40 #include <algorithm>
41 #include <limits>
42 #include <vector>
43 
44 
45 namespace shark {
46 
47 /**
48  * \brief Given a reference front R and an approximation F, calculates the
49  * additive approximation quality of F.
50  *
51  * See the following reference for further details:
52  * - Bringmann, Friedrich, Neumann, Wagner. Approximation-Guided Evolutionary Multi-Objective Optimization. IJCAI '11.
53  */
55 
56  /**
57  * \brief Executes the algorithm for the given ranges of individuals and returns the additive approximation ratio.
58  *
59  * \param [in] itPF Iterator pointing to the first valid individual of the front approximation.
60  * \param [in] itePF Iterator pointing behind the last valid individual of the front approximation.
61  * \param [in] itRF Iterator pointing to the first valid individual of the reference front.
62  * \param [in] iteRF Iterator pointing behind the last valid individual of the reference front.
63  * \param [in,out] e Extractor instance that maps elements of the set to \f$\mathbb{R}^d\f$.
64  */
65  template<
66  typename IteratorTypeA,
67  typename IteratorTypeB,
68  typename Extractor
69  >
70  double operator()( IteratorTypeA itPF, IteratorTypeA itePF, IteratorTypeB itRF, IteratorTypeB iteRF, Extractor & e ){
71  double result = -std::numeric_limits<double>::max();
72  for( IteratorTypeB itb = itRF; itb != iteRF; ++itb ) {
73  double delta = std::numeric_limits<double>::max();
74  for( IteratorTypeA ita = itPF; ita != itePF;++ita ) {
75  SIZE_CHECK(e( *ita ).size() == e( *itb ).size());
76  delta = std::min( delta, max(e(*itb)-e(*ita)) );
77  }
78  result = std::max( result, delta );
79  }
80 
81  return result;
82  }
83 
84  /// \brief Given a pareto front, returns the index of the points which is the least contributer
85  template<typename Extractor, typename ParetofrontType>
86  unsigned int leastContributor( Extractor extractor, const ParetofrontType & front)
87  {
88  std::vector<double> relativeApproximation(front.size());
89  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( front.size() ); i++ ) {
90  //find the minimum distance the front with one point removed has to be moved to dominate the original front
91  double result = -std::numeric_limits<double>::max();
92  for(std::size_t j = 0; j != front.size(); ++j){
93  if(j == i) continue; //this point is removed
94  result = std::min<double>(result,max(extractor(front[i])-extractor(front[j])));
95  }
96  relativeApproximation[i] = result;
97  }
98 
99  return std::min_element( relativeApproximation.begin(), relativeApproximation.end() ) - relativeApproximation.begin();
100  }
101 
102  /// \brief Updates the internal variables of the indicator using a whole population.
103  ///
104  /// Empty for this Indicator
105  /// \param extractor Functor returning the fitness values
106  /// \param set The set of points.
107  template<typename Extractor, typename PointSet>
108  void updateInternals(Extractor extractor, PointSet const& set){
109  (void)extractor;
110  (void)set;
111  }
112 
113  template<typename Archive>
114  void serialize( Archive & archive, const unsigned int version ) {
115  (void)archive;
116  (void)version;
117  }
118 };
119 
120 }
121 
122 #endif