Machine learning assisted (Hyper-)heuristic for combinatorial optimization problems with emerging challenges

  • Chaofan TU

Student thesis: PhD Thesis


Despite extensive efforts to address combinatorial optimization problems, traditional methods still encounter challenges when deployed in real-life scenarios. These challenges include modeling complex systems, handling uncertain events, ensuring interpretability, and more. However, in the last decade, there have been eye-catching breakthroughs in machine learning that have demonstrated its potential to enhance problem-solving capabilities when integrated into optimization algorithms.
This research investigates machine learning-assisted heuristic approaches to tackle specific challenges. The first part of this thesis centers on regular expression generation, employing a metaheuristic in conjunction with a pre-trained word2vec model. The solutions obtained through this approach are not only of high quality but also interpretable to humans. In the second part, a Deep Reinforcement Learning-based hyper-heuristic framework proves to be highly effective in tackling uncertainties within the 2D strip packing problem. The last part introduces a feature fusion method to further address the challenge of uncertainty, resulting in achieving state-of-the-art performance in solving the online 0/1 knapsack problem. The visualization of the learned strategies reveals a stage-dependent characteristic.
This research significantly advances the integration of machine learning into heuristics for solving combinatorial optimization problems within a data-driven paradigm. It offers a valuable reference for related applications and serves as an inspiration for further research in other problem domains.
Date of AwardMar 2024
Original languageEnglish
Awarding Institution
  • University of Nottingham
SupervisorRuibin Bai (Supervisor), Heshan Du (Supervisor) & Jianfeng Ren (Supervisor)


  • Machine learning
  • Hyper-heuristics
  • optimization

Cite this