基于无人机航路规划问题的蚁群算法综述

2018-01-25柳丹郭忠张树丽

汽车实用技术 2018年1期

柳丹，郭忠，张树丽

（烟台大学机电汽车工程学院，山东烟台 264000）

引言

航路规划是指在起始点与终点之间，为低空飞行器寻找出满足某种性能指标和约束的路径。在无人机飞行之前，首先要根据环境、自身约束条件来进行合理的航路规划，在保证安全的情况下，以最短的路径从起始点到达终点。本文首先介绍了基本蚁群算法，然后在基本蚁群算法的基础上综述了近几年来改进的蚁群算法。

1 蚁群算法的概叙

1.1 蚁群算法的简介

蚁群算法(ant colony algorithm, ACA)是由意大利学者M.Dorigo[1]等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。生物学家研究发现，自然界中的蚂蚁觅食是一种群体性行为，并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物源时，会在其经过的路上释放一种信息素，并能够感知其他蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该路径上的信息素浓度，路径上的信息素浓度会随着时间的推进而逐渐衰减，这样形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即最短距离。

1.2 基本蚁群算法求解航路规划问题

每只蚂蚁按照状态转移规则从起点选择下一个航路点，直到到达终点，在基本蚁群算法中，在t时刻第k只蚂蚁在路径点i转移到路径点j的状态转移规则如式(1)所示。

式(1)中：τij(t) 表示蚂蚁 k(k=1,2,…)从节点 i到节点 j的信息素值；ηij(t)为启发函数，表示在t时刻蚂蚁k从节点i到节点j的期望值，一般与两点距离dij成反比，即：

当所有蚂蚁完成一次航路点的选取后，各个航路点上的信息素根据公式（2）进行更新：

其中，ρ是信息素挥发系数，n是蚁群中蚂蚁的数量，Q是一个常熟，Lk是蚂蚁k走过航路点的总长度。

2 蚁群算法在无人机航路规划的发展

2.1 信息素问题

2.1.1 信息素初值问题

信息素初值的定义直接影响后面的状态转移规则，因此，信息素初始值的定义非常重要。张庆捷、徐华等[2]对蚁群算法的初始信息素强度进行了改进，定义轨迹的初始强度与距离成反比，最终可以得到最优的初始航路。

2.1.2 信息素更新问题

当所有蚂蚁完成一次航路点的选取后，各个航路点上的信息素将进行一次更新。焦振江、王正平等[3]提出了自适应信息素更新规则有效的提高了算法算收敛速度和解的性能；蒋定定、李万泉等[4]改进信息素更新规则，对信息素的挥发因子做了调整，从而克服了基本蚁群算法的收敛速度慢、易于过早陷入局部最优的缺点；唐增明、蒋泰等[5]提出一种新的动态自适应调整信息素的策略，对最大—最小蚂蚁系统的改进；邱小湖，邱永成等[6]前期采用了保留最优解和自适应航路点选择策略对路径进行优化，使之适应大规模问题求解;后期改进了基本蚁群算法中信息素、挥发因子的更新规则,通过改进使得每轮搜索后信息素的增量能更好地反映求解的质量，有效地避免陷入局部最优，加快了收敛，提高了搜索效率；房建卿、王和平等[7]提出的改进型蚁群算法，通过云模型来控制信息素强度 Q 和挥发系数 ρ 的大小，从而得到更好的收敛性与避免陷入局部最优解；尚梦雨等[8]采用信息素全局及局部信息素衰减法，改进了蚁群算法具有高效的迭代能力和快速的计算速度。

2.2 状态转移规则问题

航路点的选取即每只蚂蚁按照状态转移规则从起点选择下一个航路点，直到到达终点。最初的蚁群算法有收敛速度慢、计算时间长、易于陷入局部最优等缺。针对这些缺点，增强整体搜索能力，加快收敛速度，焦振江、王正平等[3]提出了保留最优解、自适应状态转换规则，有效的提高了算法算收敛速度和解的性能；陈谋、肖健等[9]将最短路径的信息反馈到系统中作为搜索的指导信号,并改进了节点选择方法,加快了搜索的效率，也容易找到最优解；李增、顾文灿等[10]提出了具有多种群的蚁群算法，并将导引因子引入到状态转移策略中，减少蚂蚁局部搜索的盲目性，确保蚂蚁最终完成航路搜索；蒋定定、李万泉等[4]改进了蚂蚁状态转移规则，从而克服了基本蚁群算法的收敛速度慢、易于过早陷入局部最优的缺点。

2.3 与其它算法结合问题

蚁群算法具有很强的鲁棒性和较好的搜索能力，很容易与多种启发式算法结合，以改善算法性能。李猛，王道波等[11]提出了结合蚁群算法与人工势场的航迹规划方法，该方法有效地提高了航迹规划的收敛精度，同时具有良好的动态收敛过程和更短的规划时间；王芳，李昆鹏等[12]提出一种势场法优化的蚁群航路规划算法，该方法改善蚁群初始路径搜索过程中的盲目性，将人工势场法的规划结果作为先验知识，对蚁群初始到达的栅格进行邻域信息素的初始化，进而运用改进的蚁群算法完成航路搜索任务；姚永杰，席庆彪，刘慧霞等[13]提出了一种改进的遗传蚁群算法，遗传算法阶段给出了一种小变异和引入新种群算子，维持了较优种群的多样性，蚁群算法阶段设计了一种基于航路代价的初始信息素获取规则，保证蚁群具有较好的初始信息素分布，在求解时能够避免陷入局部最优；田伟，张安等[14]基于两种改进蚁群算法，分别将遗传算法的交叉操作和 Dijkstra算法结合到蚁群系统的无人作战飞机航路寻优过程中，使无人作战飞机以最小的发现概率与可接受的航程到达目标点，并提高了无人作战飞机的航路寻优能力。