Research map / Learning theory and algorithms / Combinatorial and search optimization
Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels
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.
Proposes BASC, an evolutionary algorithm for mixed Pareto-lexicographic multi-objective problems with priority levels that samples within PL-based subspaces and adaptively tunes PL strictness parameters, outperforming PL-NSGA-II and posterior-filtering MOEAs on 63 problems.
Problem
Multi-objective optimization where objectives are grouped into lexicographically ordered priority levels (PL-MPL-MOPs); standard MOEAs treat all objectives equally and strict PL adherence can cause premature convergence within levels.
Approach
Decomposes the population into sub-fronts indexed by per-PL Pareto ranks (Grossone-based), samples mating partners only within subspaces formed by sub-fronts at the same PL, and adaptively adjusts PL strictness parameters (a relaxed PL-dominance) to balance exploration across PLs.
Key results
- BASC significantly outperforms PL-NSGA-II on 43 of 63 test problems and is comparable on nine.
- On the 30 CJSP scheduling problems BASC wins against PL-NSGA-II on 27 and against NSGA-II-pre on 25-30 depending on the PL metric.
- On the 9-objective, 3-PL MaF problems BASC beats PL-NSGA-II on 8 problems and loses on 3 (8-3-4 win-tie-loss on first PL metric).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| incorporate BASC instead of PL-NSGA-II | PL-MPL-MOP algorithms · 63 test problems | significant wins over PL-NSGA-II: 43 out of the 63 test problems; comparable on nine | Helped |
| incorporate priority preference during search rather than posterior filtering | PL-MPL-MOP algorithms · CJSPs | Δ(·): BASC significantly better than the four posterior filtering-based MOEAs on most of the test problems | Helped |
| add PL-subspace sampling (ablation) | BASC · CJSP1-CJSP10 | Δ(·): 3-6-1 | Helped |
| add balanced adaptive PL-selection (ablation) | BASC · CJSP1-CJSP10 | Δ(·): 8-0-2 | Helped |
Surprising findings
- Posterior-filtering MOEAs that ignore priority levels fail to provide stable search pressure, and PL-NSGA-II-level comparison shows many ties on the simpler PL-A/B/C problems.
Limitations
- Strictness parameter update depends on a check threshold kappa (set to 0.9 via grid search), a tuned hyperparameter.
- Evaluated only with NSGA-II/NSGA-III/MOEA/D-style EA frameworks; not extended to decomposition- or indicator-based frameworks.
Experimental setup
Datasets: PL-A PL-B PL-C MaF1-MaF15 (modified with priority levels) CJSP1-CJSP30 complex job-shop scheduling problems
Benchmarks: PL-A PL-B PL-C MaF suite with 4 objectives/2 PLs MaF suite with 9 objectives/3 PLs CJSP job-shop scheduling problems
Metrics: Delta metric = max(IGD, GD) per priority level Wilcoxon signed-rank test win-tie-loss
Baselines: PL-NSGA-II NSGA-III-post MOEA/DD-post NSGA-II-pre MOEA/D-pre
Builds on: PL-NSGA-II NSGA-II PL-dominance Grossone methodology
Closest papers by meaning
- 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.84)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.84)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.84)
- ParetoFlow: Guided Flows in Multi-Objective Optimization (ICLR 2025 · similarity 0.83)
- Preference-Guided Diffusion for Multi-Objective Offline Optimization (NeurIPS 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.