  Non-dominated sorting is a computational bottleneck in Pareto-based
multi-objective evolutionary algorithms (MOEAs) due to the runtime-intensive
comparison operations involved in establishing dominance relationships between
solution candidates. In this paper we introduce Rank Sort, a non-dominated
sorting approach exploiting sorting stability and ordinal information to avoid
expensive dominance comparisons in the rank assignment phase. Two algorithmic
variants are proposed: the first one, RankOrdinal (RO), uses ordinal rank
comparisons in order to determine dominance and requires O(N) space; the second
one, RankIntersect (RS), uses set intersections and bit-level parallelism and
requires O(N^2) space. We demonstrate the efficiency of the proposed methods in
comparison with other state of the art algorithms in empirical simulations
using the NSGA2 algorithm as well as synthetic benchmarks. The RankIntersect
algorithm is able to significantly outperform the current state of the art
offering up to 30% speed-up for many objectives. C++ implementations are
provided for all algorithms.
