基于改進NSGA-III算法的多無人機協同目標分配

摘 要：武器-目標分配問題是戰場環境下無人機對敵方執行打擊任務的關鍵， 其目的是基于目標的威脅、 價值和我方武器的毀傷概率， 尋找合理的武器目標分配方案， 以提高作戰效率。 針對當前多目標優化算法解決靜態武器-目標分配問題時收斂速度慢、 收斂穩定性差， 難以適應當前戰場高度實時性的問題， 提出一種改進的基于參考點的非支配排序遺傳算法。 通過二進制編碼打擊方案并優化初始種群， 引入自適應變異與交叉策略以及種群尋優更新策略， 基于對戰場態勢進行評估得到的威脅矩陣和優勢矩陣， 種群多次迭代后生成目標打擊方案。 最后計算滿足約束條件的Pareto解集， 并將Pareto前沿中的相對最優解作為多無人機的打擊方案。 多次實驗證明， 在較好情況下改進算法相比于原始算法的收斂時間減少46.74%， 目標威脅值降低50.5%， 總飛行航程減少26.46%， 殺傷目標數增加11.76%， 證明該算法在解決多無人機空對地打擊任務目標分配問題時具有合理性和高效性。

關鍵詞：對地打擊； 多無人機； 武器目標分配； 多目標優化； NSGA-III； Pareto解

中圖分類號：TJ760； V279

文獻標識碼： A

文章編號：1673-5048（2024）04-0100-12

DOI： 10.12132/ISSN.1673-5048.2023.0222

0 引 言

隨著無人系統的應用廣泛普及， 在當前作戰環境下產生了多種新穎的戰術樣式， 包括多無人機協同作戰和跨域無人集群協同作戰等。 新戰術樣式下的武器目標分配（Weapon Target Assignment， WTA）問題是當前多無人機、 無人機集群研究的關鍵問題， 是單種類任務分配的重要環節。 根據敵我雙方態勢， 合理為每架無人機分配目標， 以提高多無人機作戰效能［1］， 對于無人作戰領域來說具有重要意義， 能夠通過對無人機有限機載資源的合理分配取得最大化的作戰成果。

WTA問題經過幾十年的研究， 在算法方面一直快速發展， 大致遵循從單目標優化到多目標優化的趨勢［2］。 單目標優化主要求解在給定限制條件下的最優的解決方案， 使目標函數的值達到最優。 李洋等［3］設計了一種基于隨機動態規劃的動態武器目標分配決策算法， 基于戰場態勢轉移概率采用逆向迭代算法生成序貫攔截方案。 強裕功等［4］建立多約束條件下的武器目標優化分配模型， 基于拍賣算法解決了動態武器目標分配問題。 劉攀等［5］提出一種改進的粒子群優化算法， 引入武器轉火時間窗等約束條件， 驗證了粒子群算法解決多導彈的武器目標分配問題的有效性。 Kline等［6］針對武器目標分配問題采用實時啟發式算法進行求解， 提出一種非線性分支定界算法。 多目標優化需找到一個解決方案使其在多個目標函數下同時達到一個平衡點， 即每個解在所有目標函數下都最優。 吳思聰等［7］構建了UUV集群打擊任務分配模型， 引入第3代非支配排序遺傳算法求解， 能夠更好地為決策提供支撐。 邱少明等［8］針對武器目標分配算法中計算耗時較長、 求解效率低的問題， 提出一種多目標簡化群優化算法， 并證明了其較高的計算效率和求解精度。 鄭峰嬰等［9］提出基于自適應概率引導的多目標粒子群控制分配方法， 根據收斂性指標增加變異因子， 實現操縱面多目標控制分配。

上述文獻提出了多種針對WTA問題的優化算法， 但多數只能處理單一目標函數下的優化問題， 而實際的WTA問題往往涉及多個相互沖突的目標， 需要找到一個平衡點。 多目標優化方法存在一定的局限性， 其計算效率和求解質量受限于特定問題的算法和參數設置， 可能無法很好地適應戰場環境中的武器目標分配， 導致解決方案的有效性和實用性受到影響。 在本文的WTA問題中， 需考慮最大程度擊毀敵方無人機的任務需求， 考慮無人機續航能力、 武器數量等的性能限制， 評估敵方的威脅程度， 包括防空系統潛在的反制措施， 以及考慮地形對任務執行的影響。

遺傳算法采取多點并列搜索， 按照適者生存的原理逐代演化產生越來越好的近似解， 因此取得了大量研究成果［10］。 作為遺傳算法的衍生方法， 非支配排序遺傳算法（Non-Dominated Sorting Genetic Algorithms， NSGA）是一種基于Pareto最優概念的多目標優化算法， 由Srinivas等于1995年提出［11］。 NSGA-III算法［12］由NSGA和NSGA-II［13］發展而來， 能夠不受問題性質的限制， 有效地處理復雜問題［14］。

為解決上述問題， 提高戰場環境下的多機目標分配問題的求解質量和收斂速率， 本文將WTA問題建模為多目標優化模型， 在NSGA-III算法的基礎上， 提出改進ABCSA-NSGA-III（Artificial Bee Colony and Simulated Annealing NSGA-III）算法對其求解， 結合人工蜂群算法和模擬退火算法的優勢， 通過算例驗證了改進算法的求解質量。

1 多無人機協同目標分配模型

1.1 場景描述

假設當前處于無人機對目標的攻擊階段， 每架無人機需根據戰場中的目標信息獲取全局的戰場態勢， 再對所跟蹤鎖定的目標發射合適的武器以達到摧毀的目的。

為了實現有效的多無人機對地打擊協同目標分配， 首先提取出四個關鍵因素： 目標信息、 武器信息、 無人機性能參數和作戰要求。 假設我方擁有n架構型和攜帶武器類型均相同的無人機， 表示為無人機集合U={u1， u2， …， ui， …， un}， U包含n架無人機， 其中無人機載彈集合為W={w1， w2， …， wi， …， wnn}， W包含nn枚導彈， n≤nn。 而敵方有m個不同地面目標， 組成目標集合T={t1， t2， …， tj， …， tm}， T包含m個不同的目標。 本文的最終目標是將這n架無人機的武器有效地分配給這m個不同的目標， 以執行對地打擊任務， 作戰想定場景如圖1所示， 在目標區域可能存在多個不同類型的敵方目標， 如裝甲車、 坦克、 導彈車、 指揮所等， 其具體位置尚未確定， 導彈車應具備雷達和防空導彈， 對我方無人機構成潛在威脅。

1.2 模型約束

根據我方無人機及攜帶導彈的性能， 在無人機發射導彈時應滿足以下條件：

（1） 每架無人機的所有導彈全部被分配給目標。

∑xu， ij=nn（1）

（2） 一枚導彈只能分配給一個目標。

∑mj=1xu， ij=1（2）

根據多無人機打擊任務的要求， 決策變量xu， ij存在以下三種分配模型， 如圖2所示。

（1） 當我方無人機數量等于敵方目標數量（n=m）時， 在進行分配時需找到一對一的分配關系， 保證每個目標都會被打擊。

（2） 當我方無人機數量大于敵方數量（n>m）時， 在進行分配時需為我方多個無人機分配同一目標， 共同執行打擊任務。

（3） 當我方無人機數量小于敵方數量（n<m）時， 在進行分配時我方一架無人機可分配多個任務目標， 并按照一定的次序依次打擊這些目標， 對無人機的燃油性能要求較高， 但這種情況下完成打擊任務所用的無人機數量最少。

綜上， 決策變量根據不同的任務模型有

xu， ij=xu， i n=m

xum， uk， i n>m

xu， i， j n<m（3）

1.3 目標函數

根據1.1節和1.2節對模型的定義和約束， 在本文的WTA問題中， 多無人機的目標分配是指為多無人機組中每架攜帶導彈的無人機分配一個或多個打擊目標， 每架飛機掛載的導彈只能被分配到一個目標， 每個目標可以被一個或多個導彈攻擊， 以使整個無人機組的打擊效率和資源利用達到最優化。 使用NSGA-III算法對本文的WTA問題進行求解時， 首先需要將目標分配問題轉化為一個多目標優化問題。 考慮到打擊任務的具體需求， 以最大化我方無人機對敵方目標的傷害、 最小化敵方目標對我方無人機的威脅和最小化總飛行航程為衡量標準， 將目標分配模型定義為

minD=∑nu=1∑mi=1∑mj=1du， ij·xu， ij

minN=∑nu=1∑mj=1∑mi=1Tu， i·Psu， ij

maxF=∑ni=1∑rj=1［1－Psu， ij］ （4）

式中： minD表示最小化飛行總航程代價； du， ij為航程代價； xu， ij為決策變量； minN表示使敵方剩余目標的威脅值最小化； maxF表示最大化對敵方目標的毀傷； Tu， i為某時刻敵方對我方的威脅矩陣； r為我方無人機攜帶的導彈數； 目標的生存概率Psu， ij取決于對目標的攻擊情況， 即

Psu， ij=∏ni=1∏rj=1［1－Ddu， ij］nmu， ij（5）

式中： nmu， ij為目標受到攻擊的導彈數量； Ddu， ij為我方無人機發射導彈對目標的摧毀效果。

Ddu， ij=ωe·Pdu， ij·Wsu， ij， i， j=1， 2， …， m（6）

式中： 0<ωe<1表示環境對導彈殺傷率的影響； Pdu， ij為無人機u對目標的態勢優勢； Wsu， ij為我方無人機攜帶導彈的理想摧毀概率。

至此， 將目標分配問題轉換為多目標優化問題［15］， 下面用NSGA-III算法對問題進行求解。

2 基于ABCSA-NSGA-III算法的目標分配問題求解

2.1 多目標優化問題

將無人機的打擊目標分配模型作為多目標優化問題（Multi-Objective Optimization Problem， MOP）研究， 需要同時優化兩個不可直接比較且可能相互沖突的目標函數［16］， 意味著要優化一個目標函數的值可能會以犧牲另一個目標為代價。 算法的最優解取決于最后一次迭代中種群的非支配解集， 從而得到Pareto解集［17］， 由于這種相互制約的關系， 通常不存在唯一的最優解， 而是存在一系列權衡不同目標之間權重的解， 稱為Pareto前沿。

因此， 本文的目標是尋找Pareto前沿上的目標分配方案， 這些方案在不同程度上優化了多個沖突的目標， 在不大幅度劣化某一目標的前提下改善其余目標。

2.2 標準NSGA-III算法原理

NSGA-III算法的基本思想是通過不斷迭代生成一組非支配解集合， 其中每一個非支配解均為最優解的近似。 在每次迭代中， 算法會根據當前解集合中的非支配解生成一組新解， 通過一系列篩選和排序， 生成下一代解集合。 通過這種方式不斷同時優化多個目標函數， 最終得到一組最優的目標分配方案。 這樣， NSGA-III算法可以在保證種群多樣性的同時， 有效地尋找到Pareto最優解集合， 即那些在所有目標函數上都無法被改進的解集合。

標準NSGA-III算法的求解步驟如下：

（1） 隨機初始化規模為N的初始種群Pt， 計算種群中每個個體的適應度函數值。

（2） 對初始種群Pt進行非支配排序， 在排序結果中選擇較優的個體進行交叉和變異操作， 以產生子代種群Qt。 將兩個種群結合， 形成大小為2N的新子代種群Rt。

（3） 進行快速非支配排序， 根據非支配關系保留優良且多樣的個體， 組成新的父代種群Pt+1。

（4） 通過遺傳算法的基本操作產生新的子代種群Qt+1， 將Pt+1與Qt+1合并形成新的種群Rt+1， 重復以上操作， 直到到達指定迭代次數。

NSGA-III算法的關鍵步驟之一是采用非支配排序， 首先對個體進行分層， 依據是每個個體之間的支配與非支配關系， 每一層的個體都是相互非支配的， 即不存在一個個體在所有目標函數上都優于另一個個體。 然后根據每個個體的所處層次以及與參考點的關系進行選擇， 保留固定規模的個體， 用于子代種群的生成。 引入參考點選擇機制， 通過判斷區域的密度選擇搜索方向， 對于那些非支配并且接近參考點的種群個體進行保留， 達到充分探索解空間的目的。

2.3 求解目標分配問題的改進NSGA-III算法

2.3.1 基于二進制編碼的打擊方案編碼策略

在NSGA-III算法中， 染色體編碼方式通常有二進制編碼和實數編碼等。 由于NSGA-III算法側重于解決連續的多目標優化問題， 而目標分配問題是離散空間的組合優化問題， 為了避免實數編碼中需要對每個決策變量進行歸一化處理的問題， 以及在轉化為實數時出現不必要的精度誤差， 在進行交叉和變異操作時更加方便易行， 本文采用二進制編碼。

具體來說， 用決策變量x表示目標分配方案， 決策變量矩陣x的行列數為r和n， 代表有r個武器和n個待打擊目標。 x的第i行（i為奇數）代表選取第（i+1）/2號無人機攜帶的1號武器打擊的目標， 第i行（i為偶數）代表選取第i/2號無人機攜帶的2號武器打擊的目標， 元素為1的對應列m為攻擊目標序號， 元素為0表示不打擊。 為便于計算， 將決策變量x的矩陣按照行順序壓縮為一維向量， 壓縮后的向量即為一條染色體， 每條染色體上的一個基因對應無人機是否攻擊目標的布爾值。

染色體分布集合的示意圖如圖3所示。 N代表種群的個體數， 種群個體即為武器目標打擊方案， 這樣可以確保每個決策變量的取值范圍相同。

根據決策變量x計算適應度值時， 先將二進制編碼轉換為實際的解決方案， 用目標函數對其進行評估。 每個敵機對所有我方無人機的總威脅值基于威脅矩陣T算出， 剩余目標數基于優勢矩陣P算出。 將剩余目標數與決策變量x相乘， 如果染色體為1， 得到的是其剩余量； 如果染色體為0， 得到的剩余量為0， 從而得到每個目標的總剩余量。 最后， 將每個敵機對所有我方無人機的總威脅值乘以每個目標的剩余量， 便可得到剩余目標威脅。

2.3.2 基于改進人工蜂群算法的種群初始化策略

對于NSGA-III算法而言， 初始種群的質量對于算法的收斂效率具有重要影響。 為了實現對初始種群的優化， 本文提出一種結合人工蜂群（Artificial Bee Colony， ABC）算法和NSGA-III算法的混合方法， 可以綜合兩種算法的優點。 ABC算法具有高速高效的搜索特性以及較強的全局搜索能力， 能夠更好地探索解空間， 避免陷入局部最優解， 提高整體搜索效率。

ABC算法是一種模擬自然蜜蜂覓食行為的優化算法， 蜜源代表目標分配問題的可行解， 可行解的好壞即蜜源的優劣， 用適應度值來評價。 傳統ABC算法解決的是連續優化問題， 在產生探索新解時采用的是已有解直接加上隨機擾動， 可能無法有效地探索離散空間。 針對目標分配問題的特點， 在生成蜜源時設計了離散的初始編碼策略， 在蜜源位置更新時， 采用基于矩陣行列交換的行列狀態轉移方法， 最終得到初步尋優的解空間。 ABC算法用在確定初始種群階段， 其適應度函數FABC為三個目標函數加權平均得到的適應度值：

FABC=ω1·F+ω2·D+ω3·N（7）

式中： ω1， ω2， ω3分別為三個目標函數的加權系數。

蜂群包括三種個體： 雇傭蜂、 觀察蜂和偵查蜂。 雇傭蜂的任務是利用已有的蜜源信息搜尋新蜜源， 并以一定的概率與觀察蜂分享； 觀察蜂在蜂巢的招募區內根據雇傭蜂提供的蜜源信息來選擇蜜源； 如果蜜源在多次迭代后適應度值未提高， 則雇傭蜂變為偵查蜂， 在蜂巢附近尋找新的蜜源。

改進ABC算法具體實現步驟如下：

（1） 初始化階段。 隨機生成一群蜜蜂個體， 這些個體即為初始解。

（2） 評估階段。 對每個蜜蜂個體計算其適應度值， 得到這群蜜蜂個體的適應度值。

（3） 判斷階段。 是否到達指定迭代次數， 是則算法終止， 返回找到的最優解集合， 作為NSGA-III算法的初始種群； 否則進行步驟（4）。

（4） 雇傭蜂階段。 每個雇傭蜂個體根據其當前位置尋找相鄰的下一個蜜源， 并計算其適應度值。 根據貪心策略選擇蜜源， 如果新解更優， 雇傭蜂更新自己的位置為新蜜源位置； 否則保留原位置， 該蜜源的開采度+1。

（5） 觀察蜂階段。 觀察蜂計算每個蜜源xi被選擇的概率。

p（xi）=f itotal∑SNj=1f jind（8）

式中： fi為解xi的總適應度值； SN為總蜜源數。 計算所有個體的選擇概率之和， 即累積概率為

qacc（xi）=∑ij=1p（xj）（9）

根據累積概率基于輪盤賭法選擇一個蜜源， 并在蜜源附近隨機產生新解計算其適應度值， 與原始解決方案進行比較。 如果新解更優， 則觀察蜂選擇新解； 否則保留原始解。

（6） 偵查蜂階段。 判斷蜜源xi是否滿足被遺棄的條件， 如果同一蜜源被開采的次數大于限制次數， 則代表此位置已經陷入局部最優， 這個解對應的雇傭蜂變成偵查蜂。 偵查蜂在蜂房附近隨機地搜索新解并計算其適應度值， 如果發現更優的解決方案， 偵查蜂將新解保留。

（7） 更新最優解階段。 記錄全局最優解集合， 返回步驟（3）。

ABC算法流程圖如圖4所示。

在每個階段中， 個體根據其適應度值和其他個體之間的交互生成新的解， 如果新解比當前個體更好， 則接受新解。 ABC算法作為輔助工具， 使用加權和法將目標函數轉換為一個單一的適應度值， 迭代多次以找到單目標問題的最優解。 為進一步尋找一系列互不支配的Pareto最優解， 使用NSGA-III算法繼續優化改進， 將ABC算法得到的解作為NSGA-III算法的初始父代種群， 可以增加初始種群的豐富度和整體質量， 加速進化過程和收斂過程， 減少尋找最優解所需的時間， 從而提高整體算法的性能。

2.3.3 基于自適應策略的種群交叉與變異策略

交叉與變異也是影響NSGA-III算法收斂性的關鍵。 錦標賽法選擇優秀個體， 確保了只有最適應的個體才能參與交叉和變異操作， 從而有效地保留了種群中的優秀基因片段， 并將其傳遞給下一代。

交叉操作是交叉重組種群中每個個體的部分基因以實現全局搜索。 變異操作是隨機修改種群個體的一部分基因以實現局部搜索， 增加種群的多樣性。 采取自適應調整優化的交叉和變異算子， 使其能夠根據適應度函數的大小動態地改變， 可以避免尋優效率過低的問題。

在遺傳算法的早期， 應該采用較大的變異率和較小的交叉率， 以便盡快掌握全局范圍內的解； 進入后期， 則需要減小變異率和增加交叉率， 以便更好地跳出局部最優解， 并生成更多新的個體。 交叉和變異概率計算如下：

Passc=Pc， max－Pc， max－Pc， min1+ecosfave－fmaxfave－fmin·π fmax≤fave

Pc， maxfmax>fave （10）

Passm=Pm， max－Pm， max－Pm， min1+ecosfave－fmaxfave－fmin·π fmax≤fave

Pm， maxfmax>fave（11）

式中： Pc， max， Pc， min分別為設定交叉概率的最大值、 最小值； Pm， max， Pm， min分別為設定變異概率的最大值、 最小值； fave為適應度函數在當前解的平均值； fmax， fmin分別為適應度函數在當前解的最大值和最小值。

在交叉操作中， 采用單點交叉方式。 對于每個個體， 如果其交叉概率小于預設的交叉率， 則隨機選擇一個交叉點， 然后將兩個父代個體在該交叉點之后的基因部分進行互換， 從而實現基因的交叉。 這樣， 兩個個體之間的遺傳信息得到重新組合。 變異操作采用單點變異方式。 對于每個個體的每個基因， 計算其變異概率， 如果小于預設的變異率， 則將該基因進行取反， 即翻轉對應的二進制位。 這樣可以引入新的遺傳信息， 增加個體的多樣性。 交叉操作和變異操作示意圖如圖5～6所示。

通過重復進行交叉和變異操作， 可以不斷生成新的個體并更新適應度， 這個過程將持續進行直到停止。 在優化過程中， 交叉率與變異率根據當前種群的階段動態調整。 自適應調整使算法更靈活地適應求解過程的不同階段， 提升了整體算法的計算效率， 提高收斂速度和全局搜索能力， 搜索到更好的個體解空間， 增加了種群發現全局最優解的可能性， 同時也加速了多目標優化問題的解決速度。

2.3.4 基于模擬退火算法的種群更新策略

為了在交叉和變異環節之后更有效地尋找優質解， 本文將NSGA-III算法與模擬退火（Simulated Annealing， SA）算法相結合， 在種群個體變異之后， 對變異后的個體進行二次尋優。 SA算法尋優速度快、 搜索效率高， 善于跳出局部最優解， 尋找全局最優解， 適用于解決離散問題， 與NSGA-III算法結合可以避免其過早收斂。 充分利用二者的優勢， 從而獲得進化程度更高的種群。

SA算法的關鍵在于新解的生成策略和接受新解的概率策略。 新解的生成策略規定了從當前解生成相鄰的解的方式。 為了提高整個算法的執行速度， 在提升解的質量的同時， 基于“局部搜索”的思想， 設計解的生成策略為： 在當前解的鄰域范圍內進行隨機擴展。 考慮到目標分配矩陣的稀疏特性， 為減少算法耗時， 對當前解進行部分變換， 包括對當前解中隨機兩條染色體的一個或多個基因進行置換、 互換、 插入、 刪除操作以構成新解， 該過程的示意圖如圖7所示。

產生新解后， 計算當前解和新解之間的代價值差異， 若新解更優則保留， 若不如當前解， 以概率P判斷是否接受保留。 使用溫度參數來控制接受劣解的概率。 隨著算法的迭代進行， 溫度逐漸降低以減小接受劣解的概率。

依據Metropolis準則， 接受新解Xnew的概率策略為

Δf=f（Xpre）－f（Xnew）（12）

P=1 if Δf≥0

exp－［f（Xpre）－f（Xnew）］Tiif Δf<0 （13）

式中： f（Xnew）為新解的代價值； f（Xpre）為舊解的代價值； Δf為兩者的差值； exp（Δf/Ti）為粒子在溫度Ti時趨于平衡的概率。

通過種群更新操作， 能夠逐步改進種群中的個體， 使其逐漸趨向Pareto前沿， 從而實現多目標優化問題的收斂性， 幫助算法在搜索空間中找到一組近似最優解， 這些解代表了不同權衡的多個目標值。

2.3.5 非支配排序與參考點選擇

對交叉、 變異后的種群中所有個體進行非支配排序。 支配的定義是： 對于M個目標分量， 如果決策變量xa和xb對于所有目標都有f（xa）≤f（xb）成立， 且存在一個目標分量使得f（xa）<f（xb）成立， 則稱xa支配xb。

（1） 對當前N個解進行非支配層劃分。 將非支配層f i的種群個體按等級（i=1， 2， …， l）順序放入Stgrade中， 若|Stgrade|=N， 則Pt+1=Stgrade； 若|Stgrade|>N， 則下一代的部分解為Pt+1=∪l－1j=1Fjgrade， 剩余的部分Kgrade=N－|Pt+1|從Flgrade中選擇。

（2） 確定參考點。 采用文獻［18］的方法產生內層和外層兩個參考點的超平面， 首先產生外層超平面P1， grade， 再使用P1， grade搭建內層超平面P2， grade， 對于每個p′ij， grade∈P2， grade和pij， grade∈P1， grade， 有

p′ij， grade=12·pij， grade+12·M（14）

即可得到參考點集合Pgrade=P1， grade∪P2， grade。

（3） 種群個體的自適應歸一化。 首先， 定義種群Stgrade的理想點為∪tτ|=0Sτgrade的最小值zmini， i=1， 2， … ， M， 從而構造理想點z-=（zmin1， zmin2， …， zminM）， 基于理想點轉換目標函數為

fi′（x）=fi（x）－zmini（15）

其次， 求出每個坐標軸對應的額外點：

ASF（x， w）=maxMgradei=1fi′（x）/wi， x∈Stgrade（16）

zi， max=s：argmin x∈StgradeASF（x， wi）

wi=（τ， …， τ）T， τ的個數為目標函數個數，

τ=10-6， wij=1

（17）

式中： zi， max為對于第i個轉換目標fi′（x）產生的額外目標向量， 這M個額外向量構成線性超平面Pr， 并求出截距ai， i=1， 2， …， M， 進而自適應歸一化目標函數值為

f ni（x）=（fi′（x）－zmini）/（ai－zmini）， i=1， 2， …， M（18）

種群中的個體被歸一化到了參考點所在平面。

（4） 關聯參考點和個體保留操作。 尋找所有個體sref距離Pr的參考點wref的參考線d（sref， wref）， 求得距離最近參考點π（sref）及其對應的距離d（sref）：

d（sref， wref）=（sref-wTref·sref·wref）/|wref|（19）

π（sref）=wref：argminw∈Prd（sref， wref）（20）

d（sref）=d（sref， π（sref））（21）

求出與第j個參考點關聯數ρj的最小值Jmin， Ij-為參考點j-所聯系的個體。

Jmin={j：argminj∈Prρj}（22）

j=random（Jmin）（23）

Ij-={sref：π（sref）=j， sref∈Flgrade}（24）

將關聯較少的參考點所對應的個體保留至下一次計算。 如果有多個關聯數較少的參考點Jmin， 從中隨機選擇一個參考點保留。

綜上所述， 通過計算種群中每個個體被其他個體支配的數量， 建立非支配排序等級， 同一等級的個體互不支配， 上一等級的個體支配下一等級， 按照層級順序優先將上層的個體添加到子代種群中。 對不能完全加入到下一代的層級， 包括設置參考點、 種群的自適應標準化、 關聯操作和個體保留操作， 個體與歐式距離最近的參考點關聯， 選擇關聯較少參考點周圍的K個非支配個體成為新父代， 由此可以得到優秀的下一代種群個體并確保選擇的多樣性。

2.4 求解目標分配問題的ABCSA-NSGA-III算法

（1） 初始化種群， 包括種群編碼和種群生成。 基于二進制編碼隨機生成一個初始的候選解種群， 種群的個體數為N， ABC算法對初始種群進行優化。 計算得到種群中每個個體的適應度值（目標函數值）， 評價對應每種目標分配方案的好壞。

（2） 錦標賽選擇。 采用錦標賽選擇的方式在種群中選出優秀個體成為第一代父代， 具體如下：

a. 參與錦標賽的每個個體進行適應度計算， 適應度越高的個體得分越高。

b. 從種群中隨機選擇2個個體， 在二元錦標賽選擇中， 每個個體被選擇的概率相同。

c. 比較選中個體的適應度值， 選擇適應度值最好的個體為獲勝者， 將其選入下一代種群。

重復多次， 重復次數與原始種群的個體數相同， 直到新的種群規模達到原始種群的規模。 由于每次選擇是獨立的， 相同的個體可能在不同輪次中被多次選中， 某些個體可能在錦標賽中從未被選中， 允許優良個體更有機會被選中的同時保留了一定的隨機性以確保多樣性。

（3） 交叉與變異。 對父代種群進行自適應交叉和變異產生新子代。

（4） 交叉與變異后的種群優化。 基于SA算法對新子代進行擴展， 得到二次尋優后的新解。

（5） 合并得到新種群。 合并父代和子代， 得到規模為2N的新種群。

（6） 非支配排序與個體選擇。 對新種群進行非支配排序和參考點選擇， 包括建立種群的非支配分層、 非支配層級中的種群選擇。

（7） 判斷迭代次數。 判斷T是否大于最大迭代數， 若沒有， 則T=T+1， 并返回步驟（3）； 否則算法運行結束。

ABCSA-NSGA-III算法流程圖如圖8所示。

3 仿真實例與結果分析

3.1 場景與參數設置

設置兩組仿真場景， 按武器數量X和目標數量Y分為小規模場景和中規模場景。 表1為不同場景下的武器數和目標數。

假設我方有4架或8架無人機， 每架無人機配備2個同類型武器， 分別在10和20個地面目標中挑選目標進行打擊， 且對每個目標可以使用任意數量武器， 武器對目標的摧毀概率只與武器的類別有關。 表2為敵方目標類型。

以中規模場景為例， 我方無人機數量為8架， 敵方目標數量為20。 我方無人機與敵方目標的參數設置如表3～4所示。

地面目標j（1～20）對我方無人機i（1～8）的威脅值如表5所示。

3.2 仿真實驗及結果

實驗1： 在小規模場景（X=8， Y=10）下應用傳統NSGA-III算法和三種改進型NSGA-III算法分別進行獨立實驗， 比較ABCSA-NSGA-III算法在不同種群規模和參數配置下的實驗情況。 各算法初始參數設置如表6所示。

ABC算法中的蜜蜂數量設置為300個， 迭代次數設置為50， 判斷是否放棄蜜源的采蜜次數為150次； SA算法的初始溫度設置為1 000 ℃， 終止溫度設置為5 ℃， 降溫率設置為0.6。 進行20次獨立實驗， 得到各算法的目標函數表現如表7所示。

應用NSGA-III算法和三種改進型NSGA-III算法分別進行50次獨立實驗， 設置多組對照實驗對不同算法的收斂時間進行測試， 實驗結果如表8所示。

由表7～8可以看出， ABCSA-NSGA-III算法在收斂速度上具有明顯優勢， 其在種群規模、 迭代次數均不同的4種情況下的50次實驗平均收斂時間為0.96 s， 1.00 s， 1.14 s， 1.57s ， 與原始NSGA-III算法相比分別提速8XhePl3vk3N/uAjpd1BbMjg3q4W4B2OyES5zeHXqc7Y=17.95%， 10.71%， 44.66%， 6.55%， 相較于原始的NSGA-III算法， 時間復雜度未見明顯的上升。

通過在同一組小規模測試問題上多次獨立運行四種算法， 并比較其解質量可知， 基于ABCSA-NSGA-III算法得到的目標函數值的平均值、 最好值均明顯優于原始算法， 證明了改進的有效性。 實驗2： 在中規模場景（X=16， Y=20）下基于ABCSA-NSGA-III算法分別對模型中3個目標函數同時進行求解。

迭代過程中3個目標函數的最小值、 最大值、 平均值變化曲線如圖9～11所示。

由圖9可知， 隨著迭代次數的增加， 剩余目標威脅的最大值逐漸增加并在第232代逐漸收斂于276.43； 最小值上下波動， 并在第234代收斂于37.52； 平均值波動幅度較大， 在第180代漸進收斂于160。

由圖10可知， 飛行航程的最大值波動較大， 在第298代為22 303 m； 最小值逐漸減小， 在第285代收斂于1 891 m； 平均值雖波動幅度較大， 但仍看出在逐漸減小， 在第297代為7 704.37 m。

由圖11可知， 期望殺傷數的最小值逐漸減小并在第231代收斂于2.83； 最大值經過一次反方向大幅度波動之后逐漸增加， 在第264代收斂于17.10； 平均值在第150代開始漸進收斂于9。

綜上， 剩余目標威脅的最小值、 飛行航程的最小值逐漸減小， 殺傷目標數的最大值逐漸增大， 并分別在迭代次數為234， 285， 264時趨于穩定， 表明各目標函數已經達到最優值。

在迭代過程中， 每一代的Pareto集中最優解的個數都不相同， 在運行300次后得到一組Pareto解集， 圖12所示為非支配解的分布情況。

由圖12可以看出， 當剩余目標威脅值較小、 期望殺傷數較大時， 飛行航程通常較大， 這意味著在剩余目標威脅最小、 期望殺傷數最大和飛行航程最小這三個目標之間存在一種矛盾關系。 在這種情況下， 算法會產生一組非支配解， 表9列舉了部分Pareto解集。

從表中可以看出， 隨著Pareto解的飛行航程趨于減少， 剩余目標威脅值在逐漸增加， 說明這兩個優化目標是矛盾的。 而當期望殺傷數增加時， 剩余目標威脅值在減小， 說明這兩種指標的數據同時變好， 而飛行航程在增加， 說明該指標變差。 由此看出， 飛行航程與剩余目標威脅值、 期望殺傷數是矛盾對立的。 如果僅采用單目標優化算法求解， 則無法兼顧對立的目標。 使用本文設計的ABCSA-NSGA-III算法求解， 可以最終確定一組Pareto解集， 該解集中的每個解都能夠兼顧這3個優化目標， 由此得到優化后較為合理的目標打擊方案。

進一步對Pareto解集進行篩選， 在該想定中， 解集1～6的剩余目標威脅值相差為44%， 飛行航程相差為68%， 期望殺傷數相差為19%， 差異較小， 主要考慮其余兩個目標函數， 對比后選擇剩余目標威脅值最小的Pareto解集1。 表10為此時對應的打擊方案。

分配結果表示， 除目標4， 9， 12， 15未被分配武器外， 其余每個目標均被成功打擊。

無人機的目標分配結果如圖13所示。

綜合考慮優勢矩陣和威脅矩陣， 經過計算， 以最大程度保護我方無人機和擊毀敵方目標為準則， 上述分配方案是較優的武器目標分配方案。

實驗1和實驗2中， ABCSA-NSGA-III算法在不同的問題規模和參數配置下， 均能表現出較快的收斂時間和較優的解集， 從而證明該算法可以適應不同規模和不同參數的環境， 具有有效性。

實驗3： 為評估ABCSA-NSGA-III算法的改進效果， 分別將ABCSA-NSGA-III算法與NSGA-III算法、 ABC-NSGA-III算法、 SA-NSGA-III算法在同一場景下進行比較， 證明ABCSA-NSGA-III算法在解決同構無人機目標分配問題的有效性。

該實驗在中規模場景下進行， 我方無人機數量為8架， 敵方目標數量為20。 各算法的參數設置與實驗1相同。 ABCSA-NSGA-III算法與NSGA-III算法、 ABC-NSGA-III算法、 SA-NSGA-III算法的對比情況如圖14～17及表11所示。

對于模型期望值， 戰場環境下希望敵方的剩余目標威脅值要盡可能小， 我方飛行總航程盡可能小。 文中所提算法的剩余目標威脅值為37.52， 飛行總航程為1.89 km， 期望殺傷數為17.10。 對比其余三種算法， 所提算法求得解的值均更優。

對于算法運行收斂速率及收斂所需迭代次數， ABCSA-NSGA-III算法在第200代左右收斂， NSGA-III算法直到第300代才取得最優解， SA-NSGA-III算法在第275代附近取得理想值， 而ABC-NSGA-III算法由于提高了初始解的質量， 同樣在第200代附近便取得理想值。 對比其余兩種算法， 所提算法求得解的值均更優。

可以看出， 與NSGA-III算法相比， ABC-NSGA-III算法顯著提高了初始解的質量， 縮短了算法的收斂時間。 SA-NSGA-III算法在對初始解尋優過程中有明顯優勢， SA算法雖然增加了程序計算量， 但增加的運行時間較少， 在可接受范圍內， 并通過局部搜索顯著提高了解的質量， ABCSA-NSGA-III算法綜合了兩者優點， 既優化了初始解， 顯著減少了總體求解過程的收斂時間， 對比NSGA-Ⅲ算法總用時縮減了46.74%， 迭代次數明顯降低， 又找到了相對目標函數最優的打擊方案， 從而較好地驗證了ABC-NSGA-III算法的有效性。

綜上所述， 本文設計的ABCSA-NSGA-III算法擁有更好的穩定性， 而且只需要更少的迭代次數就能達到收斂。 此外， 該算法有助于使剩余目標的威脅值、 飛行航程更小， 殺傷數更大， 具有更好的全局搜索能力， 能夠有效地避免局部最小值， 較好地適應戰場的不確定性和對實時性的要求， 得出合理的攻擊方案。

4 結 論

本文針對多無人機協同執行打擊任務的武器目標分配問題， 在考慮導彈和無人機性能約束的基礎上， 首先將靜態武器目標分配問題轉換為多目標優化問題， 在目標分配模型建立的同時考慮剩余目標威脅、 期望殺傷數以及飛行航程三個目標函數， 設計了改進的基于非支配排序遺傳算法的靜態武器目標分配算法， 基于二進制編碼引入ABC搜索算子和SA優化算子， 對初始種群、 自適應交叉變異后的種群進行尋優， 最終通過實例與改進前的算法進行比較， 發現打擊目標的效果明顯好于之前， 為解決多目標優化的靜態目標分配問題提供了可行且高效的算法。

該算法仍存在一些不足， 如交叉與變異過程雖然引入了自適應策略， 但操作過程中缺乏引導性策略以及精英個體保留策略， 可能導致過程中損失了部分較優解； 該算法目前只能解決靜態武器目標分配問題， 不能解決動態分配， 在未來的工作中有待進一步研究。

參考文獻：

［1］ 甄子洋， 江駒， 孫紹山， 等. 無人機集群作戰協同控制與決策［M］. 北京： 國防工業出版社， 2022.

Zhen Ziyang， Jiang Ju， Sun Shaoshan， et al. Cooperative Control and Decision of UAV Swarm Operations［M］. Beijing： National Defense Industry Press， 2022.（in Chinese）

［2］ Kline A， Ahner D， Hill R. TheJ3xvbYDMwGiZ8G/npOyDNza05DME+kO+HsArvtPhwFs= Weapon-Target Assignment Problem［J］. Computers & Operations Research， 2019， 105： 226-236.

［3］ 李洋， 劉耿， 胡曉惠， 等. 基于SDP的動態武器目標分配決策算法研究［J/OL］. 航空兵器， doi： 10.121321ISSN.1673-5048.2023.0093.

Li Yang， Liu Geng， Hu Xiaohui， et al. SDP-Based Dynamic Weapon Target Assignment Algorithm ［J/OL］. Aero Weaponry， doi： 10.121321ISSN.1673-5048.2023.0093. （in Chinese）

［4］ 強裕功， 宋貴寶， 劉鐵， 等. 基于拍賣算法的動態防空武器目標分配［J］. 兵工自動化， 2023， 42（7）： 50-54.

Qiang Yugong， Song Guibao， Liu Tie， et al. Dynamic Air Defense Weapon Target Assignment Based on Auction Algorithm［J］. Ordnance Industry Automation， 2023， 42（7）： 50-54.（in Chinese）

［5］ 劉攀， 徐勝利， 張迪， 等. 基于粒子群優化的多導彈動態武器目標分配算法［J］. 南京航空航天大學學報， 2023， 55（1）： 108-115.

Liu Pan， Xu Shengli， Zhang Di， et al. Multi-Missile Dynamic Weapon Target Assignment Algorithm Based on Particle Swarm Optimization［J］. Journal of Nanjing University of Aeronautics & Astronautics， 2023， 55（1）： 108-115.（in Chinese）

［6］ Kline A G， Ahner D K， Lunday B J. Real-Time Heuristic Algorithms for the Static Weapon Target Assignment Problem［J］. Journal of Heuristics， 2019， 25（3）： 377-397.

［7］ 吳思聰， 吳曦. 基于NSGA-Ⅲ的UUV集群打擊任務分配模型［J］. 水下無人系統學報， 2023， 31（3）： 474-480.

Wu Sicong， Wu Xi. UUV Cluster Strike Task Allocation Model Based on NSGA-Ⅲ［J］. Journal of Unmanned Undersea Systems， 2023， 31（3）： 474-480.（in Chinese）

［8］ 邱少明， 王雪珂， 杜秀麗， 等. 基于改進多目標簡化群優化算法求解動態武器目標分配問題［J］. 計算機應用與軟件， 2023， 40（6）： 242-249.

Qiu Shaoming， Wang Xueke， Du Xiuli， et al. Weapon Target Assignment Based on Improved Multi-Objective Simplified Swarm Optimization［J］. Computer Applications and Software， 2023， 40（6）： 242-249.（in Chinese）

［9］ 鄭峰嬰， 王峰， 甄子洋， 等. 先進布局無人機多目標自適應概率引導控制分配［J］. 控制理論與應用， 2022， 39（12）： 2366-2376.

Zheng Fengying， Wang Feng， Zhen Ziyang， et al. Control Allocation of Multi-Objective Adaptive Probabilistic Guidance for Advanced Layout Unmanned Aerial Vehicle［J］. Control Theory & Applications， 2022， 39（12）： 2366-2376.（in Chinese）

［10］ 畢文豪， 張夢琦， 高飛， 等. 無人機集群任務分配技術研究綜述［J/OL］. 系統工程與電子技術， doi： 10 12305/j.issn.1001-506X.2024.03.18.

Bi Wenhao， Zhang Mengqi， Gao Fei， et al. Review on UAV Swarm Task Allocation Technology［J/OL］. Systems Engineering and Electronics， doi： 10 12305/j.issn.1001-506X.2024.03.18. （in Chinese）

［11］ Srinivas N， Deb K. Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms［J］. Evolutionary Computation， 1994， 2（3）： 221-248.

［12］ Jain H， Deb K. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach， Part II： Handling Constraints and Extending to an Adaptive Approach［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（4）： 602-622.

［13］ Deb K. An Efficient Constraint Handling Method for Genetic Algorithms［J］. Computer Methods in Applied Mechanics and Engineering， 2000， 186（2/3/4）： 311-338.

［14］ 牛源， 崔志華， 白慧. 異構多無人機中的任務分配優化問題［J］. 小型微型計算機系統， 2023， 44（8）： 1720-1727.

Niu Yuan， Cui Zhihua， Bai Hui. Task Allocation Optimization in Heterogeneous Multi-UAVs［J］. Journal of Chinese Computer Systems， 2023， 44（8）： 1720-1727.（in Chinese）

［15］ 劉西， 李賢， 陳偉， 等. 基于NSGA-Ⅲ算法的多目標分配方法研究［J］. 空天防御， 2021， 4（1）： 109-114.

Liu Xi， Li Xian， Chen Wei， et al. Research on Multi-Objective Assignment Method Based on NSGA-Ⅲ Algorithm［J］. Air & Space Defense， 2021， 4（1）： 109-114.（in Chinese）

［16］ Hua Y C， Liu Q Q， Hao K R， et al. A Survey of Evolutionary Algorithms for Multi-Objective Optimization Problems with Irregular Pareto Fronts［J］. CAA Journal of Automatica Sinica， 2021， 8（2）： 303-318.

［17］ 周晶， 趙曉哲， 許震， 等. 基于D-NSGA-Ⅲ算法的無人機群高維多目標任務分配方法［J］. 系統工程與電子技術， 2021， 43（5）： 1240-1247.

Zhou Jing， Zhao Xiaozhe， Xu Zhen， et al. Many-Objective Task Allocation Method Based on D-NSGA-Ⅲ Algorithm for Multi-UAVs［J］. Systems Engineering and Electronics， 2021， 43（5）： 1240-1247.（in Chinese）

［18］ Deb K， Jain H. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach， Part I： Solving Problems with Box Constraints［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（4）： 577-601.

Multi-UAV Cooperative Target Assignment Based on

Improved NSGA-III Algorithm

Wang Shuangyu1， Shen Qingmao2， Sun Mingyang3， Tang Shuang1， Zhen Ziyang1*

（1. College of Automation Engineering， Nanjing University of Aeronautics and Astronautics， Nanjing 211106， China；

2. Second Military Representative Office of Air Force Equipment Department in Beijing Area， Beijing 100000， China；

3. Institute of Intelligent Operation Research and Information Security of Aerospace

Science and Technology， Wuhan 430000， China）

Abstract： The weapon-target assignment problem is the key to the combat mission of the UAV against the enemy in the battlefield environment. The purpose is to find a reasonable weapon target assignment scheme based on the threat， value and damage probability of the target， so as to improve the combat efficiency. Aiming at the problem that the current multi-objective optimization algorithm has slow convergence speed and poor convergence stability when solving the static weapon-target assignment problem， and it is difficult to adapt to the high real-time performance of the current battlefield， an improved non-dominated sorting genetic algorithm based on reference points is proposed. The initial population is optimized by binary coding attack scheme， and adaptive mutation and crossover strategy as well as population optimization update strategy is introduced. Based on the threat matrix and advantage matrix obtained by evaluating the battlefield situation， the target attack scheme is generated after multiple iterations of the population. Finally， the Pareto solution set satisfying the constraint condition is calculated， and the relative optimal solution in the Pareto frontier is taken as the attack scheme of multi-UAV. Multiple experiments show that under good conditions， the improved algorithm reduces convergence time by 46.74%， reduces target threat value by 50.5%， reduces total flight range by 26.46%， and increases the number of killing targets by 11.76% compared with the original algorithm. It is proved that the algorithm is reasonable and efficient in solving the problem of target assignment of multi-UAV air-to-ground strike mission.

Key words： air-to-ground attack； multi-UAV； weapon target assignment； multi-objective optimization； NSGA-III； Pareto solution