Reinforcement Learning Driven Heuristic Optimization
This addresses the problem of improving heuristic algorithm efficiency for combinatorial optimization tasks, representing an incremental advancement by combining RL with existing heuristics.
The paper tackles the high sample complexity of heuristic algorithms in combinatorial optimization by introducing RLHO, a reinforcement learning framework that generates better initial solutions for heuristics, and demonstrates that it outperforms baselines on the bin packing problem.
Heuristic algorithms such as simulated annealing, Concorde, and METIS are effective and widely used approaches to find solutions to combinatorial optimization problems. However, they are limited by the high sample complexity required to reach a reasonable solution from a cold-start. In this paper, we introduce a novel framework to generate better initial solutions for heuristic algorithms using reinforcement learning (RL), named RLHO. We augment the ability of heuristic algorithms to greedily improve upon an existing initial solution generated by RL, and demonstrate novel results where RL is able to leverage the performance of heuristics as a learning signal to generate better initialization. We apply this framework to Proximal Policy Optimization (PPO) and Simulated Annealing (SA). We conduct a series of experiments on the well-known NP-complete bin packing problem, and show that the RLHO method outperforms our baselines. We show that on the bin packing problem, RL can learn to help heuristics perform even better, allowing us to combine the best parts of both approaches.