基于遗传算法的无人机避障路径规划1基于遗传算法无人机避障模型设计随着无人机在诸多领域的广泛应用，与之配套的具有避障功能的路径规划算法成为了需要重点讨论的关键问题。

伴随着计算机技术的发展，基于智能算法的无人机避障路径规划研究也取得了长足的进展。

其中，遗传算法以其优越的计算性能与极强的问题普适性受到了最为广泛的关注。

在无人机避障路径规划问题上，遗传算法相较于其他类型算法有较为突出的优势。

首先，不同于各个类型的神经网络算法，遗传算法不要求适应度函数具有可导或连续的属性，仅要求适应度函数值为正即可。

另外，大多数其他类型的优化算法的本质为单点搜索算法，面对较大规模的搜索区域时极易陷入局部最优解，全局搜索性能较差，而遗传算法作为一种多点搜索算法在面对大规模复杂区域时可以表现出极强的搜索性能，更易于获得全局最优解。

基于这些优点，遗传算法近年来被大量的应用于路径规划问题的解决。

但针对于无人机避障问题而言，相关的研究仍然较为缺乏，为了确保无人机稳定运行以及工作任务的实现，本文提出了基于遗传算法的无人机避障路径规划模型来实现复杂环境下无人机避障问题的解决。

为了能够有效描述待规划区域地图，本文采用栅格法对路径规划场地进行划分。

假设路径规划场地为矩形，根据场地具体尺寸可以确定栅格边长，由此即可以将场地划分为多个小正方形栅格，得到一个m ×n 的栅格状地图。

为了便于对模型进行描述以及与实际场地结合，同时采用坐标法与序号法对栅格地图中的栅格进行编号，两种方法可以依据实际比例相互换算得到。

如图4.15所示为10×10规模的区域栅格模型，栅格旁的行列标号为栅格横纵坐标，栅格坐标可用于快速获得该栅格在地图中的位置。

栅格中间标号为栅格序号，栅格序号适用于栅格的访问和路径的记录。

本文中所说栅格N 即指栅格序号为N 的栅格，这个序号可以由栅格中心点对应的坐标值(x, y)计算得到，计算公式为：N =x -10y +99(4.34)同样的，当由遗传算法优化路径完成后，需要对路径进行解码方能画出最优路径，这一过程的变换公式为：()101010x N%y int N /=⎧⎨=-+⎩（4.35）y图4.15 避障区域10×10栅格模型关于遗传算法的基本理论已经在本文的4.2.2.1部分进行了介绍。

利用遗传具体的算法内容如下：（1）初始化种群。

无人机的运动路径表现为一系列的连续栅格序号，利用遗传算法进行最优路径搜索时，首先将种群S 初始化为包含有P 个染色体个体。

定义无人机运动起点为0号栅格，则这些个体当中必然会包含有栅格序号0，其余序号则随机生成。

（2）适应度函数。

个体适应度函数需要能够反应每个个体对问题给出解答的性能情况，针对无人机的避障问题，本文将规划后的路径长度作为种群中的路径优化标准。

针对某一路径能否有效避开障碍物这一问题，模型引入惩罚因子进行评估，当路径经过障碍物区域时，该个体将受到“严厉”的适应度惩罚，因此不再参与到下一代计算。

（3）遗传算法的计算算子。

遗传算法的算子包括选择、取代、交叉和变异等操作。

选择算子采用轮盘赌选择法，即依据个体适应度值的高低来决定其被遗传到子代种群中的概率。

取代算子采用进化策略和最优保存策略实现，即用新一代种群中适应度值优秀的个体替换掉当前代种群中适应度值最小的个体。

交叉算子是指交换两个父代个体间的位值，本文采用单点交叉且交叉位置可变。

变异算子则采用遗传算法中常规变异方法进行操作。

需要说明，每一代个体中适应度函数值最优的个体将不再参与交叉、变异等操作而直接进入下一代个体种群中，以保留当前代的最优解，增强算法的收敛性。

在利用遗传算法进行无人机避障路径规划时，遗传代数将成为模型中重要的参数。

其原因在于当遗传代数较低时，目标函数尚未达到最优，模型对应的全局最优解存在偏离，使得模型性能降低，进而导致无人机路径规划不佳。

当遗传代数过高时，模型计算过程过度冗余，浪费计算资源，同时使得规划过程耗时过长。

因此需要对遗传代数参数的选择问题进行研究。

以图为例，无人机以0号栅格为起点开始运动，目标位置为99号栅格。

显然在全局无障碍的情况下，路径一为最佳路径规划。

但当遗传代数不足时，模型会给出路径二、路径三作为最优解，这显然不能满足实际需要。

y在路径规划问题中通常将遗传代数G选择在200~1000的范围内。

以上述问题为例，在这一范围内对基于遗传算法的无人机避障模型性能进行研究与评估。

图4.18为模型的适应度函数值与进化代数的关系图像，可以看出，当进化代数达到500代之后模型达到稳定。

图4.18避障路径规划模型中世代数与适应度函数相关关系图4.19为在MATLAB环境下利用Tik-Tok计时器获取的不同代数对应的程序运行时间情况。

可以看出模型的计算时间随着遗传代数的增加而增加。

在200-700代范围内，计算时间与代数基本呈线性关系，当算法达到700代以上时，计算时间将显著增大。

综合考虑模型稳定性与时间性能两个方面的因素，模型选择遗传代数为600。

图4.19 避障路径规划模型中世代数与计算时间相关关系在传统的遗传算法中，交叉概率p c 与变异概率p m 均为常数，在模型计算时不会发生变化。

然而在解决路径规划问题时，固定不变的参数值往往会导致模型性能的降低。

当选择较大的交叉概率p c 时，在模型初始阶段可以较大程度的丰富个体类型，增加全局最优解的可靠性，但在模型运行的中后段，较大的交叉概率p c 则会增加优秀个体被破坏的概率，导致模型收敛性降低。

反之，如果选择较小的交叉概率p c 值，具有优秀性能的潜在个体将很难被开发出了，影响模型中种群的多样性，降低全局最优解寻找的可能性。

同样的，对于变异操作，当选择较大的变异概率时，每代种群中的优秀个体将难以保留，导致收敛性下降。

当变异参数较小时，则会拖延最优解的开发过程，影响模型效率。

针对这一问题，本文提出了改进的遗传算法避障路径规划模型。

改进后的模型中交叉概率p c 与变异概率p m 将随着模型中种群世代数与收敛情况作出自适应调整。

改进后的交叉概率p c 与变异概率p m 表达式为：()12max avg max avgc avg k f f f f f f p k f f '-⎧'>⎪-=⎨⎪'≤⎩(4.36)()34max avg max avgm avg k f f f f f f p k f f -⎧>⎪-=⎨⎪≤⎩(4.37)式中：f max 是种群中最优性能个体对应的适应度函数值；f avg 是某代种群中所有个体的适应度平均值；f’是进行交叉操作的两个个体中适应度较高的个体；f 是进行变异操作的个体适应度值。

且有0<k 1, k 2, k 3, k 4<1。

进一步考虑到模型计算过程中，不同世代数下的具体要求有所区别。

在模型计算初期，某代种群中的最优个体未必是全局最优解，而依据上式，模型未考虑算法初期对种群丰富度的要求，导致较优个体基本不发生变化，因而导致了模型收敛于局部最优解的可能。

针对这一缺陷，根据代数增加过程中个体适应度值的具体情况，对自适应算子计算公式进一步改进如下：102109avg max f avg avgf f f c avg k .f f p e .f f -'-⎧'-≥⎪⎪=⎨+⎪'<⎪⎩(4.38)25101avg max f avg avgf f f m avgk f f e p .f f --⎧≥⎪⎛⎫⎪ ⎪+=⎨ ⎪⎪⎝⎭⎪<⎩(4.39)依据上式计算得到的交叉概率p c 与变异概率p m 可以满足模型在不同阶段对于算子的区别要求，符合遗传算法中的计算规律。

当种群中的某一个体的适应度高于种群平均适应度之值时，取较低的交叉概率p c 与变异概率p m ，这时该优解将以较大概率直接进入下一代种群当中而避免遭到破坏。

改进后的遗传算法避障路径规划模型中的算子不仅可以随适应度变化而自主变化，而且可以避免模型“沉溺”与当前的优解中产生停滞，帮助算法能够跳出局部最优解，并能够以更高效率给出全局最优解。

2 无人机避障模型效果对比分析为了能够实现无人机避障线路规划的有效性，模型需要从两个方面保证所给出路径的性能：（1）路径不经过障碍区域；（2）所给出路径长度为最短。

按照本文4.3.1给出的基于遗传算法的避障路径规划模型，在MATLAB 环境下展开仿真试验。

如图所示，在待规划区域内布置20个障碍栅格。

无人机目标是由0号栅格移动到99号栅格。

为了验证基于改进后的自适应遗传算法的无人机避障路径规划模型的性能，利用基于传统遗传算法模型实现的避障模型作为对比。

为了增加对比性，对模型参数进行统一设置如表 4.3所示，其中自适应遗传算法中参数k 1=2，k 2=0.5。

表4.3 遗传算法模型中的参数设置参数名称 参数值 种群规模（G ） 30 最大进化次数（MAXGEN ）600 个体长度（L ）18选择概率（p r）0.95交叉概率（p c）0.7变异概率（p m）0.01图4.20为布置20个障碍区域时仿真得到的路径规划结果。

路径一是基于传统遗传算法计算得到的路线规划方案，对应适应度函数值为15。

路径二是基于改进后的自适应遗传算法模型获得的避障线路规划方案，对应适应度函数为14。

路径一对应的计算时间为2.7760s，而路径二的计算时间仅为0.9841s。

y图4.20改进前后的遗传算法路径规划比较事实上，两种避障路径规划算法模型均存在一定的随机性，每次规划得到的路线也会有所区别。

导致这一现象发生的原因有两个，一是算法自身限于局部最优解而无法求得全局最优解，其二在于问题本身具有多个相同适应度函数值相同的最优解。

为了能够更加全面的分析与评估改进前后的遗传算法避障路径规划模型的性能，本文通过在相同的障碍条件下，分别利用两个避障模型模型进行路径规划计算，以此来比较两个模型的具体效果。

具体操作在10×10规模的区域内分别设置了5组障碍物个数Obs为10~30的测试区域，利用两个模型在每组区域内分别计算30次。

图4.21为不同障碍布置下，两种模型在某次计算后给出不同路径规划结果的图像。

(a) Obs=10 y(b) Obs=15y(e) Obs=30图4.21改进前后的遗传算法在不同障碍物数量下的路径规划结果比较统计每组适应度函数与计算时间的平均值可以得到图4.22。

图中Model 1为基于传统遗传算法避障路径规划模型，Model 2为改进后自适应遗传算法避障路径规划模型。

可以看出随着障碍区域数量的增加，两个模型给出的最优避障路径的长度与计算时间均逐渐增加。

总体而言，改进后的自适应遗传算法模型的优化路径与计算时间均显著优于改进前的传统模型。