| 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_DETAIL_COMMON_HPP |
| 8 |
#define BOOST_MATH_OPTIMIZATION_DETAIL_COMMON_HPP |
| 9 |
#include <algorithm> // for std::sort |
| 10 |
#include <cmath> |
| 11 |
#include <limits> |
| 12 |
#include <sstream> |
| 13 |
#include <stdexcept> |
| 14 |
#include <random> |
| 15 |
#include <type_traits> // for std::false_type |
| 16 |
|
| 17 |
namespace boost::math::optimization::detail { |
| 18 |
|
| 19 |
template <typename T, typename = void> struct has_resize : std::false_type {}; |
| 20 |
|
| 21 |
template <typename T> |
| 22 |
struct has_resize<T, std::void_t<decltype(std::declval<T>().resize(size_t{}))>> : std::true_type {}; |
| 23 |
|
| 24 |
template <typename T> constexpr bool has_resize_v = has_resize<T>::value; |
| 25 |
|
| 26 |
template <typename ArgumentContainer> |
| 27 |
void validate_bounds(ArgumentContainer const &lower_bounds, ArgumentContainer const &upper_bounds) { |
| 28 |
using std::isfinite; |
| 29 |
std::ostringstream oss; |
| 30 |
if (lower_bounds.size() == 0) { |
| 31 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 32 |
oss << ": The dimension of the problem cannot be zero."; |
| 33 |
throw std::domain_error(oss.str()); |
| 34 |
} |
| 35 |
if (upper_bounds.size() != lower_bounds.size()) { |
| 36 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 37 |
oss << ": There must be the same number of lower bounds as upper bounds, but given "; |
| 38 |
oss << upper_bounds.size() << " upper bounds, and " << lower_bounds.size() << " lower bounds."; |
| 39 |
throw std::domain_error(oss.str()); |
| 40 |
} |
| 41 |
for (size_t i = 0; i < lower_bounds.size(); ++i) { |
| 42 |
auto lb = lower_bounds[i]; |
| 43 |
auto ub = upper_bounds[i]; |
| 44 |
if (lb > ub) { |
| 45 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 46 |
oss << ": The upper bound must be greater than or equal to the lower bound, but the upper bound is " << ub |
| 47 |
<< " and the lower is " << lb << "."; |
| 48 |
throw std::domain_error(oss.str()); |
| 49 |
} |
| 50 |
if (!isfinite(lb)) { |
| 51 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 52 |
oss << ": The lower bound must be finite, but got " << lb << "."; |
| 53 |
oss << " For infinite bounds, emulate with std::numeric_limits<Real>::lower() or use a standard infinite->finite " |
| 54 |
"transform."; |
| 55 |
throw std::domain_error(oss.str()); |
| 56 |
} |
| 57 |
if (!isfinite(ub)) { |
| 58 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 59 |
oss << ": The upper bound must be finite, but got " << ub << "."; |
| 60 |
oss << " For infinite bounds, emulate with std::numeric_limits<Real>::max() or use a standard infinite->finite " |
| 61 |
"transform."; |
| 62 |
throw std::domain_error(oss.str()); |
| 63 |
} |
| 64 |
} |
| 65 |
} |
| 66 |
|
| 67 |
template <typename ArgumentContainer, class URBG> |
| 68 |
std::vector<ArgumentContainer> random_initial_population(ArgumentContainer const &lower_bounds, |
| 69 |
ArgumentContainer const &upper_bounds, |
| 70 |
size_t initial_population_size, URBG &&gen) { |
| 71 |
using Real = typename ArgumentContainer::value_type; |
| 72 |
using DimensionlessReal = decltype(Real()/Real()); |
| 73 |
constexpr bool has_resize = detail::has_resize_v<ArgumentContainer>; |
| 74 |
std::vector<ArgumentContainer> population(initial_population_size); |
| 75 |
auto const dimension = lower_bounds.size(); |
| 76 |
for (size_t i = 0; i < population.size(); ++i) { |
| 77 |
if constexpr (has_resize) { |
| 78 |
population[i].resize(dimension); |
| 79 |
} else { |
| 80 |
// Argument type must be known at compile-time; like std::array: |
| 81 |
if (population[i].size() != dimension) { |
| 82 |
std::ostringstream oss; |
| 83 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 84 |
oss << ": For containers which do not have resize, the default size must be the same as the dimension, "; |
| 85 |
oss << "but the default container size is " << population[i].size() << " and the dimension of the problem is " |
| 86 |
<< dimension << "."; |
| 87 |
oss << " The function argument container type is " << typeid(ArgumentContainer).name() << ".\n"; |
| 88 |
throw std::runtime_error(oss.str()); |
| 89 |
} |
| 90 |
} |
| 91 |
} |
| 92 |
|
| 93 |
// Why don't we provide an option to initialize with (say) a Gaussian distribution? |
| 94 |
// > If the optimum's location is fairly well known, |
| 95 |
// > a Gaussian distribution may prove somewhat faster, although it |
| 96 |
// > may also increase the probability that the population will converge prematurely. |
| 97 |
// > In general, uniform distributions are preferred, since they best reflect |
| 98 |
// > the lack of knowledge about the optimum's location. |
| 99 |
// - Differential Evolution: A Practical Approach to Global Optimization |
| 100 |
// That said, scipy uses Latin Hypercube sampling and says self-avoiding sequences are preferable. |
| 101 |
// So this is something that could be investigated and potentially improved. |
| 102 |
using std::uniform_real_distribution; |
| 103 |
uniform_real_distribution<DimensionlessReal> dis(DimensionlessReal(0), DimensionlessReal(1)); |
| 104 |
for (size_t i = 0; i < population.size(); ++i) { |
| 105 |
for (size_t j = 0; j < dimension; ++j) { |
| 106 |
auto const &lb = lower_bounds[j]; |
| 107 |
auto const &ub = upper_bounds[j]; |
| 108 |
population[i][j] = lb + dis(gen) * (ub - lb); |
| 109 |
} |
| 110 |
} |
| 111 |
|
| 112 |
return population; |
| 113 |
} |
| 114 |
|
| 115 |
template <typename ArgumentContainer> |
| 116 |
void validate_initial_guess(ArgumentContainer const &initial_guess, ArgumentContainer const &lower_bounds, |
| 117 |
ArgumentContainer const &upper_bounds) { |
| 118 |
using std::isfinite; |
| 119 |
std::ostringstream oss; |
| 120 |
auto const dimension = lower_bounds.size(); |
| 121 |
if (initial_guess.size() != dimension) { |
| 122 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 123 |
oss << ": The initial guess must have the same dimensions as the problem,"; |
| 124 |
oss << ", but the problem size is " << dimension << " and the initial guess has " << initial_guess.size() |
| 125 |
<< " elements."; |
| 126 |
throw std::domain_error(oss.str()); |
| 127 |
} |
| 128 |
for (size_t i = 0; i < dimension; ++i) { |
| 129 |
auto lb = lower_bounds[i]; |
| 130 |
auto ub = upper_bounds[i]; |
| 131 |
if (!isfinite(initial_guess[i])) { |
| 132 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 133 |
oss << ": At index " << i << ", the initial guess is " << initial_guess[i] |
| 134 |
<< ", make sure all elements of the initial guess are finite."; |
| 135 |
throw std::domain_error(oss.str()); |
| 136 |
} |
| 137 |
if (initial_guess[i] < lb || initial_guess[i] > ub) { |
| 138 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 139 |
oss << ": At index " << i << " the initial guess " << initial_guess[i] << " is not in the bounds [" << lb << ", " |
| 140 |
<< ub << "]."; |
| 141 |
throw std::domain_error(oss.str()); |
| 142 |
} |
| 143 |
} |
| 144 |
} |
| 145 |
|
| 146 |
// Return indices corresponding to the minimum function values. |
| 147 |
template <typename Real> std::vector<size_t> best_indices(std::vector<Real> const &function_values) { |
| 148 |
using std::isnan; |
| 149 |
const size_t n = function_values.size(); |
| 150 |
std::vector<size_t> indices(n); |
| 151 |
for (size_t i = 0; i < n; ++i) { |
| 152 |
indices[i] = i; |
| 153 |
} |
| 154 |
|
| 155 |
std::sort(indices.begin(), indices.end(), [&](size_t a, size_t b) { |
| 156 |
if (isnan(function_values[a])) { |
| 157 |
return false; |
| 158 |
} |
| 159 |
if (isnan(function_values[b])) { |
| 160 |
return true; |
| 161 |
} |
| 162 |
return function_values[a] < function_values[b]; |
| 163 |
}); |
| 164 |
return indices; |
| 165 |
} |
| 166 |
|
| 167 |
template<typename RandomAccessContainer> |
| 168 |
auto weighted_lehmer_mean(RandomAccessContainer const & values, RandomAccessContainer const & weights) { |
| 169 |
using std::isfinite; |
| 170 |
if (values.size() != weights.size()) { |
| 171 |
std::ostringstream oss; |
| 172 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 173 |
oss << ": There must be the same number of weights as values, but got " << values.size() << " values and " << weights.size() << " weights."; |
| 174 |
throw std::logic_error(oss.str()); |
| 175 |
} |
| 176 |
if (values.size() == 0) { |
| 177 |
std::ostringstream oss; |
| 178 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 179 |
oss << ": There must at least one value provided."; |
| 180 |
throw std::logic_error(oss.str()); |
| 181 |
} |
| 182 |
using Real = typename RandomAccessContainer::value_type; |
| 183 |
Real numerator = 0; |
| 184 |
Real denominator = 0; |
| 185 |
for (size_t i = 0; i < values.size(); ++i) { |
| 186 |
if (weights[i] < 0 || !isfinite(weights[i])) { |
| 187 |
std::ostringstream oss; |
| 188 |
oss << __FILE__ << ":" << __LINE__ << ":" << __func__; |
| 189 |
oss << ": All weights must be positive and finite, but got received weight " << weights[i] << " at index " << i << " of " << weights.size() << "."; |
| 190 |
throw std::domain_error(oss.str()); |
| 191 |
} |
| 192 |
Real tmp = weights[i]*values[i]; |
| 193 |
numerator += tmp*values[i]; |
| 194 |
denominator += tmp; |
| 195 |
} |
| 196 |
return numerator/denominator; |
| 197 |
} |
| 198 |
|
| 199 |
} // namespace boost::math::optimization::detail |
| 200 |
#endif |