DeepACO：用于组合优化的神经增强蚂蚁系统
文章目录
- Abstract
- 1 Introduction
- 2 Related work
- 2.1 神经组合优化
- 2.2 蚁群优化
- 3 蚁群优化初探
- 4 Methodology
- 4.1 参数化启发式空间
- 4.2 局部搜索与局部神经引导扰动交织
- 4.3 训练启发式学习器
- 4.4 更好的探索
- 4.4.1 多头解码器
- 4.4.2 Top-k熵损失
- 4.4.3 模仿损失
- 5 实验
- 5.1 实验设置
- 5.2 DeepACO作为一种增强的ACO算法
- 5.3 DeepACO作为NCO方法
Abstract
提出了 DeepACO，这是一个利用深度强化学习来自动化启发式设计的通用框架。DeepACO 旨在加强现有 ACO 算法的启发式措施，并在未来的 ACO 应用中免除繁琐的手动设计。作为一种神经增强元启发式算法，DeepACO 在使用单个神经模型和一组超参数的 8 个 COP 上始终优于其 ACO 同行。作为一种神经组合优化方法，DeepACO 在规范路由问题上的表现优于或与特定问题的方法相当。
1 Introduction
启发式设计上存在缺陷：
1）需要额外的努力，并且使得ACO灵活性较差；
2）启发式举措的有效性很大程度上依赖于专家知识和人工调优；
3）考虑到可用的专业知识的缺乏，为研究较少的问题设计启发式措施可能特别具有挑战性。
本文提出DeepACO,一种通用的神经增强 ACO 元启发式算法，以及针对上述限制的解决方案。DeepACO 旨在加强现有 ACO 算法的启发式措施，并在未来的 ACO 应用中免除繁琐的手动设计。主要涉及两个学习阶段。第一阶段通过跨 COP 实例训练神经模型来学习从实例到其启发式测量的特定问题映射。通过偏置解决方案构造并引导局部搜索（LS）逃避局部最优，将第一阶段学习的启发式措施纳入 ACO（第二学习阶段）。
此外，我们提出了三种扩展实现，以更好地平衡开发和探索：一种具有多头解码器，一种采用额外的 top-k 熵损失进行训练，另一种采用额外的模仿损失进行训练。它们通常可应用于基于热图的 NCO 方法。
2 Related work
2.1 神经组合优化
端到端方法：直接使用神经网络将问题的输入映射到输出，实现端到端的优化。神经网络可以学习问题的表示和解码策略，从而直接生成最优解或近似最优解。端到端方法的优点是简单直接，但可能受限于问题的复杂性和规模。
混合方法：将传统的优化算法与神经网络结合起来，形成混合模型。例如，可以使用神经网络来学习问题的特征表示，然后将这些特征输入到传统的优化算法中进行进一步的优化。这种混合方法结合了传统优化算法的高效性和神经网络的表示学习能力，可以在一定程度上克服端到端方法的限制。
2.2 蚁群优化
ACO 可以利用一组名为超启发式 [69] 的技术，这些技术在概念上与 DeepACO 相关。但超启发式大多涉及专家设计的启发式选择（启发式选择超启发式）[27]或针对特定问题和手动定义的组件来演化启发式（启发式生成超启发式）[14]。相比之下，DeepACO 更加通用，几乎不需要 COP 的先验知识。
3 蚁群优化初探
选择节点 j j j作为下一个目的地的概率：
基于等式(1)构建完整的解决方案需要n步图遍历。生成 s 的概率可以分解为：
构建解决方案后，可选择应用局部搜索 (LS) 来细化解决方案。
4 Methodology
DeepACO示意图如图1所示，其中与ACO进行了比较。它不需要专家知识，而是学习一套更强的启发式举措来指导ACO的进化。
4.1 参数化启发式空间
我们引入了一个启发式学习器，它由具有可训练参数 θ 的图神经网络 (GNN) 定义，以参数化启发式空间。
启发式学习器将输入COP实例 ρ \rho ρ（具体的组合优化实例）映射到启发式测量 η θ \eta_\theta ηθ。