全文HTML
--> --> -->目前, 在应急疏散路径规划中应用较为广泛的算法有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算法的可行性和有效性.
2.1.栅格地图建立
在进行传统的路径规划仿真求解时, 均使用的四边形栅格地图[19,20], 且一般采用moore型邻域, 即
图 1 栅格示意图 (a) Moore型邻域; (b) 传统四边形栅格; (c) 改进六边形栅格Figure1. Grid schematic: (a) Mooretype neighborhood; (b) traditional quadrilateral grid; (c) improved hexagon grid.
使用上述四边形栅格在进行系统仿真时, 假定栅格的边长为e, 则选择下一步的目标元胞时, 极轴和斜向方向的移动距离分别为e和





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




2
2.2.基本模型描述
使用ACCO算法对疏散路径进行规划时, 采用六边形栅格将仿真环境划分为均匀的离散网格图, 然后计算出从起始节点到目的节点的可行网格链集合, 最后在集合中选择最优解[21].蚁群元胞优化算法可表示为:



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


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

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


2
3.3.参数优化
在ACCO算法中, 参数α, β, ρ对算法的收敛速度以及解空间的大小等性能影响显著: 参数α值越小, 算法搜索的随机性增强, 但算法的收敛速度变慢; 参数β值越小, 算法越易陷入局部最优解; 参数ρ直接影响模型的全局搜索能力和收敛速度. 因此, 为提升模型性能, 将利用粒子群优化算法对参数进行优化求解.粒子群优化算法是由Eberhart与Kennedy[22]在20世纪90年代提出的一种基于种群的全局随机优化算法. 该算法中的每个粒子根据自身及其他粒子的位置信息不断调整移动速度, 同时调整移动的方向和距离, 从而实现粒子在解空间内的全局寻优. 在算法求解的迭代过程中, 粒子通过个体极值和全局极值调整自身的速度与位置, 其公式如下:




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





2
3.4.路径规划流程
使用ACCO算法进行路径规划的流程如图2所示.
图 2 算法流程图Figure2. Simulation flow chart.
4.1.仿真环境设定
为验证所构建模型的性能, 以某大型邮轮的B甲板上的展厅为工程背景进行仿真, 模型的信息素浓度取14, 蚂蚁数量为30, 计算对比ACCO算法与传统算法的优劣, 邮轮B甲板构造详情如图3所示.
图 3 某邮轮B甲板构造图Figure3. B-deck structure diagram of a cruise ship.
甲板中间位置展厅面积为20 m × 20 m的封闭空间, 其构造详情见图4(a), 仿真环境为20 × 20的栅格地图, 如图4(b)所示.
图 4 展厅构造与仿真图 (a) 展厅构造图; (b) 仿真环境图Figure4. Exhibition hall construction and simulation: (a) Exhibition hall structure; (b) simulation environment diagram.
2
4.2.仿真结果分析
34.2.1.参数优化结果
根据专家经验法[23], 对PSO算法的其他参数值分别按照表1进行赋值.| 参数名称 | 参数取值 | 备注 |
| c1, c2 | 1.49445 | |
| Tmax | 50 | 最大迭代次数 |
| ω | $ 0.5 \times (T_{\max} - t)/ T_{\max} + 0.2 $ | t 为当前迭代次数 |
| λ1 | 0.7 | |
| λ2 | 0.1 | |
| λ3 | 0.1 | |
| λ4 | 0.1 |
表1PSO算法参数取值
Table1.The parameters of PSO algorithm.
根据仿真要求进行两组运算, 其求解结果如表2所列.
| 参数名称 | α | β | ρ |
| 参数组1 | 3.50 | 8.05 | 0.68 |
| 参数组2 | 1.35 | 8.50 | 0.36 |
表2 参数求解结果
Table2.Parameter solution results.
同时为观察适应度评价函数性能, 对比分析两组参数的适应度值曲线, 如图5所示.
图 5 粒子适应度值曲线 (a) 参数组1; (b) 参数组2Figure5. The fitness value curves: (a) Parameter group 1; (b) parameter group 2.
3
4.2.2.路径规划结果
根据上述模型构建描述及参数设定, 分别使用传统算法与ACCO算法进行仿真, 其最终路径效果如图6所示.
图 6 仿真效果图Figure6. Simulation effect chart.
图6中S表示起始节点, E表示目的节点. 从图6可知, 传统模型与ACCO算法均可进行有效路径规划.
3
4.2.3.路径长度及分析
当最大迭代次数一定时, 由于传统算法与ACCO算法在路径选择概率上的差异, 导致每次迭代所有蚂蚁搜寻的总路径长度和搜索速度也不同, 其结果如图7所示.
图 7 路径长度对比 (a) 传统算法路径统计; (b) 基于经验参数的ACCO算法路径统计; (c) 启发函数优化后的路径统计; (d) 信息素更新优化的路径统计; (e) 基于参数组1的路径统计; (f) 基于参数组2的路径统计Figure7. 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算法表现出更佳的性能.
3
4.2.4.迭代对比分析
由于ACCO算法对部分参数进行优化, 导致其与传统算法在搜索能力上存在差距, 因此当增加迭代次数时, 解空间也表现出差异, 如图8所示.
图 8 路径长度迭代对比 (a) 传统算法; (b) ACCO算法Figure8. Iteration comparison of path length: (a) Traditional algorithm; (b) ACCO algorithm.
分析图8可知, 当迭代进行到第70次时, 传统算法的搜索路径已基本停滞, 从而解空间已经固定, 陷入局部最优解的可能性增大; 而ACCO算法在迭代进行到近200次时, 搜索路径的元胞总数依旧在减小, 解空间在不断增加, 表明仍然在搜寻全局最优解. 因此传统算法相比ACCO算法而言, 更易陷入局部最优解.
3
4.2.5.其他性能对比分析
在对算法的搜索能力以及收敛性等性能进行了上述分析后, 为了进一步凸显本文所提算法的优势, 现对算法其他方面性能进行分析, 主要包括:运行时间是指在相同的运行环境中, 算法运行所消耗的平均时间;
可重复性是指对真实环境进行仿真时, 对于相同输入数据, 经过多次重复实验, 实验过程中出现完全相同的局部最优路径的概率;
收敛速率是指算法运行过程中, 相邻迭代过程中最优路径的元胞数之差的平均值; 最优性是指经过相同的迭代次数, 算法搜索到的最优路径的元胞数量, 以第100次迭代为例. 详见表3.
| 时间复杂度 | 运行时间/s | 收敛 速率 | 最优性/个 | 可重 复性 | |
| 传统 算法 | O(Nmaxn2m) | 94.157737 | –0.93 | 762 | 5% |
| 本文 算法 | O(Nmaxn2m) | 111.091862 | –1.22 | 571 | 30% |
表3算法性能对比表
Table3.Performances comparison of algorithms.
通过分析可知, ACCO算法与基本蚁群算法时间复杂度的区别主要在启发函数和信息素的更新方式上, 但是改进算法只增加了时间复杂度的常数项和低幂次项, 可以忽略, 因此时间复杂度并未改变, 但由于增加了邻域元胞的选择性从而导致运行时间有所加长. 同时改进算法在收敛速率、最优性和可重复性方面均展现出明显优势.
针对以上问题, 提出以六边形栅格替代传统四边形栅格作为背景地图栅格化方法, 从而解决四边形栅格地图的时间步长不统一的问题, 为对比算法性能奠定基础. 同时, 分别对启发函数以及信息素更新方式进行了优化设计. 最后将ACCO算法的参数作为PSO算法的位置信息进行迭代求解, 利用适应度函数值对求解性能做出评价, 从而得到ACCO的最优参数组合. 仿真实验结果表明, 提出的ACCO算法相比于传统算法, 在算法收敛速度、算法搜索速度、最优解的搜寻能力等各方面上均有明显优势, 因此可以为智能疏散系统的开发设计提供有益参考.
