Research map / Learning theory and algorithms / Combinatorial and search optimization
Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
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.
Starts the runtime analysis of SEMO and GSEMO on an unbounded integer bi-objective benchmark, comparing unit-step, exponential-tail, and power-law mutation operators via proofs and experiments.
Problem
Runtime analysis of multi-objective evolutionary algorithms on unbounded integer search spaces, which has been almost unexplored theoretically compared to binary or continuous domains.
Approach
Analyzes SEMO and GSEMO with single- and full-dimensional mutation using three mutation strengths (unit step, bilateral geometric/exponential-tail, power-law) on Rudolph's integer bi-objective benchmark, deriving expected runtime bounds and comparing them experimentally.
Key results
- Theoretical runtime bounds for SEMO/GSEMO with unit-step (order a^2 for constant n), exponential-tail (order a ln a with q=1/a), and power-law (order a^beta, beta in (1,2)) mutation.
- Experiments with a=200 show power-law mutation (beta=3/2) outperforms the best tuned exponential-tail mutation (1/q=50) in both phases.
- Experimentally, power-law runtime scales roughly linearly in a, better than the theoretical bound, suggesting the bounds are not tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use power-law mutation (β=3/2) instead of exponential-tail mutation | GSEMO · Rudolph benchmark f, scenario 1 (a=200, n=2) | total evaluations: 15\,565 ± 15 vs 18\,048 ± 16 (best exponential-tail setting) | Helped |
| Use power-law mutation (β=3/2) instead of exponential-tail mutation | GSEMO · Rudolph benchmark f, scenario 1 (a=200, n=2) | 1st hit evaluations: 1\,301 ± 47 vs 1\,604 ± 34 (best exponential-tail setting) | Helped |
| Use power-law mutation (β=3/2) instead of exponential-tail mutation | GSEMO · Rudolph benchmark f, scenario 1 (a=200, n=2) | cover evaluations: 14\,263 ± 16 vs 15\,050 ± 22 (best exponential-tail setting) | Helped |
| Use unit-step mutation instead of power-law or exponential-tail mutation | GSEMO · Rudolph benchmark f, scenario 1 (a=200, n=2) | total evaluations: 852\,922 ± 11 vs 15\,565 ± 15 | Hurt |
| Set exponential-tail step size 1/q=50 rather than 1/q=200 | GSEMO with exponential-tail mutation · Rudolph benchmark f, scenario 1 (a=200, n=2) | total evaluations: 25\,908 ± 20 -> 18\,048 ± 16 | Helped |
| Tune exponential-tail parameter 1/q | GSEMO with exponential-tail mutation · Rudolph benchmark f, scenario 1 (a=200, n=2) | total evaluations: 96\,148 ± 10; 43\,634 ± 11; 24\,078 ± 14; 18\,048 ± 16; 20\,004 ± 23; 25\,908 ± 20; 47\,236 ± 23 | Mixed |
| Use power-law mutation instead of exponential-tail mutation with 1/q=a/4 | GSEMO · Rudolph benchmark f, scenario 2 (a=20 to 200) | runtime scaling | No clear effect |
| Use power-law mutation instead of its theoretical upper-bound behavior | GSEMO · Rudolph benchmark f, scenario 2 (a=20 to 200) | runtime scaling | Helped |
Surprising findings
- Power-law mutation outperforms exponential-tail mutation even when the latter uses a near-optimal parametrization.
- Empirical runtime for power-law mutation appears linear in the Pareto front size, much better than the proven polynomial bound.
Limitations
- Theoretical bounds appear not tight, especially for power-law mutation, as experiments show better scaling.
- Analysis assumes maximal population size of 2a+1, which is pessimistic.
- Only a single benchmark problem with n-dimensional integer variables is analyzed.
Experimental setup
Benchmarks: Rudolph's bi-objective integer benchmark
Metrics: expected runtime (number of function evaluations) mean and standard deviation of hitting time
Baselines: unit-step mutation exponential-tail mutation
Builds on: SEMO GSEMO Rudolph's integer benchmark variable drift theorem additive drift theorem
Closest papers by meaning
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.87)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.86)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.86)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.85)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.85)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.85)
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.