一种基于多粒子群协同演化的人车混合疏散仿真优化方法

摘要

本发明提供了一种基于多粒子群协同演化的人车混合疏散仿真优化方法，主要通过粒子群优化算法解决大型建筑物和路网集成环境中的人车混合疏散问题，利用粒子的运动过程模拟疏散个体，包括人员、车辆的混合疏散过程，并且采用基于信息素的多粒子群通信机制模拟人员和车辆之间的交互和信息共享，克服了粒子群算法只考虑了粒子之间的交互而忽略了环境对粒子运动过程的影响等不足，能够更好地模拟人车混合疏散过程中不同交通对象的竞争和协作，形成满足多个目标需求的疏散优化方案，提供合理高效的决策依据。

说明书

技术领域

本发明属于智能计算和运筹学的交叉应用领域，具体地说是一种基于多粒子群协同演化的人车混合疏散仿真优化方法，主要通过粒子群优化算法解决大型建筑物和路网集成环境中的人车混合疏散问题，利用粒子的运动过程模拟疏散个体，包括人员、车辆的混合疏散过程，并且采用基于信息素的多粒子群通信机制模拟人员和车辆之间的交互和信息共享。

背景技术

大型建筑物和路网集成环境下的人车混合疏散问题就是将紧急情况下聚集在大型建筑物中的大量人员从事发地建筑撤离并进入周边路网，与路网中的移动对象共同在路网疏散直到完全离开危险区域或到达安全区域。对于单独的建筑物人员疏散或者路网上的车辆疏散问题，国内外研究者已经提出了大量的方法，但是紧急事件的影响范围一般是由较小的范围逐渐扩大至较大范围内的移动对象，包括建筑物及其周边路网上的人员及车辆。目前国内外对紧急情况下建筑物内的人员疏散研究较多，仿真模型和疏散策略研究也相对成熟，但基于建筑物和交通路网的多模式混合交通疏散的研究相对不足。

粒子群优化算法(Particle Swarm Optimization，PSO)是由Kennedy于1995年提出的一种基于群智能的优化算法。它源于对鸟类捕食行为的模拟，假设一群鸟要搜索一定范围内的一块食物，且在整个搜索区域中只有一块食物。所有的鸟都不知食物在何处，但它们知道自己当前位置距离食物还有多远。那么找到食物的最简单有效的方法就是搜寻并移动到目前离食物最近的鸟的周围区域，并重复上述过程，最终所有的鸟都可以通过这种整体协作的方式到达食物所在的位置。

粒子群算法的运行机理不是依赖个体的自然进化规律，而是对生物群体的社会行为进行模拟，它源于对生物群体行为和人类社会行为的研究。在生物群体中，个体与个体之间、个体与群体之间都存在相互影响、相互作用，表现为一种群体中的信息共享机制。粒子群算法就是受到这样一种社会行为的启发而提出的，个体间通过信息共享可以相互借鉴经验，以促进整个群体的演化。由于粒子群算法思想简单、控制参数少、实现容易，已经成为研究多目标优化问题的重要方法，被广泛应用于模式识别、信号处理、决策支持、系统控制、模糊系统控制、神经网络训练等领域。

虽然粒子群优化算法具有简单快速的优点，但是有两个主要的缺点限制其性能：一方面，PSO对于疏散问题的研究主要集中于仿真，即粒子模拟疏散个体的行为，但是应用粒子群算法对疏散过程进行优化的研究不多，其难点在于PSO模拟的一次疏散过程为一个疏散方案，而本发明的目的是根据疏散目标得到较优的疏散方案，因此需要利用粒子群模拟多次以逼近最优方案，该过程的演化需要用到疏散网络上的信息素；另一方面，传统粒子群只考虑了粒子间的学习，而忽略了粒子所处的网络对粒子运动的影响。

发明内容

本发明的目的在于：为了克服已有技术的不足，即传统疏散模型大多注重疏散过程的模拟，缺少对疏散过程的优化，从而提出一种基于信息素的协同演化粒子优化算法，一方面使用多粒子群来模拟人员和车辆这两种类型的交通对象及其之间的交互，另一方面利用疏散网络的信息素来得到最优疏散方案。多粒子群协同演化优化算法可以模拟不同群体的运动过程，通过群体间的通信机制既体现环境对疏散过程的影响，又可以通过共享和交互信息来达到种群间的相互作用和协同疏散，从而可以得到符合实际需求的多目标优化疏散方案。

为了达到上述目的，本发明采用的技术方案是：一种基于多粒子群协同演化的人车混合疏散仿真优化方法，其特征在于，包括如下步骤：

步骤1. 根据疏散场景初始化疏散网络拓扑图：定义Network（N,>E）为疏散网络，其中N>= {1, 2, … ,>n}为疏散网络中的道路交叉点，定义N_V为车辆允许经过的节点，N_V={Rank₁,>Rank₂, … ,>Rank_n}，；

步骤2. 设置模型参数：包括粒子群的粒子数量M、最大迭代次数T_MAX、惯性系数ω、粒子群学习因子c₁,>c₂,>c₃、信息素浓度初值Q、信息素浓度挥发系数，；

步骤3. 设置人员数量M₁、车辆数量M₂，生成规模为M₁的粒子群1和规模为M₂的粒子群2，即粒子群1的粒子数量M>=>₁，粒子群2的粒子数量M>=>₂；

步骤4. 初始化人员和车辆位置，以及信息素浓度；将代表人员和车辆的粒子随机放置在疏散网络节点上，其中，代表车辆的粒子只能放置在属于N_V的节点上，将初始位置加入每个粒子的路径，初始化所有粒子的速度为0，初始化疏散网络节点上的信息素浓度为步骤2设置的Q；

步骤5. 设置迭代计数器gen>=>

步骤6. 对于粒子群1和粒子群2，分别执行步骤7-步骤20；

步骤7. 从当前粒子群中随机选择一个粒子作为第一个，设k=>

步骤8. 判断第k个粒子的状态是否为“成功撤离”，若是则执行步骤17，否则执行步骤9；

步骤9. 统计当前时刻疏散网络中每个节点的粒子数，记为num_i(t)，计算t时刻所有“未撤离”状态的粒子所覆盖的面积，记为area(t)，根据公式（1）计算t时刻粒子群的密度d(t)：

（1）

步骤10. 计算当前粒子群中所有粒子的适应值：根据每个粒子的当前位置，根据公式（2）计算每个粒子的适应值：

（2）

式中，particle_k为第k个粒子，为粒子k到出口m的距离；

步骤11. 根据步骤10得到的所有粒子适应值，找出当前粒子群中适应值f（particle_i）最小的粒子所在的位置记为当前粒子群最优粒子位置P_gbest，根据第k个粒子的路径信息，找出其路径上距离出口最近的位置记为粒子个体最优位置P_pbest，根据当前时刻疏散网络中每个位置节点的信息素浓度，将最大信息素浓度所在位置记为P_max>；

步骤12. 按公式（3）更新第k个粒子的速度：

（3）

V（t）和V（t>+ 1）分别为粒子在t时刻和t>+ 1时刻的速度，X（t）为粒子在t时刻的位置，ω为步骤2设置的惯性系数，c₁,>c₂,>c₃为步骤2设置的学习因子，r₁,>r₂,>r₃为（0，1）之间的随机数，P_pbest、P_gbest、P_max>分别为步骤11>

步骤13. 更新第k个粒子的位置，并将该位置加入粒子的路径path_k，记录第k个粒子通过上一位置节点的时间，以及该粒子从上一位置节点到最新节点的距离：根据步骤12得到的速度按公式（4）更新第k个粒子在下一时刻的位置，将粒子移动到最新位置；

（4）

X（t）和X（t>+ 1）分别为粒子在t时刻和t>+ 1时刻的位置；

步骤14. 根据步骤13得到的最新位置判断该位置是否为出口位置，若是，则代表第k个粒子已到达出口，标记该粒子状态为>

步骤15. 粒子计数加1，即k>=>k>+ 1，若k ≤>说明还未遍历完该粒子群的所有粒子，返回步骤9，否则表明完成了一个时间步的搜索，执行步骤16；

步骤16. 判断当前粒子群中所有粒子的状态是否为“成功撤离”，若是则表明本轮迭代完成，将本轮迭代的时间步数记为T，执行步骤17，否则返回步骤7；

步骤17. 根据步骤13得到的当前粒子群中每个粒子的路径，根据步骤13得到的路径上通过每个节点的时间和距离计算每个粒子通过整个路径的总时间和总距离，记为粒子疏散时间和路径长度，按公式（5）计算信息素浓度：

（5）

τ_i(gen)为第gen次迭代位置节点i上的信息素浓度，为步骤2设置的信息素浓度挥发系数，>i在个体层次上的信息素浓度增量，根据公式（6）计算：

（6）

其中，Q为步骤2设置的信息素浓度初值，dis_k>(gen)为步骤17得到的第gen次迭代中第k个粒子的路径长度，min>_k>(1,…,>gen)>k个粒子在第1次到第gen次迭代中的最短路径；

步骤18. 计算疏散目标值：根据步骤17得到的粒子疏散时间，按照公式(7)计算所有粒子的疏散时间总和F₁，根据步骤9得到的各个时刻粒子密度，按照公式（8）计算总密度值F₂，F₁和F₂即为本发明所优化的两个疏散目标值：

（7）

（8）

t_k为步骤17得到的第k个粒子的疏散时间，M>d>t)为步骤9得到的时刻粒子群的密度，T>

步骤19. 根据步骤18得到的疏散目标值F₁和F₂按照以下Pareto支配关系确定当前粒子群的Pareto最优解集ND_set，该Pareto最优解集为迭代过程中满足F₁和F₂最小的若干个疏散方案的集合；

在多目标优化问题中，Pareto支配是一个非常重要的概念，它是解的一种偏序关系，定义如下：

Pareto支配：对于决策空间Y中的任意两个决策向量和b，支配b当且仅当向量的目标值都不大于向量b>b对应的目标值；

Pareto最优解：对决策空间Y>Y中存在Pareto支配向量的决策向量；

Pareto最优解集：由决策空间Y>

步骤20. 根据步骤19得到的Pareto最优解集ND_set，对ND_set中的每一个解，即疏散方案，按照公式（9）更新其方案中所有粒子经过路径上节点位置的信息素浓度：

(9)

为步骤2设置的信息素浓度挥发系数，为位置节点i在全局层次上的信息素浓度增量；按照公式（10）计算：

（10）

Q>path_k为步骤13得到的第k>k>i>

步骤21. 粒子群间通信：每个粒子群中的粒子除了通过各自的信息素合作搜索出口外，还通过粒子群间的通信来共享信息素，以改进搜索过程；每个粒子群按照公式（11）~公式（16）来更新自己的信息素：

（11）

（12）

（13）

（14）

（15）

（16）

分别是粒子群1和粒子群2的通信因子，是衡量粒子群1和粒子群2相互影响的参数；d₁(t)，d₂(t)分别为由步骤9得到的t>T>

步骤22. 迭代计数器gen加1，即gen>= gen>+1；

步骤23. 若gen>T_MAX，T_MAX是步骤2中设置的最大迭代次数，将所有粒子放置于步骤4设置的各自的初始位置节点上，重复步骤6-22，否则，迭代结束执行步骤24；

步骤24. 输出Pareto最优解集。

作为进一步优选的，所述步骤9中t>d>t)为当前时刻粒子群体中未到达出口的粒子个数与未撤离粒子在疏散网络中所占面积之比。

作为进一步优选的，所述步骤12中粒子速度更新方式为粒子通过对当前速度、粒子个体最优位置、粒子群最优粒子位置、最大信息素浓度所在位置这几个因素的综合学习得出。

作为进一步优选的，所述步骤17中信息素浓度在个体层次上的增量由粒子自身迭代过程中的个体最优路径决定。

作为进一步优选的，所述步骤19中Pareto最优解集为同时满足粒子群疏散时间总和F₁最短和粒子总密度值F₂最小的疏散方案。

作为进一步优选的，所述步骤21中行人粒子群1和车辆粒子群2间的通信规则为一个粒子群通过引入另一个粒子群的信息素来改进搜索过程。

作为进一步优选的，本方法的参数设置为：人员数量M_{1>= 2000，车辆数量M2>= 1000，最大迭代次数T_MAX>ω=>c1>= 3，c2>= 3，c3>= 2，信息素浓度初值Q>}

本发明与现有技术相比具有以下优点：

1、本发明采用多粒子群算法模拟行人和车辆的疏散过程，能够更好地模拟人车混合疏散过程中的人员群体和车辆行为，以及不同对象之间的交互，粒子的运动除了受到自身经验和群体最优个体的影响之外，同时还向邻域中的最优个体学习，这种局部和全局并存的学习机制既模拟了疏散过程中的从众行为、小群体现象，又加速了寻找安全出口的进程。

2、本发明采用基于信息素的多粒子群协同演化算法优化人车混合疏散过程，各种群在各自独立进化的同时相互间共享和交互信息，表现在各种群利用从外界获得的信息以指导自身的搜索过程, 同时还把自身寻优经验与其他种群分享，从而使得整个系统协同进化，使得人员和车辆能够协作达到最优。

3、本发明与基于单一粒子群的方法相比，不但能够模拟行人和车辆的疏散过程，而且能够通过粒子群间的通信对疏散方案进行优化，且拥有较好的收敛速度和收敛效果。

4、本发明与其他方法相比，能够得到更好的疏散方案，并且同时满足疏散时间和疏散密度两个目标要求，从而使得疏散路径更加合理，疏散方案更加符合实际需求。

附图说明

图1是本发明的实验流程图。

图2是本发明中多粒子群协同演化算法流程图。

图3是本发明的疏散网络图。

图4是本发明的密度示意图。

图5是本发明中多粒子群协同演化算法收敛图。

图6是本发明方法和粒子群优化算法的密度变化曲线对比图。

图7是本发明方法和粒子群优化算法在疏散路径拥堵程度上的比较。

具体实施方式

为了更好地理解本发明，下面结合实施例进一步阐明本发明的内容，但本发明的内容不仅仅局限于下面的实施例。本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样在本申请所列权利要求书限定范围之内。

图1和图2是本发明的实验流程图和多粒子群协同演化优化算法流程图，从中可以看出具体实现过程如下：

步骤1. 根据疏散场景初始化疏散网络拓扑图：定义Network（N,>E）为疏散网络，其中N>= {1, 2, … ,>n}为疏散网络中的道路交叉点，定义N_V为车辆允许经过的节点，N_V={Rank₁,>Rank₂, … ,>Rank_n}，。

步骤2. 设置模型参数：包括粒子群的粒子数量M、最大迭代次数T_MAX、惯性系数ω、粒子群学习因子c₁,>c₂,>c₃、信息素浓度初值Q、信息素浓度挥发系数，。

步骤3. 设置人员数量M₁、车辆数量M₂，生成规模为M₁的粒子群1和规模为M₂的粒子群2，即粒子群1的粒子数量M>=>₁，粒子群2的粒子数量M>=>₂。

步骤4. 初始化人员和车辆位置，以及信息素浓度；将代表人员和车辆的粒子随机放置在疏散网络节点上，其中，代表车辆的粒子只能放置在属于N_V的节点上，将初始位置加入每个粒子的路径，初始化所有粒子的速度为0，初始化疏散网络节点上的信息素浓度为步骤2设置的Q。

步骤5. 设置迭代计数器gen>= 1。

步骤6. 对于粒子群1和粒子群2，分别执行步骤7-步骤20。

步骤7. 从当前粒子群中随机选择一个粒子作为第一个，设k>

步骤8. 判断第k>

步骤9. 统计当前时刻疏散网络中每个节点的粒子数，记为num_i(t)，计算t>area(t)，根据公式（1）计算t>d(t)。

（1）

步骤10. 计算当前粒子群中所有粒子的适应值：根据每个粒子的当前位置，根据公式（2）计算每个粒子的适应值：

（2）

式中，particle_k为第k个粒子，为粒子k>m>

步骤11. 根据步骤10得到的所有粒子适应值，找出当前粒子群中适应值f（particle_i）最小的粒子所在的位置记为当前粒子群最优粒子位置P_gbest，根据第k个粒子的路径信息，找出其路径上距离出口最近的位置记为粒子个体最优位置P_pbest，根据当前时刻疏散网络中每个位置节点的信息素浓度，将最大信息素浓度所在位置记为P_max>。

步骤12. 按公式（3）更新第k个粒子的速度：

（3）

V（t）和V（t>+ 1）分别为粒子在t时刻和t>+ 1时刻的速度，X（t）为粒子在t>ω为步骤2设置的惯性系数，c₁,>c₂,>c₃为步骤2设置的学习因子，r₁,>r₂,>r₃为（0，1）之间的随机数，P_pbest、P_gbest、P_max>分别为步骤11>

步骤13. 更新第k个粒子的位置，并将该位置加入粒子的路径path_k，记录第k个粒子通过上一位置节点的时间，以及该粒子从上一位置节点到最新节点的距离：根据步骤12得到的速度按公式（4）更新第k个粒子在下一时刻的位置，将粒子移动到最新位置；

（4）

X（t）和X（t>+ 1）分别为粒子在t时刻和t>+ 1时刻的位置。

步骤14. 根据步骤13得到的最新位置判断该位置是否为出口位置，若是，则代表第k个粒子已到达出口，标记该粒子状态为>

步骤15. 粒子计数加1，即k>=>k>+ 1，若k ≤>说明还未遍历完该粒子群的所有粒子，返回步骤9，否则表明完成了一个时间步的搜索，执行步骤16。

步骤16. 判断当前粒子群中所有粒子的状态是否为“成功撤离”，若是则表明本轮迭代完成，将本轮迭代的时间步数记为T，执行步骤17，否则返回步骤7。

步骤17. 根据步骤13得到的当前粒子群中每个粒子的路径，根据步骤13得到的路径上通过每个节点的时间和距离计算每个粒子通过整个路径的总时间和总距离，记为粒子疏散时间和路径长度，按公式（5）计算信息素浓度：

（5）

τ_i(gen)为第gen次迭代位置节点i上的信息素浓度，为步骤2设置的信息素浓度挥发系数，>i在个体层次上的信息素浓度增量，根据公式（6）计算：

（6）

其中，Q为步骤2设置的信息素浓度初值，dis_k>(gen)为步骤17得到的第gen>k个粒子的路径长度，min>_k>(1,…,>gen)>k个粒子在第1次到第gen次迭代中的最短路径。

步骤18. 计算疏散目标值：根据步骤17得到的粒子疏散时间，按照公式(7)计算所有粒子的疏散时间总和F₁，根据步骤9得到的各个时刻粒子密度，按照公式（8）计算总密度值F₂，F₁和F₂即为本发明所优化的两个疏散目标值：

（7）

（8）

t_k为步骤17得到的第k个粒子的疏散时间，M为当前粒子群的粒子数量，d(t)为步骤9得到的时刻粒子群的密度，T为步骤16得到的本轮迭代的时间步数。

步骤19. 根据步骤18得到的疏散目标值F₁和F₂按照以下Pareto支配关系确定当前粒子群的Pareto最优解集ND_set，该Pareto最优解集为迭代过程中满足F₁和F₂最小的若干个疏散方案的集合。

在单目标优化问题中，最优解通常是唯一确定的，而对多目标优化问题而言，由于各个目标函数之间是冲突的，不可折衷的，因而多目标优化问题的最优解集通常是一个集合，这是多目标优化问题相对于单目标优化问题的本质差别。

在多目标优化问题中，Pareto支配（dominate）是一个非常重要的概念，它是解的一种偏序关系，定义如下：

Pareto支配：对于决策空间Y>b，支配b当且仅当向量的目标值都不大于向量b>b>

Pareto最优解：对决策空间Y中的任一向量，为Pareto最优，当且仅当决策空间Y中存在Pareto支配向量的决策向量；

Pareto最优解集：由决策空间Y>

步骤20. 根据步骤19得到的Pareto最优解集ND_set，对ND_set中的每一个解（疏散方案），按照公式（9）更新其方案中所有粒子经过路径上节点位置的信息素浓度：

(9)

为步骤2设置的信息素浓度挥发系数，为位置节点i>

（10）

Q为步骤2设置的信息素浓度初值，path_k为步骤13得到的第k个粒子的路径，为步骤13得到的第k>i>

步骤17和步骤20表明了疏散网络中信息素浓度的更新受到两个方面因素的影响，一个是每个粒子根据自身迭代过程中的个体最优路径更新本路径的信息素，另一方面，根据Pareto最优解集中的非支配解集更新该方案中的所有路径上的信息素。

步骤21. 粒子群间通信：每个粒子群中的粒子除了通过各自的信息素合作搜索出口外，还通过粒子群间的通信来共享信息素，以改进搜索过程；每个粒子群按照公式（11）~公式（16）来更新自己的信息素：

（11）

（12）

（13）

（14）

（15）

（16）

分别是粒子群1和粒子群2的通信因子，是衡量粒子群1和粒子群2相互影响的参数；d₁(t)，d₂(t)分别为由步骤9得到的t>T>

步骤22. 迭代计数器gen加1，即gen>= gen>+1。

步骤23. 若gen>T_MAX，T_MAX是步骤2中设置的最大迭代次数，将所有粒子放置于步骤4设置的各自的初始位置节点上，重复步骤6-22，否则，迭代结束执行步骤24。

步骤24. 输出Pareto最优解集。

为了验证本发明的有效性，我们将本发明与基本粒子群算法进行了仿真比较。在仿真实验过程中，选取武汉体育中心体育馆及其周边区域作为实验场景。本发明的参数设置为：人员数量M_{1>= 2000，车辆数量M2>= 1000，最大迭代次数T_MAX>ω}=>c_{1>= 3，c2>= 3，c3>= 2，信息素浓度初值Q>}

图3是本发明所使用场景的疏散网络图，其中标记为圆点的节点为仅允许行人通行，标记为方形的节点为允许行人或车辆通行。

图4是本发明中关于密度定义的示意图，其中密度为场景中未疏散个体的数量与未疏散个体所占面积之比，从图中可以看出，疏散个体越分散，密度越低，本发明以疏散时间和密度作为优化目标，得到的优化方案既能够保证时间最短，又能降低疏散过程中拥堵程度，从而得到安全、快速的疏散方案。

图5是本发明中多粒子群协同演化算法的收敛图，从图中可以看出，随着迭代次数的增加，疏散总时间和总密度两个目标值都在降低，说明算法能够保证收敛，且算法在150代左右达到最优。

图6是本发明方法和基本粒子群优化算法的密度变化比较，可以看出在疏散时间上，本发明的方法比基本粒子群优化算法明显缩短，并且密度在整个疏散过程中保持较低的水平，说明本发明的方法能够使疏散个体在疏散全过程中尽可能地分散，从而避免产生拥堵。

图7是本发明方法和基本粒子群优化算法在疏散路径上的比较，图中路段由细到粗变化，代表路段的通过人数/车辆数由低到高，从图中标注区域可以看出本发明的方法明显优于基本粒子群优化算法，说明本发明的方法得到的疏散路径更加合理。

表1列出了本发明的多粒子群协同演化优化算法（CEPSO）和基本粒子群算法（PSO）在不同迭代次数下的实验结果，可以看出，随着迭代次数的增加，本发明方法（CEPSO）和基本粒子群算法（PSO）在总疏散时间、总密度和时间步上都趋于下降趋势，但本发明方法在这几个评价指标上均明显优于本粒子群算法，说明本发明的方法具有更快的收敛速度。

表1 CEPSO与PSO方法优化结果比较

本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。