Quality Diversity Genetic Programming for Learning Scheduling Heuristics

• URL: http://arxiv.org/abs/2507.02235v1
• Date: Thu, 03 Jul 2025 02:01:30 GMT
• Title: Quality Diversity Genetic Programming for Learning Scheduling Heuristics
• Authors: Meng Xu, Frank Neumann, Aneta Neumann, Yew Soon Ong,
• Abstract summary: Quality-Diversity (QD) optimization is a multifaceted approach in evolutionary algorithms that aims to generate a set of solutions that are both high-performing and diverse.<n>This paper introduces a novel QD framework for dynamic scheduling problems.<n>We propose a map-building strategy that visualizes the solution by linking genotypes to their behaviors, enabling their representation on a QD map.
• Score: 36.015695494167495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Real-world optimization often demands diverse, high-quality solutions. Quality-Diversity (QD) optimization is a multifaceted approach in evolutionary algorithms that aims to generate a set of solutions that are both high-performing and diverse. QD algorithms have been successfully applied across various domains, providing robust solutions by exploring diverse behavioral niches. However, their application has primarily focused on static problems, with limited exploration in the context of dynamic combinatorial optimization problems. Furthermore, the theoretical understanding of QD algorithms remains underdeveloped, particularly when applied to learning heuristics instead of directly learning solutions in complex and dynamic combinatorial optimization domains, which introduces additional challenges. This paper introduces a novel QD framework for dynamic scheduling problems. We propose a map-building strategy that visualizes the solution space by linking heuristic genotypes to their behaviors, enabling their representation on a QD map. This map facilitates the discovery and maintenance of diverse scheduling heuristics. Additionally, we conduct experiments on both fixed and dynamically changing training instances to demonstrate how the map evolves and how the distribution of solutions unfolds over time. We also discuss potential future research directions that could enhance the learning process and broaden the applicability of QD algorithms to dynamic combinatorial optimization challenges.

Related papers

• Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization [5.481047026874548]
  This paper presents a novel graph neural network (GNN) based DRL to configure multi-objective evolutionary algorithms.<n>We model the dynamic algorithm configuration as a Markov decision process, representing the convergence of solutions in the objective space by a graph.<n> Experiments on diverse MOCO challenges indicate that our method outperforms traditional and DRL-based algorithm configuration methods in terms of efficacy and adaptability.
  arXiv  Detail & Related papers  (2025-05-22T09:53:54Z)
• Overcoming Deceptiveness in Fitness Optimization with Unsupervised Quality-Diversity [4.787389127632926]
  Policy optimization seeks the best solution to a control problem according to an objective or fitness function.<n>In this paper, we show that unsupervised QD algorithms efficiently solve deceptive optimization problems without domain expertise.
  arXiv  Detail & Related papers  (2025-04-02T17:18:21Z)
• Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
  We study the behaviour of Quality diversity (QD) algorithms for a classical planning problem seeking several solutions.<n>Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel.
  arXiv  Detail & Related papers  (2024-12-16T04:58:32Z)
• Quantum Inspired Chaotic Salp Swarm Optimization for Dynamic Optimization [4.44483539967295]
  We study a variant of SSA known as QSSO, which integrates the principles of quantum computing. A chaotic operator is employed with quantum computing to respond to change and guarantee to increase individual searchability. As promised, the introduced QCSSO is discovered as the rival algorithm for DOPs.
  arXiv  Detail & Related papers  (2024-01-21T02:59:37Z)
• SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving [64.38649623473626]
  Large Language Models (LLMs) have driven substantial progress in artificial intelligence. We propose a novel framework called textbfSEquential subtextbfGoal textbfOptimization (SEGO) to enhance LLMs' ability to solve mathematical problems.
  arXiv  Detail & Related papers  (2023-10-19T17:56:40Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
  We apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem. We show that they are able to compute an optimal solution within expected pseudo-polynomial time.
  arXiv  Detail & Related papers  (2022-07-28T12:15:33Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.