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_ALGORITHMS_CSTRS_SELF_ADAPTIVE_HPP 30 #define PAGMO_ALGORITHMS_CSTRS_SELF_ADAPTIVE_HPP 31 32 #include <cassert> 33 #include <iostream> 34 #include <string> 35 #include <tuple> 36 #include <type_traits> 37 #include <unordered_map> 38 #include <utility> 39 #include <vector> 40 41 #include <pagmo/algorithm.hpp> 42 #include <pagmo/detail/custom_comparisons.hpp> 43 #include <pagmo/detail/visibility.hpp> 44 #include <pagmo/population.hpp> 45 #include <pagmo/rng.hpp> 46 #include <pagmo/s11n.hpp> 47 #include <pagmo/type_traits.hpp> 48 #include <pagmo/types.hpp> 49 50 namespace pagmo 51 { 52 namespace detail 53 { 54 55 // Constrainted self adaptive udp 56 /** 57 * Implements a udp that wraps a population and results in self adaptive constraints handling. 58 * 59 * The key idea of this constraint handling technique is to represent the constraint violation by one single 60 * infeasibility measure, and to adapt dynamically the penalization of infeasible solutions. As the penalization process 61 * depends on a given population, a method to update the penalties to a new population is provided. 62 * 63 * @see Farmani R., & Wright, J. A. (2003). Self-adaptive fitness formulation for constrained optimization. 64 * Evolutionary Computation, IEEE Transactions on, 7(5), 445-455 for the paper introducing the method. 65 * 66 */ 67 // TODO this UDP has a series of problems, some of which are summarized 68 // in these reports: 69 // https://github.com/esa/pagmo2/issues/270 70 // https://github.com/esa/pagmo2/issues/269 71 // 72 // The UDP does not correctly advertises its own thread safety 73 // level (which depends on the thread safety level of the internal pop, 74 // but cannot currently be larger than basic, due to the mutable cache). 75 // Also, the UDP is not serializable, which will be an issue if the 76 // cstrs internal uda requires serialization. 77 // 78 // Proposals to start fixing the UDP: 79 // - don't store a pointer to the pop, rather a copy (this allows 80 // for trivial serialization). Impact to be understood; 81 // - properly declare the thread safety level; 82 // - the cache can be an *optional* speed boost: if, in cstrs, 83 // we cannot locate a decision vector in the cache (meaning that 84 // the UDA operated on a copy of the original input problem), just re-evaluate 85 // the dv instead of asserting failure. 86 struct PAGMO_DLL_PUBLIC penalized_udp { 87 // Unused default constructor to please the is_udp type trait penalized_udppagmo::detail::penalized_udp88 penalized_udp() 89 { 90 assert(false); 91 } 92 93 // Constructs the udp. At construction all member get initialized calling update(). 94 penalized_udp(population &); 95 96 // The bounds are unchanged 97 std::pair<vector_double, vector_double> get_bounds() const; 98 99 // The fitness computation 100 vector_double fitness(const vector_double &) const; 101 102 // Call to this method updates all the members that are used to penalize the objective function 103 // As the penalization algorithm depends heavily on the ref population this method takes care of 104 // updating the necessary information. It also builds the hash map used to avoid unecessary fitness 105 // evaluations. We exclude this method from the test as all of its corner cases are difficult to trigger 106 // and test for correctness 107 PAGMO_DLL_LOCAL void update(); 108 109 // Computes c_max holding the maximum value of the violation of each constraint in the whole ref population 110 PAGMO_DLL_LOCAL void compute_c_max(); 111 112 // Assuming the various data member contain useful information, this computes the 113 // infeasibility measure of a certain fitness 114 PAGMO_DLL_LOCAL double compute_infeasibility(const vector_double &) const; 115 116 // According to the population, the first penalty may or may not be applied 117 bool m_apply_penalty_1; 118 // The parameter gamma that scales the second penalty 119 double m_scaling_factor; 120 // The normalization of each constraint 121 vector_double m_c_max; 122 // The fitness of the three reference individuals 123 vector_double m_f_hat_down; 124 vector_double m_f_hat_up; 125 vector_double m_f_hat_round; 126 // The infeasibilities of the three reference individuals 127 double m_i_hat_down; 128 double m_i_hat_up; 129 double m_i_hat_round; 130 131 vector_double::size_type m_n_feasible; 132 // A NAKED pointer to the reference population, allowing to call the fitness function and later recover 133 // the counters outside of the class, and avoiding unecessary copies. Use with care. 134 population *m_pop_ptr; 135 // The hash map connecting the decision vector to their fitnesses. The use of 136 // custom comparison is needed to take care of nans, while the custom hasher is needed as std::hash does not 137 // work on std::vectors 138 mutable std::unordered_map<vector_double, vector_double, detail::hash_vf<double>, detail::equal_to_vf<double>> 139 m_fitness_map; 140 }; 141 142 // Only for debug purposes 143 PAGMO_DLL_PUBLIC std::ostream &operator<<(std::ostream &, const penalized_udp &); 144 145 } // namespace detail 146 147 /// Self-adaptive constraints handling 148 /** 149 * 150 * This meta-algorithm implements a constraint handling technique that allows the use of any user-defined algorithm 151 * (UDA) able to deal with single-objective unconstrained problems, on single-objective constrained problems. The 152 * technique self-adapts its parameters during 153 * each successive call to the inner UDA basing its decisions on the entire underlying population. The resulting 154 * approach is an alternative to using the meta-problem pagmo::unconstrain to transform the 155 * constrained fitness into an unconstrained fitness. 156 * 157 * The self-adaptive constraints handling meta-algorithm is largely based on the ideas of Faramani and Wright but it 158 * extends their use to any-algorithm, in particular to non generational population based evolutionary approaches where 159 * a steady-state reinsertion is used (i.e., as soon as an individual is found fit it is immediately reinserted into the 160 * pop and will influence the next offspring genetic material). 161 * 162 * Each decision vector is assigned an infeasibility measure \f$\iota\f$ which accounts for the normalized violation of 163 * all the constraints (discounted by the constraints tolerance as returned by pagmo::problem::get_c_tol()). The 164 * normalization factor used \f$c_{j_{max}}\f$ is the maximum violation of the \f$j-th\f$ constraint. 165 * 166 * As in the original paper, three individuals in the evolving population are then used to penalize the single 167 * objective. 168 * 169 * \f[ 170 * \begin{array}{rl} 171 * \check X & \mbox{: the best decision vector} \\ 172 * \hat X & \mbox{: the worst decision vector} \\ 173 * \breve X & \mbox{: the decision vector with the highest objective} 174 * \end{array} 175 * \f] 176 * 177 * The best and worst decision vectors are defined accounting for their infeasibilities and for the value of the 178 * objective function. Using the above definitions the overall pseudo code can be summarized as follows: 179 * 180 * @code{.unparsed} 181 * > Select a pagmo::population (related to a single-objective constrained problem) 182 * > Select a UDA (able to solve single-objective unconstrained problems) 183 * > while i < iter 184 * > > Compute the normalization factors (will depend on the current population) 185 * > > Compute the best, worst, highest (will depend on the current population) 186 * > > Evolve the population using the UDA and a penalized objective 187 * > > Reinsert the best decision vector from the previous evolution 188 * @endcode 189 * 190 * pagmo::cstrs_self_adaptive is a user-defined algorithm (UDA) that can be used to construct pagmo::algorithm objects. 191 * 192 * \verbatim embed:rst:leading-asterisk 193 * .. note:: 194 * 195 * Self-adaptive constraints handling implements an internal cache to avoid the re-evaluation of the fitness 196 * for decision vectors already evaluated. This makes the final counter of function evaluations somewhat 197 * unpredictable. The number of function evaluation will be bounded to ``iters`` times the fevals made by one call to 198 * the inner UDA. The internal cache is reset at each iteration, but its size will grow unlimited during each call to 199 * the inner UDA evolve method. 200 * 201 * .. note:: 202 * 203 * Several modification were made to the original Faramani and Wright ideas to allow their approach to work on 204 * corner cases and with any UDAs. Most notably, a violation to the :math:`j`-th constraint is ignored if all 205 * the decision vectors in the population satisfy that particular constraint (i.e. if :math:`c_{j_{max}} = 0`). 206 * 207 * .. note:: 208 * 209 * The performances of :cpp:class:`pagmo::cstrs_self_adaptive` are highly dependent on the particular inner UDA 210 * employed and in particular to its parameters (generations / iterations). 211 * 212 * .. seealso:: 213 * 214 * Farmani, Raziyeh, and Jonathan A. Wright. "Self-adaptive fitness formulation for constrained optimization." IEEE 215 * Transactions on Evolutionary Computation 7.5 (2003): 445-455. 216 * 217 * \endverbatim 218 */ 219 class PAGMO_DLL_PUBLIC cstrs_self_adaptive 220 { 221 public: 222 /// Single entry of the log (iter, fevals, best_f, infeas, n. constraints violated, violation norm). 223 typedef std::tuple<unsigned, unsigned long long, double, double, vector_double::size_type, double, 224 vector_double::size_type> 225 log_line_type; 226 /// The log. 227 typedef std::vector<log_line_type> log_type; 228 /// Default constructor. 229 /** 230 * @param iters Number of iterations (calls to the inner UDA). After each iteration the penalty is adapted 231 * The default constructor will initialize the algorithm with the following parameters: 232 * - inner algorithm: pagmo::de{1u}; 233 * - seed: random. 234 */ 235 cstrs_self_adaptive(unsigned iters = 1u); 236 237 private: 238 // Enabler for the ctor from UDA. 239 template <typename T> 240 using ctor_enabler = enable_if_t<std::is_constructible<algorithm, T &&>::value, int>; 241 242 public: 243 /// Constructor. 244 /** 245 * 246 * @param iters Number of iterations (calls to the inner algorithm). After each iteration the penalty is adapted 247 * @param a a pagmo::algorithm (or UDA) that will be used to construct the inner algorithm. 248 * @param seed seed used by the internal random number generator (default is random). 249 * 250 * @throws unspecified any exception thrown by the constructor of pagmo::algorithm. 251 */ 252 template <typename T, ctor_enabler<T> = 0> cstrs_self_adaptive(unsigned iters,T && a,unsigned seed=pagmo::random_device::next ())253 explicit cstrs_self_adaptive(unsigned iters, T &&a, unsigned seed = pagmo::random_device::next()) 254 : m_algorithm(std::forward<T>(a)), m_iters(iters), m_e(seed), m_seed(seed), m_verbosity(0u), m_log() 255 { 256 } 257 258 // Evolve method. 259 population evolve(population) const; 260 261 // Set the seed. 262 void set_seed(unsigned); 263 264 /// Get the seed. 265 /** 266 * @return the seed controlling the algorithm's stochastic behaviour. 267 */ get_seed() const268 unsigned get_seed() const 269 { 270 return m_seed; 271 } 272 273 /// Set the algorithm verbosity. 274 /** 275 * This method will sets the verbosity level of the screen output and of the 276 * log returned by get_log(). \p level can be: 277 * - 0: no verbosity, 278 * - >0: will print and log one line each \p level call to the inner algorithm. 279 * 280 * Example (verbosity 10): 281 * @code{.unparsed} 282 * Iter: Fevals: Best: Infeasibility: Violated: Viol. Norm: N. Feasible: 283 * 1 0 -69.2141 0.235562 6 117.743 0 i 284 * 11 200 -69.2141 0.248216 6 117.743 0 i 285 * 21 400 -29.4754 0.0711599 5 44.39 0 i 286 * 31 600 -30.0791 0.0878253 4 44.3803 0 i 287 * ... ... ........ ......... . ....... . . 288 * 211 4190 -7.68336 0.000341894 1 0.273829 0 i 289 * 221 4390 -7.89941 0.00031154 1 0.273829 0 i 290 * 231 4590 -8.38299 0.000168309 1 0.147935 0 i 291 * 241 4790 -8.38299 0.000181461 1 0.147935 0 i 292 * 251 4989 -8.71021 0.000191197 1 0.100357 0 i 293 * 261 5189 -8.71021 0.000165734 1 0.100357 0 i 294 * 271 5389 -10.7421 0 0 0 3 295 * 281 5585 -10.7421 0 0 0 3 296 * 291 5784 -11.4868 0 0 0 4 297 * 298 * @endcode 299 * \p Iter is the iteration number, \p Fevals is the number of fitness evaluations, \p Best is the objective 300 * function of the best fitness currently in the population, \p Infeasibility is the normailized infeasibility 301 * measure, \p Violated is the number of constraints currently violated by the best solution, <tt>Viol. Norm</tt> is 302 * the norm of the violation (discounted already by the constraints tolerance) and N. Feasible is the number of 303 * feasible individuals in the current iteration. The small \p i appearing at the end of the line stands for 304 * "infeasible" and will disappear only once \p Violated is 0. 305 * 306 * @param level verbosity level. 307 */ set_verbosity(unsigned level)308 void set_verbosity(unsigned level) 309 { 310 m_verbosity = level; 311 } 312 313 /// Get the verbosity level. 314 /** 315 * @return the verbosity level. 316 */ get_verbosity() const317 unsigned get_verbosity() const 318 { 319 return m_verbosity; 320 } 321 322 /// Get log. 323 /** 324 * A log containing relevant quantities monitoring the last call to cstrs_self_adaptive::evolve(). Each element of 325 * the returned <tt>std::vector</tt> is a cstrs_self_adaptive::log_line_type containing: \p Iter, \p Fevals, \p 326 * Best, \p Infeasibility, \p Violated, <tt>Viol. Norm</tt>, <tt>N. Feasible</tt> as described in 327 * cstrs_self_adaptive::set_verbosity(). 328 * 329 * @return an <tt>std::vector</tt> of cstrs_self_adaptive::log_line_type containing the logged values Iters, 330 * Fevals, Best, Infeasibility, Violated and Viol. Norm and N. Feasible. 331 */ get_log() const332 const log_type &get_log() const 333 { 334 return m_log; 335 } 336 337 /// Algorithm name 338 /** 339 * @return a string containing the algorithm name. 340 */ get_name() const341 std::string get_name() const 342 { 343 return "sa-CNSTR: Self-adaptive constraints handling"; 344 } 345 346 // Extra info 347 std::string get_extra_info() const; 348 349 // Algorithm's thread safety level. 350 thread_safety get_thread_safety() const; 351 352 /// Getter for the inner algorithm. 353 /** 354 * Returns a const reference to the inner pagmo::algorithm. 355 * 356 * @return a const reference to the inner pagmo::algorithm. 357 */ get_inner_algorithm() const358 const algorithm &get_inner_algorithm() const 359 { 360 return m_algorithm; 361 } 362 363 /// Getter for the inner problem. 364 /** 365 * Returns a reference to the inner pagmo::algorithm. 366 * 367 * \verbatim embed:rst:leading-asterisk 368 * .. note:: 369 * 370 * The ability to extract a non const reference is provided only in order to allow to call 371 * non-const methods on the internal :cpp:class:`pagmo::algorithm` instance. Assigning a new 372 * :cpp:class:`pagmo::algorithm` via this reference is undefined behaviour. 373 * 374 * \endverbatim 375 * 376 * @return a reference to the inner pagmo::algorithm. 377 */ get_inner_algorithm()378 algorithm &get_inner_algorithm() 379 { 380 return m_algorithm; 381 } 382 383 private: 384 // Object serialization 385 friend class boost::serialization::access; 386 template <typename Archive> 387 void serialize(Archive &, unsigned); 388 389 // Inner algorithm 390 algorithm m_algorithm; 391 unsigned m_iters; 392 mutable detail::random_engine_type m_e; 393 unsigned m_seed; 394 unsigned m_verbosity; 395 mutable log_type m_log; 396 }; 397 398 } // namespace pagmo 399 400 PAGMO_S11N_ALGORITHM_EXPORT_KEY(pagmo::cstrs_self_adaptive) 401 402 #endif 403