基于改進(jìn)教學(xué)算法的無人機(jī)航路規(guī)劃

武巍　鄒杰

摘要：

針對(duì)傳統(tǒng)教學(xué)優(yōu)化（TLBO）算法進(jìn)行航路規(guī)劃時(shí)收斂速度慢、容易陷入局部最優(yōu)的問題，提出一種自適應(yīng)交叉教學(xué)優(yōu)化（ACTLBO）算法。首先，該算法令傳統(tǒng)教學(xué)優(yōu)化（TLBO）算法的教學(xué)因子隨著迭代次數(shù)而發(fā)生變化，提高算法的學(xué)習(xí)速度；其次，當(dāng)算法可能要陷入局部最優(yōu)時(shí)，加入一定的擾動(dòng)，使算法盡可能地跳出局部最優(yōu)；最后，為了進(jìn)一步提升算法的收斂效果，在算法中引入遺傳算法的交叉環(huán)節(jié)。利用傳統(tǒng)教學(xué)優(yōu)化（TLBO）算法、自適應(yīng)交叉教學(xué)優(yōu)化（ACTLBO）算法和量子粒子群優(yōu)化（QPSO）算法進(jìn)行無人機(jī)航路規(guī)劃，仿真結(jié)果表明，在10次規(guī)劃中，自適應(yīng)交叉教學(xué)優(yōu)化（ACTLBO）算法有8次找到了全局最優(yōu)路徑，而傳統(tǒng)教學(xué)優(yōu)化（TLBO）算法和量子粒子群優(yōu)化（QPSO）算法分別只找到了2次和1次；而且自適應(yīng)交叉教學(xué)優(yōu)化（ACTLBO）算法的收斂速度高于另外兩種算法。

關(guān)鍵詞：

教學(xué)優(yōu)化算法；無人機(jī)；航路規(guī)劃；自適應(yīng)交叉；局部最優(yōu)；量子粒子群優(yōu)化算法

中圖分類號(hào)：

TP391.9

文獻(xiàn)標(biāo)志碼：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.

英文關(guān)鍵詞Key words：

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

0引言

無人機(jī)（Unmanned Aerial Vehicle， UAV）為了完成偵查任務(wù)或者對(duì)目標(biāo)進(jìn)行打擊，首先必須對(duì)執(zhí)行任務(wù)的區(qū)域進(jìn)行分析，預(yù)先規(guī)劃出一條能夠完成任務(wù)的航路。目前航路規(guī)劃的方法有很多：文獻(xiàn)[1]采用A*算法進(jìn)行了無人機(jī)航路規(guī)劃，A*算法易于實(shí)現(xiàn)，但是算法是采用節(jié)點(diǎn)擴(kuò)展的方式進(jìn)行搜索[2]，因此節(jié)點(diǎn)擴(kuò)展方式不同，得到的航路也不同，所以可能會(huì)找不到最優(yōu)路徑；文獻(xiàn)[3]利用遺傳算法進(jìn)行航路規(guī)劃，算法從全局最優(yōu)的角度進(jìn)行計(jì)算，但是遺傳算法需要對(duì)數(shù)據(jù)進(jìn)行編碼，實(shí)現(xiàn)起來比較困難；文獻(xiàn)[4]對(duì)蟻群算法進(jìn)行了改進(jìn)，并用改進(jìn)的蟻群算法進(jìn)行了無人機(jī)航路規(guī)劃，但是蟻群算法參數(shù)繁多，并且初始信息素的設(shè)定帶有主觀因素[5]，會(huì)對(duì)算法的收斂效果產(chǎn)生較大的影響。

教學(xué)優(yōu)化（TeachingLearningBased Optimization， TLBO）算法是繼遺傳算法、蟻群算法、粒子群算法之后提出的一種新的群體智能算法，可用于復(fù)雜多目標(biāo)問題的求解[6-8]。TLBO算法模擬教師給學(xué)員的教學(xué)過程和學(xué)員的學(xué)習(xí)過程，通過教師對(duì)學(xué)員的教學(xué)，和學(xué)員之間的互相學(xué)習(xí)來提高整個(gè)班級(jí)的學(xué)習(xí)成績(jī)。傳統(tǒng)TLBO算法參數(shù)很少，并且直接采用實(shí)數(shù)編碼，在對(duì)所需求解的問題建模之后，只需要設(shè)定迭代次數(shù)，就可直接運(yùn)行，沒有其他參數(shù)[9]。但是傳統(tǒng)TLBO算法也存在著收斂速度慢、易于陷入局部最優(yōu)的缺點(diǎn)。因此，本文提出了一種自適應(yīng)交叉教學(xué)優(yōu)化（Adaptive Crossover TeachingLearningBased Optimization， ACTLBO）算法，將遺傳算法中的交叉過程引入教學(xué)算法，并且令交叉概率隨著適應(yīng)度自適應(yīng)變化，同時(shí)根據(jù)條件對(duì)算法進(jìn)行擾動(dòng)，提升算法的性能。利用改進(jìn)之后的算法進(jìn)行無人機(jī)航路規(guī)劃，并且和傳統(tǒng)教學(xué)算法、量子粒子群優(yōu)化（Quantum Behaved Particle Swarm Optimization， QPSO）算法進(jìn)行比較，驗(yàn)證了改進(jìn)算法的效果。

1威脅信息建模

當(dāng)無人機(jī)在巡航階段飛行時(shí)，一般只需要考慮水平方向上的運(yùn)動(dòng)，忽略無人機(jī)的高度和俯仰角等限制條件，所以可以將無人機(jī)的航路規(guī)劃簡(jiǎn)化為二維平面上的路徑規(guī)劃。本文的航路規(guī)劃空間如圖1所示，規(guī)劃空間的大小為100km×100km。將山體在一定高度的截面在圖中表示為實(shí)心的圓形；將對(duì)方的防御信息，如雷達(dá)和高炮等，表示為空心的圓形；將禁飛區(qū)表示為實(shí)心的矩形。由于高炮、防空導(dǎo)彈或者其他火力攻擊目標(biāo)發(fā)揮作用的前提是雷達(dá)探測(cè)到目標(biāo)，所以將火力攻擊的模型也等效為雷達(dá)的模型。所以圖1中存在著四個(gè)山體截面模型、兩個(gè)雷達(dá)模型和兩個(gè)禁飛區(qū)模型。

航路規(guī)劃就是無人機(jī)為了完成某一項(xiàng)任務(wù)，規(guī)劃出一條從起點(diǎn)到終點(diǎn)的路徑。而路徑是由一系列的路徑點(diǎn)所組成，只要找到了組成路徑的這些路徑點(diǎn)，就完成了航路的規(guī)劃。

1.1航路的代價(jià)函數(shù)

無人機(jī)執(zhí)行任務(wù)時(shí)，既要保證無人機(jī)能夠避開執(zhí)行任務(wù)區(qū)域的威脅，比如雷達(dá)、禁飛區(qū)、地形威脅等，又要確保無人機(jī)耗油量最少，花費(fèi)的時(shí)間最短，而耗油量和飛行時(shí)間與航路的長短有著直接的關(guān)系，所以，要使規(guī)劃的航路盡量短。由此可以令航路的代價(jià)函數(shù)如下所示：

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

其中Lj表示第j段航路的長度，表示航路的長度代價(jià)。

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

其中：xj和xj+1是第j段航路起點(diǎn)和終點(diǎn)的橫坐標(biāo)，yj和yj+1是第j段航路起點(diǎn)和終點(diǎn)的縱坐標(biāo)。

Thj=Tj+Sj+Qj是航路的威脅代價(jià)，Tj表示地形威脅代價(jià)，Sj表示雷達(dá)威脅代價(jià)，Qj表示禁飛區(qū)威脅代價(jià)。航路的示意圖如圖2所示。

步驟4如果滿足結(jié)束條件，就結(jié)束算法，否則轉(zhuǎn)至步驟2繼續(xù)運(yùn)算。

根據(jù)以上的步驟可以看出，TLBO算法中“教”的過程類似于具有量子行為的粒子群算法（QPSO），TLBO算法是根據(jù)所有學(xué)生的平均值和老師的值之間的誤差進(jìn)行調(diào)節(jié)，而老師的值就是所有學(xué)生的最優(yōu)值；QPSO算法是根據(jù)所有粒子的歷史最優(yōu)位置和全局最優(yōu)位置、所有粒子歷史最優(yōu)位置的平均值和粒子現(xiàn)在位置之間的誤差進(jìn)行調(diào)節(jié)。但是這些調(diào)節(jié)過程會(huì)導(dǎo)致所有個(gè)體都向最優(yōu)個(gè)體靠攏，很容易陷入局部最優(yōu)。TLBO算法中“學(xué)”的過程加強(qiáng)了學(xué)生之間的交流，群體的多樣性能夠更好地保持，所以更不容易陷入局部最優(yōu)。但是“學(xué)”過程的引入導(dǎo)致學(xué)生不完全向著老師的值靠攏，所以會(huì)導(dǎo)致算法的收斂過程增長。

2.3改進(jìn)的自適應(yīng)交叉教學(xué)算法

為了改善基本TLBO算法收斂過程長和可能陷入局部最優(yōu)這些缺點(diǎn)，本文提出了一種改進(jìn)的自適應(yīng)交叉教學(xué)算法（ACTLBO）。

1）基本教學(xué)算法中，影響學(xué)習(xí)速度的教學(xué)因子TFi=round[1+rand（0，1）]，所以教學(xué)因子不是1就是2，即學(xué)生的學(xué)習(xí)程度是隨機(jī)的，而且是離散的，沒有完全利用老師所教的信息。這里提出一種自適應(yīng)改變的教學(xué)因子，教學(xué)因子隨著迭代次數(shù)而連續(xù)發(fā)生變化，即學(xué)生的學(xué)習(xí)能力隨著迭代次數(shù)而連續(xù)發(fā)生變化。

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

式（15）表示教學(xué)因子TFi隨著迭代次數(shù)iter的變化而變化。TFmax和TFmin分別表示教學(xué)因子的最大值和最小值，itermax表示最大迭代次數(shù)。

2）基本教學(xué)算法中，當(dāng)算法陷入局部最優(yōu)時(shí)，一般很難跳出局部最優(yōu)。所以當(dāng)檢測(cè)到算法早熟時(shí)，可以在算法中加入隨機(jī)擾動(dòng)。在算法中加入早熟因子fm，把無效迭代的次數(shù)記作fg，當(dāng)無效迭代的次數(shù)大于早熟因子fm時(shí)，就在算法的“教”過程中加入擾動(dòng)。加入隨機(jī)擾動(dòng)的方法如下：

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

λ為擾動(dòng)的控制參數(shù)，λ越大，擾動(dòng)越大，反之則越小。randn（）是產(chǎn)生正態(tài)分布值的隨機(jī)函數(shù)。在本文中，令λ也隨著迭代次數(shù)變化，即：

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

無效迭代是指所有個(gè)體的最優(yōu)適應(yīng)度值隨著迭代進(jìn)行變化很小，即：

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

Fbest（t+1）表示第t+1次迭代的最優(yōu)適應(yīng)度值，F(xiàn)best（t）表示第t次迭代的最優(yōu)適應(yīng)度值，ε為最優(yōu)適應(yīng)度值變化量的下限。當(dāng)最優(yōu)適應(yīng)度值變化量小于ε時(shí)，就進(jìn)行擾動(dòng)；反之，則不擾動(dòng)。

3）在傳統(tǒng)的遺傳算法中，交叉可以產(chǎn)生新的個(gè)體，并且是主要的產(chǎn)生新個(gè)體的過程，所以把交叉引入到TLBO算法中，放在“學(xué)”過程之后。交叉相當(dāng)于是學(xué)生中關(guān)系較好的個(gè)體進(jìn)行相互交流，交流的過程可以取長補(bǔ)短，加快算法的收斂[12]；并且為了增加算法跳出局部最優(yōu)的概率，在交叉的過程中也引入擾動(dòng)。具體的實(shí)現(xiàn)方法如下：

3基于改進(jìn)教學(xué)算法的航路規(guī)劃

用改進(jìn)的自適應(yīng)交叉教學(xué)算法進(jìn)行航路規(guī)劃時(shí)，每個(gè)學(xué)生表示一條航路，每條航路由若干個(gè)航路點(diǎn)組成，這些航路點(diǎn)在算法中表示為每個(gè)學(xué)生所學(xué)的科目。假設(shè)班級(jí)中共有M個(gè)學(xué)生，每個(gè)學(xué)生學(xué)習(xí)N門科目，則表示規(guī)劃空間中有M條航路，每條航路由N個(gè)航路點(diǎn)組成。初始化M條航路之后，計(jì)算每條航路的適應(yīng)度，然后找到最優(yōu)適應(yīng)度對(duì)應(yīng)的航路，即老師，根據(jù)最優(yōu)航路進(jìn)行“教”過程，并且調(diào)節(jié)所有航路的位置；“教”過程結(jié)束之后，進(jìn)行“學(xué)”過程，調(diào)節(jié)每條航路的位置；最后進(jìn)行“交叉”，更新每條航路。通過不斷地迭代，可以找到最優(yōu)的適應(yīng)度值及其所對(duì)應(yīng)的航路。

3.1航路點(diǎn)的編碼

每一條航路都由若干個(gè)航路點(diǎn)組成，航路點(diǎn)越多，規(guī)劃出的航路越精細(xì)，反之規(guī)劃出的航路越粗糙。二維平面中，航路點(diǎn)的位置用坐標(biāo)表示。每個(gè)點(diǎn)的坐標(biāo)分為橫坐標(biāo)和縱坐標(biāo)，為了計(jì)算簡(jiǎn)便，可以采用圖5的編碼方式[14]。

圖5中，OXY是全局坐標(biāo)系，start是航路規(guī)劃的起始點(diǎn)，destination是航路規(guī)劃的終點(diǎn)。航路規(guī)劃時(shí)，以起始點(diǎn)和終止點(diǎn)的連線為新的坐標(biāo)系O′X′Y′的O′X′軸，以經(jīng)過起始點(diǎn)start并且和O′X′軸垂直的線為O′Y′軸。將起始點(diǎn)和終止點(diǎn)之間的連線進(jìn)行N+1等分，在每個(gè)等分點(diǎn)處作O′X′的垂線，可以得到相互平行的直線簇（L1，L2，…，LN），直線簇與路徑的交點(diǎn)即為航路點(diǎn)（P1，P2，…，PN），如果航路規(guī)劃找到了這些航路點(diǎn)的位置，那么連接這些航路點(diǎn)就可以得到整條航路，所以，航路規(guī)劃的主要工作就是找到這些航路點(diǎn)。由于航路點(diǎn)在平行直線簇（L1，L2，…，LN）之上，所以這些航路點(diǎn)在O′X′Y′平面內(nèi)的橫坐標(biāo)就可以根據(jù)平行直線簇來確定，要得到航路點(diǎn)具體位置只需要找到合適的縱坐標(biāo)即可。

3.2航路點(diǎn)坐標(biāo)轉(zhuǎn)換

規(guī)劃空間中的威脅都是在全局坐標(biāo)系OXY中，航路點(diǎn)的橫坐標(biāo)卻是在新坐標(biāo)系O′X′Y′中，所以就需要將航路點(diǎn)的橫坐標(biāo)轉(zhuǎn)化到全局坐標(biāo)系中。轉(zhuǎn)換公式表示如下：

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

其中：x和y是點(diǎn)在OXY坐標(biāo)系下的坐標(biāo)，x′和y′是點(diǎn)在O′X′Y′坐標(biāo)系下的坐標(biāo)，x0和y0是O′X′Y′坐標(biāo)系的原點(diǎn)在OXY坐標(biāo)系下的坐標(biāo)，θ是O′X′軸和OX軸的夾角。

3.3航路平滑處理

根據(jù)前面的分析可知，算法得到航路點(diǎn)坐標(biāo)之后，完整的航路就是用線段連接航路點(diǎn)得到的。但是得到的航路是由折線構(gòu)成的，沒有考慮到無人機(jī)轉(zhuǎn)彎半徑等因素的影響，所以要對(duì)航路進(jìn)行平滑處理。此處用文獻(xiàn)[15]采用的3次B樣條曲線方法對(duì)航路進(jìn)行平滑處理[15]。

4仿真分析

根據(jù)圖1所示的規(guī)劃空間，四個(gè)山體截面的圓心坐標(biāo)分別為（10，20），（25，70），（60，55），（50.2，70.1），截面半徑分別為（8，7，5，8）；雷達(dá)威脅的圓心坐標(biāo)分別為（45，52），（80，60），半徑分別為（6，5），威脅系數(shù)為20；矩形禁飛區(qū)的左上角和右下角坐標(biāo)分別為（30，40）、（40，0）和（70，100）、（80，70）。航路規(guī)劃的起始點(diǎn)是（0，0），終止點(diǎn)是（90，90）。

基本教學(xué)算法和自適應(yīng)交叉教學(xué)算法中，設(shè)定學(xué)生數(shù)量為M=80，每個(gè)學(xué)生學(xué)習(xí)的科目數(shù)為N=20，y′min=-50，y′max=50；量子粒子群算法中，設(shè)定粒子的數(shù)量M=80，每個(gè)粒子的維度為N=20，收縮擴(kuò)張系數(shù)從1.0到0.5線性變化。以上設(shè)定表示三種算法規(guī)劃的航路有80條，每條航路由20個(gè)航路點(diǎn)組成，在O′X′Y′坐標(biāo)系中，初始化航路點(diǎn)縱坐標(biāo)時(shí)，上限為-50，下限為50。此外，在自適應(yīng)交叉教學(xué)算法中，設(shè)定教學(xué)因子上限TFmax=2，下限TFmin=1；擾動(dòng)控制參數(shù)λ的下限λmin=1.5，上限λmax=3；早熟因子fm=20；最優(yōu)適應(yīng)度值變化量的下限ε=0.03；交叉概率計(jì)算公式中，Pc3=0.3，Pc2=0.5，Pc1=0.8。

1）迭代相同代數(shù)時(shí)三種算法性能比較。

設(shè)定最大迭代次數(shù)iternum=2000，三種算法各運(yùn)行10次。經(jīng)過仿真，可能得到的航路分為以下幾種情況，如圖6～8所示。

由圖6～8可知，得到的航路分為最優(yōu)、次優(yōu)1、次優(yōu)2和其他四種情況，這四種情況下的適應(yīng)度值范圍分別為[133.8，134.5]、[135.1，136.4]、[139.0，142.0]和[142.0，+∞]。所以此優(yōu)化問題至少有兩個(gè)局部最優(yōu)值。用三種算法各進(jìn)行10次航路規(guī)劃，則結(jié)果如表1所示，它們的平均適應(yīng)度值變化曲線如圖9所示。

TLBO算法運(yùn)行一次的時(shí)間最長，但是其收斂速度仍然最快，QPSO算法收斂速度次之，TLBO收斂速度最慢。并且ACTLBO算法沒有陷入局部最優(yōu)，而另外兩種算法都陷入了局部最優(yōu)。

所以，根據(jù)以上對(duì)比可知，基本教學(xué)算法（TLBO）和量子行為粒子群算法（QPSO）容易陷入局部最優(yōu)，并且在迭代次數(shù)一定的情況下，不一定能夠找到最優(yōu)解，甚至是次優(yōu)解；而自適應(yīng)交叉教學(xué)算法（ACTLBO）能夠很快地收斂，雖然也會(huì)陷入局部最優(yōu)，但是由于算法中加入了擾動(dòng)，它仍有一定的概率跳出局部最優(yōu)，進(jìn)而向全局最優(yōu)移動(dòng)。

5結(jié)語

本文在傳統(tǒng)教學(xué)優(yōu)化算法的基礎(chǔ)上引入了交叉過程和擾動(dòng)過程，提出了自適應(yīng)交叉教學(xué)優(yōu)化算法。通過對(duì)無人機(jī)航路規(guī)劃中存在的威脅進(jìn)行分析建模，分別用傳統(tǒng)教學(xué)優(yōu)化算法、自適應(yīng)交叉教學(xué)優(yōu)化算法和量子粒子群優(yōu)化算法進(jìn)行規(guī)劃，仿真實(shí)驗(yàn)結(jié)果表明，自適應(yīng)交叉教學(xué)優(yōu)化算法不僅提高了原算法的收斂速度，而且有效避免了原算法易陷入局部最優(yōu)的不足，可以用來解決無人機(jī)的航路規(guī)劃問題，后續(xù)工作是將規(guī)劃模型和算法擴(kuò)展到三維空間，以更好地應(yīng)用于無人機(jī)系統(tǒng)中。

參考文獻(xiàn)：

[1]

席慶彪，蘇鵬，劉慧霞.基于A*算法的無人機(jī)航路規(guī)劃算法[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]

占偉偉，王偉，陳能成，等. 一種利用改進(jìn)A*算法的無人機(jī)航跡規(guī)劃[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），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ī)航路規(guī)劃優(yōu)化研究[J].計(jì)算機(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ìn)蟻群算法的多無人機(jī)航路規(guī)劃研究[J].計(jì)算機(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]

高曼，劉以安，張強(qiáng).優(yōu)化蟻群算法在反艦導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，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.）