通过解预测和机器学习促进蚁群优化

Abstract

ML - ACO 算法的第一阶段，使用一组已知最优解的小定向越野问题实例训练一个 ML 模型。具体来说，使用分类模型根据问题特定的特征和统计度量来判断一条边是否属于最优路线。然后，训练后的模型用于预测测试问题实例中图中一条边属于最优路线的 “概率”。

在第二阶段，我们将 ML 模型预测的概率值纳入 ACO 算法中，即使用概率值作为启发式权重或用于初始化信息素矩阵。这样做的目的是使 ACO 的采样偏向于那些预测更有可能属于最优路线的边，从而有望提高 ACO 找到高质量路线的效率。

1. Introduction

利用 ML 来帮助组合优化最近引起了很多关注（Bengio 等人，2021；Karimi - Mamaghan 等人，2022）。例如，新颖的 ML 技术已被开发用于修剪大规模优化问题的搜索空间，使其缩小到现有解决方案算法可管理的大小（Sun 等人，2021b；Lauri 和 Dutta，2019；Sun 等人，2021a），用于为分支定界或树搜索算法排序决策变量（Li 等人，2018b；Shen 等人，2021），以及用于近似解决方案的目标值（Fischetti 和 Fraccaro，2019；Santini 等人，2021）。也存在一些基于 ML 的方法，试图直接为优化问题预测高质量的解决方案（Abbasi 等人，2020；Ding 等人，2020）。这些方法的关键思想通常是通过 ML 进行解预测，即尽可能接近地预测给定问题的最优解。

在 ML - ACO 算法的第一阶段，我们在一组由通用精确求解器（CPLEX V12.8.0）最优解决的小定向越野问题实例上训练一个 ML 模型，如图 1 所示。我们提取问题特定的特征以及统计措施（参见第 3.1 节）来描述已解决定向越野问题实例图中的每条边，并将每条边映射到特征空间中的一个训练点。然后，可以使用分类算法在特征空间中学习一个决策边界，以很好地区分属于最优路线的边和不属于最优路线的边。我们将测试多种现有的分类算法来完成此任务，包括图神经网络（Kipf 和 Welling，2017；Wu 等人，2021）、逻辑回归（Bishop，2006）和支持向量机（Boser 等人，1992；Cortes 和 Vapnik，1995）。对于一个未解决的测试定向越野问题实例，训练后的 ML 模型可以用于预测图中每条边属于最优路线的 “概率”，如图 2 所示。

在 ML - ACO 算法的第二阶段，我们将 ML 模型预测的概率值纳入 ACO 算法中，即使用概率值来设置启发式权重矩阵或初始化 ACO 的信息素矩阵。目的是在 ACO 构建可行路线的采样过程中，偏向于使用更有可能在最优路线中的边，希望能提高 ACO 找到高质量路线的效率。从这个意义上说，我们的 ML - ACO 算法的想法也与用于改进进化算法的播种策略相关（Liaw，2000；Hopper 和 Turton，2001；Friedrich 和 Wagner，2015；Chen 等人，2018）。

2. Background and related work

2.1 定向越野问题

考虑一个完全的有向图G(V,E,S,C)，其中V表示顶点集，E表示边集，S表示每个顶点的得分，C表示通过每条边的时间成本。

定向越野的目标是搜索一条从起始顶点$v_1$到结束顶点$v_n$的路径，该路径在给定的一个时间预算$T_{max}$内访问一个顶点子集，以使收集到的分数最大化。因此，定向越野问题可以看作是旅行商问题和背包问题的结合。

我们用$u_i$表示顶点$v_i$的访问顺序，并使用二进制变量$x_{i,j}$表示定点$v_j$是否在$v_i$之后直接被访问。定向越野问题的整数规划可以写为：

约束条件（2）确保路径从顶点$v_1$开始并在顶点$v_n$结束。
约束条件（3）保证中间的每个顶点最多只能被访问一次。
约束条件（4）是Miller - Tucker - Zemlin 子回路消除约束。
约束条件（5）满足给定的时间预算。

2.2 ACO优化

假设一只蚂蚁在顶点$v_i$，并且$V_i$表示这只蚂蚁在不违反时间预算约束的情况下下一步可以访问的顶点集合。这只蚂蚁在下一步访问顶点$v_j\in V_i$的概率由下式定义：

在定向越野问题中：我们把设置为顶点$v_j$