《基于遗传算法的多无人机路径轨迹规划的算法实现及验证》13000字【论文】

第一章绪论1.1研究背景及意义近年来，科技与经济的不断发展，无人机在生活中起到越来越重要的作用，在多个领域都有广泛的应用。比如物流运输方面，配送需求飙升，人力物力成本飙升，服务场景复杂。无人机已经成为现代物流运送不能缺少的重要工具，帮助物流业实现大规模发展[1]。除此之外，在生物监测方面，无人机比人工勘测结果更加准确，可以在人类无法到达的区域进行监测。灾害管理上也可以利用无人机获取实时资讯。因此，无人机的相关研究具有极其重要的意义与价值。需要无人机根据一定的数学模型，找出从起始位置到目标位置的最优或次优路径。无人机路径规划是想要在未知或者已知障碍物和其他条件限制下，规划起点和终点之间的最优路线。对于一架无人机来说，它体积或者尺寸一般比较小，由于机身的尺寸限制，无人机的通信性能较差，因此单架无人机执行任务的容错率比较低。因此，实际执行任务中，多采用无人机组成的无人机群共同完成任务。无人机路径规划是整个无人机规划系统的核心，目前针对于无人机路径规划的研究方法很多，根据算法的不同发展阶段，分为两部分，一部分是以D*算法、人工势场法、A*算法为代表的传统算法，另一部分是以蚁群算法、粒子群算法、遗传算法等为代表的智能算法[2]。传统的路径规划算法复杂度较高，不适用于障碍物较多的地图，本文采用遗传算法，通过设定恰当的适应度函数，减少算法运行时间，优化路径规划效果。1.2无人机路径规划研究现状1.2.1无人机应用现状根据《2020年中国民用无人机行业分析报告-市场运营态势与发展前景研究》近年来，中国机器人(包括无人机)及相关服务的消费持续快速增长，预计到2022年将达到770亿美元，2018-2022年复合年增长率为26.3%。其中，中国是全球最大的机器人市场，预计到2022年将占全球总量的38%以上[3]。从2022年中国机器人(包括无人机)的市场分布来看，制造业预计占比最高，占53%；其次是资源行业，占11%；消费品行业排名第三，整体占比7%；医疗保健行业和零售业紧随其后，分别占6%和4%。随着5G、人工智能、物联网、云计算、大数据等新型智能化技术的不断迭代和发展，无人机技术将不断迎来新的创新与技术上的突破，各种性能将实现大幅度提升，与此同时，制造的成本、搭载设备的成本也将不断下降，无人机将变得更加智能化和人性化。5G和人工智能等新兴技术对民用无人机行业影响分析如表1.1所示。表1.1无人机行业影响分析技术名称技术现状影响分析5G和人工智能中国的5G建设正在加速，自2019年11月1日正式启动商用后，截至2019年底已经开通12.6万个5G基站，在52座城市实现5G商用。伴随5G商用正式落地，云计算、人工智能、大数据、物联网等新技术将与5G技术更加深度融合，推动产业实现质变跨越，催生融合互促的新生态。5G和人工智能技术将推动无人机进入更加智能化和小型化时代；1.5G的低延时特征可以更快地实现影像数据地传输，进一步扩大无人机的飞行距离和控制范围等，有利于无人机控制摆脱距离限制，使得无人机的大规模部署成为可能。2.5G技术的发展将大大改进无人机的连接速度，集无线通信、传感器集成和空间定位等功能于一体的高性能芯片。3.无人机可以和人工智能结合，预期体积将更小。它将催生更多的无人机(UAV)代替人工，群体作战代替个体作战。电网数字化目前国内电网企业在机巡图像电子稳像技术、自动跟踪技术、基于LIDAR/可见光点云的输电线路三维重建技术、基于多光谱的输电通道林木管理技术、基于可见光和红外的巡检图像智能识别技术等关键技术方面都有明显进步，有些技术已经成熟应用于电网的管理中。1.电网数字化的发展为无人机电力巡检的网络协同和数据智能提供了技术保障。2.全国投运电网历程稳步增长，国家将重点投入配网改造，这为无人机电网巡检由输网拓展至配网提供了重要的需求支撑。1.2.2路径规划算法发展由于应用场景不同，目前的路径规划有很多种，可以根据不同的场景划分不同的路径规划。根据移动目标的不同，可分为点对点路径规划和全覆盖路径规划。静态的路径规划的情况是有已知条件，也就是已知的环境下，通过模型找到一条从起始点到中止点的路径。规划的路径一旦出现未知障碍物，规划的路径就被放弃，从起点重新规划。动态规划是在未知环境中规划一条从起点到终点的路径。路径中出现未知障碍物，不需要从起点重新规划，而是在障碍物点重新规划，避开障碍物后返回原路径。动态路径规划一般是基于静态路径规划的局部路径规划[4]，即先锻炼静态路径，如果途中遇到障碍物，在障碍物两端重新进行规划，绕过障碍物返回原路径。虽然效率高于静态路径规划，但可能存在路径过长等问题[5]-[7]。路径规划算法发展与优缺点如表1.2所示。表1.2路径规划算法对比类别智能仿生算法优点缺点根据生物自然界启发蚁群算法容错率较高；预设初始条件下，更容易找到系统最优和次优解收敛的速度较慢；收敛精度低；易陷入局部最优粒子群算法早期向极限逼近速度快；设置参数较少；实现简单后期收敛速度慢；易陷入局部最优自然组织结构启发人工神经网络算法自适应能力强，当环境发生变化时能较快做出反应，改变对应的映射关系模型运算时间长；易陷入局部极小值；收敛速度慢人工免疫算法局部找到无限接近的最优解能力更强参数相比其他模型较多；模型运算成本比较高自然界进化论遗传算法拥有可以在全局范围内寻找最优解的特点；内在并行性收敛速度慢；易陷入局部最优入侵杂草算法易于理解；良好的自适应性；强鲁棒性易陷入局部最优；收敛精度低蚁群算法，是优化算法中的一种，解决组合优化问题效果较好，能够有效的解决著名的旅行商问题(TSP)，除此之外，在其他一些领域如工序排列问题，图着色问题，网络路由器问题等，都取得较好的效果[8]。蚁群算法，就是根据自然界中蚂蚁通过分泌信息素寻找食物而来的算法。蚁群在觅食时总能找到离食物最近的路线，当一些路径上经过蚂蚁的数量越多时，当某一条路径上遗留的信息素越多，其他蚂蚁在寻找食物中采用该路径的概率就会比较大，从而增加了这条路径上的信息素浓度。假设O点为一个蚁穴，有两只蚂蚁，蚂蚁A和蚂蚁B，Q点为食物所在位置，P点只是路径上一点，假设两只蚂蚁的移动速度相同。在t0时刻，两只蚂蚁可以随机选择OP或者OQ，假设蚂蚁A选择了路径OP，蚂蚁B选择了路径OQ。在t1时刻时候，蚂蚁A走到了P点，而蚂蚁B走到了Q点，也就是食物所在的位置。他们在其经过的路径上释放了信息素，在途中用线段表示[9]。之后蚂蚁B将食物搬运到蚁穴，也在沿途释放了信息素，蚂蚁A则从P点向Q点前进。t2时刻，蚂蚁B到达蚁巢O点，蚂蚁A到达食物位置，即Q点，此时蚂蚁B再次出发携带食物，发现OP路径上的信息素浓度高于OQ路径上的信息素浓度。在图中，线段的数量可以表示信息素的浓度。OQ路径上有两条线段，OP路径上只有一条线段。根据信息素浓度，蚂蚁B选择OQ路线携带食物，而蚂蚁A在Q点获取食物后返回巢穴，但它也有两种选择，一种是按原路线返回，另一种是按OQ路线返回。和前进时的判断方法一样，蚂蚁B发现OQ路径上的信息素浓度比OP路径上的高，所以会选择OQ返回巢穴[10]。按照上述情形，OP路径的信息素浓度会变得越来越低，OQ路径上的信息素浓度会变得越来越高，也就是随着时间的流逝，OP路径上将没有蚂蚁再次经过，两只蚂蚁都都会选择路径较短的OQ线路去运送食物。图1.3蚁群算法演示图粒子群优化算法是根据自然界中鸟群的捕食行为，设计相关算法和模型来模拟自然界中的这一行为。粒子只有两个属性:速度和位置，速度代表移动的速度，位置代表移动的方向。每个粒子在搜索空间中独立搜索最优解，并记录为当前个体极值，与整个粒子群中的其他粒子共享个体极值，找到最优个体极值作为整个粒子群的当前全局最优解[11]。粒子群中的所有粒子根据自身发现的当前个体极值和整个粒子群的当前全局最优解调整自身的速度或者位置。使用粒子群算法主要步骤为，随机初始化每个例子，评估每个例子并得到全局最优，如果不满足结束条件就更新每个粒子的速度和位置，评估每个粒子的函数适应值，更新每个粒子历史最优位置，更新群体全局最优位置，直到全局最优为止[12]。1.2.3算法相关应用路径规划的应用领域非常广泛，如：机器人机械臂的路径规划、飞行器航迹规划、巡航导弹路径规划、TSP问题、导航路径规划搜索、路由问题等。属于离散范围内最短路径规划问题主要要解决的是从复杂的数据信息中提取出所需要的信息，将起点和终点定位为网络中的两个节点，随后运用搜索算法进行最短路径寻优[13]。连续范围的路经规划又可以分为三大类：全局范围规划、局部范围规划和遍历式规划。(1)第一类：全局范围路径规划这类问题包含很多细分的场景，比如无人机组路径规划，无人机的巡航相关的规划等，他们的共同特点是环境相关信息是已知的，可能是已知建模的环境或者已知障碍的环境，在全局范围内寻找如何规避障碍物，找到到达终点的最优或最短路径。(2)第二类：局部范围的路径规划这一类问题相比上一种有显著的不同点，上一种路径规划是已知环境信息，这类问题的环境信息可能是动态变化的，也就是障碍物可能是临时添加的或者动态生成的，因此，解决此类问题的难度将更大，对算法的要求也或更高，对电脑的计算能力要求也更高，随着计算机算力的发展，有更多算法产生，如神经网络算法等。(3)第三类：遍历式路径规划这类问题实际应用中有各种场景，主要应用于各种机器人，如扫地机器人等，其特点是：扫地机器人需要尽可能短的路线，为了减少电量消耗等，并且应该最大概率覆盖房间的面积，为了避免无用功，应该尽量避免重复，因此，解决此类问题一般需要进行建模，常用的方法就是栅格法，此类问题的算法主要有遗传算法、蚁群算法、粒子群算法。1.3算法性能评价衡量指数传统遗传算法中，常用的衡量指标是进化代数、收敛时间和全局搜索能力来预估算法的性能[14]。但在实验中，很难保证三个指标同时实现最优，当种群规模增大时候，三个指标的变化方向是不同的甚至是相反的，在实际问题中，我们评价算法的好坏应该具有实际意义，对三方面评价指标应该赋予不同权重。比如有的问题具有时效性，对算法的收敛时间要求较高，在一些特殊场景中，需要对迭代次数进行限制，如果迭代次数超出了计算最大值，运算时间会变长，因此需要在有限的迭代过程中产生比较理想的结果。每一个结果都需要付出一定的代价，人力、物力、财力，为了降低成本，减少相关支出，需要限制进化代数，因此可以利用加权后的值作为评价指标。pma=p1∗T+p2p1,p2,p3表示权重，p1基于以上分析，本文提出了一种基于遗传算法的多无人机路径规划研究方法，本文有以下创新和贡献：(1)遗传算法实现多无人机路径规划。(2)设置参数对比实验，找出全局最优路径和及对应参数。遗传算法基础理论及实现2.1遗传算法原理概述1975年Holland教授基于生物进化规律即物竞天择、适者生存演变而来的一种优化算法，其中，种群是指有很多个个体组成的群体，个体(染色体)相当于待求解优化问题的一个解，基因是指每个解的组成分量。x=x1x2可以看成一个个体或者染色体，相当于待求问题的解。很多个染色体或者个体组成一个群体，也就是种群，本文采用遗传算法的思想完成无人机路径规划，理想状态下，只要路径不接触障碍物，无人机就可以安全抵达终点，路线与障碍物的坐标越接近，就越有可能发生碰撞，发生事故的可能性越大。采用栅格来进行环境建模和障碍物模拟，其中主要的难点就是保证规划好的路径为连续路径，同时尽量避免与障碍物坐标出现交叉。2.1.1遗传算子其中有几个算子或者操作步骤。选择：指的是从当前的种群中选择比较好的个体，使之有机会将其基因遗传到下一代，但是选择是随机性的，表现越好被选中的概率越大，表现不好的也有可能被选中。交叉：指的是从选择好的个体中两两配对并按某种方式互换基因以产生下一代。变异：指的是对发生交叉的个体以一定概率让其发生变异，但变异的概率通常比较小，变异之后会产生一个新的个体[15]。2.1.2编码编码就是将实际问题如一些优化类型问题转换为遗传算法需要的编码。其中，包括几种编码：二进制编码、实值编码、符号编码、置换编码、灰度编码等。用二进制编码时，编码长度根据自变量范围以及要求精度进行确定，L=log2b−aeps+1，其中，(a,b)2.1.3解码解码过程就是将二进制数据转换为十进制数据，x=a+(b−a)×X/(2L−1)2.1.4选择选择的方法有很多种，但一般比较常用的就是轮盘赌选择法。下图2.1为演示图。图2.1轮盘赌选择法轮盘赌选择法的步骤为，计算各个体适应度值fi，每个个体被选中的概率pi=fifi，以及累积概率Pi，随机产生01之间的一个随机数轮盘赌选择法的个体适应度值fi不能等于0或负值，但在实际问题中，个体适应度值f适应度函数的选择直接影响到遗传算法的收敛速度和能否找到最优解，因为遗传算法在进化搜索中基本不使用外部信息，只以适应度函数为基础，利用种群中每个个体的适应度进行搜索。优化问题可以分为两类，一类是求适应度函数的全局最大值，另一类是求适应度函数的全局最小值。对于两类优化问题，搜索空间中相应个体的目标函数值f(x)到适应度函数值F(x)的转换方法[16]求最大值问题，可以进行如下计算：FX=fX+Cminiff求最小值问题，可以进行如下计算：FX=Cmax−fXiff2.1.5交叉如果编码为二进制，交叉方式有单点交叉、两点交叉和多点交叉等等，其中，单点交叉的交叉点为1个，两点交叉的交叉数据量小于单点交叉。下面介绍适用于二进制或者浮点数的交叉方式：单点交叉：是指在个体编码串中只随机设置一个交叉点，然后两个配对个体的部分染色体在这一点上互相交换。两点交叉和多点交叉：(1)两点交叉[17]：在个体编码串中随机设置两个交叉点，然后交换一些基因。(2)多点交叉均匀交叉：也叫做一致交叉，两个个体的每一对基因序列上的基因都采用相同的交叉概率，从而形成两个全新个体。算术交叉：两个个体线性组合产生两个新的个体。该操作数通常是由浮点数组成的个体。2.1.6变异交叉之后产生新的子代，让其发生变异，规定变异概率为Pm。假设长度为10，产生一个[1，10]的随机整数，若r<Pm则发生0变为，1以下一系列二进制编码：101100101011001基因突变后，可能会变成以下新编码:0011001011001。该变异算子可以用于二进制编码的个体也可以用于浮点数编码的个体：(1)基本位变异：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。(2)均匀变异：这种变异特别适合于在算法的初始运行阶段，用一定范围内均匀分布的随机数替换个体编码串中每个基因位点的原始基因值。(3)边界变异：在基因座上随机取两个对应的边界基因值中的一个，替换原来的基因值。当最优解位于或接近可行解的边界时，它特别适用于一系列问题。(4)非均匀变异：对原始基因值进行随机扰动，扰动后的结果作为突变后的新基因值。每一个轨迹以相同的概率突变后，就相当于解空间中整个解向量的一个微小变化。(5)高斯近似变异：进行变异操作时用符号均值为Ｐ的平均值正态分布的一个随机数来替换原有的基因值。因此采用遗传算法整体的步骤为：图2.2遗传算法步骤一般来说，种群规模越大，越容易找到最优解，但是由于计算机运算能力有限，种群规模越大，计算所需要的时间也会相应增加[18]，下表列出生物遗传概念在遗传算法中的对应关系：表2.3遗传算法对应表生物遗传概念遗传算法中的作用适者生存算法停止，最优可行解最大性留下个体可行解染色体可行解的编码基因可行解中每一分量的特征适应性适应度函数种群根据适应度函数值选取的一组解交配通过交配原则产生一组新可行解变异编码的某一分量发生变化的过程2.2遗传算法实现2.2.1路径建模无人机进行路径规划之前应该先根据场景建立地图，本文采用栅格法建立无人机的空间模型，栅格粒度越小，空间建模中的各种环境信息就越精确，但是占用的电脑存储空间就会越大，算法所使用的搜索时间就会越长，如果栅格粒度太大，则空间中的各种信息不能准确表示出来，因此，在建立环境模型时候，可以做以下规定：(1)：不考虑障碍物体的高度问题，也就是无人机的飞行空间假设为二维平面空间；(2)：障碍物的坐标为已知信息，也就是障碍物的大小已知，不存在静态障碍物；(3)：由于无人机的体积相较于其他载人飞机较小，因此，在做整体路径规划的时候可以把无人机看作质点。对于每一架无人机，可行解或者可行路径可以看作是一条从起点到终点、由若干线段组成的折线，可以用这些折线的端点序列表示。由于可行路径是一系列路径的连接，需要进行过渡处理，防止无人机出现“急转弯”情况。在构建栅格地图的时候将地图左下角第一个点作为坐标原点建立直角坐标系，每一个栅格都可以用(x，y，z)的坐标形式表示，用坐标填充的方式，预设障碍物，从左下角坐标开始，按照逆时针的顺序用边界坐标表示障碍物，起点为图形的左下角坐标，终点也为图形左下角坐标，例如用(2,0)，(4,0)，(4,2)，(2,2)，(2,0)表示第一个障碍物。2.2.2初始化种群遗传算法的种群初始化是生成一定数量的个体，每个个体是一个可行解，对于多无人机路径规划来说，这里的可行解指的是可行路径，也就是从一个路径起点到路径终点的，且不经过障碍的路径，因此，初始化种群得到可行路径是遗传算法求栅格路径的难点[19]。初始化种群分为两个步骤，第一步是生成必经节点路径，为了计算方便，本篇选取25*25的栅格，从左下角编号到右上角编号的路径中必将经过第二行的一个点，第三行的一个点和第n行的一个点，因此，可以在第二行的栅格中随机取一个节点，第三行的栅格中随机取一个节点，以此类推，在第n行选取一个节点，因此就形成一个必经路径的间断节点集合。为了保证路径的不间断，需要连接这些间断节点。从第一个栅格开始判断相邻的两个栅格是否为连续栅格，栅格时候连续的判断方法为：L=max⁡{absxi+1−如果L=1，则说明两个相邻栅格连续，反之，则证明不连续。同时，在连接节点的过程中要避开设置的障碍物。因此，在连接节点的过程中采用中点连接法，中点栅格的坐标计算为：xmid=int(xi+1+ymid=int(yi+1可在中点处取2个栅格，然后在这些栅格中找到自由栅格，进行等概率选择，如果有最坏的情况，这些终点处的栅格全部判定为障碍，则在这些栅格中等概率选择一个作为路径一点，该方法保证了路径的连续性，但也有可能存在经过障碍的路径，而这种障碍的路径可以在适应度函数中进行修改。初始种群点的横轴坐标、纵轴坐标和竖轴坐标分开存放，分别放在矩阵中，除去起始点与终止点两点，其他点的横轴、纵轴、竖轴随机产生，并从大到小进行排列。2.2.3个体适应度函数种群适应度以种群路径的大小为主要参考标准，路径越短，适应度越大。取一个较大的数减去种群的路径长度作为适应度，对所有种群的相邻点进行测试，如果有交集，则将适应度设置为0。本文设置判断是否相交的函数，假设判断线段AB与CD是否相交，其中A（x1,y1）、B(x2,y2)、C(x3,y3)、D(x4,y4),通过返回值判断是否相交，如果返回值为0，则代表不相交，返回值为1代表相交。除此之外，还需要判断路径的距离和平滑的程度，关于路径的距离，采用距离公式进行判断：d总=i=1end−1(在实际场景中应该考虑无人机电量消耗等问题，因此规划的无人机路径应该尽可能短，选择方式按照一般情况选择，采用轮盘赌的方式：fita=1d总实际场景中，还应该考虑动力学和运动学的限制，避免无人机的拐角过大，并且拐角较小的路径更有利于飞行，可以采用相邻三点之间的距离作为判断条件：da=i=1end−2(连续三点的夹角分为钝角，直角，锐角，平角，其中平角也就是180度效果最好，钝角，直角次之，因此赋予不同的权重进行惩罚，锐角赋予∞的权重，最后综合考虑距离、平滑度设立适应度函数。2.2.3选择方法选择方法采用比较简单的基于概率的轮盘赌方法，首先计算出所有个体的适应度函数的和，在计算每一个个体所占的概率，计算公式如下：pi=fitii=1遗传算法的缺点是算法容易陷入局部最优解，根据每个个体的概率，以轮盘赌的方式选择出下一代个体，轮盘赌的方式保证了部分非最优的个体，避免了遗传算法的缺点。2.2.4交叉与变异首先确定交叉概率。本文设定的第一组参数为pc=0.7。某个种群是否杂交由随机数决定，随机生成一个基因数范围内的整数，作为杂交的起点，在单个点与下一个种群杂交。为了更好地筛选，交叉后的种群从大到小进行排序。变异：通过随机数的方式决定某一种群是否变异，随机产生一个在基因数量范围内的整数，作为变异点，随机产生一个新的点替换原来的点，变异完成之后的种群进行从大到小的排序。本文设置的第一组变异概率pm=0.004通过交叉与变异操作防止算法收缩在局部最优解中。2.2.5结果选择按照适应度大小进行选择最合适个体。通过设置判断条件，保证适应度为0的个体不被选中，适应度最大的个体会被选出，作为函数返回值返回。除了适应度满足之外，应控制UAV可飞轨迹[20]，在飞行过程中，两段路径之间的夹角过小，会使无人机在以最小转弯半径转弯的过程中无法实现对于断电目标进行访问，见图，故本文在对路径选择时限制两段路径的夹角，两段路径的夹角不得小于某一个给定值，该给定值由无人机最小转弯半径rmin和目标点作用半径Rl≥2arcsinrminRd+rmax实验结果及其分析3.1实验结果在确定航行的位置、保障航行不间断的情况下，设计航行的路线，为了建立完整的模型[21]，通常要求超过60%的航向重叠度，同时还要求30%的旁向重叠度，因为路径的弯曲会对一致性产生一定的影响，如果弯曲度较大，会在实际场景中产生负面影响。通过三维坐标x，y，z填充障碍物，本次实验采用平面填充进行模拟障碍物。下面是障碍物的位置坐标。表3.1障碍物表示(2,0)(4,0)(4,2)(2,2)(2,0)(0,6)(2,6)(2,4)(4,8)(0,6)(0,8)(2,12)(6,10)(2,14)(2,12)(0,16)(2,16)(2,20)(0,20)(0,18)(6,4)(10,4)(10,6)(6,6)(6,4)(8,16)(10,16)(10,18)(8,18)(8,16)(10,10)(12,10)(12,12)(10,12)(10,12)(12,6)(14,6)(14,8)(12,8)(12,6)(12,18)(14,18)(14,20)(12,20)(12,18)(14,12)(18,12)(18,14)(16,14)(16,16)(14,16)(14,12)(16,4)(20,4)(20,6)(16,6)(16,4)(18,6)(20,6)(20,10)(18,10)(18,8)因为目前没有实际的无人机航线地图，所以本文实验所用到的航线地图为25*25的坐标图，通过坐标点预设障碍物，起点为(0,0)的栅格,终点为(25,25)的栅格，为达到更好的训练结果，本文采用多种形状障碍物，包括矩形以及多边形等。先是一架无人机从起点到终点进行路径规划，然后增加无人机的数目，如两架、三架等。黄色正方形代表起点，绿色五角星代表终点。当父代基数较小，例如小于400的时候，会出现错误率较高，也就是会出现避障失败，如下图：图3.1故障图示在障碍物边缘会出现交叉或者锐角情况，当个体数量选择400以上，避障效果较好，但当个体超过4000，运算速度会大幅减慢，平均为20min一次迭代，因此本文设置的个体数目为2000，迭代次数为10次，在保证计算机运行速度同时，运算结果满足预期，根据实验参数调整，随机设置数据位置，任务完成度描述表如下。表3.2任务完成情况已知任务(父代基数大于2000，迭代次数为10)任务代号123456位置(2,18)(8,20)(9,18)(6,4)(10,14)(10,16)任务状态已完成已完成已完成已完成已完成已完成已知任务(父代基数小于500，迭代次数为10)任务代号123456位置(2,8)(6,12)(7,18)(20,16)(10,14)(6,16)任务状态已完成已完成已完成未完成已完成已完成3.2对比分析为实现无人机避开障碍物效果最优，本文设置对比实验，即通过交叉和变异的参数对比，得出最优模型。设置三组实验，在种群数量，迭代次数均保持一致的情况下，第一组采用低交叉率、高变异率，第二组采用高交叉率、低变异率，第三组采用低交叉率、低变异率。表3.3对比试验对比实验代号123交叉率变异率0.010.0040.001当pc=0.3,pm=0.01图3.2一架无人机路径图3.3两架架无人机路径图3.4三架架无人机路径当pc=0.7,pm=0.004时，图3.4一架无人机路径图3.5两架架无人机路径图3.6三架架无人机路径当pc=0.9,pm=0.001时，图3.7一架无人机路径图3.8两架架无人机路径图3.9三架架无人机路径如上述实验对比所知，当参数设置为低交叉率，低变异率，路径仿真结果给出的飞机路径较为平滑，效果比较理想，实际应用中，无人机的飞行转弯角度应该适当控制，如尽量避免直角，锐角，也就是较大度数的钝角和360度的平角最合适。在第二组和第三组实验中采用，高交叉率、低变异率，低交叉率、低变异率，仿真结果中出现较大幅度的转弯，在实际复杂的地势或者外部环境中发生事故的可能性较大。总结及展望4.1总结随者路径规划算法、机器人技术与飞行控制技术的发展和成熟，无人机在越来越多的场景下得到了广泛的应用，如军事领域和日常生活领域，路径规划是无人机飞行中的重要组成部分，本文采用遗传算法的方法，设置起点、终点、障碍物等通过规划使无人机安全到达目的地。本文在第一章介绍了当前无人机相关的发展情况，民用消费级包括个人航拍，影视航拍，遥控玩具，民用工业级包括巡查、监视、安防、体育赛事转播、演艺拍摄、电力巡检、资源勘探、城市规划、地图勘探、城市规划、地图测绘、水利监测、农药喷洒、森林灭火、辅助授粉、大气取样、人工降雨、物流配送、编队表演等。本文在第二章介绍了遗传算法的理论以及实现步骤，编码，初始化种群，评估种群中个体适应度，选择，交叉，变异，不断演化，得出最终最优结果。无人机路径规划算法中包含经典算法和智能反应算法，经典算法包括，A*算法，路线图算法(RA)，细胞分解法(CD)，人工势场法(ARF),智能反应算法包括遗传算法(GA)，粒子群算法(PSO)，蜂群算法(ABC)，布谷鸟算法(CS)。考虑到无人机路径规划中存在许多限制因素或优化指标，本文对这些指标进行归一化处理，并赋予不同的权重。无人机路径规划的研究其实是一个组合优化的问题，在优化理论中是一个NP难问题。由于这个问题的解的空间是不连续的，解的邻域表达式比较困难，用普通算法很难求解。作为现代优化算法之一，遗传算法的主要特点是能够跳出局部最优解，以概率1找到非线性极值问题的全局最优解。遗传算法是基于交叉和变异的算法。在传统算法的结构中，变异操作是在交叉操作的基础上进行的，交叉操作强调交叉动作，将变异视为生物背景机制。在具体的交叉操作中，本文采用单点交叉，在基因序列中随机选择一个断点，然后将断点右端的所有染色体交换到双亲上。在变异操作中，变异算子通常通过高斯分布的随机变异来实现。近年来，有人试图利用柯西分布的随机序列实现变异，希望通过柯西分布的宽翼特性实现更大范围的变异，从而找到全局最优解。基于上述特点，本文对基于求解路径规划的算法进行了优化和改进，使其与环境建模的结果更加一致。本文简单介绍了在环境建模时候的一些假设，比如采用静态障碍物，假设障碍物数量和位置均已知，介绍了路径规划中的主要衡量指标，针对两个主要因素（距离、平滑度）提出了归一化解决方案，通过多项式回归计算出权重系数将两个度量指标线性组合得到了一种新的无人机路径规划评价方法。在第三章的实验结果中可以看到不同种群数量和迭代次数对实验结果的影响。4.2展望无人机路径规划是一个比较困难但亟待解决的研究领域。随着智能经济的慢慢到来，其应用前景非常广阔。本文将从两点对无人机路径规划的未来工作进行展望：第一点是本文需要改进的地方。本文采用的是栅格法进行环境模拟，只能保证得出的结论适用于部分特征的场景，在实际生活中或者在绝大部分的应用场景下，需要考虑更多情况的避障问题，比如婚庆典礼上，用数百架无人机模拟婚纱，需要考虑无人机编队问题，不单单是一架，两架飞机，涉及更复杂的场景，出吃之外，在考虑三维环境的时候，仍需要考虑无人机控制以及传感器灵敏度问题等，特别是室内的环境下，对模型的要求将更高。本实验考虑到计算机运算水平，种群设置限制在2000，迭代次数限制为10次，但当计算机运算水平提高，可增大种群的数量和迭代次数，将会得到更完善的结果。当综合考虑环境因素也必然会大大增加研究难度。第二点是无人机路径规划算法领域的发展[22]，无人机路径规划通常需要同时优化多个指标，比如路径长度优化、障碍物优化等，多个指标通常很难全部满足，给整体的路径优化带来诸多挑战。本文采用的方法是对多个指标进行加权，赋予不同的权重也就是归一化，这种方法计算起来较简单，但对实际问题的解决可能存在偏差，未来可能出现更优化的算法，可以同时对动力学或者结构等多个目标函数进行优化，在不同的目标之间进行统一协调，既能将成本最小化，还可以实现覆盖全区域，水下图像质量评价领域的未来发展。除此之外，神经网络的发展，也将给无人机路径规划提出新的解决方案，在不确定信息条件下[23-25]，通过神经网络构建环境模型、无人机模型和评价指标，可以实现未知环境中规划有效的安全区域侦察任务。从应用角度来看，无人机领域如此广大，可以针对某个领域的特征，建立特殊的评价方法，真正做到理论与实际应用相结合。由于本文作者写作以及学术水平有限，文中存在不足之处在所难免。在此诚恳地希望各位老师和专家批评指正！参考文献[1]詹计雨,韩士杰,雷笑天,金楠森,张健.无人机避障设计与实现[J].电脑知识与技术,2018,14(31):98-100.[2]梁晓辉,慕永辉,吴北华,江宇.关于路径规划的相关算法综述[J].价值工程,2020,39(03):295-299.[3]武正伦.无人机航路规划的研究与实现[D].吉林大学,2019.[4]王嘉琦.基于改进RRT~*算法的无人机避障路径规划[D].南昌航空大学,2019.[5]吕倩,孙宪坤,熊玉洁.改进遗传算法的无人机路径规划[J].导航定位学报,2020,8(05):42-48.[6]徐剑,周德云,黄鹤.基于改进遗传算法的多无人机路径规划[J].航空计算技术,2009,39(04):43-46.[7]贾秋玲,李广文,闫建国.基于遗传算法的多无人机协同逆推式路径规划[J].西北工业大学学报,2007(04):590-594.[8]唐朝伟,李彦,段青言,杨险峰,胡佩,陈冠豪.自适应进化蝙蝠算法下的复杂网络社区发现[J].中南大学学报(自然科学版),2018,49(01):109-117.[9]凌富园,杜承烈,孙宝亮,顾青.基于不规则障碍物环境下无人机的改进几何路径规划算法[J].航空电子技术,2019,50(04):40-46.[10]王莉莉,周娟.不同威胁情况下无人机实时航路规划算法研究[J].科学技术与工程,2014,14(30):97-101.[11]田晓亮.无人机路径规划方法研究[D].西安电子科技大学,2014.[12]王祝,刘莉,温永禄,龙腾.基于凸优化的无人机三维避障轨迹规划[A].东北大学、IEEE新加坡工业电子分会.第28届中国控制与决策会议论文集（下）[C].东北大学、IEEE新加坡工业电子分会:《控制与决策》编辑部,2016:5.[13]徐钊,