Divideandconquer algorithm for nondominated 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 nondominated sorting algorithm. More...  
Divideandconquer algorithm for nondominated sorting.
Assembles subsets/fronts of mutually nondominated individuals. Afterwards every individual is assigned a rank by pop[i].rank() = frontIndex. The front of nondominated points has the value 1.
The algorithm is described in: Generalizing the Improved RunTime Complexity Algorithm for NonDominated Sorting. FelixAntoine Fortin, Simon Grenier, and Marc Parizeau, Proceedings Genetic and Evolutionary Computation Conference (GECCO), pp. 615622, 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)^{m1}) \), which is often better than the complexity \( \mathcal{O}(n^2 m) \) of the of "fast nondominated sorting" algorithm, in particular for small m.
However, the implementation has a complexity of \( \mathcal{O}(n \log(n)^{m2}c) \), where c is the number of distinct nondominance ranks. If can hence be as bad as \( \mathcal{O}(n^2 \log(n)^{m2}) \), 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 nondominated 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().