一種基于遺傳模擬退火算法的航跡優化方法

楊曉龍，曲東才

(海軍航空工程學院 a.研究生管理大隊;b.控制工程系，山東 煙臺 264001)

飛機地形跟蹤飛行過程中由于飛行航路方向固定、飛越山頂時暴露時間過長，易被敵方發現和跟蹤。地形回避(terrain avoidance，TA)是在保持飛機飛行高度不變的基礎上，通過飛機橫向機動來繞過地形障礙的一種超低空飛行技術［1］，它可以在保證飛行安全的前提下，進一步改善飛機的飛行隱蔽性，提高飛機執行低空突防任務的成功率。

本文主要對飛機地形回避的航跡規劃進行研究，首先對地形障礙進行分類和建模，然后依據飛機地形回避的實際約束條件，利用改進狄克斯特拉算法進行初始航路規劃，在保證飛行安全的基礎上，運用遺傳模擬退火算法對航路進行優化，尋找到整體航程最短的航路。

1 障礙空間建模

航跡規劃是指在特定約束條件下，尋找運動體從初始點到目標點滿足某種性能指標最優的運動軌跡，它是飛機進行地形回避飛行過程中的一個關鍵環節，是飛機成功實現低空突防的基礎［4］。

地形障礙是飛機低空飛行的主要威脅來源，也是航跡規劃中需要避開的主要障礙物。所以在飛機進行地形回避飛行過程中要首先對地形障礙進行建模分析，盡可能地保持模型的真實性和可靠性。

1.1 地形障礙建模

實際地形多種多樣，要用一個統一的模型來表示各種地形往往比較困難?？紤]海拔高度是地形的最直接的表述參數之一，而對于地形回避而言，由于飛行高度一定，海拔高度大于其飛行高度的地形均是威脅部分。

對地形進行采樣后，選取出飛行障礙點集，并對其中各個采樣點所屬障礙的類別進行判定。因為同一個障礙的采樣點間距緊湊，所以采用k均值聚類分析算法，對采樣點集進行分類。k均值聚類算法是一種動態聚類法，該算法的基本思想為:隨機選取k個初始聚類中心，按最小距離的原則將各個采樣點分配到k類中的某一類，然后不斷地循環計算類心、調整各采樣點的類別，最終使得各采樣點到其類心距離的平方和最?。?］。

通過k均值算法分類后，對同一類地形采樣點進行統一考慮，建立地形模型。因為地形障礙邊界的不確定性，為了同時滿足對模型的精確性和統一表述的要求，只能采取折中的辦法建立近似的模型，其方法為:用一個圓形模型來近似代替一個地形障礙，其中，每個類別的類心為圓心，取該類中所有樣本點與類心距離的最大值為半徑。這樣圓心參數顯示障礙的位置，而圓半徑則反映出障礙的大小。圖1所示的是在k均值聚類方法的基礎上2個地形障礙的建模過程。

圖1 地形障礙建模過程示意圖

圖1中，通過k均值聚類算法，將采樣點分成2類，分別用圓形點和方形點表示，以類心(cx1，cy1)、(cx2，cy2)為圓心，采樣點到類心距離的最大值r1、r2為半徑，建立了地形障礙的近似模型。

1.2 建立可行節點空間

可行節點是指飛機可以安全飛行的節點，顯然，在威脅空間里擁有無窮多個可行節點，為了降低算法的復雜度，縮短算法運行時間，需要減少可行節點的數量。本文進行初始航跡規劃時選取障礙圓心之間的連線的中點和障礙圓心到地圖邊界連線的中點為可行節點。這樣選取可行節點可以將飛機飛行過程中相對于臨近的障礙威脅的危險系數降到最小。

檢驗每個可行節點的合法性，計算可行節點到每個障礙圓心的距離與其半徑的差值Dij，判斷該可行節點是否處于障礙模型內部，即

式中:i=1，2，…，n;j=1，2，…，k;Dij表示第 i個可行節點到第j個障礙圓心的距離與其半徑的差值。

向量 Di=［Di1，Di2，…，Dij，…］，如果 Di中存在小于或等于0的元素，則可行節點i是不合法的，反之則為合法的可行節點。

建立可行節點空間后，2個可行節點之間的連線就構成了一段飛行航跡，給每段航跡賦權值，由可行節點為頂點，節點之間相互連接構成一個賦權圖。Costij表示從可行節點i到可行節點j之間連線的代價函數。

并不是任何2個可行節點之間都有連線，這是因為2個可行節點的連線可能穿過某一障礙，此時該連線的代價函數的值為無窮大，如果飛機沿此航路飛行就會發生撞地的危險。

因此取代價函數的表達式

其中，sij表示可行節點i與j之間航路的長度;表示可行節點i與j之間航路到第k個障礙圓心的距離的，eij=min(-rk)，如果eij＞0則說明該航路合法，反之則不合法。由代價函數的表達式可以看出，代價函數與航路長度近似成正比，與航路的威脅系數近似成反比。

2 初始航跡規劃

當障礙空間建模完成之后，就可以利用尋優算法搜索累計代價函數值最小的最優航跡。狄克斯特拉算法是一種典型的單源最短路徑尋優算法，算法的基本思想是將賦權圖中的頂點分為2組，第1組S存放已經確定最短路徑的節點，第2組V存放未確定的節點。算法循環過程中按最短路徑長度遞增的順序將V中的節點逐個移至S中，當終點被從V中移至 S 中時，算法循環結束［4，6］。

針對地形回避問題的特殊情況，對狄克斯特拉算法進行改進，加入航路最短距離smin和最大轉彎角φ兩個約束條件，保證規劃出的航路能夠滿足飛機飛行條件。

改進狄克斯特拉算法流程:

1)初始化節點集S、V，將初始點p0放到S組，其余可行節點和終點pend放到V組，利用賦權圖建立可行節點之間的鄰接矩陣，初始化可行節點到初始點的最短路徑d(v0i)(k=0)，(i=1，2，…，n)，k表示循環次數，如果初始點到可行節點有連接線段，則對應值為線段的權值，反之取極大值。

2)選擇d(v0i)(k)中最小值d(v0j)(k)將節點j從點集V中移到點集S中。

3)根據節點j的鄰接矩陣更新數據d(v0i)(k+1)。設ηj為以節點j為末端點的航路線段向量，ηji表示以j為起點，未確定節點i為結點的航路向量，則對于航路j→i的2個約束條件可表示為

滿足式(3)則航路滿足最小距離約束，滿足式(4)，則航路滿足最大轉彎角約束，此時新的最短路徑依照式(5)更新，否則不更新。

式(5)中，d(vji)是點集V中剩余節點到節點j的路徑，如果剩余節點與j有連接線段，則對應值為線段的權值，反之取極大值。

4)重復第二和第三步，直到終點pend移到點集S中，此時d(v0n)(k)為初始點到終點的最短路徑。

3 基于遺傳模擬退火算法的航跡優化

初始航跡規劃中的可行節點為連接線的中點，因此不是整個規劃空間的最優航跡，利用遺傳算法對規劃初始航跡進行調整，讓各航跡節點在相應的障礙端點連接線上滑動，得到新的航跡節點，根據新的航跡點進行規劃，得到最優航跡。

遺傳算法由于不受搜索空間限制性假設約束，不要求優化函數具備隱含并行性、連續、可導等假設，對于航跡規劃這種含有大量模糊信息、多約束的優化問題來說，具有特別重要的意義。模擬退火算法模擬固體退火的溫度參數T，在判斷是否接受新解時依據Metropolis接受準則，既接受好的新解，同時按一定的概率對惡化解也接受，通過這樣的判斷，有效地避免了很多優化算法容易陷入局部極值和過早收斂的問題。

正是利用了模擬退火算法的優點，與遺傳算法相結合，設計一種遺傳模擬退火算法，在遺傳算法的交叉和變異操作中引入Metropolis接受準則，避免了遺傳算法陷入局部極值的問題。

3.1 基因編碼方式

遺傳算法首先需要確定基因編碼方式，用以表達需要解決的問題?；虻木幋a方法除了決定個體基因染色體排列形式外，還決定了個體從搜索空間基因型變換到解空間表現型時的解碼方法。

航跡規劃中基因編碼通常經緯度坐標系法，而單純的經緯度坐標系法不能全面反映飛行器當前狀態。因此，本文設計了一種動態鏈表染色體編碼方案，它能減少航跡規劃時重復計算量，提高了內存空間的利用效率，簡化了插入和刪除節點操作，其鏈表格式如圖2所示。

圖2 神經網絡染色體結構

圖2中Nn為航跡節點，Nni表示航跡節點的基因，其值如表1所示。這種基因編碼方式雖然增加了計算機物理內存，但是減少了重復計算量，同時，便于實時提取飛行器航跡相關信息，在不用解碼的情況下，就可以直接計算參考航跡的代價函數值，更接近問題的原始形式，表達式更有效，更能夠生成好的解。

表1 基因編碼在航跡中的物理意義

3.2 適應度函數

在遺傳算法航跡規劃中，適應度是評價航跡優劣的唯一標準。個體適應度評價函數，直接影響遺傳算法的計算效率和計算時間。它通過威脅源、航跡距離、安全高度和約束違背量等評價因素指標，評定滿足初始點到目標點的可行航跡。從本質上講，航跡規劃的目標就是使航跡的適應度更優。

對于地形回避系統，可行航跡的飛行高度一致，對威脅都已進行有效回避，只需考慮航跡總航程即可，因此可以取適應度函數f(n)為航跡總航程。

3.3 遺傳操作算子

遺傳操作算子是遺傳算法具備強大搜索能力的核心，是調整和控制進化過程的基本工具。在航跡規劃中，由于算法特殊的基因編碼方式，遺傳操作算子需要進行改進以滿足其實現航跡規劃任務。為此對遺傳算子進行的特殊處理，將其應用于航跡節點，從而生成更好的航跡路徑。

1)選擇算子。選擇運算使用比例選擇算子，是利用比例于各個個體適應度的概率來確定子孫被選擇的可能性，設種群數量為M，個體i的適應度為fi，則個體i被選中的概率為

個體的概率給定以后，隨機產生［0，1］之間的隨機數，如果個體的選擇概率大于此數則被選中，小于此數則被淘汰，從而那些高適配值個體被選中的概率就大，低適配值個體就容易被淘汰。

2)交叉算子。將2條航跡重新組合，生成新的航跡。交叉運算采用單點交叉算子，只有一個交叉點。生成2個新的子代個體可以可行，也可以不可行，且航跡節點數可以不相同。交叉概率pc一般選為0.25～1。

3)擾動算子。對航跡節點中的一個節點坐標隨機進行改變，使其沿著相應障礙的端點連線進行滑動，得到新的航跡。

3.4 算法描述

遺傳模擬退火算法航跡規劃的基本步驟如下:

1)設定種群的規模M，最大遺傳操作代數為N，初始溫度T=T0，溫度更新次數l=0，設定溫度變化按照 Tl+i=0.9Tl，設定終止溫度 Te;

2)生成初始種群Pl(k)，k=0;

3)計算種群Pl(k)中的每個染色體的適應度函數，按照適應度的大小根據比例算子選出M個染色體組成新種群Pls(k+1);

4)將新種群Pls(k+1)中染色體按照傳統方法進行交叉操作得新種群Plcl(k+1)，設種群Pls(k+1)中個體i和個體j進行了交叉得到種群Plcl(k+1)中個體i'和個體j'，交叉前2個個體i和j的適應值分別為f(i)和f(j)，交叉操作后2個個體i'和個體 j'的適應值分別為 f(i')和 f(j')，按照下式Metropolis接受準則經過若干次的迭代得到新種群Plc(k+1)

5)變異操作與交叉操作類似，將Plc(k+1)變異得到Plm1(k+1)，然后對變異后的各個個體依據式(9)得到新的種群Plm(k+1)

式(9)中i和i'分別表示變異前和變異后的個體，適應值為f(i)和 f(i')。

6)將Plm(k+1)賦給Pl(k)，同時k=k+1。判斷k是否小于N，如果是則轉至第7步，否則轉至第4步。

7)更新溫度 Tl+i=0.9Tl，l=l+1，并且更新種群Pl+1(k)=Pl(k)。如果滿足停止準則，則停止計算輸出最優解;否則轉至第4步。

4 實例仿真

對本文提出的航跡優化方案進行驗證，構建一個3000 m2區域的數字地圖［7］，在高度為300 m的基準平面內進行地形回避航路規劃。

首先構建基準平面圖，如圖3所示。在此基礎上，對平面圖中的4個地形障礙運用k均值算法聚類建模，建立障礙空間模型。如圖4所示。

設置飛行起點為p0=(200，2800)、飛行終點為pend=(2800，200)，進行初始航跡規劃，得到初始航路圖。在初始航跡的基礎上，運用遺傳模擬退火算法對航跡進行優化，設種群大小為50，以航跡的總航程為適應度值對航路進行優化，循環迭代100次后，得到航跡曲線如圖5中，圖5中實線所示初始航跡，虛線表示優化航跡，圖6將規劃的航跡還原到數字地圖中，遺傳模擬退火算法的適應度值變化曲線如圖7所示。

圖3 基準平面

圖4 k均值算法聚類建模

圖5 優化航跡曲線

圖6 優化航跡3D示意圖

圖7 適應度值變化曲線

5 結束語

本文對飛機地形回避飛行進行航路規劃研究，通過k均值算法實現了對地形障礙采用點的聚類，并在此基礎上完成了對地形障礙空間的統一建模，通過狄克斯特拉算法完成了對飛行航跡的初始規劃，然后在此基礎上運用將模擬退火算法用于遺傳算法實現了對航跡的優化，仿真結果顯示經過優化后的航跡在保證航路安全的基礎上，縮短了整個航路的航程，達到了優化的目的，證明了本文提出的方案的可行性和合理性。

［1］閔昌萬，袁建平.軍用飛行器航跡規劃綜述［J］.飛行力學，1998，19(2)：13-18.

［2］沈春林，徐克虎，賀也平.低空突防中的若干關鍵技術［J］.南京航空航天大學學報，2003(3)：134-139.

［3］范洪達，馬向玲，葉文.飛機低空突防航路規劃技術［M］.北京：國防工業出版社，2007：7-8，105-107.

［4］黃明.武裝直升機航跡規劃與軌跡控制研究［D］.南京：南京航空航天大學，2004：12-16.

［5］孫即祥.現代模式識別［M］.長沙：國防科技大學出版社，2002：30-32.

［6］項林斌，秦碩，黃學宇，等.一種無源自動地形跟隨系統的設計［J］.彈箭與制導學報，2005，25(2)：635-639.

［7］StephanWei，Markus Achtelik，Laurent Kneip.Intuitive 3D Maps for MAV Terrain Explorationand Obstacle Avoidance［J］.J Intell Robot Syst，2011(61)：473 – 493.

［8］王美仙，李明，張子軍.飛行器控制律設計方法發展綜述［J］.飛行力學，2007，25(2)：1-5.

［9］Sterens B L，Lewis F L.Aircraft Control and Simulation［M］.New York：John Wiley and Sons INC.，1992：175-240.

［10］辛貴州.無人飛行器航跡規劃算法研究［D］.哈爾濱：哈爾濱工程大學，2010：48-50.