_k_-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization  
Jean Ruppert  
1 Mathematics and Computing S.A.1, L-2360 Luxembourg, Luxembourg  
2  
Markaryta Aleksandrova  
case [8]. However, it is also known that Pareto dominance-based _many_-objective optimization evolutionary algorithms face various difficulties. Among them, the deterioration in the searchability of Pareto dominance-based sorting [4; 9]. As stated in [10], this happens due to the lack of selection pressure. Indeed, when the number of objectives increases, the number of incomparable or equally preferable solutions grows exponentially. To overcome this problem, a number of alternative approaches were proposed. Among them, there are relaxed dominance-based approaches [11], the reduction in the number of objectives via scalarization [12], and the introduction of additional indicators to guide the selection process [13], such as hypervolume. These approaches provide some advantages; however, they also have disadvantages. In particular, the indicator-based approaches require calculating the value of the the relative indicator function; scalarization-based methods require either running several single-objective optimizations during one run or running individual single-objective optimizations over many runs [12]: finally, as stated in [9; 11], the diversity maintenance can become more difficult in relaxed dominance-based approaches. In this paper, we study in detail the application of the recently introduced \(k\)-Pareto optimality-based sorting [14] to the problem of _many_-objective genetic optimization. Here, \(k\) stands for the value of the Pareto optimality. In the rest of the text, we use the terms \(k\)-Pareto optimality and Pareto optimality, as well as the corresponding abbreviations \(k\)-\(PO\) and \(PO\), interchangeably. It was shown theoretically that this sorting procedure maximizes the choice, or diversity, of a subset of the best elements selected with respect to a dominance relation. This characteristic can be valuable for genetic optimization, as a diverse gene pool allows exploring the search space more efficiently. In [14], we suggested to sort solutions by \(k\)-Pareto optimality instead of the traditional Pareto dominance and presented preliminary results demonstrating the high potential of this approach. This paper is an extension of the above-mentioned study with respect to genetic optimization. It presents more detailed experimental results through the following contributions:  
1. Based on the proposed ranking metric _Pareto-optimality_, we study three genetic algorithms in detail: \(PO\)-\(count\), \(PO\)-\(prob\), and \(PO\)-\(prob^{*}\); see Section 4 for the detailed description. All three algorithms are based on \(NSGA\)-\(II\) and differ from the latter in the selection procedure by: * \(PO\)-\(count\): counting \(PO\), which consists of counting the number of dominating solutions (counting \(PO\)); * \(PO\)-\(prob\): approximating \(PO\) via a probabilistic procedure (probabilistic \(PO\)); * \(PO\)-\(prob^{*}\): sequentially combining probabilistic calculation of \(PO\) and Pareto dominance sorting from \(NSGA\)-\(II\). 2. We compare the proposed methods with \(NSGA\)-\(II\) and \(NSGA\)-\(III\) using the 0/1 knapsack problem with the number of objectives varying from 2 to 25.