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

Abstract

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 Award	Mar 2024
Original language	English
Awarding Institution	University of Nottingham
Supervisor	Ruibin Bai (Supervisor), Heshan Du (Supervisor) & Jianfeng Ren (Supervisor)