張鴻運, 王 磊, 張 旭, 丁 宇, 呂 琛, 王昕煒

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

0 引 言

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

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

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

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

1 模 型

1.1 問題描述

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

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

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

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

表1 無人機能力矩陣

表2 目標能力需求矩陣

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

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

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

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

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

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

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

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

1.2 代價函數(shù)

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

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

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

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

(1)

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

(2)

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

1.3 約束條件

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

(3)

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

(4)

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

(5)

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

1.4 問題建模

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

2 狼群算法原理

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

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

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

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

(2) 游走行為

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

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

(3) 召喚行為

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

(4) 圍攻行為

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

(5) 狼群更新機制

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

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

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

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

3.1 整數(shù)矩陣編碼

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

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

圖2 任務分配矩陣Fig.2 Task assignment matrix

3.2 種群優(yōu)化

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

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

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

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

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

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

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

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

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

3.3 基于拍賣機制的修正策略

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

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

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

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

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

步驟2反饋競拍信息。有能力執(zhí)行拍賣任務的無人機對拍賣任務進行出價,然后向機場反饋自己的競拍信息(競拍任務和競拍價格),如圖7所示。

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

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

圖8 簽約Fig.8 Signing

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

3.4 基于拍賣機制的改進狼群算法

改進狼群的異構無人機蜂群協(xié)同任務分配算法步驟如下。

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

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

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

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

步驟5判斷是否達到最大游走次數(shù)。如果達到則轉(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按照“強者生存”的更新機制實現(xiàn)狼群的更新,再轉(zhuǎn)至步驟2。

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

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

4 算例仿真

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

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

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

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

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

4.1 算例1

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

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

表4 算例1目標參數(shù)設置

表5 算例1任務分配方案

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

4.2 算例2

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

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

表7 算例2目標參數(shù)設置

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

表8 算例2任務分配方案

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

4.3 算例3

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

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

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

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

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

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

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

5 結 論

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