基于改進(jìn)啟發(fā)式蟻群算法的無人機(jī)自主航跡規(guī)劃

辛建霖，左家亮，岳龍飛，張宏宏

（空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051）

0 引 言

隨著科學(xué)技術(shù)的發(fā)展，現(xiàn)代戰(zhàn)爭信息化、智能化程度逐漸提高，使得無人機(jī)的應(yīng)用發(fā)展受到更多關(guān)注。無人機(jī)航跡規(guī)劃是無人機(jī)作戰(zhàn)應(yīng)用的關(guān)鍵環(huán)節(jié)，其目的是在滿足各種約束條件的前提下（無人機(jī)性能、飛行安全性、任務(wù)目標(biāo)等），尋找到一條最優(yōu)或較優(yōu)航跡。航跡規(guī)劃經(jīng)歷了從手動繪制到計(jì)算機(jī)自動解算兩個階段，研究內(nèi)容主要包括：地形和威脅等環(huán)境要素的表示方法分析、基于任務(wù)需求的目標(biāo)函數(shù)構(gòu)造、滿足飛行距離和轉(zhuǎn)彎半徑等限制因素的約束條件處理、針對實(shí)時性和協(xié)同性等需求的航跡搜索算法研究。現(xiàn)有的航跡規(guī)劃已可以滿足一定的應(yīng)用需求，例如，田疆等提出了一種改進(jìn)連接型快速擴(kuò)展隨機(jī)樹算法，可用于復(fù)雜環(huán)境下的無人機(jī)三維航跡規(guī)劃，但在實(shí)時性、高效性、協(xié)同航跡規(guī)劃和可替換航跡規(guī)劃等方面仍然存在一些不足。

航跡規(guī)劃算法主要分為兩大類，一類是經(jīng)典算法，如最優(yōu)控制法、動態(tài)規(guī)劃法等；另一類是智能算法，如人工勢場法、粒子群算法、遺傳算法、蟻群算法等。最優(yōu)控制法把航跡規(guī)劃問題轉(zhuǎn)化為最優(yōu)控制問題，建立最優(yōu)控制模型進(jìn)行求解，但這種方法對初始值要求較高，建模和求解較為復(fù)雜。遺傳算法模擬生物遺傳進(jìn)化過程，求解航跡規(guī)劃問題高效、魯棒性強(qiáng)，但算法容易早熟收斂，局部搜索能力較差。李涵等在殲轟機(jī)突防突擊過程中，運(yùn)用改進(jìn)的遺傳算法進(jìn)行了航線規(guī)劃，但其計(jì)算模型考慮因素較少，模型尚不完善。蟻群算法（Ant Colony Algorithm，簡稱ACO）是一種基于對螞蟻群體覓食行為的研究而提出的搜索算法，具有魯棒性好、正反饋能力強(qiáng)的優(yōu)點(diǎn)，但面對復(fù)雜問題時，容易出現(xiàn)算法停滯、陷入局部最優(yōu)、運(yùn)算時間過長等問題。為此，國內(nèi)外對ACO 算法提出了許多改進(jìn)措施。陳雄等對信息素?fù)]發(fā)系數(shù)進(jìn)行動態(tài)調(diào)整，用優(yōu)化參數(shù)的方式有效解決了算法停滯的問題，但改進(jìn)后算法不夠靈活；B. Bulln?heimer 等引入精英螞蟻策略，通過改進(jìn)算法結(jié)構(gòu)提高最優(yōu)和次優(yōu)路徑的引導(dǎo)能力，但收斂速度較慢；Wang L 等采用融合遺傳算法的方式提升ACO 算法的尋優(yōu)能力，但算法適應(yīng)性較差。

本文提出一種改進(jìn)啟發(fā)式蟻群算法（Im?proved Heuristic Ant Colony Algorithm，簡稱IHACO）的無人機(jī)自主航跡規(guī)劃算法，通過引入Dijk?stra 算法、Logistic 混沌映射、多航跡選擇策略、模擬退火機(jī)制的方法對ACO 算法進(jìn)行改進(jìn)，以提高算法初期的搜索效率，增強(qiáng)全局尋優(yōu)能力，平衡收斂速度與全局尋優(yōu)能力之間的矛盾，增強(qiáng)算法在復(fù)雜環(huán)境中的搜索性能，并對算法進(jìn)行仿真分析。

1 航跡規(guī)劃問題描述及環(huán)境建模

1.1 問題描述

針對無人機(jī)在作戰(zhàn)任務(wù)中穿越地形障礙、躲避敵方地對空導(dǎo)彈威脅的航跡規(guī)劃，簡化運(yùn)行環(huán)境并進(jìn)行如下假設(shè)：（1）簡化模型，將無人機(jī)簡化為質(zhì)點(diǎn)；（2）假設(shè)無人機(jī)在執(zhí)行任務(wù)中，保持一定的飛行高度和速度，在二維有限空間進(jìn)行移動；（3）假設(shè)地形障礙、地空導(dǎo)彈火力覆蓋范圍已知，并用多邊形進(jìn)行表示（通常地空導(dǎo)彈火力覆蓋為圓形區(qū)，這里簡化模型，用正方形區(qū)域表示）。

1.2 空間建模

在航跡規(guī)劃中，常用的空間建模方法有VOR?ONOI 法、柵格圖法、鏈接圖法等，其中鏈接圖法具有簡化模型占用內(nèi)存少、效果好的優(yōu)點(diǎn)，故本文采用鏈接圖法構(gòu)造二維空間模型，生成規(guī)劃可用空間，如圖1 所示，在MATLAB 環(huán)境中構(gòu)造200 km×200 km 的二維空間，存在4 個不規(guī)則多邊形表示的障礙區(qū)域、多條自由鏈接線（黑色虛線表示）和初始點(diǎn)和終止點(diǎn)，鏈接各鏈接線中點(diǎn)、初始點(diǎn)和終止點(diǎn)，生成初始航跡規(guī)劃網(wǎng)絡(luò)圖（黑色實(shí)線表示）。

圖1 鏈接圖法構(gòu)造二維空間模型圖Fig.1 Construction of two dimensional space model graph by link graph method

1.3 航跡點(diǎn)的構(gòu)造

式中：h為比例參數(shù)；為與航跡相交的鏈接線數(shù)。

通過式（1）可知，用，，…，h，和可以表示一條從起始點(diǎn)到終止點(diǎn)的航跡。

1.4 建立目標(biāo)函數(shù)

在無人機(jī)飛行穿越地形障礙、躲避敵方地對空導(dǎo)彈威脅時需要進(jìn)行航跡規(guī)劃，航跡規(guī)劃的任務(wù)是根據(jù)起始點(diǎn)和目標(biāo)點(diǎn)的位置，在避開地形障礙區(qū)、導(dǎo)彈威脅區(qū)的前提下，找到一條最短航跡，保證無人機(jī)能夠安全、快速通過。目標(biāo)函數(shù)為

式中：(，)為航跡長度（在第次迭代第只螞蟻的情況）。

2 蟻群算法改進(jìn)

2.1 Dijkstra 算法規(guī)劃初始航跡

為了改善ACO 算法前期搜索效率差的問題，運(yùn)用典型的最短路徑算法，在算法求解出一個節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短航跡的基礎(chǔ)上，確定起始點(diǎn)到終止點(diǎn)的一條較優(yōu)航跡，以減少ACO 算法前期搜索的盲目性。Dijkstra 算法的基本思想是先把二維模型中的節(jié)點(diǎn)分為兩組，一組為已確定最短航跡的節(jié)點(diǎn)，另一組為未確定最短航跡的節(jié)點(diǎn)，按最短航跡長度遞增的順序逐個把未確定的節(jié)點(diǎn)加入已確定的一組中，直到所有節(jié)點(diǎn)都成為已確定的節(jié)點(diǎn)，即可得到一條從初始點(diǎn)到終止點(diǎn)的較優(yōu)航跡。Dijkstra 算法流程如圖2 所示。

圖2 Dijkstra 算法初始化航跡流程圖［20］Fig.2 Flow chart of Dijkstra algorithm initialization track［20］

2.2 引入Logistic 混沌映射初始化信息素

為了避免蟻群停滯在局部搜索，提高算法收斂速度，引入混沌擾動。混沌是在確定性系統(tǒng)中存在的隨機(jī)情況，表現(xiàn)為類似隨機(jī)的非隨機(jī)運(yùn)動現(xiàn)象，其具有規(guī)律性、遍歷性、隨機(jī)性等特點(diǎn)。本文在初始化信息素階段應(yīng)用Logistic 混沌映射。Logistic 混沌映射方程：

式中：X()為混沌變量；為控制變量。

當(dāng)=4，0 ≤X(0)≤1 時，式（3）處 于 混 沌狀態(tài)。

信息素中引入Logistic 混沌映射：

式中：為可調(diào)節(jié)參數(shù)。

2.3 多航跡選擇策略

在ACO 算法中，狀態(tài)轉(zhuǎn)移規(guī)則直接影響了搜索解的質(zhì)量和效率，將真實(shí)螞蟻在前進(jìn)中對信息素利用、對新航跡的探索以及一些“隨機(jī)行為”引入狀態(tài)轉(zhuǎn)移規(guī)則，采用多航跡選擇策略對基本狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行改進(jìn)，公式為

式 中：，為 常 數(shù) 且0 ＜＜1，0 ＜＜1；為隨機(jī)數(shù)且0 ＜＜1。

當(dāng)≤時，從 可 行 航 跡 點(diǎn) 中 找 出[τ]·[η]最 大 的 航 跡 點(diǎn)；當(dāng)＜≤時，使 用ACO 算法的狀態(tài)轉(zhuǎn)移規(guī)則選擇航跡點(diǎn)；當(dāng)＞時，隨機(jī)選擇下一個航跡點(diǎn)。這種設(shè)計(jì)很好地保證了解的多樣性，同時避免算法因收斂速度快而陷入局部最優(yōu)的情況。

2.4 模擬退火算法

Metropolis 研究發(fā)現(xiàn)一般組合優(yōu)化問題和固體物質(zhì)退火過程中物理系統(tǒng)的能量變化具有相似性，進(jìn)而提出了模擬退火優(yōu)化算法。固體物質(zhì)退火分為升溫、等溫、降溫三個階段，高溫階段固體升溫，內(nèi)能增加，固體內(nèi)的粒子無序運(yùn)動速度快，此過程與算法設(shè)置的初始溫度對應(yīng)；等溫階段固體與外界保持熱平衡狀態(tài)，此過程與算法設(shè)置Me?tropolis 抽樣準(zhǔn)則對應(yīng)；退火階段固體溫度降低、內(nèi)能減小，粒子趨于有序，最終達(dá)到穩(wěn)定狀態(tài)，此過程與算法控制參數(shù)減小相對應(yīng)。使用Metropolis抽樣準(zhǔn)則接受一定條件下的劣解，有效避免陷入局部最優(yōu)，以達(dá)到收斂全局最優(yōu)解的效果。模擬退火算法流程如下：

（1）初始化：設(shè)置系統(tǒng)溫度為，初始溫度(0)=，任取初始解，確定每個時的迭代次數(shù)，即Metropolis 鏈長。

（2）對當(dāng)前溫度和=1，2，…，，重復(fù)步驟（3）～步驟（6）。

（3）對當(dāng)前解進(jìn)行隨機(jī)擾動，得到新解；

（4）設(shè)置增 量 為d，d=()-()，為的代價函數(shù)。

（5）根據(jù)Metropolis 準(zhǔn)則，公式為

（6）當(dāng)連續(xù)多個Metropolis 鏈中都未接受新解，或退火達(dá)到終止溫度，輸出當(dāng)前解為最優(yōu)解，然后結(jié)束；否則減小溫度后返回步驟（2）。

2.5 算法步驟

IH-ACO 算法通過Dijkstra 算法初始航跡、Lo?gistic 混沌映射初始化信息素、采用多航跡選擇策略和模擬退火機(jī)制，在提高算法收斂速度的同時，能夠有效提高全局搜索能力，避免陷入局部最優(yōu)。改進(jìn)算法流程如圖3 所示，具體實(shí)施步驟為：

（1）使用鏈接圖法構(gòu)造二維空間環(huán)境模型；

（2）采用Dijkstra 算法規(guī)劃一條從起始點(diǎn)到終止點(diǎn)的初始航跡；

（3）初始化算法參數(shù)；

（4）引入Logistic 混沌映射，按照式（4）初始化信息素；

（5）設(shè)=0，只螞蟻放于初始點(diǎn)；

（6）蟻群算法開始搜索，根據(jù)式（5）選擇下一節(jié)點(diǎn)；

（7）判斷螞蟻是否到達(dá)終止點(diǎn)，若未到達(dá)終止點(diǎn)，跳轉(zhuǎn)至步驟（6），到達(dá)終止點(diǎn)則跳轉(zhuǎn)至步驟（8）；

（8）引入模擬退火機(jī)制，根據(jù)式（6）產(chǎn)生新解并更新最優(yōu)解；

（9）根據(jù)當(dāng)前航跡規(guī)劃情況，更新信息素；

（10）=+1，當(dāng)＞時，輸出結(jié)果，否則跳轉(zhuǎn)至步驟（5）。

圖3 IH-ACO 算法流程圖Fig.3 IH-ACO flow diagram

3 仿真分析

為測試IH-ACO 算法在無人機(jī)作戰(zhàn)中飛行穿越地形障礙、躲避敵方地對空導(dǎo)彈威脅的航跡規(guī)劃效果，使用MATLAB 2018a 對IH-ACO 算法進(jìn)行仿真，并與ACO 算法、文獻(xiàn)［10］的改進(jìn)算法（Novel Ant Colony Algorithm，簡稱NL-ACO）和文獻(xiàn)［12］的改進(jìn)算法（Evolutionary Ant Colony Al?gorithm，簡稱EY-ACO）在相同測試環(huán)境下進(jìn)行對比。構(gòu)造200 km×200 km 的二維仿真測試區(qū)域，進(jìn)行算法參數(shù)初始化：種群數(shù)量=20，信息啟發(fā)因子＝1，期望啟發(fā)因子＝2，初始條件下信息素濃度＝0.000 09，信息素衰減因子＝0.5，隨機(jī)概率＝0.6，迭代次數(shù)=500，模擬退火初始溫度=90 ℃，終止溫度=10 ℃，退火系數(shù)為0.9，隨機(jī)產(chǎn)生地形障礙區(qū)（不規(guī)則多邊形表示）和敵方地空導(dǎo)彈威脅區(qū)（正方形表示）、起始點(diǎn)Start 和終止點(diǎn)End。

仿真實(shí)驗(yàn)1：無人機(jī)穿越1 個的地形障礙區(qū)，初始點(diǎn)為Start（20，20）、終止點(diǎn)為End（140，90），實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 一個地形障礙區(qū)時航跡軌跡迭代圖Fig.4 Iterative map of track in a terrain obstacle area

仿真實(shí)驗(yàn)2：無人機(jī)穿越2 個地形障礙區(qū)，初始點(diǎn)為Start（20，180）、終止點(diǎn)為End（160，97），實(shí)驗(yàn)結(jié)果如圖5 所示。

圖5 兩個地形障礙區(qū)時航跡軌跡迭代圖Fig.5 Iterative map of track in two terrain obstacle areas

仿真實(shí)驗(yàn)3：無人機(jī)躲避1 個地空導(dǎo)彈威脅區(qū)并穿越3 個地形障礙區(qū)，初始點(diǎn)為Start（30，100）、終止點(diǎn)為End（180，60），實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 1 個地空導(dǎo)彈威脅區(qū)和3 個地形障礙區(qū)時航跡軌跡迭代圖Fig.6 Iterative map of track trajectory for one surface to air missile threat area and three terrain obstacle areas

仿真實(shí)驗(yàn)4：無人機(jī)穿越躲避3 個地空導(dǎo)彈威脅區(qū)并穿越5 個地形障礙區(qū)，初始點(diǎn)為Start（10，100）、終 止 點(diǎn) 為End（180，80），實(shí) 驗(yàn) 結(jié) 果 如 圖7所示。

圖7 3 個地空導(dǎo)彈威脅區(qū)和5 個地形障礙區(qū)時航跡軌跡迭代圖Fig.7 Iterative map of track trajectory for three surface to air missile threat areas and five terrain obstacle areas

從圖4～圖7 中的（a）圖可以看出：在無人機(jī)航跡規(guī)劃過程中，通過使用ACO 算法、NL-ACO 算法、EY-ACO 算法、IH-ACO 算法，無人機(jī)可以有效穿越地形障礙、躲避敵方地對空導(dǎo)彈威脅，證明四種算法都能滿足無人機(jī)航跡規(guī)劃的基本要求。

從圖4～圖7 中的（b）圖可以看出：IH-ACO 算法和ACO 算法相比，在迭代次數(shù)一定的情況下，IH-ACO 算法搜索得到的最短航跡更小，表明本文改進(jìn)算法的全局搜索能力得到了增強(qiáng)；IH-ACO算法與NL-ACO 算法、EY-ACO 算法相比，在均可加快收斂速度的情況下，NL-ACO 算法、EYACO 算法在面對復(fù)雜環(huán)境時出現(xiàn)了停滯在局部最優(yōu)解的情況，而本文改進(jìn)算法仍可以很好地進(jìn)行航跡搜索。綜上所述，可以證明IH-ACO 算法可有效解決全局尋優(yōu)與收斂速度之間矛盾。

四種算法運(yùn)算結(jié)果如表1 所示，可以看出：IHACO 算法在最短航跡、收斂時間上都要優(yōu)于其他三種算法，表明IH-ACO 算法在精度提高的同時，加快了收斂速度，即IH-ACO 算法具有更好的尋優(yōu)能力。

表1 四種算法運(yùn)算結(jié)果Table 1 Calculation results of four algorithms

綜上可知，由于在前期進(jìn)行了Dijkstra 算法初始航跡、Logistic 混沌映射初始化信息素，在中、后期采用多航跡選擇策略和模擬退火機(jī)制，IH-ACO算法加強(qiáng)了全局搜索能力并提高了算法收斂速度，相比ACO 算法具有更好的航跡規(guī)劃效果。

4 結(jié) 論

（1）使用Dijkstra 算法進(jìn)行初始化航跡、Logis?tic 混沌映射初始化信息素，保證較快的搜索速度，提高蟻群前期搜索能力。

（2）采用多航跡選擇策略的狀態(tài)轉(zhuǎn)移規(guī)則，增加解的多樣性，有效提高了算法的全局搜索能力。

（3）應(yīng)用模擬退火機(jī)制，避免算法收斂過快陷入局部最優(yōu)解。

（4）IH-ACO 算法在航跡規(guī)劃過程中，因Dijk?stra 初始化和Logistic 初始化能加快前期搜索效率、多航跡選擇策略能增加解的多樣性、模擬退火機(jī)制能防止早熟收斂，有效解決全局尋優(yōu)與收斂速度之間的矛盾，在無人機(jī)作戰(zhàn)的航跡任務(wù)規(guī)劃中有很好的適用性。

（5）HI-ACO 算法與ACO 算法相比，在收斂速度提升的同時保證了全局搜索能力；HI-ACO算法與NL-ACO 算法、EY-ACO 算法相比，在復(fù)雜環(huán)境中仍能快速、有效地進(jìn)行航跡搜索，解決了其他改進(jìn)算法在復(fù)雜環(huán)境中停滯在局部最優(yōu)解的問題。

下一步將研究如何將IH-ACO 算法應(yīng)用到有更多約束條件的復(fù)雜環(huán)境中進(jìn)行航跡規(guī)劃，并結(jié)合不同的作戰(zhàn)環(huán)境和目的要求，提出更實(shí)時高效的航跡規(guī)劃算法。