搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

蚁群元胞优化算法在人群疏散路径规划中的应用

王培良 张婷 肖英杰

引用本文:
Citation:

蚁群元胞优化算法在人群疏散路径规划中的应用

王培良, 张婷, 肖英杰

Application research of ant colony cellular optimization algorithm in population evacuation path planning

Wang Pei-Liang, Zhang Ting, Xiao Ying-Jie
PDF
HTML
导出引用
  • 针对疏散路径规划问题, 以栅格化地图为背景的基础上, 提出了蚁群元胞优化算法. 首先为统一仿真时间步长, 建立以六边形元胞为基础的栅格地图; 然后利用静态势场对启发函数进行优化, 利用分段更新规则优化信息素更新方式; 最后, 将模型参数作为粒子群优化算法的粒子位置信息进行优化, 求解参数的最优组合值. 仿真结果表明: 采用蚁群元胞优化模型进行疏散路径规划时, 不仅加快了搜索速度, 而且增大了解空间, 提高了搜索能力, 可以有效避免陷入局部最优解.
    With the improvement of people's living standards, large-scaled public activities have increased considerably, and the emergency probability has increased greatly. When an emergency occurs, the emergency evacuation can effectively reduce casualties and economic losses. Therefore, how to quickly evacuate crowd is a current research hotspot in this field. The path planning of emergency evacuation is one of the effective ways to implement the crowd evacuation. Aiming at the problem of path planning for emergency evacuation and taking the grid map as the background, the ant colony cellular optimization (ACCO) algorithm is proposed as the path planning algorithm based on the cellular automata theory and ant colony algorithm. Firstly, in order to solve the problem of inconsistent time steps in the quadrilateral grid map, the grid map based on hexagonal cell is established and the ACCO algorithm is developed based on the hexagonal grid map. And the method of solving grid coordinate is given. Then, in order to improve the convergence speed and search ability of the ACCO algorithm, the static field is used to optimize the heuristic function, and the segment update rule is used to optimize the pheromone update method. Finally, the parameters of ACCO algorithm are optimized through the particle swarm optimization (PSO) algorithm. The method of designing the fitness evaluation function is proposed, and the optimal combination of parameters of the ACCO algorithm is implemented according to the fitness function. In order to verify the scientificity and effectiveness of the algorithm proposed in this research and also to systematically verify the optimization strategy, in this research the exhibition hall on the B-deck of a large cruise ship is used as the engineering background, and the traditional algorithm and the ACCO algorithm are adopted to perform the simulations. The simulation results show that compared with the traditional quadrilateral grid, the hexagonal grid proposed in this research unifies the simulation time step and can be used as the division method of the simulation environment. At the same time, the ACCO algorithm can effectively perform the evacuation path planning, and the optimization strategy proposed in this research not only acceletates the search speed, but also increases the solution space and improves the search ability, which can effectively avoid falling into the local optimal solution.
      通信作者: 王培良, gfy5216@126.com
    • 基金项目: 国家级-国家科技支撑计划子课题(2015BAG20B05-02)
      Corresponding author: Wang Pei-Liang, gfy5216@126.com
    [1]

    Dorigo M, Gambardella L M 1997 Biosystems 43 73Google Scholar

    [2]

    Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L 2014 Procedia Eng. 96 59Google Scholar

    [3]

    Cui S G, Wang H, Li J G 2013 Third International Conference on Instrumentation & Measurement, Computer, Communication and Control Shenyang, China, September 21–23, 2013 p200

    [4]

    Chaari I, Koubaa A, Bennaceur H, Ammar A, Trigui S, Tounsi M, Shakshuki E, Youssef H 2014 Procedia Comput. Sci. 32 604Google Scholar

    [5]

    Dorigo M, Gambardella L M 1997 IEEE Trans. Evol. Comput. 1 53Google Scholar

    [6]

    Stützle T, Hoos H 1999 Meta-heuristics (Boston: Springer) p313

    [7]

    Stützle T, Hoos H 1998 Artificial Neural Nets and Genetic Algorithms Norwich, England, April 2–4, 1998 p245

    [8]

    张玮, 马炎, 赵捍东 2019 控制与决策 34 335

    Zhang W, Ma Y, Zhao H D 2019 Control Decis. 34 335

    [9]

    胡启国, 胡小华, 吴泳龙 2013 重庆交通大学学报 (自然科学版) 32 543

    Hu Q G, Hu X H, Wu Y L 2013 J. Chongqing Jiaotong Univ.(Natural Science). 32 543

    [10]

    Hsu C C, Hou R Y, Wang W Y 2013 IEEE International Conference on Systems, Man, and Cybernetics Manchester, United Kingdom, October 13–16, 2013 p2777

    [11]

    李冬妮, 贾晓宇, 陈琳, 郑丹, 陶军 2017 北京理工大学学报 37 704

    Li D N, Jia X Y, Chen L L, Zheng D, Tao J 2017 Trans. Beijing Inst. Technol. 37 704

    [12]

    王晓燕, 杨乐, 张宇, 孟帅 2018 控制与决策 33 1775

    Wang X Y, Yang L, Zhang Y, Meng S 2018 Control Decis. 33 1775

    [13]

    Zhao K, Sun X, Wang D 2017 Bull. Sci. Technol. 33 76

    [14]

    周金旺, 刘慕仁, 孔令江, 邝华 2009 物理学报 58 3001Google Scholar

    Zhou W C, Liu M R, Kong L J, Kuang H 2009 Acta Phys. Sin. 58 3001Google Scholar

    [15]

    刘毅, 沈斐敏 2018 控制与决策 33 1598

    Liu Y, Shen F M 2018 Control Desci. 33 1598

    [16]

    董力耘, 陈立, 段晓茵 2015 物理学报 64 220505Google Scholar

    Dong L Y, Chen L, Duan X Y 2015 Acta Phys. Sin. 64 220505Google Scholar

    [17]

    禹尔东, 吴正, 郭明旻 2014 物理学报 63 094501Google Scholar

    Yu E D, Wu Z, Guo M W 2014 Acta Phys. Sin. 63 094501Google Scholar

    [18]

    陈亮, 郭仁拥, 塔娜 2013 物理学报 62 050506Google Scholar

    Chen L, Guo R Y, Ta N 2013 Acta Phys. Sin. 62 050506Google Scholar

    [19]

    岳昊, 邵春福, 姚智胜 2009 物理学报 58 4523Google Scholar

    Yue H, Shao C F, Yao Z S 2009 Acta Phys. Sin. 58 4523Google Scholar

    [20]

    张磊, 岳昊, 李梅, 王帅, 米雪玉 2015 物理学报 64 060505Google Scholar

    Zhang L, Yue H, Li M, Wang S, Mi X Y 2015 Acta Phys. Sin. 64 060505Google Scholar

    [21]

    谢积鉴, 薛郁 2012 物理学报 61 194502Google Scholar

    Xie J J, Xue Y 2012 Acta Phys. Sin. 61 194502Google Scholar

    [22]

    Eberhart R, Kennedy J 1995 MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science Nagoya, Japan, October 4-6, 1995 p39

    [23]

    Eberhart R C, Shi Y 2000 Proceedings of the 2000 Congress on Evolutionary Computation La Jolla, USA, July 16–19, 2000 p84

  • 图 1  栅格示意图 (a) Moore型邻域; (b) 传统四边形栅格; (c) 改进六边形栅格

    Fig. 1.  Grid schematic: (a) Mooretype neighborhood; (b) traditional quadrilateral grid; (c) improved hexagon grid.

    图 2  算法流程图

    Fig. 2.  Simulation flow chart.

    图 3  某邮轮B甲板构造图

    Fig. 3.  B-deck structure diagram of a cruise ship.

    图 4  展厅构造与仿真图 (a) 展厅构造图; (b) 仿真环境图

    Fig. 4.  Exhibition hall construction and simulation: (a) Exhibition hall structure; (b) simulation environment diagram.

    图 5  粒子适应度值曲线 (a) 参数组1; (b) 参数组2

    Fig. 5.  The fitness value curves: (a) Parameter group 1; (b) parameter group 2.

    图 6  仿真效果图

    Fig. 6.  Simulation effect chart.

    图 7  路径长度对比 (a) 传统算法路径统计; (b) 基于经验参数的ACCO算法路径统计; (c) 启发函数优化后的路径统计; (d) 信息素更新优化的路径统计; (e) 基于参数组1的路径统计; (f) 基于参数组2的路径统计

    Fig. 7.  Path length comparison: (a) The path statistics for traditional algorithm; (b) the path statistics for ACCO algorithm with experience; (c) the path statistics for only optimizing heuristic function; (d) the path statistics for only optimizing pheromone update methods; (e) the path statistics for parameter group 1; (f) the path statistics for parameter group 2.

    图 8  路径长度迭代对比 (a) 传统算法; (b) ACCO算法

    Fig. 8.  Iteration comparison of path length: (a) Traditional algorithm; (b) ACCO algorithm.

    表 1  PSO算法参数取值

    Table 1.  The parameters of PSO algorithm.

    参数名称参数取值备注
    c1, c21.49445
    Tmax50最大迭代次数
    ω$ 0.5 \times (T_{\max} - t)/ T_{\max} + 0.2 $t 为当前迭代次数
    λ10.7
    λ20.1
    λ30.1
    λ40.1
    下载: 导出CSV

    表 2   参数求解结果

    Table 2.  Parameter solution results.

    参数名称αβρ
    参数组13.508.050.68
    参数组21.358.500.36
    下载: 导出CSV

    表 3  算法性能对比表

    Table 3.  Performances comparison of algorithms.

    时间复杂度运行时间/s收敛
    速率
    最优性/个可重
    复性
    传统
    算法
    O(Nmaxn2m)94.157737–0.937625%
    本文
    算法
    O(Nmaxn2m)111.091862–1.2257130%
    下载: 导出CSV
  • [1]

    Dorigo M, Gambardella L M 1997 Biosystems 43 73Google Scholar

    [2]

    Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L 2014 Procedia Eng. 96 59Google Scholar

    [3]

    Cui S G, Wang H, Li J G 2013 Third International Conference on Instrumentation & Measurement, Computer, Communication and Control Shenyang, China, September 21–23, 2013 p200

    [4]

    Chaari I, Koubaa A, Bennaceur H, Ammar A, Trigui S, Tounsi M, Shakshuki E, Youssef H 2014 Procedia Comput. Sci. 32 604Google Scholar

    [5]

    Dorigo M, Gambardella L M 1997 IEEE Trans. Evol. Comput. 1 53Google Scholar

    [6]

    Stützle T, Hoos H 1999 Meta-heuristics (Boston: Springer) p313

    [7]

    Stützle T, Hoos H 1998 Artificial Neural Nets and Genetic Algorithms Norwich, England, April 2–4, 1998 p245

    [8]

    张玮, 马炎, 赵捍东 2019 控制与决策 34 335

    Zhang W, Ma Y, Zhao H D 2019 Control Decis. 34 335

    [9]

    胡启国, 胡小华, 吴泳龙 2013 重庆交通大学学报 (自然科学版) 32 543

    Hu Q G, Hu X H, Wu Y L 2013 J. Chongqing Jiaotong Univ.(Natural Science). 32 543

    [10]

    Hsu C C, Hou R Y, Wang W Y 2013 IEEE International Conference on Systems, Man, and Cybernetics Manchester, United Kingdom, October 13–16, 2013 p2777

    [11]

    李冬妮, 贾晓宇, 陈琳, 郑丹, 陶军 2017 北京理工大学学报 37 704

    Li D N, Jia X Y, Chen L L, Zheng D, Tao J 2017 Trans. Beijing Inst. Technol. 37 704

    [12]

    王晓燕, 杨乐, 张宇, 孟帅 2018 控制与决策 33 1775

    Wang X Y, Yang L, Zhang Y, Meng S 2018 Control Decis. 33 1775

    [13]

    Zhao K, Sun X, Wang D 2017 Bull. Sci. Technol. 33 76

    [14]

    周金旺, 刘慕仁, 孔令江, 邝华 2009 物理学报 58 3001Google Scholar

    Zhou W C, Liu M R, Kong L J, Kuang H 2009 Acta Phys. Sin. 58 3001Google Scholar

    [15]

    刘毅, 沈斐敏 2018 控制与决策 33 1598

    Liu Y, Shen F M 2018 Control Desci. 33 1598

    [16]

    董力耘, 陈立, 段晓茵 2015 物理学报 64 220505Google Scholar

    Dong L Y, Chen L, Duan X Y 2015 Acta Phys. Sin. 64 220505Google Scholar

    [17]

    禹尔东, 吴正, 郭明旻 2014 物理学报 63 094501Google Scholar

    Yu E D, Wu Z, Guo M W 2014 Acta Phys. Sin. 63 094501Google Scholar

    [18]

    陈亮, 郭仁拥, 塔娜 2013 物理学报 62 050506Google Scholar

    Chen L, Guo R Y, Ta N 2013 Acta Phys. Sin. 62 050506Google Scholar

    [19]

    岳昊, 邵春福, 姚智胜 2009 物理学报 58 4523Google Scholar

    Yue H, Shao C F, Yao Z S 2009 Acta Phys. Sin. 58 4523Google Scholar

    [20]

    张磊, 岳昊, 李梅, 王帅, 米雪玉 2015 物理学报 64 060505Google Scholar

    Zhang L, Yue H, Li M, Wang S, Mi X Y 2015 Acta Phys. Sin. 64 060505Google Scholar

    [21]

    谢积鉴, 薛郁 2012 物理学报 61 194502Google Scholar

    Xie J J, Xue Y 2012 Acta Phys. Sin. 61 194502Google Scholar

    [22]

    Eberhart R, Kennedy J 1995 MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science Nagoya, Japan, October 4-6, 1995 p39

    [23]

    Eberhart R C, Shi Y 2000 Proceedings of the 2000 Congress on Evolutionary Computation La Jolla, USA, July 16–19, 2000 p84

  • [1] 李鑫鹏, 曹睿杰, 李铭, 郭各朴, 李禹志, 马青玉. 基于粒子群算法的超振荡超分辨聚焦声场设计. 物理学报, 2022, 71(20): 204304. doi: 10.7498/aps.71.20220898
    [2] 张毅军, 慕晓冬, 刘潇文, 王星宇, 东晨, 吴田宜, 李凯. 量子近似优化算法在指挥控制组织任务规划中的应用. 物理学报, 2021, 70(23): 230304. doi: 10.7498/aps.70.20211028
    [3] 王大为, 王召巴. 一种强噪声背景下微弱超声信号提取方法研究. 物理学报, 2018, 67(21): 210501. doi: 10.7498/aps.67.20180789
    [4] 董力耘, 陈立, 段晓茵. 基于教室人群疏散实验的行人流建模和模拟. 物理学报, 2015, 64(22): 220505. doi: 10.7498/aps.64.220505
    [5] 赵志刚, 张纯杰, 苟向锋, 桑虎堂. 基于粒子群优化支持向量机的太阳电池温度预测. 物理学报, 2015, 64(8): 088801. doi: 10.7498/aps.64.088801
    [6] 黄宇, 刘玉峰, 彭志敏, 丁艳军. 基于量子并行粒子群优化算法的分数阶混沌系统参数估计. 物理学报, 2015, 64(3): 030505. doi: 10.7498/aps.64.030505
    [7] 禹尔东, 吴正, 郭明旻. 双出口房间人群疏散的实验研究和数学建模. 物理学报, 2014, 63(9): 094501. doi: 10.7498/aps.63.094501
    [8] 徐念喜, 高劲松, 冯晓国. 基于离散粒子群算法的频率选择表面优化设计研究. 物理学报, 2014, 63(13): 138401. doi: 10.7498/aps.63.138401
    [9] 陈颖, 王文跃, 于娜. 粒子群算法优化异质结构光子晶体环形腔滤波特性. 物理学报, 2014, 63(3): 034205. doi: 10.7498/aps.63.034205
    [10] 刘暾东, 陈俊仁, 洪武鹏, 邵桂芳, 王婷娜, 郑骥文, 文玉华. 基于粒子群算法的Pt-Pd合金纳米粒子的稳定结构研究. 物理学报, 2013, 62(19): 193601. doi: 10.7498/aps.62.193601
    [11] 永贵, 黄海军, 许岩. 菱形网格的行人疏散元胞自动机模型. 物理学报, 2013, 62(1): 010506. doi: 10.7498/aps.62.010506
    [12] 张宏立, 宋莉莉. 基于量子粒子群算法的混沌系统参数辨识. 物理学报, 2013, 62(19): 190508. doi: 10.7498/aps.62.190508
    [13] 刘福才, 贾亚飞, 任丽娜. 基于混沌粒子群优化算法的异结构混沌反同步自抗扰控制. 物理学报, 2013, 62(12): 120509. doi: 10.7498/aps.62.120509
    [14] 刘乐柱, 张季谦, 许贵霞, 梁立嗣, 黄守芳. 一个修改的混沌蚁群优化算法. 物理学报, 2013, 62(17): 170501. doi: 10.7498/aps.62.170501
    [15] 郭业才, 胡苓苓, 丁锐. 基于量子粒子群优化的正交小波加权多模盲均衡算法. 物理学报, 2012, 61(5): 054304. doi: 10.7498/aps.61.054304
    [16] 李盼池, 王海英, 宋考平, 杨二龙. 量子势阱粒子群优化算法的改进研究. 物理学报, 2012, 61(6): 060302. doi: 10.7498/aps.61.060302
    [17] 方伟, 孙俊, 谢振平, 须文波. 量子粒子群优化算法的收敛性分析及控制参数研究. 物理学报, 2010, 59(6): 3686-3694. doi: 10.7498/aps.59.3686
    [18] 王校锋, 薛红军, 司守奎, 姚跃亭. 基于粒子群算法和OGY方法的混沌系统混合控制. 物理学报, 2009, 58(6): 3729-3733. doi: 10.7498/aps.58.3729
    [19] 高 飞, 童恒庆. 基于改进粒子群优化算法的混沌系统参数估计方法. 物理学报, 2006, 55(2): 577-582. doi: 10.7498/aps.55.577
    [20] 王东风, 韩 璞. 基于粒子群优化的混沌系统比例-积分-微分控制. 物理学报, 2006, 55(4): 1644-1650. doi: 10.7498/aps.55.1644
计量
  • 文章访问数:  6064
  • PDF下载量:  138
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-11-22
  • 修回日期:  2020-01-09
  • 刊出日期:  2020-04-20

/

返回文章
返回