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_IHS_HPP 30 #define PAGMO_ALGORITHMS_IHS_HPP 31 32 #include <string> 33 #include <tuple> 34 #include <vector> 35 36 #include <pagmo/algorithm.hpp> 37 #include <pagmo/detail/visibility.hpp> 38 #include <pagmo/population.hpp> 39 #include <pagmo/rng.hpp> 40 #include <pagmo/s11n.hpp> 41 #include <pagmo/types.hpp> 42 43 namespace pagmo 44 { 45 46 /// Improved Harmony Search 47 /** 48 * \image html ihs.gif 49 * 50 * Harmony search (HS) is a metaheuristic algorithm said to mimick the improvisation process of musicians. 51 * In the metaphor, each musician (i.e., each variable) plays (i.e., generates) a note (i.e., a value) 52 * for finding a best harmony (i.e., the global optimum) all together. 53 * 54 * This code implements the so-called improved harmony search algorithm (IHS), in which the probability 55 * of picking the variables from the decision vector and the amount of mutation to which they are subject 56 * vary (respectively linearly and exponentially) at each call of the ``evolve()`` method. 57 * 58 * In this algorithm the number of fitness function evaluations is equal to the number of iterations. 59 * All the individuals in the input population participate in the evolution. A new individual is generated 60 * at every iteration, substituting the current worst individual of the population if better. 61 ** 62 * 63 * \verbatim embed:rst:leading-asterisk 64 * 65 * .. warning:: 66 * 67 * The HS algorithm can and has been criticized, not for its performances, 68 * but for the use of a metaphor that does not add anything to existing ones. The HS 69 * algorithm essentially applies mutation and crossover operators to a background population and as such 70 * should have been developed in the context of Evolutionary Strategies or Genetic Algorithms and studied 71 * in that context. The use of the musicians metaphor only obscures its internal functioning 72 * making theoretical results from ES and GA erroneously seem as unapplicable to HS. 73 * 74 * .. note:: 75 * 76 * The original IHS algorithm was designed to solve unconstrained, deterministic single objective problems. 77 * In pagmo, the algorithm was modified to tackle also multi-objective (unconstrained), constrained 78 * (single-objective), mixed-integer and stochastic problems. Such extension is original with pagmo. 79 * 80 * .. seealso:: 81 * 82 * https://en.wikipedia.org/wiki/Harmony_search for an introduction on harmony search. 83 * 84 * .. seealso:: 85 * 86 * https://linkinghub.elsevier.com/retrieve/pii/S0096300306015098 for the paper that introduces and explains improved 87 * harmony search. 88 * 89 * \endverbatim 90 */ 91 class PAGMO_DLL_PUBLIC ihs 92 { 93 public: 94 /// Single data line for the algorithm's log. 95 /** 96 * A log data line is a tuple consisting of: 97 * - the number of objective function evaluations made so far, 98 * - the pitch adjustment rate, 99 * - the distance bandwidth 100 * - the population flatness evaluated as the distance between the decisions vector of the best and of the worst 101 * individual (or -1 in a multiobjective case), 102 * - the population flatness evaluated as the distance between the fitness of the best and of the worst individual 103 * (or -1 in a multiobjective case), 104 * - the number of constraints violated by the current decision vector, 105 * - the constraints violation norm for the current decision vector, 106 * - the objective value of the best solution or, in the multiobjective case, the ideal point 107 */ 108 typedef std::tuple<unsigned long long, double, double, double, double, vector_double::size_type, double, 109 vector_double> 110 log_line_type; 111 /// Log type. 112 /** 113 * The algorithm log is a collection of ihs::log_line_type data lines, stored in chronological order 114 * during the optimisation if the verbosity of the algorithm is set to a nonzero value 115 * (see ihs::set_verbosity()). 116 */ 117 typedef std::vector<log_line_type> log_type; 118 119 /// Constructor 120 /** 121 * Constructs ihs 122 * 123 * @param gen Number of generations to consider. Each generation will compute the objective function once. 124 * @param phmcr probability of choosing from memory (similar to a crossover probability) 125 * @param ppar_min minimum pitch adjustment rate. (similar to a mutation rate) 126 * @param ppar_max maximum pitch adjustment rate. (similar to a mutation rate) 127 * @param bw_min minimum distance bandwidth. (similar to a mutation width) 128 * @param bw_max maximum distance bandwidth. (similar to a mutation width) 129 * @param seed seed used by the internal random number generator 130 * 131 * @throws value_error if phmcr is not in the ]0,1[ interval, ppar min/max are not in the ]0,1[ 132 * interval, min/max quantities are less than/greater than max/min quantities, bw_min is negative. 133 */ 134 ihs(unsigned gen = 1u, double phmcr = 0.85, double ppar_min = 0.35, double ppar_max = 0.99, double bw_min = 1E-5, 135 double bw_max = 1., unsigned seed = pagmo::random_device::next()); 136 137 // Algorithm evolve method 138 population evolve(population) const; 139 140 /// Set verbosity. 141 /** 142 * This method will set the algorithm's verbosity. If \p n is zero, no output is produced during the optimisation 143 * and no logging is performed. If \p n is nonzero, then every \p n objective function evaluations the status 144 * of the optimisation will be both printed to screen and recorded internally. See ihs::log_line_type and 145 * ihs::log_type for information on the logging format. The internal log can be fetched via get_log(). 146 * 147 * Example (verbosity 100, a constrained problem): 148 * @code{.unparsed} 149 * Fevals: ppar: bw: dx: df: Violated: Viol. Norm: ideal1: 150 * 1 0.35064 0.988553 5.17002 68.4027 1 0.0495288 85.1946 151 * 101 0.41464 0.312608 4.21626 46.248 1 0.0495288 85.1946 152 * 201 0.47864 0.0988553 2.27851 8.00679 1 0.0495288 85.1946 153 * 301 0.54264 0.0312608 3.94453 31.9834 1 0.0495288 85.1946 154 * 401 0.60664 0.00988553 4.74834 40.188 1 0.0495288 85.1946 155 * 501 0.67064 0.00312608 2.91583 6.53575 1 0.00904482 90.3601 156 * 601 0.73464 0.000988553 2.98691 10.6425 1 0.000760728 110.121 157 * 701 0.79864 0.000312608 2.27775 39.7507 1 0.000760728 110.121 158 * 801 0.86264 9.88553e-05 0.265908 4.5488 1 0.000760728 110.121 159 * 901 0.92664 3.12608e-05 0.566348 0.354253 1 0.000760728 110.121 160 * @endcode 161 * Feasibility is checked against the problem's tolerance. 162 * 163 * By default, the verbosity level is zero. 164 * 165 * @param n the desired verbosity level. 166 */ set_verbosity(unsigned n)167 void set_verbosity(unsigned n) 168 { 169 m_verbosity = n; 170 } 171 /// Gets the verbosity level 172 /** 173 * @return the verbosity level 174 */ get_verbosity() const175 unsigned get_verbosity() const 176 { 177 return m_verbosity; 178 } 179 // Sets the seed 180 void set_seed(unsigned); 181 182 /// Gets the seed 183 /** 184 * @return the seed controlling the algorithm stochastic behaviour 185 */ get_seed() const186 unsigned get_seed() const 187 { 188 return m_seed; 189 } 190 191 /// Algorithm name 192 /** 193 * One of the optional methods of any user-defined algorithm (UDA). 194 * 195 * @return a string containing the algorithm name 196 */ get_name() const197 std::string get_name() const 198 { 199 return "IHS: Improved Harmony Search"; 200 } 201 202 // Extra info 203 std::string get_extra_info() const; 204 205 /// Get the optimisation log. 206 /** 207 * See ihs::log_type for a description of the optimisation log. Logging is turned on/off via 208 * set_verbosity(). 209 * 210 * @return a const reference to the log. 211 */ get_log() const212 const log_type &get_log() const 213 { 214 return m_log; 215 } 216 217 private: 218 // Object serialization 219 friend class boost::serialization::access; 220 template <typename Archive> 221 void serialize(Archive &, unsigned); 222 223 // logging is complex fir ihs as the algorithm is an "any-problem" wannabe 224 PAGMO_DLL_LOCAL void log_a_line(const population &, unsigned &, unsigned long long, double, double) const; 225 226 unsigned m_gen; 227 double m_phmcr; 228 double m_ppar_min; 229 double m_ppar_max; 230 double m_bw_min; 231 double m_bw_max; 232 mutable detail::random_engine_type m_e; 233 unsigned m_seed; 234 unsigned m_verbosity; 235 mutable log_type m_log; 236 }; 237 238 } // namespace pagmo 239 240 PAGMO_S11N_ALGORITHM_EXPORT_KEY(pagmo::ihs) 241 242 #endif 243