HypervolumeContributionMD.h
Go to the documentation of this file.
1 /*!
2  *
3  * \author O.Krause, T. Glasmachers
4  * \date 2014-2016
5  *
6  *
7  * \par Copyright 1995-2017 Shark Development Team
8  *
9  * <BR><HR>
10  * This file is part of Shark.
11  * <http://shark-ml.org/>
12  *
13  * Shark is free software: you can redistribute it and/or modify
14  * it under the terms of the GNU Lesser General Public License as published
15  * by the Free Software Foundation, either version 3 of the License, or
16  * (at your option) any later version.
17  *
18  * Shark is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU Lesser General Public License for more details.
22  *
23  * You should have received a copy of the GNU Lesser General Public License
24  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
25  *
26  */
27 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_MD_H
28 #define SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_MD_H
29 
30 #include <shark/LinAlg/Base.h>
32 #include <shark/Core/OpenMP.h>
35 
36 #include <algorithm>
37 #include <vector>
38 
39 namespace shark {
40 /// \brief Finds the hypervolume contribution for points in MD
41 ///
42 /// This implementation is slightly less naive. Instead of calculating Con{x\in S}=Hyp{S}-Hyp{S/x}
43 /// directly, we restrict the volume dominated by points in S to be inside the box [x,ref]. This
44 /// leads to points in S not being relevant for the computation and thus can be discarded using
45 /// a simple dominance test.
47  /// \brief Returns the index of the points with smallest contribution.
48  ///
49  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
50  /// \param [in] k The number of points to select.
51  /// \param [in] referencePointThe reference Point\f$\vec{r} \in \mathbb{R}^2\f$ for the hypervolume calculation, needs to fulfill: \f$ \forall s \in S: s \preceq \vec{r}\f$.
52  template<class Set, typename VectorType>
53  std::vector<KeyValuePair<double,std::size_t> > smallest(Set const& points, std::size_t k, VectorType const& ref)const{
54  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
56  std::vector<KeyValuePair<double,std::size_t> > result( points.size() );
57  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( points.size() ); i++ ) {
58  auto const& point = points[i];
59 
60  //compute restricted pointset
61  std::vector<RealVector> pointset( points.begin(), points.end() );
62  pointset.erase( pointset.begin() + i );
63  restrictSet(pointset,point);
64 
65  double baseVol = std::exp(sum(log(ref-point)));
66  result[i].key = baseVol - hv(pointset,ref);
67  result[i].value = i;
68  }
69  std::sort(result.begin(),result.end());
70  result.erase(result.begin()+k,result.end());
71 
72  return result;
73  }
74 
75  /// \brief Returns the index of the points with largest contribution.
76  ///
77  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
78  /// \param [in] referencePointThe reference Point\f$\vec{r} \in \mathbb{R}^2\f$ for the hypervolume calculation, needs to fulfill: \f$ \forall s \in S: s \preceq \vec{r}\f$.
79  template<class Set, typename VectorType>
80  std::vector<KeyValuePair<double,std::size_t> > largest(Set const& points, std::size_t k, VectorType const& ref)const{
81  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
83  std::vector<KeyValuePair<double,std::size_t> > result( points.size() );
84  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( points.size() ); i++ ) {
85  auto const& point = points[i];
86 
87  //compute restricted pointset
88  std::vector<RealVector> pointset( points.begin(), points.end() );
89  pointset.erase( pointset.begin() + i );
90  restrictSet(pointset,point);
91 
92  double baseVol = std::exp(sum(log(ref-point)));
93  result[i].key = baseVol - hv(pointset,ref);
94  result[i].value = i;
95  }
96  std::sort(result.begin(),result.end());
97  result.erase(result.begin(),result.end()-k);
98  std::reverse(result.begin(),result.end());
99  return result;
100  }
101 
102  /// \brief Returns the index of the points with smallest contribution.
103  ///
104  /// As no reference point is given, the extremum points can not be computed and are never selected.
105  ///
106  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
107  /// \param [in] k The number of points to select.
108  template<class Set>
109  std::vector<KeyValuePair<double,std::size_t> > smallest(Set const& points, std::size_t k)const{
110  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
111  //find reference point as well as points with lowest function value
112  std::vector<std::size_t> minIndex(points[0].size(),0);
113  RealVector minVal = points[0];
114  RealVector ref=points[0];
115  for(std::size_t i = 1; i != points.size(); ++i){
116  noalias(ref) = max(ref,points[i]);
117  for(std::size_t j = 0; j != minVal.size(); ++j){
118  if(points[i](j)< minVal[j]){
119  minVal[j] = points[i](j);
120  minIndex[j]=i;
121  }
122  }
123  }
125  std::vector<KeyValuePair<double,std::size_t> > result;
126  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( points.size() ); i++ ) {
127  if(std::find(minIndex.begin(),minIndex.end(),i) != minIndex.end())
128  continue;
129 
130  auto const& point = points[i];
131 
132  //compute restricted pointset
133  std::vector<RealVector> pointset( points.begin(), points.end() );
134  pointset.erase( pointset.begin() + i );
135  restrictSet(pointset,point);
136 
137  double baseVol = std::exp(sum(log(ref-point)));
138  double volume = baseVol - hv(pointset,ref);
140  result.emplace_back(volume,i);
141  }
142  }
143  std::sort(result.begin(),result.end());
144  result.erase(result.begin()+k,result.end());
145 
146  return result;
147  }
148 
149  /// \brief Returns the index of the points with largest contribution.
150  ///
151  /// As no reference point is given, the extremum points can not be computed and are never selected.
152  ///
153  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
154  /// \param [in] k The number of points to select.
155  template<class Set>
156  std::vector<KeyValuePair<double,std::size_t> > largest(Set const& points, std::size_t k)const{
157  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
158  //find reference point as well as points with lowest function value
159  std::vector<std::size_t> minIndex(points[0].size(),0);
160  RealVector minVal = points[0];
161  RealVector ref=points[0];
162  for(std::size_t i = 1; i != points.size(); ++i){
163  noalias(ref) = max(ref,points[i]);
164  for(std::size_t j = 0; j != minVal.size(); ++j){
165  if(points[i](j)< minVal[j]){
166  minVal[j] = points[i](j);
167  minIndex[j]=i;
168  }
169  }
170  }
171 
173  std::vector<KeyValuePair<double,std::size_t> > result;
174  SHARK_PARALLEL_FOR( int i = 0; i < static_cast< int >( points.size() ); i++ ) {
175  if(std::find(minIndex.begin(),minIndex.end(),i) != minIndex.end())
176  continue;
177  auto const& point = points[i];
178 
179  //compute restricted pointset
180  std::vector<RealVector> pointset( points.begin(), points.end() );
181  pointset.erase( pointset.begin() + i );
182  restrictSet(pointset,point);
183 
184  double baseVol = std::exp(sum(log(ref-point)));
185  double volume = baseVol - hv(pointset,ref);
187  result.emplace_back(volume,i);
188  }
189  }
190  std::sort(result.begin(),result.end());
191  result.erase(result.begin(),result.end()-k);
192  std::reverse(result.begin(),result.end());
193  return result;
194  }
195 private:
196  /// \brief Restrict the points to the area covered by point and remove all points which are then dominated
197  template<class Pointset, class Point>
198  void restrictSet(Pointset& pointset, Point const& point) const{
199  for(auto& p: pointset){
200  noalias(p) = max(p,point);
201  }
202  std::vector<std::size_t> ranks(pointset.size());
203  nonDominatedSort(pointset,ranks);
204  std::size_t end = pointset.size();
205  std::size_t pos = 0;
206  while(pos != end){
207  if(ranks[pos] == 1){
208  ++pos;
209  continue;
210  }
211  --end;
212  if(pos != end){
213  std::swap(pointset[pos],pointset[end]);
214  std::swap(ranks[pos],ranks[end]);
215  }
216  }
217  pointset.erase(pointset.begin() +end, pointset.end());
218  }
219 };
220 
221 }
222 #endif