Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Authors: Robbert Reijnen
Yaoxin Wu
Zaharah Bukhsh
Yingqian Zhang
Venue: ICML 2025 poster (2025)
Keywords: Deep Reinforcement Learning
Multi-objective Combinatorial Optimization
Dynamic Algorithm Configuration
Evolutionary algorithm
Primary area: optimization
TL;DR: This work proposes a new approach using deep reinforcement learning (DRL) and graph neural networks (GNNs) to dynamically configure multi-objective evolutionary algorithms for solving multi-objective combinatorial optimization problems.

Abstract: Deep reinforcement learning (DRL) has been widely used for dynamic algorithm configuration, particularly in evolutionary computation, which benefits from the adaptive update of parameters during the algorithmic execution. However, applying DRL to algorithm configuration for multi-objective combinatorial optimization (MOCO) problems remains relatively unexplored. This paper presents a novel graph neural network (GNN) based DRL to configure multi-objective evolutionary algorithms. We model the dynamic algorithm configuration as a Markov decision process, representing the convergence of solutions in the objective space by a graph, with their embeddings learned by a GNN to enhance the state representation. Experiments on diverse MOCO challenges indicate that our method outperforms traditional and DRL-based algorithm configuration methods in terms of efficacy and adaptability. It also exhibits advantageous generalizability across objective types and problem sizes, and applicability to different evolutionary computation methods.

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Robbert Reijnen'
Yaoxin Wu
Zaharah Bukhsh Yingqian Zhang'
Abstract
2022). DAC adjusts the configuration of algorithms in real time, which is advantageous for algorithms facing changes in the search space configuration during execution. This adaptability is especially relevant for iterative algorithms, such as Evolutionary Algorithms (EAs), a prominent class of Evolutionary Computation (EC) techniques for solving complex optimization problems. The performance of EAs relies on the precise adjustment of their parameters and may require changes at various phases of the search process to maintain optimal performance.
Deep reinforcement learning (DRL) has been widely used for dynamic algorithm configuration, particularly in evolutionary computation, which benefits from the adaptive update of parameters during the algorithmic execution. However, ap- plying DRL algorithm configuration for multi- objective combinatorial optimization (MOCO) problems remains relatively unexplored. This pa- per presents a novel graph neural network (GNN) based DRL to configure multi-objective evolution- ary algorithms. We model the dynamic algorithm configuration as a Markov decision process, rep- resenting the convergence of solutions in the ob- jective space by graph, with their embeddings learned by GNN to enhance the state representa- tion. Experiments on diverse MOCO challenges indicate that our method outperforms traditional and DRL-baseed algorithm configuration methods in terms of efficacy and adaptability. It also ex- hibits advantageous generalizability across objec- tive types and problem sizes, and applicability to different evolutionary computation methods.
Deep Reinforcement Learning (DRL) has been successfully used to control parameter values for various single-objective EC algorithms, as reported in the literature (Sharma et al., 2019; Reijnen et al., 2024; Begnardi al., 2025). These approaches address the parameter configuration problem by modeling it contextual Markov decision process (MDP) (Biedenkapp et al., 2020). This enables dynamic algorithm configuration to be approached as a sequential decision- making problem, enabling DRL to control algorithm config- urations during search. Xue et al. (2022) extend the existing DRL-based DAC approaches to address multi-objective op- timization. Although these methods have demonstrated their effectiveness in configuring parameters during the search, their applications are primarily limited to (multi-objective) continuous optimization, such as tuning hyperparameters of machine learning models, as in AutoML (Biedenkapp et al., 2020; Eimer al., 2021), and benchmarking continuous functions (Xue et al., 2022).
1. Introduction
Selecting the right hyperparameters is crucial for the per- formance of optimization algorithms. Some automated al- gorithm configuration (AC) methods [López-Ibãñez et al., 2016; Lindauer et al., 2022) have been developed to iden- tify well-perfomming configurations and reduce the need for labor-intensive trial-and-error tuning. As the optimal pa- rameter values may change throughout different stages of algorithmic deployment (Aleti, 2012), various dynamic al- gorithm configuration (DAC) methods have been proposed in recent years (Biedenkapp et al., 2020; Adriaensen et al.,
In this paper, propose DRL-based, dynamic algo- rithm configuration method designed specifically for solv- ing multi-objective combinatorial optimization problems (MOCOs). Most (multi-objective) combinatorial optimiza- tion problems, such as machine scheduling, vehicle rout- ing, and resource allocation problems, are NP-hard, as they involve finding high-quality solutions in a large space of discrete decision variables. Hence, practical approaches for solving these problems typically rely on heuristics, among which EAs have been widely used in various COPs (Bartz- Beielstein et al., 2014; Zhou et al., 2011).
'Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands. Correspondence to: Yaoxin Wu <y.wu2@tuc.n.
We expect (and confirm with the experiments Section 4. that the existing DAC approach designed for continuous op- timization (i.e., MADAC (Xue al., 2022)) may not work
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
well large-sized, complex COPs with many objectives, due to less smooth solution spaces and wide range of ob- jective values of COPs. To address these challenges, our proposed method, called GS-MODAC, employs a Graph Neural Network to capture the state of the search algorithm. Specifically, we take inspiration from various convergence- and diversity-based metrics for multi-objective optimiza- tion, such as the number of clite solutions, the spacing between solutions, the relative size of holes (gaps) in the solution space, and hypervolume. With this, we expect that our method leverages the graph-based representation to dy- namically learn similar (yet advanced) features during the optimization process to reflect the current state in the mul- tiple objective planes. By representing the state space as a graph, our method provides state configuration indepen- dent of the number of objectives, eliminating the need for practitioners to configure arbitrary state features manually. In addition, GS-MODAC leverages a rewarding scheme de- signed to be incentivized toward Pareto optimal solutions in a problem-agnoseee manner, fostering generalizability between differently scaled COPs.
2. Background and Related Work
Multi-Ohjective Optimization (MOO) and Combinato- rial Optimization (MOCO). Combinatorial Optimiza- tion is concerned with finding the best solution from finite set of feasible solutions. These problems are character- ized by their discrete nature, where the solutions can be represented as integers, graphs, sets, or sequences. Multi- Objective Combinatorial Optimization (MOCO) involves simultaneously optimizing multiple, often conflicting objec- tives for combinatorial optimization problems. The general formulation of MOCO can be expressed as minge X (x) (z), fz(z). ..... : f (z)). Here, X denotes the set of fea- sible solutions, N is the number of objective functions to be optimized, and each fi()) represents an objective function to be minimized.
Definition 1: Pareto Dominance. A solution T1 E X dominates another solution 222 E X (x1 X 22) if and only if: (() S fx(22)) for all i E {I...., N.). and there exists at least one j E {1...., such that fz < (22).
Definition 2: Pareto Optimality. A solution x' E X is considered Pareto optimal if there is no other solution o' E X satisfying x' < xx. In other words, x" is Pareto optimal if it is not dominated by any other solution in X.
Experimentation demonstrates that GS-MODAC is better than state-of-art algorithm configuration methods based on heuristics (irace) (López-Ibáñeez et al., 2016). Bayesian Op- timization (SMAC3) (Lindauer et al., 2022), and a multi- agent DRL approach (MADAC) (Xue et al., 2022). We fur- ther demonstrate that the proposed method can be applied to multiple Multi-Objective Evolutionary Computation al- gorithms to solve different MOCOs from distinct problem domains featuring varying numbers of objectives. Also, the trained models can generalize to effectively solve instances of larger sizes and more constrained problem variants, which were not observed in training.
Definition 3: Pareto Front. The objective of multi- objective optimization is find the Pareto front, which consists of all Pareto-optimal solutions: P {x" X Hz' E X such that x x x'). The correspond- ing Pareto front is defined as: F= {f(z) x PJ. The Pareto front consists of the objective values of the Pareto set, where each (xx represents a point in the objective space.
Definition 4: Hypervolume Indicator. The Hypervolume (HV) indicator is widely used metric for assessing perfor- mance in multi-objective optimization problems, providing comprehensive evaluation of both convergence and di- versity, even without knowledge of the exact Pareto front (Zitzler & Thiele, 1998). For a Pareto front F in the objec- tive space, the HV with respect to fixed reference point R-N is defined as:
Our study offers the following contributions:
1) We introduce GS-MODAC, a GNN and DRL-based method for dynamically controlling MOEA parameter con- figurations for solving MOCOs. This approach overcomes the limitations of static algorithm configuration methods, achieving better convergence and more diverse solutions.
2) We propose a graph representation of solutions in the ob- jective space, which is learned by graph neural network and involved in the state. Based on the normalized objectives, we also present an instance-agnostic reward function that applies to problems of different types and varying sizes.
HV, = (U ((()) UUrO)))))
U ((()EE
(I)
where i is the Lebesgue measure, representing the N N-dimensional volume, and [f(x, refers to N- dimensional cube: [f(z), [f(()), x (w)) spanning the region in the objective space between point on the Pareto front and a fixed reference point r.
3) We evaluate the proposed method on routing and schedul- ing problems and demonstrate its promising generalizability to perform effectively on more constrained problem variants and larger problem instances unseen during training.
2

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Algorithm Configuration. Algorithm Configuration (AC) involves determining optimal parameter configurations for an algorithm to maximize performance across various inputs. Dynamic Algorithm Configuration (DAC) extends AC by adjusting parameters during the optimization process to en- hance performance (Biedenkapp et al.. 2020). Unlike static configurations, DAC aims to balance exploration and ex- ploitation, increasing the likelihood of finding high-quality solutions. According to Karafotias al. (2014), it can be classified into three types: 1) Deterministic, which changes parameter configurations based on predetermined rule, often using a time-varying schedule (Sun et al., 2020); 2) Self-adaptive, integrating parameter adjustments into the search process, allowing parameters to evolve alongside solutions (Michalewiez et al., 2000); and 3) Adaptive pa- rameter control, which adjusts parameters based on search feedback, using credit assignment and operator selection to optimize performance (Aleti & Moser, 2016).
ing high-dimensional configured state spaces and optimizing for multi-objectives complicates the learning process (Yang et al.). Moreover, most studies focus search operator selection, typically configured as discretized actions, and are often trained and demonstrated on simple continuous optimization problems and standard benchmark functions (Ma et al., 2024).
The closest work to ours is Xue et al. (2022), where the authors propose MADAC for tuning parameters in multi- objective evolutionary algorithm (MOEA). The work uti- lizes deloppstccoooiiionnn networks (VDN) (Sunehag et al., 2017), a typical multi-agent RL method, to identify the opti- mal settings for different categories of parameters. The work incorporates information from the specific problem instance, the ongoing optimization process, and the evolving popu- lation of solutions. The reward function incentivizes im- provement, offering rewards for discovering better solutions and greater rewards for further advancements in later stages. The limitation of MADAC is that it typically includes infor- mation on convergences, objectives, and population- based metrics based on arbitrary hand-defined and tuned state fea- tures. This reliance on manually selected features can lead to suboptimal results, as the chosen features may not ad- equately capture the complexity of the environment. To address this, we propose novel DRL-based approach for the dynamic configuration of parameters in MOEAs aimed at solving Multi-objective Combinatorial Optimization prob- lems. Instead of relying on arbitrarily defined features, our approach involves mapping the objective spaces to graph structures and utilizing Graph Neural Networks (GNNs) to aggregate node features states. This method allows for more comprehensive and adaptive representation of the state space, scalable to multiple objective problems, potentially enhancing the performance and robustness of the EAA.
Machine Learning methods like Bayesian Optimization and Neural Networks have been used to tune parameters by pre- dicting parameter performances based on training instances (Lessmann et al. (2011); Biswas et al. (2021); Centeno- Telleria al. (2021)). Recently, Reinforcement Learning (RL) has gained attention for dynamic algorithm configu- ration, especially in evolutionary algorithms (EAs), where parameter configurations can act as actions, and when a configuration set leads to improved solutions, a reward is given to the RL agent. Recent research has demonstrated the effectiveness of RL in controlling the parameters of EAs. For example, Q-learning has been applied adapt the crossover and mutation rates of cach generation to solve vehicle routing problem (Quevedo et al., 2021). Similarly, an EA has been hybridized with SARSA and Q-Learning to control crossover and mutation rates for the flexible job- shop scheduling problem (Chen et al., 2020). Building on RL, Deep Reinforcement Learning (DRL) has demonstrated considerable potential. Notable examples include the use of double deep Q-Network agent (DDQN) to select parame- ters in Differential Evolution (DE) (Sharma et al., 2019) or a Policy Gradient method (Sun et al., 2021), and the works of (Shala et al., 2020; Speck et al., 2021; Biedenkapp et al., 2022) which have shown to generalize to longer horizons and fairly well to larger problem dimension. Extensions of these approaches have further explored multi-objective optimization (Huang et al., 2020; Tian et al., 2022; Reijnen et al., 2022; 2023b). Despite these advancements, apply- ing DRL in multi-objective optimization presents several challenges. Many existing approaches rely on manually configured features derived from convergence and fitness landscapes, such as the number of elite solutions, solution spacing, the relative size of gaps in the solution space, and hypervolume, to define the states in the MDP. This process is labor-intensive and often suboptimal. Additionally, manag-
3. The Method
This section presents our proposed method, GS-MODAC (Graph-Supported Multi-Objective Dynamic Algorithm Configuration). GS-MODAC employs Graph Neural Net- work (GNN) to capture the state of the search algorithm and Deep Reinforcement Learning (DRL) to configure the next search iteration to solve MOCOs. Graphs provide a flexible way represent structured embeddings, and GNNs effectively model complex structures and extract meaningful representations (Zhou et al., 2020). In this work, GNNs ex- tract the graph state, allowing the DRL agent to make more informed decisions based on the current search state. By representing the state space as a graph, our method uses a state configuration independent of the number of objectives, eliminating the need for practitioners to manually customize state representations for varying numbers of objectives. We illustrate the overview of GS- MODAC in Figure 1.
3

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objectinn Combinatorial Optimization
Problem Instance
State
Environment Configuration
Objective Space
Pareto Fronts
Normalization
Graph Config
State Configuration
Relu
Pooling
Parameter Configuration
Recombination
Evaluation
Linear
Reward R
Acbor
Selection
DRL Agent
Algorithm
Reward Computation
Action at
The GS-MODAC framework. The framework integrates DRL agent with graph- representation of the search state to dynamically configure each iteration of the search for multi multi-obeecctiv optimization. At each iteration, the current population is converted into a graph where nodes represent normalized objective values of solutions across multiple objective planes, and edges connect solutions within the different Pareto fronts. A Graph Neural Network (GNNs) extracts an embedding, which the agents uses configure the next iteration. The chosen actions are applied the environment, which returns a new population solutions, an updated state, and reward signal for learning.
Figure 1:
3.1. MDP formulation for GS-MODAC
izes to unexplored problem instances (Sharma al., 2019; Sun et al., 2020; Xue et al., 2022). These configurations typically include convergence information, objective values, and population diversity metrics. In contrast to the litera- ture, we innovatively propose mapping objective spaces to graphs and leveraging GNNs to dynamically learn state rep- resentations. The graph transformation of objective space illustrated in 'state configuration" in Figure
GS-MODAC is built upon the foundation of Dynamic Al- gorithm Configuration (DAC) principles (Biedenkapp et al., 2020), dynamically adjusting parameter configuration of EAs during their optimization processes. This process can be formulated as a contextual Markov Decision Process (MDP) Mr, with shared action and state spaces, but with different transition and reward functions for each instance in T. Each M, corresponds to the MDP of a specific problem instance i, encapsulating the state space S, action space A, state transition function T;, and reward function Rt
This transformation constructs graph-based base representa- tion of the current population's 's solutions across multiple objective planes. Each node in the graph corresponds to a solution, with its features comprising only the normalized objective values. Normalization is performed using the best objective values encountered during the search and the worst values observed in the initial generation. Non-Dominated Sorting is applied to rank the nodes into distinct Pareto fronts. Nodes within the same front are then interconnected, resulting in a structured graph that captures the hierarchy of solutions. This eliminates the need for manual state space design, process known to cumbersome and suboptimal. To ensure the state configuration is independent of the mag- nitude of objective values, we normalize the solution space relative to reference point that is defined by the worst observed objective values in the first population of solutions. In doing so, we provide a state configuration that effectively represents the algorithmic convergence and the diversity of solution performances, potentially generalizing to problem instances with varying objective magnitudes. An additional feature vector is correspondingly included, containing the normalized number of generations that have been passed by, representing the remaining budget available for the search.
In GS-MODAC, given a target algorithm with a configura- tion space θ, a policy æ maps a state s E to an action A, corresponding to a hyperparameter configuration 0 e Ô. The goal is train policy that enhances algorithm performance across diverse set of problem instances by minimizing the expected cost c(T, i) over instances E I. To further facilitate generalizability, we define shared reward function R to consistently measure performance im- provement across different problem instances. This function R ensures that the policy learns to optimize the performance of the target algorithm to generalize well across various in- stances rather than overfitting specific instances. We intro- duce the components of the MDP underlying GS-MODAC as follows:
States. The state space S provides a DRL agent with infor- mation on the current status of the search algorithm, help- ing to select the best action for the next iteration. Several studies have attempted create state configuration that accurately represents the convergence process and general-

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
The action space A is represented by multiple continuous values, each associated with an evolutionary algorithm parameter to be controlled. These values are normalized between -1 and 1 on parameter scale, defined based on the recommended values from rules of thumb for EA tuning (Coello et al., 2007).
Actions.
algorithm one-time with a higher budget (e.g., doubled). It is worth noting that our reward function is instance-agnostic and thus applicable to different instances of varying sizes and complexities. We empirically observe that the reward function performs consistently well on different problems and delivers outstanding generalizability of trained models.
Transitions. The transition function outlines the dynamies of the search algorithm and is led by interactions between the agent and the problem environment. In the context of GS-MODAC, each interaction (step) with the environment serves as a search iteration. Given state St, an agent takes a action a,, and the probability of moving to state 8t+1 is denoted as (ss+11/s, at). Unlike the state, action, and reward spaces (in the scope of this work), the transition function is contingent upon the specific instance i L.
3.2. Graph-based policy learning and Training Algorithm
We use the Proximal Policy Optimization (PPO) algorithm (Schulman et al., 2017) to train the parameterized policy, PPO is a widely used and highly effective policy gradient algorithm that uses probability ratio between policies to maximize the improvement of the current policy without the risk of performance collapse. In our case, the agent utilizes neural network that first processes the representation of the graph-based state through two layers of the graph con- volutional network (GCN) (Kipf & Welling, 2016). These layers are designed extract and aggregate node embed- dings (i.e., representations) effectively, capturing the essen- tial structural information within the graph. Then, global mean pooling operation is applied to average the node em- beddings, producing a single embedding across the entire graph. The embedding is concatenated with an additional feature vector containing specific search budget information. The enriched embedding is finally fed into a linear layer to predict the mean values of action distributions. We have performed ablation study in Appendix E, where we eval- uated and tested the setup and verified the effectiveness of our approach.
Rewards. The reward function is critical to guide policy learning. In multi-objective optimization, the rewarding system should encourage algorithmic convergence towards the optimal Pareto front. However, the evolving towards the Pareto front often turns increasingly demanding along search steps. The early search stages typically allow for quick gains, while the later stages require substantially more effort. In light of this, we design rewards for enhancing the evolvement of the Pareto front in the latter.
In particular, we design the reward function as follows: At each iteration t, we assess whether the hypervolume of the population H Veurrent exceeds the best hypervolume previ- ously observed Voes. If HVeurent > H Vbest, we compute the percentage improvements, that is, Acurent and Abett and then calculate the reward as the difference between the squared improvements. In this way, we magnify the rewards for larger improvements in the later stages of the conver- gence, encouraging significant evolvement of the Pareto front. The reward is defined as follows:
3.3. Multi-Objective Evolutionary Algorithm Deployment
Exact methods can find the Pareto set in Multi Multi-Objective Combinatorial Optimization (MOCO). However, the com- putational demands of these methods tend to increase expo- nentially with problem complexity, which often makes them impractical for large-scale applications. As a more feasible alternative, heuristic methods, particularly multi-objective evolutionary algorithms (MOEAs), popular in practice due to their ability to effectively approximate Pareto fronts in a computationally efficient manner. In this work, we demonstrate GS- MODAC by applying it to two widely used algorithms: 1) NSGA-II (Deb et al., 2002), which imple- ments a non-dominated sorting mechanism with a crowding distance metric to preserve solution diversity throughout the scarch, ensuring comprehensive exploration of the Pareto front; and 2) Multi- Objett-Oeeeetivee Particle Swarm Optimization (MOPSO) (Coello & Lechuga, 2002), a swarm intelligence algorithm, which adjusts positions of particles by tracking both individual best locations and the best discoveries in the swarm. It integrates an archive store non-dominated solutions effectively cover the Pareto front.
A2 aurret
2 hest
if V Veurrent > H Vhest
otherwise
where Acurem and Abeat are calculated as follows:
H HVarrent
H HV Vinitial
A Aurrent=
x 100,
H Vuleal
HV
Vocat
H Vmittil
A Abest
x 100.
H ideal
H Vinitall
Hypervolumes are calculated using nadir point, defined by the worst-case values of objectives in the initial population of solutions. The ideal hypervolume H Wi is computed using this nadir point, along with an ideal point, which approximated by running the underlying evolutionary
5

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
4. Experiments
thumb, configuring the erossover parameter as 0.7 and the mutation parameter 0.02 (Coello et al., 2007). Addi- tionally, shown in Appendix D, we empirically validate that our method effectively configures MOPSO, a swarm intelligence- based approach. We compare the proposed GS- MODAC against three algorithm configuration methods for tuning NSGA-II parameters: two widely used static AC methods, SMAC3 (Lindauer al., 2022) and irace (López- Ibáñez et al., 2016), and recent RL-based DAC approach, MADAC (Xue et al., 2022).
We evaluated GS-MODAC on two multi-objective combina- torial optimization problems to assess its performance. scal- ability, and generalization. Comparisons are made against static and dynamic algorithm configuration methods. All code and experimental details are made publicly available !
Problems. We apply our proposed method to two multi- objective combinatorial optimization problems: Flexible Job Shop Scheduling Problem (FJSP) and Capacitated Vehicle Routing Problem (CVRP). The FJSP involves scheduling multiple jobs, each composed of various operations, onto set of machines. The operations of each job must be com- pleted in a specific sequence, with each operation featuring a predefined processing time on specific machines. Based on the literature (Tamssaouet et al., 2022), we focus on min- imizing Makespan, Balanced Workload, Average Flowtime, Total Workload, and Maximum Flowtime. We refer to the variants of FJSP as the Bi-, Tri- and Penta-FUPS, solving the first 2, first and all 5 objectives, respectively. CVRP involves determining optimal routes for a fleet of vehicles to serve set of customers. Each customer has specific demand and each vehicle has a capacity limit that must not be exceeded. The objectives are to minimize the total travel distances and the longest route. We refer to the CVRP problem composed of these two objectives as the Bi-CVRP problem. Please refer Appendix A for a comprehensive discussion of FJSP and CVRP, including the constraints and objectives addressed in this work.
SMAC3 is a hyperparameter tuning method that combines Bayesian optimization and random forest regression. For the tuning. we use the generated test instances for each given instance size. Bayesian optimization is used to draw param- eter configurations from the defined parameter configuration ranges and evaluate them on the provided tuning instances over 10.000 runs of the NSGA-II configured algorithm, last- ing between 5 to 14 hours for the Bi-CVRP instances and between 8 to 40 hours for the FISP-variants. We also use the Iterated Race (irace) tuming method, which employs an iterative racing procedure. In each iteration (or 'race"), ) the worst-performing configurations are replaced with new ones, optimizing settings based on set of given instances. irace was tuned with the same budget as the BO tuning method, taking between 3 and 12 hours for Bi-CVRP problem con- figurations and 5 to 20 hours for the FISP-based variants, respectively. Since MADAC is designed to select discrete actions, we discretize the parameter space of NSGA-II with 10 actions between 0.6 and 1.0 as crossover rate and between 0 and 0.1 for the mutation rate (in line with rules-of-thumb for EA parameter configurations (Coello et al., 2007)).
Instance generation. For FJSP, we generate train and test instances for three distinct problem sizes: 1) 5 jobs and 5 machines (5j5m). 2) 10 jobs and machines (10j5m), and 3) 25 jobs and machines (25j5m), following the instance generation configuration of Song al. (2022). We generate 200 instances for each size, consisting of 100 instances for training and 100 for testing. Each instance contains a vary- ing number of operations per job, ranging from 4 to 8, and the processing time for each operation varies between 2 and 20 time units. The same instance sets are used for experi- ments with 2, 3, objectives. For CVRP, we generate 3 distinct sizes of 100, 200, and 500 customers, according to the instance generation of da Costa et al. (2021). We create 200 instances per problem size using random 2-dimensional coordinates for each customer and the depot in the 0 to range. Each customer has a random demand between I and 9, and the vehicles have a capacity of 40 units.
Training, We trained GS- MOODCC for each problem con- figuration with randomly generated problem-instance sizes. The action space for NSGA-II is defined as two contin- uous actions with ranges (0.6, 1.0) and (0.0, 0.1) for the crossover and mutation rates of NSGA-II. The training pro- cess involved 1 1.000,000 steps for the scheduling problems and 2.500.000 steps for the routing, configured with 50 gen- erations of search and a population size of 50. It was carried out on an Intel(R) Core(TM) i7-6920HQ CPU @ 2.90GHz with 8.0GB of RAM and five parallel environments. The training duration varied for different-sizenn instance sets, tak- ing around 11, 15, and 26 hours for the Bi-CVRP problem configuration and between 5 hours and 3 days for the differ- ent configured FJSP-based problems. The training process spans 2000 epochs with 500 steps per epoch. The model parameters are set as Schulman et al. (2017), and the net- work layers are configured with 64 nodes. The MADAC baseline model is trained according to Xue et al. (2022), taking between 2 and 8 hours for Bi-CVRP and 12 and 60 hours for the FJSP-based variants.
Baselines. To show the performance of our proposed dy- namic algorithm configuration method on solving multi- objective FJSP and CVPR, we use NSGA-II as base al- gorithm, whose values have been configured with rules of
'https: /ttttttttuubb/ cwm www.t//wwee/eeeeneeeeeoee GS-MODAC
6

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Table I:
Performance comparison of different methods in solving 100 instances of various problems of varying sizes 10 times, based on the mean found hypervolume (mean), the best-found hypervolume (max), and the standard deviation (std).
Bi-FJSP- 5j5m
Bi-FISP- 10j5m
Bi-FISP 25j5m
Method NSGA-II
mean
max
std
mean
max
std
mean
max
std
1.87 10*
2.02 10*
3.82 x.21 10
4.11 10
2.29x10'
9,41x 10
9.93x 10
4.84 10
frace
109
200
3.90x 1006x10a 10
4.11x10
1.95x10²
9.52x10*
9.97x10*
4.03 10
SMAC3
10
200
3.89x104 100
4.13x10
2.19x10*
905
9.97
4.46 10
MADAC
10*
1.95x00
3.69x10* x05
3,98x
4.47x
9.24x10'
9.72x10*
3.09 10
GS-MODAC
109
10
3,92x10* x007
4.15x10*
1.97
9.54x10
10.0x
4.40x 10
Tri-FISP 5j5m
Tri-FISP 10j5m
Tri-FISP
25j5m
Method
mean
max
std
mean
max
std
mean
max
std
NSGA-II
2.06x 10
2.22x10"
5.53x100 x.32x
5.95 10
3.09x
2.05x10'
1.13x 2.18x10'
irace
2.11x10
2.26x10
1.16x10
5.47x109
5.82x10
2.65x10'
2.07x10²
2.20x107
1.07 10
SMAC3
x.09x108
1.2
5.65x109 102
x.0
x09
2.07x10'
2.20x107
1.01 10
MADAC
1.99
2.14x106
x.39x101 8.86x10*
x.87
5.97x10*
2.09x10'
x.97 2.20x10²
GS-MODAC
2.10x109
2.25x10
1.16x10*
5.70
6.09 10
2.99x10'
2.14x10
2.27 x x10
1.09x 10
Penta-FiSS 5j5m
Penta-FISP 10j5m
Penta-FJSP 25j5m
Method
mean
max
std
mean
max
std
mean
max
std
NSGA-II
6.01 x10
3.70x 6.49x10' "
0.48x10"
3.96x 10 2.42 4. 10
5.08x10
5,48x 10 2.75 10
irace
x 2098x10"
2.35x10'0
5.63 5.18x10 4.95x10'2 2
2.92 10 5.33x100²
SMAC3
6.08 10
60
3.97x10" 3.29x10
4.2
2
MADAC
6.28x10"* 10
10
2.72x10
3191
4.29x
4.36x1010
5.1x10
5.74x10
5.01 x 2
GS-MODAC
6.58x 6.15x10
10
3040x10
4.16x10
4.5
2.40x10
5.62x10
6.07x
3.20x "
Bi-CVRP 100
Bi Bi-CVRP-. 200
Bi-CVRP 500
Method
mean
max
std
mean
max
std
mean
max
std
NSGA-II
1
102
7.84
1.56x102
1.72x 10
9.05
2.2
204
1.27 10
irace
103
102
8.02
1.2
1.72x102
9.53
2.2
1.26x 102
SMAC3
1.3
1
7.89
1
1.7
9.59
2.2
2.5
1.42x10*
MADAC
1
1
8.01
1.61
1.76 10
9.22
2
2.5
1.29x10*
GS-MODAC
1.35x10²
1.
7.95
10
1.76x10*
9.50
2.3
2.59x10²
1.41x10'
Testing, After training, the GS-MODAC agent is ready to be applied to tune the parameters of NSGA-II to solve unseen problem instances. Each experiment performed by running each algorithm 10 times on 100 test instances for comparison. The evaluation is based on three metrics: average hypervolume (mean), best hypervolume (max), and standard deviation (std), which are computed by averaging all test instances for each problem. Hypervolumes are calcu- lated using predefined reference points for each instance to ensure fair comparison. The paper highlights the highest mean and max hypervolumes in bold and underlined values that significantly outperform all other methods using the Wilcoxon rank-sum test (p < 0.05).
MODAC in comparison to existing methods, its ability to generalize to previously unseen instances of varying sizes,
adaptability more complex problem variants, and its scalability across different objectives.
RQ1: How does GS-MODAC perform compared to the base algorithm NSGA-II and three AC baseline meth- ods for various problem types and sizes of objectives? Table presents the performances of various methods, in- cluding the mean average performance, mean best-found solution, and the standard deviations for each method on two different problem types. The results highlight the effective- of GS-MODAC in controlling evolutionary parameters, achieving the best average and best-found solutions. For the smallest instance size in two-objective problems (Bi-), the baseline methods perform competitively, with the MADAC and irace configured baselines finding comparable mean and max solutions. However, GS-MODAC consistently excels in problem configurations with larger objective spaces, such
4.1. Experimental results
We have formulated research questions evaluate the per- formance of the proposed GS-MODAC method. Specif-
ically, these questions assess the effectiveness of GS-

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Ojecctive Combinatorial Optimization
GS MOCAC
GS-MODAC
Obj 3: Average Flowtime
7.5
SMAC3
100
NSGAİi
90
Hypervolume
6.5
5.5
60
200
160 Obj 1: Makespan
70 60 50 40 30 20
Obj 2: Balanced Workload
140
120
10
50
Iteration
Figure 2: Comparison of GS-MODAC, SMAC3, and NSGA-II solution methods: (a) Average convergence rates and (b)
Pareto front distributions.
Table 2: Generalizability of the trained models to solve unseen instances of different sizes.
Bi-CVRP- 100
Bi-CVRP-
200
Bi-CVRP 500
Method
std
mean
std
mean
max
std
NSGA-II
1.34x10²
x,4
7.84
1.56x10
1.72x10 9.05
2.48x10² 20
1.27 x12
GS-MODAC 100
1.35x10
1,48x
7.95
1.59x102
1.75x10
9.25
2. 2.5
x.3
GS-MODAC 200
1.35x10
1.48 10
8.22
1660
1.76x10
9.50
20
2.56x10*
1.36x10'
GS-MODAC
1.33x102
x.4
8.52
10
1.75x10
9.33
2.35x102
2.59x102
1.41110
GS-MODAC- all sizes
1.34x10
1.48x10
7.97
1.59x10
1.74x10 9.03
2.3
2.59x
1.1x10'
problems with objectives and larger combinatorial search spaces (large instances configurations). This is partic- ularly evident in the FISP problem configurations with five objectives (Penta-), where GS-MODAC finds significantly better solutions than all baselines regarding mean and max the Penta-FISP problem
RQ2: How well do the trained GS-MODAC models gen- eralize to previously unseen instances of varying sizes? We assess the ability of the trained GS-MODAC models to solve previously unseen instances of different sizes. The re- sults of this evaluation are presented in Table 2. In the table, the rows show the instance sizes used for training, while the columns show the instance sizes on which trained models are tested. We found that models trained on smaller problem instances and deployed on larger instances experienced slight decline in performance, but still managed to achieve performance comparable to the best performing baseline method (MADAC) while outperforming the other baselines. Morcover, models trained on a more diverse set of instance sizes can effectively learn robust, well well-performing, all- around policy. The results suggest that our models could generalize and solve problem instances beyond the size which they were trained.
found solutions. Specifically, configurations with 25 jobs and 5 machines, GS-MODAC's mean and maximum solutions are 8.2% and 5.7% better, respectively, than the best rest-performing baselines (irace and MADAC) and 10.6% and 10.8% better than the vanilla con- figured NSGA-II method.
Figures 2a and 2b illustrate that the GS-MODAC method converges significantly faster in finding the best hypervol- ume for a Tri-FJSP with 10 jobs and machines, compared baseline approaches. It achieves better-converged hyper- volume, reaching lower minimum values for each objective, and shows a wider spread across the different objective axes. Similar convergence patterns were observed for other in- stances, demonstrating the robustness of GS-MODAC. In Appendix D, we provide further analysis using alternative performance metrics to demonstrate GS GS-MODAC's ability converge towards the true Pareto front while maintaining diverse and high-quality set of solutions.
RQ3: How effectively can trained GS-MODAC mod- els handle previously unseen, more complex problem variants? We evaluate the generalization capability the trained GO-MODAC models by applying them to previously unseen instances of a different and more complex prob-
8

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Ojjective Combinatorial Optimization
Table 3: Comparing the generalizability of trained models to solve instances of more complex problem variants.
BI-DAFIS-SDST
TrIDDFFS--DST
Penta-DAFIS-SDST
Method
mcan
max
std
mcan
max
std
mean
max
std
NSGA-II
1.32x 10 1.4 7.93x 10
3,46x10
2.01 3.7 8.19x10' 8,92x 10 x.89 10
irace
1.4
1.47x10* 5.60x10
3.49x10* 30
1.86x10" 8.10x10'
8.76x 10 3.97 10
SMAC3
1.40x10
1.48x100
7.08x10"
3.37x10
3.64x10*
1.94x10"
8.26x10'
9.01 4.76x10
GS-MODAC- FISP-10j5m
1.42x10
1.50x10
6.30x10*
3.68x10*
3.94x10*
2.02x10'
9.11x1014
9,93x10
5.48x10
GS- -SDMO DAFIS SUDUSSSSSIIAR
1.4x110 1DST1144
1.51x10
1.7xx003.733111 4.00
2.25x10"
100x100 9.05x10'4
6.45x10
Table 4: Comparing the generalizability of the trained models to solve problem configuration to optimize different objectives that were not optimized in training.
Bi-
5j5m
Bi-FISPs
10j5m
Bi-FJSP# 25j5m
Method
mean
std
mean
std
mean
max
std
NSGA-II
304
3.5 9.64 4.05x10'
9.88 10
1.31 102
3.93 10
2.57 10 309
irace
3.58x10 3
x.5
9.66x10
1.48x x19 10
109
x00
2.6
SMAC3
3
3.58x10
4.60x10*
9.6
1.58x 9.8
3,92x10
3.24x 3,9
GS-MODAC
3.51x10
3.58x10
3.9
9.66x10
9.93x103
1.60x102
3.93x104
3.98x104
202
lem variant. This problem extends the Bi-, Tri- and Penta- objective FISP with assembly constraints and sequence- dependent setup times, including additional precedence con- straints between different jobs and setup times operations on machines subject to the scheduling sequence. We tested the proposed method on so-called 'DAFIS' scheduling problem as provided in Birgin al. (2014), which has been extended with sequence-dependent setup times. The re- sults, shown in Table 3, indicate that GS-MODAC trained on DAFJS-SDST demonstrates superior performance in most cases, except for the mean HV in the Penta-objectives variant. Furthermore, the model configuration trained on the 10j5m problem variants effectively transfers to more complex problem scenarios. In particular, GS-MODAC trained in 10j5m configurations outperforms all other base- lines specifically tailored to the DAFJS problem variant.
5. Conclusion
This paper introduces Sraph-SSuppoted Multi-Objective Dy- namic Algorithm Configuration (GS-MODAC), novel ap- proach that integrates Graph Neural Networks (GNNs) and Deep Reinforcement Learning (DRL) to dynamically con- figure Evolutionary Algorithms for solving multi-objective combinatorial optimization problems. GS-MODAC repre- sents the evolving state the search process as a graph, capturing the structural and convergence dynamics of solu- tions across multiple objectives. To ensure robustness across different problem instances and problem configurations, we propose an restace-agnostie reward function that is suit- able to diverse problem types and sizes. Empirical results demonstrate that GS-MODAC outperforms both traditional Algorithm Configuration approaches and sate-of-the-ar DRL-based dynamic algorithm. achieving better effective- and adaptability. Additionally, our method generalizes effectively to larger, more constrained problem instances not encountered during training.
RQ4: How effectively does the GS-MODAC model trained on a specific set of objectives adapt to different objectives than those encountered during training? We evaluate the ability of trained models to generalize across dif- ferent variants of FISP problems configured optimize for objectives different from those explored in training. Specif- ically, we assess how well models trained to optimize ob- jectives A and B perform when applied to a variant of the problem that is instead configured to optimize for objectives and D. This transfer scenario denoted as Bi-FJSP= From Table 4, it is clear that trained models can be trans- ferred to other problem configurations, finding solutions of similar better quality than the configured baselines, with similar performance gap as consistently observed for two objective problem variants displayed in Table 1.
Acknowledgements
This work supported by the Luxembourg National Re- search Fund (FNR) (15706426).
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
9

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Obeective Combinatorial Optimization
References
Coello, C. A. C., Lamont, G. B., Van Veldhuizen, D. A., et al. Evolutionary algorithms for solving multi-objecfiiv problems, volume 5. Springer, 2007.
Adriaensen, S., Biedenkapp. A., Shala, G., Awad, N., Eimer, T., Lindauer, M., and Hutter, F. Automated dynamic algorithm configuration. Journal of Artificial Intelligence Research, 15:1693-1699 2022.
Coello, C. C. and Lechuga, M. S. Mopso: A proposal for multiple objective particle swarm optimization. In Proceedings of the 2002 Congress on Evolutionary Com- putation. CEC'02 (Cat. No. 02TH8600), volume 2, pp.
Aleti, A. An adaptive approach to controlling parameters of evolutionary algorithms. Swinburne University of Tech- nology, 2012.
1051-1056. IEEE, 2002.
da Costa, P., Rhuggenaath, J., Zhang, Y., Akcay, A., and Kaymak, U. Learning 2-opt heuristics for routing prob- lems via deep reinforcement learning. SN Computer Science, 2:1-16, 2021.
Aleti, A. and Moser, I. A systematic literature review of adaptive parameter control methods for evolutionary al- gorithms. ACM Computing Surveys (CSUR), 49(3):1-355 2016.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, fast and elitist multiobjective genetic algorithm: Nsga- ii JEEE transactions evolutionary computation, 6(2):
Bartz-Beielstein, T., Branke, J., Mehnen, J., and Mersmann, O. Evolutionary algorithms. Wiley Interdisciplinary Re- views: Data Mining and Knowledge Discovery. 4(3): 178-195, 2014.
182-197, 2002.
Eimer. T., Biedenkapp, A., Reimer, M., Adriaensen, S., Hut- ter, F., and Lindauer, M. Dacbench: A benchmark library for dynamic algorithm configuration. In Proceedings of the Thirtieth International Joins Conference on Artificial Intelligence (IJCAI22), ijcai.org, August 2021.
Begnardi, L.., Meijenfeldt, B., Zhang. Y., van Jaarsveld, W., and Baier, H. Algorithm configuration in sequen- tial decision- meaiii. In International Conference on the Integration of Constraint Programming, Artificial Intelli- gence, and Operations Research, pp. 86-102. Springer, 2025.
Huang, Y., Li, W., Tian, F., and Meng. X. A fitness land- scape ruggedness multiobjective differential evolution algorithm with a reinforcement learning strategy. Applied Soft Computing, 96: 106693, 2020.
Biedenkapp, A., Bozkurt, H. F., Eimer, T., Hutter, F., and Lindauer, M. Dynamic algorithm configuration: Foun- dation of new meta-algorithmie framework. In ECAI 2020, pp. 427-434. IOS Press, 2020.
Karafotias, G., Hoogendoorn, M., and Eiben, Á. E. Pa- rameter control in evolutionary algorithms: Trends and challenges. IEEE Transactions Evolutionary Compu- tation, 19(2):167-187, 2014.
Biedenkapp, A., Speck, D., Sievers, S., Hutter, F., Lindauer, M., and Seipp, J. Learning domain-independent policies for open list selection. 2022.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: I (609002900) 2016.
Birgin, E. G., Feofiloff, P., Fernandes, C. G., De Melo, E. L., Oshiro, M. T., and Ronconi, D. P. A milp model for extended version of the flexible job shop problem. Optimization Letters, 8: 8:1417-1431, 2014.
Lessmann, S., Caserta, M., and Arango, I. M. Tuning meta- heuristics: A data mining based approach for particle swarm optimization. Expert Systems with Applications, 2011.
Biswas, S., Saha, D., De, S., Cobb, A. D., Das, S., and Jalaian, B. A. Improving differential evolution through bayesian hyperparameter optimization. In 202/ IEEE Congress on Evolutionary Computation (CEC), pp. 832- 840. IEEE, 2021.
18(10):12226-122
Lin, X., Yang, Z.,, and Zhang, Q. Pareto set learning for neural multi-objective combinatorial optimization. arXiv preprint arXiv:2203.15388 2022.
Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp. A., Deng, D., Benjamins, C., Ruhkopf. T., Sass, R., and Hutter, F. Smac3: A versatile bayesian optimization package for hyperparameter optimization. J. Mach. Learn. Res., 23(54):1-9, 2022.
Centeno-Telleria M., Zulueta, E., Germandez-Gamiz U., Teso-Fz-Betood D., and Teso-Fz-Betoño, A. Differential evolution optimal parameters tuning with artificial neural network. Mathematics, 944):227 2021.
Chen, R., Yang, B., Li, S., and Wang. S. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Computers & In- dustrial Engineering, 149:106778, 2020.
López Lóāez-Ibáñez, M., Dubois-Lacoste J., Cáceres, L. P., Bi- rattari, M., and Stützle, T. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43 58, 2016.
10

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Ma, Z.,, Guo, H., Gong, Y.J., Zhang, J., and Tan, K. C. To- ward automated algorithm design: A survey and practical guide to meta-black-bol boxpoooiooooooooiittioooo arXiv preprint arXiv:2411.00623 2024.
Speck, D., Biedenkapp, A., Hutter, F., Mattmüülle,, R., and Lindauer, M. Learning heuristic selection with dynamic algorithm configuration. In Proceedings of the Interna- tional Conference on Automated Plamning and Schedul- ing, volume 31, pp. 597-605, 2021.
Michalewicz, Z.., Fogel, D. B., and Bèack, T. Evolutionary Computation. Vol. 2, Advanced Algorithms and Operators. Taylor& & Francis, 2000.
Sun, G., Xu, G., and Jiang, N. A simple differential evolu- tion with time-varying strategy for continuous optimiza- tion. Soft Computing, 24(4):2727-27) 2020.
Quevedo, J., Abdelatti, M., Imani, F., and Sodhi, M. Using reinforcement learning for tuning genetic algorithms. In Proceedings of the Genetic and Evolutionary Computa- tion Conference Companion, pp. 1503-1507, 2021.
Sun, J., Liu, X., Bäck, T., and Xu, Z. Learning adaptive differential evolution algorithm from optimization experi- ences by policy gradient. IEEE Transactions on Evolu- tionary Computation, 25(4))666-668) 680, 2021.
Reijnen, R., Zhang, Y., Bukhsh, Z., and Guzek, M. Deep reinforcement learning for adaptive parameter control in differential evolution for multi-objective optimization. In 2022 IEEE Symposium Series on Computational Intelli- gence (SSCI), pp. 114-811.17 JEEE, 2022.
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zam- baldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint 2017.
Reijnen, R., van Straaten, K., Bukhsh, Z., and Zhang, Y. Job shop scheduling benchmark: Environments and instances for learning and non-learning methods. arXiv preprint arXiv:2308. 12794, 2023a.
Tamssaouet, K., Dauzère-Pérés. S., Knopp. S., Bitar, A.. and Yugma, C. Multiobjective optimization for complex flexible job-shop scheduling problems. European Journal of Operational Research, 296(():87-100, 2022.
Reijnen, R., Zhang, Y., Bukhsh, Z., and Guzek, M. Learn- ing to adapt genetic algorithms for multi-objective flex- ible job shop scheduling problems. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation, pp. 315-318, 2023b.
Tian, Y., Li, X., Ma, H.. Zhang, X., Tan, K. C., and Jin. Y. Deep reinforcement learning based adaptive operator selection for evolutionary multi-objective optimization. IEEE Transactions on Emerging Topics in Computational Intelligence, 7(4): 2022.
Reijnen, R., Zhang, Y., Lau, H. C., and Bukhsh, Z. On- line control of adaptive large neighborhood search us- ing deep reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 34, pp. 475-483, 2024.
Xue, K., Xu, J., Yuan, L.,, Li, M., Qian, C.,, Zhang, Z.., and Yu, Y. Multi-agent dynamic algorithm configuration. Advances in Neural Information Processing Systems, 35: 20147-20161, 2022.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXi::1707.063447 2017.
Yang. X., Wang, R., and Li, K. Meta-black-box optimiza- tion for evolutionary algorithms: Review and perspective. Available at SSRN 4956956.
Shala, G., Biedenkapp. A., Awad, N., Adriaensen, S., Lin- dauer, M., and Hutter, F. Learning step-size adaptation in ema-es. In Parallel Problem Solving from Nature-PPSS PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part I 16, pp. 691-706. Springer, 2020.
Zhang, G., Gao, L., and Shi, Y. An effective genetic algo- rithm for the flexible job-shop scheduling problem. Ex- pert Systems with Applications, 38(4):3563-3573, 2011.
Zhou, A., Qu, B.-Y., Li, H.,, Zhao, s.-Z., Suganthan, P. N., and Zhang, Q. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and evolutionary computation, 1(1): 49, 2011.
Sharma, M., Komninos, A., López-Ibáñezz M., and Kazakov, D. Deep reinforcement learning based parameter control in differential evolution. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 709-717, 2019.
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li. C., and Sun, M. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
Song, W., Chen, X., Li, Q., and Cao, Z. Flexible job-shop scheduling via graph neural network and deep reinforce- ment learning. IEEE Transactions on Industrial Informat- ics, 1900) 2022.
Zitzler, F. and Thiele, I.. Multiobjective optimization using evolutionary algorithms- comparative case study. In International conference on parallel problem solvingfrom nature, pp. 292-301. Springer, 1998.

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
A. Test problem configurations
The Flexible Job Shop Scheduling Problem (FJSP) a popular scheduling problem where multiple jobs, each composed of several operations that must be completed in a specific order, must be scheduled to a set of machines. The problem contains set of n independent jobs J J2..., J and m independent machines M {M1, ........ Jm which together for X m Flexible Job Shop Scheduling Problem (FJSP). Each job Jj consists operations Oig. where OL represents the j-th operation of the i-th job. These operations must be executed in sequence, meaning Oz.++1 may only start after Oi, is completed. The processing time for operation Oi, on machine M& is denoted as fr and is known in advance. Each machine Mj can process only one operation at a time, and operations cannot be interrupted (no preemption). The start and completion times for operation Os.5 are denoted as St and Ct,y respectively, while O₃ is the set of operations assigned to on machine Mg.
This work focuses on five key minimization objectives commonly used in scheduling:
Makespan: The total time required to complete all jobs, represented as Caax = max;=1..... Oz.-
Balance Workload: The disparity in workload distribution across machines, represented as What W max where Wmin mink==,...,m
W min-
EisJeo, k.
Average flowtime: The average time duration jobs take from start to completion Favg = 1/2 Ei= Si,nra)-
Total Workload: The cumulative sum of processing times for all jobs, defined as Wiwl = Σn E(i)Eo, t..jkk
Maximum flowtime: Denoting the longest time any job spends in the system from start to completion, defined as Fiax = max; (C,,a. Si,irs).
The Capacitated Vehicle Routing Problem (CVRP) is concerned with a fleet of vehicles that must deliver goods from central depot to a set of customer locations while satisfying capacity constraints. The problem contains a set of customer locations C' {C1, C2...... C. a depot location Co. and m identical vehicles. Each location C2 has demand 4s representing the quantity of goods that need to be delivered to that particular customer. Each vehicle has a capacity of Q, representing the maximum total demand it can serve in a single route. Each vehicle k can serve a demand of E Qe x yik < Q, where yis is a binary decision variable indicating whether vehicle k serves customer i. The distance matrix D is defined as dıy. containing the distances between all pairs of locations, including customer locations and the depot, encapsulating the travel costs or distances associated with moving from one location to another.
The objectives considered in this work are to minimize the total distance traveled by all vehicles and the longest route:
Total Travel Distance: Dioial = Ex= Li=1 2===1 di x Tisk
Longest Route:
Druxx = max x=1
n Ej= dij x Tijk
B. Multi-Objective Algorithms for MOCO
NSGA-II for FJSP. To assess the efficacy of the proposed approach for FJSP, devise multi-objective Genetic Algorithm (GA) formulation inspired by Zhang et al. (2011) and following the implementation of (Reijnen et al., 2023a). The solutions entail two integral components: Machine Selection and Operation Sequence. The first allocates operations to machines, while the second establishes the precedence of operations on the designated machines. Illustrated in Figure 3, a value of '4' in the initial position of Machine Selection indicates the scheduling of operation O1,1 on the fourth machine alternative. Subsequently, the Operation Sequence component arranges this operation as second, after O2.1-
The population is initialized using Global, Local, and Random Methods. Global Method assigns operations to machines sequentially, minimizing the total processing times of individual machines. Local Method minimizes the max machine processing times for individual jobs. Random Method allocates operations to machines randomly. The Operation Sequence is initialized randomly for all methods. Crossover is applied to the Machine Selection component using two-point and uniform crossover while precedence-preserving order-basee crossover (POX) is applied to the Operation Sequence component. POX preserves relative scheduling positions for a randomly selected set of jobs and reschedules the remaining operations according to the other crossovered individual solution. We generate 60% of the initial population using Global Method,
12

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
Machine Selection
Ope ation Sequence
Chremesomne
3
2
1
Operation
011
012
Oai
O2e
O2s
O2s
011
012
O2a
O23
Figure 3: Chromosome Representation FISP MOGA (Zhang et al., 2011)
30% using Local Method, and 10% using Random Method. Machine Selection crossovers are in 50% two-point and 50% uniform crossover. To solve the multi-objective FJSP variant using the GA formulation from Zhang et al. (2011), we employ Non-dominated Sorting Genetic Algorithm-II (NSGA-II) for selection (Deb et al., 2002).
NSGA-II for CVRP. Subsequently, we apply multi-objective Genetic Algorithm (GA) formulation to assess the efficacy of the proposed approach for CVRP. The solutions are initialized with random routes, where each solution is represented as a list of values corresponding to the sequence in which customers are visited in the CVRP.
The selected parents undergo crossover and mutation to produce offspring, using ordered crossover and shuffle mutation; crossing over two segments from two selected parent solutions, and randomly swapping elements within solutions with given probability. The next generation is formed by selecting individuals from the combined population based on their rank (front) and crowding distance. The algorithm prioritizes individuals from lower fronts and those with higher crowding distances to ensure a diverse and high-quality population. Non-dominated Sorting Genetic Algorithm-1 (NSGA-ID) is applied for the selection (Deb et al., 2002).
MOPSO for CVRP.
We define a Multi-Ohjective Particle Swarm Optimization (MOPSO) algorithm for the Capacitated Vehicle Routing Problem (CVRP). In this algorithm, solutions (particles) are initialized with random routes, represented as a list of random values where each value corresponds a customer in the CVRP. Each partiele also has associated velocities that represent changes in these routes. The initial fitness values for each particle are calculated by sorting the customers based on the values in the particle's ' position to determine the routes. Each particle's personal best solution is recorded, and all the best-found solutions are stored in separate list.
In each generation of the search, the positions and velocities of the particles are updated based on their personal best and a global best chosen from the Pareto front (randomly selected when multiple best solutions are available). The velocity update formula incorporates cognitive coefficients (ø1), social coefficients (Φ2), and an inertia weight. Initially, random coefficients (ul and u2) are generated for each particle dimension to balance exploration and exploitation. The velocity update consists of two components: one influenced by the particle's 's personal best and the other by the global best from the Pareto front. The velocity for each particle dimension is calculated using these components, scaled by the respective random coefficients and adjusted by the inertia weight. The updated velocity is clamped within predefined minimum (min) and maximum (max) bounds to remain within valid bounds. The particle's new position is determined by adding the updated velocity to the current position. Finally, each position is clamped to remain within valid bounds, typically between and 1, ensuring the particle stays within the feasible solution space.
After the update, the fitness of the particles is evaluated. The particles' personal bests and the list of best solutions are updated using non-dominated sorting to retrieve Pareto-optimal solutions. A selection mechanism based on Pareto dominance (using NSGA-II) is applied to maintain a diverse and optimal set of solutions in the population. For this work, we configure the vanilla MOPSO algorithm for CVRP with the following parameters: social and cognitive coefficients are configured as 2.0, an inertia weight of 0.9, and we use a population size of 50 particles for 50 generations. GS-MODAC is configured to tune the social and cognitive coefficients between and and the inertia weight factor between 0.6 and 0.9.
C. Alternative Performance Metrics
We further evaluate performances using additional metrics commonly employed in multi-objective optimization research: Inverted Generational Distance (IGD), Inverted Generational Distance Plus (IGD+), and the number of non-dominated solutions. These results are gathered using the same setup as used in the paper for the J25m5 scheduling problem with 2,3 and objectives. The results, shown in Table 5, highlight the effectiveness of GS-MODAC, as it finds a significantly higher number of "best" solutions (max) and achieves lower IGD+ values.
13

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
In terms of IGD, GS-MODAC outperforms the baseline methods in the experiments with more objectives. it important note that while IGD provides valuable insights into the proximity of solutions to the Pareto front, it is sensitive the distribution of solutions and is more subject to outliers. In contrast, IGD+ is less sensitive to these factors, making it more reliable measure to evaluate the overall quality and diversity of solutions. Therefore, the consistently lower IGD+ values across multiple objectives achieved by GS-MODAC highlight its ability to converge to the true Pareto front while maintaining a diverse set of hugh-quality solutions.
Table Additional Performance Metries: Inverted Generational Distance (IGD), Inverted Generation Distance Plus (IGD+), and nr. of non-dominated solutions.
Bi-FJSP- -FFJSp
IGD
IGD+
non non-dominated solutions
mean
min
Std
mcan
min
std
mean
max
std
NSGA-II
19.07
8.47
11.49
15.79
4.05
12.25
5.06
8.78
2.11
irace
15.66
7.23
8.41
11.23
2.52
9.10
4.92
8.07
1.94
SMAC3
15.13
6.99
7.75
15.13
6.99
7.75
4.99
8.26
1.98
MODDC
15.77
7.41
9.10
9.82
1.25
10.10
6,81
20.69
5,80
Tri-FISP 2.555m
IGD
IGD+
non not-dominated solutions
mean
min
std
mean
min
std
mean
max
std
NSGA-II
22.20
15.77
6.00
18.09
10.11
6.78
36.29
54.10
10.18
irace
19.23
13.44
6.09
12.29
5.36
6.83
35.30
51.29
10.06
SMAC3
19.19
13.07
6.13
11.24
3.83
7.02
35.25
52.95
9.81
GS GS-MODAC
20.63
13.86
6.77
8.40
2.46
6.79
36.64
54.83
11.07
Penta-FJSP
25j5m
IGD
IGD+
non-dominated solutions
mean
min
std
mean
min
std
mean
max
std
NSGA-II
28.58
23.42
4.19
21.18
14.18
4.70
172.20
223.14
32,46
irace
23.97
19.88
4.09
13.67
7.38
4.78
203.94
263.34
40.22
SMAC3
26.10
21.16
4.46
17.17
9.91
5.22
185.93
243.54
35.94
GS-MODAC
23.82
19.08
5,06
8.71
3.25
5.03
231.13
311.21
52.14
D. Alternative MOEA results
We show another instantiation of the proposed GS-MODAC method, where the DRL agent dynamically configures the parameters of multi-objective PSO (MOPSO) algorithm. Table 6 shows GS-MODAC can effectively improve the performance of MOPSO, achieving better results on solving the two-objective CVRP problems with sizes 20, 50, and 100.
Table 6: Performance comparison of the proposed method for dynamic algorithm configuration of Multi-Objective Particle Swarm Optimization (MOPSO) Algorithm.
Bi-CVRP- 20
Bi-CVRP- 50
Bi-CVRE 100
Method
mean
max
std
mean
Std
mcan
std
MOPSO
3.21 10 30 3.47
5.
6.90x 10S
5.65
8.67x10'
9.
5.87
GS-MODAC
10'
3.77x10' 3.20
6.27x10'
8.08x10'
9.73
100
1.46x
2.42x10'
E. Ablation study
An ablation study was conducted to account for the performance of the different components of the proposed method. a first ablation, we trained GS-MODAC without the additional feature vector that contains the normalized remaining search budget. Table 7 shows that, without this vector, the performance of the proposed method decreased average with 0.8%, 3.2%. and 1.7% respectively, for 2, 3, and 5 objectives to solve the scheduling problem with 25j5m instances. Another ablation was conducted with only one GCN layer. This resulted in an average performance decrease of 1.7%, 3.2%, and 3.4% for 2, 3, and 5 objectives.
In addition, we adapt GS-MODAC for the Penta-FISP 25j5m problem by replacing the GCN layers with Transformers and Graph Attention Networks (GAT). The results presented Table 8 indicate that Transformers are a viable alternative, with
14

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Obeective Combinatorial Optimization
Table 7: Ablation study, comparing GS-MODAC configured without additional feature vector and with one configured GCN layer.
Bi-FJSP
25j5m
Tri-FISP 25j5m
Penta-FISP
25j5m
mcan
max
std
mean
max
std
mcan
max
std
MADAC
9.24x10
9.72x10* 3.09x10* 2.09x10'
2.20x10' 1.7x11
5.1x10
5.74x10 5.01x10
GS-MODAC (No feature)
9.47x10
9.92x10
4.21x10
2.07x10²
2.21x10'
1.10x10"
5,53x1012
6.02x10 3.42x1041
GS-MODAC (One GCN)
9.38x10*
9.88x10*
4.87x10
2.07x10
2.19x10"
1.02X10
5.49x10
5.98x10²2
3.37x10"
GS-MODAC
9.54x10*
10.0x10*
4.40x10*
2.14x10"
2.27x10" 1.09x10
5.62x10'2
6.07x10'² 3,20x10
an average performance of only 0.3% lower than GCN and its best-found solutions only 0.5% worse. The performance difference of GS-MODAC configured with GAT layers is more substantial, with an average degradation of 1.4%.
Table Comparison of different network architectures (GCN, Transformer, GAT) for GS-MODAC.
Penta-FISP 25j5m
mean
max
std
GCN
5.62 10
6.07 10
3.20 10
transformer
5.61 x
6.04x10
3.60x10'
GAT
5.54x11'²
6,04x10'2
3
F. Complexity Analysis
We profiled GS-MODAC to assess its computational complexity, focusing on graph state configuration and policy network inference. The results show that the actor's inference time is 0.13 seconds, and the state extraction takes 0.2 seconds, together accounting for 2.0% of the total time for the smallest scheduling problem instances. For larger problems, this proportion decreases significantly as solution evaluations dominate the computation. Despite slight overhead, its substantial performance gains justify the minimal additional cost of GS-MODAC.
Table 9: Breakdown of GS-MODAC's computational components, highlighting total inference time, state configuration, and policy inference time.
Bi- FJSP 5j5m
Penta-FJSP 5j5m Bi-FISP 25j5m
Penta-FISP 25j5m
Total Inference Time
15.09s
15.46s
305s
302s
Total State Configuration Time
0.18s
0.21s
0.23s
0.22s
Total Policy Inference Time
0.12s
0. 12s
0.14s
0.13s
G. Comparison to End-to-End method P-MOCO
We compare GS-MODAC with P-MOCO (Lin et al., 2022), a commonly used learning-based approach for Pareto set learning. is important to note that P-MOCO features specialized network structure for simple TSP and CVRP and cannot solve scheduling problems (such as FISP), nor work for alternative, non-distance-bart objectives. Hence, we compare both methods solve the CVRP problem with 2 objectives. We train P-MOCO according the details provided in Lin et al. of instances of size 100. We evaluate its performance based the setup
(2022) and train both methods the described in Section 4, utilizing the same instances and reference points recorded in the publication. The results, presented in Table 10, compare the best obtained HV values, aligned with the experimental setup of Lin et al. (2022).
Table 10: Comparison of Hypervolume (HV) values achieved by NSGA-II, and by P-MOCO and AS-MODAC (trained on size 100) for Bi-CVRP instances of varying sizes.
Bi-CVRP 20
Bi-CVRP
Bi-CVRP 100
NSGA-II
42.86
151.24
363.87
P-MOCO
34.71
438.06 152.87
152.83
GS MODAC
45.18
366.63
15

---

Graph-Supported Dynamic Algorithm Configuration for Multi-Obeective Combinatorial Optimization
The results indicate that P-MOCO performs better than GS-MODAC when trained and tested instances of size 100, which expected since P-MOCO learns policies tailored to specific instances. However, in terms of generalizability, P-MOCO is inferior to GS-MODAC, seen in the performances on Bi-CVRP20 and Bi-CVRP50. This indicates that GS-MODAC has significantly better generalization capability than P-MOCO, which is somewhat overfitted to specific size used in training. Additionally, we also observe that GS-MODAC outperforms NSGA-II when generalizing to different sizes.
To further assess robustness, we conducted an additional comparison between GS-MODAC and P-MOCO, Both methods were trained on problem instances of size 100, and tested on problem instances generated according to normal distribution with mean of 0.3 and standard deviation 0.1, with 5% outliers (note: training instances are generated with uniform distributions). The results demonstrate that GS-MODAC consistently outperforms P-MOCO across all sizes, indicating its superior generalization capability. Unlike P-MOCO, which tends to overfit not only to specific problem size but also to the distribution of training instances, GS-MODAC shows robust performance across different instance distributions. Additionally, GS-MODAC keeps surpassing NSGA-II in the generalization to various instance distributions and sizes.
Table 11: Performances in terms of Hypervolume (HV) on Bi-CVRP instances with different distributions and outliers. compared to the training instances.
Bi-CVRP 20
Bi-CVRP 50
Bi-CVRP 100
NSGA-II
59.34
192.64
455.80
P-MOCO
51.05
186.35
454.76
GS-MODAC
59.55
194.47
458.46
16


Reviews:
[{"review_id": "NyUD4BHgrc", "reviewer": "Reviewer_g4y9", "summary": "This paper presents a DRL approach for dynamically configuring evolutionary algorithms in multi-objective combinatorial optimization. The process is modeled as a Markov decision process, where solution convergence is represented as a graph, and a GNN enhances state representation. Experimental results show that the proposed method outperforms traditional and DRL-based approaches in efficacy and adaptability across objective numbers.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's effort and insightful feedback. Here are our detailed responses.\n\n**Insufficient survey of DRL methods for assisting MOEAs**\n\nTo the best of our knowledge, our literature review (Section 2, L137) includes most existing works that propose frameworks for controlling multi-objective evolutionary algorithms in a way that generalizes across different algorithms and problems. In recent surveys (Yang et al., 2024; Ma et al., 2024) that were cited in our paper, most reinforcement learning-based multi-objective approaches are designed for specific evolutionary algorithms (mainly differential evolution), aim to configure target weight adjustments in MOEA/D, or focus solely on operator selection. Given this, we have chosen to compare our approach with MADAC, which we identify as the most relevant state-of-the-art algorithm, and is the closest work to our proposed method. \n\nFollowing the reviewer's suggestion, we have cited another latest survey paper (Song et al., 2024) to refer interested readers to learn the related work on reinforcement learning-assisted evolutionary algorithms for (multi-objective) optimization. We appreciate any additional references recommended by the reviewer and would be happy to incorporate them into our paper.\n\nReference:\nSong, Y., Wu, Y., Guo, Y., Yan, R., Suganthan, P. N., Zhang, Y., ... & Feng, Q. (2024). Reinforcement learning-assisted evolutionary algorithm: A survey and research opportunities. Swarm and Evolutionary Computation, 86, 101517.\n\n**Reference point influence**\n\nWe acknowledge that the choice of the reference point can influence absolute hypervolume values. However, our approach relies on the relative improvement in hypervolume rather than its absolute magnitude. As long as the reference point allows for meaningful differentiation between better and worse populations during the optimization process, the reward function remains effective. Besides this, in order to address variations in absolute hypervolume values across instances, we normalize the reward signal using the reference point and an ideal point. This normalization ensures a stable and consistent reward signal throughout the optimization process and across different training instances.\n\n\n**State space metric calculations**\n\nThe graph serves as a representation of the solutions in the current population on the multiple objective planes. This approach involves interconnecting normalized objective points in the different Pareto fronts to create a structured visualization of the solution space. We have specified the calculations of the different objectives in Appendix A. For normalization, we use regular min-max normalization, given the bounds of the objectives known at a certain iteration (as described in L215). Pareto fronts are identified using non-dominated sorting, following Definition 3 to identify Pareto fronts. Following your suggestion, we will extend the calculation details in our paper. We will also release the implementation for better understanding.\n\n**State Configuration in Figure 1**\n\nBased on the above comments of the reviewer, we will provide more explanation of the state-space configuration in the caption of the figure to make it more intuitive. Additionally, we agree that this work is more towards the DRL domain and we will enhance the DRL agent part in the diagram to make it more clearly presented than the evolutionary algorithm flow. We will centralize the DRL agent, provide more details about it, and simplify the evolutionary algorithm.\n\n**Points for normalization**\n\nThe points used for the normalization of the objective function are the minimum and maximum values of each objective known at a given iteration. These bounds are recalculated at each step, ensuring that they reflect the changes in the state of the population. As such, we keep track of the entire objective space by keeping the worst objective values (typically present in the first generation) and updating the minimum values when better objective values are obtained. As noted above, we will clarify this in the paper.\n\n**Algorithmic Fairness**\n\nTo ensure a fair comparison, we set algorithmic parameters, such as population size and computational budget, to be identical across all compared methods. Additionally, to maintain fairness in tuning and training time, we provided the automated algorithm configuration methods with a similar number of runs (e.g., 2000 for FJSP) as the proposed GS-MODAC method. Furthermore, the MODAC baseline method was trained until full convergence to ensure that its full potential was realized, taking more training time than the proposed method on the FJSP problem variants.", "claims_and_evidence": "No, the paper provides an insufficient survey of reinforcement learning-assisted evolutionary algorithms for multi-objective combinatorial optimization. Review papers in this field indicate the existence of such approaches, yet they are not discussed in the paper. Consequently, the absence of comparisons with state-of-the-art algorithms undermines the evaluation of the experimental study.", "methods_and_evaluation_criteria": "Yes, the multi-objective Flexible Job Shop Scheduling Problem (FJSP) and the Capacitated Vehicle Routing Problem (CVRP) are used to evaluate the effectiveness of the proposed method. As classic multi-objective combinatorial optimization problems, they serve as meaningful benchmarks for assessing the algorithm’s performance.", "theoretical_claims": "Yes, this paper is primarily based on empirical study and does not include rigorous mathematical proofs.", "experimental_designs_or_analyses": "Yes, there is one point I am unclear about. According to the experimental setup in Chapter 4, the proposed method requires longer training times than the baseline. How is the fairness of the algorithm comparison ensured under these circumstances?", "relation_to_broader_scientific_literature": "This paper models the dynamic algorithm configuration of a multi-objective evolutionary algorithm as a Markov decision process. A graph represents the convergence of solutions in the objective space, and a GNN learns their embeddings to enhance the state representation.", "essential_references_not_discussed": "The literature on reinforcement learning-assisted evolutionary algorithms for multi-objective combinatorial optimization is not discussed.", "other_strengths_and_weaknesses": "1. The reward function is highly dependent on the hypervolume calculation and relies on the hypervolume of the previously observed population. However, the hypervolume value is strongly influenced by the reference point, and the results can vary significantly depending on the reference point. Moreover, as the population evolves dynamically, the reference point set based on the initial population may no longer be appropriate. This raises concerns about the effectiveness of the proposed method.\n2. The metrics used to define the states in the MDP are specified, but their detailed calculations are not clearly explained.", "other_comments_or_suggestions": "1. The state configuration in Figure 1 is not intuitive. Additionally, the DRL agent should be depicted more clearly in the diagram compared to the conventional flow of evolutionary algorithms.\n2. \"NSGA-ii\" should be corrected to \"NSGA-II.\"", "questions_for_authors": "1. Which points are used for the normalization of the objective function? How does this calculation account for changes in the population?  \n2. How is fairness maintained in the experiments when comparing different types of algorithms?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hI3myt1ktR", "reviewer": "Reviewer_QmER", "summary": "This paper composed a graph-neural network (GNN) based deep reinforcement learning method to dynamically optimize the configurations of multi-objective combinatory optimization problems. The proposed model takes the normalized muti objectives as input and uses the GNN to learn to iteratively involve the algorithm configurations. The authors evaluated the model's performance on both scheduling and routing problems.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these insightful points. Here are our detailed responses.\n\n**Motivation behind the graph structure** \n\nThe motivation behind adopting a graph representation is to eliminate the need for manual state space design, a process known to be cumbersome and suboptimal. In this context, we use a graph structure to dynamically represent the relationships between solutions in the multi-objective optimization process. Specifically, the pair-wise embedding technique captures the relationships and distances between solutions, which allows the model to learn richer and more complex features of the objective space over time. We draw inspiration from various metrics for convergence and diversity in multi-objective optimization, such as the number of elite solutions, spacing between solutions, and hypervolume. These metrics reflect how well the optimization process is progressing across multiple objective planes. By using a graph representation, we can naturally plot and interconnect solutions on the objective space plane, which intuitively enables the GCN to understand the relative position and status of each solution. \n\nResults in Table 8 indicate that GCN is most effective, probably due to its ability to effectively capture local structural dependencies of the objective space. However, transformers are an effective alternative, with average performance being only 0.3% worse than GCN and its best-found solutions only 0.5% worse. Please refer to our response to reviewer F2sV, where we performed an additional ablation to highlight the effect of interconnecting the different solutions in our graph representation.\n\n**Solver time and sampling Efficiency**\n\nWe agree that the optimization solver’s contribution to the overall running time is significant, a challenge common to all parameter tuning methods, whether static or dynamic. As demonstrated in Tables 2 and 3, GS-MODAC effectively generalizes to larger instances and more complex problem variants, which avoids the re-training/fine-tuning, and saves the computational time from the solver (and, consequently, training time). Furthermore, we show that GS-MODAC performs well across a variety of distributed problem instances, highlighting its ability to be trained once as a one-time investment. This enables the method to maintain strong performance on new problem configurations, including those not encountered during training, without the need for retraining.\n\n**MADAC training and running  time comparison**\n\nIn terms of inference time, we observe that MADAC takes 15.5s for Penta-FJSP (5j5m) and 305s for Penta-FJSP (25j5m), slightly longer than GS-MODAC (see Table 9). We will add this to Table 9 as a reference comparison. We have reported on the training time of MADAC in the “Training” subsection. GS-MODAC takes a little longer training time than MADAC on CVRP, since the latter (with its original training settings) converged quickly to sub-optimal policy. Instead, GS-MODAC can continuously improve the policy with more time. MADAC was trained until full convergence on the FJSP problem variants, taking more training time than the proposed method.\n\n**Inputs in the objective space**\n\nThe values used as node features in the graph consist solely of the objective values from the different solutions in the population. These values are normalized based on the best objective values obtained during the search and the worst observed values from the first generation of solutions. The nodes are interconnected to form a graph using Non-Dominated Sorting, which ranks them into different Pareto fronts. The first front consists of non-dominated solutions, while subsequent fronts contain solutions that are dominated by those in higher-ranked fronts. Nodes within the same front are interconnected with each other. The problem-specific calculations for obtaining objective values are detailed in Appendix A. The Non-Dominated Sorting is performed based on Definition 3. We will add the equation for this to the paper.\n\n**Source code release**\n\nWe provide our code in supplementary material and will indeed release our source code upon acceptance.\n\n**Minor points in Figure 1 and L724**\n\nThanks for noticing, we update the Figure and value accordingly.\n\n**Demanding**\n\nIn this context, \"demanding\" means that evolving toward the Pareto front becomes increasingly challenging or difficult as the search progresses. Early in the optimization process, improvements are relatively easy to achieve, but as the algorithm gets closer to the optimal Pareto front, making further progress requires (or demands) significantly more effort/computational costs.", "claims_and_evidence": "1. The key difference between the proposed method and previous works is that the proposed model uses a neural network to represent the objective space as embedding for optimization instead of manual feature engineering. However, in L206, in the left column, the details of mapping the objective space to graphs are not clearly presented. What values are exactly processed to convert the objective space to graphs? Without explaining this may hurt the claim of automation embedding.", "methods_and_evaluation_criteria": "1. As we know, the transformer is also a powerful tool to represent structured embeddings and complex structures. Even though in Table 8, the authors present that the GCN structure is experimentally superior to the transformer and GAT structure, there is no explanation and inspiring hint behind the choice of this neural network structure. This may limit the contribution to the community. I suggest that the authors discuss the reason why a graph structure with the pair-wise embedding technique is necessary to represent the objective space.", "theoretical_claims": "No theoretical proof in the paper.", "experimental_designs_or_analyses": "1. From Table 9, we can see that the optimization solver takes most of the running time, which means the solver will seriously limit the training time; as we know, reinforcement learning generally has low sampling efficiency. Considering the reported training time in the L283 right column, I would worry about the application value of this pipeline. Could authors also report the MADAC model's training/running time as a reference comparison?", "relation_to_broader_scientific_literature": "This work may inspire the CO community by using neural networks to optimize the heuristic solver's configurations.", "essential_references_not_discussed": "None from my side.", "other_strengths_and_weaknesses": "Strengths:\n1. The evaluation is sufficient and solid, including the ablation study for components and neural network structure and the generalization testing cross-size and type of problems. \n2. The paper is well-structured, and the logic is clear, making the paper easy to follow. \n\nWeaknesses\n1. L206, left column. What inputs are exactly in the objective space seems not to be clearly shown. Adding some equations to present the states seems to be beneficial. \n2. The community will benefit if authors could provide the source code for validating and following up on works.", "other_comments_or_suggestions": "1. [Minor] Figure 1. I think there should be a connection from the \"Problem Instance\" cell to the \" Algorithm \" cell. \n2. [Minor] L724. An extra space for the $0.3$%.", "questions_for_authors": "1. L214, right column. What does \"demanding\" mean here? As I understand, does this mean \"optimization demanding\"?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tmfvENwwEq", "reviewer": "Reviewer_F2Sv", "summary": "This work considers the problem of dynamically configuring the parameters of evolutionary algorithms for solving combinatorial optimization problems. It specifically focuses on multi-objective optimisation problems, in which there are multiple (and often conflicting) objective functions. Unlike previous methods that rely on hand-engineered features, the authors propose encoding the properties of currently found solutions as a graph, and using a graph neural network to learn the relevant features automatically. The method is compared with statically configured EA algorithms, a Bayesian optimisation approach, and a recent RL method, generally showing better performance.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful feedback.\n\n**Graph Configuration and Rationale**\n\nThe graph serves as a representation of the solutions in the current population on multiple objective planes. The values used as node features in the graph consist solely of the objective values from the different solutions in the population. These values are normalized based on the best objective values obtained during the search and the worst observed values from the first generation of solutions. The nodes are interconnected to form a graph with Non-Dominated Sorting, which ranks them into different Pareto fronts. Nodes within the same front are interconnected with each other. \n\nThe motivation behind the graph representation is to eliminate the need for manual state space design, a process known to be cumbersome and suboptimal. We expect that our method leverages the graph-based representations to learn similar (yet advanced) features dynamically during the optimization process to reflect the current state in the multiple objective planes. Therefore, we plot and interconnect solutions on the plane, which intuitively allows the GCN to understand the status of solutions and help configure the algorithm for better convergence and diversity. We will extend the explanation of the graph construction.\n\n**Pareto Fronts Identification**\n\nThe representation captures all solutions present in the population at a given iteration of the search. The graphs are constructed by identifying the Pareto fronts, which serve as structured layers of solutions based on their dominance relationships. To achieve this, we rely on Non-Dominated Sorting, a method that ranks solutions into different fronts. The first front consists of non-dominated solutions, while subsequent fronts contain solutions that are dominated by those in higher-ranked fronts.\n\n**DeepSets**\n\nSolutions within the same Pareto front are interconnected by edges, whereas no connections exist between different fronts, maintaining their distinct structure. We have conducted an ablation where we adapted our architecture to use a DeepSets approach, which excludes the edges and processes the nodes independently using shared MLPs. Results below show a significant decline in performance for DeepSets, highlighting the importance of the graph structure and the interdependencies between nodes for effective learning.\n\n||Bi-FJSP-25j5m|||\n|:-:|:-:|:-:|:-:|\n||mean|max|std|\n|MADAC|9.24*10^4|9.27*10^4|3.09*10^3|\n|GS-MODAC (No feature)|9.47*10^4|9.92*10^4 |4.21*10^3|\n|GS-MODAC (One GCN)|9.38*10^4|9.88*10^4|4.87*10^3|\n|GS-MODAC (DeepSets)|9.39*10^4|9.91*10^4|4.84*10^3|\n|GS-MODAC|9.54*10^4|10.0*10^4|4.40*10^3|\n\n**Hyperparameter Configuration**\n\nAlthough we applied MADAC to a different domain than in the original paper, we chose to use its default configuration because it has been shown to perform well across a wide range of objective spaces, including smooth and convex, disconnected, multimodal, and non-convex problems. This versatility, as highlighted in the original MADAC paper, supports our decision. Likewise, we use the default hyperparameters of the PPO algorithm when training the GS-MODAC method. By maintaining these default settings, we ensure a fair and consistent comparison, avoiding potential biases that could result from excessive tuning of either method. \n\n**Seeds setting training**\n\nIn our experiments, we trained multiple models (3) for each method for each problem configuration using different seeds. We observed that GS-MODAC consistently exhibited stable training performance across different seeds, reinforcing the robustness of our approach. In contrast, MADAC showed a larger variance in learning performance across different runs. Due to this instability, we selected the best-performing MADAC models. We will add this information to our final publication. Additionally, we trained separate models for each problem configuration, and these models consistently outperformed the baselines across different configurations. This also indicates that the stability of our method, rather than random performance.\n\n**Multi-Agents MADAC**\n\nMADAC involves multiple heterogeneous agents, each responsible for adjusting a specific type of parameter within an algorithm. Its action is the value of the parameter that should be adjusted. We will clarify this point in the definition of MADAC\n\n**Transitions and reward functions**\n\nWe formulate the DAC process as a contextual MDP (Biedenkapp et al., 2020). Here, the transition function models how the algorithm’s state evolves after an action is taken. For different problem instances, the algorithm might encounter different search landscapes, which means that the same parameter change could lead to different transitions depending on the instance at hand. Similarly, the reward function reflects the quality of the transition. Since different problem instances may require different configurations to optimize performance, the reward function must account for these differences.", "claims_and_evidence": "The claims in the abstract and introduction are supported by appropriate evidence in the paper text.", "methods_and_evaluation_criteria": "- My main criticism of the method is that the procedure for constructing the graph is not actually given. This should be specified precisely -- based on Figure 1, it involves some form of determining datapoints on the Pareto front, and allowing all pairwise connections between them.\n- There is only one Pareto front at the end of the optimisation process, but the graph representation seems to rely on several intermediate ones. It should be specified how/when these intermediate fronts are determined. \n- Following on from the above, there do not seem to be clear semantics associated with the use of a graph here. The edges in this graph may not have a meaningful representation (but this is difficult to say without knowing how the graph is constructed). In my opinion, to validate this, an ablation should be conducted that compares GNNs with DeepSets (another permutation invariant learning method), effectively excluding the edges from the feature learning process.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "- Default hyperparameters are used for the MADAC baseline, but it is applied to a different type of problem altogether than in the original paper. The hyperparameters of both the proposed method and MADAC should be tuned for the considered problems to make the comparison fair. An alternative explanation for the observed performance difference is that the hyperparameters of MADAC are wrongly chosen.\n- Multiple runs of the training loop: the training of the RL agent is itself a random process and should be repeated over multiple seeds. As far as I can tell (and the authors should clarify if  this is not so), the models for each problem setting are trained only once; then error bars are given over 10 runs of the base EA algorithm but keeping the same RL model. Again, an alternative explanation is that this one model happened to obtain better performance.", "relation_to_broader_scientific_literature": "If validated successfully, this represents a contribution to the literature of hybrid methods combining RL and metaheuristics as well as multi-objective optimization.", "essential_references_not_discussed": "To the best of my knowledge, all essential references in this area are discussed.", "other_strengths_and_weaknesses": "The paper in general is fairly well-organised and well-written.", "other_comments_or_suggestions": "- Section 2: it is worth mentioning why MADAC is multi-agent: what is each of the agents responsible for?\n- Section 3: it is worth discussing in more detail why transitions and reward functions differ for each problem instance in the MDP.", "questions_for_authors": "Key questions to address include:\n\n1. The rationale for using a graph representation and the detailed procedure for constructing it.\n2. The potential issues that I raised around the evaluation methodology.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fOmF0sZSwA", "reviewer": "Reviewer_qYda", "summary": "The work proposes an extension to the dynamic algorithm configuration (DAC) framework. Particularly, the work proposes to use graph convolutional neural networks to learn embeddings of Pareto fronts such that multi-objective combinatorial optimization algorithms are dynamically optimized while proposing novel solution candidates. The work evaluates the proposed GS-MODAC approach on two different problem domains with various different problem sets and shows that the approach is capable of outperforming classical, static algorithm configuration as well as a multi-agent based dynamic algorithm configuration approach.\n\n## update after rebuttal\nI have read all reviews and am keeping my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for their thoughtful review and helpful suggestions. We have provided our responses to the comments below.\n\n**Statement general DAC**\n\nOur intention was to convey that DRL-based DAC approaches are primarily applied to single-objective (continuous) optimization problems. We will clarify this statement in the final version to prevent any misunderstanding. Additionally, we will include references to Speck et al. (2021, 2022) to highlight the capability of DAC methods to outperform the best static configurators in planning domains.\n\n**DAC aims statement**\n\nThanks for this remark. We will update the statement to reflect that DAC aims to better balance exploration and exploitation by dynamically reconfiguring parameters throughout the optimization process.\n\n**Reward scale is instance-invariant**\n\nBy incorporating normalization of the search space, we ensure that a similar reward signal can be obtained for different instances included in the training. As such, we avoid the training to overfit on instances where a larger difference in the hypervolume could be more easily obtained. We agree with the reviewer that instance-invariant is a better word choice to describe this and will update this in the final version.\n\n**Objectives SMAC and irace**\n\nIrace and SMAC are configured to optimize for hypervolume, which we consider as the main objective for our multi-objective optimization problems. To ensure clarity, we will explicitly state this in the baseline descriptions.\n\n**Cross-domain generalizability**\n\nWe indeed test the ability of trained models to generalize to different problem configurations (larger problem size, more constraints, and different objectives) from the same problem domain. We choose this to account for the problem-specific operators that are used in the algorithmic setups that the trained model learned to dynamically configure. We believe that we make no cross-domain generalization claims and will ensure this again in the final version.\n\n**Random Configuration baseline**\n\nThanks for this remark. We will include this baseline in the tables to better illustrate its comparative performance.\n\n**RQ4 Clarification**\n\nIn RQ4, we investigate the extent to which a policy trained on one set of objectives (trained to optimize objectives A and B) can generalize to a different set of objectives (C and D). Specifically, objectives A and B correspond to Makespan and Balanced Workload, while objectives C and D refer to the Average and Maximum Workloads of machines in this experiment. Results demonstrate that models can be transferred to the problem configured with different objectives configurations, finding solutions of similar or better quality than the configured baselines. To improve clarity, we will update the caption for GS-MODAC in Table 4 to explicitly indicate that it was trained on different objectives. Additionally, we will revise the text to ensure a clearer explanation of what this experiment aims to assess.\n\n**Appendix reference**\n\nThanks for noticing. We will update the reference in the final version.\n\n**References**\n\nThank you for providing these relevant references. We appreciate the insights from Speck et al. (2021, 2022), Shala et al. (2020), and Bordne et al. (2024) regarding the generalization capabilities of domain-dependent DAC policies. We will incorporate these works into our literature review.\n\n**Methods applicability**\n\nThe reviewer correctly remarks that the proposed method can also be applied to a wide variety of multi-objective problems outside of the combinatorial optimization domain. In future work, we would like to discover how we can use graph embeddings (and GNNs) from the proposed method in single-objective problem settings (e.g., in the setup of Bordne et al.).\n\n**DACBenchmark**\n\nWe plan to release our source code upon acceptance, and will contact the authors of DACbenchmark to see how to integrate with them.", "claims_and_evidence": "The claimed contributions are mostly convincing and seem well supported by the empirical evidence provided in the main part of the paper and are further complemented by analysis and experiments in the appendix.\nSome wordings seem questionable to me.\n* Line 025-031 (right side) the statement reads as if \"general DAC\" approaches are primarily limited to multi-objective continuous optimization. However, this is not the case as other works show that RL-based DAC can be applied in a variety of problem domains (see, e.g. the works by Speck et al. [2021](https://arxiv.org/abs/2006.08246) or [2022](https://andrebiedenkapp.github.io/assets/pdf/paper/22-PRL-DAC4AIPlanning.pdf) highlight that DAC can theoretically outperform the best static configurator and selector while providing additional empirical evidence that is capable of beating a static oracle). \n* Line 101-104 (right side) \"Unlike static configurations, DAC aims to balance exploration and exploitatoin, increasing the likelihood of finding high-quality solutions.\" This statement is only partially true. A static configuration can contain hyperparameters of a schedule that influences how the underlying algorithm behaves. A simple example of this are the exponential decay of learning-rates in DL which are often configured via static configurations but dynamically influence the learning behaviour of the target task.\n\nThe claim of the reward function being instance-invariant does not seem well supported to me. While I agree that the reward scale is instance-invariant due to the used normalization method, the reward space as such is still instance dependent.\nLastly, from the text it is not clear to me what the optimization objectives of SMAC and irace are. I believe that it is necessary to have a statement to show that SMAC and irace opimize the same normalized objective to highlight that the GS-MODAC approach truly outperforms such strong static baselines.\n\nA small-ish nitpick about the claims: The work discusses generalization to unseen instances, though they are always part of the same domain. Thus the claims about generalization might be reframed from this viewpoint. There can be made no claims about cross-domain generalization, though the work definitely shows that the learned policies can handle a diverse set of problems from the same domain.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the application at hand. Since, to the best of my knowledge, the standard DACBenchmark does not have any relevant benchmarks, it would be good to see that the authors make their benchmark publicly available (potentially as part of DACBench) to facilitate future reproducibility and additional work in this direction.\n\nAnother small nitpick: A random configuration policy as baseline would have helped to highlight how meaningful dynamic configuration actually is in the proposed problem setting as the work otherwise does not provide insights on the learned configuration policies.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "See my remarks in \"Claims And Evidence\".\nAdditionally, in RQ4 I do not understand the experimental setup and what is actually being investigated. Does the \"GS-MODAC model\" refer to the learned policy or the graph convolutional neural network. More explanation is needed to understand what we can learn from this experiment and what the results in Table 4 actually represent.", "relation_to_broader_scientific_literature": "The literature is mostly well covered, though some of the insights about generalizability of learned DAC policies should be better set into context with related DAC works. (See the next section)", "essential_references_not_discussed": "The works by Speck et al. [2021](https://arxiv.org/abs/2006.08246) & [2022](https://andrebiedenkapp.github.io/assets/pdf/paper/22-PRL-DAC4AIPlanning.pdf) that I also referred to earlier similarly showed that domain-dependent policies (i.e. DAC policies learned in a similar fashion to the work under review) can generalize fairly well to larger problem instances, though with some performance drop-off. Relatedly, Shala et al. [2020](https://ml.informatik.uni-freiburg.de/wp-content/uploads/papers/20-PPSN-LTO-CMA.pdf) showed that DAC policies can generalize to longer horizons, and larger problem dimensions, where the former seemed to be the more limiting factor. Further, the method used by Shala (i.e. Guided Policy Search) was specifically selected to be reward-scale invariant in-order to facilitate better generalizability (see the discussion in the appendix). Lastly, a work by Bordne et al. ([2024](https://arxiv.org/abs/2407.05789)) discussed how to exploit structure in the configuraiton space to facilitate better DAC policies. I believe this idea of exploring ways of exploting structure in DAC problems is related to the idea presented in this work, where structure in the state-space is exploited for better DAC policy learning.", "other_strengths_and_weaknesses": "The work provides a very elegant solution to the DAC problem and should be of high interest for the AutoML community, but also the RL community as the proposed setting and how to deal with the state space could inform research directions in this community as well.\n\nA weakness is that the work presents itself as being only applicable to multi-objective combinatorial optimization problems. I believe this is not the case. In it's current form the GS-DAC approach should be applicable to a wide variety of mutli-objective problems. There would not even be need for big changes in the algorithm, just the action space for PPO might change. Further, the GS-DAC approach also seems to not be limited to the multi-objective case. While it is highly applicable for this setting, the idea of using graph (convolutional) neural networks to learn better state embeddings could be used in a broader variety of problems. For example, I don't see why it would not be possible to use the GS-DAC idea and apply it directly in the setting described by Bordne et al. (2024)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Will you make the benchmark available as part of the DACBenchmark?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper was met with some strong negative and positive reviews. On the positive side, the reviewers like the novelty and function of the method. Dynamic algorithm configuration (DAC) has not been examined much in the area of multi-objective optimization. The graph embedding used by the authors is a particularly nice idea that seems to really provide the configuration mechanism (DRL agent) with good information about the current state of the search. On the negative side, there are concerns about the experiments and the clarity of the paper. Having worked in this area myself, I do not share the concerns regarding the experiments. However, I do encourage the authors of the paper to remove claims of robustness and try to make the method more clear to a wider audience. With that said, I think these are minor limitations to the work and support its acceptance.
Decision: Accept (poster)