Cross-domain Selection Hyper-heuristics with Deep Reinforcement Learning

Abstract

Während problemspezifische Heuristiken effektive Techniken zur Lösung kombinatorischer Optimierungsprobleme darstellen, bleibt die Entwicklung adaptiver Methoden, die über verschiedene Problemdomänen, einschließlich neuer und unbekannter Domänen, hinweg generalisieren, eine Herausforderung. Hyperheuristiken wählen untergeordnete Heuristiken mit nur sehr begrenzten Informationen über die aktuelle Lösung und die Problemdomäne iterativ aus. In diesem Kontext kann die Auswahlkomponente der Hyperheuristik als Reinforcement Learning Problem aufgefasst werden, für das bereits Methoden existieren. Es besteht jedoch ein Bedarf an weiterer Forschung, einschließlich der Integration von Deep Reinforcement Learning, das bereits Potenzial für ähnliche Aufgaben gezeigt hat. Basierend auf der existierenden Hyperheuristik LAST-RL, die Reinforcement Learning verwendet, untersuchen wir die Auswirkungen neuer und bestehender Features des Zustands der heuristischen Suche und schlagen andere Erweiterungen vor, darunter einen erweiterten Aktionsraum und Anpassungen bei der Belohnungsfunktion. Wir entwickeln zwei Hyperheuristiken, die Deep Reinforcement Learning verwenden: eine verwendet DeepQ-Learning, die andere Proximal Policy Optimization. Die Entwicklung liefert Einblicke in wesentliche Komponenten der Hyperheuristik, eine domänenübergreifende Strategie für die Hyperparameteroptimierung zeigt ihre Wirksamkeit, und die Auswertung auf einer Benchmarksammlung von Problemdomänen (HyFlex) hebt die Stärken und Schwächen der vorgeschlagenen Ansätze hervor. Zusätzlich werten wir die Fähigkeit unserer Ansätze, auf drei komplexen realen Personaleinsatzplanungsproblemen zu generalisieren, aus. Die vorgeschlagenen Erweiterungen für LAST-RL ermöglichen Verbesserungen auf der Benchmarksammlung HyFlex. In den Problemdomänen, die Potenzial für weitere Verbesserungen zeigten, darunter MaxSAT und Bin Packing, zeigt sich, dass die Erweiterungen effektiv sind. Obwohl die beiden Methoden, die Deep Reinforcement Learning nutzen, auf der Benchmarksammlung von Problemdomänen nur teilweise konkurrenzfähig sind, zeigt die Hyperheuristik, die den Deep Q-Learning Algorithmus verwendet, ihre Fähigkeit, für die unbekannten realen Personaleinsatzplanungsprobleme zu generalisieren. Darüber hinaus integrieren wir eine Progressive Neural Network Architektur, die Transfer Learning ermöglicht, was durch eine bessere Leistung der Hyperheuristik nach dem Training dieser Architektur auf Trainingsinstanzen bestätigt wird. Weiters beobachten wir, dass mit mehr Trainingsepochen die Fähigkeit der Hyperheuristik für Transfer Learning auf unbekannten Probleminstanzen weiter verbessert wird.

While domain-specific heuristics are effective techniques for solving combinatorial optimization problems, constructing adaptive methodologies that generalize across multiple problem domains, including new and unseen domains, remains a challenge. Hyperheuristics are higher-level methodologies designed to address this challenge by iteratively selecting low-level heuristics with very limited information about the current solution and the problem domain. In this setting, the selection component of the hyper-heuristic can be seen as a reinforcement learning task, for which several approaches already exist. However, there is a need for further advancements, including the integration of deep reinforcement learning, which has already shown potential for similar tasks. Based on the existing reinforcement learning hyper-heuristic LAST-RL, we investigate the impact of new and existing features of the heuristic search state and propose further enhancements, including an extended action space and modifications to the reward function. We design two deep reinforcement learning hyper-heuristics that both build upon the existing LAST-RL hyper-heuristic: the first one uses the deep Q-learning algorithm and the second one uses the Proximal Policy Optimization algorithm. The design process offers insights into the impact of crucial design choices, a custom hyperparameter tuning strategy across domains demonstrates its effectiveness, and the evaluation on the hyperheuristics benchmark framework HyFlex highlights the strengths and weaknesses of the proposed approaches. Additionally, we test the ability of our approaches to generalize to three complex real-life personnel scheduling domains. The proposed enhancements for LAST-RL enable improvements on the HyFlex benchmark suite. In the problem domains that showed potential for further improvements, including MaxSAT and Bin Packing, the enhanced version turns out to be effective. Although the two methods utilizing deep reinforcement learning are only partially competitive on the HyFlex benchmark suite, the hyper-heuristic that utilizes deep Q-learning shows its ability to generalize to unseen real-life personnel scheduling domains. Additionally, we integrate a progressive neural network architecture, which demonstrates its ability to transfer knowledge, as pre-training this architecture on training instances leads to better performance compared to an initial model with this architecture. We observe that increasing the number of pre-training epochs further enhances the hyper-heuristics’ ability to transfer knowledge for the heuristic search on unseen problem instances.