張鴻運(yùn), 王 磊, 張 旭, 丁 宇, 呂 琛, 王昕煒

(1. 大連理工大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024; 2. 可靠性與環(huán)境技術(shù)重點(diǎn)實(shí)驗(yàn)室, 北京 100191;3. 北京航空航天大學(xué)可靠性研究所, 北京 100191; 4. 北京航空航天大學(xué)可靠性與系統(tǒng)工程學(xué)院,北京 100191; 5. 大連理工大學(xué)工程力學(xué)系, 遼寧 大連 116023; 6. 大連理工大學(xué)工業(yè)裝備結(jié)構(gòu)分析國家重點(diǎn)實(shí)驗(yàn)室, 遼寧 大連 116023)

0 引 言

隨著智能型電子計算機(jī)技術(shù)的發(fā)展,具有高靈活性、高自主性和高智能性的無人機(jī)技術(shù)迅速成熟起來。在面對突變的戰(zhàn)場態(tài)勢時,無人機(jī)可以自主決策[1],大大改進(jìn)了無人機(jī)生存能力低的問題,提高了無人機(jī)在作戰(zhàn)中的應(yīng)用優(yōu)勢。無人機(jī)的制造成本與壽命周期維護(hù)費(fèi)用遠(yuǎn)比訓(xùn)練高效的飛機(jī)作戰(zhàn)人員低。應(yīng)用無人機(jī)替代有人機(jī)，可以避免作戰(zhàn)人員在緊張情況下出現(xiàn)操作失誤,執(zhí)行偵查敵方復(fù)雜環(huán)境、打擊高危目標(biāo)等任務(wù)時可以避免人員傷亡。此外，無人機(jī)還具備體積小、靈活性強(qiáng)、隱蔽性好、續(xù)航時間長等特點(diǎn),在實(shí)際作戰(zhàn)中發(fā)揮著至關(guān)重要的作用[2]。相比中大型無人機(jī),小型無人機(jī)因其優(yōu)異的突防能力,被廣泛地用于實(shí)際作戰(zhàn)中。但是，單個小型無人機(jī)的執(zhí)行能力有限,在執(zhí)行任務(wù)過程中面臨偵查范圍小、執(zhí)行任務(wù)耗時長、攻擊力弱等問題,導(dǎo)致作戰(zhàn)任務(wù)無法高效完成。因此，無人機(jī)蜂群協(xié)同作戰(zhàn)應(yīng)運(yùn)而生[3],其不僅可提高任務(wù)完成的速度和質(zhì)量,而且可以通過動態(tài)調(diào)整任務(wù)分配以應(yīng)對突發(fā)狀況的出現(xiàn)[4]。為保證小型無人機(jī)蜂群協(xié)同作戰(zhàn)任務(wù)的高效完成,有必要對相應(yīng)的任務(wù)分配技術(shù)開展深入的研究[5]。

目前,國內(nèi)外不少學(xué)者已經(jīng)對多無人機(jī)協(xié)同作戰(zhàn)任務(wù)分配問題進(jìn)行了研究[6]。文獻(xiàn)[7]針對異構(gòu)無人機(jī)編隊(duì)在反雷達(dá)作戰(zhàn)中的協(xié)同任務(wù)分配問題,提出了一種考慮時間窗的改進(jìn)混合整數(shù)線性規(guī)劃任務(wù)分配算法。文獻(xiàn)[8]針對環(huán)境中的風(fēng)險,構(gòu)造了一種新的分配問題的隨機(jī)公式,提出了兩種動態(tài)規(guī)劃近似方法(一步法和兩步前瞻法)，對構(gòu)建的動態(tài)規(guī)劃問題進(jìn)行求解。文獻(xiàn)[9]擴(kuò)展了用于連接網(wǎng)絡(luò)的基線算法處理無人機(jī)通信范圍有限的問題,提出了基于市場的分散分配算法。但是，傳統(tǒng)的優(yōu)化算法[10-12]只適用于求解小規(guī)模任務(wù)分配問題。在實(shí)際多無人機(jī)協(xié)同作戰(zhàn)任務(wù)分配問題中，存在著多種約束條件,如無人機(jī)攻擊次數(shù)約束[13]、任務(wù)時序約束[14]、可飛行軌跡約束[15]等,將所有的約束條件整合到任務(wù)分配模型中會導(dǎo)致非確定多項(xiàng)式難題[16],計算的復(fù)雜度會隨著求解規(guī)模的增大呈指數(shù)增長。新興的智能優(yōu)化算法[17]不僅能夠降低計算量,而且在有限時間內(nèi)能快速找到問題的最優(yōu)解,因此許多學(xué)者使用遺傳算法[18-19]、蟻群算法[20-21]、果蠅算法[22]、粒子群優(yōu)化算法[23]、狼群算法[24]等求解多無人機(jī)協(xié)同任務(wù)分配問題。為了提高求解效率,部分學(xué)者對現(xiàn)有智能算法加以改進(jìn),或進(jìn)行復(fù)合[25]。文獻(xiàn)[26]在求解多無人機(jī)偵察任務(wù)分配問題時,通過對傳統(tǒng)蟻群算法進(jìn)行改進(jìn),將信息素分為隸屬信息素和序列信息素,同時引入負(fù)反饋機(jī)制加速算法收斂,該算法綜合考慮不同無人機(jī)的性能和異構(gòu)目標(biāo)的特點(diǎn)，但未考慮需要對目標(biāo)執(zhí)行多個任務(wù)，以及任務(wù)之間存在時序的情況。文獻(xiàn)[27]在求解多功能異構(gòu)無人機(jī)任務(wù)分配問題時,通過引入多群機(jī)制提高果蠅優(yōu)化算法的全局搜索能力,在基于氣味的搜索階段進(jìn)行雙搜索策略切換,而在基于視覺的搜索階段使用貪婪選擇策略達(dá)到快速尋優(yōu)的目的,但該算法缺乏對執(zhí)行目標(biāo)差異的考慮,并且在求解大規(guī)模任務(wù)分配問題時會由于搜索強(qiáng)度不足而陷入局部最優(yōu)。文獻(xiàn)[28]根據(jù)適應(yīng)度值對粒子群進(jìn)行階層劃分,并引入獨(dú)立權(quán)重的思想提高算法的搜索能力,提出的算法可以有效求解復(fù)雜約束條件下無人機(jī)協(xié)同任務(wù)分配問題,對于實(shí)際作戰(zhàn)具有一定貢獻(xiàn)價值,但在求解大規(guī)模任務(wù)分配問題時存在局限性。在眾多的智能優(yōu)化算法中,文獻(xiàn)[29]提出的狼群算法由于具有良好的全局收斂性和計算魯棒性,并且特別適用于高維問題的求解,而在近年來被廣為研究。文獻(xiàn)[30]通過自適應(yīng)機(jī)制,將增強(qiáng)隨機(jī)分形搜索中的高斯游走引入狼群算法，提高了算法的收斂精度和魯棒性。文獻(xiàn)[31]采用基于有向圖的方法和新的元啟發(fā)式優(yōu)化方法共同改進(jìn)狼群算法,但是有向圖解鎖方式的引入會降低計算效率和收斂速度。文獻(xiàn)[32]在離散的狼群算法中融入粒子群和遺傳算法思想,提出的算法在大規(guī)模任務(wù)分配問題中表現(xiàn)出優(yōu)秀的搜索能力,但沒有考慮時序約束以及無人機(jī)和目標(biāo)的個體差異,不能有效地應(yīng)用于實(shí)際作戰(zhàn)。上述研究顯示,狼群算法能夠高效求解多無人機(jī)協(xié)同任務(wù)分配問題,且在大規(guī)模問題的求解上具有更佳的魯棒性以及效率。但是，在針對其目前的研究中,并沒有較全面地考慮實(shí)際作戰(zhàn)問題中存在的各類約束。

小型無人機(jī)由于其自身的優(yōu)良特性而被廣泛地應(yīng)用于實(shí)際作戰(zhàn)中,但是小型無人機(jī)的體積小,承載資源有限,每架小型無人機(jī)至多可執(zhí)行一次攻擊任務(wù)。此外,如果無人機(jī)反復(fù)在敵方空域執(zhí)行攻擊任務(wù),容易被敵方的反導(dǎo)系統(tǒng)鎖定,這不僅會導(dǎo)致任務(wù)執(zhí)行失敗，而且也會危及無人機(jī)自身安全。另外,由于每架小型無人機(jī)的用途需求不一致，其配備的各傳感器性能存在差異,導(dǎo)致無人機(jī)各子系統(tǒng)的裝備性能各不相同,定義的子系統(tǒng)能力矩陣直觀形象地展示出無人機(jī)在各子系統(tǒng)上的差異,并將無人機(jī)任務(wù)執(zhí)行能力和子系統(tǒng)能力聯(lián)系起來。而敵方目標(biāo)的規(guī)模大小、危險性和精密程度因其作用和所處環(huán)境的不同而不同,因此目標(biāo)要求無人機(jī)具備的最差裝備性能也各不相同,定義的目標(biāo)能力需求矩陣可直接展示出目標(biāo)任務(wù)之間的差異。然而,現(xiàn)有研究中鮮有考慮包含無人機(jī)各子系統(tǒng)執(zhí)行能力的差異以及目標(biāo)對無人機(jī)能力約束條件的無人機(jī)蜂群任務(wù)分配問題,而這些限制非常符合無人機(jī)作戰(zhàn)的實(shí)際情況。因此，有必要研究在子系統(tǒng)能力約束條件下的無人機(jī)蜂群協(xié)同任務(wù)分配問題。

本文針對異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題建模,在無人機(jī)子系統(tǒng)能力約束、任務(wù)時序約束和攻擊次數(shù)約束等多個約束條件下,最小化時間代價和資源代價。根據(jù)求解問題的特點(diǎn),提出一種基于拍賣機(jī)制的改進(jìn)狼群算法(auction mechanism based improved wolf pack algorithm,AMIWPA),引入子系統(tǒng)能力矩陣,從而實(shí)現(xiàn)無人機(jī)異構(gòu)性與任務(wù)執(zhí)行能力的統(tǒng)一描述。本文考慮對目標(biāo)執(zhí)行多個任務(wù)的情況,故采用矩陣編碼方式,為了快速求解無人機(jī)蜂群任務(wù)分配問題,在算法設(shè)計過程中融入遺傳算法思想,通過相鄰行交換操作和間隔列交叉操作實(shí)現(xiàn)個體狼的位置更新,并在狼群更新階段引入第三優(yōu)狼以增強(qiáng)種群的多樣性,有效地避免算法陷入局部最優(yōu)。此外,提出基于拍賣機(jī)制的修正策略，對違反攻擊次數(shù)約束的非可行解進(jìn)行調(diào)整。將本文提出的算法與基于拍賣機(jī)制的改進(jìn)粒子群優(yōu)化算法(auction mechanism based improved particle swarm optimization algorithm,AMIPSOA)和基于拍賣機(jī)制的改進(jìn)模擬退火算法(auction mechanism based improved simulated annealing algorithm,AMISAA)進(jìn)行對比實(shí)驗(yàn),仿真結(jié)果表明所提算法具有更好的尋優(yōu)性和收斂性。

1 模 型

1.1 問題描述

本文以小型無人機(jī)群在模擬二維戰(zhàn)場環(huán)境中對多個目標(biāo)執(zhí)行一系列任務(wù)為背景,研究多功能異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配的問題。

假設(shè)坐落在機(jī)場的Nu架小型無人機(jī)組成無人機(jī)蜂群，對敵方的Nt個目標(biāo)執(zhí)行任務(wù),無人機(jī)集合為U={U1,U2,…,UNu},目標(biāo)集合為T={T1,T2,…,TNt},需要對每個目標(biāo)依次執(zhí)行識別、攻擊和評估。對于目標(biāo)的這3類任務(wù),要么都執(zhí)行,要么都不執(zhí)行,并且任務(wù)之間必須嚴(yán)格按照順序執(zhí)行。k∈K,K={1,2,3}為對應(yīng)的任務(wù)集合(k=1代表識別任務(wù);k=2代表攻擊任務(wù);k=3代表評估任務(wù)),Nk表示需要對每個目標(biāo)執(zhí)行的任務(wù)數(shù)量。顯然，Nk=3。

在任務(wù)場景中,每架無人機(jī)都具備3個子系統(tǒng),分別為識別、攻擊和評估,M表示無人機(jī)的子系統(tǒng)集合。無人機(jī)的異構(gòu)性主要體現(xiàn)在子系統(tǒng)不同的裝備性能上,與無人機(jī)配備的傳感器有關(guān),使用子系統(tǒng)執(zhí)行能力衡量子系統(tǒng)裝備性能的好壞,進(jìn)一步評估無人機(jī)執(zhí)行任務(wù)的能力水平。例如,無人機(jī)U1配備了高分辨率視覺傳感器,無人機(jī)U2配備了低分辨率視覺傳感器,因此無人機(jī)U1識別子系統(tǒng)的執(zhí)行能力可以達(dá)到80%,即具有較強(qiáng)的目標(biāo)識別功能,無人機(jī)U2識別子系統(tǒng)的執(zhí)行能力只能達(dá)到20%,視覺傳感器的分辨率限制了無人機(jī)U2的目標(biāo)識別功能,無人機(jī)U2不能滿足對特定目標(biāo)的識別要求,如小尺寸且構(gòu)造復(fù)雜的目標(biāo)或背景環(huán)境復(fù)雜的目標(biāo)。綜上所述,無人機(jī)執(zhí)行任務(wù)的前提是必須滿足任務(wù)要求的執(zhí)行能力。

為了能直觀地反映無人機(jī)和目標(biāo)的異構(gòu)性,本文定義無人機(jī)能力矩陣Xc和目標(biāo)能力需求矩陣Xcr。無人機(jī)能力矩陣展示了每架無人機(jī)具備的子系統(tǒng)以及相應(yīng)子系統(tǒng)的能力值,從而在統(tǒng)一的框架下描述無人機(jī)的異構(gòu)性與任務(wù)執(zhí)行能力。若無人機(jī)存在某個能力水平為0的子系統(tǒng),則表明無人機(jī)不具備執(zhí)行相應(yīng)任務(wù)的能力,間接反映出無人機(jī)的異構(gòu)性;若無人機(jī)的某子系統(tǒng)能力水平大于0,則直接反映了無人機(jī)執(zhí)行任務(wù)的能力水平。通過與各目標(biāo)執(zhí)行不同任務(wù)的能力需求進(jìn)行對比,從而判斷無人機(jī)是否可以對特定目標(biāo)執(zhí)行特定任務(wù)。以5架無人機(jī)和3個目標(biāo)為例,表1和表2給出了無人機(jī)能力矩陣和目標(biāo)能力需求矩陣。對于T1的識別任務(wù),由表2可知執(zhí)行T1的識別任務(wù)要求無人機(jī)識別子系統(tǒng)達(dá)到最低能力值的60%。由表1可知,U1～U5識別子系統(tǒng)的能力值分別為60%、50%、90%、40%、30%,因此只有U1和U3有能力執(zhí)行T1的識別任務(wù)。

表1 無人機(jī)能力矩陣

表2 目標(biāo)能力需求矩陣

為了避免不確定因素對研究問題的影響,現(xiàn)作出如下假設(shè):

(1) 在任務(wù)執(zhí)行過程中,沒有禁飛區(qū)、地形障礙以及突發(fā)威脅;

(2) 目標(biāo)的地理信息是已知且靜止的;

(3) 無人機(jī)由當(dāng)前位置飛到下一位置的距離用歐式距離來計算;

(4) 無人機(jī)始終保持勻速飛行;

(5) 不同無人機(jī)執(zhí)行同一任務(wù)的耗時相同;

(6) 無人機(jī)在執(zhí)行任務(wù)過程中不會被毀壞;

(7) 無人機(jī)被分配多個不同種類任務(wù)時,執(zhí)行順序在前的同類任務(wù)優(yōu)先執(zhí)行。

1.2 代價函數(shù)

由于戰(zhàn)場環(huán)境的變化莫測,任務(wù)執(zhí)行的時間敏感性極高,因此必須在較短的時間內(nèi)完成所有任務(wù)。由于目標(biāo)任務(wù)的執(zhí)行按照識別、攻擊、評估的順序進(jìn)行,為了最小化任務(wù)完成時間,也就是盡可能讓目標(biāo)的最后一項(xiàng)任務(wù)結(jié)束時間最早,因此任務(wù)完成時間就是最晚的評估任務(wù)結(jié)束時間。同時，為了高效利用資源,應(yīng)最小化無人機(jī)消耗的燃油量。

無人機(jī)燃油量的消耗主要受飛行路程的影響,由于已假設(shè)無人機(jī)勻速飛行,飛行路程的長短可以通過飛行時間來量化,因此無人機(jī)耗油量可通過無人機(jī)總飛行時間來量化。無人機(jī)的飛行時間由兩部分組成,無人機(jī)從初始位置飛向目標(biāo)的時間和無人機(jī)從前序目標(biāo)飛向執(zhí)行目標(biāo)的時間。

定義ui k表示執(zhí)行目標(biāo)i的k任務(wù)的無人機(jī)編號;PTui k表示無人機(jī)ui k的執(zhí)行目標(biāo)i的前序目標(biāo),PTui k=0表示無人機(jī)ui k無前序目標(biāo),意味著無人機(jī)從初始位置直接飛到目標(biāo)i執(zhí)行k任務(wù);PTSui k表示無人機(jī)ui k的前序任務(wù);TOui k·i表示無人機(jī)從初始位置飛到目標(biāo)i的飛行時間;TPTui k·i表示無人機(jī)ui k從前序目標(biāo)PTui k飛到執(zhí)行目標(biāo)i的飛行時間。

因此,目標(biāo)函數(shù)為

(1)

式中:ti k表示目標(biāo)i的k(k=1,2,3)任務(wù)執(zhí)行完成時間,具體計算公式如下:

(2)

式中:定義ti·0=0。由于目標(biāo)i評估任務(wù)的開始是在識別和攻擊任務(wù)完成的基礎(chǔ)上,根據(jù)式(2)，計算ti3時需要先計算ti1和ti2。tk表示k任務(wù)的執(zhí)行時間,目標(biāo)i的k任務(wù)執(zhí)行完成時間ti k主要受到無人機(jī)ui k在前序目標(biāo)任務(wù)執(zhí)行完成時間、無人機(jī)ui k飛到目標(biāo)i的時間和目標(biāo)i的k-1任務(wù)執(zhí)行完成時間的影響。當(dāng)無人機(jī)ui k飛向目標(biāo)i執(zhí)行k任務(wù),如果TOui k·i時刻無人機(jī)ui k到達(dá)目標(biāo)i,目標(biāo)i的k-1任務(wù)未執(zhí)行完成,無人機(jī)ui k需等待目標(biāo)i的k-1任務(wù)執(zhí)行完成才能執(zhí)行k任務(wù),則無人機(jī)ui k開始執(zhí)行目標(biāo)i的k任務(wù)的時間為ti·(k-1)=max(TOui k·i,ti·(k-1)),此時無人機(jī)ui k執(zhí)行目標(biāo)i的k任務(wù)的結(jié)束時間為ti·(k-1)+tk。如果TOui k·i時刻目標(biāo)i的k-1任務(wù)已經(jīng)執(zhí)行完成,則目標(biāo)i的k任務(wù)的執(zhí)行完成時間ti k受到無人機(jī)ui k是否有前序目標(biāo)任務(wù)的影響,若無人機(jī)ui k無前序目標(biāo)任務(wù),則無人機(jī)ui k開始執(zhí)行目標(biāo)i的k任務(wù)的時間為TOui k·i=max(TOui k·i,ti·(k-1)),此時無人機(jī)ui k執(zhí)行完成目標(biāo)i的k任務(wù)的時間為TOui k·i+tk。若無人機(jī)ui k有前序目標(biāo)任務(wù),則無人機(jī)ui k開始執(zhí)行目標(biāo)i的k任務(wù)的時間為tPTui k·PTSui k+TPTui k·i=max(tPTui k·PTSui k+TPTui k·i,ti·(k-1)),此時無人機(jī)ui k執(zhí)行完成目標(biāo)i的k任務(wù)的時間為tPTui k·PTSui k+TPTui k·i+tk。

1.3 約束條件

(1) 每架無人機(jī)的攻擊次數(shù)是有限的,至多執(zhí)行一次攻擊任務(wù)。

(3)

(2) 多機(jī)協(xié)同約束,每個目標(biāo)上的多個任務(wù)可以被不同的無人機(jī)執(zhí)行,但每個任務(wù)僅由一架無人機(jī)執(zhí)行一次,且必須保證所有的任務(wù)都被執(zhí)行。

(4)

(3) 無人機(jī)子系統(tǒng)能力約束,無人機(jī)u對目標(biāo)i執(zhí)行k任務(wù)必須滿足相應(yīng)子系統(tǒng)的能力值高于目標(biāo)i的k任務(wù)要求的最低能力值。

(5)

(4) 任務(wù)時序約束ti k的計算如式(2)所示。式(2)由兩項(xiàng)構(gòu)成,前項(xiàng)是任務(wù)開始執(zhí)行時間,主要受到tPTui k·PTSui k、TPTui k·i和ti·(k-1)的影響；后項(xiàng)是任務(wù)執(zhí)行時間,tk為大于零的常數(shù)。因此，由式(2)可知,目標(biāo)i的k任務(wù)執(zhí)行結(jié)束時間一定晚于目標(biāo)i的k-1任務(wù)執(zhí)行結(jié)束時間。

1.4 問題建模

本文使用整數(shù)規(guī)劃模型描述多功能異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題,優(yōu)化所有無人機(jī)執(zhí)行任務(wù)的累計資源消耗和任務(wù)完成時間,構(gòu)建的數(shù)學(xué)模型目標(biāo)函數(shù)如式(1)所示，約束條件如式(2)～式(5)所示。

2 狼群算法原理

狼是喜愛群居生活的動物,狼群之間的團(tuán)結(jié)協(xié)作一次又一次完成了圍捕獵物活動,在捕獵活動中每個個體都有明確的社會分工。根據(jù)職責(zé)，將狼分為頭狼、探狼和猛狼。頭狼是離獵物最近的狼,感知到的獵物氣味濃度最大,是整個狼群的指揮,指揮狼群朝獵物方向行進(jìn)并迅速捕獲獵物；探狼通過對周圍環(huán)境進(jìn)行探索,朝著獵物氣味最濃的方向前進(jìn)；猛狼則負(fù)責(zé)對獵物進(jìn)行圍攻。狼群相互傳遞信息,通過分工合作完成獵物的捕抓活動,圖1展示了狼群圍捕獵物的過程?；诶侨鹤ゲ东C物的行為活動和獵物分配的規(guī)則抽象得到狼群算法。狼群算法的主體包括3種智能行為(游走行為、召喚行為、圍攻行為)和兩條規(guī)則(“勝者為王”的頭狼產(chǎn)生規(guī)則，“強(qiáng)者生存”的狼群更新機(jī)制)。

圖1 狼群捕獵過程Fig.1 Hunting process of wolves

(1) 頭狼產(chǎn)生規(guī)則

初始化狼群產(chǎn)生N只狼,選擇具有最優(yōu)目標(biāo)函數(shù)值(感知到的獵物氣味最濃)的狼作為頭狼。在迭代過程中,如果存在一只狼的目標(biāo)函數(shù)值優(yōu)于當(dāng)前的頭狼,則進(jìn)行頭狼的更新。如果同時存在多只狼的目標(biāo)函數(shù)值是更優(yōu)的,則隨機(jī)選取一只作為新的頭狼。頭狼不參加后續(xù)智能行為，直接進(jìn)入下次迭代,直至被更優(yōu)的狼所替代。

(2) 游走行為

在狼群中，除頭狼外，位置最優(yōu)的Snum只狼作為探狼,探狼執(zhí)行游走行為。Snum隨機(jī)取[N/(α+1),N/α]中的整數(shù),α為探狼的比例因子。探狼從當(dāng)前的位置出發(fā),試探性地沿著h個方向向前行走,由于每只探狼存在個體差異,探索環(huán)境的細(xì)致程度不一致,因此h是從[hmin,hmax]中隨機(jī)選取的整數(shù)。h越大,偵查得越細(xì),游走步長為stepa。記錄下沿著每個方向前進(jìn)一步探狼感知到的獵物氣味濃度,每個方向偵察完后讓探狼返回初始位置,直至偵查完所有方向,最后探狼沿著獵物氣味濃度最大的方向前進(jìn)，并更新探狼的位置。

比較探狼在新位置上感知到的獵物氣味濃度和當(dāng)前頭狼感知到的獵物氣味濃度,如果探狼在新位置上感知到的獵物氣味更濃,則探狼取代當(dāng)前頭狼成為新的頭狼,整個狼群直接開始召喚行為,否則探狼繼續(xù)執(zhí)行游走行為直至達(dá)到最大的游走次數(shù)Tmax。

(3) 召喚行為

Mnum(Mnum=N-Snum-1)只猛狼聽到頭狼發(fā)出的召喚以較大的步長快速地向頭狼奔去,奔襲步長為stepb。在奔襲途中,如果猛狼在新位置感知到的獵物氣味濃度比當(dāng)前頭狼感知到的獵物氣味濃度更濃,則猛狼取代當(dāng)前頭狼成為新的頭狼,整個狼群直接開始圍攻行為,否則猛狼繼續(xù)向頭狼逼近，直至猛狼和頭狼之間的距離小于給定的距離閾值dnear。

(4) 圍攻行為

在圍攻行為中,猛狼將聯(lián)合探狼對獵物進(jìn)行圍攻,此時狼群已經(jīng)比較接近獵物(頭狼的位置視為獵物的位置),只需在小范圍內(nèi)進(jìn)行精細(xì)搜尋,因此猛狼和探狼以較小的步長對獵物實(shí)施圍攻抓捕,圍攻步長為stepc。如果猛狼和探狼在新位置感知到的獵物氣味濃度比其在原始位置感知到的獵物氣味濃度大,則更新其位置,否則保持原始位置不動。

(5) 狼群更新機(jī)制

獵物根據(jù)由強(qiáng)到弱的原則進(jìn)行分配,老弱病殘的狼奔跑速度緩慢,離獵物較遠(yuǎn),只能分到少量食物甚至沒有食物,最終會被餓死。因此,目標(biāo)函數(shù)值最差的R只狼會被消滅,為了維持狼群的數(shù)量,同時會產(chǎn)生R只新狼。R越大,則新狼的數(shù)量越多,有利于維持狼群的個體多樣性,但是R的數(shù)值不能太大,否則狼群趨向執(zhí)行隨機(jī)搜索；同時，R也不能過小,否則不利于維持種群的多樣性,并且減弱了狼群開拓搜尋獵物新領(lǐng)域的能力。在每次的捕獵過程中,獵物的大小和數(shù)量會有差異,故餓死的狼的數(shù)量總是不等的,因此R是[N/2β,N/β]中的隨機(jī)整數(shù),β是狼群的更新比例因子。

3 基于改進(jìn)狼群的多任務(wù)種類協(xié)同分配優(yōu)化算法

狼群算法適用于變量連續(xù)變化的問題,但是任務(wù)分配問題是一個離散問題,每個變量都屬于整數(shù)集合。因此,有必要根據(jù)任務(wù)分配問題的離散性對個體的編碼方式進(jìn)行改進(jìn),使之符合任務(wù)分配問題的整數(shù)離散特征。對于異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題的求解，可以概述為對具有單目標(biāo)函數(shù)和包含多個約束的優(yōu)化問題的求解,通過種群優(yōu)化尋找最優(yōu)分配方案,并將遺傳算法思想引入到個體更新中，以實(shí)現(xiàn)快速尋優(yōu)。

狼群算法與異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題的對應(yīng)關(guān)系如下:狼個體-可行任務(wù)分配方案;狼位置變動-任務(wù)分配方案變動;狼感知獵物氣味濃度-目標(biāo)函數(shù)值。

3.1 整數(shù)矩陣編碼

個體狼的編碼是異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題求解的前提,也是設(shè)計狼群算法的關(guān)鍵。狼群中的每個個體都對應(yīng)著一個可行的任務(wù)分配方案,也就是說個體的編碼需要給出所有任務(wù)的分配情況。針對多功能異構(gòu)無人機(jī)的特性,僅根據(jù)目標(biāo)來分配無人機(jī)會導(dǎo)致任務(wù)無法完成,這是由于目標(biāo)不同和任務(wù)之間的差異導(dǎo)致對無人機(jī)的需求能力不一致,所分配的無人機(jī)不一定有能力執(zhí)行該目標(biāo)的所有任務(wù),因此需要對目標(biāo)的每個任務(wù)分配無人機(jī)。目標(biāo)和任務(wù)是兩個不同的維度,因此需引入矩陣編碼方式對個體進(jìn)行編碼。

在矩陣編碼中,每一行對應(yīng)一個目標(biāo),每一列對應(yīng)一類任務(wù),需要對每個目標(biāo)執(zhí)行3類任務(wù)且任務(wù)之間必須滿足嚴(yán)格的時序約束,因此矩陣有且僅有3列,依次對應(yīng)識別、攻擊和評估任務(wù),矩陣中的編碼值表示無人機(jī)編號。以5架無人機(jī)和3個目標(biāo)為例,根據(jù)矩陣編碼方式,個體狼的編碼是一個3行3列的矩陣,如圖2所示。第1行的3個編碼值2、3、5分別表示分配U2執(zhí)行T1的識別任務(wù),U3執(zhí)行攻擊任務(wù),U5執(zhí)行評估任務(wù)。

圖2 任務(wù)分配矩陣Fig.2 Task assignment matrix

3.2 種群優(yōu)化

傳統(tǒng)狼群算法主要針對連續(xù)問題尋優(yōu),更新迭代公式也僅僅適用于變量連續(xù)變化的情況。因此，根據(jù)本文研究問題的特點(diǎn),有必要對個體的更新方式進(jìn)行改進(jìn)。為了提高算法的收斂速度和尋優(yōu)能力,需要在個體更新中引入交叉算子,但是個體的更新會導(dǎo)致違反攻擊次數(shù)約束,對此需要提出基于拍賣機(jī)制的修正策略,實(shí)現(xiàn)對非可行解的調(diào)整,最后在狼群更新階段引入第三優(yōu)狼來提高狼群的質(zhì)量和多樣性,避免陷入局部最優(yōu)。

探狼的游走行為實(shí)質(zhì)上是對解空間的隨機(jī)探索,為了更高效地獲得最優(yōu)解,需要對解進(jìn)行合理更新,但是解的變動不宜過小,否則收斂速度緩慢,解的變動也不宜過大,否則會由于搜索不細(xì)致從而得不到最優(yōu)解。因此，根據(jù)問題的特點(diǎn)并結(jié)合遺傳算法中基因片段交叉的思想,游走階段的個體更新主要是對兩個相鄰目標(biāo)編號的stepa個連續(xù)任務(wù)對應(yīng)的無人機(jī)編號進(jìn)行互換,即對個體采用行變換操作,將由stepa個位于同行的相鄰元素組成的片段與相鄰行對應(yīng)位置的元素進(jìn)行互換。與一般的更新方式，如隨機(jī)從矩陣中選取stepa個任務(wù)重新分配無人機(jī)相比,這樣的更新方式更有利于快速收斂到最優(yōu)解,因?yàn)橥ǔ６詫⒛繕?biāo)上的連續(xù)stepa個任務(wù)分配給同一架無人機(jī)執(zhí)行耗費(fèi)的時間和資源是最少的。如果目標(biāo)上的連續(xù)stepa個任務(wù)由不同的無人機(jī)執(zhí)行,會直接增加無人機(jī)飛往目標(biāo)的時間和資源消耗,而隨機(jī)從矩陣中選取stepa個任務(wù)重新分配無人機(jī)會使得連續(xù)任務(wù)由同一無人機(jī)執(zhí)行的概率大幅下降,降低算法的收斂速度。

游走階段的更新操作具體實(shí)現(xiàn)過程如下:首先，隨機(jī)生成一個二維數(shù)組(i,k),i∈T,k=1,2,3,根據(jù)二維數(shù)組確定在矩陣中的位置,二維數(shù)組中的i表示第i行,二維數(shù)組中的k表示第k列,找到對應(yīng)編碼值,將包含該編碼值在內(nèi)且位于同一行的連續(xù)stepa個元素組成的片段和相鄰行對應(yīng)位置的編碼值進(jìn)行交換。如圖3所示,隨機(jī)生成的二維數(shù)組是(2,1),stepa=2。

圖3 游走階段的位置更新Fig.3 Position update of wandering phase

頭狼的召喚行為體現(xiàn)了對狼群的指揮,是猛狼快速收斂到當(dāng)前最優(yōu)解的關(guān)鍵,也決定了算法的收斂速度。為了快速向頭狼靠攏,個體的更新會參考當(dāng)前最優(yōu)個體,從當(dāng)前最優(yōu)個體中復(fù)制部分信息。具體實(shí)現(xiàn)過程如下:首先隨機(jī)生成stepb個二維數(shù)組,根據(jù)二維數(shù)組確定猛狼編碼矩陣的stepb個編碼位,從頭狼編碼矩陣中復(fù)制對應(yīng)編碼位的數(shù)值。如圖4所示,設(shè)置stepb=4,隨機(jī)生成的stepb個二維數(shù)組分別為(1,1),(2,3),(3,2),(3,3)。

圖4 召喚階段的位置更新Fig.4 Position update of calling phase

探狼和猛狼的圍攻行為可以理解為在獵物周圍進(jìn)行緊密地搜索,避免算法過早陷入局部最優(yōu)。具體實(shí)現(xiàn)操作如下:首先隨機(jī)生成stepc個二維數(shù)組,根據(jù)二維數(shù)組確定個體狼需要更新的編碼位,將需要更新的編碼值與間隔列對應(yīng)位置的編碼值交換,若交換的那列超出矩陣的索引范圍,則采用模數(shù)取余法確定交換的那列。如圖5所示,設(shè)置stepc=1,隨機(jī)生成的二維數(shù)組為(2,2),位置(2,2)的編碼值應(yīng)該與間隔一列對應(yīng)位置(2,4)的編碼值交換,但目前研究問題只考慮了3類任務(wù),矩陣的最大列數(shù)為3,位置(2,4)不存在,因此采用模數(shù)取余法,故與第1列對應(yīng)位置的編碼值進(jìn)行互換,即將位置(2，2)的編碼值與位置(2,1)的編碼值互換。

圖5 圍攻階段的位置更新Fig.5 Position update of sieging phase

在狼群更新中,R只最弱小的狼會被餓死,為了維持狼群的數(shù)量,需要生成新狼以實(shí)現(xiàn)狼群的進(jìn)化,傳統(tǒng)狼群算法中新狼的產(chǎn)生與初始化種群一樣,生成的新狼不具備強(qiáng)競爭力,無法快速收斂到最優(yōu)解,因此有必要改進(jìn)新狼的產(chǎn)生方式。通過在種群更新階段引入頭狼、次優(yōu)狼和第三優(yōu)狼,讓生成的新狼繼承強(qiáng)者的優(yōu)勢基因從而增強(qiáng)競爭力,改進(jìn)的方式既要克服傳統(tǒng)狼群算法的缺點(diǎn)，又要提高算法的收斂速度。具體實(shí)現(xiàn)過程如下:首先需要確定變異概率a,a是介于0～1的隨機(jī)數(shù),如果0

3.3 基于拍賣機(jī)制的修正策略

由于個體狼的位置更新產(chǎn)生新的任務(wù)分配方案,可能不滿足無人機(jī)攻擊次數(shù)約束而生成非可行方案,為了對非可行方案進(jìn)行調(diào)整,提出了基于拍賣機(jī)制的非可行方案修正策略。

對于新的任務(wù)分配方案,首先檢查分配方案中執(zhí)行攻擊任務(wù)的無人機(jī),如果無人機(jī)編號各不相同,說明沒有違反約束,否則將違反約束的無人機(jī)執(zhí)行的攻擊任務(wù)作為拍賣任務(wù),所有拍賣任務(wù)構(gòu)成拍賣任務(wù)集。機(jī)場發(fā)布拍賣活動且每輪只拍賣一個任務(wù),已經(jīng)執(zhí)行攻擊任務(wù)的無人機(jī)不再參與競拍活動,其余有能力執(zhí)行拍賣任務(wù)的無人機(jī)根據(jù)自身執(zhí)行任務(wù)的目標(biāo)函數(shù)值對拍賣任務(wù)進(jìn)行出價，并將競拍信息(競拍任務(wù)和競拍價格)發(fā)送給機(jī)場,機(jī)場從所有接收到的競拍信息中選擇出價最高的無人機(jī)。如果有兩個或多個無人機(jī)出價相同,則從中隨機(jī)選擇一個,再將競拍結(jié)果(競拍任務(wù)和中標(biāo)無人機(jī))反饋給所有參與本輪競拍的無人機(jī),已拍賣的任務(wù)從拍賣任務(wù)集中刪除,本輪中標(biāo)的無人機(jī)不再參與后續(xù)競拍活動。

基于拍賣機(jī)制的修正策略可以概括為以下4個步驟。

步驟1拍賣任務(wù)發(fā)布。當(dāng)前的任務(wù)分配方案違反攻擊次數(shù)約束時,由機(jī)場發(fā)布拍賣活動,每輪競拍只拍賣一個任務(wù),如圖6所示。

圖6 拍賣任務(wù)發(fā)布Fig.6 Auction task release

步驟2反饋競拍信息。有能力執(zhí)行拍賣任務(wù)的無人機(jī)對拍賣任務(wù)進(jìn)行出價,然后向機(jī)場反饋?zhàn)约旱母偱男畔?競拍任務(wù)和競拍價格),如圖7所示。

圖7 反饋競拍信息Fig.7 Feedback on bidding information

步驟3簽約。機(jī)場對所有競拍信息進(jìn)行處理,根據(jù)競拍價格挑選出最合適的無人機(jī),并向所有參與本輪競拍的無人機(jī)發(fā)送拍賣結(jié)果,如圖8所示。

圖8 簽約Fig.8 Signing

步驟4本輪簽約的無人機(jī)執(zhí)行拍賣任務(wù)，且不再參與后續(xù)拍賣活動,并將已拍賣任務(wù)從拍賣任務(wù)集中刪除,進(jìn)入下一輪競拍,直至拍賣任務(wù)集為空集。

3.4 基于拍賣機(jī)制的改進(jìn)狼群算法

改進(jìn)狼群的異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配算法步驟如下。

步驟1初始化狼群以及算法參數(shù)。設(shè)定參數(shù):種群數(shù)量N、最大迭代次數(shù)Maxgen、探狼的比例因子α、最大游走次數(shù)Tmax、距離閾值dnear、狼群更新因子β、游走步長stepa、召喚步長stepb和圍攻步長stepc。

步驟2判斷攻擊次數(shù)約束是否滿足。若滿足,則轉(zhuǎn)至步驟3;若不滿足,采用基于拍賣機(jī)制的修正策略,再轉(zhuǎn)至步驟3。

步驟3計算每個個體狼的目標(biāo)函數(shù)值,并對目標(biāo)函數(shù)值進(jìn)行排序，挑選出頭狼。

步驟4判斷是否達(dá)到最大迭代次數(shù)。如果達(dá)到則輸出最優(yōu)解,否則轉(zhuǎn)至步驟5。

步驟5判斷是否達(dá)到最大游走次數(shù)。如果達(dá)到則轉(zhuǎn)至步驟6,否則繼續(xù)執(zhí)行游走行為,若探狼在游走過程中,產(chǎn)生了比頭狼更優(yōu)的解,則取代頭狼轉(zhuǎn)至步驟6。

步驟6判斷猛狼與頭狼的距離是否小于給定的距離閾值dnear。如果小于則轉(zhuǎn)至步驟7,否則繼續(xù)執(zhí)行召喚行為,若猛狼在途中,產(chǎn)生了比頭狼更優(yōu)的解,則取代頭狼轉(zhuǎn)至步驟7。

步驟7猛狼聯(lián)合探狼執(zhí)行圍攻行為。

步驟8按照“強(qiáng)者生存”的更新機(jī)制實(shí)現(xiàn)狼群的更新,再轉(zhuǎn)至步驟2。

綜上,AMIWPA的流程如圖9所示。

圖9 AMIWPA流程圖Fig.9 Flow chart of AMIWPA

4 算例仿真

本文在Windows 10 操作系統(tǒng)上,基于Matlab環(huán)境實(shí)現(xiàn)AMIWPA的仿真實(shí)驗(yàn),PC機(jī)配置為11th Gen Intel(R) Core(TM) i5-1135G7@2.40 GHz 2.42 GHz,16G內(nèi)存。狼群算法的參數(shù)設(shè)置為:狼群規(guī)模大小N=50,探狼的比例因子α=4,最大游走迭代次數(shù)Tmax=10,給定的距離閾值dnear=3,狼群的更新比例因子β=0.4,游走步長stepa=2,召喚步長stepb=4,圍攻步長stepc=1。此外,無人機(jī)對目標(biāo)執(zhí)行識別、攻擊和評估任務(wù)的時間分別為10 min、5 min、10 min。

本文采用3個仿真場景對AMIWPA進(jìn)行驗(yàn)證,仿真場景1和仿真場景2為小規(guī)模,這兩個場景主要用于驗(yàn)證AMIWPA算法的可行性和有效性。仿真場景3為大規(guī)模,在此場景下將AMIWPA與其他兩種改進(jìn)算法進(jìn)行對比，進(jìn)一步驗(yàn)證AMIWPA算法的性能。

本文采用的兩種對比算法為AMIPSOA和AMISAA,由于粒子群優(yōu)化算法和模擬退火算法的標(biāo)準(zhǔn)形式均可用于求解連續(xù)型優(yōu)化問題,因此本文在采用粒子群優(yōu)化算法和模擬退火算法這兩類經(jīng)典算法求解本文問題時,先對這兩種算法進(jìn)行轉(zhuǎn)化,為了讓粒子群優(yōu)化算法和模擬退火算法的求解效率更高,在轉(zhuǎn)化的基礎(chǔ)上做了相應(yīng)改進(jìn),在此簡要介紹這兩種算法。

在AMIPSOA中,個體采用與本文一致的矩陣編碼方式。其中，慣性權(quán)重為ω,學(xué)習(xí)因子c1和c2是隨迭代次數(shù)變化的量,基于粒子群優(yōu)化算法的核心思想,個體按照如下方式進(jìn)行更新：首先隨機(jī)生成介于0和1之間的更新概率a,如果a<ω,則個體通過變異操作進(jìn)行更新；如果a

在AMISAA中,個體仍然采用矩陣編碼方式,個體的更新主要通過突變的形式，即從編碼矩陣中隨機(jī)選擇任務(wù)重新分配無人機(jī),對于新解再使用Metropolis準(zhǔn)則判斷是否可以被接受,若可以被接受,則檢查是否違反約束,如果違反,則采用基于拍賣機(jī)制的修正策略進(jìn)行調(diào)整；否則直接用新解替換當(dāng)前解。

4.1 算例1

仿真場景1中有8架無人機(jī)和5個目標(biāo),表3給出了無人機(jī)的初始位置和能力矩陣,表4給出了目標(biāo)的初始位置和能力需求矩陣,采用本文提出的AMIWPA獲得的最優(yōu)任務(wù)分配方案(如表5所示)。為了直觀地展示無人機(jī)的飛行情況,圖10繪制了無人機(jī)執(zhí)行任務(wù)的飛行路線。從獲得的任務(wù)分配方案中可以看出,無人機(jī)U1和U4未分配到任務(wù),由于存在任務(wù)時序約束,U6先對目標(biāo)T1執(zhí)行識別任務(wù),再由U3對T1執(zhí)行攻擊和評估任務(wù)。對于T2,U8先對其執(zhí)行識別任務(wù),隨后U2對其執(zhí)行攻擊任務(wù),最后由U8執(zhí)行評估任務(wù)。同樣,T3～T5的任務(wù)也滿足時序約束,由此可知,所有目標(biāo)的3類任務(wù)均滿足時序約束且均分配無人機(jī)執(zhí)行,并且每個目標(biāo)的攻擊任務(wù)均由不同無人機(jī)執(zhí)行。另外,由目標(biāo)能力需求矩陣可知,目標(biāo)T1的識別、攻擊和評估任務(wù)要求無人機(jī)相應(yīng)子系統(tǒng)具備的最低能力值分別為70%、40%、50%。任務(wù)分配方案顯示，U6執(zhí)行目標(biāo)T1的識別任務(wù),U3執(zhí)行目標(biāo)T1的攻擊和評估任務(wù)。由無人機(jī)能力矩陣可知,U6的識別子系統(tǒng)的能力值為70%,U3的攻擊和評估子系統(tǒng)的能力值分別為60%和70%,顯然滿足無人機(jī)子系統(tǒng)能力約束。仿真結(jié)果與實(shí)際問題相符,說明任務(wù)分配結(jié)果是可行的,因此采用AMIWPA求解異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題是可行的。

表3 算例1無人機(jī)參數(shù)設(shè)置

表4 算例1目標(biāo)參數(shù)設(shè)置

表5 算例1任務(wù)分配方案

圖10 算例1無人機(jī)飛行路徑Fig.10 Unmanned aerial vehicle flight path in case 1

4.2 算例2

為了進(jìn)一步驗(yàn)證AMIWPA的有效性,將問題規(guī)模擴(kuò)大,仿真場景2中有15架無人機(jī)和8個目標(biāo),表6和表7具體給出了無人機(jī)和目標(biāo)的相關(guān)參數(shù)設(shè)置。

表6 算例2無人機(jī)參數(shù)設(shè)置

表7 算例2目標(biāo)參數(shù)設(shè)置

采用AMIWPA對算例2進(jìn)行求解,獲得的任務(wù)分配方案如表8所示,相應(yīng)無人機(jī)的飛行路徑如圖11所示。由算例2可以看出,隨著仿真場景規(guī)模的擴(kuò)大,AMIWPA仍然能夠有效地求解考慮子系統(tǒng)能力約束的無人機(jī)蜂群任務(wù)分配問題。例如，對于目標(biāo)T4的任務(wù)分配,先由U6對T4執(zhí)行識別和攻擊任務(wù),再由U7對T4執(zhí)行評估任務(wù),從最小化資源消耗的目的出發(fā),由一架無人機(jī)執(zhí)行完目標(biāo)的所有類任務(wù)為最優(yōu)選擇。但是結(jié)合本文研究問題的特點(diǎn),無人機(jī)子系統(tǒng)能力約束的限制使得T4的評估任務(wù)不得不分配給其他無人機(jī)執(zhí)行,因?yàn)閁6評估子系統(tǒng)的執(zhí)行能力遠(yuǎn)低于T4評估任務(wù)的需求能力。算例2的仿真結(jié)果表明,采用AMIPWA求解考慮子系統(tǒng)能力約束的無人機(jī)蜂群任務(wù)分配問題是十分有效的。

表8 算例2任務(wù)分配方案

圖11 算例2的無人機(jī)飛行路徑Fig.11 Unmanned aerial vehicle flight path in case 2

4.3 算例3

為了進(jìn)一步驗(yàn)證AMIWPA在異構(gòu)無人機(jī)蜂群任務(wù)分配應(yīng)用下的穩(wěn)定性和收斂性,進(jìn)行仿真對比實(shí)驗(yàn),將AMIWPA與AMIPSOA、AMISAA進(jìn)行比較,采用3種算法對仿真場景3(100架無人機(jī)和80個目標(biāo))下的異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題進(jìn)行求解。每種算法獨(dú)立求解20次,最大迭代次數(shù)為1 000,獲得的目標(biāo)函數(shù)值的統(tǒng)計結(jié)果如表9所示,表9包含20次求解獲得的最小值fbest、最大值fworst、平均值favg以及每種算法的平均計算時間Tavg，以及最優(yōu)值的標(biāo)準(zhǔn)差std。

表9 3種算法在算例3中運(yùn)行20次獲得的目標(biāo)函數(shù)值

由表9中的結(jié)果可知,AMIWPA的整體性能優(yōu)于其他兩種改進(jìn)算法。一方面,AMIWPA在多次求解中獲得的最優(yōu)值的標(biāo)準(zhǔn)差比AMIPSOA和AMISAA獲得的標(biāo)準(zhǔn)差小,說明AMIWPA具有較好的穩(wěn)定性。另一方面,在20次求解中,AMIWPA獲得的最差目標(biāo)函數(shù)值比AMISAA和AMIPSOA獲得的最優(yōu)目標(biāo)函數(shù)值更優(yōu),說明AMIWPA在每次求解中獲得的最優(yōu)解始終優(yōu)于其他兩種改進(jìn)算法獲得的最優(yōu)解。此外,采用AMIWPA求解的計算時間也是最短的。因此,與AMISAA和AMIPSOA相比,本文提出的AMIWPA具有更好的穩(wěn)定性和尋優(yōu)能力。

為了直觀地對AMIWPA的收斂性進(jìn)行分析,繪制了3種算法在仿真場景3中求解異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題得到的收斂曲線,如圖12所示。

圖12 算例3中3種算法收斂曲線對比Fig.12 Convergence curve comparison of three algorithms in case 3

隨著迭代次數(shù)的增加,3種算法得到的目標(biāo)函數(shù)值均呈現(xiàn)下降的趨勢,其中AMIWPA的下降速度最為顯著,AMISAA次之,二者呈現(xiàn)近似指數(shù)的收斂速度;AMIPSOA的收斂速度最為緩慢,呈現(xiàn)近似線性的收斂速度。另外，3種算法獲得的解均被優(yōu)化,其中AMIWPA的解優(yōu)化強(qiáng)度最大。因此，所提算法不僅具有最快的收斂速度，還具有最強(qiáng)的優(yōu)化能力,具體原因分析如下：首先,AMIWPA融入了遺傳算法中的染色體交叉變異思想,有效地提高了種群多樣性。其次,狼群算法本身獨(dú)特的三階段搜索方式和本文改進(jìn)的更新方式加強(qiáng)了解空間的探索,提高了算法的搜索能力。此外,引入基于拍賣機(jī)制的修正策略可以獲得局部最優(yōu)解,從而加速尋優(yōu)歷程,相比隨機(jī)地處理非可行解,還提高了計算效率。最后,不同于傳統(tǒng)的狼群算法,AMIWPA在種群更新階段引入第三優(yōu)狼來產(chǎn)生新狼,不僅增加了種群的多樣性，還可以有效地避免局部極值。

由上述3個算例可以明顯看出,不管是對于大規(guī)模場景還是小規(guī)模場景,AMIWPA在求解異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題上都具有良好的性能,且在大規(guī)模任務(wù)場景下,相比于其他兩種改進(jìn)算法,AMIWPA不僅能夠有效跳出局部最優(yōu)位置,而且擁有更好的穩(wěn)定性、尋優(yōu)性，以及更快的收斂速度。

5 結(jié) 論

利用狼群算法適用于求解大規(guī)模離散優(yōu)化問題的特點(diǎn),針對子系統(tǒng)能力約束條件下的多機(jī)協(xié)同任務(wù)分配問題,提出了一種融合拍賣機(jī)制和帶有遺傳算法特點(diǎn)的狼群算法。對于無人機(jī)之間以及目標(biāo)之間存在的差異,提出的能力矩陣直觀形象地將無人機(jī)異構(gòu)性與子系統(tǒng)能力、目標(biāo)異構(gòu)性與目標(biāo)任務(wù)需求能力兩兩關(guān)聯(lián)；根據(jù)任務(wù)的異構(gòu)性,結(jié)合無人機(jī)子系統(tǒng)能力,構(gòu)建異構(gòu)無人機(jī)蜂群協(xié)同任務(wù)分配問題模型,將任務(wù)完成時間和無人機(jī)燃油消耗作為評價指標(biāo),考慮了子系統(tǒng)能力約束、攻擊次數(shù)約束和任務(wù)時序約束等多個約束。此外,在狼群算法中引入遺傳算法思想實(shí)現(xiàn)頭狼、探狼和猛狼位置的更新，以實(shí)現(xiàn)快速尋優(yōu),采用基于拍賣機(jī)制的修正策略處理非可行解以提高計算效率,并在狼群更新階段引入第三優(yōu)狼提高狼群的質(zhì)量和多樣性。最后，通過3個模擬仿真實(shí)驗(yàn),驗(yàn)證了本文所提算法的性能。