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 #include <algorithm>
30 #include <atomic>
31 #include <cassert>
32 #include <cmath>
33 #include <initializer_list>
34 #include <iostream>
35 #include <limits>
36 #include <stdexcept>
37 #include <string>
38 #include <typeindex>
39 #include <utility>
40 #include <vector>
41
42 #include <boost/numeric/conversion/cast.hpp>
43
44 #include <pagmo/detail/bfe_impl.hpp>
45 #include <pagmo/detail/type_name.hpp>
46 #include <pagmo/exceptions.hpp>
47 #include <pagmo/io.hpp>
48 #include <pagmo/problem.hpp>
49 #include <pagmo/problems/null_problem.hpp>
50 #include <pagmo/types.hpp>
51 #include <pagmo/utils/constrained.hpp>
52
53 // MINGW-specific warnings.
54 #if defined(__GNUC__) && defined(__MINGW32__)
55 #pragma GCC diagnostic push
56 #pragma GCC diagnostic ignored "-Wsuggest-attribute=pure"
57 #endif
58
59 namespace pagmo
60 {
61
62 namespace detail
63 {
64
check_problem_bounds(const std::pair<vector_double,vector_double> & bounds,vector_double::size_type nix)65 void check_problem_bounds(const std::pair<vector_double, vector_double> &bounds, vector_double::size_type nix)
66 {
67 const auto &lb = bounds.first;
68 const auto &ub = bounds.second;
69 // 0 - Check that the size is at least 1.
70 if (lb.size() == 0u) {
71 pagmo_throw(std::invalid_argument, "The bounds dimension cannot be zero");
72 }
73 // 1 - check bounds have equal length
74 if (lb.size() != ub.size()) {
75 pagmo_throw(std::invalid_argument, "The length of the lower bounds vector is " + std::to_string(lb.size())
76 + ", the length of the upper bounds vector is "
77 + std::to_string(ub.size()));
78 }
79 // 2 - checks lower < upper for all values in lb, ub, and check for nans.
80 for (decltype(lb.size()) i = 0u; i < lb.size(); ++i) {
81 if (std::isnan(lb[i]) || std::isnan(ub[i])) {
82 pagmo_throw(std::invalid_argument,
83 "A NaN value was encountered in the problem bounds, index: " + std::to_string(i));
84 }
85 if (lb[i] > ub[i]) {
86 pagmo_throw(std::invalid_argument,
87 "The lower bound at position " + std::to_string(i) + " is " + std::to_string(lb[i])
88 + " while the upper bound has the smaller value " + std::to_string(ub[i]));
89 }
90 }
91 // 3 - checks the integer part
92 if (nix) {
93 const auto nx = lb.size();
94 if (nix > nx) {
95 pagmo_throw(std::invalid_argument, "The integer part cannot be larger than the bounds size");
96 }
97 const auto ncx = nx - nix;
98 for (auto i = ncx; i < nx; ++i) {
99 if (std::isfinite(lb[i]) && lb[i] != std::trunc(lb[i])) {
100 pagmo_throw(std::invalid_argument, "A lower bound of the integer part of the decision vector is: "
101 + std::to_string(lb[i]) + " and is not an integer.");
102 }
103 if (std::isfinite(ub[i]) && ub[i] != std::trunc(ub[i])) {
104 pagmo_throw(std::invalid_argument, "An upper bound of the integer part of the decision vector is: "
105 + std::to_string(ub[i]) + " and is not an integer.");
106 }
107 }
108 }
109 }
110
111 // Helper functions to compute sparsity patterns in the dense case.
112 // A single dense hessian (lower triangular symmetric matrix).
dense_hessian(vector_double::size_type dim)113 sparsity_pattern dense_hessian(vector_double::size_type dim)
114 {
115 sparsity_pattern retval;
116 for (decltype(dim) j = 0u; j < dim; ++j) {
117 for (decltype(dim) i = 0u; i <= j; ++i) {
118 retval.emplace_back(j, i);
119 }
120 }
121 return retval;
122 }
123
124 // A collection of f_dim identical dense hessians.
dense_hessians(vector_double::size_type f_dim,vector_double::size_type dim)125 std::vector<sparsity_pattern> dense_hessians(vector_double::size_type f_dim, vector_double::size_type dim)
126 {
127 return std::vector<sparsity_pattern>(boost::numeric_cast<std::vector<sparsity_pattern>::size_type>(f_dim),
128 dense_hessian(dim));
129 }
130
131 // Dense gradient.
dense_gradient(vector_double::size_type f_dim,vector_double::size_type dim)132 sparsity_pattern dense_gradient(vector_double::size_type f_dim, vector_double::size_type dim)
133 {
134 sparsity_pattern retval;
135 for (decltype(f_dim) j = 0u; j < f_dim; ++j) {
136 for (decltype(dim) i = 0u; i < dim; ++i) {
137 retval.emplace_back(j, i);
138 }
139 }
140 return retval;
141 }
142
143 } // namespace detail
144
145 /// Default constructor.
146 /**
147 * The default constructor will initialize a pagmo::problem containing a pagmo::null_problem.
148 *
149 * @throws unspecified any exception thrown by the constructor from UDP.
150 */
problem()151 problem::problem() : problem(null_problem{}) {}
152
153 // Implementation of the generic ctor.
generic_ctor_impl()154 void problem::generic_ctor_impl()
155 {
156 // 0 - Integer part
157 const auto tmp_size = ptr()->get_bounds().first.size();
158 m_nix = ptr()->get_nix();
159 if (m_nix > tmp_size) {
160 pagmo_throw(std::invalid_argument, "The integer part of the problem (" + std::to_string(m_nix)
161 + ") is larger than its dimension (" + std::to_string(tmp_size) + ")");
162 }
163 // 1 - Bounds.
164 auto bounds = ptr()->get_bounds();
165 detail::check_problem_bounds(bounds, m_nix);
166 m_lb = std::move(bounds.first);
167 m_ub = std::move(bounds.second);
168 // 2 - Number of objectives.
169 m_nobj = ptr()->get_nobj();
170 if (!m_nobj) {
171 pagmo_throw(std::invalid_argument, "The number of objectives cannot be zero");
172 }
173 // NOTE: here we check that we can always compute nobj + nec + nic safely.
174 if (m_nobj > std::numeric_limits<vector_double::size_type>::max() / 3u) {
175 pagmo_throw(std::invalid_argument, "The number of objectives is too large");
176 }
177 // 3 - Constraints.
178 m_nec = ptr()->get_nec();
179 if (m_nec > std::numeric_limits<vector_double::size_type>::max() / 3u) {
180 pagmo_throw(std::invalid_argument, "The number of equality constraints is too large");
181 }
182 m_nic = ptr()->get_nic();
183 if (m_nic > std::numeric_limits<vector_double::size_type>::max() / 3u) {
184 pagmo_throw(std::invalid_argument, "The number of inequality constraints is too large");
185 }
186 // 4 - Presence of batch_fitness().
187 // NOTE: all these m_has_* attributes refer to the presence of the features in the UDP.
188 m_has_batch_fitness = ptr()->has_batch_fitness();
189 // 5 - Presence of gradient and its sparsity.
190 m_has_gradient = ptr()->has_gradient();
191 m_has_gradient_sparsity = ptr()->has_gradient_sparsity();
192 // 6 - Presence of Hessians and their sparsity.
193 m_has_hessians = ptr()->has_hessians();
194 m_has_hessians_sparsity = ptr()->has_hessians_sparsity();
195 // 7 - Is this a stochastic problem?
196 m_has_set_seed = ptr()->has_set_seed();
197 // 8 - Name.
198 m_name = ptr()->get_name();
199 // 9 - Check the sparsities, and cache their sizes.
200 if (m_has_gradient_sparsity) {
201 // If the problem provides gradient sparsity, get it, check it
202 // and store its size.
203 const auto gs = ptr()->gradient_sparsity();
204 check_gradient_sparsity(gs);
205 m_gs_dim = gs.size();
206 } else {
207 // If the problem does not provide gradient sparsity, we assume dense
208 // sparsity. We can compute easily the expected size of the sparsity
209 // in this case.
210 const auto nx = get_nx();
211 const auto nf = get_nf();
212 if (nx > std::numeric_limits<vector_double::size_type>::max() / nf) {
213 pagmo_throw(std::invalid_argument, "The size of the (dense) gradient sparsity is too large");
214 }
215 m_gs_dim = nx * nf;
216 }
217 // Same as above for the hessians.
218 if (m_has_hessians_sparsity) {
219 const auto hs = ptr()->hessians_sparsity();
220 check_hessians_sparsity(hs);
221 for (const auto &one_hs : hs) {
222 m_hs_dim.push_back(one_hs.size());
223 }
224 } else {
225 const auto nx = get_nx();
226 const auto nf = get_nf();
227 if (nx == std::numeric_limits<vector_double::size_type>::max()
228 || nx / 2u > std::numeric_limits<vector_double::size_type>::max() / (nx + 1u)) {
229 pagmo_throw(std::invalid_argument, "The size of the (dense) hessians sparsity is too large");
230 }
231 // We resize rather than push back here, so that an std::length_error is called quickly rather
232 // than an std::bad_alloc after waiting the growth
233 m_hs_dim.resize(boost::numeric_cast<decltype(m_hs_dim.size())>(nf));
234 std::fill(m_hs_dim.begin(), m_hs_dim.end(), nx * (nx - 1u) / 2u + nx); // lower triangular
235 }
236 // 10 - Constraint tolerance
237 m_c_tol.resize(m_nec + m_nic);
238 // 11 - Thread safety.
239 m_thread_safety = ptr()->get_thread_safety();
240 }
241
242 /// Copy constructor.
243 /**
244 * The copy constructor will deep copy the input problem \p other.
245 *
246 * @param other the problem to be copied.
247 *
248 * @throws unspecified any exception thrown by:
249 * - memory allocation errors in standard containers,
250 * - the copying of the internal UDP.
251 */
problem(const problem & other)252 problem::problem(const problem &other)
253 : m_ptr(other.ptr()->clone()), m_fevals(other.m_fevals.load(std::memory_order_relaxed)),
254 m_gevals(other.m_gevals.load(std::memory_order_relaxed)),
255 m_hevals(other.m_hevals.load(std::memory_order_relaxed)), m_lb(other.m_lb), m_ub(other.m_ub),
256 m_nobj(other.m_nobj), m_nec(other.m_nec), m_nic(other.m_nic), m_nix(other.m_nix), m_c_tol(other.m_c_tol),
257 m_has_batch_fitness(other.m_has_batch_fitness), m_has_gradient(other.m_has_gradient),
258 m_has_gradient_sparsity(other.m_has_gradient_sparsity), m_has_hessians(other.m_has_hessians),
259 m_has_hessians_sparsity(other.m_has_hessians_sparsity), m_has_set_seed(other.m_has_set_seed),
260 m_name(other.m_name), m_gs_dim(other.m_gs_dim), m_hs_dim(other.m_hs_dim), m_thread_safety(other.m_thread_safety)
261 {
262 }
263
264 /// Move constructor.
265 /**
266 * @param other the problem from which \p this will be move-constructed.
267 */
problem(problem && other)268 problem::problem(problem &&other) noexcept
269 : m_ptr(std::move(other.m_ptr)), m_fevals(other.m_fevals.load(std::memory_order_relaxed)),
270 m_gevals(other.m_gevals.load(std::memory_order_relaxed)),
271 m_hevals(other.m_hevals.load(std::memory_order_relaxed)), m_lb(std::move(other.m_lb)),
272 m_ub(std::move(other.m_ub)), m_nobj(other.m_nobj), m_nec(other.m_nec), m_nic(other.m_nic), m_nix(other.m_nix),
273 m_c_tol(std::move(other.m_c_tol)), m_has_batch_fitness(other.m_has_batch_fitness),
274 m_has_gradient(other.m_has_gradient), m_has_gradient_sparsity(other.m_has_gradient_sparsity),
275 m_has_hessians(other.m_has_hessians), m_has_hessians_sparsity(other.m_has_hessians_sparsity),
276 m_has_set_seed(other.m_has_set_seed), m_name(std::move(other.m_name)), m_gs_dim(other.m_gs_dim),
277 m_hs_dim(other.m_hs_dim), m_thread_safety(std::move(other.m_thread_safety))
278 {
279 }
280
281 /// Move assignment operator
282 /**
283 * @param other the assignment target.
284 *
285 * @return a reference to \p this.
286 */
operator =(problem && other)287 problem &problem::operator=(problem &&other) noexcept
288 {
289 if (this != &other) {
290 m_ptr = std::move(other.m_ptr);
291 m_fevals.store(other.m_fevals.load(std::memory_order_relaxed), std::memory_order_relaxed);
292 m_gevals.store(other.m_gevals.load(std::memory_order_relaxed), std::memory_order_relaxed);
293 m_hevals.store(other.m_hevals.load(std::memory_order_relaxed), std::memory_order_relaxed);
294 m_lb = std::move(other.m_lb);
295 m_ub = std::move(other.m_ub);
296 m_nobj = other.m_nobj;
297 m_nec = other.m_nec;
298 m_nic = other.m_nic;
299 m_nix = other.m_nix;
300 m_c_tol = std::move(other.m_c_tol);
301 m_has_batch_fitness = other.m_has_batch_fitness;
302 m_has_gradient = other.m_has_gradient;
303 m_has_gradient_sparsity = other.m_has_gradient_sparsity;
304 m_has_hessians = other.m_has_hessians;
305 m_has_hessians_sparsity = other.m_has_hessians_sparsity;
306 m_has_set_seed = other.m_has_set_seed;
307 m_name = std::move(other.m_name);
308 m_gs_dim = other.m_gs_dim;
309 m_hs_dim = std::move(other.m_hs_dim);
310 m_thread_safety = std::move(other.m_thread_safety);
311 }
312 return *this;
313 }
314
315 /// Copy assignment operator
316 /**
317 * Copy assignment is implemented as a copy constructor followed by a move assignment.
318 *
319 * @param other the assignment target.
320 *
321 * @return a reference to \p this.
322 *
323 * @throws unspecified any exception thrown by the copy constructor.
324 */
operator =(const problem & other)325 problem &problem::operator=(const problem &other)
326 {
327 // Copy ctor + move assignment.
328 return *this = problem(other);
329 }
330
331 /// Fitness.
332 /**
333 * This method will invoke the <tt>%fitness()</tt> method of the UDP to compute the fitness of the
334 * input decision vector \p dv. The return value of the <tt>%fitness()</tt> method of the UDP is expected to have a
335 * dimension of \f$n_{f} = n_{obj} + n_{ec} + n_{ic}\f$
336 * and to contain the concatenated values of \f$\mathbf f, \mathbf c_e\f$ and \f$\mathbf c_i\f$ (in this order).
337 * Equality constraints are all assumed in the form \f$c_{e_i}(\mathbf x) = 0\f$ while inequalities are assumed in
338 * the form \f$c_{i_i}(\mathbf x) <= 0\f$ so that negative values are associated to satisfied inequalities.
339 *
340 * In addition to invoking the <tt>%fitness()</tt> method of the UDP, this method will perform sanity checks on
341 * \p dv and on the returned fitness vector. A successful call of this method will increase the internal fitness
342 * evaluation counter (see problem::get_fevals()).
343 *
344 * @param dv the decision vector.
345 *
346 * @return the fitness of \p dv.
347 *
348 * @throws std::invalid_argument if either
349 * - the length of \p dv differs from the value returned by get_nx(), or
350 * - the length of the returned fitness vector differs from the the value returned by get_nf().
351 * @throws unspecified any exception thrown by the <tt>%fitness()</tt> method of the UDP.
352 */
fitness(const vector_double & dv) const353 vector_double problem::fitness(const vector_double &dv) const
354 {
355 // NOTE: it is important that we can call this method on the same object from multiple threads,
356 // for parallel initialisation in populations/archis. Such thread safety must be maintained
357 // if we change the implementation of this method.
358
359 // 1 - checks the decision vector
360 // NOTE: the check uses UDP properties cached on construction. This is const and thread-safe.
361 detail::prob_check_dv(*this, dv.data(), dv.size());
362
363 // 2 - computes the fitness
364 // NOTE: the thread safety here depends on the thread safety of the UDP. We make sure in the
365 // parallel init methods that we never invoke this method concurrently if the UDP is not
366 // sufficiently thread-safe.
367 vector_double retval(ptr()->fitness(dv));
368
369 // 3 - checks the fitness vector
370 // NOTE: as above, we are just making sure the fitness length is consistent with the fitness
371 // length stored in the problem. This is const and thread-safe.
372 detail::prob_check_fv(*this, retval.data(), retval.size());
373
374 // 4 - increments fitness evaluation counter
375 // NOTE: this is an atomic variable, thread-safe.
376 increment_fevals(1);
377
378 return retval;
379 }
380
381 /// Batch fitness.
382 /**
383 * This method implements the evaluation of multiple decision vectors in batch mode
384 * by invoking the <tt>%batch_fitness()</tt> method of the UDP. The <tt>%batch_fitness()</tt>
385 * method of the UDP accepts in input a batch of decision vectors, \p dvs, stored contiguously:
386 * for a problem with dimension \f$ n \f$, the first decision vector in \p dvs occupies
387 * the index range \f$ \left[0, n\right) \f$, the second decision vector occupies the range
388 * \f$ \left[n, 2n\right) \f$, and so on. The return value is the batch of fitness vectors \p fvs
389 * resulting from computing the fitness of the input decision vectors.
390 * \p fvs is also stored contiguously: for a problem with fitness dimension \f$ f \f$, the first fitness
391 * vector will occupy the index range \f$ \left[0, f\right) \f$, the second fitness vector
392 * will occupy the range \f$ \left[f, 2f\right) \f$, and so on.
393 *
394 * \verbatim embed:rst:leading-asterisk
395 * If the UDP satisfies :cpp:class:`pagmo::has_batch_fitness`, this method will forward ``dvs``
396 * to the ``batch_fitness()`` method of the UDP after sanity checks. The output of the ``batch_fitness()``
397 * method of the UDP will also be checked before being returned. If the UDP does not satisfy
398 * :cpp:class:`pagmo::has_batch_fitness`, an error will be raised.
399 * \endverbatim
400 *
401 * A successful call of this method will increase the internal fitness evaluation counter (see
402 * problem::get_fevals()).
403 *
404 * @param dvs the input batch of decision vectors.
405 *
406 * @return the fitnesses of the decision vectors in \p dvs.
407 *
408 * @throws std::invalid_argument if either \p dvs or the return value are incompatible
409 * with the properties of this problem.
410 * @throws not_implemented_error if the UDP does not have a <tt>%batch_fitness()</tt> method.
411 * @throws unspecified any exception thrown by the <tt>%batch_fitness()</tt> method of the UDP.
412 */
batch_fitness(const vector_double & dvs) const413 vector_double problem::batch_fitness(const vector_double &dvs) const
414 {
415 // Check the input dvs.
416 detail::bfe_check_input_dvs(*this, dvs);
417
418 // Invoke the batch fitness function of the UDP, and
419 // increase the fevals counter as well.
420 auto retval = detail::prob_invoke_mem_batch_fitness(*this, dvs, true);
421
422 // Check the produced vector of fitnesses.
423 detail::bfe_check_output_fvs(*this, dvs, retval);
424
425 return retval;
426 }
427
428 /// Gradient.
429 /**
430 * This method will compute the gradient of the input decision vector \p dv by invoking
431 * the <tt>%gradient()</tt> method of the UDP. The <tt>%gradient()</tt> method of the UDP must return
432 * a sparse representation of the gradient: the \f$ k\f$-th term of the gradient vector
433 * is expected to contain \f$ \frac{\partial f_i}{\partial x_j}\f$, where the pair \f$(i,j)\f$
434 * is the \f$k\f$-th element of the sparsity pattern (collection of index pairs), as returned by
435 * problem::gradient_sparsity().
436 *
437 * If the UDP satisfies pagmo::has_gradient, this method will forward \p dv to the <tt>%gradient()</tt>
438 * method of the UDP after sanity checks. The output of the <tt>%gradient()</tt>
439 * method of the UDP will also be checked before being returned. If the UDP does not satisfy
440 * pagmo::has_gradient, an error will be raised.
441 *
442 * A successful call of this method will increase the internal gradient evaluation counter (see
443 * problem::get_gevals()).
444 *
445 * @param dv the decision vector whose gradient will be computed.
446 *
447 * @return the gradient of \p dv.
448 *
449 * @throws std::invalid_argument if either:
450 * - the length of \p dv differs from the value returned by get_nx(), or
451 * - the returned gradient vector does not have the same size as the vector returned by
452 * problem::gradient_sparsity().
453 * @throws not_implemented_error if the UDP does not satisfy pagmo::has_gradient.
454 * @throws unspecified any exception thrown by the <tt>%gradient()</tt> method of the UDP.
455 */
gradient(const vector_double & dv) const456 vector_double problem::gradient(const vector_double &dv) const
457 {
458 // 1 - checks the decision vector
459 detail::prob_check_dv(*this, dv.data(), dv.size());
460 // 2 - compute the gradients
461 vector_double retval(ptr()->gradient(dv));
462 // 3 - checks the gradient vector
463 check_gradient_vector(retval);
464 // 4 - increments gradient evaluation counter
465 m_gevals.fetch_add(1u, std::memory_order_relaxed);
466 return retval;
467 }
468
469 /// Gradient sparsity pattern.
470 /**
471 * This method will return the gradient sparsity pattern of the problem. The gradient sparsity pattern is a
472 * lexicographically sorted collection of the indices \f$(i,j)\f$ of the non-zero elements of
473 * \f$ g_{ij} = \frac{\partial f_i}{\partial x_j}\f$.
474 *
475 * If problem::has_gradient_sparsity() returns \p true,
476 * then the <tt>%gradient_sparsity()</tt> method of the UDP will be invoked, and its result returned (after sanity
477 * checks). Otherwise, a a dense pattern is assumed and the returned vector will be
478 * \f$((0,0),(0,1), ... (0,n_x-1), ...(n_f-1,n_x-1))\f$.
479 *
480 * @return the gradient sparsity pattern.
481 *
482 * @throws std::invalid_argument if the sparsity pattern returned by the UDP is invalid (specifically, if
483 * it is not strictly sorted lexicographically, or if the indices in the pattern are incompatible with the
484 * properties of the problem, or if the size of the returned pattern is different from the size recorded upon
485 * construction).
486 * @throws unspecified memory errors in standard containers.
487 */
gradient_sparsity() const488 sparsity_pattern problem::gradient_sparsity() const
489 {
490 if (has_gradient_sparsity()) {
491 auto retval = ptr()->gradient_sparsity();
492 check_gradient_sparsity(retval);
493 // Check the size is consistent with the stored size.
494 // NOTE: we need to do this check here, and not in check_gradient_sparsity(),
495 // because check_gradient_sparsity() is sometimes called when m_gs_dim has not been
496 // initialised yet (e.g., in the ctor).
497 if (retval.size() != m_gs_dim) {
498 pagmo_throw(std::invalid_argument,
499 "Invalid gradient sparsity pattern: the returned sparsity pattern has a size of "
500 + std::to_string(retval.size())
501 + ", while the sparsity pattern size stored upon problem construction is "
502 + std::to_string(m_gs_dim));
503 }
504 return retval;
505 }
506 return detail::dense_gradient(get_nf(), get_nx());
507 }
508
509 /// Hessians.
510 /**
511 * This method will compute the hessians of the input decision vector \p dv by invoking
512 * the <tt>%hessians()</tt> method of the UDP. The <tt>%hessians()</tt> method of the UDP must return
513 * a sparse representation of the hessians: the element \f$ l\f$ of the returned vector contains
514 * \f$ h^l_{ij} = \frac{\partial f^2_l}{\partial x_i\partial x_j}\f$
515 * in the order specified by the \f$ l\f$-th element of the
516 * hessians sparsity pattern (a vector of index pairs \f$(i,j)\f$)
517 * as returned by problem::hessians_sparsity(). Since
518 * the hessians are symmetric, their sparse representation contains only lower triangular elements.
519 *
520 * If the UDP satisfies pagmo::has_hessians, this method will forward \p dv to the <tt>%hessians()</tt>
521 * method of the UDP after sanity checks. The output of the <tt>%hessians()</tt>
522 * method of the UDP will also be checked before being returned. If the UDP does not satisfy
523 * pagmo::has_hessians, an error will be raised.
524 *
525 * A successful call of this method will increase the internal hessians evaluation counter (see
526 * problem::get_hevals()).
527 *
528 * @param dv the decision vector whose hessians will be computed.
529 *
530 * @return the hessians of \p dv.
531 *
532 * @throws std::invalid_argument if either:
533 * - the length of \p dv differs from the output of get_nx(), or
534 * - the length of the returned hessians does not match the corresponding hessians sparsity pattern dimensions, or
535 * - the size of the return value is not equal to the fitness dimension.
536 * @throws not_implemented_error if the UDP does not satisfy pagmo::has_hessians.
537 * @throws unspecified any exception thrown by the <tt>%hessians()</tt> method of the UDP.
538 */
hessians(const vector_double & dv) const539 std::vector<vector_double> problem::hessians(const vector_double &dv) const
540 {
541 // 1 - checks the decision vector
542 detail::prob_check_dv(*this, dv.data(), dv.size());
543 // 2 - computes the hessians
544 auto retval(ptr()->hessians(dv));
545 // 3 - checks the hessians
546 check_hessians_vector(retval);
547 // 4 - increments hessians evaluation counter
548 m_hevals.fetch_add(1u, std::memory_order_relaxed);
549 return retval;
550 }
551
552 /// Hessians sparsity pattern.
553 /**
554 * This method will return the hessians sparsity pattern of the problem. Each component \f$ l\f$ of the hessians
555 * sparsity pattern is a lexicographically sorted collection of the indices \f$(i,j)\f$ of the non-zero elements of
556 * \f$h^l_{ij} = \frac{\partial f^l}{\partial x_i\partial x_j}\f$. Since the Hessian matrix
557 * is symmetric, only lower triangular elements are allowed.
558 *
559 * If problem::has_hessians_sparsity() returns \p true,
560 * then the <tt>%hessians_sparsity()</tt> method of the UDP will be invoked, and its result returned (after sanity
561 * checks). Otherwise, a dense pattern is assumed and \f$n_f\f$ sparsity patterns
562 * containing \f$((0,0),(1,0), (1,1), (2,0) ... (n_x-1,n_x-1))\f$ will be returned.
563 *
564 * @return the hessians sparsity pattern.
565 *
566 * @throws std::invalid_argument if a sparsity pattern returned by the UDP is invalid (specifically, if
567 * if it is not strictly sorted lexicographically, if the returned indices do not
568 * correspond to a lower triangular representation of a symmetric matrix, or if the size of the pattern differs
569 * from the size recorded upon construction).
570 */
hessians_sparsity() const571 std::vector<sparsity_pattern> problem::hessians_sparsity() const
572 {
573 if (m_has_hessians_sparsity) {
574 auto retval = ptr()->hessians_sparsity();
575 check_hessians_sparsity(retval);
576 // Check the sizes are consistent with the stored sizes.
577 // NOTE: we need to do this check here, and not in check_hessians_sparsity(),
578 // because check_hessians_sparsity() is sometimes called when m_hs_dim has not been
579 // initialised yet (e.g., in the ctor).
580 // NOTE: in check_hessians_sparsity() we have already checked the size of retval. It has
581 // to be the same as the fitness dimension. The same check is run when m_hs_dim is originally
582 // created, hence they must be equal.
583 assert(retval.size() == m_hs_dim.size());
584 auto r_it = retval.begin();
585 for (const auto &dim : m_hs_dim) {
586 if (r_it->size() != dim) {
587 pagmo_throw(std::invalid_argument,
588 "Invalid hessian sparsity pattern: the returned sparsity pattern has a size of "
589 + std::to_string(r_it->size())
590 + ", while the sparsity pattern size stored upon problem construction is "
591 + std::to_string(dim));
592 }
593 ++r_it;
594 }
595 return retval;
596 }
597 return detail::dense_hessians(get_nf(), get_nx());
598 }
599
600 /// Box-bounds.
601 /**
602 * @return \f$ (\mathbf{lb}, \mathbf{ub}) \f$, the box-bounds, as returned by
603 * the <tt>%get_bounds()</tt> method of the UDP. Infinities in the bounds are allowed.
604 *
605 * @throws unspecified any exception thrown by memory errors in standard containers.
606 */
get_bounds() const607 std::pair<vector_double, vector_double> problem::get_bounds() const
608 {
609 return std::make_pair(m_lb, m_ub);
610 }
611
612 /// Set the constraint tolerance (from a vector of doubles).
613 /**
614 * @param c_tol a vector containing the tolerances to use when
615 * checking for constraint feasibility.
616 *
617 * @throws std::invalid_argument if the size of \p c_tol differs from the number of constraints, or if
618 * any of its elements is negative or NaN.
619 */
set_c_tol(const vector_double & c_tol)620 void problem::set_c_tol(const vector_double &c_tol)
621 {
622 if (c_tol.size() != this->get_nc()) {
623 pagmo_throw(std::invalid_argument, "The tolerance vector size should be: " + std::to_string(this->get_nc())
624 + ", while a size of: " + std::to_string(c_tol.size())
625 + " was detected.");
626 }
627 for (decltype(c_tol.size()) i = 0; i < c_tol.size(); ++i) {
628 if (std::isnan(c_tol[i])) {
629 pagmo_throw(std::invalid_argument,
630 "The tolerance vector has a NaN value at the index " + std::to_string(i));
631 }
632 if (c_tol[i] < 0.) {
633 pagmo_throw(std::invalid_argument,
634 "The tolerance vector has a negative value at the index " + std::to_string(i));
635 }
636 }
637 m_c_tol = c_tol;
638 }
639
640 /// Set the constraint tolerance (from a single double value).
641 /**
642 * @param c_tol the tolerance to use when checking for all constraint feasibilities.
643 *
644 * @throws std::invalid_argument if \p c_tol is negative or NaN.
645 */
set_c_tol(double c_tol)646 void problem::set_c_tol(double c_tol)
647 {
648 if (std::isnan(c_tol)) {
649 pagmo_throw(std::invalid_argument, "The tolerance cannot be set to be NaN.");
650 }
651 if (c_tol < 0.) {
652 pagmo_throw(std::invalid_argument, "The tolerance cannot be negative.");
653 }
654 m_c_tol = vector_double(this->get_nc(), c_tol);
655 }
656
657 /// Set the seed for the stochastic variables.
658 /**
659 * Sets the seed to be used in the fitness function to instantiate
660 * all stochastic variables. If the UDP satisfies pagmo::has_set_seed, then
661 * its <tt>%set_seed()</tt> method will be invoked. Otherwise, an error will be raised.
662 *
663 * @param seed seed.
664 *
665 * @throws not_implemented_error if the UDP does not satisfy pagmo::has_set_seed.
666 * @throws unspecified any exception thrown by the <tt>%set_seed()</tt> method of the UDP.
667 */
set_seed(unsigned seed)668 void problem::set_seed(unsigned seed)
669 {
670 ptr()->set_seed(seed);
671 }
672
673 /// Feasibility of a decision vector.
674 /**
675 * This method will check the feasibility of the fitness corresponding to
676 * a decision vector \p x against
677 * the tolerances returned by problem::get_c_tol().
678 *
679 * \verbatim embed:rst:leading-asterisk
680 * .. note::
681 *
682 * One call of this method will cause one call to the fitness function.
683 *
684 * \endverbatim
685 *
686 * @param x a decision vector.
687 *
688 * @return \p true if the decision vector results in a feasible fitness, \p false otherwise.
689 *
690 * @throws unspecified any exception thrown by problem::feasibility_f() or problem::fitness().
691 */
feasibility_x(const vector_double & x) const692 bool problem::feasibility_x(const vector_double &x) const
693 {
694 // Wrong dimensions of x will trigger exceptions in the called functions
695 return feasibility_f(fitness(x));
696 }
697
698 /// Feasibility of a fitness vector.
699 /**
700 * This method will check the feasibility of a fitness vector \p f against
701 * the tolerances returned by problem::get_c_tol().
702 *
703 * @param f a fitness vector.
704 *
705 * @return \p true if the fitness vector is feasible, \p false otherwise.
706 *
707 * @throws std::invalid_argument if the size of \p f is not the same as the output of problem::get_nf().
708 */
feasibility_f(const vector_double & f) const709 bool problem::feasibility_f(const vector_double &f) const
710 {
711 if (f.size() != get_nf()) {
712 pagmo_throw(std::invalid_argument,
713 "The fitness passed as argument has dimension of: " + std::to_string(f.size())
714 + ", while the problem defines a fitness size of: " + std::to_string(get_nf()));
715 }
716 auto feas_eq
717 = detail::test_eq_constraints(f.data() + get_nobj(), f.data() + get_nobj() + get_nec(), get_c_tol().data());
718 auto feas_ineq = detail::test_ineq_constraints(f.data() + get_nobj() + get_nec(), f.data() + f.size(),
719 get_c_tol().data() + get_nec());
720 return feas_eq.first + feas_ineq.first == get_nc();
721 }
722
723 /// Problem's extra info.
724 /**
725 * If the UDP satisfies pagmo::has_extra_info, then this method will return the output of its
726 * <tt>%get_extra_info()</tt> method. Otherwise, an empty string will be returned.
727 *
728 * @return extra info about the UDP.
729 *
730 * @throws unspecified any exception thrown by the <tt>%get_extra_info()</tt> method of the UDP.
731 */
get_extra_info() const732 std::string problem::get_extra_info() const
733 {
734 return ptr()->get_extra_info();
735 }
736
737 /// Check if the problem is in a valid state.
738 /**
739 * @return ``false`` if ``this`` was moved from, ``true`` otherwise.
740 */
is_valid() const741 bool problem::is_valid() const
742 {
743 return static_cast<bool>(m_ptr);
744 }
745
746 /// Get the type of the UDP.
747 /**
748 * \verbatim embed:rst:leading-asterisk
749 * .. versionadded:: 2.15
750 *
751 * This function will return the type
752 * of the UDP stored within this problem
753 * instance.
754 * \endverbatim
755 *
756 * @return the type of the UDP.
757 */
get_type_index() const758 std::type_index problem::get_type_index() const
759 {
760 return ptr()->get_type_index();
761 }
762
get_ptr() const763 const void *problem::get_ptr() const
764 {
765 return ptr()->get_ptr();
766 }
767
get_ptr()768 void *problem::get_ptr()
769 {
770 return ptr()->get_ptr();
771 }
772
773 /// Streaming operator
774 /**
775 * This function will stream to \p os a human-readable representation of the input
776 * problem \p p.
777 *
778 * @param os input <tt>std::ostream</tt>.
779 * @param p pagmo::problem object to be streamed.
780 *
781 * @return a reference to \p os.
782 *
783 * @throws unspecified any exception thrown by querying various problem properties and streaming them into \p os.
784 */
operator <<(std::ostream & os,const problem & p)785 std::ostream &operator<<(std::ostream &os, const problem &p)
786 {
787 os << "Problem name: " << p.get_name();
788 if (p.is_stochastic()) {
789 stream(os, " [stochastic]");
790 }
791 os << "\n\tC++ class name: " << detail::demangle_from_typeid(p.get_type_index().name()) << '\n';
792 os << "\n\tGlobal dimension:\t\t\t" << p.get_nx() << '\n';
793 os << "\tInteger dimension:\t\t\t" << p.get_nix() << '\n';
794 os << "\tFitness dimension:\t\t\t" << p.get_nf() << '\n';
795 os << "\tNumber of objectives:\t\t\t" << p.get_nobj() << '\n';
796 os << "\tEquality constraints dimension:\t\t" << p.get_nec() << '\n';
797 os << "\tInequality constraints dimension:\t" << p.get_nic() << '\n';
798 if (p.get_nec() + p.get_nic() > 0u) {
799 stream(os, "\tTolerances on constraints: ", p.get_c_tol(), '\n');
800 }
801 os << "\tLower bounds: ";
802 stream(os, p.get_bounds().first, '\n');
803 os << "\tUpper bounds: ";
804 stream(os, p.get_bounds().second, '\n');
805 stream(os, "\tHas batch fitness evaluation: ", p.has_batch_fitness(), '\n');
806 stream(os, "\n\tHas gradient: ", p.has_gradient(), '\n');
807 stream(os, "\tUser implemented gradient sparsity: ", p.has_gradient_sparsity(), '\n');
808 if (p.has_gradient()) {
809 stream(os, "\tExpected gradients: ", p.m_gs_dim, '\n');
810 }
811 stream(os, "\tHas hessians: ", p.has_hessians(), '\n');
812 stream(os, "\tUser implemented hessians sparsity: ", p.has_hessians_sparsity(), '\n');
813 if (p.has_hessians()) {
814 stream(os, "\tExpected hessian components: ", p.m_hs_dim, '\n');
815 }
816 stream(os, "\n\tFitness evaluations: ", p.get_fevals(), '\n');
817 if (p.has_gradient()) {
818 stream(os, "\tGradient evaluations: ", p.get_gevals(), '\n');
819 }
820 if (p.has_hessians()) {
821 stream(os, "\tHessians evaluations: ", p.get_hevals(), '\n');
822 }
823 stream(os, "\n\tThread safety: ", p.get_thread_safety(), '\n');
824
825 const auto extra_str = p.get_extra_info();
826 if (!extra_str.empty()) {
827 stream(os, "\nExtra info:\n", extra_str);
828 }
829 return os;
830 }
831
check_gradient_sparsity(const sparsity_pattern & gs) const832 void problem::check_gradient_sparsity(const sparsity_pattern &gs) const
833 {
834 // Cache a couple of quantities.
835 const auto nx = get_nx();
836 const auto nf = get_nf();
837
838 // Check the pattern.
839 for (auto it = gs.begin(); it != gs.end(); ++it) {
840 if ((it->first >= nf) || (it->second >= nx)) {
841 pagmo_throw(std::invalid_argument, "Invalid pair detected in the gradient sparsity pattern: ("
842 + std::to_string(it->first) + ", " + std::to_string(it->second)
843 + ")\nFitness dimension is: " + std::to_string(nf)
844 + "\nDecision vector dimension is: " + std::to_string(nx));
845 }
846 if (it == gs.begin()) {
847 continue;
848 }
849 if (!(*(it - 1) < *it)) {
850 pagmo_throw(std::invalid_argument,
851 "The gradient sparsity pattern is not strictly sorted in ascending order: the indices pair ("
852 + std::to_string((it - 1)->first) + ", " + std::to_string((it - 1)->second)
853 + ") is greater than or equal to the successive indices pair (" + std::to_string(it->first)
854 + ", " + std::to_string(it->second) + ")");
855 }
856 }
857 }
858
check_hessians_sparsity(const std::vector<sparsity_pattern> & hs) const859 void problem::check_hessians_sparsity(const std::vector<sparsity_pattern> &hs) const
860 {
861 // 1 - We check that a hessian sparsity is provided for each component
862 // of the fitness
863 const auto nf = get_nf();
864 if (hs.size() != nf) {
865 pagmo_throw(std::invalid_argument, "Invalid dimension of the hessians_sparsity: " + std::to_string(hs.size())
866 + ", expected: " + std::to_string(nf));
867 }
868 // 2 - We check that all hessian sparsity patterns have
869 // valid indices.
870 for (const auto &one_hs : hs) {
871 check_hessian_sparsity(one_hs);
872 }
873 }
874
check_hessian_sparsity(const sparsity_pattern & hs) const875 void problem::check_hessian_sparsity(const sparsity_pattern &hs) const
876 {
877 const auto nx = get_nx();
878 // We check that the hessian sparsity pattern has
879 // valid indices. Assuming a lower triangular representation of
880 // a symmetric matrix. Example, for a 4x4 dense symmetric
881 // [(0,0), (1,0), (1,1), (2,0), (2,1), (2,2), (3,0), (3,1), (3,2), (3,3)]
882 for (auto it = hs.begin(); it != hs.end(); ++it) {
883 if ((it->first >= nx) || (it->second > it->first)) {
884 pagmo_throw(std::invalid_argument, "Invalid pair detected in the hessians sparsity pattern: ("
885 + std::to_string(it->first) + ", " + std::to_string(it->second)
886 + ")\nDecision vector dimension is: " + std::to_string(nx)
887 + "\nNOTE: hessian is a symmetric matrix and PaGMO represents "
888 "it as lower triangular: i.e (i,j) is not valid if j>i");
889 }
890 if (it == hs.begin()) {
891 continue;
892 }
893 if (!(*(it - 1) < *it)) {
894 pagmo_throw(std::invalid_argument,
895 "The hessian sparsity pattern is not strictly sorted in ascending order: the indices pair ("
896 + std::to_string((it - 1)->first) + ", " + std::to_string((it - 1)->second)
897 + ") is greater than or equal to the successive indices pair (" + std::to_string(it->first)
898 + ", " + std::to_string(it->second) + ")");
899 }
900 }
901 }
902
check_gradient_vector(const vector_double & gr) const903 void problem::check_gradient_vector(const vector_double &gr) const
904 {
905 // Checks that the gradient vector returned has the same dimensions of the sparsity_pattern
906 if (gr.size() != m_gs_dim) {
907 pagmo_throw(std::invalid_argument,
908 "Gradients returned: " + std::to_string(gr.size()) + ", should be " + std::to_string(m_gs_dim));
909 }
910 }
911
check_hessians_vector(const std::vector<vector_double> & hs) const912 void problem::check_hessians_vector(const std::vector<vector_double> &hs) const
913 {
914 // 1 - Check that hs has size get_nf()
915 if (hs.size() != get_nf()) {
916 pagmo_throw(std::invalid_argument, "The hessians vector has a size of " + std::to_string(hs.size())
917 + ", but the fitness dimension of the problem is "
918 + std::to_string(get_nf()) + ". The two values must be equal");
919 }
920 // 2 - Check that the hessians returned have the same dimensions of the
921 // corresponding sparsity patterns
922 // NOTE: the dimension of m_hs_dim is guaranteed to be get_nf() on construction.
923 for (decltype(hs.size()) i = 0u; i < hs.size(); ++i) {
924 if (hs[i].size() != m_hs_dim[i]) {
925 pagmo_throw(std::invalid_argument, "On the hessian no. " + std::to_string(i)
926 + ": Components returned: " + std::to_string(hs[i].size())
927 + ", should be " + std::to_string(m_hs_dim[i]));
928 }
929 }
930 }
931
932 namespace detail
933 {
934
935 // Check that the decision vector starting at dv and with
936 // size s is compatible with the input problem p.
prob_check_dv(const problem & p,const double * dv,vector_double::size_type s)937 void prob_check_dv(const problem &p, const double *dv, vector_double::size_type s)
938 {
939 (void)dv;
940 // 1 - check decision vector for length consistency
941 if (s != p.get_nx()) {
942 pagmo_throw(std::invalid_argument, "A decision vector is incompatible with a problem of type '" + p.get_name()
943 + "': the number of dimensions of the problem is "
944 + std::to_string(p.get_nx())
945 + ", while the decision vector has a size of " + std::to_string(s)
946 + " (the two values should be equal)");
947 }
948 // 2 - Here is where one could check if the decision vector
949 // is in the bounds. At the moment not implemented
950 }
951
952 // Check that the fitness vector starting at fv and with size s
953 // is compatible with the input problem p.
prob_check_fv(const problem & p,const double * fv,vector_double::size_type s)954 void prob_check_fv(const problem &p, const double *fv, vector_double::size_type s)
955 {
956 (void)fv;
957 // Checks dimension of returned fitness
958 if (s != p.get_nf()) {
959 pagmo_throw(std::invalid_argument, "A fitness vector is incompatible with a problem of type '" + p.get_name()
960 + "': the dimension of the fitness of the problem is "
961 + std::to_string(p.get_nf())
962 + ", while the fitness vector has a size of " + std::to_string(s)
963 + " (the two values should be equal)");
964 }
965 }
966
967 // Small helper for the invocation of the UDP's batch_fitness() *without* checks.
968 // This is useful for avoiding doing double checks on the input/output values
969 // of batch_fitness() when we are sure that the checks have been performed elsewhere already.
970 // This helper will also take care of increasing the fevals counter in the
971 // input problem, if requested.
prob_invoke_mem_batch_fitness(const problem & p,const vector_double & dvs,bool incr_fevals)972 vector_double prob_invoke_mem_batch_fitness(const problem &p, const vector_double &dvs, bool incr_fevals)
973 {
974 // Invoke the batch fitness from the UDP.
975 auto retval(p.ptr()->batch_fitness(dvs));
976
977 // Increment the number of fitness evaluations, if
978 // requested.
979 if (incr_fevals) {
980 p.increment_fevals(boost::numeric_cast<unsigned long long>(dvs.size() / p.get_nx()));
981 }
982
983 return retval;
984 }
985
986 } // namespace detail
987
988 } // namespace pagmo
989