基于改进Actor-Critic架构与PPO算法的旅行商问题优化研究：自适应温度调度与综合状态表征的创新方法

本研究针对旅行商问题(TSP)这一NP难组合优化问题，提出了一种集成近端策略优化(PPO)的改进Actor-Critic架构。通过引入自适应温度调度机制、综合状态表征和层归一化技术，显著提升了学习稳定性。实验结果表明，该方法在20-100城市规模问题上相比传统强化学习基线实现了8.7%-55.9%的性能提升，在TSPLIB基准测试中显示出12%-33%的持续优势，为解决物流、电信和制造领域的路径优化问题提供了有效方案。

　　

旅行商问题（Traveling Salesman Problem, TSP）作为组合优化领域的经典NP难问题，在物流配送、电路设计、通信网络规划等众多领域具有重要应用价值。该问题要求在给定一组城市及其相互距离的条件下，找到一条访问每个城市恰好一次并返回起点的最短路径。随着问题规模增大，精确算法面临计算复杂度呈指数级增长的限制，而传统启发式方法又往往需要大量参数调优且泛化能力有限。

近年来，深度强化学习为求解TSP提供了新思路，指针网络、注意力机制和图神经网络等方法都展现出潜力。然而，现有方法仍存在明显局限：自回归模型存在顺序推理瓶颈，计算效率随问题规模增大而急剧下降；图神经网络难以捕捉长程依赖关系；多数强化学习方法在探索-利用平衡方面缺乏系统机制，容易陷入局部最优。这些限制促使研究人员寻求更高效的解决方案。

在此背景下，来自北卡罗来纳农工州立大学计算机科学系的研究团队在《Expert Systems with Applications》上发表了创新性研究成果，提出了一种改进的Actor-Critic架构结合近端策略优化（PPO）的方法来解决TSP问题。该研究通过四个关键技术创新：构建综合状态表征捕获空间、时间和历史访问信息；设计自适应温度调度动态平衡探索与利用；采用课程学习策略逐步增加问题复杂度；使用余弦退火学习率增强训练稳定性。

研究采用的关键技术方法包括：基于PPO的强化学习框架，其中Actor网络负责城市选择策略，Critic网络进行状态价值评估；综合状态表征包含归一化城市坐标、二进制访问向量和最近访问序列；自适应温度调度机制实现从探索到利用的平滑过渡；使用TSPLIB标准基准和随机生成实例进行系统验证。

3.1. Reinforcement Learning Formulation for TSP

研究将TSP构建为顺序决策过程，智能体逐步选择访问城市直至完成完整路径。状态表示包含所有城市的归一化坐标、已访问城市的二进制指示向量和最近三个访问城市的索引。动作空间为选择下一个未访问城市，奖励函数设置为负的欧几里得距离，在完成所有访问后提供基于总路径效率的额外奖励。

3.2. Actor-Critic Architecture for TSP

Actor网络采用三层结构处理状态输入并输出城市选择概率，使用层归一化和ReLU激活函数确保训练稳定性。通过掩码机制强制满足每个城市只访问一次的约束条件。Critic网络采用四层结构评估状态价值，使用LeakyReLU激活和dropout正则化防止过拟合。

3.3. Proximal Policy Optimization for TSP

采用PPO算法确保策略更新的稳定性，通过裁剪替代目标函数限制更新幅度，避免破坏性的大幅更新。价值函数使用均方误差损失，Actor更新包含优势函数和熵正则化项，平衡策略改进与探索鼓励。

3.4. Computational Complexity Analysis

理论分析表明，传统表格方法具有O(n空间复杂度，无法扩展到大规模问题。而神经网络方法仅需O(n)空间复杂度，实现了从阶乘到线性的显著改进。训练时间复杂度为O(E×n²)，推理时间为O(n²)，在实际应用中提供了可接受的计算负担。

3.5. Algorithm Implementation

完整算法包含三个核心组件：改进的Actor-Critic训练流程、TSP状态表征和奖励计算、神经网络架构设计。自适应温度调度采用指数衰减策略，初期鼓励探索（τ=1.0），后期聚焦利用（τ=0.5），实现从广泛探索到精细利用的自然过渡。

实验结果表明，该方法在20-250城市规模的各种问题上 consistently outperforms established reinforcement learning baselines including Q-Learning, SARSA, Double Q-Learning, Actor-Critic with Experience Replay (ACER), and Trust Region Policy Optimization (TRPO)。在20城市问题上，改进方法达到413.30的最佳距离，相比表格方法提升55.9%；在100城市问题上，达到4109.20的最佳距离，相比ACER提升2.0%。在TSPLIB标准测试中，方法在berlin52、eil76、st70等多个实例上表现出显著优势。

4.2.3. Statistical Reliability and Consistency

统计可靠性分析显示，改进方法在大多数问题规模上表现出较低的方差和较高的一致性。95%置信区间分析表明性能优势具有统计显著性，系数变异分析证实了方法的稳定性。

4.3. TSPLIB Benchmark Results

在TSPLIB基准测试中，方法在berlin52实例上达到16994.12的最佳距离，相比ACER提升34.7%；在eil76实例上达到1555.45，相比ACER提升18.3%。这些结果验证了方法在标准测试集上的有效性。

4.7. Ablation Studies and Component Interactions

消融研究揭示了各组件的重要性：改进状态表征贡献最大（30.6%性能提升），PPO裁剪贡献17.2%，自适应温度调度贡献13.4%，层归一化贡献7.8%。组件间存在显著协同效应，联合使用产生27%的额外增益。

研究结论表明，改进的Actor-Critic架构与PPO算法相结合为TSP求解提供了有效框架。方法在解决方案质量和计算效率间实现了良好平衡，既能处理大规模问题，又保持合理的计算需求。自适应温度调度和综合状态表征是性能提升的关键因素，使智能体能够学习空间聚类模式并做出明智的决策路径。

该研究的重要意义在于为组合优化问题提供了新的强化学习解决方案，证明了神经网络方法在解决NP难问题上的潜力。方法在物流规划、通信路由、集成电路设计等领域具有直接应用价值，其设计原则也可推广到其他顺序决策问题。未来工作可扩展到时变TSP、多目标优化和动态环境等更复杂场景，进一步推动强化学习在组合优化中的应用前沿。