1 /* Copyright 2017-2021 PaGMO development team 2 3 This file is part of the PaGMO library. 4 5 The PaGMO library is free software; you can redistribute it and/or modify 6 it under the terms of either: 7 8 * the GNU Lesser General Public License as published by the Free 9 Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 or 13 14 * the GNU General Public License as published by the Free Software 15 Foundation; either version 3 of the License, or (at your option) any 16 later version. 17 18 or both in parallel, as here. 19 20 The PaGMO library is distributed in the hope that it will be useful, but 21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 22 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 23 for more details. 24 25 You should have received copies of the GNU General Public License and the 26 GNU Lesser General Public License along with the PaGMO library. If not, 27 see https://www.gnu.org/licenses/. */ 28 29 #ifndef PAGMO_UTILS_HV_BF_APPROX_HPP 30 #define PAGMO_UTILS_HV_BF_APPROX_HPP 31 32 #include <memory> 33 #include <string> 34 #include <vector> 35 36 #include <pagmo/detail/visibility.hpp> 37 #include <pagmo/rng.hpp> 38 #include <pagmo/types.hpp> 39 #include <pagmo/utils/hv_algos/hv_algorithm.hpp> 40 41 namespace pagmo 42 { 43 44 /// Bringmann-Friedrich approximation method 45 /** 46 * This is the class containing the implementation of the Bringmann-Friedrich approximation method for the computation 47 * of the least contributor to the hypervolume. 48 * Default values for the parameters of the algorithm were obtained from the shark implementation of the 49 * algorithm (http://image.diku.dk/shark/doxygen_pages/html/_least_contributor_approximator_8hpp_source.html) 50 * 51 * @see "Approximating the least hypervolume contributor: NP-hard in general, but fast in practice", Karl Bringmann, 52 * Tobias Friedrich. 53 * 54 */ 55 class PAGMO_DLL_PUBLIC bf_approx final : public hv_algorithm 56 { 57 public: 58 /// Constructor 59 /** 60 * Constructs an instance of the algorithm 61 * 62 * @param use_exact boolean flag stating whether algorithm is allowed to use exact algorithms for the computation 63 * @param trivial_subcase_size size of the sub-front (points overlapping the bounding box) for which algorithm 64 * skips to the exact computation right away 65 * @param eps accuracy of the approximation 66 * @param delta confidence of the approximation 67 * @param gamma constant used for computation of delta for each of the points during the sampling 68 * @param delta_multiplier factor with which delta diminishes each round 69 * @param initial_delta_coeff initial coefficient multiplied by the delta at round 0 70 * @param alpha coefficicient stating how accurately current lowest contributor should be sampled 71 * @param seed seeding for the pseudo-random number generator 72 */ 73 bf_approx(bool use_exact = true, unsigned trivial_subcase_size = 1, double eps = 1e-2, double delta = 1e-6, 74 double delta_multiplier = 0.775, double alpha = 0.2, double initial_delta_coeff = 0.1, 75 double gamma = 0.25, unsigned seed = pagmo::random_device::next()); 76 77 // Compute hypervolume 78 [[noreturn]] double compute(std::vector<vector_double> &, const vector_double &) const override; 79 80 // Least contributor method 81 unsigned long long least_contributor(std::vector<vector_double> &, const vector_double &) const override; 82 83 // Greatest contributor method 84 unsigned long long greatest_contributor(std::vector<vector_double> &, const vector_double &) const override; 85 86 // Verify before compute method 87 void verify_before_compute(const std::vector<vector_double> &, const vector_double &) const override; 88 89 // Clone method. 90 std::shared_ptr<hv_algorithm> clone() const override; 91 92 // Algorithm name 93 std::string get_name() const override; 94 95 private: 96 // Compute delta for given point 97 PAGMO_DLL_LOCAL double compute_point_delta(unsigned, vector_double::size_type, double) const; 98 99 // Compute bounding box method 100 PAGMO_DLL_LOCAL vector_double compute_bounding_box(const std::vector<vector_double> &, const vector_double &, 101 vector_double::size_type) const; 102 103 // Determine whether point 'p' influences the volume of box (a, b) 104 PAGMO_DLL_LOCAL int point_in_box(const vector_double &, const vector_double &, const vector_double &) const; 105 106 // Performs a single round of sampling for given point at index 'idx' 107 PAGMO_DLL_LOCAL void sampling_round(const std::vector<vector_double> &, double, unsigned, vector_double::size_type, 108 double) const; 109 110 // samples the bounding box and returns true if it fell into the exclusive hypervolume 111 PAGMO_DLL_LOCAL bool sample_successful(const std::vector<vector_double> &, vector_double::size_type) const; 112 113 enum extreme_contrib_type { LEAST = 1, GREATEST = 2 }; 114 115 // Approximated extreme contributor method 116 PAGMO_DLL_LOCAL vector_double::size_type approx_extreme_contributor( 117 std::vector<vector_double> &, const vector_double &, extreme_contrib_type, bool (*)(double, double), 118 bool (*)(vector_double::size_type, vector_double::size_type, vector_double &, vector_double &), 119 double (*)(vector_double::size_type, vector_double::size_type, vector_double &, vector_double &)) const; 120 121 // ---------------- 122 PAGMO_DLL_LOCAL static double lc_end_condition(vector_double::size_type, vector_double::size_type, vector_double &, 123 vector_double &); 124 125 PAGMO_DLL_LOCAL static double gc_end_condition(vector_double::size_type, vector_double::size_type, vector_double &, 126 vector_double &); 127 128 PAGMO_DLL_LOCAL static bool lc_erase_condition(vector_double::size_type, vector_double::size_type, vector_double &, 129 vector_double &); 130 131 PAGMO_DLL_LOCAL static bool gc_erase_condition(vector_double::size_type, vector_double::size_type, vector_double &, 132 vector_double &); 133 134 // flag stating whether BF approximation should use exact computation for some exclusive hypervolumes 135 const bool m_use_exact; 136 137 // if the number of points overlapping the bounding box is small enough we can just compute that exactly 138 // following variable states the number of points for which we perform the optimization 139 const unsigned m_trivial_subcase_size; 140 141 // accuracy of the approximation 142 const double m_eps; 143 144 // confidence of the approximation 145 const double m_delta; 146 147 // multiplier of the round delta value 148 const double m_delta_multiplier; 149 150 // alpha coefficient used for pushing on the sampling of the current least contributor 151 const double m_alpha; 152 153 // initial coefficient of the delta at round 0 154 const double m_initial_delta_coeff; 155 156 // constant used for the computation of point delta 157 const double m_gamma; 158 159 mutable detail::random_engine_type m_e; 160 161 /** 162 * 'least_contributor' method variables section 163 * 164 * Section below contains member variables that are relevant only to the least_contributor method. 165 * They are not serialized as the members below are irrelevant outside of that scope. 166 */ 167 // number of elementary operations performed for each point 168 mutable std::vector<vector_double::size_type> m_no_ops; 169 170 // number of samples for given box 171 mutable std::vector<vector_double::size_type> m_no_samples; 172 173 // number of "successful" samples that fell into the exclusive hypervolume 174 mutable std::vector<vector_double::size_type> m_no_succ_samples; 175 176 // stores the indices of points that were not yet removed during the progress of the algorithm 177 mutable std::vector<vector_double::size_type> m_point_set; 178 179 // exact hypervolumes of the bounding boxes 180 mutable vector_double m_box_volume; 181 182 // approximated exlusive hypervolume of each point 183 mutable vector_double m_approx_volume; 184 185 // deltas computed for each point using chernoff inequality component 186 mutable vector_double m_point_delta; 187 188 // pair (boxes[idx], points[idx]) form a box in which monte carlo sampling is performed 189 mutable std::vector<vector_double> m_boxes; 190 191 // list of indices of points that overlap the bounding box of each point 192 // during monte carlo sampling it suffices to check only these points when deciding whether the sampling was 193 // "successful" 194 mutable std::vector<std::vector<vector_double::size_type>> m_box_points; 195 /** 196 * End of 'least_contributor' method variables section 197 */ 198 }; 199 } // namespace pagmo 200 201 #endif 202