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

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

(景德鎮陶瓷大學信息工程學院，333403，江西，景德鎮)

0 引言

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

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

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

1 數據處理及問題的約束

1.1 數據處理

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

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

1.2 問題的約束

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

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

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

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

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

5)飛行器在轉彎時受到結構和控制系統的限制，前進的方向不可以突然改變，因此設定飛行器的最小轉彎半徑為200 m。

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

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

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

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

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

(1)

其中cpi表示飛行區域中編號為i的校正點，這里面的下標i表示數據集1和數據集2中校正點的編號，在數據集1中，m的值為611；在數據集2中，m的值為325。

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

(2)

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

(3)

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

(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步：確定蟻群算法模型的信息素更新條件。

設信息素初始分布矩陣為：

τcpicpk(0)=3

(13)

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

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

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

(14)

(15)

判斷出現新的路徑是否能更新Ccpicpk和DTcpicpk：

(16)

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

(17)

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

(18)

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

(19)

(20)

G為信息素加強的系數等于5 000。

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

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

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

(21)

(22)

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

(23)

則圓心O點的坐標通過計算可以表示為：

(24)

(25)

求∠FOC的角度β：

(26)

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

(27)

(28)

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

(29)

(30)

第4步：確定模型的目標函數。

由題可知該模型的目標如下。目標1：盡可能地使飛行器的航跡長度達到最小；目標2：飛行器經過校正點的數量盡可能少。

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

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

Result={FP1,FP2,…,FPl}

(31)

(32)

C(FPi)=len(FPi)-2

(33)

其中len(FPi)為求該列表元素數量的函數，由于只需要計算經過校正點的數量，所以需要減去起點和終點。

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

(34)

目標函數：

min(CAB)

(35)

min(DT(FPi))

(36)

約束條件：

Hcpk≤α1且Vcpk≤α2

(37)

Hcpk≤β1且Vcpk≤β2

(38)

(39)

(40)

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

D(cpk,0)≥200

(41)

3 數據仿真

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

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

(42)

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

3.1 數據集1的運行結果

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

表1 數據集1的航跡規劃表

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

表1中序號為1的航跡規劃示意圖如圖2及航跡規劃結果如表2所示。

表2 校正點最少且航行路程最小的航跡規劃結果表

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

3.2 數據集2的運行結果

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

表3 數據集2中校正點數量最少的航跡規劃表

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

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

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

表4 航行路程最小且校正點最少的航跡規劃結果表

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

3.3 結果分析

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

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

4 總結

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