Hot off the Press: A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization
TL;DR
This paper theoretically demonstrates that incorporating an archive to store best-found solutions enables smaller populations and enhances SPU-based MOEA performance and proves archives reduce expected running time upper bounds (even exponentially).
Abstract
Evolutionary algorithms (EAs) are popular for multi-objective optimization due to their population-based nature. While population updates in multi-objective EAs (MOEAs) are typically greedy and deterministic. However, recent studies have questioned this practice and shown that stochastic population update (SPU), which allows inferior solutions have a chance to be preserved, can help MOEAs jump out of local optima more easily. Nevertheless, SPU risks losing high-quality solutions, potentially requiring a large population. Intuitively, a possible solution to this issue is to introduce an archive that stores the best solutions ever found. This paper theoretically demonstrates that incorporating an archive to store best-found solutions enables smaller populations and enhances SPU-based MOEA performance. Analyzing SMS-EMOA and NSGA-II on the bi-objective OneJumpZeroJump problem, we prove archives reduce expected running time upper bounds (even exponentially). The comparison between SMS-EMOA and NSGA-II also suggests that the (μ + μ) update mode may be more suitable for SPU than the (μ + 1) update mode. We also validate our findings empirically. This paper for the Hot-off-the-Press track at GECCO 2026 sum marizes the work S. Ren, Z. Liang, M. Li, and C. Qian. A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization. IJCAI, 2025, 8921: 8929. [17]