Research map / Graph learning / Graph algorithms and clustering
Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial 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.
Proposes GS-MODAC, a GNN-based PPO agent that dynamically configures NSGA-II (and MOPSO) crossover/mutation parameters for multi-objective FJSP and CVRP, using a graph of normalized population objectives as state and an instance-agnostic hypervolume-improvement reward.
Problem
Dynamic algorithm configuration of multi-objective evolutionary algorithms for multi-objective combinatorial optimization (FJSP, CVRP), where prior DRL-based DAC methods rely on hand-crafted state features and were designed for continuous problems.
Approach
Represent the current MOEA population as a graph over non-dominated fronts with normalized objective values as node features, encode it with a GCN, and use the embedding plus remaining budget as PPO state to set NSGA-II crossover and mutation rates each generation, with a reward based on squared percentage hypervolume improvements.
Key results
- On Penta-FJSP 25j5m, GS-MODAC achieves mean HV 5.62e12 vs 5.18e12 for irace and 5.10e12 for MADAC (about 8.2% better than best baseline per the text).
- On Bi-CVRP 500, GS-MODAC reaches mean HV 2.35e2, matching or beating NSGA-II (2.27e2), irace, SMAC3 and MADAC (2.33e2).
- On Bi-CVRP 20, GS-MODAC attains HV 45.18 vs 42.86 for NSGA-II and 34.71 for P-MOCO; P-MOCO is better at size 100 (438.06 vs 366.63).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GS-MODAC instead of tuned baselines | NSGA-II on FJSP · Penta-FJSP, especially 10j5m and 25j5m | mean hypervolume: 4.03$\times10^{11}$ -> 4.16$\bm{\times10^{11}}$; 5.18$\times10^{12}$ -> 5.62$\bm{\times10^{12}}$ | Helped |
| Use GS-MODAC instead of tuned baselines | NSGA-II on CVRP · Bi-CVRP 100, 200, and 500 | mean hypervolume: 1.35$\bm{\times10^2}$ vs 1.35$\bm{\times10^2}$; 1.61$\bm{\times10^2}$ -> 1.60$\times10^2$; 2.33$\times10^2$ -> 2.35$\bm{ | Mixed |
| Remove the normalized remaining-search-budget feature (ablation) | GS-MODAC · Bi-FJSP 25j5m | mean hypervolume: 9.54$\bm{\!\times\!10^4}$ -> 9.47$\!\times\!10^4$ | Hurt |
| Remove the normalized remaining-search-budget feature (ablation) | GS-MODAC · Tri-FJSP 25j5m | mean hypervolume: 2.14$\bm{\!\times\!10^7}$ -> 2.07$\!\times\!10^7$ | Hurt |
| Remove the normalized remaining-search-budget feature (ablation) | GS-MODAC · Penta-FJSP 25j5m | mean hypervolume: 5.62$\bm{\!\times\!10^{12}}$ -> 5.53$\!\times\!10^{12}$ | Hurt |
| Use one GCN layer instead of two (ablation) | GS-MODAC · Bi-FJSP 25j5m | mean hypervolume: 9.54$\bm{\!\times\!10^4}$ -> 9.38$\!\times\!10^4$ | Hurt |
| Use one GCN layer instead of two (ablation) | GS-MODAC · Tri-FJSP 25j5m | mean hypervolume: 2.14$\bm{\!\times\!10^7}$ -> 2.07$\!\times\!10^7$ | Hurt |
| Use one GCN layer instead of two (ablation) | GS-MODAC · Penta-FJSP 25j5m | mean hypervolume: 5.62$\bm{\!\times\!10^{12}}$ -> 5.49$\!\times\!10^{12}$ | Hurt |
| Replace GCN layers with Transformer (ablation) | GS-MODAC · Penta-FJSP 25j5m | mean hypervolume: 5.62$\bm{\times10^{12}}$ -> 5.61$\times10^{12}$ | Hurt |
| Replace GCN layers with GAT (ablation) | GS-MODAC · Penta-FJSP 25j5m | mean hypervolume: 5.62$\bm{\times10^{12}}$ -> 5.54$\times10^{12}$ | Hurt |
Surprising findings
- The GNN state with a single GCN layer is only slightly worse than two layers, and the method performs on par with MADAC on the smallest Bi-FJSP instances.
- P-MOCO, a dedicated Pareto set learning method, outperforms GS-MODAC at the training size of 100 on Bi-CVRP but generalizes worse to other sizes and distributions.
Limitations
- Gains over baselines are small on several 2-objective and CVRP settings, and many differences are not significant.
- Training uses a laptop CPU with 8 GB RAM and reports long training times (up to 3 days), and the reward needs an ideal hypervolume estimated by a doubled-budget run.
- Evaluated only on NSGA-II and MOPSO with a limited set of two problem domains.
Experimental setup
Datasets: generated FJSP instances (5j5m, 10j5m, 25j5m) generated Bi-CVRP instances (100, 200, 500 customers) DAFJS-SDST scheduling variant
Benchmarks: generated FJSP test instances (Bi/Tri/Penta-FJSP) generated CVRP test instances (Bi-CVRP 100/200/500) DAFJS-SDST generalization Bi-FJSP* unseen objectives
Metrics: hypervolume (mean) hypervolume (best) hypervolume standard deviation IGD IGD+ number of non-dominated solutions
Baselines: NSGA-II (default parameters) irace SMAC3 MADAC P-MOCO
Builds on: PPO NSGA-II MADAC GCN
Closest papers by meaning
- Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement (NeurIPS 2023 · similarity 0.90)
- Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization (AAAI 2021 · similarity 0.89)
- Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (NeurIPS 2025 · similarity 0.87)
- Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024 · similarity 0.86)
- ConfigX: Modular Configuration for Evolutionary Algorithms via Multitask Reinforcement Learning (AAAI 2025 · similarity 0.86)
- Learning Encodings for Constructive Neural Combinatorial Optimization Needs to Regret (AAAI 2024 · 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.