---
title: "A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization"
authors:
  - "Shengjie Ren"
  - "Zimin Liang"
  - "Miqing Li"
  - "Chao Qian"
doi: "10.24963/ijcai.2025/992"
url: "https://ijcai.org/proceedings/2025/992"
pdf: "https://ijcai.org/proceedings/2025/0992.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8921-8929"
track: "Main Track"
keywords:
  - "Search: S: Evolutionary computation"
---

# A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization

Shengjie Ren, Zimin Liang, Miqing Li, Chao Qian

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8921-8929. DOI: [10.24963/ijcai.2025/992](https://doi.org/10.24963/ijcai.2025/992)

## Abstract

Evolutionary algorithms (EAs) have been widely applied to multi-objective optimization due to their population-based nature. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. 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. In this paper, we theoretically show that using an archive allows a small population and may enhance the search performance of SPU-based MOEAs. We examine two classic algorithms, SMS-EMOA and NSGA-II, on the bi-objective problem OneJumpZeroJump, and prove that using an archive can reduce the expected running time upper bound (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. We hope this work may provide theoretical support to explore different ideas of designing algorithms in evolutionary multi-objective optimization.