Weak Pareto Boundary: The Achilles' Heel of Evolutionary Multi-Objective Optimization

The weak Pareto boundary (WPB) refers to a boundary in the objective space of a multi-objective optimization problem, characterized by weak Pareto optimality rather than Pareto optimality. The WPB brings severe challenges to multi-objective evolutionary algorithms (MOEAs), as it may mislead the algorithms into finding dominance-resistant solutions (DRSs), i.e., solutions that excel on some objectives but severely underperform on the others, thereby missing Pareto-optimal solutions. Although the severe impact of the WPB on MOEAs has been recognized, a systematic and detailed analysis remains lacking. To fill this gap, this paper studies the attributes of the WPB. In particular, the category of a WPB, as an attribute derived from its weakly Pareto-optimal property, is theoretically analyzed. The analysis reveals that the dominance resistance degrees of DRSs induced by different categories of WPBs exhibit distinct asymptotic growth rates as the DRSs in the objective space approach the WPBs, where a steeper asymptotic growth rate indicates a greater hindrance to MOEAs. Beyond that, experimental studies are conducted on various new test problems to investigate the impact of WPB's attributes. The experimental results demonstrate consistency with our theoretical findings. Experiments on other attributes show that the performance of an MOEA is highly sensitive to some attributes. Overall, no existing MOEAs can comprehensively address challenges brought by these attributes.