Research map / Learning theory and algorithms / Combinatorial and search optimization
Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms
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 running-time analysis of an interactive multi-objective EA (R-NSGA-II), showing it beats NSGA-II on OneMinMax and OneJumpZeroJump but can be exponentially slower on a OneMinMax variant.
Problem
Running time of interactive multi-objective evolutionary algorithms (iMOEAs), which theory had only studied for single-objective-style variants (iRLS, (1+1)-iEA); practical iMOEAs like R-NSGA-II lacked analysis.
Approach
Model the decision maker as a reference point and analyze R-NSGA-II, which ranks critical-front solutions by Euclidean distance to the reference point instead of crowding distance; this drives the population toward the reference point and removes the need for a large population, but can backfire when the closest objective point is far in decision space.
Key results
- R-NSGA-II finds the reference point in O(Nn log n) expected evaluations on OneMinMax for any population size N, versus O(Nn log n) for NSGA-II requiring N >= 4(n+1), i.e. about n times faster with constant N.
- On OneJumpZeroJump, R-NSGA-II with N in o(n^k) runs in O(n^k) expected evaluations, while NSGA-II needs O(Nn^k) with N >= 4(n-2k+3).
- On OneMinMax*, R-NSGA-II with any polynomial population size requires Omega(n^{n/4}) expected evaluations, while NSGA-II needs O(Nn log n); experiments on NK-landscape show R-NSGA-II is much worse than NSGA-II.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use reference-point preference instead of crowding distance in NSGA-II | NSGA-II · OneMinMax | fitness evaluations: O(Nn\log n) -> O(Nn \log n) | Helped |
| Use reference-point preference instead of crowding distance in NSGA-II | NSGA-II · OneJumpZeroJump | fitness evaluations: O(Nn^k) -> O(n^k) | Helped |
| Use reference-point preference instead of crowding distance in NSGA-II | NSGA-II · OneMinMax* | fitness evaluations: O(Nn\log n) -> \Omega(n^{n/4}) | Hurt |
| Use R-NSGA-II with N=1 instead of NSGA-II with N=4(n+1) | OneMinMax optimization · OneMinMax | fitness evaluations | Helped |
| Use R-NSGA-II with N=4(n+1) rather than N=1 (ablation) | R-NSGA-II · OneMinMax | fitness evaluations | No clear effect |
| Use R-NSGA-II with N=1 instead of NSGA-II with N=4(n-2k+3) | OneJumpZeroJump optimization · OneJumpZeroJump | fitness evaluations | Helped |
| Increase R-NSGA-II population size from N=1 to N=4(n-2k+3) (ablation) | R-NSGA-II · OneJumpZeroJump | fitness evaluations | Hurt |
| Use R-NSGA-II instead of NSGA-II | NSGA-II · OneMinMax* | fitness evaluations | Hurt |
| Use R-NSGA-II instead of NSGA-II | NSGA-II · Bi-objective NK-Landscape | fitness evaluations | Hurt |
Surprising findings
- R-NSGA-II can be exponentially slower than NSGA-II on the OneMinMax* variant, because moving closer to the reference point in objective space moves away from it in decision space.
- The reported experiments on the NK-landscape problem show R-NSGA-II performing much worse than NSGA-II, supporting the theoretical failure mode on a combinatorial problem.
Limitations
- Analysis restricted to bi-objective pseudo-Boolean problems with a fixed reference point on the Pareto front and an idealized DM.
- The reference point is set to a Pareto-optimal objective vector, so the DM's preference is modeled rather than human-in-the-loop.
- Experiments on NK-landscape are limited to small problem sizes (n up to 25).
Experimental setup
Datasets: OneMinMax OneJumpZeroJump OneMinMax* multi-objective NK-landscape
Benchmarks: OneMinMax OneJumpZeroJump OneMinMax* bi-objective NK-landscape
Metrics: expected number of fitness evaluations until finding the ref
Baselines: NSGA-II iRLS (1+1)-iEA
Builds on: NSGA-II R-NSGA-II OneMinMax OneJumpZeroJump
Closest papers by meaning
- Why Popular MOEAs are Popular: Proven Advantages in Approximating the Pareto Front (NeurIPS 2025 · similarity 0.90)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.90)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.89)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.88)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.86)
- Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels (AAAI 2025 · 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.