Rank-based Non-dominated Sorting
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.
Code (2)
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Anomaly detection and classification for streaming data using PDEs
Nondominated sorting, also called Pareto Depth Analysis (PDA), is widely used in multi-objective optimization and has recently found important applications in multi-criteria anomaly detection. Recently, a partial differe…
Anomaly DetectionClassificationGeneral ClassificationMerge Non-Dominated Sorting Algorithm for Many-Objective Optimization
Many Pareto-based multi-objective evolutionary algorithms require to rank the solutions of the population in each iteration according to the dominance principle, what can become a costly operation particularly in the cas…
Evolutionary AlgorithmsMulti-User Remote lab: Timetable Scheduling Using Simplex Nondominated Sorting Genetic Algorithm
The scheduling of multi-user remote laboratories is modeled as a multimodal function for the proposed optimization algorithm. The hybrid optimization algorithm, hybridization of the Nelder-Mead Simplex algorithm and Non-…
SchedulingNon-Dominated Sorting Bidirectional Differential Coevolution
Constrained multiobjective optimization problems (CMOPs) are commonly found in real-world applications. CMOP is a complex problem that needs to satisfy a set of equality or inequality constraints. This paper proposes a v…
Multiobjective OptimizationOn Asynchronous Non-Dominated Sorting for Steady-State Multiobjective Evolutionary Algorithms
In parallel and distributed environments, generational evolutionary algorithms often do not exploit the full potential of the computation system since they have to wait until the entire population is evaluated before sta…
BlockingEvolutionary Algorithms