Hyperheuristic Frameworks for Combinatorial Optimization Problems using Deep Reinforcement Learning

Abstract

Many metaheuristic frameworks exist for solving different combinatorial optimization problems. Despite formulating general strategies that can be applied to many problems, they often rely on problem-specific implementation. Hyperheuristic frameworks attempt to fully generalize the solution method by only relying on general search information for decision making. The addition of Deep Reinforcement Learning (DRL) in a hyperheuristic framework provides the opportunity of learning complex relations between different actions and the state of the search. When it is used for selection of heuristics, it is important to mitigate the opportunity for reward hacking by carefully designing the reward function to be as representative of our objective as possible. This thesis proposes two hyperheuristic frameworks using DRL, with a new reward function for heuristic selection that is based on the percentage improvement compared to the initial solution. Deep Reinforcement Learning Hyperheuristic Plus (DRLH+) combines this DRL heuristic selection with the acceptance strategy of simulated annealing. Dual-Network Deep Reinforcement Learning Hyperheuristic (D^2RLH) combines the DRL heuristic selection with a second DRL agent for acceptance. The frameworks are tested by solving instances of the Pickup and Delivery Problem with Time Windows, and consistently perform well on large problem sizes. The reward function is shown to improve upon the reward function of Deep Reinforcement Learning Hyperheuristic (DRLH) by making gradual and consistent improvements throughout the search, and is able to adjust the strategy to account for extended searches.