Debian Codegraph @

third-party/boost-math/include/boost/math/optimization/differential_evolution.hpp

raw
1 /*
2 * Copyright Nick Thompson, 2024
3 * Use, modification and distribution are subject to the
4 * Boost Software License, Version 1.0. (See accompanying file
5 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 */
7 #ifndef BOOST_MATH_OPTIMIZATION_DIFFERENTIAL_EVOLUTION_HPP
8 #define BOOST_MATH_OPTIMIZATION_DIFFERENTIAL_EVOLUTION_HPP
9 #include <atomic>
10 #include <boost/math/optimization/detail/common.hpp>
11 #include <cmath>
12 #include <limits>
13 #include <mutex>
14 #include <random>
15 #include <sstream>
16 #include <stdexcept>
17 #include <thread>
18 #include <utility>
19 #include <vector>
20
21 namespace boost::math::optimization {
22
23 // Storn, R., Price, K. (1997). Differential evolution-a simple and efficient heuristic for global optimization over
24 // continuous spaces.
25 // Journal of global optimization, 11, 341-359.
26 // See:
27 // https://www.cp.eng.chula.ac.th/~prabhas//teaching/ec/ec2012/storn_price_de.pdf
28
29 // We provide the parameters in a struct-there are too many of them and they are too unwieldy to pass individually:
30 template <typename ArgumentContainer> struct differential_evolution_parameters {
31 using Real = typename ArgumentContainer::value_type;
32 using DimensionlessReal = decltype(Real()/Real());
33 ArgumentContainer lower_bounds;
34 ArgumentContainer upper_bounds;
35 // mutation factor is also called scale factor or just F in the literature:
36 DimensionlessReal mutation_factor = static_cast<DimensionlessReal>(0.65);
37 DimensionlessReal crossover_probability = static_cast<DimensionlessReal>(0.5);
38 // Population in each generation:
39 size_t NP = 500;
40 size_t max_generations = 1000;
41 ArgumentContainer const *initial_guess = nullptr;
42 unsigned threads = std::thread::hardware_concurrency();
43 };
44
45 template <typename ArgumentContainer>
46 void validate_differential_evolution_parameters(differential_evolution_parameters<ArgumentContainer> const &de_params) {
47 using std::isfinite;
48 using std::isnan;
49 std::ostringstream oss;
50 detail::validate_bounds(de_params.lower_bounds, de_params.upper_bounds);
51 if (de_params.NP < 4) {
52 oss << __FILE__ << ":" << __LINE__ << ":" << __func__;
53 oss << ": The population size must be at least 4, but requested population size of " << de_params.NP << ".";
54 throw std::invalid_argument(oss.str());
55 }
56 // From: "Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series)"
57 // > The scale factor, F in (0,1+), is a positive real number that controls the rate at which the population evolves.
58 // > While there is no upper limit on F, effective values are seldom greater than 1.0.
59 // ...
60 // Also see "Limits on F", Section 2.5.1:
61 // > This discontinuity at F = 1 reduces the number of mutants by half and can result in erratic convergence...
62 auto F = de_params.mutation_factor;
63 if (isnan(F) || F >= 1 || F <= 0) {
64 oss << __FILE__ << ":" << __LINE__ << ":" << __func__;
65 oss << ": F in (0, 1) is required, but got F=" << F << ".";
66 throw std::domain_error(oss.str());
67 }
68 if (de_params.max_generations < 1) {
69 oss << __FILE__ << ":" << __LINE__ << ":" << __func__;
70 oss << ": There must be at least one generation.";
71 throw std::invalid_argument(oss.str());
72 }
73 if (de_params.initial_guess) {
74 detail::validate_initial_guess(*de_params.initial_guess, de_params.lower_bounds, de_params.upper_bounds);
75 }
76 if (de_params.threads == 0) {
77 oss << __FILE__ << ":" << __LINE__ << ":" << __func__;
78 oss << ": There must be at least one thread.";
79 throw std::invalid_argument(oss.str());
80 }
81 }
82
83 template <typename ArgumentContainer, class Func, class URBG>
84 ArgumentContainer differential_evolution(
85 const Func cost_function, differential_evolution_parameters<ArgumentContainer> const &de_params, URBG &gen,
86 std::invoke_result_t<Func, ArgumentContainer> target_value =
87 std::numeric_limits<std::invoke_result_t<Func, ArgumentContainer>>::quiet_NaN(),
88 std::atomic<bool> *cancellation = nullptr,
89 std::atomic<std::invoke_result_t<Func, ArgumentContainer>> *current_minimum_cost = nullptr,
90 std::vector<std::pair<ArgumentContainer, std::invoke_result_t<Func, ArgumentContainer>>> *queries = nullptr) {
91 using Real = typename ArgumentContainer::value_type;
92 using DimensionlessReal = decltype(Real()/Real());
93 using ResultType = std::invoke_result_t<Func, ArgumentContainer>;
94 using std::clamp;
95 using std::isnan;
96 using std::round;
97 using std::uniform_real_distribution;
98 validate_differential_evolution_parameters(de_params);
99 const size_t dimension = de_params.lower_bounds.size();
100 auto NP = de_params.NP;
101 auto population = detail::random_initial_population(de_params.lower_bounds, de_params.upper_bounds, NP, gen);
102 if (de_params.initial_guess) {
103 population[0] = *de_params.initial_guess;
104 }
105 std::vector<ResultType> cost(NP, std::numeric_limits<ResultType>::quiet_NaN());
106 std::atomic<bool> target_attained = false;
107 // This mutex is only used if the queries are stored:
108 std::mutex mt;
109
110 std::vector<std::thread> thread_pool;
111 auto const threads = de_params.threads;
112 for (size_t j = 0; j < threads; ++j) {
113 // Note that if some members of the population take way longer to compute,
114 // then this parallelization strategy is very suboptimal.
115 // However, we tried using std::async (which should be robust to this particular problem),
116 // but the overhead was just totally unacceptable on ARM Macs (the only platform tested).
117 // As the economists say "there are no solutions, only tradeoffs".
118 thread_pool.emplace_back([&, j]() {
119 for (size_t i = j; i < cost.size(); i += threads) {
120 cost[i] = cost_function(population[i]);
121 if (current_minimum_cost && cost[i] < *current_minimum_cost) {
122 *current_minimum_cost = cost[i];
123 }
124 if (queries) {
125 std::scoped_lock lock(mt);
126 queries->push_back(std::make_pair(population[i], cost[i]));
127 }
128 if (!isnan(target_value) && cost[i] <= target_value) {
129 target_attained = true;
130 }
131 }
132 });
133 }
134 for (auto &thread : thread_pool) {
135 thread.join();
136 }
137
138 std::vector<ArgumentContainer> trial_vectors(NP);
139 for (size_t i = 0; i < NP; ++i) {
140 if constexpr (detail::has_resize_v<ArgumentContainer>) {
141 trial_vectors[i].resize(dimension);
142 }
143 }
144 std::vector<URBG> thread_generators(threads);
145 for (size_t j = 0; j < threads; ++j) {
146 thread_generators[j].seed(gen());
147 }
148 // std::vector<bool> isn't threadsafe!
149 std::vector<int> updated_indices(NP, 0);
150
151 for (size_t generation = 0; generation < de_params.max_generations; ++generation) {
152 if (cancellation && *cancellation) {
153 break;
154 }
155 if (target_attained) {
156 break;
157 }
158 thread_pool.resize(0);
159 for (size_t j = 0; j < threads; ++j) {
160 thread_pool.emplace_back([&, j]() {
161 auto& tlg = thread_generators[j];
162 uniform_real_distribution<DimensionlessReal> unif01(DimensionlessReal(0), DimensionlessReal(1));
163 for (size_t i = j; i < cost.size(); i += threads) {
164 if (target_attained) {
165 return;
166 }
167 if (cancellation && *cancellation) {
168 return;
169 }
170 size_t r1, r2, r3;
171 do {
172 r1 = tlg() % NP;
173 } while (r1 == i);
174 do {
175 r2 = tlg() % NP;
176 } while (r2 == i || r2 == r1);
177 do {
178 r3 = tlg() % NP;
179 } while (r3 == i || r3 == r2 || r3 == r1);
180
181 for (size_t k = 0; k < dimension; ++k) {
182 // See equation (4) of the reference:
183 auto guaranteed_changed_idx = tlg() % dimension;
184 if (unif01(tlg) < de_params.crossover_probability || k == guaranteed_changed_idx) {
185 auto tmp = population[r1][k] + de_params.mutation_factor * (population[r2][k] - population[r3][k]);
186 auto const &lb = de_params.lower_bounds[k];
187 auto const &ub = de_params.upper_bounds[k];
188 // Some others recommend regenerating the indices rather than clamping;
189 // I dunno seems like it could get stuck regenerating . . .
190 trial_vectors[i][k] = clamp(tmp, lb, ub);
191 } else {
192 trial_vectors[i][k] = population[i][k];
193 }
194 }
195
196 auto const trial_cost = cost_function(trial_vectors[i]);
197 if (isnan(trial_cost)) {
198 continue;
199 }
200 if (queries) {
201 std::scoped_lock lock(mt);
202 queries->push_back(std::make_pair(trial_vectors[i], trial_cost));
203 }
204 if (trial_cost < cost[i] || isnan(cost[i])) {
205 cost[i] = trial_cost;
206 if (!isnan(target_value) && cost[i] <= target_value) {
207 target_attained = true;
208 }
209 if (current_minimum_cost && cost[i] < *current_minimum_cost) {
210 *current_minimum_cost = cost[i];
211 }
212 // Can't do this! It's a race condition!
213 //population[i] = trial_vectors[i];
214 // Instead mark all the indices that need to be updated:
215 updated_indices[i] = 1;
216 }
217 }
218 });
219 }
220 for (auto &thread : thread_pool) {
221 thread.join();
222 }
223 for (size_t i = 0; i < NP; ++i) {
224 if (updated_indices[i]) {
225 population[i] = trial_vectors[i];
226 updated_indices[i] = 0;
227 }
228 }
229 }
230
231 auto it = std::min_element(cost.begin(), cost.end());
232 return population[std::distance(cost.begin(), it)];
233 }
234
235 } // namespace boost::math::optimization
236 #endif