POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
Authors:
Preprint
Abstract
In neural combinatorial optimization (CO), reinforcement learning (RL) can turn a deep neural net into a fast, powerful heuristic solver of NP-hard problems. This approach has a great potential in practical applications because it allows near-optimal solutions to be found without expert guides armed with substantial domain knowledge. We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. POMO uses a modified REINFORCE algorithm that forces diverse rollouts towards all optimal solutions. Empirically, the low-variance baseline of POMO makes RL training fast and stable, and it is more resistant to local minima compared to previous approaches. We also introduce a new augmentation-based inference method, which accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based on POMO shows a significant improvement in performance over all recent learned heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100 while reducing inference time by more than an order of magnitude.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Learning Improvement Heuristics for Solving Routing ProblemsIEEE Transactions on Neural Networks and Learning Systems, 2022
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems2020
- BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding2019
- An effective implementation of the Lin–Kernighan traveling salesman heuristicEuropean Journal of Operational Research, 2000
- Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning1992
- Function Optimization using Connectionist Reinforcement Learning AlgorithmsConnection Science, 1991