Sym-NCO：利用对称性进行神经组合优化
文章目录
- Abstract
- 1 Introduction
- 2 组合优化马尔可夫决策过程中的对称性
- 2.1 组合马尔可夫决策过程
- 2.2 CO-MDP中的对称性
- 3 对称神经组合优化
- 3.1 通过LSym-RL正则化REINFORCE的问题和解决方案对称性
- 3.2 通过预先识别的对称性学习不变表示： L i n v L_{inv} Linv
- 4 相关工作
- 5 Experiments
- 5.1 任务和基线选择
- 5.2 实验设置
- 5.3 性能指标
- 5.4 实验结果
- 6 讨论
- 6.1 基于正则化的对称性学习讨论
- 6.2 限制和未来方向
- 6.3 社会影响
Abstract
深度强化学习（DRL）基础的组合优化（CO）方法（即DRL-NCO）与传统的CO求解器相比具有显著优势，因为DRL-NCO能够学习较少依赖于特定问题的专家领域知识（启发式方法）和监督标记数据（监督学习方法）。本文提出了一种新的训练方案Sym-NCO，它是一种基于正则化的训练方案，利用各种CO问题和解决方案中的普遍对称性。利用诸如旋转和反射不变性等对称性可以显著提高DRL-NCO的泛化能力，因为它允许学习到的求解器利用同一CO问题类别中共同的对称性。我们的实验结果验证了我们的Sym-NCO在四个CO任务上大大提高了DRL-NCO方法的性能，包括旅行商问题（TSP）、带容量限制的车辆路径问题（CVRP）、奖励收集TSP（PCTSP）和定向问题（OP），而且没有利用特定问题的专家领域知识。值得注意的是，Sym-NCO不仅超越了现有的DRL-NCO方法，而且在PCTSP中以240倍更快的速度超越了竞争性的常规求解器——迭代局部搜索（ILS）。我们的源代码可在https://git