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-2017 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://shark-ml.org/>
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_DIRECTSEARCH_INDICATORS_ADDITIVE_EPSILON_INDICATOR_H
34 #define SHARK_ALGORITHMS_DIRECTSEARCH_INDICATORS_ADDITIVE_EPSILON_INDICATOR_H
35 
36 #include <shark/LinAlg/Base.h>
37 #include <limits>
38 
39 namespace shark {
40 
41 /// \brief Implements the Additive approximation properties of sets
42 ///
43 /// The additive approximation measures which value must be subtracted from a reference set
44 /// until it becomes dominated by a target set.
45 ///
46 /// The implemented least contributor algorithm calculates the point
47 /// That is approximated best by the remaining points. Thus the reference set is the full set and the target
48 /// sets all in which one point is removed.
49 ///
50 /// See the following reference for further details:
51 /// - Bringmann, Friedrich, Neumann, Wagner. Approximation-Guided Evolutionary Multi-Objective Optimization. IJCAI '11.
53  /// \brief Given a pareto front, returns the index of the point which is the least contributer
54  ///
55  /// The archive has no effect on the volume as the archive is dominating all points in the front
56  template<typename ParetoFrontType, typename ParetoArchive>
57  std::size_t leastContributor( ParetoFrontType const& front, ParetoArchive const& /*archive*/)const{
58  std::size_t leastIndex = 0;
59  double leastValue = std::numeric_limits<double>::max();
60  for( std::size_t i = 0; i != front.size(); i++ ) {
61  //find the minimum distance the front with one point removed has to be moved to dominate the original front
62  double result = std::numeric_limits<double>::max();
63  for(std::size_t j = 0; j != front.size(); ++j){
64  if(j == i) continue; //this point is removed
65  result = std::min(result,max(front[j]-front[i]));
66  }
67  if(result < leastValue){
68  leastValue = result;
69  leastIndex = i;
70  }
71  }
72  //~ std::cout<<leastIndex<<" "<<leastValue<<std::endl;
73  return leastIndex;
74  }
75 
76  template<typename ParetoFrontType, typename ParetoArchive>
77  std::vector<std::size_t> leastContributors( ParetoFrontType const& front, ParetoArchive const& archive, std::size_t K)const{
78  std::vector<std::size_t> indices;
79  std::vector<RealVector> points(front.begin(),front.end());
80  std::vector<std::size_t> activeIndices(points.size());
81  std::iota(activeIndices.begin(),activeIndices.end(),0);
82  for(std::size_t k=0; k != K; ++k){
83  std::size_t index = leastContributor(points,archive);
84 
85  points.erase(points.begin()+index);
86  indices.push_back(activeIndices[index]);
87  activeIndices.erase(activeIndices.begin()+index);
88  }
89  return indices;
90  }
91 
92  template<class random>
93  void init(std::size_t /*numOfObjectives*/, std::size_t /*mu*/, random& /*rng*/){}
94 
95  template<typename Archive>
96  void serialize( Archive &, const unsigned int ) {}
97 };
98 
99 }
100 
101 #endif