导语
求解路径优化这类组合优化问题，进化计算是非常成熟的方法，优势在于其较强的鲁棒性，但是其缺点在于效率较低且理论并不完备。基于学习的方法难于泛化。传统的深度强化学习具有很高的适应性、探索能力和开发能力。 然而，不足之处在于设计奖励函数极为困难且探索能力相对较弱。 结合两者的优点，进化算法融合强化学习形成新的求解方式范式，是当下的正在蓬勃发展研究方向。基于此前集智俱乐部《群体智能读书会》贾亚晖老师做的《强化学习路径优化：群体、个体智能协同算法》的主题报告，本文详细介绍了上述方法。
关键词：车辆路径优化（Vehicle Routing Problems）、神经求解器（Neural Solvers）、强化学习（Reinforcement Learning）进化计算（Evolutionary Computation）、进化强化学习（Evolutionary Reinforcement Learning）
刘向宇丨作者
目录
从神经组合优化说起
提升强化模型的泛化能力
进化强化学习
未来展望
1. 从神经组合优化说起
神经组合优化（Neural Combinatorial Optimization，NCO）是一个很大的领域，这个领域的核心是训练一个神经求解器来解决组合优化问题。 在这个过程中，可以采用强化学习的方法进行训练，也可以使用监督学习的方法来实现优化。本文采用的是强化学习方法。流程如图1。
图1. 强化学习方法基本流程
首先，需要提供大量的训练数据。这些数据包含了问题的特征，然后设定一个基于深度强化学习的方法。最终会得到一个深度模型，这个模型可以用于解决其他相似的问题。 如图2，强化学习的基本框架通常包含智能体（Agent）、环境（Environment）和奖励（Reward）。其中，智能体可视为我们训练的模型，它根据当前环境状态选择动作，并与环境交互。环境则反馈下一个状态和相应的即时奖励。强化学习的目标是最大化累积奖励，为此有一系列算法用于优化智能体的决策策略。
图2. 强化学习训练示意图
神经组合优化方法大致可分为构造式、改进式和预测式三类，如图3所示。本文主要集中于构造式方法。其核心思想是训练一个深度模型，使其能够像贪心策略一样，在求解过程中逐步决策下一个要访问的点（例如，每次选择距离当前点最近的未访问点），从而逐步构造出一个完整解。具体过程如下，在训练阶段，模型基于Transformer架构（如多头注意力机制）进行学习，输入训练数据（每个数据点包含坐标、需求等特征）并输出对应的概率分布。在推理阶段，针对新输入的问题，借助束搜索等技术生成最终解。该框架一旦构建完成，具有较好的通用性，无需针对不同问题频繁调整算法或复杂调试。
图3. 神经组合优化方法分类
与依赖专家知识设计算子的进化计算不同，强化学习方法能在充足算力下自主学习，最终得到一个有效求解器。但其缺点在于可扩展性差。训练好的模型通常只能处理与训练集规模相近的问题。例如，基于100个点数据训练的路径优化模型，难以直接用于1000个点的场景。而许多传统优化方法一旦参数设定，可灵活处理从10到1000等不同规模的问题。因此，规模泛化是神经组合优化需要解决的核心挑战之一。
2. 提升模型的泛化能力
提升神经组合优化模型跨规模时的泛化能力主要有两种思路：一是将专家知识用于引导神经网络的特征学习，使其更好地捕捉与规模无关的通用规律，如下图4(a)；二是将专家知识嵌入神经网络结构，例如在Transformer解码阶段引入辅助网络，以增强模型在大规模问题上的决策合理性，如下图4(b)。
图4. 提升神经求解器泛化能力方法
值得注意的是，贪心算法每一步决策仅选取当前最优解，虽简单却在许多场景中表现良好，文章[1]提出一种结合贪心经验的改进神经求解器（Distance-aware Attention Reshaping，DAR）。首先训练了一个规模为一千的神经求解器。从结果来看，高分的点非常有限。每次选择下一个点时，得分超过零分的高分点几乎没有，只有少数几个得分较高的点。接着，将其放置在另一个分布上进行测试。第一次，在一个均匀分布的地图上寻路，而后来文章又尝试了一种叫做"cluster"的分布。结果发现，高分的点明显增多。 然而，如果给出的选择过多，有时也会导致选择困难症。这个神经求解器也是如此，当高分的点太多时，它就会陷入选择困难。增加密度并将平均分从100提升到1000。经过这一调整，在处理规模为一千的问题时，高分点的数量显著增加，实验结果如图5。但即便如此，求解器在这种规模下，每次做出的决策仍然只是一部分理智，无法达到最优方案。 这种现象被文章称为"注意力分散"（attention dispersion）。
图5. 不同规模节点数据训练结果
当问题规模扩大时，原本在小规模数据上训练的神经求解器会出现这种"注意力分散"。具体表现为，可供选择的高分点数量激增，且这些点的得分分布趋于平缓，导致模型难以做出清晰、可靠的决策。可视化分析发现，模型学到的主要是方向偏好，而非精确的距离信息，这使其在面对新分布时产生混乱。文章没有选择设计更复杂的模型，而是采用了一种直接且基于经验的策略。将贪心思想作为先验知识植入注意力机制，如下图6所示。具体做法是在原始注意力分数上，叠加一个基于距离的调整项（如使用对数函数），使得离当前点更近的候选点获得更高的分数加成。
图6. 专业知识整合为一个训练好的模型
将贪心作为一种矫正方法来调整注意力分数这完全依赖于人类的经验。 经验告诉我们，选择下一个更近的选项大概率是正确的。 虽然它可能不是最优解，但通常也是最好的选择。 将这个理念作为指导思想，交给神经网络，让它在学习过程中带着这个思想。
如上式（1）文章对后面的注意力分数进行了调整，将等于ai加bi。 其中，ai代表原始的注意力分数，而b则是文章设计的距离分数。文章如式（2）用对数（log）的方式来设计这个距离分数。离得越近，分数越高。离得越远，分数越低。式（3）到（6）证明了DAR可以降低概率分布的熵，即缓解注意力分数分散的问题。这也解释了为何选择log是如此重要的原因，背后的逻辑同样非常有趣。
下图7内容解释了选择负log的原因。 在计算每个点被访问的概率时使用的softmax本身是一个指数函数。通过添加负log后，最终会转化为一个常数。使用负log时，它既不会变成贪心策略，也不会因为问题规模的增大而失去效用。无论问题的规模多大，在使用负log的情况下，专家信息和神经网络自身学习到的信息都会发挥作用。
图7 推导过程
文章进行了进一步的实验来深入探究，结果发现上述方法表现更佳。 从图8结果中可以看出，右下角能看出文章提出的方法能够轻松找到一些高分点，但这些高分点的数量明显少于之前那些方法所找到的高分点数量。
图8 推导过程
解决了跨规模泛化的问题，接着文章[2]探讨了能否开发出一个跨问题的求解器。如同时求解车辆路径问题（VRP），还包括旅行商问题（TSP）。其实验也证明了，采用文章提出的"软"的训练方式在多任务场景下是有用的，具体方法内容可以参考文献[2]。
3. 进化强化学习
本系列文章探讨的一个重要主题就是个体智能与群体智能的协作范式。经过多年研究，进化计算应用与神经网络优化取得不错的效果。进化强化学习就是个体智能与群体智能的协作的一个重要方向，架构如图9。进化强化学习（ERL）经过几年的发展主要可以分为三类。 第一类是利用进化计算辅助强化学习。在这种范式中，强化学习是主体，而进化计算则负责生成多样性的动作或优化某些参数。 第二类是利用强化学习优化进化计算。在这种情况下，进化计算仍然是求解问题的主要部分，使用强化学习来调整进化计算的参数，或者将进化计算的一些组件视为动作，利用强化学习自适应生成最适合当前问题的进化计算方法。 第三类称之为"合成优化"（synthetics optimization），在这种方式下，进化计算和强化学习都在执行相似的任务，目的是获得一个求解器，并且两者之间可以互通信息。本节探讨第三类方法。
图9. ERL框架
首先介绍 Synergy（协同结合）的概念。将深度强化学习与进化算法相结合的原因在于一方面，传统深度强化学习具有较强的适应性和开发（exploitation）能力，其理论基础十分扎实，例如贝尔曼最优理论及相关 ODR 理论已经在理论上证明了算法的有效性与收敛性。另一方面，传统深度强化学习也存在明显的不足。奖励函数的设计极为困难，回报函数的构造复杂；同时，其探索能力相对较弱，训练过程不够稳定。一旦探索方向出现偏离，由于通常只采用单一的决策网络结构，后续的训练很容易陷入不稳定状态。
相比之下，进化算法（EA）方法的优势在于其较强的鲁棒性。它采用的是种群形式进行搜索，这意味着它不像传统方法那样依赖单一个体，而是像集群兵团一样进行探索。这样的设计更具探索能力且不关注中间状态的细节。尽管在实际应用中表现良好，不过也有效率较低的缺点。由于是基于种群搜索，其随机性虽然有助于探索，但也导致搜索时间较长且资源消耗相对较大。并且进化计算的理论并不完备。虽然一些经典方法的收敛性已经被证明，但许多其他方法在理论上尚缺乏充分的验证。将其与深度强化学习结合，有望形成一种新的范式。
图10. 进化计算结合强化学习
上图10展示了进化计算与强化学习的结合方式。左边代表进化计算。它涉及一个种群，有一个评估机制evaluation。这个评估可以视作后面提到的环境（environment）。在这个群体中，每一个解的适应值都将被评估。根据这些适应值，进行选择（selection）、交叉（cross over）和变异（mutation），从而生成新的种群，并不断迭代。最终，输出整个过程中找到的最优解。 中间展示了强化学习的actor-critic算法。
Actor负责生成动作，而critic则评估当前策略的优劣，评价每个动作的效果。可以这样理解，它们与环境互动以获取经验，并将这些经验用于训练和再训练，这就是强化学习的基本过程。右边代表进化强化学习计算。进化计算的左侧代表进化计算部分，右侧则是其他学习部分。它们共享经验值（experience）。相较于强化学习的一个actor，进化强化学习种群中有一群actor。 这个种群的进化依然通过选择、交叉和变异的方式进行，而不是依靠原来的梯度方法（policy gradients）。进化计算的算子用于更新个体，同时这些个体产生的经验被注入经验池，供强化学习个体学习。这样，强化学习便能借助一批经验丰富的"老师"获得更多样本。经过一段时间的学习，强化学习的actor也可将其成果同步回种群，成为其中一员，从而实现群体与个体之间的双向经验共享。然而，问题随之而来，群体产生的经验对强化学习个体是否总是有用？答案显然是否定的。好比在一个班级里，既有优秀学生也有表现较差的学生，你自然会优先向优秀者学习，而不是照单全收。这就引出了两个关键问题。
图11. 经验不匹配与前提失效问题
如上图11所示，首先是经验不匹配的问题。具体来说，就是EA所产生的经验与RL所需的经验不一致。 第二个问题被称为"前提失效"。这个概念是什么意思呢？在大家探索新环境的初期，比如在自动驾驶的场景中，最开始的策略网络尚不成熟，车辆常常会发生碰撞。如果这些初始的经验被反复学习，它们将对后续的学习过程产生负面影响。一旦你加入了一个群体，最初大部分成员的表现也是失败的。这些失败的经验会不断累积，从而影响到后续的强化学习训练。
图12. SERL-OS-EF算法框架
文献[3]提出SERL-OS-EF算法，如图12所示。算法首先设计了一个策略，采用了算子选择的方式。具体来说，对于不同的actor种群中的不同actor，文章选择不同的进化算子进行进化。我们的目标是确保每个个体都能有所提升，而不仅仅关注个别表现最好的个体。如下图13所示算子选择：设计一个套娃式的结构。使用另一种更简单的强化学习进行算子选择，并将其应用于种群中的不同个体，以提高性能和多样性。原本只是使用强化学习，在其中加入了进化计算就变成了进化强化学习。在进化计算的操作符选择部分，又嵌入了在线强化学习，层层嵌套。 文章使用了PPO这样的强化学习方法，来完成进化计算部分的操作符选择。 经验过滤的道理其实也很简单。以最好的个体作为参考标准，对于那些表现差于最佳个体百分之百的个体，我们就不再考虑它们产生的经验。这里强调的是经验，而不是个体本身。
图13. 算子选择
即便如此，由于随机性的存在，个体之间仍然会有差距。因此，文章设置了一个经验过滤器，剔除那些表现过于差劲的经验，不再使用每一代中较差的经验，以应对动作的多样性。如下图14所示，经验过滤器将比最优个体差 beta% 以内的个体加入回放缓冲区。针对生成的大量异构Actor，文章将其置于特定状态下执行动作。根据行为模式的相似性，文章将这些Actor的输出进行聚类。由于在相同状态下同类Actor的策略趋于一致，我们仅需从每个类别中选取代表性个体生成经验即可。这就好比解题时，若全班三分之一用方法A、三分之一用方法B、剩下用方法C，我们无需让所有人分享，只需从A、B、C三组各选一位代表讲解其思路，便足以覆盖所有的解决方案。
图14. 经验过滤器
最后，文章引入了动态混合采样策略。在经验池中，文章区分了种群的经验和个体强化学习所产生的经验，不将它们混合在一起。这种区分使得个体在不同阶段可以选择更多地自学或参考群体的经验。如下式（7），来自种群的体验与强化学习智能体的体验分开存储。式（8）则说明在早期阶段，强化学习智能体自身贡献更多以保证稳定性；在后期阶段，种群贡献更多以增加多样性。
4. 未来展望
结合上一篇关于进化计算求解路径规划问题的文章总结一下这两篇的工作。利用进化计算求解组合优化问题（COP）已相当成熟，相关方法多属于群体智能或基于种群的算法。这类方法通常作为一个框架，再融入问题相关的启发式或局部搜索策略。另一个较新的方向是结合学习方法，例如自动选择合适的算子来解决特定问题，甚至引入大模型。强化学习（RL）在组合优化领域仍是热门方向，但深度强化学习的训练成本较高。目前的工作主要围绕改进神经网络架构展开，竞争激烈，类似于当年对各类基准测试模型的不断优化。因此，越来越多研究者开始将强化学习与组合优化问题及其他学习范式相结合。单靠传统基准测试已难以脱颖而出，结合大模型的方法有望带来更强的泛化能力和语义理解能力。
进化强化学习（ERL）仍有很大潜力。尽管已发展十余年，但进展较慢，仍是一片蓝海。ERL 的挑战在于它结合了进化计算和深度强化学习的随机性与高成本。目前测试环境多为小规模仿真任务（如模块化仿真或迷宫问题），训练的网络规模也较小，通常只有四到五层，隐含层维度在 256 到 512 之间。进化计算本身也在努力求解大规模参数优化问题，尤其是百万到千万级参数的优化。ERL 仍有许多可探索的方向。一是扩大规模，包括策略网络和训练网络的复杂度；二是寻找更多应用场景，目前 ERL 研究多集中在基准测试和仿真上，真实环境中的应用尚需深入探讨（如与能源调度相关的实际任务），研究 ERL 是否在复杂决策环境中优于传统深度强化学习。三是结合进化计算的强大能力，如多目标优化等，这些都是未来的研究方向。
参考文献
1. Wang Y , Jia Y H , Chen W N ,et al.Distance-Aware Attention Reshaping for Enhancing Generalization of Neural Solvers[J].IEEE Transactions on Neural Networks and Learning Systems, 2010, 36(10):15.DOI:10.1109/TNNLS.2025.3588209.
2. Wang Y , Jia Y H , Chen W N ,et al.Soft Parameter Sharing Model for Cross-Problem Generalization in Vehicle Routing Problems[J].IEEE Transactions on Artificial Intelligence, 2026(1):7.DOI:10.1109/TAI.2025.3576336.
3. Cai Q , Jia Y H , Zheng K ,et al.Evolutionary Reinforcement Learning With Late-Start Evolution and Clustering Archive[J].IEEE Transactions on Evolutionary Computation, PP[2026-06-03].DOI:10.1109/TEVC.2025.3627631.
群体智能读书会
如果你对这些反直觉但极有用的现象感兴趣——从蚁群搭桥、鱼群同步、到无人机集群表演、集群机器人协作、群智优化与多智能体系统、网络舆论建模研究等——欢迎加入「群体智能」读书会：我们用动物—人类—机器三条线，希望把群体智能的涌现这件事讲清楚、讲透彻；用物理学、数理逻辑、多主体建模、计算传播等多学科视角，去追问同一个核心：集群何以比个体更聪明？群体智能又在何时涌现？
集智俱乐部联合北京师范大学系统科学学院韩战钢教授、暨南大学计算传播研究中心赵甜芳副教授、新疆大学物理科学与技术学院玉素甫·艾比布拉副教授等来自11所高校的学者，共同发起本次「群体智能」读书会，尝试用一条普适的线索，把自然界的鸟群蚁群、人类社会的集群行为、以及人工智能时代的多智能体与群智优化，放在同一张地图上重新理解。读书会现已结束，欢迎所有对群体智能如何涌现、如何被理解、以及如何被设计，感兴趣的朋友加入读书会，查看回放。
详情请见：生物、机器与社会的群体智能——11所高校联合发起的群体智能读书会
推荐阅读
2. 突破四十年"排序障碍"：清华团队提出寻找最短路径新方法
3. 自然 · 通讯：网络不只是"小世界"，社群结构让最短路径变得"选择困难"
4. 大语言模型智能体社群中的涌现关系秩序：从集体情感到权威分层丨Vibe Modeling读书会第四期
5. 9900分可兑换"涌现"文化衫，报名任意读书会送299积分！
6. 集智学园精品课程免费开放，解锁系统科学与 AI 新世界
点击"阅读原文"，报名读书会
登录后才可以发布评论哦
打开小程序可以发布评论哦