Multiobjective optimization utilities
Multiobjective 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 multiobjective optimization tasks.

bool pagmo::pareto_dominance(const vector_double &obj1, const vector_double &obj2)#
Paretodominance.
Return true if
obj1
Pareto dominatesobj2
, false otherwise. Minimization is assumed.Each pair of corresponding elements in
obj1
andobj2
is compared: if all elements inobj1
are less or equal to the corresponding element inobj2
, 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
ifobj1
is dominatingobj2
,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 runtime complexity of multiobjective EAs: The NSGAII and other algorithms.” IEEE Transactions on Evolutionary Computation 7.5 (2003): 503515.
 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 twoobjectives
 Returns
A
std::vector
containing the indexes of the points in the nondominated 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 nondominated front. Failure to this condition will result in undefined behaviour.
See: Deb, Kalyanmoy, et al. “A fast elitist nondominated sorting genetic algorithm
for multiobjective optimization: NSGAII.” 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 pointsstd::invalid_argument – If points in
do
not all have at least two objectivesstd::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 nondominated sorting genetic algorithm
for multiobjective optimization: NSGAII.” 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 multiobjective 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 multiobjective 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 nondominated 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 multiobjective 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 lowdiscrepancy 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
andnw
are not compatible with the selected weight generation method or ifmethod
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
andref_point
have different sizesstd::invalid_argument – if
method
is not one of “weighted”, “tchebycheff” or “bi”
 Returns
the decomposed objective.