多約束隨機進化因子的蟻群算法求解航跡規(guī)劃

詹棠森，熊 峰，薛廣富，趙世棟，施明勇，湯可宗

(景德鎮(zhèn)陶瓷大學(xué)信息工程學(xué)院，333403，江西，景德鎮(zhèn))

0 引言

復(fù)雜環(huán)境下的飛行器航跡規(guī)劃是實現(xiàn)智能飛行器控制的一項關(guān)鍵技術(shù)[1]。近年來，很多學(xué)者提出了很多改進航跡規(guī)劃模型[2-4]，但這些模型容易陷入局部最優(yōu)。另外，也有學(xué)者雖然提出解決局部最優(yōu)的航線軌跡優(yōu)化問題[5-7]，但這些問題都是在平面上的軌跡上的問題。目前，很多航線軌跡問題是在多約束條件下對飛行器進行航跡規(guī)劃，往往受到地形、天氣情況等因素的影響，很難預(yù)先獲得精準(zhǔn)信息。飛行器在飛行任務(wù)時，隨著航程的增加，定位過程中的垂直誤差和水平誤差也隨之積累，若誤差沒有及時糾正，會直接影響飛行任務(wù)的成敗，文獻[8-13]提出飛行器在飛行過程中智能優(yōu)化算法，但這些智能優(yōu)化算法由于其計算量隨問題維數(shù)呈指數(shù)增長，難以在復(fù)雜環(huán)境下規(guī)劃出優(yōu)化航跡。文獻[14-18]提出基 于即時架構(gòu)的搜索算法研究，但這些算法降低了算法節(jié)點擴展的效率。文獻[19]將即時修復(fù)式構(gòu)架與SAS相結(jié)合算法(anytime repairing SAS, AR-SAS)，但沒有考慮水平誤差限及垂直誤差的相互制約作用;另外，還要考慮校正次數(shù)最少的多目標(biāo)問題。

近年來航跡規(guī)劃的傳統(tǒng)經(jīng)典算法有Dijkstra算法、模擬退火算法和人工勢場法。文獻[20]基于Voronoi圖使用Dijkstra算法求最優(yōu)航跡，文獻[21]基于可視圖上使用Dijkstra算法求最短航跡，文獻[22]同樣用Dijkstra算法在三維網(wǎng)絡(luò)上求最短航跡。諸如這些算法，對于高度差等約束就沒有進行優(yōu)化規(guī)劃。

綜上所述，本文根據(jù)各種算法的缺陷去改進，在多約束條件情況下，提出多約束下隨機進化因子修正誤差的蟻群算法，通過指定的校正點進行誤差糾正后，利用信息素對飛行器的航跡進行合理的優(yōu)化，使得飛行器的航跡最短，同時以減少飛行器通過的誤差校正點。重點考慮提高算法的搜索效率和搜索精度。

1 數(shù)據(jù)處理及問題的約束

1.1 數(shù)據(jù)處理

針對文獻[22]所要求的數(shù)據(jù)集1中含有306個水平誤差校正點以及305個垂直誤差校正點和數(shù)據(jù)集2中含有167個水平誤差校正點以及158個垂直誤差校正點。飛行器在飛行過程中，每飛行1 m，垂直誤差和水平誤差將各增加0.001個單位。到達終點時，只有垂直誤差和水平誤差均小于某確定單位時，飛行器才能按照規(guī)劃路徑飛行。進行垂直誤差校正需要此時的垂直誤差不大于某確定單位，水平誤差不大于某確定單位。進行水平誤差校正需要此時的垂直誤差不大于某確定單位，水平誤差不大于某確定單位。以飛行器從出發(fā)點出發(fā)，進行誤差校正只能尋找與出發(fā)點距離小于某確定值的垂直誤差點或與發(fā)點距離小于某確定值的水平誤差點，通過計算可知，符合條件的第一個水平誤差校正點有19個點；符合條件的第一個垂直誤差校正點有7個點。到達終點時，只有垂直誤差和水平誤差均小于20個單位時，飛行器才能按照規(guī)劃路徑飛行，因此飛行器要到達終點，必須經(jīng)過距離終點B 20 000 m以內(nèi)的校正點，通過計算可知，符合距離終點B為20 000 m以內(nèi)的水平誤差校正點有20個點；符合距離終點B為20 000 m以內(nèi)的垂直誤差校正點有13個點。

同理由數(shù)據(jù)集2可知，出發(fā)點A到終點B的直線距離為：103 045.12 m。飛行器在飛行過程中，每飛行1 m，垂直誤差和水平誤差將各增加0.001個單位。進行垂直誤差校正需要此時的垂直誤差不大于20個單位，水平誤差不大于10個單位。進行水平誤差校正需要此時的垂直誤差不大于15個單位，水平誤差不大于20個單位。所以飛行器從出發(fā)點A出發(fā)，進行誤差校正只能尋找與A點距離小于10 000 m的垂直誤差點或與A點距離小于15 000 m的水平誤差點，通過計算可知，符合條件的第一個水平誤差校正點6個點；符合條件的第一個垂直誤差校正點有4個點。到達終點時，只有垂直誤差和水平誤差均小于20個單位時，飛行器才能按照規(guī)劃路徑飛行，因此飛行器要到達終點，必須經(jīng)過距離終點B 20 000 m以內(nèi)的校正點，通過計算可知，符合距離終點B 20 000 m以內(nèi)的水平誤差校正點有7個點；符合距離終點B 20 000 m以內(nèi)的垂直誤差校正點有3個點。

1.2 問題的約束

該智能飛行器的航跡約束如下。

1)飛行器在飛行過程中，每飛行1 m，垂直誤差和水平誤差將各增加δ個單位，到達終點時，假設(shè)只有垂直誤差和水平誤差均小于θ個單位時，飛行器才能按照規(guī)劃路徑飛行。

2)飛行器到達垂直校正點時能夠進行垂直的誤差校正，使得該垂直的誤差變?yōu)?，另一個類型的誤差保持不變。

3)進行垂直誤差校正需要此時的垂直誤差不大于α1個單位，水平誤差不大于α2個單位。

4)進行水平誤差校正需要此時的垂直誤差不大于β1個單位，水平誤差不大于β2個單位。

5)飛行器在轉(zhuǎn)彎時受到結(jié)構(gòu)和控制系統(tǒng)的限制，前進的方向不可以突然改變，因此設(shè)定飛行器的最小轉(zhuǎn)彎半徑為200 m。

2 多約束下隨機進化因子修正誤差的蟻群算法

數(shù)據(jù)集1和數(shù)據(jù)集2中都含有大量的定位誤差校正點，使用蟻群算法對路徑進行隨機搜索會加大程序的運算量。所以本文計劃提前篩選出滿足約束條件的第一個校正點集合F和最后一個校正點集合E。當(dāng)螞蟻從起點A出發(fā)時，只能從集合F中隨機挑選一個誤差校正點進行定位誤差的校正，隨后再進行航跡的搜索；當(dāng)螞蟻到達集合E中的校正點時，通過引入遺傳算法中的選擇運算[23]，加大終點B的個體適應(yīng)度，從而加快算法的收斂速度。算法的具體步驟如下。

第1步：確定模型的決策變量與約束條件。

1)飛行區(qū)域中的校正點(Check Point)用集合CP表示：

CP={cp1,cp2,…,cpm}(m∈Ν)

(1)

其中cpi表示飛行區(qū)域中編號為i的校正點，這里面的下標(biāo)i表示數(shù)據(jù)集1和數(shù)據(jù)集2中校正點的編號，在數(shù)據(jù)集1中，m的值為611；在數(shù)據(jù)集2中，m的值為325。

2)假設(shè)飛行器的航跡路線(flight path)由列表FP表示：

(2)

3)校正點cpi(x1,y1,z1),cpk(x2,y2,z2)的歐式空間距離：

(3)

4)校正點cpi是否被規(guī)劃到了飛行器的航跡路線中：

(4)

5)校正點cpi的類型Type(cpi)：

(5)

(6)

(7)

(8)

(9)

8)若Type(cpk)=0，判斷飛行器是否能到達校正點cpk進行誤差校正：

(10)

其中1表示飛行器是能到達校正點cpk進行誤差校正，0表示不能。

9)若Type(cpk)=1，判斷飛行器是否能從校正點cpi到達校正點cpk進行誤差校正

(11)

其中1表示飛行器是能到達校正點cpk進行誤差校正，0表示不能。

10)判斷飛行器是否能從校正點cpi到達終點B：

(12)

第2步：確定蟻群算法模型的信息素更新條件。

設(shè)信息素初始分布矩陣為：

τcpicpk(0)=3

(13)

DAB是起點A到終點B的歐式距離，m是飛行區(qū)域中校正點的數(shù)量。

為了避免殘留的信息素過多所導(dǎo)致的啟發(fā)信息被覆蓋[6]，需要令每一只螞蟻走到下一個節(jié)點或成功到達終點時對殘留的信息素進行更新。t時刻在校正點cpicpk之間的殘留信息更新方程如下：

τcpicpk(t)=(1-ρ)*ττcpicpk(t)+△ττcpicpk

(14)

(15)

判斷出現(xiàn)新的路徑是否能更新Ccpicpk和DTcpicpk：

(16)

算法中螞蟻選擇下一個誤差校正點cpk的概率公式為：

(17)

按照遺傳算法的選擇策略求得的路徑選擇概率。

(18)

如果2個校正點中有新的路徑產(chǎn)生，則計算該條新路徑的校正點數(shù)量以及路徑長度，由此來決定是否加強該路徑的信息素濃度：

(19)

(20)

G為信息素加強的系數(shù)等于5 000。

第3步：確定圓弧上符合條件的F點坐標(biāo)，以及求出圓弧arc(EF)的長度。

由于飛行器在轉(zhuǎn)彎時受到結(jié)構(gòu)和控制系統(tǒng)的限制，前進的方向不可以突然改變，并設(shè)定飛行器的最小轉(zhuǎn)彎半徑R。這樣就不能繼續(xù)使用二點的歐式距離來定義2個誤差校正點的路程，需要計算飛行器到達第一個校正點的入射向量，通過下一個校正點的坐標(biāo)確定一個平面，同時計算出該平面中與入射向量垂直的向量，并在該垂直向量上找到一個與入射點距離為200的點作為圓心，得出半徑為200的圓。飛行路徑如圖1所示：假設(shè)飛行器從點D直線到達下一個校正點E,則校正點E到下一個校正點C的運動軌跡為先以半徑200 m圓弧飛行，直到下一個校正點C出現(xiàn)在飛行器航行方向的直線上時，才開始走直線直接到達下一個校正點C。所以需要尋找圓弧上符合條件的F點坐標(biāo)，該點與下一個校正點構(gòu)成的直線會相切于圓，并且用于計算到達下一個誤差校正點C的入射向量。

圖1 飛行器從E點到C點的平面航線示意圖

(21)

(22)

因為E到圓心O的距離為r=200，所以聯(lián)立式(21)和(22)可得出圓心O的坐標(biāo)求解如下：

(23)

則圓心O點的坐標(biāo)通過計算可以表示為：

(24)

(25)

求∠FOC的角度β：

(26)

則∝ = 180-θ-β，參照圓心O的求解思路，可求出G點與F點的坐標(biāo)：

(27)

(28)

所以EF的圓弧長度arc(EF)計算公式為：

(29)

(30)

第4步：確定模型的目標(biāo)函數(shù)。

由題可知該模型的目標(biāo)如下。目標(biāo)1：盡可能地使飛行器的航跡長度達到最??；目標(biāo)2：飛行器經(jīng)過校正點的數(shù)量盡可能少。

由此可知，該問題是一個多目標(biāo)優(yōu)化的問題，所以在獲得了可行解后，需要對得出的路徑進行分析篩選，得出比較好的解決方案。

若通過模型得出的可行路線規(guī)劃為集合Result:

Result={FP1,FP2,…,FPl}

(31)

(32)

C(FPi)=len(FPi)-2

(33)

其中l(wèi)en(FPi)為求該列表元素數(shù)量的函數(shù)，由于只需要計算經(jīng)過校正點的數(shù)量，所以需要減去起點和終點。

每種航跡路線的累計路程為：

(34)

目標(biāo)函數(shù)：

min(CAB)

(35)

min(DT(FPi))

(36)

約束條件：

Hcpk≤α1且Vcpk≤α2

(37)

Hcpk≤β1且Vcpk≤β2

(38)

(39)

(40)

加入轉(zhuǎn)彎半徑作為新的約束條件，即下一個校正點cpk與飛行器沿圓弧航行的圓心O(x0,y0,z0)的歐式距離需要大于200。

D(cpk,0)≥200

(41)

3 數(shù)據(jù)仿真

結(jié)合遺傳算法中的自然選擇策略來改進蟻群算法，通過信息素的濃度來分派每個校正點的適應(yīng)度，在此基礎(chǔ)上加入剪枝策略，預(yù)先篩選出符合要求的第一個校正點，從而降低尋優(yōu)過程中的網(wǎng)絡(luò)維數(shù)，加快收斂速度。同時增加處于終點附近的校正點選擇終點B作為下一個節(jié)點的概率，在數(shù)據(jù)集1和數(shù)據(jù)集2中，本文設(shè)定模型的參數(shù)如下：

α=1,β=1,ρ=0.5,τcpicpk(0)=3,G=5 000

(42)

其中最大迭代次數(shù)設(shè)定為10 000，螞蟻的數(shù)量為100 000個。運行得出的結(jié)果如下。

3.1 數(shù)據(jù)集1的運行結(jié)果

經(jīng)過計算得出，航跡路線中的校正點數(shù)量最少為8個，按航行路程從小到大排序的航跡規(guī)劃如表1所示，由于模型得出可行解比較多，所以只挑選出前10中的航跡規(guī)劃。

表1 數(shù)據(jù)集1的航跡規(guī)劃表

由表1可知，飛行器通過誤差校正點的數(shù)量最少為8個，其中最短的航跡路程為105 205.858 7 m。

表1中序號為1的航跡規(guī)劃示意圖如圖2及航跡規(guī)劃結(jié)果如表2所示。

表2 校正點最少且航行路程最小的航跡規(guī)劃結(jié)果表

圖2 校正點最少且航程最短的航跡示意圖

3.2 數(shù)據(jù)集2的運行結(jié)果

在飛行器經(jīng)過校正點數(shù)量最少的情況下，按航行路程從小到大排序的航跡規(guī)劃如表3所示。

表3 數(shù)據(jù)集2中校正點數(shù)量最少的航跡規(guī)劃表

由表3可知，數(shù)據(jù)集2中校正點數(shù)量最少且路徑最短的航線規(guī)劃為：

[A,275,104,128,227,305,309,121,123,45,160,92,93,61,B]。

飛行器通過誤差校正點的數(shù)量最少為12個，其中最短的航跡路程為115 471.921 9 m。表3中序號為1的航跡規(guī)劃如圖3及航跡規(guī)劃結(jié)果如表4所示。

表4 航行路程最小且校正點最少的航跡規(guī)劃結(jié)果表

圖3 航行路程最小且校正點最少的航跡示意圖

3.3 結(jié)果分析

數(shù)據(jù)集1中不考慮飛行器在轉(zhuǎn)彎半徑約束，航線的航程為104 526.940 7 m，一共經(jīng)過10個校正點。數(shù)據(jù)集2中不考慮飛行器在轉(zhuǎn)彎半徑時，飛行器通過誤差校正點的數(shù)量為12個，其中航跡路程為104 526.940 7 m。數(shù)據(jù)集1中考慮飛行器在轉(zhuǎn)彎半徑時，航線的航程為105 205.858 7 m，一共經(jīng)過8個校正點。數(shù)據(jù)集2中考慮飛行器在轉(zhuǎn)彎半徑時，飛行器通過誤差校正點的數(shù)量為13個，其中航跡路程為115 471.921 9 m。

因為考慮飛行器在轉(zhuǎn)彎半徑約束，使得在尋找下一個誤差校正點時，除了需要考慮到達該點時的水平和垂直誤差是否超過閾值，還要考慮下一個校正點是否處于飛機的最小轉(zhuǎn)彎半徑范圍內(nèi)。通過計算飛行器到達每一個校正點的入射角，來確定符合飛機最小轉(zhuǎn)彎半徑的圓心坐標(biāo)，從而求出飛行器在繞圓心航行中脫離圓弧的坐標(biāo)。由此來計算出飛行器繞圓心航行的圓弧長度和脫離圓弧時到達下一個點的歐式距離，用來定義飛行器轉(zhuǎn)彎性能受到限制的情況下，到達下一個校正點的航程。

4 總結(jié)

為了解決蟻群算法容易陷入局部最優(yōu)解且收斂速度慢的特點，結(jié)合了遺傳算法中的自然選擇策略來改進的蟻群算法，通過改變節(jié)點的適應(yīng)度大小對各節(jié)點的信息素進行更新，同時更新2個校正點之間的最短路徑的路程和中間節(jié)點數(shù)量，用此來刪除Allowed表中較差的路徑，從而加快算法的收斂速度。此外，還引入隨機因子來解決陷入局部最優(yōu)解問題。在進行求解前，通過剪枝使得第一個校正點和最后一個校正點的數(shù)量大幅度減少，同時引入的隨機進化因子急速地加快了算法的收斂速度。信息素的二次加強為算法尋找最優(yōu)路徑提供方向，在尋找最優(yōu)解和搜索速度上相互平衡，能夠得到一個又快又好的解。通過對模型求解出結(jié)果進行分析，進一步地驗證了模型的準(zhǔn)確性，能夠快速地解出符合約束條件的航跡路線，同時與起點A和終點B的直線距離相比，模型得出的航跡路程已經(jīng)很逼近直線距離。同時模型對于蟻群算法中各個參數(shù)的初始設(shè)定依賴于別人模型的經(jīng)驗，需要在今后多測試幾組參數(shù)，盡可能地加快模型的收斂速度，同時能夠較準(zhǔn)確地得出最優(yōu)解。結(jié)合遺傳算法中的自然選擇策略來改進蟻群算法，通過信息素的濃度來分派每個校正點的適應(yīng)度，在此基礎(chǔ)上加入剪枝策略，由于剪枝策略的引入，在刪除路徑時容易錯過最優(yōu)解，且更新一些路徑時，會導(dǎo)致飛行器無法到達下一個誤差校正點，所以需要更新剪枝的約束條件，讓模型在減少節(jié)點數(shù)量的同時，又不會錯過最佳的路徑選擇。