基于量子遺傳算法的無人機沖突解脫方法

甄 然，王 攀，武曉晶，吳學禮*

(1.河北科技大學電氣工程學院，石家莊 050018；2.河北省生產過程自動化工程技術研究中心，石家莊 050018)

隨著科技的日益發展，無人機的應用越來越廣泛,致使空域變得越來越擁堵,導致無人機飛行沖突易發、空域資源緊張等，嚴重影響了無人機飛行安全和可行性。無人機飛行數量的增加和飛行路線的多向性也增加了飛行沖突的可能性，因此，無人機沖突解脫問題的研究變得異常重要。多年來各國學者對飛行沖突解脫進行了各種各樣的研究，Alonso-Ayuso等[1]提出了一種混合整數線性優化模型，采用近似序列混合整數線性優化方法來解決飛行沖突解脫問題。Lehouillier等[2]利用一種最小權最大集團模型的新形式來解決飛行沖突，通過引入兩個分解算法，可在較短時間內獲得飛行機動集合最優解。Vela等[3]構建了一種優化模型來避免飛機沖突，并考慮了燃油成本因素，使其成本最小。Yang等[4]提出了一種無人機的雙層沖突探測與解脫機制，并采用了航向變化和速度變化混合的沖突解脫方法，能夠較好地處理復雜情況，降低額外成本。Emmanuel等[5]建立了一種三維沖突計數模型來分析非結構化空域和分層空域設計的安全性，其對兩種空域設計的瞬時沖突計數都有較高的估計精度。梁曼等[6]提出一種改進的案例檢索方法，提高推理速度，從而更好地實現飛行沖突智能解脫。黃洋等[7]利用復雜網絡快速同步修改無人機軌跡，從而達到沖突解脫避險的目的。楊新湦等[8]通過劃分興趣區，分析管制員在沖突解脫時的眼動行為，提高進行管制飛行沖突的效率，但是其沒有對解脫航跡優化方面進行分析研究。文獻[9]將A*算法應用到飛行沖突解脫中，文獻[10]和文獻[11]分別基于合作博弈和改進蟻群算法來解決沖突解脫問題，均取得不錯的效果，但他們都沒有考慮和優化整體解脫過程中的航向轉彎次數，這關系到整體的飛行成本。文獻[12]使用蒙特卡洛法，仿真了無人機飛行沖突過程，較明顯地減小了事故率，但其沒有在算法的求解時間方面進行比較分析。

在綜合以上研究的基礎上，充分考慮研究了解脫航跡優化、求解時間、航向轉彎次數、總延誤距離等方面，提出了一種基于量子遺傳算法的無人機沖突解脫方法。首先建立沖突解脫模型，然后確定適應度函數，設計并加入延誤指數函數強制優化策略和變航向優化策略，利用量子遺傳算法求解得出最優的解脫航跡，通過MATLAB仿真，驗證其有效性，以期達到比遺傳算法更好的解脫航跡、更小延誤距離等效果。

1 無人機沖突解脫問題的描述與建模

根據國家空中交通管制的安全規定和無人機實際飛行情況，對無人機的沖突解脫問題進行了合理簡化。

(1)考慮到無人機在實際飛行時，除了起飛和降落期間外，其他階段都是在固定的高度飛行，且考慮到無人機的油耗等要求，把無人機的沖突解脫問題簡化為二維平面進行研究。

(2)無人機在實際巡航飛行過程中，其速度沒有較大變化，所以假設無人機的速度大小不變。

(3)根據國家的空中交通管制規定，兩架飛行器之間的安全間隔至少為20 km，所以設定兩架飛機間的距離需大于20 km作為約束條件，無人機的飛行步長定為10 km[13]。

(4)假設無人機在進行航向調整時，只能進行3種航向調整：保持原飛行航向、左轉30°、右轉30°。

圖1 原計劃航跡Fig.1 Original planning tracks

假設兩架無人機以相同速度且保持不變同時進入一個200 km×200 km的正方形區域里，無人機如果按圖1所示的無航跡調整的原計劃航跡飛行時，兩機將在正方形的幾何中心點發生碰撞，過程中每架無人機每飛行一個步長取一個航跡節點，即每架無人機在整個區域飛行了20個步長，其在正方形區域的總飛行時間也分為了20步。其中無人機的飛行步長可理解為檢測頻率，無人機每飛行一個步長就被檢測一回，判斷是否發生沖突。無人機在每一個步長飛行時，保持飛行的航向和速度。在進入每一個步長時，無人機進行航向調整，從而防止沖突發生。

約束條件設定為兩架無人機之間的距離D大于飛行安全距離20 km[14]，即

(1)

對于每架無人機根據其進入正方形空域入口點、開始航向、每一個航跡節點的位置坐標和航向變化等方面，計算分析整個航跡，并分析是否有沖突情況。一旦在任何一節點發現沖突情況，那么包含這條航跡的個體適應度值將被設置為0。

無人機飛行沖突的出現會迫使無人機進行航跡調整，從而不可避免地造成脫離原計劃航跡的情況，產生飛行延誤，使無人機從出發地到目的地的飛行距離增加，實際飛行時間相比無沖突時的原計劃航行時間增加，無人機的能耗也因此增加，從飛行時間、經濟成本等方面考慮，在保證無人機間無沖突的前提下，優化目標為使無人機實際飛行解脫航跡相比原計劃航跡的總延誤距離最小(此處的總延誤距離指兩架飛機的延誤距離之和，每架無人機延誤距離定義為從第一個航跡節點到第20個航跡節點沖突解脫結束時，實際解脫航跡節點與原計劃航跡節點的直線距離之和。)則沖突解脫問題的目標函數為

(2)

根據要優化的目標設定了適應度函數，適應度值越大，最終的解質量越好。適應度函數為

(3)

式(3)中：k1為常數。

在染色體的編碼環節涉及了二進制編碼，用N表示空域中的無人機數量，I為各無人機在區域內的總飛行步長。構建了一個N×I×2的解空間，將每個染色體對應的解空間分解成N個I維向量：Xn=(xn1,xn2,…，xnI)(i=1,2,…,I)，其指第n架無人機在區域內的航向調整。其中：xni=10表示第n架無人機在第i步時左偏30°；xni=01表示第n架無人機在第i步時右偏30°；xni=00或11時表示第n架無人機在第i步時保持直行[15]。

根據所設計的兩架無人機的沖突解脫模型，設定無人機數目N=2，每架無人機總飛行步長I=20。

2 算法原理

2.1 量子遺傳算法

量子遺傳算法是在標準遺傳算法的基礎上，結合量子計算而生成的一種改進的遺傳算法，其編碼方式獨特，在傳統的遺傳編碼中加入了量子態，使染色體中的基因既可以為0態，也可以為1態，或是兩者的隨機疊加態。因此，每條染色體可以呈現多種態的疊加。然后利用量子旋轉門來實現種群中個體的更新和演化。與標準遺傳算法相比，量子遺傳算法能夠獲得更好的種群多樣性，從而最終能求得更優的解。

2.2 量子比特表示

在量子計算機當中，作為信息存儲單元的物理介質是一個雙態量子系統，其稱作量子比特。其獨特之處是其可以處在“0”態和“1”態的疊加態中，即

|φ〉=α|0〉+β|1〉

(4)

式(4)中：α、β均為復數，表示相應狀態的概率幅[16]，|α|2、|β|2分別指處在“0”態和“1”態的概率，其滿足|α|2+|β|2=1；|0〉表示自旋向下態；|1〉表示自旋向上態[17]。

在量子遺傳算法中，染色體中的每個基因可含有一個或多個量子比特，每條染色體可由多個量子比特表達的基因組成。如一條由s個量子比特組成的染色體C可以表示為

(5)

式(5)中：|αi|2+|βi|2=1(i=1,2,…,s)，染色體C可以表示2s個狀態[18]。

2.3 量子旋轉門

量子遺傳算法的演化方式不同于標準遺傳算法的選擇、交叉、變異等操作，主要通過利用量子旋轉門進行演化操作，通過對疊加態加以作用，使疊加態之間進行相互干涉，發生相位形變，因此改變了各基態的概率幅，完成染色體的更新演化。采用如下的量子旋轉門調整操作：

(6)

量子旋轉門更新過程為

(7)

式(7)中：[α′i,β′i]T為更新后的第i個量子比特；θi為旋轉角，θi由表1的旋轉角調整策略決定。

3 基于量子遺傳算法的無人機沖突解脫

3.1 染色體編碼

(8)

式(8)中：m為一條染色體的基因數目；s為單個基因中的量子比特數目。

(9)

圖2 航跡二進制編碼示意圖Fig.2 A diagram of tracks binary coding

3.2 旋轉角選擇策略

根據本文沖突解脫的設計需求，采用了表1的旋轉角調整策略。

3.3 延誤指數函數強制優化策略

圖3 總延誤距離驟增示意圖Fig.3 A diagram of the sharp increase in total delay distance

(10)

3.4 變航向優化策略

在無人機飛行沖突解脫的過程中，航向轉彎次數也會影響整體解脫的效果。設計提出了一種變航向優化策略，約束規范航向轉彎次數，減少飛行能耗，且避免過多偏離原航線的情況，如式(11)所示。

T>k2?適應度值置0

(11)

式(11)中：T為兩架無人機的總轉彎次數；k2為允許的最大轉彎次數。k2的取值關系到解脫的效果，如果取值過小，對算法解的約束過大，會造成算法搜索不到合適的解，得不到理想的航跡，此外也有大幅度偏離原航線的可能；如果取值過大，則對轉彎約束過小，也有可能造成轉彎過多的現象。根據多次仿真驗證得出，k2在區間[12,17]內取值的效果較為理想，既防止了過度偏離原航線，又能節約飛行成本。

3.5 求解流程

(3)對這組確定解進行適應度值評價，加入延誤指數函數強制優化策略和變航向優化策略進行適應度值的篩選優化，并記錄最優個體和其適應度值, 并作為當前的目標值。

(4)判斷是否達到最大迭代次數，滿足則退出，輸出最優解，否則繼續計算。

(5)對種群再進行一次測量，得到其對應的確定解，求出其中個體的適應度值，并加入延誤指數函數強制優化策略和變航向優化策略進行優化。

(6)使用量子旋轉門調整策略進行更新演化，得到更新后的種群；記錄更新后的最優個體和其適應度值，并與當前目標值進行比較，如果大于目標值，則進行替換并作為新的目標值，否則的話保留當前的目標值。

(7)代數t加1，并返回步驟(4)。

4 仿真及驗證

分別使用本文中提出的基于量子遺傳算法的沖突解脫方法和遺傳算法在兩架無人機的沖突解脫問題上進行了仿真驗證，并在算法的適應度函數值、飛行解脫航跡與飛行總延誤距離等方面進行了分析對比。假設兩架無人機以相同的恒定速度同時進入一個200 km×200 km的一個正方形空域，各自直線飛行前往目的地，一架在(0,100)開始從正西向東飛行，一架在(100,0)開始從正南向北飛行，若不進行沖突解脫調整，則將在正方形空域幾何中心位置發生碰撞，為保證仿真對比的客觀性，仿真所用的兩種算法的種群數目均為200，迭代次數均為200代，所用適應度函數也相同。其中所用遺傳算法的交叉概率為0.7，變異概率為0.03。

4.1 適應度函數值對比

本文方法與遺傳算法得出的適應度值曲線如圖4所示，兩種算法的適應度數據對比如表2所示。

圖4 兩種算法的適應度值曲線Fig.4 Fitness value curves of the two algorithms

表2 適應度值數據對比Table 2 Data comparison of fitness value

由圖4和表2可以看出，迭代結束時，相比遺傳算法，本文方法得出的適應度值更高，則求出的解質量更好，且在較小代得到的適應度值比遺傳算法最終代的適應度值還要高。

4.2 沖突解脫航跡對比

遺傳算法與本文方法得出的解脫航跡分別如圖5和圖6所示，兩種算法沖突解脫航跡數據對比如表3所示。

圖5 基于遺傳算法的沖突解脫航跡Fig.5 Conflict resolution tracks based on GA

圖6 基于本文方法的沖突解脫航跡Fig.6 Conflict resolution tracks based on the proposed method

表3 沖突解脫航跡數據對比Table 3 Data comparison of conflict resolution tracks

由圖5、圖6和表3可以得出，使用本文方法的解脫航跡相比遺傳算法的航跡更加平滑，更加貼近于原計劃航跡，轉彎次數更少，節省飛行能耗；在解脫結束后兩架飛機距目的地的總距離相比使用遺傳算法的距離更近，從而無人機在解脫后能更快到達目的地。

4.3 總延誤距離對比

本文方法與遺傳算法得出的總延誤距離曲線如圖7所示，兩種算法總延誤距離數據的對比如表4所示。

圖7 兩種算法的總延誤距離曲線Fig.7 Total delay distance curves of two algorithms

表4 總延誤距離數據對比Table 4 Data comparison of total delay distance

由圖7和表4可以得出，本文方法求得的總延誤距離相比遺傳算法更小，實現了更小的飛行延誤，在第9代時就能達到408 km的延誤距離，比遺傳算法最終代的延誤距離還要小，即能更早地實現比遺傳算法更小的延誤。

4.4 與多種性能算法的綜合對比

不同的交叉概率pc和變異概率pm會使遺傳算法具有不同的性能和求解能力，為了更全面地進行比較，用本文方法與3種具有不同pc、pm值的遺傳算法進行對比，通過多次的仿真實驗，求出了各項主要對比數據的平均值，如表5所示。

表5 綜合數據對比Table 5 Comprehensive data comparison

從表5結果可以看出,本文方法相比不同性能的遺傳算法仍有明顯的優勢，適應度值更高，解的質量更高，求解時間較短，總延誤距離小，解脫后能更快到達目的地，轉彎次數少，節省飛行成本，在解決無人機沖突解脫問題上更有優勢。

5 結論

針對兩架無人機在空域內的飛行沖突問題，提出了一種基于量子遺傳算法的無人機沖突解脫方法。構建了沖突解脫相關的數學模型，設置了合理的適應度函數和約束條件，設計加入延誤指數函數強制優化策略和變航向優化策略在總延誤距離值、轉彎次數、適應度值等方面進行了優化，利用量子遺傳算法求出最優解，得到最優的沖突解脫航跡。通過仿真證明，本文方法有效地解決了兩架無人機的沖突解脫問題，求解時間較短，求得解的質量高，無人機在解脫后能更快到達目的地，且在適應度值、解脫航跡質量、總延誤距離等方面均優于遺傳算法。

在以后的研究中將開展以下幾方面工作：①嘗試將本文方法用于解決多架無人機的沖突解脫問題，并驗證其可行性；②考慮空域中的復雜情況，比如風力擾動的因素，提高無人機在擾動情況下的沖突解脫成功率；③增加優化目標，提高優化的全面性；④在已有二維空域飛行沖突研究的基礎上，嘗試進行無人機在三維空域的沖突解脫研究。