基于差分进化算法的大型公共场所人流引导路径规划方法

摘要

本发明公开了一种基于差分进化算法的大型公共场所人流引导路径规划方法。本发明将路径规划问题表示为一个连续优化问题，利用差分进化算法结合多目标优化技术解决大型公共场所的人流引导路径规划问题，将路径方案编码为一组前后相关互联的基因序列，在差分进化过程中，基于人群行为仿真的结果对路径方案进行适应度评估，引导种群进行个体选择，将安全性和效率作为多目标选择操作的两个目标，应用经典的NSGA‑II算法进行种群个体选择，得到的路径方案既有着较好的安全性，又能引导人群高效通过场景，有效地克服了现有技术优化时评估准则过于单一的不足，减少了路径交叉，兼顾了安全性和效率。

说明书

技术领域

本发明涉及路径规划和智能计算技术领域，具体涉及一种基于差分进化算法的大型公共场所人流引导路径规划方法。

背景技术

大型公共场所的人流引导问题是公共安全的重要问题。它要求在给定场景下提供路牌或路线指示，从而使得行人能快速、安全地到达各自的目的地，同时尽可能地避免不同路线之间的交叉导致的拥堵。

路径规划方法主要包括根据场景信息进行的全局路径规划和根据实时信息进行的局部路径规划。传统的路径规划方法包括Dijkstra算法和A*算法等，近年来也有仿生学方法被应用于路径规划，如蚁群算法、遗传算法等。这些方法往往针对给定的静态场景提供一组最短或较短的路径，但在像车站和商场这些人流密集、行人路线复杂的场景下，仅优化距离得到的路径往往不够安全，行走方向不同的人流之间的交叉可能会导致人群拥堵，而严重的拥堵则可能引发安全事故。在这类场景下，路径的距离或人群通过场景的效率往往不是唯一应该考虑的的优化目标，而现有的路径规划方法大多仅适用于优化单一目标，故而，在路径复杂的场景下，考虑路径的距离提高效率的同时减少路径交叉，从而提高路径安全性成为一个需要解决的问题。

此外，对于多出入口的场景，还需要将出口的选择作为规划内容的一部分，如何为走向各目的地的行人合理分配出口，既提高出口利用率，也控制出口的负载，同样是一个既关乎安全性也关乎效率的需要解决的问题。

发明内容

本发明的目的是为了解决现有技术中的上述缺陷，提供一种基于差分进化算法的大型公共场所人流引导路径规划方法。差分进化算法是一种基于种群的启发式搜索算法，种群中的每个种群个体对应一个解向量，称之为目标向量，其进化流程包括变异、杂交和选择等操作，生成测试向量，通过对目标向量和测试向量进行适应度评估，更新种群个体，经过不断地进化迭代，保留优良个体，淘汰劣质个体，引导搜索向最优解逼近。本发明提出的路径规划方法利用差分进化算法结合多目标优化技术解决路径规划问题，有效地克服了现有技术优化时评估准则过于单一的不足，减少了路径交叉，兼顾了安全性和效率，提高了其实用性。

本发明的目的可以通过采取如下技术方案达到：

一种基于差分进化算法的大型公共场所人流引导路径规划方法，其路径规划方法包括以下步骤：

S1、执行初始化操作：根据场景中的可行区域，随机生成大小为N的种群Q，所述种群包含N个种群个体；用前后基因互相关联的编码方式编码路径方案，为每个种群个体构建目标向量，路径方案由多条路径组成，对路径方案进行编码即对路径用前后基因互相关联的编码方式进行编码；基于人群行为的仿真结果计算所述目标向量的目标函数值，在仿真过程中，利用智能体模拟人群行为。

S2、执行个体交叉操作：为每个所述种群个体构建测试向量；基于人群行为仿真的结果计算测试向量的目标函数值；进行适应度评估，执行多目标选择操作更新种群个体的目标向量。

S3、执行局部搜索操作：更新种群个体测试向量；基于人群行为仿真的结果计算测试向量的目标函数值；进行适应度评估，执行多目标选择操作更新种群个体的目标向量。

S4、重复执行S2、S3步骤，直到达到预设迭代次数或路径方案的安全性和效率都满足预设需求。

S5、将最后一次迭代得到的路径方案作为最终路径方案，并对路径规划方案进行后期处理。

进一步地，步骤S1中目标向量包含规划方案的路线信息和终点信息，按如下方式构建：

P

其中，X

每个种群个体被编码成一个M×(D+1)维的实数向量，每个个体X

进一步地，目标函数值按如下方式计算：

f

f

其中，C是以预设边长对场景对进行网格划分后得到的某个方形区域的中心点；H(C)是不同路径的行人经过点C的所在网格的频率的熵；f

对于每个路径方案，进行预定时长的人群行为仿真，该仿真用多个智能体模拟行人产生人群动态，以计算两个目标函数值。在仿真过程中，各个智能体在不同时刻进入场景，并沿着路径方案中给出的路径走向各自的出口。

进一步地，所述步骤S2中的测试向量按如下方式构建：

其中，u

进一步地，所述步骤S3的局部搜索中更新测试向量按如下方式操作：

对当前种群中的每个个体，根据目标向量的路径方案计算测试向量；选定对测试向量路径方案熵值贡献最大的路径，应用该路径的起点和终点，按前后基因互相关联的编码方式，重新随机生成一条路径；用生成的这条路径代替测试向量路径方案中对熵值贡献最大的那条路径，即淘汰掉带来最多安全隐患的路径。路径方案中的一条路径对路径方案熵值的贡献可以通过计算该路径方案中不含此条路径的其他路径的熵值来得到，若此计算得到的熵值越小，说明这条路径对整个路径方案熵值的贡献越大。

进一步地，所述步骤S5中后期处理为平滑处理，所述平滑处理为利用贝塞尔曲线对路径方案中的路径进行平滑，此外，还可以采用B-样条曲线来平滑路径方案中的路径。

进一步地，所述步骤S2和步骤S3中适应度评估，按如下方式操作：

比较种群个体目标向量和测试向量的适应度，适应度包括两个目标函数值，如果测试向量的两个目标函数值都小，即测试向量支配目标向量，则用测试向量取代目标向量；如果目标向量的两个目标函数值都小，即目标向量支配测试向量，则舍弃测试向量；如果测试向量有目标函数值比目标向量的目标函数值小，目标向量也有目标函数值比测试向量的目标函数值小，即目标向量和测试向量互不支配，此时将测试向量记录下来。

进一步地，所述步骤S2和步骤S3中多目标选择操作，按如下方式操作：

将记录下来的测试向量加入当前种群，执行NSGA-II算法的基于非支配排序和拥挤距离的多目标选择操作，逐个选择优秀的个体，使得当前种群的大小保持为N。除了NSGA-II算法，多目标选择还可以采用NSGA-III算法，NSGA-III为NSGA-II的改进版本，专门针对高维多目标优化。

进一步地，所述步骤S2和步骤S3中基于非支配排序和拥挤距离操作具体过程如下：

将所有种群个体根据支配关系分配为指定个前沿，前一个前沿支配后一个前沿，同一个前沿内的种群个体互相不支配；如果一个种群个体的两个目标函数值都优于另一个种群个体的目标函数值，则称前者支配后者；

计算前沿中每个种群个体的拥挤距离，并将种群个体按照拥挤距离从大到小排序，拥挤距离反映了每个种群个体周围的种群个体密度，为了保持种群中个体的多样性，选择操作将在互不支配的个体中优先选择周围种群个体密度稀疏的种群个体；

优先选择靠前的前沿中的种群个体加入新种群，在同一个前沿中则优先将拥挤距离大的种群个体加入新种群，直到新种群大小为N。

进一步地，所述步骤S3的局部搜索中根据目标向量的路径方案计算测试向量是将目标向量的路径方案直接赋值给测试向量。

进一步地，所述步骤S1中的人群行为仿真基于RVO2和A*算法实现。RVO2算法用于实现碰撞避免，也可以选择社会力模型来实现碰撞避免。A*算法用于实现点到点的路径导航，还可以采用Dijkstra算法、D*算法等进行路径导航。仿真分为两步：第一步是利用单个智能体根据关键点进行仿真，得到点间距离比关键点间距离更近的路径；第二步是用多个智能体模拟现实中的行人，智能体从各个入口持续不断地进入场景，沿着第一步仿真得到的路径，走向出口。

进一步地，所述步骤S2和步骤S3中的应用多目标选择操作更新种群个体的目标向量时，还可以采用线性加权的方式，即考虑对两个目标函数值线性加权，将其转化为单目标问题，可以根据实际应用场景有侧重性地考虑路径规划方案的安全性或效率。相较而言，多目标优化无需设计权值，具有参数较少的优点。

本发明相对于现有技术具有如下的优点及效果：

本发明将路径规划问题表示为一个连续优化问题，利用差分进化算法结合多目标优化技术解决大型公共场所的人流引导路径规划问题，采用一种新的前后基因相互关联的编码方式将路径方案编码为一组前后相关联的基因序列，在差分进化过程中，基于人群行为仿真的结果对路径方案进行适应度评估，引导种群更新进行种群个体选择，将安全性和效率作为多目标选择操作的两个目标，应用经典的NSGA-II基于非支配排序和拥挤距离的多目标选择操作进行种群个体选择，得到的路径方案既有着较好的安全性，又能引导人群高效通过场景，有效地克服了现有技术优化时评估准则过于单一的不足，减少了路径交叉，兼顾了安全性和效率。

附图说明

图1是本发明实施例中公开的基于差分进化算法的大型公共场所人流引导路径规划方法的流程图；

图2是本发明实施例中广州体育西路地铁站示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

下面结合附图对本发明的方法作更详细的描述。

实施例

对于大型公共场景，假设有M条不同的路径需要规划，M取决于人流有多少个主要的流向，将出、入口分组，每组入口与每组出口之间都有一条路径，人群可以根据自身所在的位置以及要抵达的出口，确定自己要跟随的路线指引。由于进行分组操作，一条路径可能对应多个入口和出口，每条规划路径均包含出口的选择以及中间的路线。我们的目标是在有效引导人群快速到达终点的同时，尽可能减少场景内不同路线上的人群之间的交汇，以提高安全性，因此，效率和安全性是本发明使用的多目标差分进化算法中的两个目标，对应了两个目标函数值，也即适应度。目标函数值按如下方式计算：

f

f

其中，C是以预设边长对场景进行网格划分后得到的某个方形区域的中心点，网格划分将场景划分为多个大小相同的方形，便于计算熵，每个经过网格的模拟行人的智能体都会被用于计算该网格的熵；H(C)是在进行评估的仿真过程中，不同路线的模拟行人的智能体经过点C所在的网格的频率的熵，f

对于每个路径方案，将基于用于碰撞避免的RVO2算法和用于路径导航的A*算法，进行持续2分钟的仿真，该仿真用多个智能体模拟行人产生人群动态，以计算两个目标函数值，在仿真过程中，各个智能体在不同时刻进入场景，并沿着该算法给出的路径方案走向各自的出口。

本实施例中，依据两个目标函数值也即适应度对路径方案进行适应度评估，适应度评估方式如下：

比较种群个体目标向量和测试向量的适应度，适应度包括两个目标函数值，如果测试向量的两个目标函数值都小，即测试向量支配目标向量，则用测试向量取代目标向量；如果目标向量的两个目标函数值都小，即目标向量支配测试向量，则舍弃测试向量；如果测试向量有目标函数值比目标向量的目标函数值小，目标向量也有目标函数值比测试向量的目标函数值小，即目标向量和测试向量互不支配，此时将测试向量记录下来。

本实施例中，应用用多目标优化技术更新种群，按如下方式操作：

在每个个体都生成过一个测试向量以后，将记录下来的测试向量加入到种群中，用基于非支配排序和拥挤距离的选择操作淘汰差的个体，使得新种群大小保持为N，选择的过程如下：

首先，将所有种群个体根据支配关系分配为多个前沿，前一个前沿内的种群个体支配后一个前沿内的种群个体，同一个前沿内的种群个体互相不支配。如果一个种群个体的两个目标函数值都优于另一个种群个体，则前者支配后者；

计算前沿中每个种群个体的拥挤距离，并将种群个体按照拥挤距离从大到小排序，拥挤距离反映了每个种群个体周围的种群个体密度，为了保持种群中个体的多样性，选择操作将在互不支配的个体中优先选择周围种群个体密度稀疏的种群个体；

优先选择靠前的前沿中的种群个体加入新种群，在同一个前沿中则优先将拥挤距离大的种群个体加入新种群，直到新种群大小为N。

为了减小搜索空间，提高搜索效率，需要对不同路线的人群进行分组，并为种群个体的路线规划设置关键点间距离。关键点由进化算法搜索得到，关键点间的距离是一个预设的参数，参照路径整体的曲折程度和算力设定，关键点之间的距离越短，关键点的连线越接近方案对应的实际路径，如果方向要频繁发生改变，则距离要适当设置得小一些，但是为了提高搜索效率，距离不应当设置得过小，因为路径上的关键点如果比较多，搜索会变慢，适当减少关键点的个数，还可以简化目标向量，提高进化算法的搜索效率。

进行分组时，将出入口所在分组相同的人群分为一组。在执行进化算法的过程中，为了提高搜索效率，路径由数量较少、间隔距离较大的多个关键点表示，不足以在实际情形中引导行人，故在进行适应度评估的仿真之前，需要先用单个智能体来模拟单个行人进行简单仿真以得到间距较小的更多的点来表示路径。该仿真与用于适应度评估的仿真不同，单个智能体不会反映人群动态的安全性和效率，仅用于在路径上生成的更多的点，这些点的点间距比关键点之间的距离更小，该智能体根据路径方案中的关键点，结合传统的路径规划算法，如A*、Dijkstra和D*算法，对每条路径走出一条由间距比关键点之间的距离更小的更多的点组成的新路径，这条新路径在实际应用中比关键点的引导能力更强，可用于直接在地面绘制路线。在随后用于正式的适应度评估的仿真过程中，模拟多个行人的多个智能体将依据自己的起点和终点，跟随先前走出的路径点序列走向目的地。

图1给出了本发明实施例中基于差分进化算法的大型公共场所人流引导路径规划方法的流程图。下面就流程图的内容分步描述整个算法的具体实施方式：

S1、执行初始化操作：

根据场景中可以行走的区域，随机生成大小为N的种群Q，在生成过程中，如果发现当前点不在可以行走的区域内时，则重新生成这个点，直至它落到可以行走的区域内，确保规划路径上的每个关键点都落在场景中可以行走的区域内。对于体育西路地铁站的场景，种群大小N设为30。用前后基因互相关联的编码方式为每个种群个体构建目标向量，目标向量中包含了路线信息和终点信息。随后，利用前文所述的计算目标函数值的方法计算种群个体目标向量的目标函数值。目标向量按如下方式被编码成一个M×(D+1)维的实数向量：

P

其中，X

在体育西路地铁站场景中，本实施例将M的值设为16，D的值设为10，表示一个路径方案包括16条路径，每条路径上有10个关键点。在最终的路径方案中，并非所有的关键点都会发挥作用，即一条路径对应的10个关键点的后几个点可能是冗余的。在图2的场景示意图中，左上的入口归为一组，右上的入口归为一组，中央上方偏右的两个入口归为一组，其余5个入口每个入口单独为一组，这样总共有8组入口，场景内部的电梯口按上、下位置分为2组，共有16条路径。

在体育西路地铁站场景中，网格设为边长为1平方米的正方形。在仿真过程中，有如下假设：

(a)模仿行人的智能体持续以近似相同的频率根据泊松分布从入口进入场景；

(b)所有智能体的目的地均为某个电梯口；

(c)一半智能体选择场景上部的电梯口作为目的地，另一半选择场景下部的电梯口作为目的地。

S2、执行个体交叉操作，更新种群个体：

对于种群中的每个目标向量，使其与当代其他个体用差分进化算法的随机交叉方式生成一个测试向量，以将其他个体的信息结合到自身，在修正该测试向量使其合法后，计算测试向量的目标函数值，进行适度度评估，执行NSGA-II的基于非支配排序和拥挤距离的多目标选择操作，更新种群个体。

S21、种群里的每个个体X

其中，u

S22、按前文所述的方法计算测试向量的目标函数值；

S22、按前文所述的方法进行适应度评估：

S23、按前文所述的方法用多目标优化技术更新种群个体的目标向量。

S3、执行局部搜索操作，更新种群个体：

种群个体交叉操作完成后，执行局部搜索操作。局部搜索的目的是通过对个体对应的路径方案中的某条路径进行调整，以得到更好的方案。本实施中，考虑到每条路径对应的基因段实际上是一组前后相关联的关键点，因此将一整条路径作为局部搜索对象，而不是将路径上的单独一个点作为搜索对象，以提高搜索效率。

S31、局部搜索操作的测试向量按如下步骤得到：

对于当前种群的每一个种群个体，将其目标向量路径方案的值直接赋值给测试向量；

选定对测试向量路径方案熵值贡献最大的路径，应用该路径的起点和终点，按前后基因互相关联的编码方式，重新随机生成一条路径；

用生成的这条路径代替测试向量路径方案中对熵值贡献最大的那条路径，即淘汰掉带来最多安全隐患的路径。路径方案中的一条路径对路径方案熵值的贡献可以通过计算该路径方案中不含此条路径的其他路径的熵值来得到，仅用其他路径计算得到的熵值越小，说明这条路径对整个路径方案熵值的贡献越大。

S32、按前文所述的方法计算测试向量的目标函数值；

S33、按前文所述的方法进行适应度评估：

S34、按前文所述的方法用多目标优化技术更新种群个体的目标向量。

S4、重复执行S2、S3步骤，直到达到预设迭代数，或者所得方案在人流引导上的安全性和效率都满足了预设需求。

S5、将最后一次迭代得到的路径方案作为最终路径方案，利用贝塞尔曲线对路径方案中的路径进行曲线平滑等后期处理，得到可以实际应用的路径。

特别地，在进行人群行为仿真时，碰撞避免还可以用社会力模型，社会力模型更接近人的真实行为，但RVO2模型有较为完善的库，可以方便地实现并行运算，效率更高；路径导航算法还可以采用Dijkstra算法、D*算法等，但A*算法比Dijkstra算法和D*算法的效率高。在执行多目标选择操作更新种群个体时，还可以采用NSGA-II的改进版本NSGA-III算法，也可以采用线性加权的方式对两个目标函数值线性加权，将多目标选择操作转化为单目标操作，以便根据实际应用场景有侧重性地考虑路径规划方案的安全性或效率；此外，在对所得路径进行平滑处理时，还可以应用B-样条曲线对路径进行平滑。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。