Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels

Wenjing HongAAAI 2025 · DOI

TL;DR

This paper introduces a novel algorithm, Balanced Adaptive Subspace Collaboration (BASC), designed to tackle complex optimization problems where objectives have different importance levels (Mixed Pareto-Lexicographic Multi-Objective Problems). BASC effectively balances exploration and exploitation across these priority levels, leading to superior performance compared to existing methods on a wide range of benchmark and real-world problems.

What Problem Does This Paper Address?

Many real-world optimization tasks involve multiple objectives that aren't equally important. For instance, in manufacturing, minimizing cost might be paramount, followed by minimizing production time, and then maximizing product quality. These problems, termed Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels (PL-MPL-MOPs), are challenging because standard multi-objective optimization algorithms treat all objectives as equally important. This can lead to inefficient searches and a failure to adequately address the higher-priority objectives. Existing methods that try to incorporate priority levels often struggle with premature convergence or computational inefficiencies. This paper aims to bridge this gap by proposing a more effective approach to handle these prioritized objectives.

Methods

The core of the proposed solution is the Balanced Adaptive Subspace Collaboration (BASC) algorithm. BASC introduces two key mechanisms:

  • PL-Subspace Sampling Mechanism: This mechanism divides the search space into subspaces based on the priority levels (PLs) of the objectives. It then generates new solutions by sampling exclusively within subspaces corresponding to the same PL. This allows for focused exploration and exploitation within each priority level, preventing the algorithm from getting lost in lower-priority objectives.
  • Balanced Adaptive PL-Selection Mechanism: This component uses a set of adaptive parameters to control the "strictness" of adherence to each PL. These parameters are dynamically adjusted during the optimization process to balance convergence (focusing on higher-priority objectives) and diversity (exploring lower-priority objectives). This adaptive adjustment helps prevent premature convergence on higher PLs and encourages a more balanced exploration across all levels.

These two mechanisms are integrated into a conventional evolutionary algorithm framework.

Datasets

The paper evaluates BASC on a comprehensive set of 63 test problems, categorized as follows:

  • Three Benchmarking Problems: PL-A, PL-B, and PL-C, specifically designed for PL-MPL-MOPs.
  • 30 MaF Problems: An extension of the popular MaF benchmark suite, featuring configurations with four objectives and two PLs, and nine objectives and three PLs.
  • 30 Complex Job-Shop Scheduling Problems (CJSPs): Real-world problems derived from semiconductor manufacturing, featuring four objectives and two PLs.

Key Insights and Ideas

  • Prioritization is Crucial: Standard MOEAs that ignore objective priorities are insufficient for PL-MPL-MOPs, highlighting the need for specialized algorithms.
  • Subspace Decomposition is Effective: Breaking down the search space by priority levels allows for more targeted exploration and exploitation, leading to better performance.
  • Adaptive Strictness Balances Exploration: Dynamically adjusting the adherence to priority levels is key to preventing premature convergence and ensuring a good balance across all objectives.
  • Real-World Problems Benefit: The proposed BASC algorithm demonstrates significant advantages on complex, real-world job-shop scheduling problems, indicating its practical applicability.

Key Results

BASC demonstrated superior performance compared to five state-of-the-art algorithms across the 63 test problems. Specifically:

  • BASC significantly outperformed existing methods on 43 out of 63 test problems.
  • It achieved comparable results on an additional 9 problems.
  • The algorithm showed particular strength on the complex CJSP problems, outperforming PL-NSGA-II (a strong baseline) on 27 out of 30 problems.
  • The paper also conducted an ablative study showing that both the PL-subspace sampling and the adaptive PL-selection mechanisms contribute significantly to BASC's overall performance.

Limitations and Future Work

The authors acknowledge several avenues for future research:

  • Developing More Benchmarks: There's a need for more PL-MPL-MOPs with varying properties (e.g., geometry of optimal solutions, scalability) to further test algorithms.
  • Exploring Other MOEA Frameworks: Investigating how BASC's principles can be integrated into decomposition-based and indicator-based MOEA frameworks.
  • Theoretical Analysis: Extending theoretical analysis of MOEAs to the specific context of PL-MPL-MOPs.
  • Deeper Analysis of Problem Properties: Further exploring the impact of problem characteristics like parameter dependencies and different application scenarios.

Summary updated

BibTeX
@inproceedings{hong2025balanced,
  author = {Wenjing Hong},
  title = {{Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34907},
}
Figure