【《基于改进蚁群算法的无人机通道路径规划案例分析》7600字】

第第页基于改进蚁群算法的无人机通道路径规划案例分析连接起点位置与终点位置的有序点或曲线称之为路径，构成路径的策略称之为路径规划。无人机路径规划算法，是建立无人机安全通道的关键技术之一。路径规划的方法有很多种，结合其自身的优缺点，适用的范围和领域也各不相同。根据对各领域和常用路径规划算法的研究，参照算法的时间发展历程和对应的基本原理，可将算法大致分为以下四类：传统算法、图形学算法、智能仿生学算法和其他算法。随着搜索空间复杂度和待解决问题维度的提升，一些传统算法在处理此类问题上的计算量也呈指数上升趋势，进而其中一些算法在当前应用场景下已无法体现出其优越的性能。取而代之的是一些传统算法的改进算法和仿生学算法。目前常用在全局路径规划的搜索算法主要有：A*算法、粒子群算法、人工势场法、遗传算法、Voronoi图法、最速下降法和蚁群算法等[40]。在这几类搜索算法中，特别是蚁群算法及其优化改进算法，近几年正逐步被应用到规划、商旅、调度等诸多行业领域中。本章通过对比传统蚁群算法和改进蚁群算法，对无人机飞行路径进行规划，并通过仿真软件加以实现和验证，为后续无人机航迹规划模型奠定算法基础。1.1路径规划算法评价1.1.1A*算法A*算法是一种经典的最优启发式搜索算法，一般应用于静态规划问题。和Dijkstra算法相似，在路径规划和图像搜索中有着极其宽泛的应用[41]。A*算法在平面路径规划图上有多个节点，每当节点向外扩展时，总是在所有扩展节点中，选择权值最小的节点作为下一步扩展起点，然后求解出此平面图上的一条最短路径。如果在高维度搜索空间中，需要扩展的节点过多，导致A*算法的运行需要大量计算时间，同时增加对内存的需求。因此在复杂环境下的搜索空间中，A*算法已不能满足当前需求。作为启发式搜索算法，目前的许多算法原理和思想都来源于A*算法。而稀疏A*算法（SAS）作为A*算法的改进算法之一，虽然舍弃了在路径空间搜索中的无用节点，缩短了搜索时间成本，但在面对三维全局规划空间时，其规划时间随着空间的增大而增大。所以，A*算法以及其改进算法并不满足本课题中路径规划算法的需求。1.1.2Voronoi图法Voronoi图是计算几何学中一种重要的几何结构，由两个或者多个多边形，将平面分割为几部分，每一个多边形均包含一个点。Voronoi图和Delaunay三角网原理相似，被应用于碰撞检测、聚类分析、航迹规划等领域。在航迹规划中，从目标起始点至终点的威胁回避路径可作为以威胁或者障碍为依据的Voronoi图，每一个多边形内均有一个威胁源，作为Voronoi图中的特征元素，然后给出这些边界的权值来搜索最优的航迹。依照此原理获得的路径很粗糙，而且所得的路径是分段的，需要对路径进行平滑处理。常用的Voronoi图构造法有：半平面交叉法、增量构造法和分治法。在高维度空间问题中，Voronoi图所需时间成本巨大，不适用于高位空间的路径规划问题。1.1.3遗传算法遗传算法（GA）由美国计算机专家JohnHolland教授依据达尔文的“适者生存、优胜劣汰” 的理论，于1975年提出的。遗传算法基于自然遗传学和自然选择机理，是一种随机搜索算法，可作为通用框架用于求解复杂优化问题，并且对求解问题的详细细节要求不高，对问题的种类具有很强的鲁棒性，且在适应性、全局优化性和隐含并行性上均有较好展现，体现了全面的全局搜索能力。与传统搜索算法不同的是，遗传算法的进化开始，需要设立一个初始种群，种群中的个体称作染色体，代表一种规划的可行解。染色体的进化通过一系列迭代产生，在每次迭代后，由对应的评价机制来决定染色体的存活概率，称为适应值。在染色体进化过程中，适应值高的染色体进行交叉和变异，形成新的种群，最终通过多次迭代，得到遗传算法收敛后的全局最优解或局部最优解[42]。选取遗传算法进行路径规划的主要步骤为：=1\*GB2⑴.对路径编码；=2\*GB2⑵.选取合理的路径评价函数；=3\*GB2⑶.选择适用于路径规划的特定遗传算子；=4\*GB2⑷.计算并微调算子或参数来获得最终解。遗传算法作为一种全局优化算法，通常可以快速收敛到最优解附近，但是在接近最优解后，算法的收敛速度可能会变得很慢，需要在收敛到近似优化解后，采取其他的搜索算法以得到最终优化路径的解。这些都暴露了遗传算法收敛速度慢、易陷入局部最优解的缺点。同时，遗传算法需要多个参数作为进化初始种群的信息元素，一旦参数设置不合理，便有可能导致无法获得最优解。例如在路径规划中，不仅要选取适当的函数，还要考虑无人机飞行的约束条件。因此，遗传算法不适合应用于本课题的算法研究中。1.1.4人工势场法人工势场法（APFM）是在不考虑其他约束条件的情况下，将目标点作为引力势场，任务中的威胁和障碍作为排斥场，从而避开排斥元素，抵达目标引力点。人工势场法的构建需要对约束信息和目标进行评估，虽然非常直观，但对一些参数条件不好处理，所以人工势场法一般用在路径规划的后期处理中。因此，人工势场法同样不适合作为核心算法应用在本章的路径规划中。1.1.5粒子群算法粒子群算法（PSO）由Kennedy和Eberhart在1995年提出，该算法启发来源于对鸟群觅食行为的观察和研究。粒子群算法以随机的方式产生初始种群，每个粒子元素都代表一个可行解，而且粒子不需要复制和突变，仅依据适应度函数值来调整粒子当前的状态，从而达到整体和局部的平衡关系。较于其他搜索算法，粒子群算法能够快速的得到路径规划的最优解。粒子群算法函数简洁，编程难度小，易实现，无需梯度信息，只通过利用目标信息的取值进行搜索，因此协同性和搜索能力较强。虽然标准的粒子群算法虽然搜索能力强于其他搜索算法，但是其搜索空间有限，易陷入局部最优解，这种缺陷在高维度空间搜索下更明显。所以，标准粒子群算法无法在无人机路径规划中加以应用。1.1.6路径规划算法对比综上所述，各类搜索算法均存在不同程度的性能缺点，受限于特定的路径规划场景使用范围。相反，蚁群算法依靠通用性强、认知性强、鲁棒性优越和全局搜索能力强等特点[43]，契合对无人机路径规划的研究需求。算法对比的维恩图如图1.1所示。图1.1搜索算法维恩图结合相关文献资料和海内外学者的研究现状，参照蚁群算法在多方面性能表现出的优越性，为此，本课题在无人机路径规划的算法上，拟采取蚁群算法作为核心搜索算法，并开展下一步的具体研究和相关讨论。1.2蚁群算法概述通过对自然界真实蚁群的行为活动观察，蚁群中单一的蚂蚁个体虽不能体现出较强的能力，但蚁群整体却可以通过相互之间的协同合作来实现觅食、筑巢、巡逻、清理蚁穴等复杂任务。尤其在觅食行为中，我们可以发现虽然食物源是不规则且随机分布在蚁穴周围，但是蚁群经过一段时间的群体觅食之后，大多数蚂蚁会以最短路线到达食物源所在的觅食区，若路线环境发生改变，蚁群仍能够寻找另一条最短路线以适应环境带来的改变。基于此特性，相关学者开展了对蚁群系统的深入研究，提出了蚁群算法理论[44-45]。1.2.1蚁群算法的原理蚁群系统(AntSystem或AntColonySystem)最早是由意大利学者Dorigo和Maniezzo等人在20世纪90年代所提出的[46]。1992年，MarcoDorigo在他的博士论文中正式提出了这种寻找优化路径的概率型算法——蚁群算法，随后吸引了一大批世界各地的学者竞相研究[47]。研究发现蚁群中单个蚂蚁的行为较为简单，但整个蚁群却可以体现一些智能化的行为方式。以蚁群觅食为例，这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。在后续研究中发现，蚂蚁会在其经过的路径上释放一种物质，称之为“信息素”。蚂蚁对“信息素”的感知能力极强，它们会沿着“信息素”浓度较高的路径行走，而每只经过的蚂蚁又会重新留下“信息素”以加深此路径上的信息浓度，因此形成了一种正反馈的机制。一段时间过后，整个觅食的蚁群就会沿着这条最短路径到达食物源所在的觅食区了[48]。Goss等学者在1989年为了对蚁群的觅食行为做更深层次的研究，进行了“非对称双桥实验”。如图1.2所示，觅食去和蚁穴之间由非对称双桥相连，蚁群需要经过非对称双桥抵达觅食区觅食。在觅食初期阶段，由于蚁群未在所有可行的行动路径上留下信息素，因此，蚁群可随机自由选择路径抵达觅食区，即通过左右两侧路径的概率相等。分别在实验开始的4分钟和8分钟做记录和比较，观察得较短路径上的蚂蚁个数逐渐增多，残留下的信息素也随之增多，越来越多的蚂蚁被此条最短路径所“吸引”。该实验表明，蚁群在觅食行为中，总能找到一条蚁穴至觅食区之间的最短路径，并且被绝大多数的蚂蚁共享，同时也印证了蚁群具有较强的适应能力，引申至蚁群算法中，表现为自适应性强。图1.2非对称双桥实验1.2.2蚁群算法的数学模型蚁群算法在推广之初，主要应用于解决组合优化中旅行商（TSP）的问题，旅行商需要按照一定的顺序访问城市，保证从出发城市开始至返回出发城市的过程中，每个城市只访问一次，且所选路径最短。以旅行商问题为例，参照表1.1，引入以下蚁群算法数学模型中的参数符号。表1.1蚁群算法数学模型参数符号参数含义蚁群算法中蚂蚁的总个数TSP问题中城市的数量（规模）信息启发式因子期望启发式因子信息素发挥系数，城市到城市之间的路径距离启发因子，从城市到城市的期望程度城市与城市之间的信息素浓度在时刻蚂蚁从城市到城市的概率，为当前所在城市禁忌表，记录蚂蚁已走过的城市注：通常表示为：蚁群算法数学模型的状态转移概率公式[49]可表示为：#其中，为蚂蚁还未曾到访的城市，；、均为常数。蚂蚁在每走完一步或经过每一个城市之后，都要对路径上的信息素进行更新替换，此举是为了防止在某条路径上的信息素残留过多，导致启发信息失去作用，为此，城市与城市之间的信息素规则更新如下：##其中，为信息素残留系数；表示在迭代过程中，第只蚂蚁在城市至城市之间的路径上所带来的信息素增量。依据信息素更新方式的不同，三种基本蚁群算法模型——蚁周（Ant-Cycle）、蚁量（Ant-Quantity）及蚁密（Ant-Density）模型的求解方法也不相同[49]。蚁周（Ant-Cycle）模型：#蚁量（Ant-Quantity）模型：#蚁密（Ant-Density）模型：#其中，为蚂蚁经过路径时所释放的信息素强度；为第只蚂蚁在现有迭代过程中所经过的路径总长。上述三种模型信息素的调整方式各不相同，在蚁量模型和蚁密模型中，蚂蚁每完成一步就要更新调整信息素，而非等到所有蚂蚁都走完所有城市之后再更新，由此可见，这两种模型的调整规则为局部信息素调整方式。在蚁周模型中，信息素的更新调整在全部蚂蚁走完所有城市之后进行，结合了蚂蚁的整体信息，适用于本课题中对无人机路径搜索的方式。因此，在本文接下来的研究中，将采用蚁周模型作为理论依据。1.2.3蚁群算法的算法描述在确定蚁群算法的数学模型之后，即可将算法应用于具体问题的解决方案中。蚁群算法的流程图如图1.3所示。图1.3蚁群算法流程图而蚁群算法的实现过程可概括为以下几步内容：Step1：参数初始化。令循环次数，设定最大循环次数，并初始化禁忌表；Step2：若，则开始循环；Step3：蚂蚁数目；Step4：每只蚂蚁依据公式（1.1）来选择下一个目的城市；Step5：修改禁忌表，将蚂蚁已经经过的城市加入到禁忌表中；Step6：若仍有蚂蚁未抵达过的城市，则跳转至Step3；否则继续执行Step7；Step7：依据公式（1.2）和（1.3）更新每条路经上的信息素；Step8：若，则继续执行Step9；否则执行，跳转至Step2；Step9：输出最优路径，结束流程。1.2.4蚁群算法的优缺点蚁群算法是通过观察真实蚁群的生活习性，研究蚂蚁在觅食中的现象而形成的算法，因此蚁群算法继承了真实蚁群系统的诸多特点[50]。现将蚁群算法的优缺点进行罗列比对，其具体优点归纳如下：=1\*GB2⑴自适应性强蚁群算法可以不借助外界因素的帮助而高效、有序地运行，具有较强的自适应性。蚁群特有的信息共享机制和搜索机制是蚁群自适应性的基本保障。基于此特性，蚁群在行为决策和系统调整时，也能保证蚁群整体架构继续可靠地运行。=2\*GB2⑵鲁棒性优越蚁群算法之所以广泛应用在各个领域中，关键因素就是其鲁棒性优越，在外界干扰下，也能保证固有的特性继续保持，体现为稳定鲁棒性和性能鲁棒性两点。蚁群算法通过调整概率转移模型来求解问题的最优解，而算法的收敛程度不受参数、概率模型的改变而改变。=3\*GB2⑶并行计算能力强并行计算是指能够同时使用多种运算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。蚁群算法能够独立有效地求解搜索空间中的最优解，使运算过程同步进行，在产生信息素的同时，协同合作，继续搜索，确保了搜索方向的可靠性。=4\*GB2⑷全局搜索能力强在面对复杂环境的搜索任务时，往往需要算法将所有可能的解呈现出来，因此，在某些特定应用场景下，需要体现出相应算法的全局搜索能力。而蚁群算法中的每个蚂蚁都作为一个信息素，对全局进行搜索并传递信息，所以蚁群算法具有极强的全局搜索能力。=5\*GB2⑸易结合，通用性好蚁群算法易于与其他算法相结合，通过在算法性能上的互补，来求解最优解以展现算法的高性能，此特点完善了混合智能算法的应用，使得蚁群算法在解决诸多问题上可以通用。蚁群算法的起源虽来源于真实蚁群，单在其诸多优点的背后，固然存在一定的缺点，现将蚁群算法的缺点归纳如下：=1\*GB2⑴搜索时间长蚁群算法在搜索过程中，每一个信息素，即每只蚂蚁都需要依据转移概率函数公式来进行下一步的搜索，使得算法的复杂度相对偏高，因此需要花费大量时间。而在搜索时长上的劣势，目前可通过高性能的硬件设备来弥补和完善。=2\*GB2⑵较难获得全局最优解蚁群算法通过信息元素的正反馈机制传导信息，而这一过程使得算法很容易陷入局部空间，而不能对问题中的搜索空间进行全局搜索。针对这一缺点，有学者提出一种加入混沌因子的蚁群算法，引导蚁群避开局部最优解，同时提升了搜索效率。在对蚁群算法的原理，数学模型、优缺点等进行分析后，更加确立了蚁群算法在本课题中求解无人机路径规划问题的核心地位，结合时下多位学者的研究现状和所提出的改进算法，继续对蚁群算法在无人机路径规划的问题上做研究。1.3基于蚁群算法的二维路径规划1.1.1栅格法划分二维空间栅格法是一种地图建模方法，通过将地图进行单元分割，用大小相同的方块表示，来直观地分析路径规划等问题。栅格地图的精度取决于栅格块的大小，栅格区域越小，地图信息就越清晰，反之亦然。将二维路径的规划空间进行栅格化划分，生成的路径由起始点与目标节点的栅格相连所构成。如图1.4所示，以当前节点i为中心所构建的九宫格栅格结构，节点周围共计8个相邻节点（7、8、9、12、13、16、17、18）。当最小栅格尺寸大于等于无人机最小步长时，所划分的路径空间才成立。本文将在后续章节的研究中，分析无人机最小步长等约束条件。图1.4二维空间栅格划分示意图1.1.2信息素矩阵设计起始点、目标点、威胁点坐标和栅格划分大小决定了规划空间，设二维规划空间的四个顶点坐标分别为：、、、；设栅格大小为，则栅格总行数为，总列数为，栅格节点总数为。1.1.3信息启发因子设计蚁群算法启发因子设计的优劣，决定了所增加的待选节点的可见度、算法的收敛速度和算法的可预见性，便于蚁群算法以最快速度获得最优路径。二维路径规划从起始点出发，在所规划的路径中，约束条件中的威胁代价占较大比重，因此，信息启发因子可设置为约束条件相关威胁代价参数的倒数。无人机真实场景下的飞行主要面对的威胁代价主要有雷达、导弹、高炮、地形、大气威胁。由于在二维空间规划下，地形威胁的高度威胁不存在，而本课题是对民用无人机进行研究，导弹威胁和高炮威胁也不存在，因此忽略上述三种威胁。设雷达威胁和大气威胁分别为和，第个威胁点坐标分别为、，则当前节点到威胁点的信息启发因子为：#其中，，。蚁群算法状态转移概率和信息素更新策略分别参考公式（1.1）和（1.2）、（1.3）。1.1.4验证与分析为验证蚁群算法在二维通道路径规划问题上的综合性能，本节将参照实例数据进行仿真验证，仿真软/硬件环境参照表1.2，在本章后续章节中，所采用的仿真软/硬件环境均与表1.2中参数相同，在本章后续小节不做过多赘述。表1.2仿真计算机软/硬件参数参数数值Matlab仿真软件操作系统CPUR2016bWindows7AMD四核A8-4500M（2.8GHz）内存显卡8GBAMDRadeonHD7640G+7670M双显卡（2GB专用显存）蚁群算法二维路径规划仿真实验中，起止点坐标参数见表1.3，规划空间为~的矩阵，雷达威胁、大气威胁和地形威胁等威胁约束条件在二维路径规划中以平面直角黑色区域展示，如图1.5所示。表1.3二维路径规划参数及数值参数坐标（x,y）起始点目标点（0,0）（20,20）图1.5二维规划空间示意图通过设置不同信息素强度Q，在相同迭代次数和蚂蚁数量的前提下，通过仿真获得规划路径长度。算法仿真的相关参数为：蚂蚁数量m=50；算法迭代次数k=100；信息素启发因子；期望启发因子；信息素挥发系数；Q为变量。仿真数据统计如表1.4所示。表1.4二维通道路径规划仿真数据统计信息素强度参数迭代次数蚂蚁数量运算时间（s）输出路径长度Q=11005042.67636.63Q=10Q=20100100505042.59240.95036.3831.8Q值的变化表明在其他条件相同的情况下，蚁群信息素强度越高，算法运行的时间越短（最终收敛于基本运行时间以上）。仿真所得三个不同Q值下，三条二维通道路径规划参考路径和收敛曲线变化趋势如图1.6所示。图1.6蚁群算法二维通道路径规划和不同Q值下的收敛曲线示意图由仿真结果可知，蚁群算法在二位路径规划中，可参照不同信息素强度参数的设定，获取当前条件下的最优解和次优解，但基础蚁群算法理论所得收敛曲线波动较大，且三个不同Q值下的规划路径输出长度最大偏差为15.19%，表明蚁群算法在路径规划上虽然可行，但所得最优解和收敛曲线并不能作为最终无人机安全通道路径规划的可靠参考。为此，本文加入改进蚁群算法用于求解规划空间的最优解，并在后续仿真实验中加以验证。1.4基于改进蚁群算法的二维路径规划在上一小节中，