高 程, 都延麗,*, 步雨濃, 劉燕斌, 王宇飛

(1. 南京航空航天大學(xué)航天學(xué)院, 江蘇 南京 211106; 2. 北京機(jī)電工程研究所, 北京 100854)

0 引 言

近年來(lái),無(wú)人機(jī)作戰(zhàn)樣式正從單機(jī)作戰(zhàn)向集群協(xié)同作戰(zhàn)方向轉(zhuǎn)變[1]。無(wú)人機(jī)集群分為同構(gòu)集群和異構(gòu)集群兩種類型,異構(gòu)集群中各無(wú)人機(jī)之間功能互補(bǔ),能力協(xié)同,能夠適應(yīng)復(fù)雜多樣的作戰(zhàn)任務(wù)需求,逐漸成為集群作戰(zhàn)的主力[2-3]。

合理的任務(wù)分配是提高異構(gòu)集群作戰(zhàn)系統(tǒng)效能的關(guān)鍵[4]。集群任務(wù)分配問(wèn)題可以看作是復(fù)雜多約束條件下的組合優(yōu)化問(wèn)題[5-6],隨著集群任務(wù)規(guī)模的增大,作戰(zhàn)任務(wù)分配問(wèn)題的求解難度劇增[7]。因此,將大規(guī)模集群的任務(wù)分配問(wèn)題進(jìn)行分解,轉(zhuǎn)化為中小規(guī)模問(wèn)題后再進(jìn)行求解,能夠顯著提高任務(wù)分配問(wèn)題的求解效率[8-9]。

大規(guī)模任務(wù)分配問(wèn)題的分解[10]包括任務(wù)分組和無(wú)人機(jī)集群分組兩個(gè)環(huán)節(jié),任務(wù)分組是無(wú)人機(jī)集群分組的前提。為了減小分組對(duì)全局任務(wù)分配的影響,通常按照任務(wù)的地理位置進(jìn)行分組,將地理位置相近的任務(wù)聚類為一組,因此任務(wù)的分組問(wèn)題可以采用聚類方法進(jìn)行求解[11-12]。典型的聚類算法包括基于劃分的聚類[13]、基于層次的聚類[14]、基于網(wǎng)格的聚類[15]、基于密度的聚類[16]等。其中,K-means算法是一種應(yīng)用十分廣泛的基于劃分的聚類方法,原理簡(jiǎn)單,計(jì)算高效,但是對(duì)初始值和噪聲十分敏感,容易陷入局部最優(yōu)[17-18]。文獻(xiàn)[19]提出一種基于相異性度量選取初始聚類中心改進(jìn)的K-means聚類算法,并利用各簇中數(shù)據(jù)點(diǎn)的中位數(shù)代替均值,消除離群點(diǎn)對(duì)聚類準(zhǔn)確率的影響。文獻(xiàn)[20]提出了一種基于K-medoids算法和粒子群優(yōu)化算法的任務(wù)調(diào)度技術(shù),用于最小化云計(jì)算中的任務(wù)完成時(shí)間。文獻(xiàn)[21]設(shè)計(jì)了一種加權(quán)密度的改進(jìn)K-means聚類算法,將超密集網(wǎng)絡(luò)中的毫微微基站劃分為不同的簇。

異構(gòu)無(wú)人機(jī)集群的分組不同于任務(wù)分組,其本質(zhì)上是一類多對(duì)一的雙邊穩(wěn)定匹配問(wèn)題[22-23]。Gale等[24]提出了穩(wěn)定匹配的概念和延遲接受(deferred-acceptance, DA)算法,用于解決“婚姻市場(chǎng)”中一對(duì)一的雙邊匹配問(wèn)題,并證明了DA算法所得匹配結(jié)果的穩(wěn)定性。文獻(xiàn)[25]針對(duì)終端用戶和基站的匹配問(wèn)題,采用基于DA算法的多對(duì)一匹配博弈實(shí)現(xiàn)網(wǎng)絡(luò)能效的最大化。文獻(xiàn)[26]提出了基于改進(jìn)DA算法的電動(dòng)汽車-快充樁匹配策略,通過(guò)多輪次算法解決充電服務(wù)市場(chǎng)中的多對(duì)一匹配問(wèn)題。文獻(xiàn)[27]以異構(gòu)網(wǎng)絡(luò)中網(wǎng)絡(luò)吞吐量和用戶性能作為優(yōu)化指標(biāo),提出了一種基于兩階段穩(wěn)定匹配的動(dòng)態(tài)頻譜分配算法。文獻(xiàn)[28]提出了一種基于雙層穩(wěn)定匹配的異構(gòu)無(wú)人機(jī)集群“分布式”協(xié)同算法,將三邊匹配問(wèn)題轉(zhuǎn)化為雙層-雙邊穩(wěn)定匹配問(wèn)題進(jìn)行求解。雙邊穩(wěn)定匹配方法應(yīng)用廣泛,并且具有良好的穩(wěn)定性和最優(yōu)性,因此可以將穩(wěn)定匹配的相關(guān)方法應(yīng)用于無(wú)人機(jī)集群的分組問(wèn)題中。

本文中設(shè)計(jì)了一種異構(gòu)無(wú)人機(jī)集群按任務(wù)進(jìn)行分組的方法。整個(gè)分組的過(guò)程分為兩個(gè)環(huán)節(jié),在任務(wù)聚類分組環(huán)節(jié),首先利用局部密度對(duì)目標(biāo)點(diǎn)樣本集合進(jìn)行離群點(diǎn)檢測(cè)預(yù)處理,通過(guò)虛擬目標(biāo)點(diǎn)替換異常點(diǎn)的方法提高K-means聚類精度。然后,對(duì)目標(biāo)進(jìn)行固定初始聚類中心的聚類分組,并進(jìn)行分組均衡性的調(diào)整,任務(wù)分組完成后計(jì)算分組需求的各類無(wú)人機(jī)的數(shù)量。在無(wú)人機(jī)集群分組環(huán)節(jié),運(yùn)用穩(wěn)定匹配的思想,對(duì)DA算法進(jìn)行改進(jìn),首先基于最優(yōu)性的考慮,通過(guò)任務(wù)傾向的偏好列表快速地將無(wú)人機(jī)映射到匹配度高的分區(qū),然后設(shè)計(jì)兩階段的沖突消除保證匹配的穩(wěn)定性和收斂性,得到無(wú)沖突的分配方案,完成無(wú)人機(jī)集群的分組調(diào)配。最后,通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

1 問(wèn)題描述

本文主要研究復(fù)雜多任務(wù)下異構(gòu)無(wú)人機(jī)集群的分組調(diào)配問(wèn)題,系統(tǒng)模型如圖1所示。首先對(duì)任務(wù)進(jìn)行聚類分組,然后將無(wú)人機(jī)集群匹配到任務(wù)分組,將目標(biāo)點(diǎn)任務(wù)-無(wú)人機(jī)集群之間的直接任務(wù)分配轉(zhuǎn)化為組內(nèi)小規(guī)模任務(wù)分配。假設(shè)二維空間的任務(wù)區(qū)域中存在NT個(gè)目標(biāo)區(qū)域T={T1,T2,…,TNT},目標(biāo)區(qū)域是無(wú)人機(jī)集群執(zhí)行任務(wù)的區(qū)域,在分組過(guò)程中將其簡(jiǎn)化為目標(biāo)點(diǎn)進(jìn)行處理。每個(gè)目標(biāo)點(diǎn)有多個(gè)類型的任務(wù),在分組過(guò)程中默認(rèn)將同一目標(biāo)點(diǎn)的多個(gè)任務(wù)分為一組,因此任務(wù)聚類分組問(wèn)題可以等效為目標(biāo)點(diǎn)聚類分組問(wèn)題。異構(gòu)無(wú)人機(jī)集群U={U1,U2,…,UNV}有多個(gè)類型的無(wú)人機(jī)共NV架,不同類別的無(wú)人機(jī)攜帶的載荷資源不同,因此用于執(zhí)行不同的任務(wù)。按照?qǐng)?zhí)行任務(wù)后是否發(fā)生變化將無(wú)人機(jī)的載荷資源分為消耗型載荷和非消耗型載荷,任務(wù)需求一個(gè)或多個(gè)載荷資源。同一無(wú)人機(jī)在某時(shí)刻只能滿足任務(wù)的一個(gè)載荷資源需求。由此可知,目標(biāo)點(diǎn)需求某類無(wú)人機(jī)的數(shù)量即為任務(wù)需求對(duì)應(yīng)類型載荷資源的數(shù)量。為了避免無(wú)人機(jī)冗余,規(guī)定某類任務(wù)的載荷需求數(shù)量不小于可分配的無(wú)人機(jī)數(shù)量。將目標(biāo)點(diǎn)聚類后的分組稱為分區(qū)。

圖1 分組調(diào)配問(wèn)題系統(tǒng)模型Fig.1 System model of grouping deployment problem

合理的分組調(diào)配能夠有效降低任務(wù)分配問(wèn)題的求解難度。以某類需求單個(gè)非消耗型載荷的任務(wù)為例,假設(shè)任務(wù)數(shù)量為m,可分配的無(wú)人機(jī)數(shù)量為n,分組數(shù)量為k,則直接任務(wù)分配的解的數(shù)量級(jí)為nm,分組調(diào)配后組內(nèi)任務(wù)分配的解的數(shù)量級(jí)為(n/k)m/k,分組數(shù)量k越大,則二者的數(shù)量級(jí)相差越大。因此,分組調(diào)配可以降低任務(wù)分配問(wèn)題解的數(shù)量級(jí),從而提高其求解效率。

(1)

2 目標(biāo)聚類分組

聚類算法是一種無(wú)監(jiān)督學(xué)習(xí),考慮到訓(xùn)練的對(duì)象只有目標(biāo)的坐標(biāo)值,本文采用改進(jìn)的K-means聚類方法對(duì)目標(biāo)點(diǎn)進(jìn)行分組。

2.1 基于局部密度的離群點(diǎn)檢測(cè)

K-means聚類對(duì)異常點(diǎn)比較敏感,為了使最終的聚類效果更加理想,本文首先采用離群點(diǎn)檢測(cè)算法對(duì)目標(biāo)點(diǎn)樣本集進(jìn)行預(yù)處理,將離群點(diǎn)轉(zhuǎn)化為同類型的密集點(diǎn),然后再對(duì)數(shù)據(jù)集進(jìn)行聚類分組。根據(jù)文獻(xiàn)[29-30],離群點(diǎn)具有較大的相對(duì)距離和較小的局部密度,因此本文中通過(guò)求取局部密度進(jìn)行離群點(diǎn)檢測(cè),算法的相關(guān)定義如下。

(1) 第m距離dm(j):目標(biāo)Tj的第m距離,定義為距離Tj第m遠(yuǎn)的目標(biāo)點(diǎn)到Tj的距離,不包括Tj本身。

(2) 第m距離鄰域Nm(j):目標(biāo)點(diǎn)Tj的第m距離鄰域,定義為以Tj為圓心,以第m距離為半徑的區(qū)域內(nèi)所有目標(biāo)點(diǎn)的集合,包括第m距離上的目標(biāo)點(diǎn)。

(3) 第m可達(dá)距離reach_dism(i,j):目標(biāo)點(diǎn)Ti到Tj的第m可達(dá)距離表示為

reach_dism(i,j)=max{dm(i),d(i,j)}

(2)

式中:d(i,j)為目標(biāo)點(diǎn)Ti到Tj的歐式距離。

(4) 第m局部可達(dá)密度lrdm(j):目標(biāo)點(diǎn)Tj的第m局部可達(dá)密度lrdm(j)表示為

(3)

即Tj的第m距離鄰域內(nèi)的所有目標(biāo)點(diǎn)的平均第m可達(dá)距離的倒數(shù)。

(5) 第m局部離群因子lofm(j):Tj的第m局部離群因子表示為

(4)

即Tj的|Nm(j)|鄰域內(nèi)所有目標(biāo)點(diǎn)的平均局部可達(dá)密度與Tj的局部可達(dá)密度的比值。這個(gè)比值越接近 1,表明Tj與其鄰域點(diǎn)密度相近,Tj可能和鄰域同屬一簇;這個(gè)比值越大于1,表明Tj越小于其鄰域點(diǎn)的密度,Tj越可能是離群點(diǎn)。

離群點(diǎn)檢測(cè)算法的基本流程如下:首先計(jì)算每個(gè)目標(biāo)點(diǎn)的第m可達(dá)距離和第m局部可達(dá)密度。然后,通過(guò)局部可達(dá)密度得到每個(gè)目標(biāo)點(diǎn)的第m局部離群因子,該離群因子表示目標(biāo)點(diǎn)的離群程度,因子值越大,離群程度越高,因子值越小,離群程度越低。最后,通過(guò)設(shè)定離群因子閾值的方式輸出密集點(diǎn)集合Ω1和離群點(diǎn)集合Ω2。

2.2 目標(biāo)點(diǎn)初始聚類分組

(5)

圖2 k=3時(shí)的初始聚類中心Fig.2 Initial cluster center when k=3

以全局中心Cmap為圓心,設(shè)定各分區(qū)的聚類中心圍繞Cmap均勻分布,編號(hào)為i的分區(qū)聚類中心的坐標(biāo)值為

(6)

K-means聚類的優(yōu)化目標(biāo)為最小化目標(biāo)點(diǎn)到所在分組聚類中心距離的誤差平方和(sum of squared error, SSE):

(7)

式中:p∈Si為分組Si中的目標(biāo);μi=∑p∈Sip/|Si|為分組Si的質(zhì)心,稱為分組的聚類中心。初始聚類算法如算法1所示,在計(jì)算得到初始的聚類中心后,分別計(jì)算每個(gè)目標(biāo)距離聚類中心的距離,將目標(biāo)加入到距離最近聚類中心所在的分組。每一輪分組完成后,重新計(jì)算新的聚類中心,若更新后的聚類中心發(fā)生變化,則重新計(jì)算各分區(qū)到新質(zhì)心的距離,循壞迭代訪問(wèn)直到聚類中心不再更新,即完成一次K-means聚類分組。

算法 1 目標(biāo)點(diǎn)初始K-means聚類分組算法輸入 目標(biāo)點(diǎn)樣本集T,初始聚類分組數(shù)量k輸出 分組聚類中心集合μ,聚類分組劃分S1:按照式(5)和式(6)計(jì)算初始的k個(gè)聚類中心μ2:while flag=1 do3: flag=0;4: for ?Tj∈T5: 計(jì)算目標(biāo)Tj與各聚類中心的距離列表;6: 選擇距離目標(biāo)最近的聚類中心μi,將目標(biāo)Tj加入μi的分組Si;7: end for8: for ?i≤k9: 計(jì)算新的聚類中心μ'i=1|Si|∑p∈Sip;10: if μ'i≠μi then11: μi=μ'i;12: flag=1;13: else14: 保持當(dāng)前分組聚類中心不變;15: end if16:end for17: end while

2.3 分區(qū)均衡性調(diào)整

初始聚類得到的分區(qū)結(jié)果可能存在目標(biāo)數(shù)量不均衡的問(wèn)題,并且在聚類過(guò)程中使用了虛擬的密集點(diǎn)集合,因此需要將虛擬的目標(biāo)點(diǎn)還原為實(shí)際的目標(biāo)點(diǎn),并進(jìn)行分區(qū)均衡性調(diào)整。采用余量表示各分區(qū)的目標(biāo)數(shù)量情況,首先根據(jù)總的目標(biāo)數(shù)量和分區(qū)數(shù)量,計(jì)算余量基準(zhǔn)值nd:

(8)

(9)

在所有分區(qū)都為近鄰的理想情況下,余量為正表明分區(qū)余量充足,可作為轉(zhuǎn)移分區(qū)加入新的目標(biāo);余量為0表明分區(qū)無(wú)法加入新的目標(biāo),但也無(wú)需向其他分區(qū)轉(zhuǎn)移目標(biāo);余量為負(fù)表明目標(biāo)數(shù)量過(guò)多,須將多余的目標(biāo)調(diào)整到余量充足的轉(zhuǎn)移分區(qū)。而在實(shí)際情況下,分區(qū)之間可能不存在近鄰關(guān)系,為了保證分組精度,轉(zhuǎn)移的策略也需要進(jìn)行調(diào)整。分區(qū)均衡性調(diào)整的相關(guān)概念如下:

(2) 轉(zhuǎn)移代價(jià)矩陣C:C與M相對(duì)應(yīng),用于存儲(chǔ)目標(biāo)到分區(qū)的轉(zhuǎn)移代價(jià)。可轉(zhuǎn)移目標(biāo)的轉(zhuǎn)移代價(jià)為轉(zhuǎn)移前后與分區(qū)聚類中心距離的差值,不可轉(zhuǎn)移目標(biāo)的轉(zhuǎn)移代價(jià)為+∞。

算法 2 分區(qū)均衡性調(diào)整算法輸入 未進(jìn)行均衡性調(diào)整的聚類分區(qū)S輸出 更新后的分區(qū)S'1: 計(jì)算轉(zhuǎn)移可行性矩陣M和分區(qū)余量;2: for ?i≤k3: ifi<0 then4: 查找分區(qū)中能夠轉(zhuǎn)移到其他分區(qū)的nMi個(gè)目標(biāo);5: if nMi≠06: for ?j≤min{nMi,|i|}7: ξ=arg minξCξm,ξ∈Si;8: m=arg minmCξm,ξ∈Si;9: Sm=Sm⊕{Tξ},Si=Si{Tξ};10: end for11: end if12: end if13: end for

K-means聚類和均衡性調(diào)整僅依靠目標(biāo)點(diǎn)的距離關(guān)系進(jìn)行分組,沒(méi)有考慮到可分配給各分區(qū)的無(wú)人機(jī)數(shù)量是否能夠滿足分區(qū)任務(wù)的最低需求,因此需要對(duì)分組結(jié)果進(jìn)行可行性判斷。各分區(qū)需求的無(wú)人機(jī)數(shù)量滿足一定的區(qū)間要求,將此區(qū)間表示為[nmin,nmax],區(qū)間的上限nmax由分區(qū)中所有目標(biāo)的載荷需求之和決定,區(qū)間的下限nmin是分區(qū)的最低需求。對(duì)于需求非消耗型載荷資源的任務(wù),必須要保證載荷需求最多的任務(wù)能夠完成,因此區(qū)間的下限由分區(qū)中單個(gè)目標(biāo)的載荷需求的最大值決定;而對(duì)于需求消耗型載荷資源的任務(wù),要考慮單個(gè)無(wú)人機(jī)的最大載荷數(shù)量約束,區(qū)間的下限要保證所有任務(wù)的載荷需求都能得到滿足。因此,區(qū)間需求的最小無(wú)人機(jī)數(shù)量nmin的計(jì)算方法為

(10)

目標(biāo)聚類分組將分區(qū)內(nèi)的目標(biāo)點(diǎn)信息傳遞到聚類中心,改進(jìn)K-means聚類基于虛擬的密集點(diǎn)集合求解聚類中心,因此聚類中心更加靠近組內(nèi)的大多數(shù)實(shí)際目標(biāo)點(diǎn),有效避免了離群點(diǎn)的影響。分組均衡性調(diào)整可以避免各分區(qū)的目標(biāo)數(shù)量相差過(guò)大,提高分組的均衡性。通過(guò)計(jì)算比較無(wú)人機(jī)數(shù)量需求下限與實(shí)際可分配的無(wú)人機(jī)數(shù)量,保證當(dāng)前分組方案的可行性。

3 無(wú)人機(jī)集群匹配分組

3.1 分區(qū)待分配無(wú)人機(jī)數(shù)量計(jì)算

在使用聚類分組算法得到目標(biāo)點(diǎn)的分區(qū)后,需要根據(jù)分區(qū)數(shù)量,計(jì)算每個(gè)分區(qū)待分配的某類無(wú)人機(jī)的數(shù)量,各分區(qū)待分配的某類無(wú)人機(jī)的數(shù)量Mj的計(jì)算方式如下:

(11)

由于式(11)中存在取整運(yùn)算符,可能導(dǎo)致無(wú)人機(jī)存在冗余的情況,因此需要調(diào)整個(gè)別分區(qū)的無(wú)人機(jī)需求數(shù)量,保證無(wú)人機(jī)分組后無(wú)冗余。為了提高任務(wù)執(zhí)行的效率,通過(guò)計(jì)算各分區(qū)中無(wú)人機(jī)的平均負(fù)載來(lái)判斷分區(qū)對(duì)無(wú)人機(jī)的需求情況,平均負(fù)載較大的分區(qū)對(duì)無(wú)人機(jī)的需求更高,因此冗余的名額優(yōu)先分配給平均負(fù)載較大的分區(qū)。若存在負(fù)載相同的情況,則計(jì)算分區(qū)的組內(nèi)平均誤差,優(yōu)先分配給平均誤差值較大的分區(qū)。

3.2 基于兩階段延遲接受算法的匹配分組

在得到各分區(qū)中各類無(wú)人機(jī)的待分配數(shù)量后,需要將無(wú)人機(jī)集群進(jìn)行分組,映射到目標(biāo)分區(qū)。每個(gè)無(wú)人機(jī)只能映射到一個(gè)分區(qū),同一個(gè)分區(qū)需要多個(gè)無(wú)人機(jī),因此將分組問(wèn)題建模為多對(duì)一類型的穩(wěn)定匹配問(wèn)題。傳統(tǒng)的延遲接受算法在進(jìn)行多對(duì)一穩(wěn)定匹配時(shí)存在一定的局限性,分組的過(guò)程由“多”方依據(jù)其偏好發(fā)起,而后由“一”方根據(jù)其偏好選擇是否接受,從而得到穩(wěn)定的匹配結(jié)果。在匹配過(guò)程中,“一”方只能被動(dòng)地選擇部分“多”方對(duì)象,并因此錯(cuò)過(guò)自身的最優(yōu)解,得到的匹配結(jié)果容易陷入局部最優(yōu)。本文中對(duì)延遲接受算法進(jìn)行改進(jìn),提出了一種基于兩階段DA(two-phase DA, TPDA)算法的匹配分組方法。

本文中多對(duì)一穩(wěn)定匹配問(wèn)題的匹配度由無(wú)人機(jī)的載荷資源種類以及到各分區(qū)聚類中心的距離決定。計(jì)算各無(wú)人機(jī)到所有分區(qū)的航程代價(jià)矩陣E,并對(duì)所有分區(qū)所需的載荷資源進(jìn)行匹配,目標(biāo)Ti與分區(qū)Sj的匹配值的計(jì)算方法為

即若滿足載荷資源要求則將航程代價(jià)的倒數(shù)作為對(duì)應(yīng)分區(qū)的匹配值,不滿足載荷要求則將匹配值設(shè)為0。在計(jì)算得到所有無(wú)人機(jī)的匹配值后,根據(jù)各分區(qū)需求無(wú)人機(jī)的數(shù)量對(duì)無(wú)人機(jī)進(jìn)行匹配。按照每個(gè)分區(qū)的無(wú)人機(jī)匹配值大小生成任務(wù)傾向的偏好列表,偏好列表中只包含與其匹配值不為0的無(wú)人機(jī),且匹配值越大的無(wú)人機(jī)匹配度越高,在偏好列表中的位置越靠前。結(jié)合各分區(qū)的載荷需求數(shù)量和任務(wù)傾向偏好列表,生成預(yù)中選方案。任務(wù)傾向偏好列表中位于各分區(qū)載荷需求范圍內(nèi)的無(wú)人機(jī)稱為“預(yù)中選者”,位于各分區(qū)載荷需求范圍外的匹配值最大的無(wú)人機(jī)稱為“候補(bǔ)中選者”,將各分區(qū)的預(yù)中選者作為預(yù)中選方案的解。

3.3 兩階段沖突消除

預(yù)中選方案是每個(gè)分區(qū)的最優(yōu)解,但不同分區(qū)的任務(wù)傾向偏好列表中可能存在相同的預(yù)中選者,導(dǎo)致其分配方案之間存在沖突。由于單個(gè)無(wú)人機(jī)只能分配到一個(gè)分區(qū),因此定義一個(gè)列表match,用來(lái)存儲(chǔ)無(wú)人機(jī)的分配情況。沖突消除的流程圖如圖3所示。

圖3 兩階段沖突消除流程圖Fig.3 Two-phase conflict resolution flow chart

這個(gè)過(guò)程分為兩個(gè)階段進(jìn)行,第一階段將沖突的預(yù)中選者替換為候補(bǔ)中選者,以消除當(dāng)前方案中存在相同預(yù)中選者的沖突。具體策略為,若當(dāng)前分區(qū)的預(yù)中選者已被分配到其他分區(qū),則比較該無(wú)人機(jī)在當(dāng)前分區(qū)以及已分配的分區(qū)中替換為候補(bǔ)中選者的匹配值之差,選擇使用候補(bǔ)中選者代價(jià)較小的方案,將對(duì)應(yīng)的預(yù)中選者替換為候補(bǔ)中選者,并修正列表match中對(duì)應(yīng)預(yù)中選者的已分配分區(qū)。由于當(dāng)前分區(qū)的候補(bǔ)中選者可能是其他分區(qū)的預(yù)中選者,若此類候補(bǔ)中選者成為預(yù)中選者,則會(huì)再次出現(xiàn)沖突,因此需要多輪沖突消除。沖突消除的過(guò)程是將部分分區(qū)的最優(yōu)解替換為次優(yōu)解的過(guò)程,多輪沖突消除可能會(huì)使得部分分區(qū)資源冗余,導(dǎo)致其他分區(qū)的候補(bǔ)中選者不足,無(wú)法完成分區(qū)任務(wù)。通過(guò)設(shè)置閾值β控制沖突消除第一階段的迭代次數(shù),若第一階段結(jié)束后不存在沖突,則接受預(yù)中選方案作為最終方案,否則仍對(duì)預(yù)中選方案延遲接受,并進(jìn)行第二階段的局部調(diào)整。

沖突消除第二階段局部調(diào)整的目的是為了獲得可接受的全局可行解,首先對(duì)各分區(qū)的分配方案進(jìn)行檢測(cè),將存在沖突的分區(qū)和未分配的無(wú)人機(jī)進(jìn)行回收。對(duì)于競(jìng)爭(zhēng)同一無(wú)人機(jī)的分區(qū),只有一個(gè)分區(qū)能夠保留原始解,其他分區(qū)需要從回收池中選擇次優(yōu)解進(jìn)行替換。通過(guò)計(jì)算優(yōu)先級(jí)權(quán)值來(lái)判斷當(dāng)前分區(qū)進(jìn)行次優(yōu)解替換的優(yōu)先級(jí),優(yōu)先級(jí)較高的分區(qū)先進(jìn)行次優(yōu)解的選擇,優(yōu)先級(jí)最小的分區(qū)不進(jìn)行替換,保留原始解。優(yōu)先級(jí)的計(jì)算方法為假設(shè)當(dāng)前分區(qū)的優(yōu)先級(jí)最高,計(jì)算替換前后的匹配值差值,作為計(jì)算優(yōu)先級(jí)的權(quán)值。權(quán)值越小說(shuō)明替換為次優(yōu)解后對(duì)全局的影響越小,因此權(quán)值最小的分區(qū)優(yōu)先級(jí)最高,優(yōu)先進(jìn)行可行解的選擇,已分配的分區(qū)和無(wú)人機(jī)從回收池中移除,不參與下一次的調(diào)整。不斷重復(fù)這個(gè)過(guò)程,直到競(jìng)爭(zhēng)同一無(wú)人機(jī)的分區(qū)數(shù)量為1,表明沖突的分區(qū)都已替換為回收池中的可行解,各分區(qū)方案中的沖突已消除,此時(shí)接受預(yù)中選方案。

TPDA算法的初始預(yù)中選方案為各分區(qū)的最優(yōu)偏好,沖突消除第一階段通過(guò)計(jì)算預(yù)中選者替換為候補(bǔ)中選者的代價(jià),將部分分區(qū)的最優(yōu)解替換為次優(yōu)解,以消除部分沖突。第二階段為局部的調(diào)整,按照分區(qū)的優(yōu)先級(jí)從回收池中選擇可行解,直到所有無(wú)人機(jī)均匹配到唯一的分區(qū)。兩個(gè)階段均按照最優(yōu)性原則消除沖突,因此得到的可行解仍是全局最優(yōu)性較好的匹配方案。

4 仿真驗(yàn)證與分析

本文在典型的異構(gòu)無(wú)人機(jī)集群協(xié)同執(zhí)行多任務(wù)場(chǎng)景下,通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證所提出的集群任務(wù)分組調(diào)配算法的有效性,并與其他算法進(jìn)行算法性能的對(duì)比。仿真平臺(tái)為具有Intel Core i5-6300HQ 2.30 GHz處理器和8G內(nèi)存的PC機(jī)。

4.1 典型場(chǎng)景下集群分組仿真結(jié)果

任務(wù)場(chǎng)景設(shè)定如下:在50 km×50 km的范圍內(nèi)有20個(gè)目標(biāo)區(qū)域,待執(zhí)行的任務(wù)類型共3種,目標(biāo)區(qū)域的參數(shù)如表1所示。首先對(duì)目標(biāo)樣本進(jìn)行聚類分組仿真實(shí)驗(yàn),離群點(diǎn)檢測(cè)的離群因子閾值設(shè)為5,分組數(shù)量k設(shè)為4,余量裕度α設(shè)為10%,截?cái)嘞禂?shù)dc設(shè)為1.35。目標(biāo)聚類分組前后的對(duì)比如圖4和圖5所示,分組結(jié)果如表2所示。從圖4中可以看出,聚類算法在離群因子閾值設(shè)為5時(shí)檢測(cè)出2個(gè)離群點(diǎn),將離群點(diǎn)替換為虛擬的密集點(diǎn)后,得到的聚類中心更加靠近分組中的大多數(shù)目標(biāo)點(diǎn),使得后續(xù)匹配分組的結(jié)果準(zhǔn)確性更高。圖5中各分區(qū)的目標(biāo)點(diǎn)均位于其聚類中心附近,聚類中心能夠有效地代表分區(qū)中的目標(biāo)點(diǎn),與無(wú)人機(jī)集群進(jìn)行匹配。表2中各分區(qū)的目標(biāo)點(diǎn)數(shù)量均位于平均值附近,因此在設(shè)置的余量裕度范圍內(nèi),各分組的目標(biāo)數(shù)量基本保持均衡,避免了某些分組的任務(wù)分配問(wèn)題規(guī)模仍舊過(guò)大,將復(fù)雜的大規(guī)模問(wèn)題分解為中小規(guī)模問(wèn)題,有效地提高了任務(wù)分配問(wèn)題的求解效率。在50 km×20 km的區(qū)域中隨機(jī)生成無(wú)人機(jī)集群,集群中有3種類型的無(wú)人機(jī)共60架,各類無(wú)人機(jī)的參數(shù)如表3所示。表3中,INF表示非消耗型資源。利用目標(biāo)聚類分組的結(jié)果進(jìn)行無(wú)人機(jī)匹配分組仿真實(shí)驗(yàn),TPDA算法的閾值β設(shè)為4,得到的TPDA匹配分組的最終結(jié)果如表4所示。以匹配結(jié)果中出現(xiàn)沖突的無(wú)人機(jī)數(shù)量與無(wú)人機(jī)總數(shù)的比值作為沖突率,為了方便表示,在實(shí)際沖突率的基礎(chǔ)上加10%作為相對(duì)沖突率,得到的預(yù)中選結(jié)果、經(jīng)過(guò)第一階段沖突消除的匹配結(jié)果、匹配分組的最終結(jié)果的沖突率對(duì)比如圖6所示。

表1 目標(biāo)區(qū)域參數(shù)Table 1 Target area parameters

圖4 目標(biāo)聚類分組前示意圖Fig.4 Schematic diagram of target clustering before grouping

圖5 目標(biāo)聚類分組后示意圖Fig.5 Schematic diagram of target clustering after grouping

表2 目標(biāo)聚類分組結(jié)果Table 2 Target cluster grouping results

表3 無(wú)人機(jī)集群參數(shù)Table 3 Unmanned aerival vehicle cluster parameters

表4 無(wú)人機(jī)匹配分組結(jié)果Table 4 Unmanned aerival vehicle matching grouping results

圖6 匹配分組3個(gè)階段沖突率對(duì)比Fig.6 Comparison of conflict rates of matching groups in three stages

從仿真結(jié)果中可以看出,表4中的匹配分組結(jié)果與各分區(qū)的需求一致,編號(hào)1～60的無(wú)人機(jī)均對(duì)應(yīng)唯一的分區(qū),因此所提出的TPDA算法能夠?qū)崿F(xiàn)滿足分區(qū)要求的無(wú)人機(jī)集群匹配分組,集群中所有無(wú)人機(jī)均得到了匹配分組,分組結(jié)果無(wú)沖突。并且,受益于目標(biāo)分組階段的負(fù)載均衡性調(diào)整算法,匹配到各分區(qū)的無(wú)人機(jī)數(shù)量比較均衡,各分區(qū)待求解的任務(wù)分配問(wèn)題規(guī)?；疽恢?。圖6中的預(yù)中選結(jié)果由于沒(méi)有經(jīng)過(guò)沖突檢測(cè),3種類型任務(wù)的沖突率都較高;第一階段沖突消除按照最優(yōu)性原則替換部分分區(qū)的最優(yōu)解,因此經(jīng)過(guò)第一階段沖突消除的匹配結(jié)果能夠有效地消除部分沖突,在某些情況下甚至能夠完全消除沖突,其沖突率明顯低于預(yù)中選結(jié)果;最終結(jié)果的沖突率為0%,這說(shuō)明第二階段的沖突消除能夠完全消除匹配結(jié)果中的沖突情況。這是因?yàn)榈诙A段局部調(diào)整的策略是按照優(yōu)先級(jí)依次為仍存在沖突的少量分區(qū)從回收池中選擇可行解,已選擇的無(wú)人機(jī)從回收池中移除,從而保證匹配的唯一性,消除所有沖突。

4.2 算法性能對(duì)比分析

算例 1為了驗(yàn)證所提出的目標(biāo)聚類分組算法的性能,在50 km×50 km的范圍內(nèi)隨機(jī)生成30個(gè)目標(biāo)樣本點(diǎn),首先在分組數(shù)量k固定為5的情況下進(jìn)行50次分組的蒙特卡羅仿真實(shí)驗(yàn),與K-means、K-means++算法進(jìn)行對(duì)比,得到的3種算法的SSE性能指標(biāo)對(duì)比圖如圖7所示,分組結(jié)果的目標(biāo)數(shù)量均衡性對(duì)比如圖8所示,算法的求解耗時(shí)對(duì)比如圖9所示。

圖7 SSE性能指標(biāo)對(duì)比圖Fig.7 Comparison chart of SSE performance indexes

圖8 目標(biāo)數(shù)量均衡性對(duì)比圖Fig.8 Comparison chart of target quantity balance

圖9 聚類算法的求解耗時(shí)對(duì)比圖Fig.9 Comparison chart of time consumption of clustering algorithms

從仿真結(jié)果中可以看出,本文中采用的聚類分組算法與另外兩種方法的求解耗時(shí)基本一致,但分組結(jié)果具有更優(yōu)的SSE值和目標(biāo)數(shù)量均衡性,并且算法的穩(wěn)定性更高。這是因?yàn)镵-means算法和K-means++算法沒(méi)有排除離群點(diǎn)的影響,并且初始聚類中心的選擇都具有隨機(jī)性,導(dǎo)致聚類結(jié)果容易陷入局部最優(yōu)。而本文中的改進(jìn)K-means算法在分組之前通過(guò)離群點(diǎn)檢測(cè)將目標(biāo)點(diǎn)樣本中的離群點(diǎn)替換為密集點(diǎn),同時(shí)保留了離群點(diǎn)的載荷信息,有效降低了離群點(diǎn)對(duì)聚類中心的影響。固定的初始聚類中心提高了算法的求解效率和穩(wěn)定性,同時(shí)分區(qū)均衡性調(diào)整算法能夠?qū)D(zhuǎn)移代價(jià)較小的目標(biāo)進(jìn)行調(diào)整,在保證最優(yōu)性的前提下使得分組的結(jié)果負(fù)載更加均衡。

算例 2為了驗(yàn)證所提出的TPDA匹配分組算法的性能,利用表2中典型場(chǎng)景下的聚類分組結(jié)果,按照第4.1節(jié)中的參數(shù)隨機(jī)生成無(wú)人機(jī)集群,設(shè)定沖突消除第一階段的閾值β設(shè)為3,進(jìn)行20次無(wú)人機(jī)集群匹配分組的仿真實(shí)驗(yàn),將TPDA的匹配分組結(jié)果與多對(duì)一的DA算法進(jìn)行對(duì)比,得到的平均匹配值對(duì)比如圖10所示,算法求解耗時(shí)對(duì)比如圖11所示。從仿真結(jié)果中可以看出,TPDA算法的平均匹配值比DA算法更高,這是因?yàn)門PDA算法以所有分區(qū)的最優(yōu)解為出發(fā)點(diǎn),然后對(duì)替換代價(jià)較小的分區(qū)進(jìn)行次優(yōu)解替換,逐步消除沖突尋找可行解。而DA算法按照無(wú)人機(jī)的偏好發(fā)起匹配,分區(qū)只能被動(dòng)地在發(fā)起匹配的無(wú)人機(jī)中選擇最優(yōu)解,容易陷入局部最優(yōu),無(wú)法保證解的全局最優(yōu)性。在閾值β設(shè)為3時(shí),TPDA算法的求解耗時(shí)與DA算法基本一致,因此TPDA算法能夠在保證時(shí)效性的同時(shí),提高匹配結(jié)果的全局最優(yōu)性。

圖10 平均匹配值對(duì)比圖Fig.10 Comparison chart of average matching values

圖11 匹配算法求解耗時(shí)對(duì)比圖Fig.11 Comparison chart of matching algorithm solving time consumption

算例 3算例2的仿真驗(yàn)證了無(wú)人機(jī)集群與聚類中心匹配的最優(yōu)性,為了進(jìn)一步地驗(yàn)證所提出的集群分組調(diào)配方法的有效性,按照第4.1節(jié)中的參數(shù)在任務(wù)區(qū)域中隨機(jī)生成目標(biāo)點(diǎn)和無(wú)人機(jī)集群,進(jìn)行20次分組調(diào)配仿真實(shí)驗(yàn)。利用式(1)中的性能指標(biāo)函數(shù)對(duì)分組調(diào)配結(jié)果進(jìn)行評(píng)價(jià),調(diào)節(jié)系數(shù)λ設(shè)為0.000 5,將本文中的分組調(diào)配方法與采用K-means++聚類和DA算法匹配的方法進(jìn)行對(duì)比,得到的目標(biāo)函數(shù)值對(duì)比如圖12所示。圖12顯示,本文所提出的分組調(diào)配方法在20次仿真實(shí)驗(yàn)中的目標(biāo)函數(shù)值均高于對(duì)比方法,分組后的集群完成分組任務(wù)的代價(jià)更小。因此,改進(jìn)的K-means算法和TPDA算法能夠有效地進(jìn)行目標(biāo)聚類分組和集群匹配分組,通過(guò)分組調(diào)配將大規(guī)模的直接任務(wù)分配轉(zhuǎn)化為組內(nèi)小規(guī)模的任務(wù)分配,提高任務(wù)分配問(wèn)題的求解效率。

圖12 分組調(diào)配算法目標(biāo)函數(shù)值對(duì)比圖Fig.12 Comparison chart of objective function values of grouping deployment algorithm

5 結(jié) 論

本文中針對(duì)異構(gòu)無(wú)人機(jī)集群按任務(wù)分組調(diào)配問(wèn)題,設(shè)計(jì)了一種考慮分組均衡性的任務(wù)聚類分組方法和提高全局最優(yōu)性的無(wú)人機(jī)匹配分組方法。在任務(wù)聚類分組環(huán)節(jié),首先利用局部密度對(duì)目標(biāo)點(diǎn)樣本集合進(jìn)行離群點(diǎn)檢測(cè)預(yù)處理,通過(guò)虛擬目標(biāo)點(diǎn)替換異常點(diǎn)的方法提高聚類精度。然后,對(duì)目標(biāo)進(jìn)行固定初始聚類中心的聚類分組,并進(jìn)行分組均衡性的調(diào)整。在無(wú)人機(jī)集群分組環(huán)節(jié),運(yùn)用穩(wěn)定匹配的思想,對(duì)延遲接受算法進(jìn)行改進(jìn),首先基于最優(yōu)性的考慮,通過(guò)任務(wù)傾向的偏好列表快速地將無(wú)人機(jī)映射到匹配度高的分區(qū),然后設(shè)計(jì)了兩階段的沖突消除過(guò)程,選擇對(duì)全局最優(yōu)性影響較小的可行解,保證匹配的最優(yōu)性、穩(wěn)定性和收斂性,得到無(wú)沖突的匹配分組方案。最后,通過(guò)仿真實(shí)驗(yàn)分析并與其他方法進(jìn)行對(duì)比,驗(yàn)證了本文所提方法的有效性。