300字范文 > 【三维路径规划】基于matlab自适应遗传算法求解单无人机三维路径规划问题【含Matlab源

【三维路径规划】基于matlab自适应遗传算法求解单无人机三维路径规划问题【含Matlab源

时间：2019-06-24 07:17:00

一、无人机简介

1 遗传算法

遗传算法由约翰·霍兰德在20世纪60年代提出，并于1975年首次出版，是一种基于达尔文的生物进化论和孟德尔的遗传学的随机搜索与优化算法[9]。具有适用性广，鲁棒性强的全局优化能力[10]。文献[11]证明了遗传算法在采用精英保留策略时具有全局收敛性。一般采用遗传算法处理飞行航迹规划需要确定以下问题：（1）个体表示方法，即基因编码；（2）评价方法；（3）选择方法；（4）基因操作；（5）确定控制参数，如种群大小等。

1.1 基因编码

基因编码的方式决定了规划问题的具体表达方式，也决定了遗传操作的形式。本文采用的编码方法如下：首先，将规划空间表示为m×n×l的栅格地图，并对每个栅格进行编号，使每个栅格具有一个且只有一个标识号N。以10×10×10栅格地图为例，如果空间坐标系中某点的坐标为(x1,y1,z1)，则基因与坐标的映射关系为

其中mod表示取剩余部分，floor表示四舍五入。一定数量的航迹节点形成一条轨迹，相应地，一定数量的基因按一定顺序形成染色体。

1.2 航迹评价函数和选择方法

使用第1节给出的代价函数计算每条航迹的代价值。个体的价值越小，环境的适应度越高，更满足的理想航迹要求。

选择方法决定了哪些个体将被保留，同时将其特征传递给后代，对于每一代种群，健康状况较差的个体，即代价值较高的个体被淘汰。本文采用的选择方法是将精英保留策略和轮盘赌法结合，即根据个体在种群中的适应度决定个体被选择的概率。这相当于将完整的轮盘分为多个扇区，每个扇形的中心角越大，扇形的面积越大，被选中的概率越大，同时保留每一代最优航迹。

1.3 基因操作

基因操作也被称为进化算子，包括交叉算子和变异算子，变异算子包括扰动算子、插入算子和删除算子。具体含义如下：1.交叉算子：将两条航迹的染色体从某一位置切割，然后将切割的染色体重新组合，形成两条新的航迹。2.扰动算子：随机改变航迹的某个航迹节点。3.插入算子：在航迹中的随机位置（起点和目标点除外）随机插入一个新的航迹节点。4.删除算子：随机从航迹中删除除起点和目标点外的航迹节点。

1.4 遗传算法流程

遗传算法具体过程如下：

1.确定种群大小Q、每一代淘汰个体数量E和各种基因操作的作用概率，并确定终止条件（最大进化次数）。设置与航迹相关的参数，如每个航迹节点的最大数目和最小数目。初始化规划空间，设置起点和目标点，加载禁飞区，地形以及威胁。

2.生成初始群体，每个航迹的起始点和目标点都是固定的，中间节点在规划空间中随机生成。

3.评估和选择航迹，保留数量为(Q−E)的航迹，如果满足终止条件，转到第5步，否则转到第4步。

4.在保留的航迹上进行基因操作产生新的个体，并向原来的种群添加新生成的航迹，从而将种群规模恢复到Q，转到第3步。

5.从航迹中选择代价值最低的个体作为规划出的航迹，进化过程结束。

2 自适应遗传算法

基因操作可以产生新的个体，推动进化进程，传统遗传算法先进行交叉操作，再进行变异操作。交叉操作的概率可以影响种群的丰富程度，概率值越大，种群的丰富程度越大，但同时，种群中的优良个体被破坏的可能也越大。变异操作的概率影响遗传算法的全局寻优能力，概率值越大，越不容易陷入极值陷阱，但同时，算法的随机性增强，收敛概率减小。进化到后期，种群的适应度越来越集中，种群差异度较小，种群的多样性不足，进行交叉操作，产生新个体的适应度改变不大，之后再进行变异操作，容易破坏优良个体，减缓了收敛的速度。因此，自适应遗传算法[9]被提出，其思想是当群体适应度比较集中时，同时增加交叉概率和变异概率；当群体适应度比较分散时，同时减少交叉概率和变异概率。交叉概率和变异概率按式(19)和(20)进行自适应调整。

其中，Pc是交叉概率，Pm是变异概率，fmax是种群的最大适应度；fave是种群的适应度平均值；f′是两个交叉个体适应度较大者的适应度；f是变异个体的适应度；k1>0,k2,k3,k4≤1为常数。

从公式可以看出，当个体的适应度高于或等于种群平均适应度的时候自适应的调整交叉和变异概率，当个体适应度低于种群平均适应度的时候交叉概率和变异概率被赋予一个较大的固定常数值，这种方法可以在一定程度上减少较差的个体，但是同时也会损失较差个体中的优良基因，破坏种群的丰富程度。