Research map / Learning theory and algorithms / Combinatorial and search optimization
How to Use the Metropolis Algorithm for Multi-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.
Runtime analysis of multi-objective Metropolis algorithms on a new bi-objective multimodal benchmark DLTB, showing parent-replacement variants are inefficient while a keep-parent variant solves it efficiently.
Problem
Whether the advantages of the Metropolis algorithm (accepting inferior solutions to escape local optima), proven for single-objective optimization, carry over to multi-objective optimization.
Approach
Introduces DLTB, a bi-objective multimodal benchmark built from the single-objective DLB problem, where not all local optima are Pareto optimal; shows that replacing the parent with an accepted inferior offspring fails, while keeping the parent (removing only weakly dominated solutions) yields efficient runtimes.
Key results
- Metropolis with parent replacement cannot cover the DLTB Pareto front with one-bit mutation (population size always one), and needs Omega(n^5) time with standard bit-wise mutation.
- GSEMO, SMS-EMOA and NSGA-II cover the DLTB Pareto front in O(n^4) expected time (GSEMO ~3e n^3(n-1)/2 evaluations; NSGA-II O(Nn^3) with N>=4(n-1)).
- Metropolis keeping the parent with bit-wise mutation has an upper bound of 3e/4 n^5 + 3e/2 n^3, and experiments show one-bit variant performs better than other algorithms tested.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the parent with an accepted inferior offspring | Multi-objective Metropolis with one-bit mutation · DLTB | coverage of the full Pareto front | Hurt |
| Replace the parent with an accepted inferior offspring | Multi-objective Metropolis with standard bit-wise mutation · DLTB | expected runtime to cover the full Pareto front | Hurt |
| Use one-bit mutation instead of standard bit-wise mutation (ablation) | Multi-objective Metropolis with parent replacement · DLTB | coverage of the full Pareto front | Hurt |
| Keep the parent when an inferior offspring is accepted (ablation) | Multi-objective Metropolis · DLTB | expected runtime to cover the full Pareto front: cannot cover the full Pareto front -> O(n5) | Helped |
| Use standard bit-wise mutation instead of one-bit mutation (ablation) | Multi-objective Metropolis with parent kept · DLTB | runtime | Hurt |
| Use GSEMO instead of parent-replacement multi-objective Metropolis | DLTB optimizers · DLTB | expected runtime to cover the full Pareto front: Ω(n5) -> 3en3(n−1)/2 | Helped |
| Use NSGA-II instead of parent-replacement multi-objective Metropolis | DLTB optimizers · DLTB | expected iterations to cover the full Pareto front: Ω(n5) -> O(n3) | Helped |
| Use SMS-EMOA instead of parent-replacement multi-objective Metropolis | DLTB optimizers · DLTB | expected runtime to cover the full Pareto front: Ω(n5) -> 3eµn3/2 | Helped |
| Use parent-kept Metropolis with one-bit mutation instead of GSEMO | DLTB optimizers · DLTB | runtime | Helped |
| Use parent-kept Metropolis with standard bit-wise mutation instead of GSEMO | DLTB optimizers · DLTB | runtime | No clear effect |
Surprising findings
- Metropolis with parent replacement, the natural multi-objective extension, cannot cover the Pareto front of DLTB even though the single-objective Metropolis outperforms RLS on DLB.
- The keep-parent Metropolis variant with one-bit mutation experimentally outperforms GSEMO, NSGA-II and SMS-EMOA despite no proven advantage.
Limitations
- Proofs omitted from the paper; the O(n^5) bound for the keep-parent variant is not tight and the experimentally better one-bit variant lacks a proof.
- Only a simple sum of objective differences is used as acceptance rule; other acceptance probabilities unexplored.
- Analysis restricted to bi-objective DLTB benchmark and no additional MOSA features (e.g., dominating-solution counts).
Experimental setup
Benchmarks: DLTB
Metrics: expected number of fitness evaluations to cover the Pareto f
Baselines: GSEMO NSGA-II SMS-EMOA SEMO RLS
Builds on: Metropolis algorithm SEMO GSEMO NSGA-II SMS-EMOA
Closest papers by meaning
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.86)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.84)
- Smooth Tchebycheff Scalarization for Multi-Objective Optimization (ICML 2024 · similarity 0.84)
- Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization (ICLR 2025 · similarity 0.84)
- Simple Extensions of Single-Objective Acquisition Functions and Hedge Strategies for Multi-Objective Bayesian Optimization (NeurIPS 2026 · similarity 0.84)
- PSMGD: Periodic Stochastic Multi-Gradient Descent for Fast Multi-Objective Optimization (AAAI 2025 · similarity 0.83)
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.