基于自適應(yīng)郊狼算法的無人機離線航跡規(guī)劃

陳 都, 孟秀云

(北京理工大學(xué)宇航學(xué)院, 北京 100081)

0 引 言

伴隨科技的飛速發(fā)展,無人機向著信息化、智能化、體系化方向發(fā)展,航跡規(guī)劃問題作為無人機任務(wù)規(guī)劃的一部分,是無人機自主智能執(zhí)行任務(wù)的一個核心步驟。無人機離線航跡規(guī)劃是在無人機起飛前,考慮無人機的動力學(xué)約束、任務(wù)要求、環(huán)境因素等,在一個合理的時間內(nèi)為無人機規(guī)劃一條從起點到終點的最優(yōu)航跡。

相對于在線實時的無人機航跡規(guī)劃,無人機離線航跡規(guī)劃側(cè)重于規(guī)劃出飛行軌跡的最優(yōu)性與穩(wěn)定性,其本質(zhì)上是一個多約束多峰高維的最優(yōu)化問題,因此，元啟發(fā)式群體智能算法很適合無人機離線航跡規(guī)劃。元啟發(fā)式群體智能算法在解決最優(yōu)化問題時,隨機初始化一群個體,每一個個體代表優(yōu)化問題一個可能的解,在航跡規(guī)劃問題中每個個體代表一條航跡,然后根據(jù)算法的元啟發(fā)操作算子,更新個體的值,直至達到停止條件。

大量文獻對無人機離線航跡規(guī)劃問題進行了研究,各種元啟發(fā)式群體智能算法被應(yīng)用于無人機離線航跡規(guī)劃,如傳統(tǒng)的遺傳算法(genetic algorithm,GA)、粒子群優(yōu)化(particle swarm optimization,PSO)算法、蟻群算法,近些年提出的各種新型算法,如蝙蝠算法、灰狼(grey wolf optimizer,GWO)算法、烏賊算法、共生生物搜索算法、樽海鞘算法等。在用元啟發(fā)式群體智能算法搜索無人機航跡時,存在兩方面問題:一是對于復(fù)雜環(huán)境的航跡規(guī)劃問題,算法易陷入局部最優(yōu),過早地收斂,全局尋優(yōu)能力不足,很多文獻針對該問題在元啟發(fā)式算法基礎(chǔ)上提出了許多改進策略,如將隨機游走、混沌序列、正余弦優(yōu)化、強化學(xué)習(xí)等與元啟發(fā)式算法結(jié)合,還有文獻將兩種基礎(chǔ)算法混合,這些改進能在一定程度上提高算法全局搜索能力,但也受限于原始算法本身的特性;二是在建立無人機航跡規(guī)劃模型時,將問題的維數(shù)設(shè)置較高時,算法表現(xiàn)不夠穩(wěn)定,有時難以在合理的時間內(nèi)收斂,針對該問題,許多文獻采用降維搜索的策略,如文獻[20-21]設(shè)置最小威脅曲面搜索,文獻[22]通過固定一個方向的數(shù)值搜索,還有大多數(shù)文獻[10,23-24]通過指定較少的航跡點個數(shù)或僅在二維平面搜索來降低離線航跡規(guī)劃問題的維數(shù),降維處理的方式使算法在處理離線航跡規(guī)劃問題時表現(xiàn)更穩(wěn)定,但也容易使算法輸出的航跡偏離最優(yōu)航跡。

本文針對上述元啟發(fā)式群體智能算法應(yīng)用于無人機離線航跡規(guī)劃時的兩個問題,研究基于自適應(yīng)郊狼優(yōu)化算法(self-adaptive coyote optimization algorithm, SACOA)的無人機離線航跡規(guī)劃方法。建立無人機離線航跡規(guī)劃的數(shù)學(xué)模型,包括規(guī)劃空間的表示、航跡的初始化方式以及代價函數(shù)的建立。隨后在郊狼優(yōu)化算法(coyote optimization algorithm, COA)的基礎(chǔ)上設(shè)計4種不同性質(zhì)的操作算子和一種自適應(yīng)學(xué)習(xí)機制,并設(shè)計萊維飛行策略,提高算法的運算效率和全局搜索能力。最后利用基準函數(shù)評測算法的性能并進行航跡規(guī)劃仿真實驗分析。

1 數(shù)學(xué)模型

1.1 規(guī)劃空間模型

無人機的飛行軌跡表示為一系列離散空間點序列{,,,…,,},和分別為航跡規(guī)劃的起點和終點,,,…,為需要規(guī)劃的中間節(jié)點,在三維離線航跡規(guī)劃中,=×3為規(guī)劃問題的維數(shù)。

本文仿真實驗設(shè)計的無人機任務(wù)環(huán)境包括地形模型和威脅模型。原始地形建模讀取某一區(qū)域的數(shù)字地形高程圖,通過雙線性插值建立一個連續(xù)的地形模型,原始地形是一塊44.64 km×46.98 km的矩形區(qū)域,威脅區(qū)域建模為半徑為3 km,高為2.5 km的圓柱體。

相對于一般最優(yōu)化問題,離線航跡規(guī)劃問題解具有一定特點,其解在解空間的分布不是無序的,而是一條可執(zhí)行的飛行軌跡。由此本文設(shè)計一種橢圓初始化方式,如圖1所示。

圖1 離線航跡規(guī)劃的初始化方式Fig.1 Initialization of offline path planning

根據(jù)航跡點可能的分布情況,以規(guī)劃的起點和終點為橢圓長軸的兩個端點建立一個橢圓方程,以橢圓的上半圓、下半圓和長軸作為基準線,根據(jù)航跡點的個數(shù)生成條分割線等分橢圓的長軸,在每一條基準線附近應(yīng)用正態(tài)分布生成航跡點的、坐標,同時滿足、坐標在分割線上,坐標以不與地形碰撞為約束在規(guī)劃空間中按均勻分布隨機生成。圖1是以橢圓長軸為基準線的初始化示例。橢圓初始化方式讓離線航跡規(guī)劃問題的解初始化在最優(yōu)解附近,縮小了算法在解空間的搜索范圍,從而提高元啟發(fā)式群體智能算法在應(yīng)對高維復(fù)雜離線航跡規(guī)劃問題時的穩(wěn)定性。

1.2 約束模型

無人機航跡規(guī)劃過程中需要考慮各類約束條件。

(1) 最大轉(zhuǎn)彎角約束。無人機轉(zhuǎn)彎的角度受其機動性能的約束,不能超過一定范圍。設(shè)允許的最大轉(zhuǎn)彎角為,第個航跡點的空間坐標為(,,),第段航跡在水平面的投影可表示為=(--1,--1),則最大轉(zhuǎn)彎角約束可以描述為

(1)

(2) 最大爬升、俯沖角約束。無人機的最大爬升、俯沖角受無人機的推力、機動性能的影響。設(shè)無人機允許的最大爬升、俯沖角為,則該約束可表示為

(2)

(3) 最小相對飛行高度約束。無人機在執(zhí)行任務(wù)時需要與地面保持一定距離避免發(fā)生碰撞,設(shè)第段航跡段最低點的相對高度為,則該約束可表示為

≥

(3)

(4) 最短航跡段約束。受無人機機動性能的影響,無人機在改變航向之前有一個最短的直飛距離,設(shè)第段航跡的長度為,則該約束表述為

≥

(4)

1.3 代價函數(shù)模型

無人機離線航跡規(guī)劃問題的代價函數(shù)是評估航跡優(yōu)劣的標準,代價函數(shù)主要考慮的因素有任務(wù)要求、航跡長度和無人機約束條件。將航跡點序列表示為向量=(,,…,3),設(shè)()為目標函數(shù),()為約束條件函數(shù),則離線航跡規(guī)劃問題可描述為

(5)

本文以航跡的總長度為搜索目標,將約束條件以罰函數(shù)形式表示,由此代價函數(shù)()可表示為

(6)

()=()+∑()

(7)

式中:表示從航跡起點到終點的直線距離;為第個約束函數(shù)的懲罰因子。

2 SACOA

2.1 COA

COA是2018年由Pierezan等人提出的一種新型元啟發(fā)式群體智能算法,它通過模擬郊狼種群的生物特性來尋找優(yōu)化問題的解。COA在應(yīng)用于高維度多峰多約束的優(yōu)化問題時,不易早熟,全局搜索能力較強,但它也存在可操作性不高、適應(yīng)能力較差的問題。

COA主要有4個步驟:郊狼種群的分組與初始化、組內(nèi)郊狼的成長、郊狼的出生與死亡、郊狼在組與組之間的驅(qū)趕與接納。

郊狼種群的初始化主要包括設(shè)置種群的數(shù)量,分組的個數(shù)以及每組的個數(shù),其中=×。設(shè)置算法停止的條件:最大迭代次數(shù)或算法運行時間限制。根據(jù)最優(yōu)化問題的維數(shù),以向量形式表示每一頭郊狼,第次迭代第組的第個個體的表達式如式(8)所示,對于沒有明顯特征的一般最優(yōu)化問題,每個郊狼個體的每一維按照式(9)進行初始化,隨后按照式(10)計算每頭郊狼的適應(yīng)度值。

(8)

=lb+(ub-lb)

(9)

fit=()

(10)

式中:lb和ub分別表示郊狼個體第維社會因子的上限和下限,=1,2,…,,表示優(yōu)化問題的維數(shù);表示[0,1]范圍內(nèi)服從均勻分布的隨機數(shù);(·)表示適應(yīng)度函數(shù)。

組內(nèi)郊狼的成長主要考慮每組的最優(yōu)個體、每組的組文化趨勢、以及在每組隨機選擇的兩個個體cr和cr。組文化趨勢在算法中以每組的中位數(shù)個體表示。式(11)～式(15)表示了郊狼種群中每個個體的成長方式。

(11)

(12)

(13)

(14)

(15)

在一次迭代得到一個新解后,根據(jù)貪婪策略決定是否接受該新解:

(16)

郊狼的出生與死亡。幼年郊狼的誕生受組中隨機選擇的父母郊狼和環(huán)境因素的共同作用,式(17)表示了幼年郊狼的誕生過程:

(17)

式中:和為在組隨機選擇的兩個父郊狼序號;和為優(yōu)化問題的兩個隨機維度,確保兩個父代的基因一定能夠遺傳給子代;rnd為[0,1]內(nèi)均勻分布的隨機數(shù);為在優(yōu)化問題第維范圍內(nèi)產(chǎn)生的隨機數(shù),表征著環(huán)境因素的影響;和分別為分散概率與關(guān)聯(lián)概率,決定著新誕生的郊狼受父代和環(huán)境影響的比率,其計算表達式為

=1

(18)

=(1-)2

(19)

為保證種群的個數(shù)不變,在幼年郊狼出生后,根據(jù)其社會適應(yīng)度值決定幼年郊狼的生與死:當(dāng)組內(nèi)存在比幼年郊狼適應(yīng)度差的郊狼時,幼年郊狼存活,適應(yīng)度值最差的個體死亡,當(dāng)新出生的郊狼適應(yīng)度值在組內(nèi)最差時,則幼年郊狼直接死亡。

郊狼的驅(qū)趕與接納。郊狼開始是隨機分配到某一組群中,為保證種群的活力,增強組與組之間的信息交流與聯(lián)系,郊狼在成長的過程中,有一定概率離開它所在的組而進入其他組,其概率為

(20)

2.2 SACOA

COA以組群中隨機兩個個體與最優(yōu)個體、“組文化”之間的差值來引導(dǎo)組群中個體在解空間搜索,相比于粒子群算法、灰狼算法等傳統(tǒng)仿生智能群算法的操作算子,這種操作算子是一種間接啟發(fā)信息模型,在解空間中探索未知空間的能力比較強,全局搜索能力強,但存在搜索效率較低、可操作性不高的問題。

本章提出SACOA,在COA的基礎(chǔ)上,設(shè)計4種不同的操作算子,讓算法搜索中每個個體根據(jù)自適應(yīng)學(xué)習(xí)機制智能選擇合適的操作算子,同時去除COA中個體生與死步驟,讓種群在搜索過程中小概率做隨機方向的萊維飛行。

2.2.1 操作算子與自適應(yīng)學(xué)習(xí)機制設(shè)計

COA中操作算子和貪婪策略引導(dǎo)種群中個體向著最優(yōu)解收斂,但對于不同優(yōu)化問題、不同個體,由于個體所處的位置不同、解決的問題性質(zhì)不同,每個個體趨向于收斂位置的路徑是不同的,采取同一操作算子效率較低,由此本文設(shè)計4種操作算子,并設(shè)計一種自適應(yīng)智能學(xué)習(xí)機制,使種群中每一個個體在每次迭代中,根據(jù)自身的情況,智能選取合適的操作算子,增加有效迭代的次數(shù),提高算法收斂速度以及全局搜索能力。以下是4種操作算子的表達式:

(21)

(22)

(23)

(24)

在SACOA中,引導(dǎo)信息包括每組的最優(yōu)個體、組文化趨勢、最鄰近的個體以及變異因子,智能學(xué)習(xí)機制是為了在貪婪策略下,針對不同問題、不同個體,讓每個個體每次迭代選擇最合適的操作算子,減少無效迭代的次數(shù),提高算法的收斂速度與全局尋優(yōu)能力。以下是自適應(yīng)學(xué)習(xí)機制的描述。

對于每個粒子,每種操作算子的初始選擇概率為025,在自適應(yīng)智能學(xué)習(xí)機制中,第個個體選擇第個操作算子的概率為():

(25)

式中:表示最小概率,本文設(shè)置為01;()表示第個個體選擇第個操作算子的回報函數(shù),其計算表達式為

(26)

式中:()為第個個體選擇第個操作算子成功改善個體適應(yīng)度值的次數(shù);和分別為獎勵因子和懲罰因子,當(dāng)上一次選擇第個操作算子,若成功改善個體適應(yīng)度值則獎勵因子置為一個正值,本文取01,若沒有改善適應(yīng)度值則懲罰因子置一個正值,本文取01,其他情況置0。

222 萊維飛行策略設(shè)計

萊維飛行在應(yīng)用于搜索未知空間方面有很多實例,文獻[27]數(shù)據(jù)表明用萊維飛行和布朗運動可以表述海洋生物的捕食運動。文獻[28-30]研究表明合理地應(yīng)用萊維飛行能有效改善算法的搜索能力。

萊維飛行相對于其他類型的隨機游走而言,有相對較高的概率出現(xiàn)大的跨步,屬于一種短距離和長距離相間混合的行走方式。在數(shù)學(xué)描述中,萊維分布是一種冪函數(shù)分布:()～e-,在實際應(yīng)用中一般用Mantegna算法模擬萊維飛行:

(27)

式中:=-1,一般取常數(shù)15;和服從正態(tài)分布:

(28)

(29)

(30)

式中:(·)為伽馬函數(shù);=1。

本文設(shè)置在迭代過程中,個體以小概率做萊維飛行:

(31)

綜上,SACOA的操作步驟如下。

設(shè)置初始參數(shù):種群個數(shù),分組數(shù),每組的個體數(shù)量,萊維飛行概率;

初始化郊狼種群,并計算每個個體的適應(yīng)度值;

每個個體根據(jù)式(25)計算每個操作算子的選擇概率,并按概率選擇操作算子;

根據(jù)所選擇的操作算子計算個體的值,根據(jù)式(16)更新個體的值并更新個體的適應(yīng)度值;

每個個體按概率,根據(jù)式(31)進行隨機方向的萊維飛行;

每個組群之間按式(20)規(guī)定的概率進行“驅(qū)離”與“接納”操作;

判斷是否達到終止條件,若是則輸出最優(yōu)個體,否則重復(fù)步驟3～步驟7。

3 仿真實驗與分析

本文首先利用基準函數(shù)測試SACOA的性能,隨后進行離線航跡規(guī)劃仿真實驗驗證SACOA應(yīng)用于無人機離線航跡規(guī)劃的有效性。實驗程序由C#語言編寫,Visual Studio 2019平臺運行。SACOA和COA的公共參數(shù)設(shè)置如下:=100,=5,=20,SACOA萊維飛行的概率設(shè)置為=0.01。

3.1 基準函數(shù)測試與對比

為了驗證SACOA應(yīng)用于高維復(fù)雜函數(shù)時的性能,本文采用來自CEC2017的復(fù)雜函數(shù)進行實驗驗證。CEC2017的測試函數(shù)包含30個不同特性的函數(shù):單峰函數(shù)(F1～F3)、單一多峰函數(shù)(F4～F10)、混合多峰函數(shù)(F11～F20)和組合多峰函數(shù)(F21～F30)。所有測試函數(shù)的維數(shù)設(shè)置為=50,每一維的搜索區(qū)間為[-100,100]。選取用于對比的元啟發(fā)式群體智能算法包括PSO、GA、GWO、COA。

考慮到公平對比,所有算法的公共參數(shù)保持一致。PSO、GA、GWO的參數(shù)采取默認參數(shù)。最大迭代次數(shù)設(shè)置為10 000次,每種算法獨立實驗50次。實驗結(jié)果如表1所示。

表1 SACOA和其他算法在CEC2017測試函數(shù)上的性能對比

續(xù)表1

本文采用均值(Mean)和標準差(Std.Dev)來評估一個算法的尋優(yōu)能力和穩(wěn)定性能。均值越小表示算法的尋優(yōu)能力越強,標準差越小則表示算法穩(wěn)定性越好。同時給每個算法在每一個函數(shù)的表現(xiàn)進行排名(Rank),并統(tǒng)計每一種算法的平均排名與總體排名。由表1可以看出:① 在30個高維測試函數(shù)中,SACOA和COA整體平均排名分別位居第一和第二,SACOA在24個函數(shù)測試中排名第一,COA在3個測試函數(shù)中排名第一,在23個測試函數(shù)中排名第二,由此表明SACOA和COA在應(yīng)對高維復(fù)雜最優(yōu)化問題時的性能優(yōu)勢明顯;② 進一步觀察發(fā)現(xiàn),SACOA、COA相較于GA、PSO、GWO的優(yōu)勢主要是單一多峰函數(shù)、混合多峰函數(shù)和組合多峰函數(shù),單峰函數(shù)主要考察算法的局部開發(fā)能力,多峰函數(shù)主要考察算法的全局搜索能力,由此可知SACOA、COA的優(yōu)勢是應(yīng)對復(fù)雜高維多峰最優(yōu)化問題時,具有較強的全局搜索能力,不易陷入局部最優(yōu),這與離線航跡規(guī)劃的要求十分契合;③ SACOA相對于COA,在25個多峰復(fù)雜函數(shù)上的表現(xiàn)有不同程度的提高,這表明SACOA相較于COA進一步提高了應(yīng)對多峰復(fù)雜最優(yōu)化問題時的全局探索能力。

COA采取貪婪策略,每個個體的每次迭代只會接受適應(yīng)度得到改善的操作,每一次接受稱為一次有效迭代,圖2為在單一多峰函數(shù)、混合多峰函數(shù)、組合多峰函數(shù)中分別選取兩個函數(shù),畫出SACOA、COA一次運算中每個個體的平均有效迭代次數(shù)的條形圖,由圖2可以看出,SACOA相比于COA,在相同的最大迭代次數(shù)情況下,有效迭代次數(shù)均有不同程度的提高,這使得SACOA搜索效率更高,探索未知空間的次數(shù)更多,能更均勻地搜索解空間,這是SACOA全局尋優(yōu)能力更強的原因,表明了本文設(shè)計的自適應(yīng)學(xué)習(xí)機制和萊維飛行策略的有效性。

圖2 有效迭代次數(shù)對比Fig.2 Comparison of effective iterations

綜上,SACOA具有良好的全局搜索能力,不易早熟,適用于解決高維多峰的復(fù)雜最優(yōu)化問題。

3.2 離線航跡規(guī)劃仿真

為了驗證本文所提策略應(yīng)用于無人機離線航跡規(guī)劃的有效性,本節(jié)在三維環(huán)境下分別使用SACOA、COA、GA、PSO進行航跡規(guī)劃。仿真條件設(shè)置:約束條件設(shè)置為最大轉(zhuǎn)彎角=45°,最大爬升、俯沖角=30°,最小航跡段=1 000 m,最低相對高度=100 m。航跡規(guī)劃的起點為(5 670,41 670,1 000)m,終點為(42 030,2 349,800)m。最大迭代次數(shù)為5 000次。

圖3為分別設(shè)置10個(30維)、20個(60維)、30個(90維)航跡點,應(yīng)用SACOA、COA、GA、PSO進行重復(fù)實驗50次,得到的平均代價以及其上下波動范圍。由圖3可以看出,在30～90維范圍內(nèi),隨著航跡規(guī)劃問題維數(shù)的上升,算法規(guī)劃得到的航跡代價值整體是上升的,SACOA在不同維數(shù)的條件下均取得了最優(yōu)的效果,航跡平均代價最小,上下限波動范圍也是最小的。同時,可以看出當(dāng)航跡規(guī)劃問題維數(shù)設(shè)置為30維時,4種算法規(guī)劃得到的航跡代價相差較小,當(dāng)問題維數(shù)上升時,尤其是90維時,SACOA仍能保持較好的全局搜索能力,而其他3種算法規(guī)劃得到的航跡代價均具有較大幅度的上升。

圖3 SACOA和其他算法規(guī)劃的航跡相對代價Fig.3 Cost of the path planned by SACOA and other algorithms

圖4為設(shè)置20個(60維)航跡點時,SACOA、COA、GA、PSO規(guī)劃結(jié)果對比。由圖4可以看出,相較于GA、PSO和COA,SACOA規(guī)劃的航跡曲折更小,更平滑,相對高度更低,航跡長度更短,表明SACOA規(guī)劃的航跡質(zhì)量更高。圖5為航跡代價隨迭代次數(shù)的變化曲線,由圖5可看出,SACOA的相對代價值最小,表明SACOA的航跡最優(yōu)。同時可以看出PSO、GA收斂很快,在不到1 000次時就陷入了局部最優(yōu),而SACOA和COA收斂較慢,在2 000～3 000次時航跡代價還有微弱的改善,這表明SACOA和COA在應(yīng)用于無人機離線航跡規(guī)劃時有良好的全局搜索能力。同時可以看出,SACOA相比于COA達到同一代價值所需的迭代次數(shù)更少,表明SACOA的效率更高,全局尋優(yōu)能力更強,也表明本文提出的操作算子、自適應(yīng)學(xué)習(xí)機制和萊維飛行策略的有效性。

圖4 航跡規(guī)劃結(jié)果對比Fig.4 Comparison of path planning results

圖5 航跡代價隨迭代次數(shù)變化曲線Fig.5 Curve of cost with the number of iterations

綜上離線航跡規(guī)劃仿真,SACOA應(yīng)用于無人機離線航跡規(guī)劃時具有良好的全局搜索能力,能適應(yīng)不同維數(shù)的離線航跡規(guī)劃問題。

4 結(jié) 論

本文提出了一種SACOA,在原始COA的基礎(chǔ)上設(shè)計了4種操作算子和一種自適應(yīng)學(xué)習(xí)機制,讓種群中的郊狼個體每次迭代智能選擇合適的操作算子,同時設(shè)計了萊維飛行策略,提高了算法的搜索效率和全局搜索能力。進行了函數(shù)測試與航跡規(guī)劃仿真分析,函數(shù)測試表明SACOA具有良好的搜索效率和全局尋優(yōu)能力,適合解決多峰高維最優(yōu)化問題,航跡規(guī)劃仿真實驗表明SACOA能很好地處理不同維數(shù)的無人機離線航跡規(guī)劃問題,具有良好的工程價值。