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.

使用改进的 REINFORCE 算法的 POMO 方法，结合了基于增强的推理方法，可获得用于解决 NP-hard 问题的先进的启发式方法，可用于广泛的组合优化问题，显着提高了其性能和速度。