Repeated $$\varepsilon$$-Sampling for Many-Objective Optimization: A Study on MNK-Landscapes

• DOI: 10.1007/s42979-025-03899-1
• Publication Date: 2025-04-29T07:52:04Z
• Authors: Yu Takei; Hernán Aguirre; Kiyoshi Tanaka

Abstract Many-objective optimizers based on Pareto dominance and its extensions rely on the diversity preservation mechanism embedded in survival selection to achieve good performance. However, diversity estimation in these algorithms does not scale up well in many-objective problems, and effective methods should be investigated. This work proposes Repeated

$$\varepsilon$$

ε

-Sampling to select accurately a sample of well-distributed solutions in objective space from the non-dominated solutions set. The proposed method iteratively applies

$$\varepsilon$$

ε

-Sampling that uses

$$\varepsilon$$

ε

-dominance to determine near solutions, increasing at each iteration the

$$\varepsilon$$

ε

expansion rate, gradually eliminating near solutions in objective space. We use Adaptive

$$\varepsilon$$

ε

-Sampling and

$$\varepsilon$$

ε

-Hood as a base algorithm to investigate the proposed method, either as an assistant to the sampling mechanism used by the host algorithm in its truncation selection step or as a substitute sampling mechanism. We use MNK-landscapes as a benchmark problem and compare the performance of the proposed method with MOEA/D, a decomposition-based algorithm widely used for many-objective optimization. To evaluate the Pareto front obtained and the reliability of the algorithms, we use five complementary metrics to assess convergence and diversity. We show that the proposed method accurately samples a subset of well-distributed solutions in objective space, which leads to improved convergence and diversity of the solutions found. We also show that performance by Repeated

$$\varepsilon$$

ε

-Sampling scales up better with the number of objectives and variables of the problem when it replaces Adaptive

$$\varepsilon$$

ε

-Sampling than when it is used as its assistant and performs better than MOEA/D in epistatic binary problems.