A Ranking Method Based on Two Preference Criteria: Chebyshev Function and ε-Indicator


Abstract

Previously a preference relation based on the Chebyshev achievement function to solve many-objective optimization problems was proposed. Although using this preference relation improved the performance of NSGA-II, in this paper we present a new ranking method based on the ∈-indicator and the Chebyshev achievement function. The goal of this new method is two fold: i) to improve the performance of the original algorithm, and ii) to design a parallel sorting method in order to use it with large populations (>> 10^4 individuals). To do so, unlike the original approach, we have completely replaced the nondominated sorting by a method that ranks the population based on these two preference criteria. As the experiments show, the resulting algorithm outperforms both the standard NSGA-II and our previous approach in selected DTLZ problems. We also present a parallel implementation of the new sorting method. The running time analysis shows that the communication overhead is low enough to allow the speedup reach its peak for a large number of processors.