基于改進教學算法的無人機航路規劃

武巍　鄒杰

摘要：

針對傳統教學優化（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.）