基于自适应变异遗传算法的动态飞行路径规划方法

摘要

本发明公开了一种基于自适应变异遗传算法的动态飞行路径规划方法，随机生成初始种群并计算其适应度，统计种群中可行解E(t)并进行精英保留操作，对非可行解S(t)进行交叉、变异、插入、删除操作，计算操作过后的E(t)和S(t)组成的过渡种群的适应度；用E(t)单点随机变异得到的个体和随机生成的个体中的可行解，替换过渡种群的不可行解；判断是否进化到根据问题复杂程度选取的代数或者种群已收敛；若是，则种群中最优个体就是规划出来的飞行路径。本发明可以提高种群的多样性和收敛能力，可以为动态飞行路径规划这样的随时间变化的动态优化问题提供一种可行的解决途径。

说明书

技术领域

本发明涉动态优化技术领域，以及飞行器路径规划技术领域。

背景技术

动态飞行路径规划是指在环境中存在运动障碍，或者存在事先未知障碍情况下的实时飞行路径规划。由于外部环境随着时间在变化，因而动态飞行路径规划实际上是一个动态优化问题。用遗传算法解决动态优化问题是一项具有挑战性的工作。

现有基于遗传算法解决动态优化问题的方法中，很多都用到了随机变迁方法和精英变异方法。随机变迁方法是通过随机生成的个体，取代种群中原有的部分个体，以提高种群的多样性。精英变异方法是用上代种群中的精英个体通过变异取代种群中的最差个体的方法，这种变异的个体有更强的当前环境的适应性。

随机变迁方法和基本遗传算法初始种群的生成一样，由于个体也是随机产生的，虽然能在一定程度上增加种群的多样性，但不能利用现有种群的优良个体信息，会削弱算法的收敛能力，所以，基于随机变迁的遗传算法不适合于解决实时性要求强的动态飞行路径规划问题。

精英变异虽然可以提高个体对当前环境的适应性，但这种机制存在的问题一方面是可能降低种群多样性，使得种群有可能收敛于局部最优解，另一方面，对于有些优化问题，比如，动态飞行路径规划问题，可能在开始的几代种群中根本就不存在可行解，更不用说精英解了。所以，基于精英变异方法的遗传算法也不适合于解决动态飞行路径规划问题。

发明内容

为了克服现有技术不适合解决动态飞行路径规划问题的不足，本发明提供一种基于自适应变异遗传算法的动态飞行路径规划方法，可以根据当前种群中可行解的数量，自适应地把随机变迁和精英变异动态相结合，提高种群的多样性和收敛能力，为动态飞行路径规划这样的随时间变化的动态优化问题提供一种可行的解决方案。

本发明解决其技术问题所采用的技术方案包括以下步骤：

第一步：随机生成初始种群P(t)，t＝0；飞行路径的编码直接使用导航点编码方式，即一条染色体就对应于一条飞行路径，染色体基因位的取值就是空间一个点(x_k，y_k)。在每一代种群中，每一条染色体的长度可以是不同的，但它们的第一个基因位的取值都是飞行器初始位置(x_s，y_s)，最后一个基因位的取值都是目标点位置(x_g，y_g)。

第二步：计算初始种群适应度其中，g(x，y)表示约束条件，J(x，y)表示目标函数；在本发明中，把飞行路径与障碍物之间的碰撞代价看作是约束条件，把飞行路径长度当作目标函数。

因此，当g(x，y)＝0，即飞行路径与障碍物没有发生碰撞时，适应度函数的取值为飞行路径长度；对应的飞行路径称为可行路径，或称为动态优化问题的可行解；

当g(x，y)≠0，即飞行路径与障碍物发生碰撞时，适应度函数的取值为无穷大；对应的飞行路径称为不可行路径，或称为动态优化问题的不可行解。

对于动态飞行路径规划问题，需要求最小适应度对应的飞行路径(由第二步适应度函数定义可知，由于适应度为飞行路径长度，所以最小适应度就是最短飞行路径长度，对应的是路径长度最短的飞行路径。)。

第三步：统计种群P(t)中可行解的数量，记作n_feasible(t)；P(t)中的可行解集合记为E(t)，非可行解集合记为S(t)；计算r_ei(t)和r_ri(t)，分别表示第t代种群精英变异和随机变迁相对于种群规模的比率，取r_ei(0)＝0和r_ri(0)＝1。

$r_{\mathrm{ei}}\left(t\right)=\frac{n_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}$

$r_{\mathrm{ri}}\left(t\right)=\frac{{n-n}_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}$

r_ri(t)+r_ei(t)＝(n-n_feasible(t))/n

t-1代种群中的精英变异和随机变迁得到的个体总数为第t代种群中不可行解的数量，把这些个体和第t代种群中不可行解比较，保留适应度小的n-n_feasible(t)个个体到t+1代种群。其中，n_elitist(t)表示当代种群中有多少个可行解保留到下代种群。n表示种群规模。

第四步：对E(t)进行精英保留操作，精英保留算子

第五步：对S(t)进行交叉、变异、插入、删除操作；

所述的交叉采用单点交叉的方法，在种群中随机选择两个个体，并选择一个交叉点，交换两个个体在交叉点后面的部分基因位，得到两个新个体。

所述的变异采用单点随机变异，在种群中随机选择一个个体，并随机选择一个变异位，随机改变这个基因位的取值，得到一个新个体。

所述的插入采用随机插入算法，在种群中随机选择一个个体，并随机选择一个插入点，在这一点插入一个基因位，这个基因位随机取值，得到一个新个体。

所述的删除采用随机单基因位删除算子，在种群中随机选择一个个体，并随机选择一个基因位，删除这个基因位，得到一个新个体。

第六步：计算操作过后的E(t)和S(t)组成的过渡种群P′(t)的适应度；

第七步：通过E(t)单点随机变异得到r_ei(t)×n个个体，并计算它们的适应度；

第八步：随机生成r_ri(t)×n个个体，并计算它们的适应度；

第九步：用上述r_ei(t)×n加r_ri(t)×n个个体中的可行解，替换P′(t)中的不可行解；

第十步：令P(t+1)＝P′(t)，t＝t+1；

第十一步：判断是否进化到一定代数(代数根据问题复杂程度选取。)，即t＞n_g，或者种群已收敛；如果是，结束运行，这时候种群中最优个体就是规划出来的飞行路径；如果不是，转到第三步。

本发明的有益效果是：由于可以在上述第三步至第九步中根据当前种群中可行解的数量，自适应地把随机变迁和精英变异动态相结合，因此，本发明可以提高种群的多样性和收敛能力，可以为动态飞行路径规划这样的随时间变化的动态优化问题提供一种可行的解决途径。

下面结合附图和实施例对本发明进一步说明。

附图说明

图1是本发明的流程图；

图2是交叉算子示意图；

图3是变异算子示意图；

图4是插入算子示意图；

图5是是删除算子示意图；

图6是规划问题算例示意图；

图7是约束条件示意图；

图8是静态环境下的飞行路径规划结果；

图9是静态环境下基本遗传算法和自适应变异遗传算法收敛性比较；

图10是不同种群规模下基本遗传算法和自适应变异遗传算法对于静态飞行路径规划问题的收敛时间比较；

图11是迭代30步时的动态环境下基于自适应变异遗传算法的飞行路径规划结果；

图12是当满足终止条件时的动态环境下基于自适应变异遗传算法的飞行路径规划结果；

图13动态环境下基本遗传算法和自适应变异遗传算法收敛性比较。

具体实施方式

对于动态飞行路径规划这样的动态优化问题，由于用传统的基于随机变迁和精英变异的方法不能取得理想的效果；因此，我们提出基于自适应变异遗传算法的动态飞行路径规划方法。该方法主要由三部分组成，一是随机变迁，二是精英变异，三是自适应变异机制。方法的主要思想是采用自适应变异机制，也就是说，在精英变异和随机变迁间自适应，当前种群中可行解多时，精英变异占主导，可行解少的时候，随机变迁占主导；这样就可以做到，可行解较少的时候，本方法能够增加种群多样性；可行解较多时，本方法能够充分利用优良解信息快速收敛到最优解。该方法的流程如图1所示。

图中，n_feasible(t)、r_ei(t)和r_ri(t)表示第t代种群中的可行解数量、精英变异和随机变迁相对于种群规模的比率；

E(t)＝elitism(E(t)，r_ei(t))表示对种群E(t)进行精英保留操作，elitism(E(t)，r_ei(t))为精英保留操作算子；

S(t)＝crossover(S(t)，pc)表示对种群S(t)进行交叉操作，crossover(S(t)，pc)为交叉操作算子；

S(t)＝mutate(S(t)，pm)表示对种群S(t)进行变异操作，mutate(S(t)，pm)为变异操作算子；

S(t)＝insert(S(t)，pi)表示对种群S(t)进行插入操作，insert(S(t)，pi)为插入操作算子；

S(t)＝delete(S(t)，pd)表示对种群S(t)进行删除操作，delete(S(t)，pd)为删除操作算子；

pc、pm、pi、pd分别是交叉概率、变异概率、插入概率、以及删除概率，n为种群规模，n_g为事先设定的进化代数。

具体实施步骤：

第一步：随机生成初始种群P(t)，t＝0；

飞行路径的编码直接使用导航点编码方式，即一条染色体就对应于一条飞行路径，染色体基因位的取值就是空间一个点(x_k，y_k)。在每一代种群中，每一条染色体的长度可以是不同的，但它们的第一个基因位的取值都是飞行器初始位置(x_s，y_s)，最后一个基因位的取值都是目标点位置(x_g，y_g)。

第二步：计算初始种群适应度；

我们把适应度函数设计为如下形式：

$f(x,y)=\left(\begin{array}{cc}J(x,y),& g(x,y)=0\\ \infty ,& g(x,y)\ne 0\end{array}\right)---\left(1\right)$

其中，g(x，y)表示约束条件，J(x，y)表示目标函数。在本发明中，把飞行路径与障碍物之间的碰撞代价看作是约束条件，把飞行路径长度当作目标函数。

因此，当g(x，y)＝0，即飞行路径与障碍物没有发生碰撞时，适应度函数的取值为飞行路径长度；对应的飞行路径称为可行路径，或称为动态优化问题的可行解；

当g(x，y)≠0，即飞行路径与障碍物发生碰撞时，适应度函数的取值为无穷大；对应的飞行路径称为不可行路径，或称为动态优化问题的不可行解。

对于动态飞行路径规划问题，需要求最小适应度对应的飞行路径。

第三步：统计种群P(t)中可行解的数量，记作n_feasible(t)；P(t)中的可行解集合记为E(t)，非可行解集合记为S(t)；计算r_ei(t)和r_ri(t)，分别表示第t代种群精英变异和随机变迁相对于种群规模的比率，我们取r_ei(0)＝0和r_ri(0)＝1。

$r_{\mathrm{ei}}\left(t\right)=\frac{n_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}---\left(2\right)$

$r_{\mathrm{ri}}\left(t\right)=\frac{{n-n}_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}---\left(3\right)$

r_ri(t)+r_ei(t)＝(n-n_feasible(t))/n              (4)

由上面三个公式可以看出，当t-1代种群中的可行解越少时，根据其得到的精英变异个体越少，随机变迁得到的个体越多，精英变异和随机变迁得到的个体总数为第t代种群中不可行解的数量。把这些个体和第t代种群中不可行解比较，保留适应度高的个体到t+1代种群。

第四步：对E(t)进行精英保留操作，精英保留算子如下：

精英保留算子把当代种群中适应度高的个体保留到下一代种群，这样能够提高种群的平均质量。在本发明的算法中，我们根据当代种群中可行解的数量，来确定有多少个可行解保留到下一代，如下式所示：

$n_{\mathrm{elitist}}\left(t\right)=\left(\begin{array}{cc}{n}_{\mathrm{feasible}}\left(t\right),& n_{\mathrm{feasible}}\left(t\right)<n·r_{\mathrm{ei}}\left(t\right)\\ n·r_{\mathrm{ei}}\left(t\right),& n_{\mathrm{feasible}}\left(t\right)\ge n·r_{\mathrm{ei}}\left(t\right)\end{array}\right)---\left(5\right)$

其中，n_elitist(t)表示当代种群中有多少个可行解保留到下代种群。

第五步：对S(t)进行交叉、变异、插入、删除操作；

(1)交叉算子

我们采用单点交叉的方法，如图2所示。即，在种群中随机选择两个个体，并选择一个交叉点，交换两个个体在交叉点后面的部分基因位，得到两个新个体。

(2)变异算子

我们采用单点随机变异，如图3所示。即，在种群中随机选择一个个体，并随机选择一个变异位，随机改变这个基因位的取值，得到一个新个体。

(3)插入算子

我们采用随机插入算法，如图4所示。即，在种群中随机选择一个个体，并随机选择一个插入点，在这一点插入一个基因位，这个基因位随机取值，得到一个新个体。

(4)删除算子

我们采用随机单基因位删除算子，如图5所示。即，在种群中随机选择一个个体，并随机选择一个基因位，删除这个基因位，得到一个新个体。

第六步：计算操作过后的E(t)和S(t)组成的过渡种群P′(t)的适应度；

第七步：通过E(t)单点随机变异得到r_ei(t)×n个个体，并计算它们的适应度；

第八步：随机生成r_ri(t)×n个个体，并计算它们的适应度；

第九步：用上述r_ei(t)×n加r_ri(t)×n个个体中的可行解，替换P′(t)中的不可行解；

第十步：P(t+1)＝P′(t)，t＝t+1；

第十一步：判断是否进化到一定代数，即t＞n_g，或者种群已收敛；如果是，结束运行，这时候种群中最优个体就是规划出来的飞行路径；如果不是，转到第三步。

在这里，我们对基本遗传算法和本发明提出的自适应遗传算法应用在动态飞行路径规划问题的效果进行比较。

首先，对规划问题进行描述：

图6给出了待求解的规划问题的示意图。图中，飞行器为具有一定半径的圆，其半径为R_AV；飞行器的起点位于(x_s，y_s)，终点位于(x_g，y_g)。需要避开的障碍物的初始中心位置为i＝1，2，…，8，障碍物i的半径为现在，要为飞行器规划一条飞行路径(x，y)＝{x_k，y_k)}，k＝0，1，…，N，在满足约束g(x，y)的条件下，使得目标函数J(x，y)最小。

其中，(x₀，y₀)＝(x_s，y_s)，(x_N，y_N)＝(x_g，y_g)；约束条件g(x，y)和目标函数J(x，y)各是一个标量函数，在本发明中，我们把飞行路径与障碍物之间的碰撞代价看作是约束条件，因此，有约束条件g(x，y)的定义如下。

如图7所示，由导航点(x_k，y_k)和(x_k+1，y_k+1)组成航路段k，障碍物i在t时刻的中心位置为

设D_i，k为障碍物i的中心位置在t时刻到航路段k的距离，则有：

$D_{i,k}=\frac{A·x_{i,t}^o+B·y_{i,t}^o+C}{\sqrt{A^2+B^2}}---\left(6\right)$

其中：

A＝(y_k+1-y_k)

B＝(x_k-x_k+1)

C＝(x_k+1-x_k)y_k-x_k(y_k+1-y_k)

定义：

$g_{i,k}=\left(\begin{array}{cc}0,& D_{i,k}>R_{\mathrm{AV}}+R_i^o\\ 1,& D_{i,k}\le R_{\mathrm{AV}}+R_i^o\end{array}\right)---\left(7\right)$

$g(x,y)=\underset{k=0}{\overset{N-1}{\Sigma }}\underset{i=1}{\overset{N^o}{\Sigma }}{g}_{i,k}---\left(8\right)$

可以看出，随着时间的变化，发生改变，使得g(x，y)发生变化，因而，(x，y)＝{(x_k，y_k)}，k＝0，1，…，N，会发生变化。这是一个动态优化问题。

我们把目标函数处理为路径长度代价，因此，目标函数J(x，y)为：

$J(x,y)=\underset{k=0}{\overset{N-1}{\Sigma }}\sqrt{[{(x_{k+1}-x_k)}^2+{(y_{k+1}-y_k)}^2]}---\left(9\right)$

其中，(x_k+1，y_k+1)和(x_k，y_k)是规划出路径上的导航点。

本实施例包括以下具体实施步骤：

第一步：随机生成初始种群P(t)，t＝0，种群规模为n＝100，随机生成初始种群。

第二步：计算初始种群适应度；

适应度函数采用如下形式：

$f(x,y)=\left(\begin{array}{cc}J(x,y),& g(x,y)=0\\ \infty ,& g(x,y)\ne 0\end{array}\right)$

即，把可行路径的适应度取为路径长度，不可行路径的适应度惩罚为无穷大。对于动态飞行路径规划问题，需要求最小适应度对应的飞行路径。

第三步：统计种群P(t)中可行解的数量，记作n_feasible(t)；我们取r_ei(0)＝0和r_ri(0)＝1，计算第t代种群精英变异和随机变迁相对于种群规模的比率r_ei(t)和r_ri(t)：

$r_{\mathrm{ei}}\left(t\right)=\frac{n_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}$

$r_{\mathrm{ri}}\left(t\right)=\frac{{n-n}_{\mathrm{feasible}}(t-1)}{n}·\frac{n-n_{\mathrm{feasible}}\left(t\right)}{n}$

第四步：对P(t)中的可行解集合E(t)进行精英保留操作，由n_elitist(t)确定当代种群中有多少个可行解保留到下代种群：

$n_{\mathrm{elitist}}\left(t\right)=\left(\begin{array}{cc}{n}_{\mathrm{feasible}}\left(t\right),& n_{\mathrm{feasible}}\left(t\right)<n·r_{\mathrm{ei}}\left(t\right)\\ n·r_{\mathrm{ei}}\left(t\right),& n_{\mathrm{feasible}}\left(t\right)\ge n·r_{\mathrm{ei}}\left(t\right)\end{array}\right)$

第五步：对P(t)中的不可行解集合S(t)进行交叉、变异、插入、删除操作，其中pc＝25％，pm＝20％，pi＝10％，pd＝10％。

第六步：计算操作过后的E(t)和S(t)组成的过渡种群P′(t)的适应度；

第七步：通过E(t)单点随机变异得到r_ei(t)×n个个体，并计算它们的适应度；

第八步：随机生成r_ri(t)×n个个体，并计算它们的适应度；

第九步：用上述r_ei(t)×n加r_ri(t)×n个个体中的可行解，替换P′(t)中的不可行解；

第十步：P(t+1)＝P′(t)，t＝t+1；

第十一步：选取算法终止条件为种群收敛于最优解。判断是否满足终止条件；如果是，结束运行，这时候种群中最优个体就是规划出来的飞行路径；如果不是，转到第三步。

图8是当所有障碍都是静止的时候，规划出的从起点到终点的飞行器飞行路径。图9是在这种情况下，基本遗传算法和自适应变异遗传算法收敛性的比较，从图中可以看出，本发明提出的自适应变异遗传算法有更好的收敛性。图10是不同种群规模下基本遗传算法和自适应变异遗传算法对于静态飞行路径规划问题的适应度评估次数的比较，从图中可以看出，本发明提出的自适应变异遗传算法有更少的评估次数。因此，本发明提出的自适应变异遗传算法比基本遗传算法在解决静态环境下的路径规划问题时有更好的收敛效果。

接下来，我们比较本发明提出的自适应变异遗传和基本遗传算法对于动态飞行路径规划问题的效果。现在，我们假设障碍是一个运动障碍，它从其初始位置向着图中的右上角运动，运动速度设为每单位时间运动4个单位坐标。

图11和图12给出了在不同进化代数下的规划结果。图13给出了在此动态环境下基本遗传算法和自适应变异遗传算法收敛性的比较。从图中可以看出，本发明提出的自适应变异遗传算法有更好的收敛性。这是因为，当种群中可行解少时，自适应变异遗传算法可以利用更大的变异比率提高种群的多样性；而当种群中的可行解数量多的时候，自适应变异遗传算法可以利用这些可行解蕴含的信息，加快算法的收敛速度。因此，本发明提出的自适应变异遗传算法可以根据当前种群中可行解的数量，自适应地把随机变迁和精英变异动态相结合，提高种群的多样性和收敛能力。