Jul 2026· GECCO Companion· pp. 49-50· 0 citations· 20 references
Computer Science
TL;DR
This work significantly enhance the understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark, and proves a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years.
Abstract
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in only sporadic tight runtime analyses existing. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark. From this, we prove a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n2), improving over the previous estimate of O(n2 log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(nk+1) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2, 3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Andre Opris: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm. International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8876–8884. [6].
This paper introduces the bi-objective problem class CLIMB and analyzes the runtime of GSEMO and the widely used NSGA-II on this problem, and proves that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes, can find the Pareto front of CLIMB in expected fitness evaluations.
Metaheuristics require sustained global search without sacrificing local refinement, yet many variable-structure methods change operators through one-way iteration schedules. We introduce the Weather State Ants Optimizer (WSAO), in which a discrete-time Markov chain recurrently selects one of three population updates. Sunny, cloudy, and rainy states correspond to global exploration, movement toward nests, and local refinement, respectively. An archive-based mechanism also maintains several spatially separated nests as concurrent search centers. Thirty independent runs compared WSAO with 11 algorithms on 29 CEC2017 and 12 CEC2022 functions. WSAO achieved the lowest Friedman mean rank on both suites, at 2.48 and 2.33. Across five constrained design cases, it joined the leading group by mean objective value on four cases and ranked second on pressure-vessel design. Targeted CEC2022 controls showed that no alternative transition matrix dominated the baseline. Eliminating the trial perturbation worsened every selected function, whereas the contribution of multiple nests depended on the landscape structure. The combined evidence supports recurrent state-controlled search as a competitive framework for continuous numerical and constrained optimization.
It is found that neutral framing of behavioural features, reporting the feature value without prescriptive advice, consistently outperforms the prescriptive variants, and that prescriptive feedback steers the median feature value in the advised direction in only 37% of cases despite empirically grounded advice.
Applied to five engineering optimization problems, modified momentum–leader–differential grey wolf optimizer consistently achieves the lowest objective values, while analytically proving its ability to navigate heavily penalized boundaries and satisfy all constraints.
Xin Su, Yichen Liu· Cluster Computing· 0 citations
The university class timetabling is known to be a classic example of a problem in combinatorial optimization, where an allocation of classes to time periods, classrooms, and tutors is needed. Although modern works mostly concentrate on designing various hybrid or specialized algorithms and metaheuristics, one should also examine the performance of the original algorithm to obtain a baseline metric for future comparisons. This paper considers a simple application of the unaltered SGA on Dataset A that has 38 subjects, 8 tutors, 8 classrooms, five days of operation, and two types of classes (theoretical and practical). As far as scalability was concerned, we have tested several population sizes for the algorithm, namely 15, 30, 60, and 120. Performance metrics such as fitness and the rate of convergence were measured according to the value of the fitness function and runtime as well as memory usage. It could be demonstrated that despite being extremely simple, classical SGA produces valid solutions for this problem but is quite sensitive to changes in population size. To make the analysis more robust, the paper also includes a very basic comparison experiment involving Simulated Annealing as another basis of evaluation.
Y. Farhang, Saman Tarighpeyma Aghbolagh, Ülker Başar· Journal of Innovative Engine...· 0 citations
