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

发布时间：2021-07-12 13:44

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

【文章来源】：计算机工程. 2020,46(11)北大核心CSCD

【文章页数】：8 页

【部分图文】：

采用方法3构造初始解的示例过程

图2为采用方法4构造初始解的示例过程(以eil51为例)。值得注意的是,按方法2、方法3与方法4生成初始解后,都需采用局部搜索方法(详见下节)将其优化至局部最优,然后采用与预学习阶段相同的方法更新矩阵W中的元素及变量Num的值,从而实现持续学习。

在TSP上,2-Opt是一个被广泛使用的操作算子,其基本思想是从当前解中删除2条边,然后再添加2条不同的边将其重新连接成合法解。采用2-Opt操作对解进行一次变换的过程如图3所示。如图3所示,给定2个不相邻的城市i和j,删除边(i,i+1)和(j,j+1)后,添加边(i,j)和(i+1,j+1)是让其重新成为合法解的唯一方式,所对应的变换操作即为一个2-Opt操作,其操作复杂度为O(1)。不难发现,给定一个具有n个城市的环路,总共有O(n2)个可能的2-Opt操作。为降低总计算复杂度,选定城市i后,将城市j限定为与城市i距离最近的前10个城市,从而将可能的2-Opt操作数量控制在O(n)之内,通过牺牲优度来大幅提升计算速度。

【参考文献】：
期刊论文
[1]基于文化混合优化算法的旅行商问题求解[J]. 马晗,常安定,陈童,李江杰.  计算机工程与科学. 2019(07)
[2]求解旅行商问题的近似骨架分段蚁群优化算法[J]. 王飞鹏,谭旭杰.  计算机工程与设计. 2019(04)
[3]求解旅行商问题的搜寻者遗传算法[J]. 张立毅,高杨,费腾,王玉婧.  数学的实践与认识. 2019(07)
[4]基于离散粒子群优化算法的含权旅行商问题新解法[J]. 钱真坤.  计算机应用与软件. 2019(01)
[5]基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题[J]. 张子成,韩伟,毛波.  电子学报. 2018(08)
[6]一种混合局部搜索算法的遗传算法求解旅行商问题[J]. 宗德才,王康康.  计算机应用与软件. 2015(03)
[7]求解TSP问题的多级归约算法[J]. 邹鹏,周智,陈国良,顾钧.  软件学报. 2003(01)



本文编号：3280020