Divide-and-conquer algorithm for non-dominated sorting. More...
#include <shark/Algorithms/DirectSearch/Operators/Domination/DCNonDominatedSort.h>
Public Member Functions | |
| template<typename PointRange , typename RankRange > | |
| void | operator() (PointRange const &pointRange, RankRange &rankRange) |
| Executes the non-dominated sorting algorithm. More... | |
Divide-and-conquer algorithm for non-dominated sorting.
Assembles subsets/fronts of mutually non-dominated individuals. Afterwards every individual is assigned a rank by pop[i].rank() = frontIndex. The front of non-dominated points has the value 1.
The algorithm is described in: Generalizing the Improved Run-Time Complexity Algorithm for Non-Dominated Sorting. Felix-Antoine Fortin, Simon Grenier, and Marc Parizeau, Proceedings Genetic and Evolutionary Computation Conference (GECCO), pp. 615-622, 2013.
The algorithm is based on an earlier publication by Jensen, 2003. Its runtime complexity for n points and m objectives is claimed to be as low as \( \mathcal{O}(n \log(n)^{m-1}) \), which is often better than the complexity \( \mathcal{O}(n^2 m) \) of the of "fast non-dominated sorting" algorithm, in particular for small m.
However, the implementation has a complexity of \( \mathcal{O}(n \log(n)^{m-2}c) \), where c is the number of distinct non-dominance ranks. If can hence be as bad as \( \mathcal{O}(n^2 \log(n)^{m-2}) \), but in practice it is usually fast. The same applies to the reference implementation in the DEAP library (at the time of writing, March 2016).
Definition at line 69 of file DCNonDominatedSort.h.
|
inline |
Executes the non-dominated sorting algorithm.
Afterwards every individual is assigned a rank by pop[i].rank() = frontNumber. The front of dominating points has the value 1.
Definition at line 116 of file DCNonDominatedSort.h.
References shark::dominance(), S, SHARK_ASSERT, SIZE_CHECK, and shark::transform().