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

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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -Sampling that uses $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -dominance to determine near solutions, increasing at each iteration the $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> expansion rate, gradually eliminating near solutions in objective space. We use Adaptive $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -Sampling and $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -Sampling scales up better with the number of objectives and variables of the problem when it replaces Adaptive $$\varepsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -Sampling than when it is used as its assistant and performs better than MOEA/D in epistatic binary problems.