基于强化学习的旅行商问题解构造方法

摘要：

基于迭代局部搜索(ILS)的启发式算法是目前最为先进的旅行商问题求解算法,在多数国际公开算例上保持着世界最优纪录.解构造方法是影响ILS性能的重要因素,为此,提出4种不同的解构造方法.解构造方法1为基准算法,其仅利用城市间的距离等静态结构信息来构造初始解,解构造方法2～解构造方法4则尝试利用搜索过程中积累的历史数据,通过强化学习挖掘有用信息,用于引导解的构造过程.在25个国际公开算例上的测试结果表明,基于历史信息的强化学习方法可有效优化构造解的质量,提升ILS整体性能.

关键词：旅行商问题、迭代局部搜索、解构造、强化学习、过滤网络

所属期刊栏目：46

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;深圳市基础研究项目;住房和城乡建设部软科学研究项目

在线出版日期：2021-01-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：293-300