Research map / Optimization / Optimizers
Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first runtime analysis of SMS-EMOA for many objectives on a new m-objective OJZJ (jump) benchmark, plus analyses of stochastic population update, heavy-tailed mutation, and bi-objective OneMinMax/LOTZ.
Problem
Runtime of the SMS-EMOA, a steady-state NSGA-II variant using hypervolume contribution, on many-objective multimodal pseudo-Boolean benchmarks, where NSGA-II is known to fail.
Approach
Proves that SMS-EMOA, unlike NSGA-II, does not lose Pareto-optimal objective values when the population size is at least the maximum incomparable set size, and uses this to bound the time to cover the full Pareto front of a new m-objective OJZJ benchmark in O(mu M n^k) iterations; it also extends stochastic population update and heavy-tailed mutation analyses to many objectives.
Key results
- SMS-EMOA covers the full Pareto front of mOJZJ in O(mu M n^k) expected iterations, with M=(2n/m-2k+3)^{m/2}, while NSGA-II needs exponential time on mOneMinMax.
- Stochastic population update gives at most a speed-up of order 2^k/mu for many objectives, vanishing when m >= k.
- Heavy-tailed mutation gives a speed-up of order k^{k+0.5-beta}/e^k for many objectives, independent of m.
- SMS-EMOA covers the OneMinMax front in at most 2e*mu*n(ln n+1) iterations and the LOTZ front in at most 2e*mu*n^2 iterations for mu >= n+1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace standard bit-wise mutation with heavy-tailed mutation | SMS-EMOA on m-OJZJ · m-OJZJ | expected runtime: speed-up of order k^{0.5+k-\beta}/e^k | Helped |
| Use stochastic population update | SMS-EMOA on m-OJZJ · m-OJZJ | expected runtime: speed-up by a factor of order 2^{k} / \mu; ... vanishes, e.g., when m \ge k | Mixed |
| Use SMS-EMOA instead of NSGA-II | Many-objective m-OneMinMax · m-OneMinMax (k=1) | runtime to cover the full Pareto front | Helped |
| Use SMS-EMOA rather than NSGA-II | OneMinMax · OneMinMax | runtime: 2e\mu n(\ln n+1) iterations; \frac{2e^2}{e-1}\mu n(\ln n+1) | No clear effect |
| Use SMS-EMOA rather than NSGA-II | LOTZ · LOTZ | runtime: 2e\mu n^2; \frac{2e^2}{e-1}\mu n^2 | No clear effect |
Surprising findings
- The stochastic population update's advantage from the bi-objective case largely disappears for many objectives because larger population sizes are needed.
- The authors' conference version wrongly claimed the largest incomparable set equals the Pareto front size; the correct maximum can be considerably larger.
Limitations
- Results are upper bounds on runtime; no tight lower bounds are proven for the stochastic population update variant.
- Analysis assumes population size mu at least the maximum incomparable set size, which can be large.
- Analysis restricted to pseudo-Boolean benchmarks with bit-wise or heavy-tailed mutation and no crossover (crossover only handled as a constant-factor robustness remark).
Experimental setup
Benchmarks: mOJZJ OneMinMax LOTZ
Metrics: expected number of iterations (runtime) expected function evaluations
Baselines: NSGA-II GSEMO NSGA-III SMS-EMOA with stochastic population update
Builds on: NSGA-II SMS-EMOA GSEMO OJZJ heavy-tailed mutation
Closest papers by meaning
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.89)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.88)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.88)
- How to Use the Metropolis Algorithm for Multi-Objective Optimization? (AAAI 2024 · similarity 0.86)
- Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization (ICLR 2025 · similarity 0.86)
- Offline Multi-Objective Optimization (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.