论文标题
基于等级的非主导分类
Rank-based Non-dominated Sorting
论文作者
论文摘要
非主导排序是基于帕累托的多目标进化算法（MOEAS）的计算瓶颈，这是由于在建立解决方案候选者之间建立优势关系的运行时密集型比较操作所致。在本文中，我们介绍了排序，这是一种非主导的排序方法，利用排序稳定性和顺序信息，以避免在等级分配阶段昂贵的优势比较。提出了两种算法变体：第一个算法（rankordinal（ro））使用顺序等级比较来确定优势并需要O（n）空间；第二个，RankTintersect（RS），使用设置的相交和比特级并行性，并且需要O（n^2）空间。我们证明了使用NSGA2算法和合成基准在经验模拟中与其他最先进的算法相比，提出的方法的效率与其他最先进的算法相比。 Ranktrestect算法能够显着胜过当前最高现状，可为许多目标提供高达30％的速度。为所有算法提供C ++实现。
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.
