Reinforcement Learning for Cross-Domain Hyper-Heuristics

Florian Mischek, Nysret MusliuIJCAI 2022 · DOI

TL;DR

This paper introduces a novel hyper-heuristic approach that leverages reinforcement learning (RL) to automatically select low-level heuristics for solving complex optimization problems across different domains. By learning a sophisticated selection policy and incorporating strategic resets, their method achieves competitive results, even outperforming previous RL-based approaches and placing among the top performers in a challenging benchmark competition.

What Problem Does This Paper Address?

Designing effective heuristics for complex optimization problems (like the Traveling Salesman Problem or Bin Packing) is a challenging and time-consuming task. Hyper-heuristics aim to automate this process by learning to select and combine simpler "low-level" heuristics. The Cross-Domain Heuristic Search Challenge (CHeSC) highlighted the need for hyper-heuristics that can generalize across diverse problem domains. While reinforcement learning has been explored for this purpose, prior RL-based methods in the CHeSC competition did not perform as well as other approaches. This paper investigates whether a well-designed RL framework can indeed produce state-of-the-art hyper-heuristics for cross-domain optimization.

Methods

The core of the proposed approach is a reinforcement learning agent that learns a policy for selecting low-level heuristics. Key innovations include:

  • State Representation: The agent's "state" is defined by features derived from the search history, such as the index and type of the last heuristic applied, and the remaining "tail length" before a potential reset. They also explore a "recent improvement" feature to track progress.
  • Action Selection Policy: They employ an ε-greedy or ε-softmax policy, which balances exploiting current knowledge with exploring new options. They also investigate decaying ε values to adapt over time.
  • Reward Mechanism: Instead of immediate objective function changes, rewards are given at the end of "solution chains" (sequences of heuristic applications). A successful chain (finding a new best solution) receives a reward, while a reset without improvement yields zero. They study different reward formulations, including constant rewards, total objective delta, and delta per time.
  • Solution Chain Management: A crucial element is the strategic reset of the current solution back to the best-found solution. This prevents the search from getting stuck in unpromising regions. They use Luby's sequence to dynamically determine the length of these chains, which proved significantly better than fixed lengths.
  • Update Rules: They evaluate standard RL update rules like Monte-Carlo (MC), Q-learning, SARSA, and Expected-SARSA (E-SARSA).

Datasets

The experiments were conducted using the HyFlex framework, which provides a standardized benchmark for cross-domain hyper-heuristics. The problem domains used were:

  • Maximum Satisfiability Problem (MaxSAT)
  • Bin Packing (BP)
  • Flow Shop (FS)
  • Personnel Scheduling (PS)
  • Traveling Salesman Problem (TSP)
  • Vehicle Routing Problem (VRP)

The paper notes that for the CHeSC competition, instances for the latter four domains were withheld from participants until after the competition.

Key Insights and Ideas

  • Strategic Resets are Crucial: The ability to reset the search to a previously found good solution is vital for avoiding getting stuck and achieving competitive performance. This is a key differentiator from simpler RL approaches.
  • Luby's Sequence for Chain Length: Dynamically adjusting solution chain lengths using Luby's sequence is significantly more effective than fixed-length chains, suggesting a need for adaptive exploration/exploitation of chain lengths.
  • State Representation Matters, But Not Overly: While the choice of state features (like last heuristic, tail length, recent improvement) impacts performance, the results are surprisingly robust. Even a very simple state representation (learning a single value per heuristic) performed competitively.
  • Reward Design is Key: Rewarding only at the end of successful chains, rather than for every small improvement, better aligns with the goal of finding high-quality solutions and avoids penalizing heuristics that might temporarily worsen the solution but enable future improvements.
  • RL is a Viable Paradigm: The paper strongly supports reinforcement learning as a powerful and well-suited paradigm for developing general-purpose hyper-heuristics.

Key Results

  • The proposed RL-based hyper-heuristic, with a specific configuration (LH+RI10 state, 0.1-softmax policy with decaying ε, constant rewards, and Luby's sequence for chain length, updated via MC learning), achieved a second-place ranking if it had participated in the CHeSC 2011 competition.
  • This performance places it among the top hyper-heuristics, significantly improving upon previous RL-based approaches submitted to the competition.
  • The approach also demonstrated competitive results when compared to a more recent hyper-heuristic that also utilized repeated solution chains.

Limitations and Future Work

  • Function Approximation: The authors suggest investigating function approximation techniques for reinforcement learning. This could allow the agent to generalize better to unseen states and potentially handle larger state spaces more efficiently.
  • State Similarity Metric: Defining a metric to measure the similarity between states and distributing rewards to similar states is proposed as a way to achieve more robust learning.
  • No Crossover Operators: For this work, crossover operators were not used as the focus was on single-solution optimization. Future work could explore their integration.
  • Fixed Chain Lengths: While Luby's sequence was used, the maximum chain length was still a parameter. Further exploration of adaptive maximum chain lengths could be beneficial.

Summary updated

BibTeX
@inproceedings{mischek2022reinforcement,
  author = {Florian Mischek and Nysret Musliu},
  title = {{Reinforcement Learning for Cross-Domain Hyper-Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/664},
}
Figure