0 引言

无人机(Unmanned Aerial Vehicle, UAV)为了完成侦查任务或者对目标进行打击，首先必须对执行任务的区域进行分析，预先规划出一条能够完成任务的航路。目前航路规划的方法有很多：文献[1]采用A^*算法进行了无人机航路规划，A^*算法易于实现，但是算法是采用节点扩展的方式进行搜索^[2]，因此节点扩展方式不同，得到的航路也不同，所以可能会找不到最优路径；文献[3]利用遗传算法进行航路规划，算法从全局最优的角度进行计算，但是遗传算法需要对数据进行编码，实现起来比较困难；文献[4]对蚁群算法进行了改进，并用改进的蚁群算法进行了无人机航路规划，但是蚁群算法参数繁多，并且初始信息素的设定带有主观因素^[5]，会对算法的收敛效果产生较大的影响。

教-学优化(Teaching-Learning-Based Optimization, TLBO)算法是继遗传算法、蚁群算法、粒子群算法之后提出的一种新的群体智能算法，可用于复杂多目标问题的求解^[6-8]。TLBO算法模拟教师给学员的教学过程和学员的学习过程，通过教师对学员的教学，和学员之间的互相学习来提高整个班级的学习成绩。传统TLBO算法参数很少，并且直接采用实数编码，在对所需求解的问题建模之后，只需要设定迭代次数，就可直接运行，没有其他参数^[9]。但是传统TLBO算法也存在着收敛速度慢、易于陷入局部最优的缺点。因此，本文提出了一种自适应交叉教-学优化(Adaptive Crossover Teaching-Learning-Based Optimization, AC-TLBO)算法，将遗传算法中的交叉过程引入教-学算法，并且令交叉概率随着适应度自适应变化，同时根据条件对算法进行扰动，提升算法的性能。利用改进之后的算法进行无人机航路规划，并且和传统教-学算法、量子粒子群优化(Quantum Behaved Particle Swarm Optimization, QPSO)算法进行比较，验证了改进算法的效果。

1 威胁信息建模

当无人机在巡航阶段飞行时，一般只需要考虑水平方向上的运动，忽略无人机的高度和俯仰角等限制条件，所以可以将无人机的航路规划简化为二维平面上的路径规划。本文的航路规划空间如图 1所示，规划空间的大小为100km×100km。将山体在一定高度的截面在图中表示为实心的圆形; 将对方的防御信息，如雷达和高炮等，表示为空心的圆形; 将禁飞区表示为实心的矩形。由于高炮、防空导弹或者其他火力攻击目标发挥作用的前提是雷达探测到目标，所以将火力攻击的模型也等效为雷达的模型。所以图 1中存在着四个山体截面模型、两个雷达模型和两个禁飞区模型。

航路规划就是无人机为了完成某一项任务，规划出一条从起点到终点的路径。而路径是由一系列的路径点所组成，只要找到了组成路径的这些路径点，就完成了航路的规划。

1.1 航路的代价函数

无人机执行任务时，既要保证无人机能够避开执行任务区域的威胁，比如雷达、禁飞区、地形威胁等，又要确保无人机耗油量最少，花费的时间最短，而耗油量和飞行时间与航路的长短有着直接的关系，所以，要使规划的航路尽量短。由此可以令航路的代价函数如下所示：

$ cost = \sum\limits_{j = 0}^N {\left( {{T_j} + {S_j} + {Q_j} + {L_j}} \right) = } \sum\limits_{j = 0}^N {\left( {T{h_j} + {L_j}} \right)} $

(1)

其中L_j表示第j段航路的长度，表示航路的长度代价。

$ {L_j} = \sqrt {{{\left( {{x_{j + 1}} - {x_j}} \right)}^2} + {{\left( {{y_{j + 1}} - {y_j}} \right)}^2}} $

(2)

其中:x_j和x_j+1是第j段航路起点和终点的横坐标，y_j和y_j+1是第j段航路起点和终点的纵坐标。

Th_j=T_j+S_j+Q_j是航路的威胁代价，T_j表示地形威胁代价，S_j表示雷达威胁代价，Q_j表示禁飞区威胁代价。航路的示意图如图 2所示。

1.2 圆形威胁

对于地形威胁和雷达威胁都可等效为圆形的威胁，可将这两种威胁用图 3的方式进行量化^[10]。

图 3中: j表示航路中第j个航路点，j+1表示第j+1个航路点; 图中0.1、0.4、0.6等表示把第j个航路点和第j+1个航路点之间平均分成10份，每一份所对应的端点。

对于地形威胁：

$ {T_j} = \left\{ \begin{array}{l} \Lambda ,第j段航路有点在山体圆之内\\ 0,第j段航路没有点在山体圆之内 \end{array} \right. $

(3)

其中Λ表示一个足够大的数。

对于雷达威胁：

$ {S_j} = \sum\limits_{k = 1}^n {{s_{k,j}}} $

(4)

$ {s_{k,j}} = \left\{ \begin{array}{l} {W_j},{d_{\min }} \le {R_k}\\ 0,\;\;\;{d_{\min }} > {R_k} \end{array} \right. $

(5)

$ {W_j} = {L_j}\sum\limits_{k = 1}^n {\left[ {{f_k}\left( {{d_{k,j,1/10}}} \right) + {f_k}\left( {{d_{k,j,2/10}}} \right) + \cdots {f_k}\left( {{d_{k,j,9/10}}} \right)} \right]} $

(6)

$ {f_k}\left( x \right) = {\delta _k}/{x^4} $

(7)

式(4)中，s_{k, j}表示第k个雷达对第j段航路的威胁。式(5)中，d_min表示第j段航路的等分点中，离雷达中心最近的距离，R_k表示第k个雷达的作用范围。式(6)中，L_j表示第j段航路的长度，d_{k, j, 1/10}表示第j段航路第1个等分点和雷达中心的距离，d_{k, j, 2/10}表示第j段航路第2个等分点和雷达中心的距离。式(7)表示雷达对某个点的作用与雷达中心和此点的距离的四次方成反比^[11]，δ_k表示第k个雷达的作用强度。

1.3 禁飞区威胁

在战场环境中，无人机进行航路规划时，必须完全避开禁飞区，不允许航路中的任何一点落在禁飞区之内。所以，禁飞区的威胁对航路的影响可以量化为：

$ {Q_j} = \left\{ \begin{array}{l} \Lambda ,第j段航路有点在禁飞区之内\\ 0,\;第j段航路没有点在禁飞区之内 \end{array} \right. $

(8)

其中Λ表示一个足够大的数。

2 改进的自适应交叉教-学算法 2.1 基本教-学算法(TLBO)

教-学算法是模拟以班级为单位的学习方式，班级中学生水平的提高需要老师来教学引导，同时，同学间的相互学习也可以促进整体水平的提高。而班级中的老师就是全部个体中适应度最好的个体。

2.2 教-学算法的基本步骤

步骤1  初始化整个班级。班级中每个学生X_i=(x_i¹, x_i², …, x_i^d)(i=1, 2, …, NP)，其中NP表示全部学生的个数，d表示每个学生所学科目的数量，即每个学生的维度。

$ \begin{array}{l} x_i^k = x_i^{{k_L}} + {\rm{rand}}\left( {0,1} \right) \times \left( {x_i^{{k_U}} - x_i^{{k_L}}} \right)\\ k = 1,2, \cdots ,d,i = 1,2, \cdots ,NP \end{array} $

(9)

步骤2  “教”阶段。在教-学算法的“教”阶段，班级中每个学生根据老师X_teacher和学生平均值Mean之间的差异度进行学习。

1)“教”的过程如下所示：

$ {\boldsymbol{X}_{i,{\rm{new}}}}{\rm{ = }}{\boldsymbol{X}_{i,{\rm{old}}}} + \boldsymbol{Difference} $

(10)

$ \boldsymbol{Difference} = {r_i} \cdot \left( {{\boldsymbol{X}_{{\rm{teacher}}}} - T{F_i} \cdot \boldsymbol{Mean}} \right) $

(11)

其中：X_{i, new}和X_{i, old}分别表示第i个学生学习后和学习前的值；Mean=$\frac{1}{{NP}}\sum\limits_{i = 1}^{NP} {{\boldsymbol{X}_i}} $是所有学生的平均值；TF_i表示教学因子，TF_i=round[1+rand(0, 1)]；r_i表示学习步长，r_i=rand(0, 1)。

2)在“教”完成之后，每个学生根据学习之前的成绩和学习之后的成绩进行比较。如果学习之后的成绩更好，就更新自身的成绩。

if f(X_{i, new})>f(X_{i, old})

 X_{i, old}=X_{i, new};

end

步骤3  “学”阶段。在“学”阶段，每个学生X_i在班级中随机选取两个学习对象X_j和X_k(i≠j≠k)，学生X_i通过分析学生X_j和X_k之间的差异进行学习。学习的具体过程如下：

1)“学”的过程如下所示：

$ {\boldsymbol{X}_{i,{\rm{new}}}}{\rm{ = }}\left\{ \begin{array}{l} {\boldsymbol{X}_{i,{\rm{old}}}} + {r_i} \cdot \left( {{\boldsymbol{X}_j} - {\boldsymbol{X}_k}} \right),f\left( {{\boldsymbol{X}_k}} \right) < f\left( {{\boldsymbol{X}_j}} \right)\\ {\boldsymbol{X}_{i,{\rm{old}}}} + {r_i} \cdot \left( {{\boldsymbol{X}_k} - {\boldsymbol{X}_j}} \right),f\left( {{\boldsymbol{X}_j}} \right) < f\left( {{\boldsymbol{X}_k}} \right) \end{array} \right. $

(12)

其中：r_i=rand(0, 1)表示第i个学生的学习因子。

2)在“学”完成之后，每个学生根据学习之前的成绩和学习之后的成绩进行比较。如果学习之后的成绩更好，就更新自身的成绩。

if f(X_{i, new})>f(X_{i, old})

X_{i, old}=X_{i, new};

end

步骤4  如果满足结束条件，就结束算法，否则转至步骤2继续运算。

根据以上的步骤可以看出，TLBO算法中“教”的过程类似于具有量子行为的粒子群算法(QPSO)，TLBO算法是根据所有学生的平均值和老师的值之间的误差进行调节，而老师的值就是所有学生的最优值；QPSO算法是根据所有粒子的历史最优位置和全局最优位置、所有粒子历史最优位置的平均值和粒子现在位置之间的误差进行调节。但是这些调节过程会导致所有个体都向最优个体靠拢，很容易陷入局部最优。TLBO算法中“学”的过程加强了学生之间的交流，群体的多样性能够更好地保持，所以更不容易陷入局部最优。但是“学”过程的引入导致学生不完全向着老师的值靠拢，所以会导致算法的收敛过程增长。

2.3 改进的自适应交叉教-学算法

为了改善基本TLBO算法收敛过程长和可能陷入局部最优这些缺点，本文提出了一种改进的自适应交叉教-学算法(AC-TLBO)。

1)基本教-学算法中，影响学习速度的教学因子TF_i=round[1+rand(0, 1)]，所以教学因子不是1就是2，即学生的学习程度是随机的，而且是离散的，没有完全利用老师所教的信息。这里提出一种自适应改变的教学因子，教学因子随着迭代次数而连续发生变化，即学生的学习能力随着迭代次数而连续发生变化。

$ T{F_i} = T{F_{\max }} - \left( {T{F_{\max }} - T{F_{\min }}} \right) \cdot iter/itermax $

(13)

式(15)表示教学因子TF_i随着迭代次数iter的变化而变化。TF_max和TF_min分别表示教学因子的最大值和最小值，itermax表示最大迭代次数。

2)基本教-学算法中，当算法陷入局部最优时，一般很难跳出局部最优。所以当检测到算法早熟时，可以在算法中加入随机扰动。在算法中加入早熟因子f_m，把无效迭代的次数记作f_g，当无效迭代的次数大于早熟因子f_m时，就在算法的“教”过程中加入扰动。加入随机扰动的方法如下：

$ {\boldsymbol{X}_{i,{\rm{new}}}}{\rm{ = }}{\boldsymbol{X}_{i,{\rm{old}}}} + \boldsymbol{Difference} + \lambda \cdot \boldsymbol{randn}\left( {} \right) $

(14)

λ为扰动的控制参数，λ越大，扰动越大，反之则越小。randn()是产生正态分布值的随机函数。在本文中，令λ也随着迭代次数变化，即:

$ \lambda = {\lambda _{\min }} + \left( {{\lambda _{\max }} - {\lambda _{\min }}} \right) \cdot iter/itermax $

(15)

无效迭代是指所有个体的最优适应度值随着迭代进行变化很小，即:

$ \left| {{F_{{\rm{best}}}}\left( {t + 1} \right) - {F_{{\rm{best}}}}\left( t \right)} \right| < \varepsilon $

(16)

F_best(t+1)表示第t+1次迭代的最优适应度值，F_best(t)表示第t次迭代的最优适应度值，ε为最优适应度值变化量的下限。当最优适应度值变化量小于ε时，就进行扰动；反之，则不扰动。

3)在传统的遗传算法中，交叉可以产生新的个体，并且是主要的产生新个体的过程，所以把交叉引入到TLBO算法中，放在“学”过程之后。交叉相当于是学生中关系较好的个体进行相互交流，交流的过程可以取长补短，加快算法的收敛^[12]；并且为了增加算法跳出局部最优的概率，在交叉的过程中也引入扰动。具体的实现方法如下：

if rand(0, 1) < pcross

 temp=rand(0, 1);

 X_{i, new}=temp·X_{i, old}+(1-temp)·X_{j, old};

 X_{j, new}=temp·X_{j, old}+(1-temp)·X_{i, old};

 if f_g>f_m

  X_{i, new}=X_{i, new}+λ·randn();

  X_{j, new}=X_{j, new}+λ·randn();

 end

end

上述方法中，X_{i, old}和X_{j, old}是随机选取的两个学生；rand(0, 1)是产生0~1的随机数；pcross是交叉的概率，当满足交叉的条件时，才进行交叉；pcross按照式(20)进行自适应交叉概率计算^[13]。

$ pcross = \left\{ \begin{array}{l} \frac{{{P_{c3}}\left( {{f_{{\rm{avg}}}} - f} \right) + {P_{c2}}\left( {f - {f_{\min }}} \right)}}{{{f_{{\rm{avg}}}} - {f_{\min }}}},f < {f_{{\rm{avg}}}}\\ \frac{{{P_{c2}}\left( {{f_{\max }} - f} \right) + {P_{c1}}\left( {f - {f_{{\rm{avg}}}}} \right)}}{{{f_{\max }} - {f_{{\rm{avg}}}}}},f \ge {f_{{\rm{avg}}}} \end{array} \right. $

(17)

其中： f表示要交叉的两个个体中较好个体的适应度值。根据以上的交叉概率计算方法，个体的交叉概率能够自适应地改变。每个个体的交叉概率与其自身的适应度、所有个体的最低适应度值f_min、所有个体的最高适应度值f_max和平均适应度值f_avg有关，所以个体的交叉概率是随着整体适应度自适应变化的。

在交叉完成之后，每个学生根据“交叉”之前的成绩和交叉之后的成绩进行比较。如果交叉之后的成绩更好，就更新自身的成绩。

if f(X_{i, new})>f(X_{i, old})

 X_{i, old}=X_{i, new};

end

通过以上三点的改进，改进的自适应交叉教-学算法流程如图 4所示。

3 基于改进教-学算法的航路规划

用改进的自适应交叉教-学算法进行航路规划时，每个学生表示一条航路，每条航路由若干个航路点组成，这些航路点在算法中表示为每个学生所学的科目。假设班级中共有M个学生，每个学生学习N门科目，则表示规划空间中有M条航路，每条航路由N个航路点组成。初始化M条航路之后，计算每条航路的适应度，然后找到最优适应度对应的航路，即老师，根据最优航路进行“教”过程，并且调节所有航路的位置；“教”过程结束之后，进行“学”过程，调节每条航路的位置；最后进行“交叉”，更新每条航路。通过不断地迭代，可以找到最优的适应度值及其所对应的航路。

3.1 航路点的编码

每一条航路都由若干个航路点组成，航路点越多，规划出的航路越精细，反之规划出的航路越粗糙。二维平面中，航路点的位置用坐标表示。每个点的坐标分为横坐标和纵坐标，为了计算简便，可以采用图 5的编码方式^[14]。

图 5中，O-XY是全局坐标系，start是航路规划的起始点，destination是航路规划的终点。航路规划时，以起始点和终止点的连线为新的坐标系O′-X′Y′的O′X′轴，以经过起始点start并且和O′X′轴垂直的线为O′Y′轴。将起始点和终止点之间的连线进行N+1等分，在每个等分点处作O′X′的垂线，可以得到相互平行的直线簇(L₁, L₂, …, L_N)，直线簇与路径的交点即为航路点(P₁, P₂, …, P_N)，如果航路规划找到了这些航路点的位置，那么连接这些航路点就可以得到整条航路，所以，航路规划的主要工作就是找到这些航路点。由于航路点在平行直线簇(L₁, L₂, …, L_N)之上，所以这些航路点在O′-X′Y′平面内的横坐标就可以根据平行直线簇来确定，要得到航路点具体位置只需要找到合适的纵坐标即可。

$ x{'_i} = i \cdot \frac{{{L_{SD}}}}{{N + 1}};i = 1,2, \cdots ,N $

(18)

$ y{'_i} = {\rm{rand}}\left( {y{'_{\min }},y{'_{\max }}} \right);i = 1,2, \cdots ,N $

(19)

3.2 航路点坐标转换

规划空间中的威胁都是在全局坐标系O-XY中，航路点的横坐标却是在新坐标系O′-X′Y′中，所以就需要将航路点的横坐标转化到全局坐标系中。转换公式表示如下：

$ \left[ \begin{array}{l} x\\ y \end{array} \right] = \left[ {\begin{array}{*{20}{c}} {\cos \theta }&{ - \sin \theta }\\ {\sin \theta }&{\cos \theta } \end{array}} \right]\left[ \begin{array}{l} x'\\ y' \end{array} \right] + \left[ \begin{array}{l} {x_0}\\ {y_0} \end{array} \right] $

(20)

其中：x和y是点在O-XY坐标系下的坐标，x′和y′是点在O′-X′Y′坐标系下的坐标，x₀和y₀是O′-X′Y′坐标系的原点在O-XY坐标系下的坐标，θ是O′X′轴和OX轴的夹角。

3.3 航路平滑处理

根据前面的分析可知，算法得到航路点坐标之后，完整的航路就是用线段连接航路点得到的。但是得到的航路是由折线构成的，没有考虑到无人机转弯半径等因素的影响，所以要对航路进行平滑处理。此处用文献[15]采用的3次B样条曲线方法对航路进行平滑处理^[15]。

4 仿真分析

根据图 1所示的规划空间，四个山体截面的圆心坐标分别为(10, 20)，(25, 70)，(60, 55)，(50.2, 70.1)，截面半径分别为(8, 7, 5, 8)；雷达威胁的圆心坐标分别为(45, 52)，(80, 60)，半径分别为(6, 5)，威胁系数为20；矩形禁飞区的左上角和右下角坐标分别为(30, 40)、(40, 0)和(70, 100)、(80, 70)。航路规划的起始点是(0, 0)，终止点是(90, 90)。

基本教-学算法和自适应交叉教-学算法中，设定学生数量为M=80，每个学生学习的科目数为N=20，y′_min=-50，y′_max=50；量子粒子群算法中，设定粒子的数量M=80，每个粒子的维度为N=20，收缩扩张系数从1.0到0.5线性变化。以上设定表示三种算法规划的航路有80条，每条航路由20个航路点组成，在O′-X′Y′坐标系中，初始化航路点纵坐标时，上限为-50，下限为50。此外，在自适应交叉教-学算法中，设定教学因子上限TF_max=2，下限TF_min=1；扰动控制参数λ的下限λ_min=1.5，上限λ_max=3；早熟因子f_m=20；最优适应度值变化量的下限ε=0.03；交叉概率计算公式中，P_c3=0.3, P_c2=0.5, P_c1=0.8。

1)迭代相同代数时三种算法性能比较。

设定最大迭代次数iternum=2000，三种算法各运行10次。经过仿真，可能得到的航路如图 6~8所示。

由图 6~8可知，得到的航路分为最优、次优1、次优2和其他四种情况，这四种情况下的适应度值范围分别为[133.8, 134.5]、[135.1, 136.4]、[139.0, 142.0]和[142.0, +∞]。所以此优化问题至少有两个局部最优值。用三种算法各进行10次航路规划，则结果如表 1所示，它们的平均适应度值变化曲线如图 9所示。

算法的平均运行时间如表 2所示。

根据图 9可知，迭代相同的代数，从收敛速度而言，AC-TLBO收敛最快，TLBO和QPSO算法收敛速度不相上下；从是否容易陷入局部最优而言，AC-TLBO算法最不容易陷入局部最优，TLBO算法次之，QPSO算法最差。根据表 2可知，AC-TLBO算法运行时间最长，主要是由于在基本TLBO算法中加入了“交叉”和“扰动”；QPSO算法运行时间最短。

2)运行相同时间时三种算法性能比较。

设定算法的运行时间都为300s，则三种算法的适应度值变化曲线如图 10所示。

根据图 10可知，三种算法运行同样的时间，虽然AC-TLBO算法运行一次的时间最长，但是其收敛速度仍然最快，QPSO算法收敛速度次之，TLBO收敛速度最慢。并且AC-TLBO算法没有陷入局部最优，而另外两种算法都陷入了局部最优。

所以，根据以上对比可知，基本教-学算法(TLBO)和量子行为粒子群算法(QPSO)容易陷入局部最优，并且在迭代次数一定的情况下，不一定能够找到最优解，甚至是次优解；而自适应交叉教-学算法(AC-TLBO)能够很快地收敛，虽然也会陷入局部最优，但是由于算法中加入了扰动，它仍有一定的概率跳出局部最优，进而向全局最优移动。

5 结语

本文在传统教-学优化算法的基础上引入了交叉过程和扰动过程，提出了自适应交叉教-学优化算法。通过对无人机航路规划中存在的威胁进行分析建模，分别用传统教-学优化算法、自适应交叉教-学优化算法和量子粒子群优化算法进行规划，仿真实验结果表明，自适应交叉教-学优化算法不仅提高了原算法的收敛速度，而且有效避免了原算法易陷入局部最优的不足，可以用来解决无人机的航路规划问题，后续工作是将规划模型和算法扩展到三维空间，以更好地应用于无人机系统中。