Multi-objective optimization utilities#

A number of utilities to compute quantities that are of relevance to the determination of non dominated fronts, Pareto dominance criteria and more in general, to multi-objective optimization tasks.

bool pagmo::pareto_dominance(const vector_double &obj1, const vector_double &obj2)#

Pareto-dominance.

Return true if obj1 Pareto dominates obj2, false otherwise. Minimization is assumed.

Each pair of corresponding elements in obj1 and obj2 is compared: if all elements in obj1 are less or equal to the corresponding element in obj2, but at least one is different, true will be returned. Otherwise, false will be returned.

Parameters

  • obj1 – first vector of objectives.

  • obj2 – second vector of objectives.

Throws

std::invalid_argument – if the dimensions of the two objectives are different

Returns

true if obj1 is dominating obj2, false otherwise.

std::vector<pop_size_t> pagmo::non_dominated_front_2d(const std::vector<vector_double> &input_objs)#

Non dominated front 2D (Kung’s algorithm)

Finds the non dominated front of a set of two dimensional objectives. Complexity is O(N logN) and is thus lower than the complexity of calling pagmo::fast_non_dominated_sorting

See: Jensen, Mikkel T. “Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms.” IEEE Transactions on Evolutionary Computation 7.5 (2003): 503-515.

Parameters

input_objs – an std::vector containing the points (i.e. vector of objectives)

Throws

std::invalid_argument – If the objective vectors are not all containing two-objectives

Returns

A std::vector containing the indexes of the points in the non-dominated front

vector_double pagmo::crowding_distance(const std::vector<vector_double> &non_dom_front)#

Crowding distance.

An implementation of the crowding distance. Complexity is \( O(MNlog(N))\) where \(M\) is the number of objectives and \(N\) is the number of individuals. The function assumes the input is a non-dominated front. Failure to this condition will result in undefined behaviour.

See: Deb, Kalyanmoy, et al. “A fast elitist non-dominated sorting genetic algorithm

for multi-objective optimization: NSGA-II.” Parallel problem solving from nature PPSN VI. Springer Berlin Heidelberg, 2000.

Parameters

non_dom_front – An std::vector<vector_double> containing a non dominated front. Example {{0,0},{-1,1},{2,-2}}

Throws

  • std::invalid_argument – If non_dom_front does not contain at least two points

  • std::invalid_argument – If points in do not all have at least two objectives

  • std::invalid_argument – If points in non_dom_front do not all have the same dimensionality

Returns

a vector_double containing the crowding distances. Example: {2, inf, inf}

fnds_return_type pagmo::fast_non_dominated_sorting(const std::vector<vector_double> &points)#

Fast non dominated sorting.

An implementation of the fast non dominated sorting algorithm. Complexity is \( O(MN^2)\) where \(M\) is the number of objectives and \(N\) is the number of individuals.

See: Deb, Kalyanmoy, et al. “A fast elitist non-dominated sorting genetic algorithm

for multi-objective optimization: NSGA-II.” Parallel problem solving from nature PPSN VI. Springer Berlin Heidelberg, 2000.

Parameters

points – An std::vector containing the objectives of different individuals. Example {{1,2,3},{-2,3,7},{-1,-2,-3},{0,0,0}}

Throws

std::invalid_argument – If the size of points is not at least 2

Returns

an std::tuple containing:

  • the non dominated fronts, an std::vector<std::vector<pop_size_t>> containing the non dominated fronts. Example {{1,2},{3},{0}}

  • the domination list, an std::vector<std::vector<pop_size_t>> containing the domination list, i.e. the indexes of all individuals dominated by the individual at position \(i\). Example {{},{},{0,3},{0}}

  • the domination count, an std::vector<pop_size_t> containing the number of individuals that dominate the individual at position \(i\). Example {2, 0, 0, 1}

  • the non domination rank, an std::vector<pop_size_t> containing the index of the non dominated front to which the individual at position \(i\) belongs. Example {2,0,0,1}

std::vector<pop_size_t> pagmo::sort_population_mo(const std::vector<vector_double> &input_f)#

Sorts a population in multi-objective optimization.

Sorts a population (intended here as an std::vector<vector_double> containing the objective vectors) with respect to the following strict ordering:

  • \(f_1 \prec f_2\) if the non domination ranks are such that \(i_1 < i_2\). In case \(i_1 = i_2\), then \(f_1 \prec f_2\) if the crowding distances are such that \(d_1 > d_2\).

Complexity is \( O(MN^2)\) where \(M\) is the number of objectives and \(N\) is the number of individuals.

This function will also work for single objective optimization, i.e. with 1 objective in which case, though, it is more efficient to sort using directly one of the following forms:

std::sort(input_f.begin(), input_f.end(), [] (auto a, auto b) {return a[0] < b[0];});

std::vector<pop_size_t> idx(input_f.size());
std::iota(idx.begin(), idx.end(), pop_size_t(0u));
std::sort(idx.begin(), idx.end(), [] (auto a, auto b) {return input_f[a][0] < input_f[b][0];});

Parameters

input_f – Input objectives vectors. Example {{0.25,0.25},{-1,1},{2,-2}};

Throws

unspecified – all exceptions thrown by pagmo::fast_non_dominated_sorting and pagmo::crowding_distance

Returns

an std::vector containing the indexes of the sorted objectives vectors. Example {1,2,0}

std::vector<pop_size_t> pagmo::select_best_N_mo(const std::vector<vector_double> &input_f, pop_size_t N)#

Selects the best N individuals in multi-objective optimization.

Selects the best N individuals out of a population, (intended here as an std::vector<vector_double> containing the objective vectors). The strict ordering used is the same as that defined in pagmo::sort_population_mo.

Complexity is \( O(MN^2)\) where \(M\) is the number of objectives and \(N\) is the number of individuals.

While the complexity is the same as that of pagmo::sort_population_mo, this function returns a permutation of:

auto ret = pagmo::sort_population_mo(input_f).resize(N);

but it is faster than the above code: it avoids to compute the crowding distance for all individuals and only computes it for the last non-dominated front that contains individuals included in the best N.

If N is zero, an empty vector will be returned.

Parameters

  • input_f – Input objectives vectors. Example {{0.25,0.25},{-1,1},{2,-2}};

  • N – Number of best individuals to return

Throws

unspecified – all exceptions thrown by pagmo::fast_non_dominated_sorting and pagmo::crowding_distance

Returns

an std::vector containing the indexes of the best N objective vectors. Example {2,1}

vector_double pagmo::ideal(const std::vector<vector_double> &points)#

Ideal point.

Computes the ideal point of an input population, (intended here as an std::vector<vector_double> containing the objective vectors).

Complexity is \( O(MN)\) where \(M\) is the number of objectives and \(N\) is the number of individuals.

Parameters

points – Input objectives vectors. Example {{-1,3,597},{1,2,3645},{2,9,789},{0,0,231},{6,-2,4576}};

Throws

std::invalid_argument – if the input objective vectors are not all of the same size

Returns

A vector_double containing the ideal point. Example: {-1,-2,231}

vector_double pagmo::nadir(const std::vector<vector_double> &points)#

Nadir point.

Computes the nadir point of an input population, (intended here as an std::vector<vector_double> containing the objective vectors).

Complexity is \( O(MN^2)\) where \(M\) is the number of objectives and \(N\) is the number of individuals.

Parameters

points – Input objective vectors. Example {{0,7},{1,5},{2,3},{4,2},{7,1},{10,0},{6,6},{9,15}}

Returns

A vector_double containing the nadir point. Example: {10,7}

template<typename Rng>
inline std::vector<vector_double> pagmo::decomposition_weights(vector_double::size_type n_f, vector_double::size_type n_w, const std::string &method, Rng &r_engine)#

Decomposition weights generation.

Generates a requested number of weight vectors to be used to decompose a multi-objective problem. Three methods are available:

  • ”grid” generates weights on an uniform grid. This method may only be used when the number of requested weights to be generated is such that a uniform grid is indeed possible. In two dimensions this is always the case, but in larger dimensions uniform grids are possible only in special cases

  • ”random” generates weights randomly distributing them uniformly on the simplex (weights are such that \(\sum_i \lambda_i = 1\))

  • ”low discrepancy” generates weights using a low-discrepancy sequence to, eventually, obtain a better coverage of the Pareto front. Halton sequence is used since low dimensionalities are expected in the number of objectives (i.e. less than 20), hence Halton sequence is deemed as appropriate.

Example: to generate 10 weights distributed somewhat regularly to decompose a three dimensional problem: 

std::mt19937 r_engine;
auto lambdas = decomposition_weights(3u, 10u, "low discrepancy", r_engine);

Note

All generation methods are guaranteed to generate weights on the simplex (\(\sum_i \lambda_i = 1\)). All weight generation methods are guaranteed to generate the canonical weights [1,0,0,…], [0,1,0,..], … first.

Parameters

  • n_f – dimension of each weight vector (i.e. fitness dimension)

  • n_w – number of weights to be generated

  • method – methods to generate the weights of the decomposed problems. One of “grid”, “random”, “low discrepancy”

  • r_engine – a C++ random engine

Throws

std::invalid_argument – if nf and nw are not compatible with the selected weight generation method or if method is not one of “grid”, “random” or “low discrepancy”

Returns

an std:vector containing the weight vectors

vector_double pagmo::decompose_objectives(const vector_double &f, const vector_double &weight, const vector_double &ref_point, const std::string &method)#

Decomposes a vector of objectives.

A vector of objectives is reduced to one only objective using a decomposition technique.

Three different decomposition methods are here made available:

  • weighted decomposition,

  • Tchebycheff decomposition,

  • boundary interception method (with penalty constraint).

In the case of \(n\) objectives, we indicate with: \( \mathbf f(\mathbf x) = [f_1(\mathbf x), \ldots, f_n(\mathbf x)] \) the vector containing the original multiple objectives, with: \( \boldsymbol \lambda = (\lambda_1, \ldots, \lambda_n) \) an \(n\)-dimensional weight vector and with: \( \mathbf z^* = (z^*_1, \ldots, z^*_n) \) an \(n\)-dimensional reference point. We also ussume \(\lambda_i > 0, \forall i=1..n\) and \(\sum_i \lambda_i = 1\).

The resulting single objective is thus defined as:

  • weighted decomposition: \( f_d(\mathbf x) = \boldsymbol \lambda \cdot \mathbf f \),

  • Tchebycheff decomposition: \( f_d(\mathbf x) = \max_{1 \leq i \leq m} \lambda_i \vert f_i(\mathbf x) - z^*_i \vert \),

  • boundary interception method (with penalty constraint): \( f_d(\mathbf x) = d_1 + \theta d_2\),

where \(d_1 = (\mathbf f - \mathbf z^*) \cdot \hat {\mathbf i}_{\lambda}\), \(d_2 = \vert (\mathbf f - \mathbf z^*) - d_1 \hat {\mathbf i}_{\lambda})\vert\) and \( \hat {\mathbf i}_{\lambda} = \frac{\boldsymbol \lambda}{\vert \boldsymbol \lambda \vert}\).

Parameters

  • f – input vector of objectives.

  • weight – the weight to be used in the decomposition.

  • ref_point – the reference point to be used if either “tchebycheff” or “bi”. was indicated as a decomposition method. Its value is ignored if “weighted” was indicated.

  • method – decomposition method: one of “weighted”, “tchebycheff” or “bi”

Throws

  • std::invalid_argument – if f, weight and ref_point have different sizes

  • std::invalid_argument – if method is not one of “weighted”, “tchebycheff” or “bi”

Returns

the decomposed objective.