Self-adaptive constraints handling#

class cstrs_self_adaptive#

Self-adaptive constraints handling.

This meta-algorithm implements a constraint handling technique that allows the use of any user-defined algorithm (UDA) able to deal with single-objective unconstrained problems, on single-objective constrained problems. The technique self-adapts its parameters during each successive call to the inner UDA basing its decisions on the entire underlying population. The resulting approach is an alternative to using the meta-problem pagmo::unconstrain to transform the constrained fitness into an unconstrained fitness.

The self-adaptive constraints handling meta-algorithm is largely based on the ideas of Farmani and Wright but it extends their use to any-algorithm, in particular to non generational population based evolutionary approaches where a steady-state reinsertion is used (i.e., as soon as an individual is found fit it is immediately reinserted into the pop and will influence the next offspring genetic material).

Each decision vector is assigned an infeasibility measure \(\iota\) which accounts for the normalized violation of all the constraints (discounted by the constraints tolerance as returned by pagmo::problem::get_c_tol()). The normalization factor used \(c_{j_{max}}\) is the maximum violation of the \(j-th\) constraint.

As in the original paper, three individuals in the evolving population are then used to penalize the single objective.

\[\begin{split} \begin{array}{rl} \check X & \mbox{: the best decision vector} \\ \hat X & \mbox{: the worst decision vector} \\ \breve X & \mbox{: the decision vector with the highest objective} \end{array} \end{split}\]

The best and worst decision vectors are defined accounting for their infeasibilities and for the value of the objective function. Using the above definitions the overall pseudo code can be summarized as follows:

> Select a pagmo::population (related to a single-objective constrained problem)
> Select a UDA (able to solve single-objective unconstrained problems)
> while i < iter
> > Compute the normalization factors (will depend on the current population)
> > Compute the best, worst, highest (will depend on the current population)
> > Evolve the population using the UDA and a penalized objective
> > Reinsert the best decision vector from the previous evolution

pagmo::cstrs_self_adaptive is a user-defined algorithm (UDA) that can be used to construct pagmo::algorithm objects.

See also

Farmani, Raziyeh, and Jonathan A. Wright. “Self-adaptive fitness formulation for constrained optimization.” IEEE Transactions on Evolutionary Computation 7.5 (2003): 445-455.

Note

Self-adaptive constraints handling implements an internal cache to avoid the re-evaluation of the fitness for decision vectors already evaluated. This makes the final counter of function evaluations somewhat unpredictable. The number of function evaluation will be bounded to iters times the fevals made by one call to the inner UDA. The internal cache is reset at each iteration, but its size will grow unlimited during each call to the inner UDA evolve method.

Note

Several modification were made to the original Farmani and Wright ideas to allow their approach to work on corner cases and with any UDAs. Most notably, a violation to the \(j\)-th constraint is ignored if all the decision vectors in the population satisfy that particular constraint (i.e. if \(c_{j_{max}} = 0\)).

Note

The performances of pagmo::cstrs_self_adaptive are highly dependent on the particular inner UDA employed and in particular to its parameters (generations / iterations).

Public Types

typedef std::tuple<unsigned, unsigned long long, double, double, vector_double::size_type, double, vector_double::size_type> log_line_type#

Single entry of the log (iter, fevals, best_f, infeas, n. constraints violated, violation norm).

typedef std::vector<log_line_type> log_type#

The log.

Public Functions

cstrs_self_adaptive(unsigned iters = 1u)#

Default constructor.

Parameters

iters – Number of iterations (calls to the inner UDA). After each iteration the penalty is adapted The default constructor will initialize the algorithm with the following parameters:

  • inner algorithm: pagmo::de{1u};

  • seed: random.

template<typename T, ctor_enabler<T> = 0>
inline explicit cstrs_self_adaptive(unsigned iters, T &&a, unsigned seed = pagmo::random_device::next())#

Constructor.

Parameters

  • iters – Number of iterations (calls to the inner algorithm). After each iteration the penalty is adapted

  • a – a pagmo::algorithm (or UDA) that will be used to construct the inner algorithm.

  • seed – seed used by the internal random number generator (default is random).

Throws

unspecified – any exception thrown by the constructor of pagmo::algorithm.

population evolve(population) const#

Evolve method.

This method will call evolve on the inner algorithm iters times updating the penalty to be applied to the objective after each call

Parameters

pop – population to be evolved.

Throws

std::invalid_argument – if the problem is multi-objective or stochastic, or unconstrained and if the population does not contain at least 3 individuals.

Returns

evolved population.

void set_seed(unsigned)#

Set the seed.

Parameters

seed – the seed controlling the algorithm’s stochastic behaviour.

inline unsigned get_seed() const#

Get the seed.

Returns

the seed controlling the algorithm’s stochastic behaviour.

inline void set_verbosity(unsigned level)#

Set the algorithm verbosity.

This method will sets the verbosity level of the screen output and of the log returned by get_log(). level can be:

  • 0: no verbosity,

  • >0: will print and log one line each level call to the inner algorithm.

Example (verbosity 10): 

Iter:        Fevals:          Best: Infeasibility:      Violated:    Viol. Norm:   N. Feasible:
    1              0       -69.2141       0.235562              6        117.743              0 i
   11            200       -69.2141       0.248216              6        117.743              0 i
   21            400       -29.4754      0.0711599              5          44.39              0 i
   31            600       -30.0791      0.0878253              4        44.3803              0 i
  ...            ...       ........      .........              .        .......              . .
  211           4190       -7.68336    0.000341894              1       0.273829              0 i
  221           4390       -7.89941     0.00031154              1       0.273829              0 i
  231           4590       -8.38299    0.000168309              1       0.147935              0 i
  241           4790       -8.38299    0.000181461              1       0.147935              0 i
  251           4989       -8.71021    0.000191197              1       0.100357              0 i
  261           5189       -8.71021    0.000165734              1       0.100357              0 i
  271           5389       -10.7421              0              0              0              3
  281           5585       -10.7421              0              0              0              3
  291           5784       -11.4868              0              0              0              4
Iter is the iteration number, Fevals is the number of fitness evaluations, Best is the objective function of the best fitness currently in the population, Infeasibility is the normalized infeasibility measure, Violated is the number of constraints currently violated by the best solution, Viol. Norm is the norm of the violation (discounted already by the constraints tolerance) and N. Feasible is the number of feasible individuals in the current iteration. The small i appearing at the end of the line stands for “infeasible” and will disappear only once Violated is 0.

Parameters

level – verbosity level.

inline unsigned get_verbosity() const#

Get the verbosity level.

Returns

the verbosity level.

inline const log_type &get_log() const#

Get log.

A log containing relevant quantities monitoring the last call to cstrs_self_adaptive::evolve(). Each element of the returned std::vector is a cstrs_self_adaptive::log_line_type containing: Iter, Fevals, Best, Infeasibility, Violated, Viol. Norm, N. Feasible as described in cstrs_self_adaptive::set_verbosity().

Returns

an std::vector of cstrs_self_adaptive::log_line_type containing the logged values Iters, Fevals, Best, Infeasibility, Violated and Viol. Norm and N. Feasible.

inline std::string get_name() const#

Algorithm name.

Returns

a string containing the algorithm name.

std::string get_extra_info() const#

Extra info.

Returns

a string containing extra info on the algorithm.

thread_safety get_thread_safety() const#

Algorithm’s thread safety level.

The thread safety of this meta-algorithm is the minimum between the thread safety of the internal pagmo::algorithm and the basic thread safety level. I.e., this algorithm never provides more than the basic thread safety level.

Returns

the thread safety level of this algorithm.

inline const algorithm &get_inner_algorithm() const#

Getter for the inner algorithm.

Returns a const reference to the inner pagmo::algorithm.

Returns

a const reference to the inner pagmo::algorithm.

inline algorithm &get_inner_algorithm()#

Getter for the inner problem.

Returns a reference to the inner pagmo::algorithm.

Note

The ability to extract a non const reference is provided only in order to allow to call non-const methods on the internal pagmo::algorithm instance. Assigning a new pagmo::algorithm via this reference is undefined behaviour.

Returns

a reference to the inner pagmo::algorithm.