融合强化学习的分阶段策略求解旅行背包问题

作     者：章政 夏小云 陈泽丰 向毅 ZHANG Zheng;XIA Xiaoyun;CHEN Zefeng;XIANG Yi

作者机构：浙江理工大学计算机科学与技术学院浙江杭州310018 嘉兴大学人工智能学院浙江嘉兴314001 中山大学人工智能学院广东珠海519082 华南理工大学软件学院广东广州510006 

出 版 物：《计算机工程与科学》 (Computer Engineering & Science)

年 卷 期：2025年第47卷第1期

页      面：140-149页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点研发计划(2023YFC3305900,2023YFC3305903) 国家自然科学基金(62206313,61703183) 中央高校基本科研业务费专项资金(2024ZYGXZR097) 广东省基础与应用基础研究基金(2024A1515030022) 浙江省自然科学基金(LGG19F030010) 嘉兴大学“勤慎”青年学者培养计划(嘉院人字12号) 

主　　题：强化学习 旅行背包问题 演员-评论家算法 组合优化 

摘      要：旅行背包问题TTP是传统的旅行商问题和背包问题的结合,属于NP难问题。相较于独立的旅行商问题和背包问题,旅行背包问题更加符合现实情况,具有更高的研究价值。先前的TTP求解算法主要为启发式算法,性能有限,其他类型的算法则研究较少。为了提高TTP的求解性能,提出了融合强化学习的算法,采用分阶段策略。第1阶段根据物品的属性生成物品选择计划,第2阶段利用强化学习演员-评论家(Actor-Critic)算法求解旅行路径,第3阶段引入邻域搜索策略优化所得解。实验结果表明,所提算法在大部分算例上都取得了较好的结果,并且在部分算例上,解的质量超越了其他对比算法,表明了所提算法具有较优的性能。