Quality Diversity Genetic Programming for Learning Scheduling Heuristics Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; July 14–18, 2025, Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.37

Meng Xu, Frank Neumann, Aneta Neumann, Yew Soon Ong · 2025

Read Quality Diversity Genetic Programming for Learning Scheduling Heuristics Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; July 14–18, 2025, Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.37 by Meng Xu, Frank Neumann, Aneta Neumann, Yew Soon Ong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02235.txt.

Introduction

Meng Xu, Frank Neumann, Aneta Neumann, and Yew Soon Ong bring quality-diversity methods to learning scheduling rules, in a 2025 paper. Real problems often need many good solutions that differ from each other, not just one best answer. Quality-diversity search builds such sets by exploring varied niches.

Most past work used static problems, while scheduling changes over time. The team built a map that links each rule's code to its behavior, so diverse rules can be found and kept. Experiments on fixed and changing training cases show how the map fills over time. The paper also discusses theory gaps and future directions for dynamic problems.

Catalog record

CREATORMeng Xu, Frank Neumann, Aneta Neumann, Yew Soon Ong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02235

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quality Diversity Genetic Programming for Learning Scheduling Heuristics Conference: Genetic and Evolutionary Computation Conference; July 14–18, 2025; July 14–18, 2025, Malaga, Spain Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain DOI: 10.1145/3712256.3726343 ISBN: 979-8-4007-1465-8/2025/07 CCS: Theory of computation Random search heuristics CCS: Computing methodologies Heuristic function construction CCS: Theory of computation Theory of randomized search heuristics CCS: General and reference Experimentation Meng Xu, Frank Neumann, Aneta Neumann, Yew Soon Ong 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. 1. Introduction Recent research highlights the competitiveness of diversity-seeking optimization approaches, such as Quality-Diversity (QD) ( Cully and Demiris 2017 ; Flageat and Cully 2023 ) . Encouraging the generation of creative and diverse solutions has been shown to enhance exploration ( Qin et al. 2024 ) , facilitate the discovery of stepping stones toward novel solutions, and improve adaptability to unforeseen situations. However, current QD methods primarily focus on searching within the solution space, leaving their potential in the heuristic space largely unexplored. This paper addresses these gaps by applying QD to dynamic and large-scale problems, exemplified by the dynamic flexible job shop scheduling (DFJSS) problem. By shifting the focus of QD from directly finding schedule solutions to learning scheduling heuristics, this study significantly broadens the applicability of QD. It opens new pathways for addressing complex, real-world challenges where adaptability and diversity in decision-making strategies are crucial. DFJSS problem is a complex combinatorial optimization problem that involves scheduling a set of jobs on a set of machines in dynamic environments, where factors such as job arrival times can change over time ( Shahgholi Zadeh et al. 2019 ) . Existing studies in DFJSS typically focus on learning either a single scheduling heuristic ( Guo et al. 2024 ) or an ensemble of scheduling heuristics ( Xu et al. 2023 ) to produce a single scheduling solution for a specific DFJSS scenario. However, these approaches lack flexibility, as they do not provide decision-makers with a diverse set of alternative heuristics and corresponding scheduling solutions for comparative analysis and selection—especially in response to unexpected disruptions. In real-world applications, DFJSS problems often extend to supply chain networks ( Ceylan et al. 2021 ) , where localized disruptions (e.g., supplier delays) can propagate and severely impact operations. Developing multiple diverse, high-quality scheduling heuristics enables systems to dynamically generate alternative schedules, allowing for real-time adjustments in priorities and resource allocations to mitigate the effects of such disruptions. This highlights the critical need to study the QD of solutions in DFJSS problems. Focusing on learning multiple high-quality, diverse scheduling heuristics enhances DFJSS systems’ adaptability, robustness, and alignment with real-world challenges. Rather than relying on a single heuristic, leveraging a portfolio of diverse heuristics supports dynamic decision-making, better addressing the varied and evolving demands of modern manufacturing and logistics. Additionally, analyzing QD is essential for understanding both the complexity of DFJSS problems and the vastness of their solution spaces, potentially uncovering even more effective individual heuristics. In the context of existing genetic programming (GP) ( Koza 1994 ) methods for learning scheduling heuristics, QD analysis offers the potential to provide valuable insights into understanding the search space of GP for learning scheduling heuristics—an area that remains largely unexplored. Gaining this deeper understanding is crucial for designing more effective algorithms and heuristics, equipping DFJSS systems to better manage the variability and unpredictability inherent in dynamic environments. However, it is challenging to generate a QD map for individuals (scheduling heuristics) in DFJSS for the following reasons: (1) Scheduling heuristics, represented as tree structures, can be mapped to behaviors based on phenotypic characteristics ( Hildebrandt and Branke 2015 ) . However, the vast space of potential behaviors poses challenges in constructing a QD map. Determining appropriate descriptors to effectively represent and build the map remains an open issue that requires further investigation. (2) The ever-changing nature of DFJSS problems, with varying job arrival times, makes it challenging to generate a static map that accurately represents the relationship between genotypes and behaviors across all possible scenarios. The context-dependent nature of heuristics means that the effectiveness of a heuristic may vary depending on the specific problem instance. (3) Changing the training instance(s) for each new generation is a common strategy to enhance the generalization ability of scheduling heuristics in DFJSS. However, this approach complicates the maintenance of a static map and makes it challenging to directly compare individuals across different generations. Consequently, this complexity makes the map update process more difficult and less straightforward. (4) Evaluating the performance of a heuristic in a DFJSS problem is often computationally expensive, especially for large-scale problems. This makes it difficult to generate a comprehensive map of the heuristic space within a limited time. In summary, studying QD in DFJSS requires addressing the following challenges step-by-step: (1) How to determine descriptors to construct a QD map? (2) How can the search space be wisely reduced to construct a fixed (static), appropriately sized search space and map? (3) How can individuals be compared, and how can the map be efficiently updated, especially when individuals are evaluated using different training instances? This paper proposes a QD map-building strategy integrated with GP for combinatorial optimization, using the DFJSS problem as a case study. This approach provides a tool to visualize the solution space and analyze population diversity, guiding the evolutionary process toward learning high-quality, diverse heuristics. 2. Preliminaries 2.1. Dynamic Flexible Job Shop Scheduling In DFJSS ( Xu et al. 2023 ) , a set of machines, M=\{M_{1},M_{2},\dots,M_{m}\} , is available to process a set of jobs, J=\{J_{1},J_{2},\dots,J_{n}\} . Each job J_{i} comprises a sequence of operations [O_{i1},O_{i2},\dots,O_{ik}] , where each operation O_{ij} can be processed on a subset of machines M_{ij}\subseteq M , allowing flexibility in machine selection. The capabilities of machines vary, and the processing time of operation O_{ij} on machine M_{m} is denoted as p_{ijm} . Jobs arrive dynamically over time, with r_{i} representing the release time of job J_{i} (when the job becomes available for processing), and d_{i} representing the due date for job J_{i} . The core challenge lies in

Read the complete text