搜索

文章查询

x

留言板

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

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

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

王培良 张婷 肖英杰

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

王培良, 张婷, 肖英杰
PDF
HTML
导出引用
导出核心图
  • 针对疏散路径规划问题, 以栅格化地图为背景的基础上, 提出了蚁群元胞优化算法. 首先为统一仿真时间步长, 建立以六边形元胞为基础的栅格地图; 然后利用静态势场对启发函数进行优化, 利用分段更新规则优化信息素更新方式; 最后, 将模型参数作为粒子群优化算法的粒子位置信息进行优化, 求解参数的最优组合值. 仿真结果表明: 采用蚁群元胞优化模型进行疏散路径规划时, 不仅加快了搜索速度, 而且增大了解空间, 提高了搜索能力, 可以有效避免陷入局部最优解.
      通信作者: 王培良, gfy5216@126.com
    • 基金项目: 国家级-国家科技支撑计划子课题(2015BAG20B05-02)
    [1]

    Dorigo M, Gambardella L M 1997 BIOSYSTEMS 43 73

    [2]

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

    [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 604

    [5]

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

    [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 Vienna, Austria, July, 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 3001

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

    [15]

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

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

    [16]

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

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

    [17]

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

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

    [18]

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

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

    [19]

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

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

    [20]

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

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

    [21]

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

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

    [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 × (Tmax - t)/ Tmax + 0.2t为当前迭代次数
    λ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 73

    [2]

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

    [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 604

    [5]

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

    [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 Vienna, Austria, July, 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 3001

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

    [15]

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

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

    [16]

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

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

    [17]

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

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

    [18]

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

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

    [19]

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

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

    [20]

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

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

    [21]

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

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

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

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

  • 1. 上海海事大学商船学院, 上海 201306
  • 2. 山东交通职业学院航海学院, 潍坊 261206
  • 3. 潍坊科技学院, 潍坊 262700
  • 通信作者: 王培良, gfy5216@126.com
    基金项目: 国家级-国家科技支撑计划子课题(2015BAG20B05-02)

摘要: 针对疏散路径规划问题, 以栅格化地图为背景的基础上, 提出了蚁群元胞优化算法. 首先为统一仿真时间步长, 建立以六边形元胞为基础的栅格地图; 然后利用静态势场对启发函数进行优化, 利用分段更新规则优化信息素更新方式; 最后, 将模型参数作为粒子群优化算法的粒子位置信息进行优化, 求解参数的最优组合值. 仿真结果表明: 采用蚁群元胞优化模型进行疏散路径规划时, 不仅加快了搜索速度, 而且增大了解空间, 提高了搜索能力, 可以有效避免陷入局部最优解.

English Abstract

    • 随着现代工业和科技的发展, 大型建筑物结构变得越来越复杂, 突发事件的发生, 使得疏散人群的难度越来越高, 易造成重大的人员伤亡和经济损失. 如何快速及时的预警、应对突发事件已经成为世界范围内亟待解决的问题. 疏散路径规划是提升疏散成功率的有效方式之一, 大量学者正进行坚持不懈的研究, 以期最大限度地降低发生突发事件所带来的危害, 因此疏散路径规划已成为当前学科研究的重点和热点.

      目前, 在应急疏散路径规划中应用较为广泛的算法有Dijkstra算法、Floyd算法、A*算法、蚁群算法(ant colony clgorithm, ACO)等. 相比于时间损耗较大的Dijkstra算法、时间复杂度较高而不适应大量数据仿真的Floyd算法、以及易陷入局部最优解的A*算法, Dorigo和Gambardella [1]提出的带有正反馈、启发式的ACO算法, 具有较强的鲁棒性及全局搜索能力, 在解决路径规划问题时效果良好. Babinec等[2]提出了跳点搜索策略, 减少了遍历节点的数目, 提高了算法运算速度, 但是在所规划的路径中仍存在转折点. Cui等[3]通过改进启发式因子对蚁群算法进行优化, 提升了寻径效果. Imen等[4]提出了改进的禁忌搜索模型, 用于求解网格地图中的路径规划问题. Dorigo和Gambardella[5]通过研究提出了蚂蚁系统模型(ant colony system, ACS), 该算法能够在保持蚂蚁算法模型的基础上, 精简了算法结构. Stützle和Hoos[6,7]提出了最大-最小蚂蚁系统(max-min ant system, MMAS), 该算法通过设置信息素的阈值提高了其全局搜索能力, 避免出现停滞现象. 张玮等[8]将蚁群算法与烟花算法相结合, 通过对信息素的初始值进行优化提升算法性能. 胡启国等[9]通过优化信息素更新和状态转移规则, 解决了算法容易陷入局部最优解的问题. Hsu等[10]通过改进信息素的更新规则对蚁群算法进行优化, 缓解了原算法易陷入局部最优解的问题. 李东妮等[11]将蚁群算与遗传算法相结合, 加入交叉和变异算子, 增加了获得全局最优解的概率. 王晓燕等[12]结合人工势场法, 通过优化信息素初始值以及挥发系数, 提升了算法搜索能力. 总之, 现有研究主要依据传统四边形栅格为背景的ACO算法, 并进行优化来进行路径规划[13,14], 未能解决仿真时步长不统一问题, 同时对算法参数的优化也未能提出系统性方法[15-17].

      鉴于上述问题, 本文提出蚁群元胞优化模型(ant colony cellular optimization, ACCO), 以六边形栅格为仿真地图划分依据, 重新设计并优化启发函数和信息素更新方式, 以期提升ACCO算法的搜索能力、收敛速度等. 同时系统性地提出利用粒子群优化(partical swarm optimization, PSO)算法对ACCO算法参数进行优化的方法[18]. 最后通过仿真对比分析, 验证ACCO算法的可行性和有效性.

    • 在进行传统的路径规划仿真求解时, 均使用的四边形栅格地图[19,20], 且一般采用moore型邻域, 即$N = \left\{ {{s_1}, {s_2}, \cdots {s_i}} \right\}, i \in \left[ {1, 8} \right], {s_i} \in \left[ {0, 1} \right]$, isi均取整数, i表示邻域元胞编号, si表示元胞是否被选中, 取1时表示被选中, 灰色为中心元胞即蚂蚁当前所在元胞, 黑色元胞表示障碍物或者边界, (2 1)分别表示栅格的行列号(行号以中心点所在位置为基准, 列号同理), 如图1(a)所示.

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

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

      使用上述四边形栅格在进行系统仿真时, 假定栅格的边长为e, 则选择下一步的目标元胞时, 极轴和斜向方向的移动距离分别为e$\sqrt 2 e$, 如图1(b)所示, 因此当元胞的移动速度v不变时, 元胞的移动时间为${}^{e}\!\!\diagup\!\!{}_{v}\;$或者$\sqrt{2}{}^{e}\!\!\diagup\!\!{}_{v}\;$, 产生时间步长不统一问题, 影响模型的真实性. 为有效避免“斜向穿墙”现象, 提出使用六边形栅格, 当栅格边长仍为e时, 元胞每次仿真移动的距离为$\sqrt 3 e$, 移动时间为$\sqrt{3}{}^{e}\!\!\diagup\!\!{}_{v}\;$, 如图1(c).

      因此, 建立六边形栅格地图, 并以地图左下角为原点建立笛卡尔坐标系, 水平方向为X轴. 设每个六边形的内切圆圆心为其中心坐标点, 则坐标值(x, y)为

      $ \begin{array}{*{20}{c}} {x = \left\{ {\begin{aligned} &{\frac{{5e}}{2} + \left( {j - 1} \right) \times {\rm{d}}x,} \quad{{\rm{mod}}\left( {i,2} \right) = 1,}\\ &{e + \left( {j - 1} \right) \times {\rm{d}}x,}\quad{{\rm{mod}}\left( {i,2} \right) = 0,} \end{aligned}} \right.}\\ {y = {\rm{d}}y \times i,} \end{array} $

      其中i为当前栅格行号, $i \in \left[ {1, 2, \cdots {N_i}} \right]$; j为当前栅格列号, $j \in [1, 2, \cdots {N_j}]$; NiNj分别为栅格的行列总数; ${\rm{d}}x = \sqrt 3 e$${\rm{d}}y = {}^{\sqrt{3} e}\!\!\diagup\!\!{}_{2}\;$分别为x, y方向上的单位增量.

    • 使用ACCO算法对疏散路径进行规划时, 采用六边形栅格将仿真环境划分为均匀的离散网格图, 然后计算出从起始节点到目的节点的可行网格链集合, 最后在集合中选择最优解[21].

      蚁群元胞优化算法可表示为:

      $ {\rm{ACCO}} = \left( {{G_{m \times n}},{P_{m \times n}},{C_{\rm{S}}},{C_{\rm{w}}},{C_{\rm{N}}},{C_{\rm{R}}},O} \right), $

      其中${G_{m \times n}}$为网格地图的信息矩阵; ${P_{m \times n}}$为信息素矩阵; mn表示矩阵的行列数, m一般与单次迭代蚂蚁数量相同; CS为元胞状态, 取值为${\rm{\{ 0, 1\} }}$, 表征此元胞是否被占用, 1表示被占用; Cw为元胞空间, w表示空间维数, 从G中获取, 这里w取2维; CN为元胞邻域, 使用1.1节中所述Moore型; CR为元胞规则, 是蚁群移动的基本约束, 主要取决于三点, 即1)所选元胞为非障碍物或边界; 2)所选元胞更加有利于到达目的元胞; 3)概率转移公式决定邻域元胞被选中的概率, 如

      $ {p_{ij}} = \left\{ {\begin{aligned} & {\frac{{{{\left( {{\tau _{ij}}} \right)}^\alpha } \times {{\left( {{\eta _{ij}}} \right)}^\beta }}}{{\mathop \sum \nolimits_{{\rm{s}} \in {\rm{tabu}}} {{\left( {{\tau _{ij}}} \right)}^\alpha } \times {{\left( {{\eta _{ij}}} \right)}^\beta }}},\;{\rm{if}}\;j \notin {\rm{tabu}},}\\ & {0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{others}},} \end{aligned}} \right. $

      其中pij为由元胞i转移到元胞j的概率值, τij为元胞ij之间的信息素浓度, ηij为元胞ij之间的启发函数, αβ为信息素启发因子和期望启发因子, tabu为当前蚂蚁的禁忌表; O为优化策略, 主要针对传统模型存在的问题进行优化, 详见第3节.

    • ACCO算法的优化策略主要是对启发函数、信息素更新方式以及参数组合设定等方面优化, 以解决传统蚁群算法在进行路径规划问题时存在的收敛速度慢、搜索空间小、易陷入局部最优解等问题.

    • 启发函数表征各邻域元胞被选择的期望程度, 传统四边形栅格地图常选用两元胞之间的距离值为参考标准, 而六边形栅格地图两元胞之间的距离值为常数, 导致启发函数为常数而失去价值. 将静态势场引入启发函数的设计优化中. 静态势场值反映邻域元胞与目的元胞之间的距离程度, 距离越近, 静态势场值越大, 因此符合模型对启发函数的要求. 同时静态场值的引入在提高模型收敛速度的基础上, 降低了迂回现象的发生概率.

      优化后的启发函数为

      $ {\eta _{ij}} = \frac{1}{{\left| {X - {X_i}} \right| + \left| {Y - {Y_i}} \right| + C}}, $

      其中$\left( {X, Y} \right)$$({X_i}, {Y_i})$分别为目的元胞和邻域元胞在元胞空间的横纵坐标, C为常数, 一般取0.001, 目的是为防止目的元胞自身的启发函数无意义.

      同时, 为增加解空间的范围, 提升最优解的效果, 当ACCO算法迭代到一定次数后, 对最优路径中的节点与目的节点之间的启发函数使用(3)式进行更新:

      $\begin{split} & {{\eta _{id}} = \frac{1}{{{D_{id}}}},}\\ & {{D_{id}} = S - {D_{\left( {i - 1} \right)d}},} \end{split} $

      其中Did为节点i与目的节点d之间的距离值, S为最优路径长度, i-1为最优路径中节点i的前一节点.

    • 当前常用的信息素更新方式主要分为三类: 蚁密模型, 蚁量模型, 以及蚁周模型. 以蚁周模型为基础, 将全局信息素浓度的值限定在阈值[τmin, τmax]范围内, 设计分段更新规则进行信息素的更新, 公式如下:

      $ {\tau _{ij}} =\begin{cases} {{\tau _{{\rm{max}}}},}&{{\tau _{ij}} \geqslant {\tau _{{\rm{max}}}},}\\ {{\tau _{{\rm{min}}}},}&{{\tau _{ij}} \leqslant {\tau _{{\rm{min}}}},}\\ {\left( {1 - \rho } \right){\tau _{ij}}\left( t \right) +\sum\limits_{k = 1}^m \Delta \tau _{ij}^k\left( t \right),}&{{\text{其他}},} \end{cases} $

      $ \Delta \tau _{ij}^k = \begin{cases} {\dfrac{Q}{{{L_{\rm{b}}}}},}&{\text{路径}}\left( {i,j} \right){\text{在本次迭代结果的}}\\ &{\text{最优路径中}},\\ {\dfrac{Q}{{{L_k}}},}&{\text{路径}}\left( {i,j} \right){\text{在本次迭代结果的非}}\\&{\text{最优路径中}},\\ 0,&{\text{其他}}, \end{cases} $

      其中k为当前蚂蚁; 信息素浓度τmin, τmax分别为${1}/{{{L_{\rm{b}}}}}$, ${\tau}_{\text{max}}/{20}$; $\rho \in \left[ {0, 1} \right]$为信息素挥发系数; Q为信息素浓度总量; Lb为本次迭代的最优路径长度值; Lk为蚂蚁k完成本次搜索所经过的路径长度.

    • 在ACCO算法中, 参数α, β, ρ对算法的收敛速度以及解空间的大小等性能影响显著: 参数α值越小, 算法搜索的随机性增强, 但算法的收敛速度变慢; 参数β值越小, 算法越易陷入局部最优解; 参数ρ直接影响模型的全局搜索能力和收敛速度. 因此, 为提升模型性能, 将利用粒子群优化算法对参数进行优化求解.

      粒子群优化算法是由Eberhart与Kennedy[22]在20世纪90年代提出的一种基于种群的全局随机优化算法. 该算法中的每个粒子根据自身及其他粒子的位置信息不断调整移动速度, 同时调整移动的方向和距离, 从而实现粒子在解空间内的全局寻优. 在算法求解的迭代过程中, 粒子通过个体极值和全局极值调整自身的速度与位置, 其公式如下:

      $ \begin{split} & {V_{ig}^t = \omega V_{ig}^t + {c_1}{r_1}\left( {P_{ig}^t - X_{ig}^t} \right) + {c_2}{r_2}{r_1}\left( {P_{gg}^t - X_{ig}^t} \right),}\\ & {X_{ig}^k = X_{ig}^k + V_{ig}^k,} \end{split} $

      其中V表示粒子速度; ${{X}} = \left( {{X_1}, \;{X_2}, \;{X_3}, \; \cdots \;{X_n}} \right)$G维空间n个粒子组成的种群, 分别代表粒子当前位置; ω为惯性权重; $g = 1, 2 \cdots , G$; $i = 1, 2 \cdots , n$表示粒子编号; t为当前迭代次数; Pig为个体极值; Pgg为全局极值; c1c2为非负常数, 称为加速度因子; r1r2为介于$\left[ {0, 1} \right]$之间的随机数.

      使用粒子群优化算法进行参数优化的思路是: 将ACCO算法的参数α, β, ρ作为粒子群优化算法的粒子位置信息进行求解, 通过适应度评价函数不断调整粒子位置, 从而求得参数的最优值和组合值. 因此针对解路径规划问题, 综合考虑寻优能力、运行时间、收敛速度和稳定性等影响因素, 设计出如下适应度评价函数:

      $ \begin{split} & { {{F}_{i}}\left( x \right)={{\lambda }_{1}}{{L}_{i}}\left( x \right)+{{\lambda }_{2}}{{S}_{i}}\left( x \right)+{{\lambda }_{3}}{{Q}_{i}}\left( x \right)-{{\lambda }_{4}}{{T}_{i}}\left( x \right),}\\ & {{{L}_{i}}\left( x \right)~={}^{1}\!\!\diagup\!\!{}_{\left( {{L}_{\rm{best}}}+1 \right)}\;,}\\ & {{{S}_{i}}\left( x \right)={{\rm{e}}^{{}^{-{{N}_{\rm{best}}}}\!\!\diagup\!\!{}_{{{N}_{\rm{max}}}}\;}},}\\ & {{{Q}_{i}}\left( x \right)={}^{1}\!\!\diagup\!\!{}_{{{L}_{\rm{std}}}}\;,}\\ & {{{T}_{i}}\left( x \right)=~{{\rm{e}}^{1-{}^{1}\!\!\diagup\!\!{}_{\rm{Dis}}\;}},} \end{split} $

      其中${F_i}\left( x \right)$为第i个粒子代表的参数所对应的适应度函数值; λ1, λ2, λ3, λ4为权重系数, 且满足λ1 + λ2 + λ3 + λ4 = 1; ${L_i}\left( x \right)$是使用粒子i运算所得的参数, 表示ACCO算法搜索最优路径的能力; Lbest表示每次PSO迭代所得到的最优路径的元胞数量; ${S_i}\left( x \right)$是使用粒子i运算所得的参数, 表征ACCO算法的收敛速度; Nbest为ACCO算法搜索到当前最优路径时自身的迭代次数; Nmax为元胞蚂蚁的最大迭代次数; ${Q_i}\left( x \right)$是使用粒子i运算所得的参数, 表示ACCO算法的稳定性; Lstd为每次PSO迭代过程中, 表征ACCO算法搜索到的路径的方差; ${T_i}\left( x \right)$表示使用粒子i运算所得的参数, 表征ACCO算法的运行时间; Dis表示元每次PSO迭代过程中ACCO算法搜索路径总和.

    • 使用ACCO算法进行路径规划的流程如图2所示.

      图  2  算法流程图

      Figure 2.  Simulation flow chart.

    • 为验证所构建模型的性能, 以某大型邮轮的B甲板上的展厅为工程背景进行仿真, 模型的信息素浓度取14, 蚂蚁数量为30, 计算对比ACCO算法与传统算法的优劣, 邮轮B甲板构造详情如图3所示.

      图  3  某邮轮B甲板构造图

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

      甲板中间位置展厅面积为20 m × 20 m的封闭空间, 其构造详情见图4(a), 仿真环境为20 × 20的栅格地图, 如图4(b)所示.

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

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

    • 根据专家经验法[23], 对PSO算法的其他参数值分别按照表1进行赋值.

      参数名称参数取值备注
      c1, c21.49445
      Tmax50最大迭代次数
      ω0.5 × (Tmax - t)/ Tmax + 0.2t为当前迭代次数
      λ10.7
      λ20.1
      λ30.1
      λ40.1

      表 1  PSO算法参数取值

      Table 1.  The parameters of PSO algorithm.

      根据仿真要求进行两组运算, 其求解结果如表2所列.

      参数名称αβρ
      参数组13.508.050.68
      参数组21.358.500.36

      表 2   参数求解结果

      Table 2.  Parameter solution results.

      同时为观察适应度评价函数性能, 对比分析两组参数的适应度值曲线, 如图5所示.

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

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

    • 根据上述模型构建描述及参数设定, 分别使用传统算法与ACCO算法进行仿真, 其最终路径效果如图6所示.

      图  6  仿真效果图

      Figure 6.  Simulation effect chart.

      图6S表示起始节点, E表示目的节点. 从图6可知, 传统模型与ACCO算法均可进行有效路径规划.

    • 当最大迭代次数一定时, 由于传统算法与ACCO算法在路径选择概率上的差异, 导致每次迭代所有蚂蚁搜寻的总路径长度和搜索速度也不同, 其结果如图7所示.

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

      Figure 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.

      图7分析可知, 两类算法在搜索路径时, 所经过的元胞总数随着迭代次数的增加而逐渐减少; 在算法迭代次数相同的情况下, ACCO算法经过的元胞总数明显小于传统算法, 表明ACCO算法的搜索速度较快; 随着迭代的不断进行, 传统算法的搜索已基本停滞, 而ACCO算法仍在进行; 横向对比图7(a),(b),(c),(d)可知, 当只是优化启发函数或者信息素更新方式时, 优化算法所经过的元胞总数高于ACCO算法, 并且在收敛性方面也相对较弱, 但是优化算法的规划效果明显高于传统算法; 同时从图7(b)中曲线走势可明显看出, 优化后的启发函数对算法搜索能力和收敛速度的提升; 对比分析图7(b),(e),(f)可知, 基于经验值的ACCO算法的收敛速度和搜索速度明显弱于参数组1, 参数组2, 但是收敛性比参数组1强, 而参数组2在收敛速度、搜索能力以及收敛性方面均表现出明显优势. 此外, 由于存在部分断头路径问题, 传统算法在前期的搜索中波动性比较明显. 因此在算法搜索能力上, ACCO算法表现出更佳的性能.

    • 由于ACCO算法对部分参数进行优化, 导致其与传统算法在搜索能力上存在差距, 因此当增加迭代次数时, 解空间也表现出差异, 如图8所示.

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

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

      分析图8可知, 当迭代进行到第70次时, 传统算法的搜索路径已基本停滞, 从而解空间已经固定, 陷入局部最优解的可能性增大; 而ACCO算法在迭代进行到近200次时, 搜索路径的元胞总数依旧在减小, 解空间在不断增加, 表明仍然在搜寻全局最优解. 因此传统算法相比ACCO算法而言, 更易陷入局部最优解.

    • 在对算法的搜索能力以及收敛性等性能进行了上述分析后, 为了进一步凸显本文所提算法的优势, 现对算法其他方面性能进行分析, 主要包括:

      运行时间是指在相同的运行环境中, 算法运行所消耗的平均时间;

      可重复性是指对真实环境进行仿真时, 对于相同输入数据, 经过多次重复实验, 实验过程中出现完全相同的局部最优路径的概率;

      收敛速率是指算法运行过程中, 相邻迭代过程中最优路径的元胞数之差的平均值; 最优性是指经过相同的迭代次数, 算法搜索到的最优路径的元胞数量, 以第100次迭代为例. 详见表3.

      时间复杂度运行时间/s收敛
      速率
      最优性/个可重
      复性
      传统
      算法
      O(Nmaxn2m)94.157737–0.937625%
      本文
      算法
      O(Nmaxn2m)111.091862–1.2257130%

      表 3  算法性能对比表

      Table 3.  Performances comparison of algorithms.

      通过分析可知, ACCO算法与基本蚁群算法时间复杂度的区别主要在启发函数和信息素的更新方式上, 但是改进算法只增加了时间复杂度的常数项和低幂次项, 可以忽略, 因此时间复杂度并未改变, 但由于增加了邻域元胞的选择性从而导致运行时间有所加长. 同时改进算法在收敛速率、最优性和可重复性方面均展现出明显优势.

    • 在进行路径规划算法时, 传统算法使用四边形栅格地图进行求解, 容易导致时间步长不一致、搜索速度慢、易陷入局部最优解等问题.

      针对以上问题, 提出以六边形栅格替代传统四边形栅格作为背景地图栅格化方法, 从而解决四边形栅格地图的时间步长不统一的问题, 为对比算法性能奠定基础. 同时, 分别对启发函数以及信息素更新方式进行了优化设计. 最后将ACCO算法的参数作为PSO算法的位置信息进行迭代求解, 利用适应度函数值对求解性能做出评价, 从而得到ACCO的最优参数组合. 仿真实验结果表明, 提出的ACCO算法相比于传统算法, 在算法收敛速度、算法搜索速度、最优解的搜寻能力等各方面上均有明显优势, 因此可以为智能疏散系统的开发设计提供有益参考.

参考文献 (23)

目录

    /

    返回文章
    返回