2025/05/03 by Mingfeng Li, Li, Mingfeng, Weijie Zheng +3 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Context-Aware Activity Recognition Systems #Embedded Systems Design Techniques #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE)
paper · doi:10.48550/arxiv.2505.01647
openalex publication_date 2025/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Different from single-objective evolutionary algorithms, where non-elitism is an established concept, multi-objective evolutionary algorithms almost always select the next population in a greedy fashion. In the only notable exception, Bian, Zhou, Li, and Qian (IJCAI 2023) proposed a stochastic selection mechanism for the SMS-EMOA and proved that it can speed up computing the Pareto front of the bi-objective jump benchmark with problem size n and gap parameter k by a factor of max\1,2k/4/n\. While this constitutes the first proven speed-up from non-elitist selection, suggesting a very interesting research direction, it has to be noted that a true speed-up only occurs for k ≥ 4log2(n), where the runtime is super-polynomial, and that the advantage reduces for larger numbers of objectives as shown in a later work. In this work, we propose a different non-elitist selection mechanism based on aging, which exempts individuals younger than a certain age from a possible removal. This remedies the two shortcomings of stochastic selection: We prove a speed-up by a factor of max\1,Θ(k)k-1\, regardless of the number of objectives. In particular, a positive speed-up can already be observed for constant k, the only setting for which polynomial runtimes can be witnessed. Overall, this result supports the use of non-elitist selection schemes, but suggests that aging-based mechanisms can be considerably more powerful than stochastic selection mechanisms.