VRP-TSP系列论文1 2023-06-09 组合优化 暂无评论 129 次阅读 ---- ## LEARNING TO CROSS EXCHANGE TO SOLVE MIN-MAX VEHICLE ROUTING PROBLE ICLR 2023  ### 问题 min-max FMDVRP + FMDVRP FMDVRP: 多个车辆和多个站点，允许车辆返回任何站点，而不管它们的起始站点。 诸多问题可以看作它的特例： TSP 是具有单个车辆和站点的 VRP mTSP 是具有多个车辆和单个站点的 VRP MDVRP 是具有多个车辆和站点的 VRP。 + min-max mini-sum: 对于一个VRP实例，最小化所有车辆路线的总长度。 mini-max: 对于一个VRP实例，最小化所有车辆路线中长度的最大值。 由于 FMDVRP 是一个通用问题类，我们学习了 FMDVRP 的求解器并用它来解决其他特定问题（即最小-最大 MDVRP、最小-最大 mTSP 和最小-最大 CVRP），而无需重新训练或微调。 ### 模型 + 前置：CE CROSS EXCHANGE: 启发式方法，$O(n^{4})$  + 本文方法：Neuro CROSS exchange(NCE) + NeuroCROSS Operation( $O(n^2)$ ) + CE 操作可以显示为从所选路线（即 τ1、τ2）中选择两对节点（即 a1/b1 和 a2/b2 对）。这通常涉及 O(n4) 次搜索。 + 为了降低高搜索复杂度，NCE 利用成本递减模型 fθ(a1, a2; τ1, τ2) 预测给定的 τ1 和 τ2 及其子旅行的起始节点 a1 和 a2 的最大成本递减y*。去掉了（b1, b2)的搜索。 + 从所有（a1，a2）选择中选择前K大 y* 的（a1，a2）,排除不太有改进希望的（a1, a2)对 。 + 为搜索候选集中的每个 (a1, a2) 找到最好的 (b1, b2)，并选择最大化实际成本递减的最佳子旅行 (a1, a2, b1, b2)。 + 成本递减预测模型(COST-DECREMENT PREDICTION MODEL) 带注意力图神经网络，输入是两个路线$\tau_1 \tau_2$ 输出是预测的cost $\hat{y}$  + 总体流程   ### 训练 有监督 Huber loss ### 实验 文中说他们的方法是第一个用神经网络解决 min-max FMDVRP的。    后续还有实验对比在min-max mTSP、min-max CVRP问题。 ### 总结 FMDVRP，VRP变体 改进解，有监督训练，带注意力图神经网络 --- ## Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems OR Spectrum 期刊 中科院4区 JCR3区  作者有李晓东，这篇他在IEEE那个线上会议上也提过 ### 问题 经典TSP问题 整体来看是启发式的方法，手工设计特征，中间有用到传统机器学习的方法(SVM)做分类任务。 预测每条边是否属于最短路线，并从完整图中移除那些不属于最短路线的边。目的是找到一个仍然包含（接近）最佳路线的稀疏子图，再用其它求解器求解。 ### 模型 + 使用最优求解的 TSP 实例作为训练集，并将最优解中的每条边视为训练实例。 + 将类别标签 1 分配给属于最佳路线的边，将 -1 分配给不属于最佳路线的边。 + 提取两个统计量度和四个graph features来表征每条边。 + 构建训练集后，我们的目标是在特征空间中学习决策边界，以区分正（类标签 1）和负（类标签 −1）训练实例。这成为一个典型的二元分类问题，任何分类算法都可以用于此任务，我们使用 SVM 来学习此任务的决策边界。 + 对于我们不知道最佳路线的给定大型 TSP 实例，经过训练的模型可用于预测图中每条边的类标签。通过移除预测为 −1 的边，我们得到了一个简化的稀疏图，希望现有的求解算法更容易求解。  关于特征提取，是手工设计的特征，挺麻烦的。 ### 训练 训练SVM，有监督 ### 实验 结果不是sota，主要是探索 MLPR 模型的泛化能力。 + 不同特征的泛化能力： 表 1：我们的 MLPR 模型在对一类 TSP 实例进行训练并在另一类实例上进行测试时产生的平均最优性差距 (%)。 7类实例分别标记为I1、···、I7。在类别 I j 上训练的 MLPR 模型表示为 MLPR-I j。为每个测试类别生成的最佳最优性差距以粗体显示。 表 2：在一类 TSP 实例上训练我们的 MLPR 模型并在另一类实例上测试时，剩余问题大小相对于其原始问题大小的百分比 (%)。 7类实例分别标记为I1、···、I7。在类别 I j 上训练的 MLPR 模型表示为 MLPR-I j。  + 不同问题大小的泛化能力： 可以看到还是能去掉不少边的。 图 2：在小型 TSP 实例上训练我们的 MLPR 模型并在较大实例上测试它时，减少后剩余问题大小的百分比。横轴表示测试 TSP 实例中的城市数量。  后续还有些实验，主要探讨TSP变体的泛化性问题、作为预处理和其它方法结合的效果、和其它类似的reduction method比较。 ### 总结 经典TSP问题，启发式方法， reduction method：改进解？热图？ 手工设计特征真是一点不优雅，深度学习yyds --- ## Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP AAAI 2019 https://github.com/machine-reasoning-ufrgs/TSP-GNN  巴西阿雷格里港 UFRGS 信息学研究所 [](_pictures/Pasted%20image%2020230612142228.png) ### 问题 Decision TSP: Given a TSP instance X = (G, C) composed of a graph G = (V, E) and a target cost C ∈ R， output: 是否有 a Hamiltonian path with cost < C ? ### 模型 图神经网络 输入：点特征V 边特征E 边映射到两端点的矩阵EV，边的初始化：concat(w,C) MLP-> E 更新：MLP轮流更新点特征边特征 分类：边特征经过MLP,输出每条边是对决策问题答案的预测的对数概率。 输出：平均 logits 并转化为概率，二分类，YES or NO  ### 训练 有监督 数据：随机生成TSP instances 用Concorde求出最优解C*  YES NO Loss：二元交叉熵 ### 实验 好  然后关于deviation的不同值和问题规模n做了些实验和分析，不展开了。 ### 总结 dicision TSP似乎比经典TSP问题简单，毕竟是个二分类。 图神经网络的方法，有监督训练，规模不大。 感觉没说新奇的，这能发AAAI? 标签: 组合优化 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭