%0 Journal Article %A 王若愚 %A 陈勇全 %T 基于强化学习的旅行商问题解构造方法 %D %R 10.19678/j.issn.1000-3428.0055910 %J 计算机工程 %P 293-300 %V 46 %N 11 %X 基于迭代局部搜索(ILS)的启发式算法是目前最为先进的旅行商问题求解算法,在多数国际公开算例上保持着世界最优纪录。解构造方法是影响ILS性能的重要因素,为此,提出4种不同的解构造方法。解构造方法1为基准算法,其仅利用城市间的距离等静态结构信息来构造初始解,解构造方法2~解构造方法4则尝试利用搜索过程中积累的历史数据,通过强化学习挖掘有用信息,用于引导解的构造过程。在25个国际公开算例上的测试结果表明,基于历史信息的强化学习方法可有效优化构造解的质量,提升ILS整体性能。 %U http://www.ecice06.com/CN/10.19678/j.issn.1000-3428.0055910