cs.NEApr 20, 2026

On Scalability of Multi-Objective Evolutionary Algorithms on Combinatorial Optimisation Problems

Authors: Menghao Tang, Zimin Liang, Miqing Li

Abstract

Scalability of evolutionary algorithms refers to assessing how their performance changes as problem size increases. In the area of multi-objective optimisation, research on the scalability of multi-objective evolutionary algorithms (MOEAs) has predominantly focussed on continuous problems. However, multi-objective combinatorial optimisation problems (MOCOPs) differ from continuous ones. Their discrete and rigid structure often brings rugged landscape, numerous local optimal solutions and disjoint global optimal regions. This leads to different behaviour of MOEAs. For example, SEMO, a simple MOEA without mating selection and diversity maintenance mechanisms, has been shown to be highly competitive, and in many cases to outperform more sophisticated MOEAs on MOCOPs. Yet, it remains unclear whether such findings hold for large-scale cases. In this paper, we conduct an empirical investigation into the scalability of MOEAs on combinatorial problems, with problem size from 50 to 5,000. Our results show that SEMO experiences a decline in convergence speed as dimensionality increases, compared to other MOEAs such as NSGA-II, SMS-EMOA and MOEA/D. We further demonstrate that the absence of crossover is a major contributor to SEMO's underperformance in large-scale problems, and that incorporating crossover into SEMO can substantially accelerate convergence in general, despite being detrimental in spreading solutions over the Pareto front.

Explore similar work

CardsList
May 14, 2026cs.NE

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number r>2r > 2 of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an rr-valued counterpart of the classic \oneminmax benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of O(n2r2log⁡n)O(n^2 r^2 \log n) and a near-tight lower bound of Ω(n2r(r+log⁡n))Ω(n^2 r (r + \log n)). We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of O(n2r(r+log⁡n))O(n^2 r (r + \log n)), matching our lower bound (which also holds for this variant). Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.
Mingfeng Li, Zheng Cheng, Weijie Zheng +1
Multi-Objective Evolutionary AlgorithmPareto Frontier
AskPDF
Jul 26, 2026cs.NE

Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization

This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class CLIMB and analyze the runtime of GSEMO and the widely used NSGA-II on this problem. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a speedup of order Ω(n/log⁡n)Ω(\sqrt{n}/\log n). In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes we propose in this paper, can find the Pareto front of CLIMB in expected O(nlog⁡n)O(n \log n) fitness evaluations, whereas NSGA-II with a fixed population size requires Ω(n1.5)Ω(n^{1.5}) fitness evaluations in expectation. To the best of our knowledge, this is the first rigorous runtime analysis in multi-objective optimization demonstrating a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, like the evolution of population diversity over time, and employs the well-known family-three method to prove the lower bound.
Andre Opris
Multi-Objective Evolutionary AlgorithmEvolutionary AlgorithmsMulti-Objective OptimizationPopulation DynamicsEnd-To-End Speedup
AskPDF
Feb 5, 2026cs.NE

Variable Search Stepsize for Randomized Local Search in Multi-Objective Combinatorial Optimization

Over the past two decades, research in evolutionary multi-objective optimization has predominantly focused on continuous domains, with comparatively limited attention given to multi-objective combinatorial optimization problems (MOCOPs). Combinatorial problems differ significantly from continuous ones in terms of problem structure and landscape. Recent studies have shown that on MOCOPs multi-objective evolutionary algorithms (MOEAs) can even be outperformed by simple randomised local search. Starting with a randomly sampled solution in search space, randomised local search iteratively draws a random solution (from an archive) to perform local variation within its neighbourhood. However, in most existing methods, the local variation relies on a fixed neighbourhood, which limits exploration and makes the search easy to get trapped in local optima. In this paper, we present a simple yet effective local search method, called variable stepsize randomized local search (VS-RLS), which adjusts the stepsize during the search. VS-RLS transitions gradually from a broad, exploratory search in the early phases to a more focused, fine-grained search as the search progresses. We demonstrate the effectiveness and generalizability of VS-RLS through extensive evaluations against local search and MOEAs methods on diverse MOCOPs.
Xuepeng Ren, Maocai Wang, Guangming Dai +4
Parallel Continuous Local SearchMulti-Objective Evolutionary AlgorithmCombinatorial OptimizationOptimalLarge Step Sizes
AskPDF