摘要
旅行商问题(Travelling Salesman Problem, TSP)作为经典的组合优化问题之一，它在实际生活中具有重要的理论研究价值和广泛的应用意义。随着人工智能技术的不断发展，深度强化学习在工业自动化、游戏智能等领域被广泛应用。不同于传统求解方法往往受到问题规模和复杂度的限制，深度强化学习将具有表征能力的深度学习和具有决策能力的强化学习相结合，能够更好地适应复杂环境和大规模数据，具有较强的泛化能力。因此，诸多学者探索利用深度强化学习解决组合优化问题，这为求解旅行商问题提供了新的思路。基于此，本文以深度强化学习为切入点，针对单旅行商问题和均衡多旅行商问题(Balanced Multiple Travelling Salesman Problem, BMTSP)进行研究。 针对基于指针网络的深度强化学习算法求解旅行商问题中，策略网络和价值网络的编码器都采用了复杂的长短期记忆网络结构(Long Short-term Memory, LSTM)，这在求解大规模旅行商问题时造成训练时间过长的问题。考虑到作为输入结点之间位置顺序的无关性，本文对指针网络中编码器的循环神经网络进行修改，将策略网络和价值网络编码器中长短期记忆网络都替换为一维卷积神经网络，提出了一种改进的基于指针网络的深度强化学习算法。改进的指针网络可以降低计算复杂度和提升模型的效率，并且明显提高了模型的准确度。在训练阶段，本文采用带基线的 REINFORCE 算法训练策略网络参数。为进一步降低方差并加快收敛速度，本文对策略梯度中基线进行估计，引入含有参数的价值网络作为基线。 针对单旅行商问题，利用本文提出的改进指针网络的深度强化学习算法，对深度强化学习中策略网络与价值网络同步训练，利用策略网络生成的概率分布形成完整的路径，根据策略网路得到价值网络的估计值，计算损失函数并采用梯度下降方式修改策略网络参数，寻找最优路径。针对路由分配过程中既要求总路径最小又要求每位旅行商路径均衡，本文提出在任务分配均衡条件下，优化多旅行商问题，依据策略网络计算子路径的总和，采用梯度下降方式修改策略参数，寻找均衡条件下的最优总路径。 在实验阶段，本文分别对不同旅行商问题进行数值实验，并且将实验结果与原指针网络模型以及现有的启发式算法进行对比。实验结果表明，改进模型算法与原模型在求解单旅行商问题结果上并无明显差别，但训练时间比原模型降低了 12%~15%。此外，针对均衡多旅行商问题，改进模型的实验结果均优于大多启发式算法，对比结果验证了改进模型的有效性。
NETL