基于APF导向的蚁群航路规划算法参数优化研究

王　芳，李昆鹏

(1.西安航空学院 机械工程学院，陕西 西安 710077；2.长安大学 道路施工技术与装备教育部重点实验室，陕西 西安 710064)

基于APF导向的蚁群航路规划算法参数优化研究

王芳1，李昆鹏2

(1.西安航空学院 机械工程学院，陕西 西安 710077；2.长安大学 道路施工技术与装备教育部重点实验室，陕西 西安 710064)

摘要：针对基于APF导向的蚁群航路规划算法中的参数优化问题，提出了算法中的参数优化规则。分析了APFGA算法中参数m、α、β、γ、和ρ等的选取原则，通过合理选择参数，使蚁群的搜索有效地避免陷入局部最优，加快了算法的速度，提高了蚁群的搜索效率。实验结果给出了参数选择依据，通过合理设置算法参数可以有效地改善蚁群算法的性能，有利于APFGA算法在航路规划等方面的应用和推广。

关键词：航路规划；参数优化；搜索效率

0引言

航路规划作为无人机任务规划的重要组成部分之一，是在特定约束下寻找一条起点到目标点之间最优的可行航路。航路规划问题一直是关乎无人机性能以及智能性的重要体现，目前航路规划主要集中在环境模型构建、规划策略设计以及参数优化等方面[1-4]。文献[5]中提出了一种人工势场导向的蚁群航路规划算法，将人工势场的目标导向作用运用于蚁群优化算法中，改善了蚂蚁搜索的盲目性，提高了路径搜索效率。但是，在运用蚁群算法求解问题时，参数值的选择直接决定了算法的好坏，而算法中不仅参数的个体取值十分重要，并且参数之间的组合取值更是直接影响着整个算法的结果，如果参数取值不当，会导致算法陷入局部最优等问题。如何找到参数间的关系成为了算法优劣的关键。

本文重点研究基于APF导向的蚁群算法对于航路搜索效果与算法本身参数配置的关系，从而更好地发挥算法航路寻优的性能。针对基于APF导向的蚁群算法参数取值问题，分析算法参数设置，通过实验分析确定参数合理取值区间。

1基于APF导向的蚁群航路规划算法

蚁群算法是一种智能随机搜索算法，多用于解决离散问题。算法中蚂蚁是根据系统路径上信息素的强度完成状态转移的，但在搜索初期，路径上信息素较弱，难以实现信息素的导向作用，同时在搜索后期，会因为某条次优路径上信息素的短暂加强使得蚂蚁搜索难以跳出局部极小，而利用人工势场的导向作用可以将人工势场规划结果作为蚁群路径搜索的初始解，以及通过构建势场导向权，使势场法的引导作用于蚁群路径搜索的始终，可以改善蚂蚁路径搜索的盲目性，从而显著提高收敛速度。基于APF导向的蚁群算法基本模型如下[5]。

算法执行时，先计算机器人在虚拟势场中受到的引力、斥力，并计算势场导向权。设Fatt、Frep分别为人工势场的引力和斥力，则蚂蚁在人工势场中的避障角度为：

θ=∠(Fatt+∑Frep)

(1)

假设当前蚂蚁在某栅格中，其向邻域栅格转移的方向角为φ，则定义该栅格方向的人工势场导向权为：

q(t)=λ·exp(cos(θ-φ)

(2)

式中，λ为调整系数。由上式可以看出，蚂蚁邻域某栅格方向与势场法避障方向越接近，其导向权值越大。

利用人工势场修正蚂蚁状态转移概率pk(begin,end)，按概率随机得到蚂蚁下一步的移动位置，并更新禁忌表。

(3)

式中，τij(t)为t时刻节点i和j之间残留的信息素；α为信息素启发因子；ηij(t)为t时刻节点i和j之间的期望启发函数；β为期望启发因子；qij(t)为导向权；γ为导向权启发因子。ηij(t)为距离定义式。

蚂蚁走过的路径上会留下信息素，同时为了避免路径上因残留信息素过多而造成启发信息被淹没，信息素会随着时间的流逝而挥发，设ρ为信息素挥发系数且(0≤ρ<1)，t+Δt时刻节点i和j上的信息素更新规则为[6]：

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t)

(4)

(5)

(6)

式中，Q为信息素强度；Lk为蚂蚁k在本次循环中所走过路径的总长度。

2算法参数优化

基于势场导向权优化的蚁群算法由于融合了人工势场和蚁群算法的优势，因而其搜索性能得到很好提升。从上面的分析不难看出，在算法中蚂蚁数m，信息素启发因子α，期望启发因子β，导向权启发因子γ和清晰度衰减系数ρ等参数最为重要，但是，通过大量的数学计算和分析，参数选择尚无严格的理论依据，因此，先采用一些文献提出的参数[3-4,7]，通过逐步调整各个参数的取值，再进行一系列的仿真实验，找到蚁群算法中最佳的参数选择。针对文献[5]中给出的环境对基于导向权优化的蚁群算法参数进行了性能测试研究。

2.1蚂蚁数(m)

在蚁群路径规划算法中，增大蚂蚁数势必会提高算法的搜索能力，但是蚂蚁数越大，算法的计算量越大，运行效率越低；而蚂蚁数太小，也不利于体现算法的正反馈机制，使其快速收敛于最优解。因此，选择合适的蚂蚁数m对充分发挥算法性能具有重要意义。

(a)平均路径长度

(b)平均收敛代数

针对给出的两种环境，在保持其它参数不变的前提下，使m值在[1,80]范围内由小到大变化进行50次独立随机测试，考察蚂蚁平均路径长度和平均收敛代数的变化情况，如图1所示。由图可见，兼顾算法的计算精度和运行效率，m值选取15较为合适。

2.2信息素启发因子(α)

蚂蚁依靠信息素的强弱进行转移，完成路径搜索，因此，路径上信息素的强弱是蚂蚁进行状态转移的重要依据。在保持其它参数不变的前提下，使α值在[0,5]范围内由小到大变化进行50次独立随机测试，考察蚂蚁平均路径长度和平均收敛代数的变化情况，如图2所示。随着α值的增大，蚂蚁倾向于沿着先前蚂蚁走过的路径转移，从收敛代数也可见，随着α值的增大，算法很容易收敛到局部极小；而当α值过小时，蚂蚁搜索新路径的能力增强，但收敛速度变慢。参考测试结果，选取α值为1时能同时兼顾算法性能和搜索效率，较为合适。

(a)平均路径长度

(b)平均收敛代数

2.3期望启发因子(β)

期望启发因子β反映的是蚂蚁在运动过程中距离启发信息在蚂蚁选择路径中受重视程度。同样，在保持其它参数不变的前提下，使β值在[0,5]范围内由小到大变化进行50次独立随机测试，考察蚂蚁平均路径长度和平均收敛代数的变化情况，如图3所示。由图可见，增大β值，算法收敛速度加快，蚂蚁选择距离近的路径可能性加大，但是，β值过大，将淡化蚂蚁信息素的指导作用，使其容易陷入局部极小；而β值过小，算法搜索效率会大大降低。依据测试结果，为保证规划性能，β值选取2左右为宜。

(a)平均路径长度

(b)平均收敛代数

2.4导向权启发因子(γ)

导向权启发因子γ是势场法优化规划算法的重要体现，反映的是势场法在蚂蚁状态转移过程中指导作用的重要程度。同样，在保持其它参数不变的前提下，使γ值在[0,5]范围内由小到大变化进行50次独立随机测试，考察蚂蚁平均路径长度和平均收敛代数的变化情况，如图4所示。由结果可见，减小γ值，相当于削弱势场法的导向作用，算法趋向于单一的蚁群搜索，其收敛代数增大，搜索性能会变差；而增大γ值，算法的性能则主要由势场法来体现，其全局搜索能力下降，容易陷入局部极小。因此，为兼顾两种算法的优势，依据测试结果，选取γ值为2左右较为理想。

(a)平均路径长度

(b)平均收敛代数

2.5清晰度衰减系数(ρ)

清晰度衰减系数ρ表示的是路径上蚂蚁信息素随时间推移挥发后的残余量。同样，在保持其它参数不变的前提下，使ρ值在[0,1]范围内由小到大变化进行50次独立随机测试，考察蚂蚁平均路径长度和平均收敛代数的变化情况，如图5所示。由结果可见，ρ值越大，算法收敛性能加快，但是，算法很容易陷入局部极小，其全局搜索性能变差；而减小ρ值，蚂蚁信息素启发作用变弱，算法趋向于随机搜索，影响其规划性能。权衡算法收敛性及全局搜索性能，选取ρ值为0.2左右为宜。

(a)平均路径长度

(b)平均收敛代数

3结语

本文在研究基于APF导向的蚁群算法模型的基础上，通过一系列仿真数值实验，利用大量的数据分析了算法中m、α、β、γ、和ρ等参数的不同取值对算法性能的影响。通过仿真实验验证，提出了最优参数组合方法，对于大多数蚁群优化问题而言，本文提出的参数优化方法都能使算法快速、有效地找到全局最优解，提高了算法的效率，对基于APF导向的蚁群算法在航路搜索应用中有一定的参考价值。

参考文献

[1] 董文洪,易波,栗飞.无人机航路规划环境模型研究[J].计算机工程与应用,2012,48(15):236-239.

[2] 林娜,张亚伦.自适应RRT无人机航路规划算法研究与仿真[J].计算机仿真,2015,32(1):73-77.

[3] 魏星,李燕.蚁群算法中参数优化及其仿真研究[J].制造业自动化,2015,37(5)：33-35.

[4] 梁亚澜,聂长海.覆盖表生成的遗传算法配置参数优化[J].计算机学报,2012,35(7):1522-1538.

[5] 王芳,李昆鹏,袁明新.一种人工势场导向的蚁群路径规划算法[J].计算机科学，2014，41(11A)：47-50.

[6] 袁明新,王孙安,李昆鹏,等.基于势场法优化的蚁群免疫网络路径规划研究[J].系统仿真学报,2009,21(15):4686-4690.

[7] 赵英淳,何雅玲,席奂,等.采用蚁群算法的中温余热有机朗肯循环性能参数优化[J].西安交通大学学报,2013,47(11):29-34.

[责任编辑、校对：周千]

Study on Parameter Optimization of Path Planning Based on APF-Guided Ant Colony Algorithm

WANGFang1,LIKun-peng2

(1.College of Mechanical Engineering,Xi′an Aeronautical University,Xi′an 710077,China;2.Key Laboratory of Road Construction Technology and Equipment of MOE,Chang′an University,Xi′an 710064,China)

Abstract：Parameter optimization rules are proposed for APF-guided ant colony algorithm,which is used for path planning.The paper analyzes the principles for selecting parameters such as m,α,β,γ,and ρ in APFGA algorithm.The reasonable selection of these parameters effectively prevents ant colony search from falling into local optimization,accelerates the speed of the algorithm,and enhances the efficiency of ant colony search.Experiment results offer the basis of parameter selection.The performance of the ant colony algorithm can be effectively improved through reasonably setting parameters,which is favorable for the application and promotion of APFGA algorithm in path planning.

Key words：path planning;parameter optimization;search efficiency

收稿日期：2016-04-17

基金项目：中央高校基本科研业务费专项资金资助项目(0009-2014G1251028);西安航空学院校级科研项目(12XP818)

作者简介：王芳(1987-)，女，山西长治人，讲师，主要从事优化设计及智能优化算法研究。

中图分类号：V279;TP301.6

文献标识码：A

文章编号：1008-9233(2016)03-0046-05