论文标题
通过退火来补充复发性神经网络，以解决组合优化问题
Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
论文作者
论文摘要
组合优化问题可以通过启发式算法（例如模拟退火（SA））来解决，该算法旨在通过热波动在较大的搜索空间中找到最佳解决方案。该算法通过马尔可夫链蒙特卡洛技术生成新的解决方案。这种抽样方案可能会导致严重的局限性，例如趋势缓慢和在较小温度下留在同一局部搜索空间内的趋势。为了克服这些缺点，我们使用了将自回归复发性神经网络（RNN）与传统退火结合的变异经典退火（VCA）框架与不相关的样品解决方案。在本文中，我们证明了使用VCA作为解决现实世界优化问题的方法的潜力。与SA相比，我们探索了VCA的性能，以解决三个流行的优化问题：最大切割问题（最大切割），护士调度问题（NSP）和旅行推销员问题（TSP）。对于所有这三个问题，我们发现VCA在渐近极限中平均在相对误差方面平均超过一个或多个数量级。有趣的是，我们达到了TSP的大型系统尺寸最高256美元的城市。我们还得出结论，在最好的情况下，当SA无法找到最佳解决方案时，VCA可以作为一个很好的选择。
Combinatorial optimization problems can be solved by heuristic algorithms such as simulated annealing (SA) which aims to find the optimal solution within a large search space through thermal fluctuations. The algorithm generates new solutions through Markov-chain Monte Carlo techniques. This sampling scheme can result in severe limitations, such as slow convergence and a tendency to stay within the same local search space at small temperatures. To overcome these shortcomings, we use the variational classical annealing (VCA) framework that combines autoregressive recurrent neural networks (RNNs) with traditional annealing to sample solutions that are uncorrelated. In this paper, we demonstrate the potential of using VCA as an approach to solving real-world optimization problems. We explore VCA's performance in comparison with SA at solving three popular optimization problems: the maximum cut problem (Max-Cut), the nurse scheduling problem (NSP), and the traveling salesman problem (TSP). For all three problems, we find that VCA outperforms SA on average in the asymptotic limit by one or more orders of magnitude in terms of relative error. Interestingly, we reach large system sizes of up to $256$ cities for the TSP. We also conclude that in the best case scenario, VCA can serve as a great alternative when SA fails to find the optimal solution.
