一种带泛化性能的动态混合模型求解大范围TSP问题 |
| |
引用本文: | 柯琳,杨笑笑,陈智斌.一种带泛化性能的动态混合模型求解大范围TSP问题[J].系统科学与数学,2024(1):31-44. |
| |
作者姓名: | 柯琳 杨笑笑 陈智斌 |
| |
作者单位: | 昆明理工大学理学院 |
| |
基金项目: | 国家自然科学基金(11761042,12361065)资助课题; |
| |
摘 要: | 旅行商问题(TSP)是组合最优化中的典型问题,求解TSP问题的现实意义重大.随着深度强化学习(DRL)在工业界的广泛应用,利用DRL模型自动设计学习算法成为近期的研究热点.为提升DRL模型在大范围TSP问题上的泛化能力,文章提出一种动态图卷积网络编码和空间注意力机制解码的混合模型求解大范围TSP问题.动态图卷积模块可以动态编码节点信息,从而有效地更新每个节点的隐藏层状态;空间注意力有利于捕捉节点之间的全局联系,进而通过加权所有局部特征计算和提取关键特征.实验结果表明文章模型将TSP50的训练策略泛化至TSP250/500/750/1000时的优化性能超越了先前DRL模型,且在TSPlib标准数据集上的测试结果也显示出模型对优化性能的提升.
|
关 键 词: | 旅行商问题 深度强化学习 动态图卷积网络 空间注意力 组合最优化 |
|
|