导语
外卖派送、物流规划、灭火救灾等机器人调度，本质上都离不开路径优化这类组合优化问题。现实场景中的这类问题规模大、约束多、变化快。计算智能已成为主流工具，其中进化计算等群体智能方法擅长全局搜索，强化学习等个体智能方法更适合从交互中学策略。在集智俱乐部《群体智能读书会》上，贾亚晖老师做了《强化学习路径优化：群体、个体智能协同算法》的主题报告，详细介绍了相关方法。本文我们将先介绍进化计算，以及其在电动车路径优化，多机器人任务分配以及动态交通分问题中的应用。梳理算法的设计思路，并探讨其求解质量与适应性。
关键词：组合优化（Combinatorial Optimization）、车辆路径优化（Vehicle Routing Problems）、进化计算（Evolutionary Computation）、蚁群算法（Ant Colony Optimization）
从组合优化说起
从计算智能到进化计算
蚁群优化算法求解电动车路径优化问题
粒子群算法求解多机器人任务分配问题
遗传编程算法求解动态交通规划的问题
未来的工作方向
1. 从组合优化说起
1. 从组合优化说起
我们在高中阶段都接触过线性规划问题，其目标是在线性约束下求一个线性目标函数的最大值或最小值，决策变量通常是连续的。线性规划是类似的，组合优化的目标也是寻找最值。但其研究如何从有限个离散对象的组合中寻找满足条件的最优方案，决策变量是离散的，典型的问题包括旅行商问题、背包问题与车间调度问题。
在解决这类问题时，我们最初想到的通常是精确的求解方法。如分支定界法，割平面法等精确的求解方法。这些方法通常适用于小规模问题或要求证明最优性的场景。当问题规模大、结构复杂或需要快速求解时，启发式算法是更实用的选择。 启发式方法通常分为两种类型。第一种是解构造方法，即按照某种策略直接构建出一个可行解。第二种是解改进方法，先产生一个质量较差的初始解，然后通过一系列简单而有效的规则对其进行迭代优化。这类规则往往需要借助一定的专家知识来设计，虽然不能保证得到全局最优解，但通常能获得易于理解且效果可接受的结果。
1. 从计算智能到进化计算
1. 从计算智能到进化计算
启发式方法属于计算智能（Computational Intelligence, CI）领域，IEEE计算智能官网对其介绍如下。计算智能是指受生物学和语言学启发的计算范式的理论、设计、应用和开发[1]。计算智能包含三个方面如图1。第一是进化计算（Evolutionary Computation，EC），第二类是神经网络（Neural Networks，NNs），第三类是模糊系统（Fuzzy system，FS）。
图1 计算智能领域知识框架
（1）进化计算方向：以生物进化，种群行为为灵感来源的进化计算通过生成、评估和修改可能解的群体来解决优化问题。该领域涵盖遗传算法、进化规划、进化策略、遗传编程、群体智能、差分进化、可进化硬件、多目标优化等多种方法。
（2）神经网络方向：以人脑为灵感来源的人工神经网络是大规模并行分布式网络，具备从案例中学习并进行概括的能力。该研究领域涵盖前馈神经网络、递归神经网络、自组织神经网络、深度学习、卷积神经网络等多种类型。
（3）模糊系统方向：以人类语言为灵感来源的模糊系统能够对语言的不精确性进行建模，并基于传统逻辑的泛化来解决不确定性问题，使我们能够进行近似推理。该研究领域涵盖模糊集合与系统、模糊聚类与分类、模糊控制器、语言概括、模糊神经网络、二型模糊集合与系统等多种类型。
本文我们主要探讨进化计算方法，这种方法可根据遗传算法分为进化优化与进化学习算法。优化是指直接针对当前问题构建一个优化算法逐步求解。学习是指从多个问题实例中学习一个模型，然后利用模型去求解当前的问题。
进化计算可大致分为如图2所示三类，这与“群体智能”概念紧密相关。首先是受进化论启发的进化算法涵盖遗传算法（Genetic Algorithm，GA）、进化策略（Evolution Strategy，ES）和遗传编程（Genetic Programming，GP）等。其次，受自然界生物群体行为启发的群体智能优化方法，如粒子群优化（Particle Swarm Optimization，PSO）、蚁群优化(Ant Colony Optimization，ACO)和人工蜂群算法(Artificial Bee Colony，ABC)，也属于这一范畴。此外，进化计算还包括差分进化(Differential Evolution，DE)、分布估计算法（Estimation of Distribution Algorithm ，EDA）以及学习分类器（learning classify system，LCS）。其中，GP和LCS更偏向学习算法，其余则为优化算法。这些方法在运筹学中常被统称为“基于种群的方法”。像蚁群优化、粒子群优化属于此类，而遗传编程等可视为“超启发式”方法，旨在自动生成启发式规则。
图2 进化计算概念框架
3. 蚁群优化算法求解电动车路径优化问题
3. 蚁群优化算法求解电动车路径优化问题
自然界中蚂蚁群体在觅食时总能沿着最短路径到达食物源。经研究，蚂蚁觅食时释放信息素，蚁群感知并跟随高浓度路径行走，每只蚂蚁也会留下信息素。这种正反馈机制使蚁群逐渐聚集到最短路径，从而高效到达食物源。受到这一现象和机理的启发。意大利学者Marco Dorigo于1992年在其博士论文中首次提出蚁群算法，将蚂蚁觅食过程中依赖“信息素”进行路径选择的行为抽象为一种高效的启发式优化算法。其中最关键的两步，第一步是构造解。一只蚂蚁将从节点i到节点j，其概率如下式（1）。
其中τij是边i→j上的信息素总量，代表“过往经验”的积累。
α：控制信息素影响力的参数。α越大，算法偏向利用已知优质路径；α越小，算法更爱探索新路径。
ηi,j：边i→j的启发式吸引力。
β：控制启发式信息影响力的参数。β越大，算法更聚焦局部最优；β越小，算法更依赖全局经验。
第二步为更新解。边i→j的信息素更新如下式（2）。
其中τij：更新后，边i→j的信息素总量。
ρ：信息素蒸发率(0<ρ<1)，表示信息素自然消散的比例。
Δτi,j：本轮迭代中，所有蚂蚁在边i→j上沉积的信息素量，其计算公式如下式(3)。
其中Lk是第k只蚂蚁在本轮迭代路程。
图3 电动车车辆路径优化问题示意图
车辆路径问题（Vehicle Routing Problems，VRP）是组合优化中一个极其重要且应用广泛的经典问题，也是供应链管理中最具代表性的实际难题之一。它旨在为一组车辆设计最优的行驶路线，以服务多个客户点，在满足各种约束（如载重、时间、距离）的前提下，优化总成本、车辆数或行驶距离等目标。复杂的模型还要考虑送货时间，例如客户要求只能在上午或下午送货等约束条件。电动车车辆路径优化问题（Electric Vehicle Routing Problem，EVRP）是VRP问题的子问题，载有一定量货物的电动车从仓库出发，服务所有客户点。为一个电动车辆车队规划行驶路线，在满足载重与电量双重约束下，决定下一个客户的目的地。最终的解是车辆寻找服务顺序与充电规划，以最小化总成本，其最基础的目标仍是最小化总行驶路程。
将约束条件分开后，这个问题可以拆分为两个子问题。第一个是传统的容量限制车辆路径问题（CVRP），它考虑了车辆的容量约束，但不涉及充电。另外一个是固定路线车辆充电问题（FRVCP），在给定路线的情况下，选择最佳的充电策略。 可以简单地认为这两个问题是相加的。然而，如果按照加法的方式，先解决CVRP再解决FRVCP，无法保证得到最优解。
图4 BACO算法结构
传统容量限制车辆路径问题（CVRP）已有丰富研究，在此基础上，文献[2]提出一种如图4所示的BACO双层蚁群优化算法。对应两个层级的子问题，BACO生成一个可行解需要两个步骤。首先，通过移除电量约束和充电站，将CEVRP降级为对应的CVRP。仅考虑配送中心和客户，应用OS-MMAS算法来生成对应CVRP的容量可行路径。然后，在给定容量可行路径的基础上，将电量约束纳入考虑。为固定路径寻找最优充电调度的问题被称为FRVCP。为了有效且高效地解决FRVCP，文章提出了移除启发函数，RH算法。下层RH算法为上层OS-MMAS生成的路径找到充电方案后，计算得到完整CEVRP解的目标值（总行驶距离），并用此反馈信息来更新上层ACO的信息素，从而引导蚁群在未来迭代中向更优的客户服务顺序搜索。算法在搜索结束后，采用一种限制性枚举方法对全局最优解中的每条路径进行精细化搜索，以进一步提升充电方案的质量，返回全局最优解。
图5 移除启发执行示意图
移除启发函数通过两阶段操作确定充电位置。在插入阶段，为路径中每一对连续节点插入带来最小额外行驶距离的充电站，确保路径满足电量约束。随后在移除阶段，逐个检查已插入的充电站，若移除后路径仍满足电量约束，则记录其可节省的距离；最终移除可节省距离最大的充电站。重复此过程直至无充电站可移除，输出电量可行的最终路径。示例如图5所示，假设从零号仓库出发，经过一号、二号、三号和五号顾客，最后再返回仓库。在每两个点之间添加三角形充电站。在完成充电站的添加后，逐一删除那些不必要的充电站，或者是距离太远的充电站。这其中涉及到一些策略判断。经过删除后，得到了一个包含充电决策的最终路径，这条路径还包括服务这些顾客的顺序。充电次数最多不会超过四次，问题规模较小时，直接进行穷举实际上是可行的。
图6 ACO算法结果
图6是文中ACO算法的一些结果，已经取得了不错的效果。然而，ACO算法存在一个致命的缺点：首先，它的参数调节非常困难；其次，它的运行速度极慢。单靠群体算法本身，如果不添加大量的局部搜索，算法的运行速度会非常缓慢。 因此，文中加入了许多局部搜索，这是一种在求解CVRP问题时表现优秀的优化算法，称为HGS（Hybrid Genetic Search）。从结果来看，这个HGS算法的优化速度明显快于文中ACO方法。
4. 粒子群算法求解多机器人任务分配问题
4. 粒子群算法求解多机器人任务分配问题
多机器人任务分配（Multiple Robot Task Allocation，MRTA）问题是为多种任务调配足够数量的机器人。问题的目标是为每个机器人找到执行时间（完成时间）最短的最优计划。约束有机器人随时间变化的约束、机器人能力约束以及机器人间的协作方式约束等。
图7 多机器人救火场景任务分配问题
如图7所示，在救灾场景中，如果某个地方发生火灾，单个机器人可能无法扑灭大火，这时就需要一群机器人共同协作来完成救援任务。 在任务执行中，参与的机器人越多，任务完成的速度也会越快。我们的目标是调度一群机器人，完成分散在地图上的动态任务。这里的“动态”指的是任务量会不断增加。
PSO算法适用于上述问题。PSO算法的提出者是一位心理学家。他观察到鸟类觅食时的行为，发现鸟类在寻找食物的过程中，会记住曾经找到食物的地方，并继续探索其他区域。此外，鸟群之间会共享信息。这些观察促使算法的设计者制定了简单的更新公式。
图8 粒子群算法示意图与流程图
PSO算法的框架步骤仅有三步。首先生成初始的粒子群，评价其适应度，不断更新粒子群的速度与位置直到算法收敛。在PSO算法中，每个个体（或称鸟）代表一个解，位于问题空间中的一个点。这只鸟的下一步探索方向是如公式（4），个体的速度向量由以下几个部分组成：第一部分是原始速度和一个惯性权重的结合；第二部分是鸟之前发现的优质解的引导；第三部分则是整个种群曾经找到的最优解的引导。通过将这三个向量相加，便得到了新的速度向量。个体的新位置则是当前的位置加上更新后的速度，如公式（5）。PSO算法最初是为了求解连续优化问题而设计的，公式中主要是加、减、乘的运算。
然而，PSO算法本身只是一个框架，并不局限于连续优化。文章[6]考虑每个解X都是一个集合。只需定义实数与集合的乘法、集合之间的减法和加法，便可实现组合优化的求解。 在多机器人任务分配的问题上，文章进一步增加了难度，引入了任务点之间的依赖关系。这使得问题变得更加复杂。
在完成一个进一步升级的任务后，文献[5]提出了一个更加简化且适用于路径优化的算法，多阶段粒子群优化算法（multi stage PSO，MSPSO），这种算法主要是基于减法。以排列问题为例，x1代表第一个机器人依次完成一号、二号、三号和四号任务，而x2则代表这个机器人完成三号、十三号任务后，再执行一号、二号和四号任务。这两个序列的差异可以通过直接将它们视为实数进行减法运算。经过计算，得到的结果是-2，1，1，0。为了处理负数，将所有负值归零，这就是文中定义的离散减法。文中将正数的元素向前移动。例如，原来的序列3124，经过x1减去x2的运算，得到的就是x2，能将2和3互换，再将1和2互换。会发现加法便是将元素向前调整。这样，路径就相应地改变了。 通过重新定义减法和加法，便得到了一个新的粒子群算法，可以用于路径优化。
图9 MSPSO算法加减法规则
下图10是最终的优化结果。左边显示文中提出的这个多阶段粒子群优化算法的效果非常显著。右边展示的是一个实例，12个机器人完成众多任务。该图展示每个机器人先执行几号任务，再完成几号任务。显而易见，MSPSO算法最终得到的解比遗传算法要短得多，整体安排更优。此外，MSPSO还展现了更丰富和合理的多机器人协作完成一个任务的情况。
图10 MSPSO算法优化效果
5. 遗传编程算法求解动态交通规划的问题
5. 遗传编程算法求解动态交通规划的问题
前面提到的两个优化算法可以视为元启发算法的一种，而现在要提到的遗传编程则是一种超启发式方法。遗传编程通常不用于求解信息完全已知的静态问题，而是更适用于动态或不确定的环境，其目标是生成一种能够实时调整的策略，而非一条固定路径。例如，快递员在取件时若遇到客户提交信息与实际不符，原定路线可能不再最优。此时需要的是能即时响应变化的决策策略，而遗传编程正是为了自动生成这类适应性策略而设计的算法。
图11 任务树形结构
如遗传编程算法结构如图11所示树形结构来展示。下方是一个数学表达式，它代表了遗传编程中一个解的调度规则。 在这个表达式中，X和Y可以视为某个任务的特定属性。最终计算得出的值，可以理解为优先级。 输出值通常是路由调度问题中候选者的优先级。值越大越大优先级越高，反之亦然。因此，这个过程就变成了一个学习任务。 我们可以使用一些生成的训练实例，输入到遗传编程算法中，从而生成这样的模型即调度规则。最终，我们可以把这个调度规则应用到其他相似的动态环境。
利用遗传编程求解去求解中心化动态交通分配问题（Decentralized Dynamic Traffic Assignment，DDTA）以一个有关动态交通规划的问题。在这个问题中，文献[6]设想了一个分布式的场景。是一个去中心化的系统，每辆车根据自身所处的环境和后续路径，自主决定应该选择哪条路。在静态路径的交通分配中，交通流量是固定的，并且与时间无关。 这种情况可以通过一些静态优化算法来求解，比如整数规划、线性规划或遗传优化算法等。 然而，动态交通流则可能与时间相关，且往往是混乱的。 因此，这种情况下只能采用一些学习方法进行求解。
文献中动态交通分配问题的目标是最大化在特定时间段内完成行程的车辆数。车辆在当前位置u，需要经过节点vi去到目的地。选择使 “从u到vi的实时距离D” 加上 “从vi到目的地Ak的预估成本S” 总和最小的节点，如公式（6）。这不同于最小化单车旅行时间，而是强调路网的整体吞吐量和效率，是系统最优的体现。文章在公式（6）的基础上增加了一个惩罚项，这个惩罚项可以通过除以或乘以某个值来实现，两者效果相同。文章希望利用遗传编程的方法来优化这个惩罚项。 因此，设计了这样的一个Simulator，下图12展示了一份标准的遗传编程程序。 在最终的优化过程中，成功地将公式中惩罚项进行了优化。
图12 动态交通分配问题
优化完成后，就学习到最终的问题求解模型。将其与一些经典算法进行了多次对比。在不同的网络和路网结构上，包括人流和车流的模拟，文中进行了系列实验。 结果显示，利用遗传编程算法优化的调度规则，能够使整个系统的运行更加流畅。
图13 遗传编程与其他方法效果
6. 未来的工作方向
6. 未来的工作方向
使用进化计算来求解组合优化问题已经非常成熟，本文介绍了三种进化计算求解组合优化问题的实例。前两个问题通过改进经典的进化优化算法求解，第三个问题则设计遗传编程这类基于学习的算法求解。这些方法可以视为一个框架，即先使用群体智能算法作为求解架构，然后再设计一系列与问题相关的启发式或局部搜索方法加入其中。 由于方法论已趋于成熟，大多数研究者的工作集中在寻找新的现实应用问题上。与强化学习结合形成的演化强化学习（ERL）也具有很大的潜力，下一章我们将进行强化学习求解方法，以及演化计算与强化学习结合方法的介绍。
参考文献
1. What is Computational Intelligence？
2. Jia Y H , Mei Y , Zhang M .A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem[J].IEEE transactions on cybernetics, 2022.DOI:10.1109/TCYB.2021.3069942.
3. Jia Y H , Mei Y , Zhang M .Confidence-Based Ant Colony Optimization for Capacitated Electric Vehicle Routing Problem With Comparison of Different Encoding Schemes[J].IEEE Transactions on Evolutionary Computation, 2022, 26:1394-1408.DOI:10.1109/TEVC.2022.3144142.
4. Gao, Guanqiang, Yi Mei, Ya-Hui Jia, Will N. Browne, and Bin Xin. "Adaptive coordination ant colony optimization for multipoint dynamic aggregation." IEEE Transactions on Cybernetics 52, no. 8 (2021): 7362-7376.
5. Dai S H , Jia Y H , Chen W N ,et al.Multistage Particle Swarm Optimization for Heterogeneous Multipoint Dynamic Aggregation[J].Systems, Man, and Cybernetics: Systems, IEEE Transactions on, 2025, 55(7-Part1):4614-4628.DOI:10.1109/TSMC.2025.3553553.
6. Liao, Xiao-Cheng, Wei-Neng Chen, Ya-Hui Jia, and Wen-Jin Qiu."Towards scalable dynamic traffic assignment with streaming agents: A decentralized control approach using genetic programming."IEEE Transactions on Emerging Topics in Computational Intelligence8, no. 1 (2023): 942-955.
7. Citation: X. -C. Liao, Y. -H. Jia, X. -M. Hu and W. -N. Chen, "Uncertain Commuters Assignment Through Genetic Programming Hyper-Heuristic," in IEEE Transactions on Computational Social Systems, vol. 11, no. 2, pp. 2606-2619, April 2024.
群体智能读书会
如果你对这些反直觉但极有用的现象感兴趣——从蚁群搭桥、鱼群同步、到无人机集群表演、集群机器人协作、群智优化与多智能体系统、网络舆论建模研究等——欢迎加入「群体智能」读书会：我们用动物—人类—机器三条线，希望把群体智能的涌现这件事讲清楚、讲透彻；用物理学、数理逻辑、多主体建模、计算传播等多学科视角，去追问同一个核心：集群何以比个体更聪明？群体智能又在何时涌现？
集智俱乐部联合北京师范大学系统科学学院韩战钢教授、暨南大学计算传播研究中心赵甜芳副教授、新疆大学物理科学与技术学院玉素甫·艾比布拉副教授等来自11所高校的学者，共同发起本次「群体智能」读书会，尝试用一条普适的线索，把自然界的鸟群蚁群、人类社会的集群行为、以及人工智能时代的多智能体与群智优化，放在同一张地图上重新理解。读书会现已结束，欢迎所有对群体智能如何涌现、如何被理解、以及如何被设计，感兴趣的朋友加入读书会，查看回放。
