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_DE_HPP 30 #define PAGMO_ALGORITHMS_DE_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 42 namespace pagmo 43 { 44 45 /// Differential Evolution Algorithm 46 /** 47 * \image html de.png "Differential Evolution block diagram." 48 * 49 * Differential Evolution is an heuristic optimizer developed by Rainer Storn and Kenneth Price. 50 * 51 * ''A breakthrough happened, when Ken came up with the idea of using vector differences for perturbing 52 * the vector population. Since this seminal idea a lively discussion between Ken and Rainer and endless 53 * ruminations and computer simulations on both parts yielded many substantial improvements which 54 * make DE the versatile and robust tool it is today'' (from the official web pages....) 55 * 56 * The implementation provided for PaGMO is based on the code provided in the official 57 * DE web site. pagmo::de is suitable for box-constrained single-objective continuous optimization. 58 * 59 * \verbatim embed:rst:leading-asterisk 60 * .. note:: 61 * 62 * The feasibility correction, that is the correction applied to an allele when some mutation puts it outside 63 * the allowed box-bounds, is here done by creating a random number in the bounds. 64 * 65 * .. seealso:: 66 * 67 * The paper that introduces Differential Evolution https://link.springer.com/article/10.1023%2FA%3A1008202821328 68 * 69 * \endverbatim 70 */ 71 class PAGMO_DLL_PUBLIC de 72 { 73 public: 74 /// Single entry of the log (gen, fevals, best, dx, df) 75 typedef std::tuple<unsigned, unsigned long long, double, double, double> log_line_type; 76 /// The log 77 typedef std::vector<log_line_type> log_type; 78 79 /// Constructor. 80 /** 81 * Constructs de 82 * 83 * The following variants (mutation variants) are available to create a new candidate individual: 84 * @code{.unparsed} 85 * 1 - best/1/exp 2. - rand/1/exp 86 * 3 - rand-to-best/1/exp 4. - best/2/exp 87 * 5 - rand/2/exp 6. - best/1/bin 88 * 7 - rand/1/bin 8. - rand-to-best/1/bin 89 * 9 - best/2/bin 10. - rand/2/bin 90 * @endcode 91 * 92 * @param gen number of generations. 93 * @param F weight coefficient (dafault value is 0.8) 94 * @param CR crossover probability (dafault value is 0.9) 95 * @param variant mutation variant (dafault variant is 2: /rand/1/exp) 96 * @param ftol stopping criteria on the f tolerance (default is 1e-6) 97 * @param xtol stopping criteria on the x tolerance (default is 1e-6) 98 * @param seed seed used by the internal random number generator (default is random) 99 100 * @throws std::invalid_argument if F, CR are not in [0,1] 101 * @throws std::invalid_argument if variant is not one of 1 .. 10 102 */ 103 de(unsigned gen = 1u, double F = 0.8, double CR = 0.9, unsigned variant = 2u, double ftol = 1e-6, 104 double xtol = 1e-6, unsigned seed = pagmo::random_device::next()); 105 106 // Evolve. 107 population evolve(population) const; 108 // Set the seed. 109 void set_seed(unsigned); 110 /// Get the seed 111 /** 112 * @return the seed controlling the algorithm stochastic behaviour 113 */ get_seed() const114 unsigned get_seed() const 115 { 116 return m_seed; 117 } 118 /// Sets the algorithm verbosity 119 /** 120 * Sets the verbosity level of the screen output and of the 121 * log returned by get_log(). \p level can be: 122 * - 0: no verbosity 123 * - >0: will print and log one line each \p level generations. 124 * 125 * Example (verbosity 100): 126 * @code{.unparsed} 127 * Gen: Fevals: Best: dx: df: 128 * 5001 100020 3.62028e-05 0.0396687 0.0002866 129 * 5101 102020 1.16784e-05 0.0473027 0.000249057 130 * 5201 104020 1.07883e-05 0.0455471 0.000243651 131 * 5301 106020 6.05099e-06 0.0268876 0.000103512 132 * 5401 108020 3.60664e-06 0.0230468 5.78161e-05 133 * 5501 110020 1.7188e-06 0.0141655 2.25688e-05 134 * @endcode 135 * Gen, is the generation number, Fevals the number of function evaluation used, Best is the best fitness 136 * function currently in the population, dx is the population flatness evaluated as the distance between 137 * the decisions vector of the best and of the worst individual, df is the population flatness evaluated 138 * as the distance between the fitness of the best and of the worst individual. 139 * 140 * @param level verbosity level 141 */ set_verbosity(unsigned level)142 void set_verbosity(unsigned level) 143 { 144 m_verbosity = level; 145 }; 146 /// Gets the verbosity level 147 /** 148 * @return the verbosity level 149 */ get_verbosity() const150 unsigned get_verbosity() const 151 { 152 return m_verbosity; 153 } 154 /// Gets the generations 155 /** 156 * @return the number of generations to evolve for 157 */ get_gen() const158 unsigned get_gen() const 159 { 160 return m_gen; 161 } 162 /// Algorithm name 163 /** 164 * One of the optional methods of any user-defined algorithm (UDA). 165 * 166 * @return a string containing the algorithm name 167 */ get_name() const168 std::string get_name() const 169 { 170 return "DE: Differential Evolution"; 171 } 172 // Extra info. 173 std::string get_extra_info() const; 174 /// Get log 175 /** 176 * A log containing relevant quantities monitoring the last call to evolve. Each element of the returned 177 * <tt>std::vector</tt> is a de::log_line_type containing: Gen, Fevals, Best, dx, df as described 178 * in de::set_verbosity 179 * @return an <tt>std::vector</tt> of de::log_line_type containing the logged values Gen, Fevals, Best, dx, df 180 */ get_log() const181 const log_type &get_log() const 182 { 183 return m_log; 184 } 185 186 private: 187 // Object serialization 188 friend class boost::serialization::access; 189 template <typename Archive> 190 void serialize(Archive &, unsigned); 191 192 unsigned m_gen; 193 double m_F; 194 double m_CR; 195 unsigned m_variant; 196 double m_Ftol; 197 double m_xtol; 198 mutable detail::random_engine_type m_e; 199 unsigned m_seed; 200 unsigned m_verbosity; 201 mutable log_type m_log; 202 }; 203 204 } // namespace pagmo 205 206 PAGMO_S11N_ALGORITHM_EXPORT_KEY(pagmo::de) 207 208 #endif 209