(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110219913.2 (22)申请日 2021.02.26 (65)同一申请的已公布的文献号 申请公布号 CN 112884229 A (43)申请公布日 2021.06.01 (73)专利权人 中新国际联合研究院 地址 510000 广东省广州市广州知识城腾 飞科技园腾飞一 街2号1018室 (72)发明人 钟竞辉　李东芮　蔡文桐　 (74)专利代理 机构 广州市华学知识产权代理有 限公司 4 4245 专利代理师 李盛洪 (51)Int.Cl. G06Q 10/04(2012.01) G06F 30/27(2020.01)G06N 3/00(2006.01) G06F 111/06(2020.01) (56)对比文件 CN 112231968 A,2021.01.15 CN 105430707 A,2016.0 3.23 林煦涵等.基于遗传算法的最短路径规划. 《电子世界》 .2017,(第08 期), 审查员 张榆 (54)发明名称 基于差分进化算法的大型公共场所人流引 导路径规划方法 (57)摘要 本发明公开了一种基于差分进化算法的大 型公共场所人流引导路径规划方法。 本发明将路 径规划问题表 示为一个连续优化问题， 利用差分 进化算法结合多目标优化技术解决大型公共场 所的人流引导路径规划问题， 将路径方案编码为 一组前后相关互联的基因序列， 在差分进化过程 中， 基于人群行为仿真的结果对路径方案进行适 应度评估， 引导种群进行个体选择， 将安全性和 效率作为多目标选择操作的两个目标， 应用经典 的NSGA‑II算法进行种群个体选择， 得到的路径 方案既有着较好的安全性， 又能引导人群高效通 过场景， 有效地克服了 现有技术优化时评估准则 过于单一的不足， 减少了路径交叉， 兼顾了安全 性和效率。 权利要求书2页 说明书8页 附图2页 CN 112884229 B 2022.12.20 CN 112884229 B 1.一种基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述 路径规划方法包括以下步骤： S1、 执行初始化操作： 随机生成大小为N的种群Q， 所述种群Q包含N个种群个体； 用前后 基因互相关联 的编码方式编码路径方案， 为每个种群个体构建目标向量； 基于人群行为仿 真的结果计算所述目标向量的目标函数值； S2、 执行个体交叉操作： 为每个所述种群个体构建测试向量； 基于人群行为仿真的结果 计算所述测试向量的目标函数值； 进行适应度评估， 执行多目标选择操作更新种群个体的 目标向量； S3、 执行局部搜索操作： 更新每个种群个体的测试向量； 基于人群行为仿真的结果计算 测试向量的目标函数值； 进行适应度评估， 执 行多目标选择操作更新种群 个体的目标向量； S4、 重复执行步骤S2、 S3， 直到达到预设迭代次数或路径方案的安全性和效率都满足预 设需求； S5、 将最后一次迭代得到的路径方案作为最终路径方案， 并对路径规划方案进行后期 处理； 其中， 所述 步骤S1中目标向量按如下 方式构建： Pi， k＝[ θi， k， 1， θi， k， 2， ...， θi， k， j， ...， θi， k， D， ei， k] 其中， Xi表示种群中的第i个个体， θi， k， j表示第i个个体对应的路径方案中的第k条路径 的第j个关键点与前一个点的连线与水平方向的夹角， Pi， k表示第i个个体对应的路径方案 中的第k条路径， ei， k表示第i个个体在第k条路径的终点， i＝1， 2， ......， N， N为种群个体的 数量、 k＝1， 2， ......， M， M为路径方案中的路径数量、 j＝1， 2， ......， D， D为每条路径的关 键点个数； 每个种群个体被编码成一个M ×(D+1)维的实数 向量： 每个个体Xi包含M条路径； 每条路 径用一个(D+1)维的向量表示， 按前后基因互相关联的编码方式对路径方案中的每一条路 径进行编码： 路径在编码 中简单地用关键点序列表示， 前D个实数是角的弧度值， 表示该数 对应的关键点与前一个点连线与水平线之间的夹角， 第D+1个实数ei， k映射为具体目的地； θi， k， 1对应的关键点的前一个点是路径的入口组的位置， θi， k， D对应的关键点的后一个点是 ei， k对应的目的地， 除了第一个关键点以外， 其他关键点的前一个点均为关键点； 所述关键 点在路径上依次按预设距离排列。 2.根据权利要求1所述的基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述目标函数值按如下 方式计算： f1＝∑H(C) f2＝L/T 其中， C是以预设边长对场景进行网格划分后得到的某个方形区域的中心点； H(C)是不权　利　要　求　书 1/2 页 2 CN 112884229 B 2同路径的行人经过点C所在方形区域的频率的熵； f1是所有网格中心点熵的和， 表示整个路 径方案的熵； L是在进行评估的仿真结束时仍然留在场景内的人数， T是进行评估的仿真过 程中进入场景的总人数， f2反映给定路径方案下人群通过场景的效率； 两个目标函数值被 合称为适应度。 3.根据权利要求1所述的基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述 步骤S2中测试向量按如下 方式构建： 其中， ui， m是测试向量第i个向量中的第m个元素， xi， m是目标向量第i个向量中的第m个 元素， m＝1， 2， ......， M ×(D+1)， F和CR是范围在(0， 1)之间的参数， F是缩放比例因子， CR是 差分进化中个体交叉的概率， Xb和Xd是在种群中随机选择的除Xi外的两个不同的个体， xb， m 和xd， m则是这两个 个体的目标向量中的第m个元 素。 4.根据权利要求1所述的基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述 步骤S3中更新测试向量按如下 方式操作： 对每个种群个体， 根据目标向量的路径方案计算测试向量； 选定对测试向量路径方案 熵值贡献最大的路径， 应用该路径的起点和终点， 按 前后基因互相关联的编 码方式， 重新随 机生成一条路径； 用生成的这条路径代替测试向量路径方案中对熵值贡献最大的那条路 径。 5.根据权利要求1所述的基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述 步骤S5中所述后期处 理为平滑处理。 6.根据权利要求1至5任一所述的基于差分进化算法的大型公共场所人流引 导路径规 划方法， 其特 征在于， 所述 步骤S2和步骤S3中适应度评估， 按如下 方式操作： 比较所述种群个体目标向量和测试向量的适应度， 适应度包括两个目标函数值， 如果 测试向量的两个目标函数值 都小， 即测试向量支配目标向量， 则用测试向量取代目标向量； 如果目标向量的两个目标函数值都小， 即目标向量支配测试向量， 则舍弃测试向量； 如果测 试向量有目标函数值比目标向量的目标函数值小， 目标向量也有目标函数值比测试向量的 目标函数值小， 即目标向量和 测试向量互不支配， 此时将测试向量记录下来。 7.根据权利要求1至5任一所述的基于差分进化算法的大型公共场所人流引 导路径规 划方法， 其特 征在于， 所述 步骤S2和步骤S3中多目标选择操作， 按如下 方式操作： 将记录下来的测试向量加入当前种群， 执行基于非支配排序和拥挤距离的多目标选择 操作， 逐个选择优秀的个 体， 使得当前种群的大小保持为 N。 8.根据权利要求7所述的基于差分进化算法的大型公共场所人流引导路径规划方法， 其特征在于， 所述基于非支配排序和拥挤距离操作， 具体过程如下： 将所有种群个体根据支配关系分配为指定个前沿， 前一个前沿支配后一个前沿， 同一 个前沿内的种群个体互相不支配； 如果一个种群个体的两个目标函数值 都优于另一个种群 个体， 则称前者支配后者； 计算前沿中每 个种群个体的拥挤距离， 并按照拥挤距离从大到小排序； 优先选择靠前的前沿中的种群个体加入新种群， 在同一个前沿中则优先将拥挤距离大 的种群个体加入新种群， 直到新种群大小为 N。权　利　要　求　书 2/2 页 3 CN 112884229 B 3