Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization

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.

Algorithms need to be set up with the right parameters to perform well. However, the best settings often change as the algorithm runs, based on the progress it makes. Dynamic algorithm configuration addresses this challenge by allowing the algorithm to adjust its parameters on the fly. In this paper, we explore how to make these adaptive decisions smarter and more effective, especially for problems with multiple conflicting optimization goals (such as cost vs. quality). We use a deep reinforcement learning (DRL) based to train an agent that learns from past experience how to adjust the algorithm’s settings dynamically. To help the agent see how solutions are improving, we represent the solutions as a graph and use a graph neural network (GNN) to learn the patterns in this progress. This helps the system understand when and how to adjust its settings. Our results show that this method works better than both traditional fixed settings and other learning-based methods. It not only finds better solutions but also generalizes to different problem variants and sizes.