基于改进教学算法的无人机航路规划

武巍　邹杰

摘要：

针对传统教学优化（TLBO）算法进行航路规划时收敛速度慢、容易陷入局部最优的问题，提出一种自适应交叉教学优化（ACTLBO）算法。首先，该算法令传统教学优化（TLBO）算法的教学因子随着迭代次数而发生变化，提高算法的学习速度；其次，当算法可能要陷入局部最优时，加入一定的扰动，使算法尽可能地跳出局部最优；最后，为了进一步提升算法的收敛效果，在算法中引入遗传算法的交叉环节。利用传统教学优化（TLBO）算法、自适应交叉教学优化（ACTLBO）算法和量子粒子群优化（QPSO）算法进行无人机航路规划，仿真结果表明，在10次规划中，自适应交叉教学优化（ACTLBO）算法有8次找到了全局最优路径，而传统教学优化（TLBO）算法和量子粒子群优化（QPSO）算法分别只找到了2次和1次；而且自适应交叉教学优化（ACTLBO）算法的收敛速度高于另外两种算法。

关键词：

教学优化算法；无人机；航路规划；自适应交叉；局部最优；量子粒子群优化算法

中图分类号：

TP391.9

文献标志码：A

Abstract：

Aiming at the problem of slow convergence and being easy to fall into local optimum in the route planning of the traditional teachinglearningbased optimization algorithm， an adaptive crossover teachinglearningbased optimization algorithm was proposed. Firstly， the teaching factor of the algorithm was changed with the number of iterations， so the learning speed of the algorithm was improved. Secondly， when the algorithm was likely to fall into local optimum， a certain disturbance was added to make the algorithm jump out of local optimum as far as possible. Finally， in order to improve the convergence effect， the crossover link of genetic algorithm was introduced into the algorithm. Then the path planning of Unmanned Aerial Vehicle （UAV） was carried out by using the traditional teachinglearningbased optimization algorithm， the adaptive crossover teachinglearningbased optimization algorithm and the Quantum Particle Swarms Optimization （QPSO） algorithm. The simulation results show that in 10 times of planning， the adaptive crossover teachinglearningbased optimization algorithm finds the global optimal route for 8 times， while the traditional teachinglearningbased optimization algorithm and the QPSO algorithm find the route for only 2 times and 1 time respectively， and the convergence of the adaptive crossover teachinglearningbased optimization algorithm is faster than the other two algorithms.

英文关键词Key words：

teachinglearningbased optimization algorithm； Unmanned Aerial Vehicle （UAV）； route planning； adaptive crossover； local optimum； Quantum Particle Swarms Optimization （QPSO） algorithm

0引言

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

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

1威胁信息建模

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

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

1.1航路的代价函数

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

cost=∑Nj=0（Tj+Sj+Qj+Lj）=∑Nj=0（Thj+Lj）（1）

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

Lj=（xj+1-xj）2+（yj+1-yj）2（2）

其中：xj和xj+1是第j段航路起点和终点的横坐标，yj和yj+1是第j段航路起点和终点的纵坐标。

Thj=Tj+Sj+Qj是航路的威胁代价，Tj表示地形威胁代价，Sj表示雷达威胁代价，Qj表示禁飞区威胁代价。航路的示意图如图2所示。

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

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

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

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

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

TFi=TFmax-（TFmax-TFmin）·iter/itermax（13）

式（15）表示教学因子TFi随着迭代次数iter的变化而变化。TFmax和TFmin分别表示教学因子的最大值和最小值，itermax表示最大迭代次数。

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

Xi，new=Xi，old+Difference+λ·randn（）（14）

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

λ=λmin+（λmax-λmin）·iter/itermax（15）

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

Fbest（t+1）-Fbest（t）<ε（16）

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

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

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

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

3.1航路点的编码

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

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

3.2航路点坐标转换

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

xy=cos θ-sin θsin θcos θx′y′+x0y0（20）

其中：x和y是点在OXY坐标系下的坐标，x′和y′是点在O′X′Y′坐标系下的坐标，x0和y0是O′X′Y′坐标系的原点在OXY坐标系下的坐标，θ是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。此外，在自适应交叉教学算法中，设定教学因子上限TFmax=2，下限TFmin=1；扰动控制参数λ的下限λmin=1.5，上限λmax=3；早熟因子fm=20；最优适应度值变化量的下限ε=0.03；交叉概率计算公式中，Pc3=0.3，Pc2=0.5，Pc1=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所示。

TLBO算法运行一次的时间最长，但是其收敛速度仍然最快，QPSO算法收敛速度次之，TLBO收敛速度最慢。并且ACTLBO算法没有陷入局部最优，而另外两种算法都陷入了局部最优。

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

5结语

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

参考文献：

[1]

席庆彪，苏鹏，刘慧霞.基于A*算法的无人机航路规划算法[J].火力与指挥控制，2013，38（11）：5-9.（XI Q B， SU P， LIU H X. Research on a path plannings method for UAV based on A* algorithm [J]. Fire Control & Command Control， 2013， 38（11）：5-9.）

[2]

占伟伟，王伟，陈能成，等. 一种利用改进A*算法的无人机航迹规划[J].武汉大学学报（信息科学版），2015，40（3）：315-320.（ZHAN W W， WANG W， CHEN N C， et al. Path planning strategies for UAV based on improved A* algorithm [J]. Geomatics and Information Science of Wuhan University， 2015，40（3）：315-320.）

[3]

郑锐，冯振明，陆明泉.基于遗传算法的无人机航路规划优化研究[J].计算机仿真，2011，28（6）：88-91.（ZHENG R， FENG Z M， LU M Q. Application of particle genetic algorithm to path planning of unmanned aerial vehicle [J]. Computer Simulation， 2011， 28（6）： 88-91.）

[4]

孟祥恒，王社伟，陶军.基于改进蚁群算法的多无人机航路规划研究[J].计算机仿真，2008，25（11）：56-59.（MENG X H， WANG S W， TAO J. Cooperative route planning for UCAVs using Voronoi based multibehavior ant colony algorithm [J]. Computer Simulation， 2008， 25（11）： 56-59.）

[5]

高曼，刘以安，张强.优化蚁群算法在反舰导弹航路规划中的应用[J].计算机应用，2012，32（9）：2530-2533.（GAO M， LIU Y A， ZHANG Q. Application of improved ant colony algorithm to route planning of antiship missile [J]. Journal of Computer Applications， 2012， 32（9）： 2530-2533.）