计算机工程

作者：王若愚, 陈勇全

单位：1. 深圳供电局有限公司 输电规划科, 广东 深圳 518001;2. 香港中文大学(深圳) 机器人与智能制造研究院, 广东 深圳 518172;3. 深圳市人工智能与机器人研究院 无人系统研究中心, 广东 深圳 518129

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

基金：国家自然科学基金（U1613216）；深圳市基础研究项目（JCYJ20180508162406177）；住房和城乡建设部软科学研究项目（2018-K8-034）。

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

来源：2020年第11期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第11期