【论文笔记】DeepACO Neural-enhanced Ant Systems for Combinatorial Optimization

概述

使用了一种深度强化学习方法自动化了启发式设计

ACO算法的灵感源于自然界中利用信息素路径进行自学习的蚁群系统，用于解决组合优化问题（Combinatorial Optimization Problems，COPs）但是在传统的meta-heuristic方法中，heuristic measure是需要基于先验知识和设计专门定义的，但是对于复杂的问题而言，这种手工定义的方法就变得非常困难

传统的启发式学习需要手工使用专家知识先验地构造启发式设计，而本论文使用了深度学习来免除了手工设计的劳累，加强了现有的ACO（Ant Colony Optimization，蚁群优化）算法的heuristic measures

相关工作

神经组合优化 Neural Combinatorial Optimization (NCO)

传统的NCO分为：

• 端到端的：具有良好的性能，但是其性能能够通过迭代细化与算法混合进一步提升
• 混合的：采用了神经学习器来进行启发，在启发中使用或生成热图来辅助启发

DeapACO属于混合型的NCO

蚁群优化 Ant Colony Optimization (ACO)

ACO是一种meta-heuristic and evolutionary algorithm (EA)，使用一系列基于专家知识的hyper-heuristics进行知识驱动的适应

与之相比DeepACO更加具有泛化性，更加不依赖于专家知识

预备知识

COP模型

下面定义组合优化问题的模型

简单来说，搜索空间S是由一系列离散决策变量X来定义的，并遵循一系列限制Ω，同时有一个目标函数f进行最小化/优化。而一个可行的解（非最优解）是所有决策变量满足所有限制的解。

信息素模型

一个信息素模型是以决策变量为点、部分解为边的构造图。每一个部分解c都代表着对决策变量x的分配，并与信息素信息素试验τ和启发度量η有关。

信息素试验τ和启发度量η决定了部分解c的可信度。其中信息素试验往往是标准初始化并迭代更新的，而启发度量是预定义与固定的。

比如，在TSP问题（旅行商问题）中，城市i是节点i，而部分解$c_{ij}$代表在访问城市i后马上访问节点j。而启发度量η常被设置为城市i与城市j间的倒数。

解构造

定义了如何选择下一个部分解。其中，ρ是一个COP的实例，N是步骤t之前的可行解集，α和β是控制参数（本论文中全为1）。

由此，生成可行解s的可能性定义为：

方法

heuristic measure学习

本文使用了图神经网络GNN（参数为θ）作为启发式学习器来参数化启发空间。启发式学习器以一个COP实例ρ作为输入计算启发度量，定义为$\eta_{\theta}(\rho)或\eta_{\theta}$，以此为偏移，从而更改上面的生成可行解可能性的公式为：

NLS

传统的Local Search(LS)具有贪婪性，而在DeepACO中使用了学习好的heuristic measure表示全局的最优性，但这仍然不够。

因此，论文提出了 LS interleaved with neural-guided perturbation (NLS)

NLS采用了两次LS，第一次LS使其不断达到局部最优，第二次LS通过多次扰动不断靠近全局最优，然后将两次LS得到的解s输入目标函数，选取使目标函数最小的解$s^*$

heuristic learner训练

其中W是超参

简而言之就是最小化构造解的目标函数值与NLS后的目标函数值的加权和的期望

在实际应用中，作者使用蚁群系统来依照前文提到的概率公式随机构建解决方案，并固定信息素试验次数为1以确保估计不带偏见。作者应用了一个基于REINFORCE算法的梯度估计方法来估计上式，而梯度估计器定义为：

三种扩展设计

Multihead decoder

在GNN顶上使用了m个MLP解码器，用于多样化启发度量

并加入了一个新的基于KL散度的loss：

η代表第k个解码器输出的部分解c的启发式度量值

意思是不断最小化各个head间启发度量的差异

Top-k entropy loss

熵损失鼓励产生更多的多样性而非一味地重复某一动作。

而在本文的背景下，这个Top-k熵损失函数专注于在决策变量的前k个最大启发式度量的部分解上促进更大的均匀性（从而每个部分解的权重都是趋于均匀的，也就促进了多样性）

Imitation loss

有时候，我们可以获取一个问题的专家设计的启发度量，这时可以额外增加一个模仿损失（基于交叉熵损失）：

专家设计的启发度量通常比学习得到的启发度量保守，因此它们可以作为一种正则化手段来维持探索性，避免过度专注于已经学到的策略，而如果首先完善模仿，可以保证学习到的启发度量至少不会比专家设计的启发度量差

实验效果

扫码阅读此文章
点击按钮复制分享信息