基于AC-DSDE進(jìn)化算法多UAVs協(xié)同目標(biāo)分配

黃 剛 李軍華

多無(wú)人機(jī)協(xié)同目標(biāo)分配優(yōu)化問(wèn)題(Multi-UAV cooperative target allocation optimal problem,MUCTAOP)是指在復(fù)雜任務(wù)環(huán)境中,為無(wú)人機(jī)編隊(duì)分配一個(gè)或一組有序任務(wù),即對(duì)有限的UAVs 資源進(jìn)行合理的分配,同時(shí)編隊(duì)整體效率達(dá)到最優(yōu)[1].文獻(xiàn)[2?4]指出多機(jī)協(xié)同目標(biāo)分配優(yōu)化問(wèn)題具有協(xié)同性較高、計(jì)算難度大、復(fù)雜度高等特點(diǎn).在目標(biāo)分配過(guò)程中,既要考慮飛行器的性能差異、戰(zhàn)場(chǎng)勢(shì)態(tài)的復(fù)雜性、任務(wù)執(zhí)行權(quán)重等因素;還需要考慮可行的飛行代價(jià)、合理的分配算法及各種協(xié)同約束條件.

近年來(lái),為了解決多機(jī)協(xié)同目標(biāo)分配問(wèn)題,研究者們提出了很多優(yōu)秀算法.這些協(xié)同目標(biāo)分配算法主要可以分為三類:

1) 基于數(shù)學(xué)規(guī)劃法的協(xié)同目標(biāo)分配

數(shù)學(xué)規(guī)劃法是解決集中式分配問(wèn)題的經(jīng)典方法;在處理維數(shù)較低的分配情況時(shí),該方法簡(jiǎn)單靈活,求解速度較快;但在處理維數(shù)較高的情況時(shí),求解的難度呈指數(shù)級(jí)增長(zhǎng),且要求已知研究對(duì)象所有的信息,將復(fù)雜作戰(zhàn)環(huán)境信息過(guò)度簡(jiǎn)化,因此僅適合低維的簡(jiǎn)單任務(wù)環(huán)境問(wèn)題求解.例如匈牙利算法[5]、混合整數(shù)線性規(guī)劃法(Mixed integer linear programming,MILP)[6]、動(dòng)態(tài)規(guī)劃法[7].

2) 基于協(xié)商法的協(xié)同目標(biāo)分配

協(xié)商法能夠有效解決分布式目標(biāo)分配問(wèn)題,該類算法計(jì)算靈活,可以將不同層次的分配問(wèn)題,在各個(gè)節(jié)點(diǎn)上進(jìn)行分布處理.但在復(fù)雜任務(wù)環(huán)境中,隨著分配規(guī)模的增大,系統(tǒng)的魯棒性較差;同時(shí),對(duì)協(xié)同約束的處理能力較差,致使其實(shí)現(xiàn)效果偏差較大.例如基于合同網(wǎng)的協(xié)商算法(Contract net based negotiation algorithm,CNBNA)[8],基于共識(shí)捆綁算法(Consensus-based bundle algorithm,CBBA)[9].

3) 基于進(jìn)化算法的協(xié)同目標(biāo)分配

該類算法是建立在自然選擇與群體遺傳基礎(chǔ)上的尋優(yōu)算法,實(shí)質(zhì)上遵循“優(yōu)勝劣汰”和“適者生存”的思想,具有較高魯棒性和廣泛適用性.但是該類算法容易出現(xiàn)局部最優(yōu)解,收斂速度較慢,以及停滯等現(xiàn)象[10?13].例如遺傳算法[14]、粒子群算法[15]、蟻群算法[16]、差分進(jìn)化算法[17]等.

由于人們對(duì)無(wú)人機(jī)系統(tǒng)需求不斷提高,尤其是三維真實(shí)環(huán)境和異構(gòu)多無(wú)人機(jī)體系構(gòu)建,使該領(lǐng)域的研究更注重復(fù)雜高精,密切貼合實(shí)際等要求.數(shù)學(xué)規(guī)劃法與協(xié)商法在目標(biāo)分配過(guò)程中都簡(jiǎn)化了三維真實(shí)環(huán)境.進(jìn)化算法靈活的編碼結(jié)構(gòu)適合復(fù)雜三維問(wèn)題的建模和求解[18].因此,進(jìn)化算法逐漸成為多機(jī)協(xié)同目標(biāo)分配研究方法之一.其中差分進(jìn)化算法(Differential evolution algorithm,DE)運(yùn)行穩(wěn)定、收斂速度較快、空間復(fù)雜度較低,在處理高維問(wèn)題中顯示出較好的結(jié)果.因此,本文重點(diǎn)研究基于DE的多無(wú)人機(jī)協(xié)同目標(biāo)分配.

盡管DE 算法已經(jīng)很好地處理多無(wú)人機(jī)協(xié)同目標(biāo)分配問(wèn)題,但在處理高維復(fù)雜環(huán)境下多機(jī)協(xié)同目標(biāo)分配仍然存在如下難點(diǎn):

1) 現(xiàn)用的進(jìn)化策略進(jìn)行目標(biāo)分配求解時(shí),往往只關(guān)注優(yōu)化的某一個(gè)方面,選擇適合探索(尋找更多全局最優(yōu)區(qū)域)和開發(fā)(加速收斂到最優(yōu)區(qū)域速度)的適當(dāng)繁衍方案是一個(gè)兩難選擇.例如,具有高隨機(jī)性的變異方案?jìng)?cè)重于探索,而貪婪的變異方案?jìng)?cè)重于開發(fā),這就導(dǎo)致了在解決組合優(yōu)化問(wèn)題時(shí)存在不足.針對(duì)不同策略的改進(jìn)和混合,以平衡探索性與開發(fā)性也是目前的一個(gè)難點(diǎn).

2) 如何構(gòu)建符合實(shí)際問(wèn)題約束函數(shù),文獻(xiàn)[14,17?18]采用了大量的約束,但文獻(xiàn)中仍假設(shè)無(wú)人機(jī)具有相同航程,不變的速度;雖然簡(jiǎn)化了問(wèn)題的復(fù)雜度,但忽略了實(shí)際戰(zhàn)場(chǎng)中異構(gòu)UAV 自身不同的性能.因此構(gòu)建合理實(shí)際的約束函數(shù)才更符合真實(shí)優(yōu)化目標(biāo)的需要.

為解決這些難點(diǎn),本文提出適用于三維環(huán)境下多無(wú)人機(jī)協(xié)同目標(biāo)分配的近似聚類混合雙策略差分進(jìn)化算法(Approximate clustering dual-strategy differential evolution algorithm,AC-DSDE).該方法有助于平衡種群的多樣性與收斂性;然后,結(jié)合歸檔技術(shù)的代間變異方法取代原來(lái)的隨機(jī)滅絕,以增加搜索覆蓋范圍的可控性;最后,構(gòu)建加權(quán)混合適應(yīng)度函數(shù),在文獻(xiàn)[22]的基礎(chǔ)上,限制無(wú)人機(jī)載彈量,即限制無(wú)人機(jī)可執(zhí)行的任務(wù)數(shù).其方法的主要特征和優(yōu)點(diǎn)描述如下:

1) 首先,根據(jù)父代種群適應(yīng)度值將個(gè)體分成“開發(fā)性個(gè)體”與“探索性個(gè)體”兩個(gè)子種群,“探索性個(gè)體”能夠有效識(shí)別問(wèn)題空間中的最優(yōu)解區(qū)域;“開發(fā)性個(gè)體”能夠加速優(yōu)化收斂的速度.通過(guò)這種方式,在進(jìn)化過(guò)程中可以根據(jù)不同性質(zhì)的個(gè)體指導(dǎo)種群的進(jìn)化.其次,采用混合雙策略變異方案,使每個(gè)個(gè)體根據(jù)搜索進(jìn)程,動(dòng)態(tài)調(diào)整變異策略,有助于探索性與開發(fā)性達(dá)到平衡.然后,結(jié)合歸檔技術(shù)與代間變異率來(lái)儲(chǔ)存一定數(shù)量的較優(yōu)收斂的個(gè)體,避免進(jìn)化過(guò)程中種群的隨機(jī)變異,導(dǎo)致已經(jīng)搜索到的優(yōu)解變得無(wú)效;同時(shí)建立選擇概率函數(shù),選擇一定數(shù)量的“探索性個(gè)體”與“開發(fā)性個(gè)體”,有助于收斂的過(guò)程中跳出局部最優(yōu)解.

2) 構(gòu)建加權(quán)混合適應(yīng)度函數(shù),將估計(jì)航程代價(jià)、航程時(shí)間和約束違背量之和作為適應(yīng)度函數(shù);加入載彈量約束,限制無(wú)人機(jī)巡游模式中執(zhí)行目標(biāo)數(shù),將問(wèn)題的約束作為懲罰函數(shù)應(yīng)用于進(jìn)化算法的重要評(píng)價(jià)階段,使得運(yùn)行過(guò)程更加符合真實(shí)的戰(zhàn)爭(zhēng)環(huán)境.

1 相關(guān)工作

1.1 差分進(jìn)化算法

差分進(jìn)化(Differential evolution algorithm,DE)算法[17]類似于很多經(jīng)典的進(jìn)化算法,是一種高效的全局優(yōu)化算法.種群中每個(gè)個(gè)體對(duì)應(yīng)一個(gè)解向量,通過(guò)不同的突變策略產(chǎn)生新的個(gè)體,交叉算子根據(jù)個(gè)體與目標(biāo)個(gè)體進(jìn)行混合,生成實(shí)驗(yàn)個(gè)體;選擇算子根據(jù)實(shí)驗(yàn)個(gè)體的適應(yīng)度值與目標(biāo)個(gè)體的適應(yīng)度值相比較,決定下一代個(gè)體.在算法終止前,變異、交叉和選擇構(gòu)成了DE 的主循環(huán).

1.1.1 初始化種群

在解空間中隨機(jī)均勻生成NP個(gè)個(gè)體:

式(1)與式(2)中NP代表種群的大小,D表示解空間的維度,表示種群中第i個(gè)“個(gè)體”的第j個(gè)“基因”的下界,表示種群中第i個(gè)“個(gè)體”的第j個(gè)“基因”的上界,xj,i(0) 表示第0 代中第i個(gè)“個(gè)體”的第j個(gè)“基因”,rand(0,1)表示在(0,1)區(qū)間內(nèi)均勻分布的隨機(jī)數(shù).

1.1.2 變異

初始化種群后,DE 算法通過(guò)變異算子從種群中隨機(jī)選取兩個(gè)個(gè)體作差,所得的差向量加權(quán)后與第三個(gè)個(gè)體求和產(chǎn)生變異個(gè)體;其中,針對(duì)不同的問(wèn)題有不同的變異策略,這些變異策略影響著種群的進(jìn)化.下面列出了5 種常用的變異策略:

1) DE/rand/1

式(3)～ 式(7)中,r1,r2,r3,r4,r5 是在[1,N]中隨機(jī)選取的5 個(gè)整數(shù)且r5,xi(g) 表示第g代種群中第i個(gè)個(gè)體,xj,best(g)表示第g代種群中最好的個(gè)體,vj,i(g+1) 表示變異個(gè)體.參數(shù)F是縮放因子,F值的大小直接影響算法的全局尋優(yōu)能力.F越小,算法對(duì)覆蓋問(wèn)題空間精細(xì)搜索能力更好,但收斂速度會(huì)變慢.F越大,收斂速度更快,算法能夠跳出局部最優(yōu),但可能出現(xiàn)丟解的情況;同時(shí)F值的大小影響種群的多樣性[17].

1.1.3 交叉

在變異之后,DE 通常執(zhí)行二項(xiàng)式交叉操作,交叉是由交叉率CR決定,其從xj,i(g) 和vj,i(g+1) 進(jìn)行部分交換以形成新的試驗(yàn)向量uj,i(g+1) :

式(8)中,CR是交叉率,決定子代、父代與中間變異體之間交換個(gè)體基因大小程度.CR的值越大,種群的多樣性隨之增加;CR的值越小,種群的多樣性也會(huì)減少,不利于全局尋優(yōu).

1.1.4 選擇

DE 采用貪婪算法來(lái)選擇進(jìn)入下一代種群的個(gè)體,該算子從試驗(yàn)向量uj,i(g+1) 和原始向量xj,i(g)中選擇更好的個(gè)體進(jìn)入下一代:

式(9)中,f(x) 是根據(jù)具體問(wèn)題構(gòu)建的適應(yīng)度函數(shù).例如,構(gòu)建目標(biāo)函數(shù),對(duì)于求最大化問(wèn)題時(shí),具有較高適應(yīng)值的向量被選擇到下一代.

1.2 MUCTAOP

多無(wú)人機(jī)協(xié)同目標(biāo)分配最優(yōu)問(wèn)題,旨在多任務(wù)分配過(guò)程中求解最小的航程代價(jià).文獻(xiàn)[18]指出多機(jī)協(xié)同目標(biāo)分配是一個(gè)多模式、多約束、計(jì)算難度大,雜度呈幾何級(jí)增長(zhǎng)的最優(yōu)化NP 問(wèn)題.這就要求必須對(duì)目標(biāo)分配問(wèn)題進(jìn)行統(tǒng)一建模,明確飛行器執(zhí)行的層次和階段,才能獲得較好的分配結(jié)果.

Ramirez 等[2]提出了加權(quán)隨機(jī)策略生成突變的新個(gè)體,該策略將搜索的重點(diǎn)放在找到解空間中最好的解,雖然提高了收斂速度,但忽略了種群的多樣性.Ramirez-Atencia 等[19]提出多目標(biāo)遺傳算法解決協(xié)同分配問(wèn)題,該方法通過(guò)變量?jī)蓛山M合(飛行距離、飛行時(shí)間、飛行數(shù)量、燃料消耗),根據(jù)評(píng)級(jí)的方式,獲得了較好的分配方案.Wang 等[20]以智能體加速度作為控制輸入,考慮了限制加速度和速度的物理約束,提出了基于梯度的算法以最小化性能度量并確定最佳軌跡.魏政磊等[21]采用了灰狼優(yōu)化(GWO)算法對(duì)多無(wú)人機(jī)任務(wù)分配模型進(jìn)行求解,該方法在二維仿真場(chǎng)景中取得了較好的效果,但未考慮三維復(fù)雜場(chǎng)景.Zhao 等[22]研究了三維環(huán)境中多機(jī)協(xié)同統(tǒng)一分配方法.建立仿真戰(zhàn)場(chǎng)環(huán)境,在研究三維環(huán)境中多無(wú)人機(jī)協(xié)同目標(biāo)分配具有較好的指導(dǎo)作用;因此本文在該建模的基礎(chǔ)上進(jìn)行擴(kuò)展,加入了無(wú)人機(jī)載彈約束,即限定了無(wú)人機(jī)可執(zhí)行目標(biāo)點(diǎn)的個(gè)數(shù).

MUCTAOP 的場(chǎng)景具體描述為在復(fù)雜的三維環(huán)境中攻擊一組目標(biāo)的一組無(wú)人機(jī)N={U1,U2,···,Un}.該問(wèn)題的目的是找到一組分配序列M={T1,T2,···,Tm},其具有最短的估計(jì)航程代價(jià)、最短的飛行時(shí)間和最小的約束違背.其典型的場(chǎng)景和仿真環(huán)境如圖1 所示.

圖1 中三維仿真場(chǎng)景包含10 架UAVs 和10 個(gè)目標(biāo)點(diǎn),圓圈代表無(wú)人機(jī)的位置坐標(biāo),五角星代表目標(biāo)點(diǎn)的位置坐標(biāo),威脅障礙物包括山地形與雷達(dá)輻射區(qū)(半球型)的結(jié)合.無(wú)人機(jī)與目標(biāo)點(diǎn)的對(duì)應(yīng)關(guān)系由垂直切面與山地形的交線和可飛行航跡組成,即為圖中顯示的實(shí)線部分.

圖1 MUCTA 在三維任務(wù)環(huán)境中的場(chǎng)景Fig.1 Simulation diagram of MUCTA in a three-dimensional environment

2 AC-DSDE For MUCTAOP

2.1 隨機(jī)分組和自選分組

在解決多機(jī)協(xié)同目標(biāo)分配時(shí),種群中的個(gè)體即為備選解,備選解的優(yōu)劣直接影響搜索算法尋優(yōu)效率的高低.因此在進(jìn)化之前需要對(duì)種群進(jìn)行有效地劃分.劃分方法有兩種:隨機(jī)分組和自選分組;種群中個(gè)體隨機(jī)分組,旨在種群中的個(gè)體盡可能探索到種群的未知區(qū)域,對(duì)空間有較大的覆蓋性.但是該方法不能快速搜索到最優(yōu)解,甚至出現(xiàn)不收斂的現(xiàn)象.例如Crowding 聚類小生境方法[24],該方法引入了新的參數(shù)CS(聚類大小),設(shè)置參考點(diǎn)R,在種群中找到最近的個(gè)體X到R,X及其最近的CS?1 個(gè)體形成新的子種群,流程如算法2 所示:

自選分組方法如Speciation 聚類小生境方法[24?25].本文結(jié)合該方法引入父代種群的適應(yīng)度值,從每一代中,選取整數(shù)作為聚類大小CS,小生境數(shù)為NP/CS.將父代種群適應(yīng)度值進(jìn)行排序,最好的個(gè)體定義為參考點(diǎn),參考點(diǎn)及其近鄰CS?1 個(gè)個(gè)體形成新的子種群,流程如算法3 所示:

從“探索性”子種群中挑選個(gè)體可以幫助保持種群的多樣性,從“開發(fā)性”子種群中選擇個(gè)體可以幫助快速收斂到最優(yōu)個(gè)體.具體操作方法如下:將整個(gè)種群劃分為若干個(gè)子種群,然后根據(jù)個(gè)體的適應(yīng)度將每個(gè)子種群細(xì)分為數(shù)量相等的部分.如圖2 所示,父代種群中包含“探索性個(gè)體”和“開發(fā)性個(gè)體”,首先將父代種群進(jìn)行排序,設(shè)定聚類大小為CS=2,形成兩個(gè)子種群.

2.2 動(dòng)態(tài)混合進(jìn)化策略

上節(jié)已經(jīng)將種群劃分成“探索性”與“開發(fā)性”兩種不同的子種群.探索初期,隨機(jī)搜索的探索性應(yīng)該比精細(xì)化搜索的開發(fā)性比重大,選用DE/rand/2 快速識(shí)別空間中最優(yōu)解的區(qū)域,然后選用DE/best/2 優(yōu)化收斂的速度,確保在搜索的最后階段,精細(xì)搜索趨于主導(dǎo)地位.因此,探索性與開發(fā)性得到了平衡,算法的整體性能得到了提高.混合策略產(chǎn)生新個(gè)體如式(10)所示:

此外,之前曾分析過(guò)縮放因子F值的大小直接影響算法的全局尋優(yōu)能力.F越小,算法對(duì)覆蓋問(wèn)題空間精細(xì)搜索能力更好,但收斂速度會(huì)變慢.F越大,收斂速度更快,算法能夠跳出局部最優(yōu);因此,在產(chǎn)生新個(gè)體的過(guò)程中,設(shè)定動(dòng)態(tài)縮放因子Fd代替靜態(tài)縮放因子F非常重要.Fd設(shè)置如式(11)所示:

圖2 個(gè)體分組Fig.2 Individual grouping

2.3 歸檔技術(shù)

本節(jié)結(jié)合了代間變異率與歸檔技術(shù)取代了原先的隨機(jī)重置,以增加搜索范圍的可控性.在進(jìn)化過(guò)程中,最優(yōu)解在整個(gè)種群中反映的信息量較低,隨著迭代次數(shù)的增加而極可能被覆蓋,使之前的搜索變得無(wú)效,導(dǎo)致信息的不連貫和資源浪費(fèi).因此在世代間滅絕操作時(shí),建立合理的選擇算子概率模型與使用歸檔技術(shù)非常有必要.在存檔中保存當(dāng)前種群中一定數(shù)量的較優(yōu)個(gè)體,將其它的普通個(gè)體全部重置,直到搜索結(jié)束.保存收斂的個(gè)體和代間變異可能找到的最優(yōu)解,避免種群突變帶來(lái)的資源浪費(fèi).

選擇算子概率如式(12)所示,適應(yīng)度越大的個(gè)體被選中的概率越大,同時(shí)設(shè)置代間變異率(Intergenerational mutation rate,IGMR)為0.3.該方法能避免進(jìn)化過(guò)程中優(yōu)秀個(gè)體的徹底消亡,在保持種群多樣性的同時(shí),也加速了收斂速度.

圖3 (a)表示每代計(jì)算的個(gè)體適應(yīng)度值,經(jīng)過(guò)選擇算子計(jì)算后得出較好的收斂個(gè)體存儲(chǔ)在歸檔庫(kù)圖3 (b)中.

2.4 完整AC-DSDE 算法框架如下:

圖3 個(gè)體分組Fig.3 Individual grouping

2.5 目標(biāo)分配模式

多機(jī)協(xié)同目標(biāo)分配可按UAVs 和目標(biāo)點(diǎn)對(duì)應(yīng)數(shù)量進(jìn)行分類.本文中取N,M分別代表無(wú)人機(jī)的數(shù)量與目標(biāo)點(diǎn)的數(shù)量,按數(shù)量對(duì)應(yīng)關(guān)系可分成以下三種不同的模式[22]:

1) 模式1:當(dāng)N=M時(shí),該模式任務(wù)分配關(guān)系較為簡(jiǎn)單,每架UAV 分配一個(gè)目標(biāo)點(diǎn),每個(gè)目標(biāo)點(diǎn)分配一架UAV,UAV 與目標(biāo)點(diǎn)是一一對(duì)應(yīng)的關(guān)系;該模式計(jì)算復(fù)雜度較低,求解的關(guān)鍵在于分配過(guò)程中如何避免目標(biāo)競(jìng)爭(zhēng)引發(fā)的沖突,如何利用協(xié)同降低毀傷概率,使總的適應(yīng)度值最大.

2) 模式2:當(dāng)N>M時(shí),該模式任務(wù)分配關(guān)系較為復(fù)雜,每一個(gè)目標(biāo)點(diǎn)可以分配多架無(wú)人機(jī),每架無(wú)人必須執(zhí)行一個(gè)目標(biāo)點(diǎn),UAVs 與目標(biāo)點(diǎn)是多對(duì)一的關(guān)系;該模式對(duì)應(yīng)關(guān)系不平衡,導(dǎo)致計(jì)算復(fù)雜度較高,問(wèn)題求解的關(guān)鍵在于嚴(yán)格的時(shí)間約束導(dǎo)致多機(jī)協(xié)同困難.

3) 模式3:當(dāng)N

2.5.1 分配模式統(tǒng)一建模

多機(jī)協(xié)同目標(biāo)分配等同于運(yùn)籌學(xué)中的指派問(wèn)題.現(xiàn)假設(shè)有N架無(wú)人機(jī),打擊M個(gè)分布在不同位置的目標(biāo).要求構(gòu)建目標(biāo)函數(shù)考慮航程距離最短、總飛行時(shí)間最少和約束違背最小,并且能夠統(tǒng)一處理N=M、N>M和N

其中,d(i,j)是無(wú)人機(jī)i到目標(biāo)點(diǎn)j的距離,該距離利用垂直切面法估算航程代替直線,該方法雖然不是最短的航程,但是充分考慮了三維地形信息,比直線距離更接近最優(yōu)航程;wj是目標(biāo)j的權(quán)重且0

2.5.2 協(xié)同約束函數(shù)及協(xié)調(diào)關(guān)系:

1) UAV 與目標(biāo)點(diǎn)決策變量約束:當(dāng)N ≥M時(shí),UAVs 數(shù)量大于等于目標(biāo)點(diǎn)的數(shù)量,此時(shí)任務(wù)決策為:每架UAV 必須執(zhí)行一個(gè)目標(biāo)點(diǎn),每個(gè)目標(biāo)點(diǎn)必須被一架UAV 執(zhí)行;當(dāng)N

式(15)和式(16)分別表示了兩種不同決策對(duì)應(yīng)的關(guān)系.

2) 最大航程約束D(km) :不同的模式下,最大航程代價(jià)指所有分配關(guān)系的估計(jì)航程代價(jià)的總和;該約束體現(xiàn)了各UAVs 自身性能,比如油耗、有效通信等.

式(17) 中d(i,j) 表示估計(jì)航程代價(jià),Di表示各UAVs 的限定的最大航程距離;式(18)表示無(wú)人機(jī)i執(zhí)行任務(wù)j,若無(wú)人機(jī)i超出其自身限定的最大航程距離將對(duì)其進(jìn)行懲罰.

3) UAVs 最小/最大速度約束V(km/h) :

式(19) 中V(i)min表示無(wú)人機(jī)i的最小速度,V(i)max表示無(wú)人機(jī)i的最大速度;式(20)表示若無(wú)人機(jī)i超出限定的最小速度或者最大速度將對(duì)其進(jìn)行懲罰.

4) 最大航行時(shí)間約束T(h) :表示協(xié)同分配結(jié)果中執(zhí)行目標(biāo)耗費(fèi)時(shí)間最長(zhǎng)的無(wú)人機(jī),最大航行時(shí)間也是規(guī)劃完成的標(biāo)志.

根據(jù)式(17)最大航程約束與式(19)最大、最小速度約束,可以計(jì)算出最大航行時(shí)間;式(22)表示若無(wú)人機(jī)i實(shí)際航行時(shí)間超出其限定的最大航行時(shí)間將對(duì)其進(jìn)行懲罰.

5) UAVs 最大載彈量約束Umissile:該約束體現(xiàn)了UAVs 最大載彈量.即在模式3)中,單架無(wú)人機(jī)在巡游過(guò)程中執(zhí)行任務(wù)數(shù)量不可以超過(guò)其有效地載荷量.

式(23)表示無(wú)人機(jī)i的載彈量應(yīng)小于其最大的載彈量;式(24)表示若無(wú)人機(jī)i的載彈量超過(guò)其最大載彈量將對(duì)其進(jìn)行懲罰.

6) 目標(biāo)點(diǎn)之間的時(shí)序約束Tsort:該約束體現(xiàn)了目標(biāo)點(diǎn)之間的執(zhí)行順序,重要的目標(biāo)點(diǎn)必須優(yōu)先執(zhí)行,其他目標(biāo)點(diǎn)根據(jù)其約束依次執(zhí)行;

式(25)表示目標(biāo)點(diǎn)j必須晚于目標(biāo)點(diǎn)j+τ執(zhí)行,τ為正整數(shù).式(26)表示若目標(biāo)點(diǎn)Tj,Tj+τ不符合限定執(zhí)行次序則進(jìn)行懲罰.

7) 等待時(shí)間約束Twait:為了確保模式一與模式二中部分UAVs 同時(shí)到達(dá)指定目標(biāo),允許部分UAVs 等待一段時(shí)間后再出發(fā).

式(27) 限定各無(wú)人機(jī)到達(dá)目標(biāo)的等待時(shí)間;式(28)表示各目標(biāo)點(diǎn)被攻擊時(shí)間的交集不可超過(guò)時(shí)間段σ,通常σ時(shí)間段認(rèn)為是極小的,可根據(jù)真實(shí)戰(zhàn)場(chǎng)勢(shì)態(tài)進(jìn)行調(diào)整.

該模型針對(duì)三種不同分配模式建立了統(tǒng)一的分配關(guān)系.將航程代價(jià)、時(shí)間代價(jià)與約束違背量之和作為適應(yīng)度函數(shù).在進(jìn)化前,建立UAVs 與目標(biāo)點(diǎn)的估計(jì)航程代價(jià)庫(kù),進(jìn)化時(shí)通過(guò)查找估計(jì)航程代價(jià)矩陣,可以大幅提高計(jì)算效率.

3 實(shí)驗(yàn)結(jié)果和分析

為驗(yàn)證改進(jìn)后的AC-DSDE 算法處理MUCTAOP 有效性,本文在Matlab R2016a 進(jìn)行多組仿真實(shí)驗(yàn).實(shí)驗(yàn)包括以下部分:1) 選取數(shù)量較少的UAVs 和目標(biāo)點(diǎn)驗(yàn)證改進(jìn)算法的有效性;2) 選取數(shù)量較多的UAVs 和目標(biāo)點(diǎn)驗(yàn)證改進(jìn)算法能夠有效處理復(fù)雜環(huán)境下目標(biāo)分配;3) 將改進(jìn)的AC-DSDE與同類算法進(jìn)行比較.

表1 中“Upos”、“Tpos”、“Rpos”分別表示無(wú)人機(jī)、目標(biāo)點(diǎn)和雷達(dá)的坐標(biāo);“W”表示各目標(biāo)點(diǎn)的權(quán)重;

表2 設(shè)定了兩組不同實(shí)驗(yàn)參數(shù).“Un”表示UAVs 的數(shù)量,“Tn”表示目標(biāo)點(diǎn)的數(shù)量,“Pn”表示種群的規(guī)模,“Gen”代表進(jìn)化迭代次數(shù).因?yàn)椴罘诌M(jìn)化算法是隨機(jī)搜索算法,為了驗(yàn)證解的一致性,本文設(shè)置“Num”參數(shù)對(duì)同一情境下進(jìn)行多次實(shí)驗(yàn).

3.1 驗(yàn)證改進(jìn)算法的有效性

圖4 顯示了實(shí)驗(yàn)1 分配結(jié)果,其中圓圈代表UAVs 的三維坐標(biāo),星形代表目標(biāo)點(diǎn)三維坐標(biāo);同時(shí),本文將每個(gè)坐標(biāo)進(jìn)行編號(hào),以便后續(xù)統(tǒng)計(jì)分配數(shù)據(jù).從圖中看出基于AC-DSDE 算法的多機(jī)協(xié)同分配能夠在多雷達(dá)區(qū)域和目標(biāo)點(diǎn)隨機(jī)分布的三維環(huán)境中,充分結(jié)合了整體山地形,有效地處理三種不同模式下的分配問(wèn)題.

表3 表示實(shí)驗(yàn)1 中三種不同模式下無(wú)人機(jī)與目標(biāo)點(diǎn)最優(yōu)分配的結(jié)果;其中UAV 表示UAVs 分配序列,Target 表示對(duì)應(yīng)的目標(biāo)點(diǎn)分配序列,Cost 是UAV 與Target 對(duì)應(yīng)的總航程代價(jià),包含了航行距離、飛行時(shí)間等.同時(shí),仿真數(shù)據(jù)均符合三種模式無(wú)人機(jī)與目標(biāo)點(diǎn)之間的對(duì)應(yīng)關(guān)系.圖4 與表3 表明了改進(jìn)的AC-DSDE 算法能夠有效處理三種不同的模式,并找到相對(duì)應(yīng)的分配方案.

3.2 驗(yàn)證算法處理復(fù)雜環(huán)境的有效性

為驗(yàn)證算法處理復(fù)雜環(huán)境的有效性,本節(jié)中選取了5 個(gè)評(píng)價(jià)指標(biāo)對(duì)算法的性能進(jìn)行評(píng)價(jià):

表1 實(shí)驗(yàn)初始數(shù)據(jù)Table 1 Initialization of experimental data

表2 兩組實(shí)驗(yàn)進(jìn)化參數(shù)的設(shè)定Table 2 Setting of experimental evolution parameters of two groups

3) 最優(yōu)代價(jià)Cbest:多組實(shí)驗(yàn)中最小代價(jià)值;

4) 約束違背:最優(yōu)解中約束違背量總和占最優(yōu)代價(jià)的百分比,該評(píng)價(jià)指標(biāo)衡量了算法的協(xié)同性能.

5)“優(yōu)解”表示陷入局部最優(yōu)的次數(shù)和當(dāng)前優(yōu)于平均代價(jià)的次數(shù)占實(shí)驗(yàn)總次數(shù)的百分比.

其中,平均代價(jià)和最優(yōu)代價(jià)都是綜合了航程代價(jià)、時(shí)間代價(jià)和各種約束違背量的適應(yīng)度值.

表4 分別統(tǒng)計(jì)了實(shí)驗(yàn)1 與實(shí)驗(yàn)2 的數(shù)據(jù),可以得出以下結(jié)論:

圖4 三維環(huán)境中實(shí)驗(yàn)1 的仿真結(jié)果Fig.4 Simulation results of Experiment 1 in a three-dimensional environment

圖5 三維環(huán)境中實(shí)驗(yàn)2 的仿真結(jié)果Fig.5 Simulation results of Experiment 2 in a three-dimensional environment

表3 實(shí)驗(yàn)1 的分配結(jié)果Table 3 Assignment results of Experiment 1

圖6 實(shí)驗(yàn)1 分配結(jié)果的單條收斂曲線Fig.6 Single convergence curve of Experiment 1 assignment results

1) 實(shí)驗(yàn)1 算法運(yùn)行時(shí)間較短,且能得到較好的分配結(jié)果,數(shù)據(jù)表明所提出的AC-DSDE 算法能夠有效地處理不同模式下的多無(wú)人機(jī)協(xié)同目標(biāo)分配問(wèn)題;

表4 兩組實(shí)驗(yàn)分配結(jié)果的統(tǒng)計(jì)數(shù)據(jù)Table 4 Statistics of the results of the two groups of experimental assignments

圖7 實(shí)驗(yàn)1 分配結(jié)果的單條和平均收斂曲線對(duì)比Fig.7 Comparison of the single and average convergence curves of the results of Experiment 1

2) 實(shí)驗(yàn)2 盡管增加了UAVs 與目標(biāo)點(diǎn)的數(shù)量,算法中的執(zhí)行效率有所降低,但是AC-DSDE 在有效的時(shí)間內(nèi)搜索到最優(yōu)解.

3) 各模式中平均代價(jià)值與最優(yōu)代價(jià)值接近,表明改進(jìn)算法搜索的結(jié)果接近全局最優(yōu)解.

4) 較小的協(xié)同違背率證明改進(jìn)算法協(xié)同能力較強(qiáng).較高的優(yōu)解率說(shuō)明了實(shí)驗(yàn)發(fā)現(xiàn)最優(yōu)解的可能性較大.

3.3 AC-DSDE 算法的性能

表5 AC-DSDE 與其他算法之間的比較Table 5 Comparison between AC-DSDE and other algorithms

圖8 不同算法的平均收斂曲線Fig.8 Average convergence curve of different algorithms

本節(jié)將從單次實(shí)驗(yàn)收斂曲線與多組實(shí)驗(yàn)平均收斂曲線進(jìn)一步研究AC-DSDE 算法處理多無(wú)人機(jī)協(xié)同目標(biāo)分配的性能.

1) 單次實(shí)驗(yàn)收斂曲線與多組實(shí)驗(yàn)平均收斂曲線

圖6 中實(shí)線表示單次實(shí)驗(yàn)的收斂曲線,并且顯示改進(jìn)算法進(jìn)化迭代過(guò)程中的最優(yōu)解以及代間變異隨機(jī)搜索到的最優(yōu)解,分別用圓圈與星號(hào)表示.從收斂曲線可以看出代間變異不僅增加了種群的多樣性,而且找到了更多的優(yōu)解.圖7 是單收斂曲線與平均收斂曲線的對(duì)比,單收斂曲線和平均收斂曲線具有相似的收斂趨勢(shì),搜索前期能夠快速收斂到優(yōu)解區(qū)域,后期能夠很快地收斂到最優(yōu)解.因此ACDSDE 具有較好的收斂性能.

2) AC-DSDE 與同類目標(biāo)分配算法之間的比較

本節(jié)將改進(jìn)后的AC-DSDE 算法、DMDE 算法[22]與APC-DE 算法[26]進(jìn)行比較.實(shí)驗(yàn)所采用的進(jìn)化參數(shù)、種群規(guī)模、迭代次數(shù)相同.表5 中,變量CR表示交叉率,變量MR 表示變異率,變量IGMR 為DE 算法的代間變異率.圖8 是不同算法的平均收斂曲線,表5 和圖8 顯示,AC-DSDE 算法總的航程代價(jià)值最小,收斂速度最快,執(zhí)行時(shí)間最短.盡管其他兩種算法都能在一定的時(shí)間內(nèi)找到最優(yōu)解,但總的航程代價(jià)值較高且需要更長(zhǎng)的執(zhí)行時(shí)間.

4 總結(jié)

本文提出了基于AC-DSDE 混合雙策略差分進(jìn)化算法以解決無(wú)人機(jī)協(xié)同目標(biāo)優(yōu)化分配.首先,為了提高算法的性能,提出了混合雙策略動(dòng)態(tài)變異的方法.該方法根據(jù)不同類型的個(gè)體選用不同的變異策略,同時(shí)構(gòu)建動(dòng)態(tài)縮放因子Fd,解決目前進(jìn)化過(guò)程中存在的探索性和開發(fā)性平衡的問(wèn)題.然后結(jié)合歸檔技術(shù)與代間變異方法,在增加了種群的多樣性的同時(shí),也保證了收斂個(gè)體不會(huì)隨著迭代次數(shù)消亡.最后擴(kuò)展原有的約束條件,增加了UAVs 的載彈量約束,限制UAVs 可執(zhí)行的目標(biāo)個(gè)數(shù).仿真實(shí)驗(yàn)表明,該方法能夠有效快速地解決多無(wú)人機(jī)協(xié)同目標(biāo)分配問(wèn)題,且協(xié)同能力強(qiáng).

對(duì)于下一步工作,將著重考慮差分進(jìn)化算法在多無(wú)人機(jī)協(xié)同航跡規(guī)劃方法的研究,如何有效降低三維空間復(fù)雜度,獲得關(guān)鍵路徑點(diǎn)的集合,保證最終航跡是安全且可行.