基于禁忌搜索的作戰重心分析與選擇方法

張國輝，楊 征，杜正軍，周江平

（1.解放軍31004 部隊，北京 100094；2.解放軍31001 部隊，北京 100091）

0 引言

“重心”在物理學上是指物體重量的集中作用點，不論物體的位置如何改變，物體的各部分都圍繞著這一點保持平衡。重心概念由克勞塞維茨最早運用于軍事領域［1-2］。克勞塞維茨認為“重心是一切力量與運動的中心，是一切事物的依靠。在戰爭中，應集中所有的力量打擊這一點”［1，3］。

20 世紀90 年代美軍將“基于效果作戰（Effect Based Operation，EBO）”理論應用于戰爭實踐以來，其他國家也紛紛開展了支持EBO 的作戰計劃制定方法的研究［4］。最典型的作戰計劃擬制過程為：作戰重心確定→作戰重心發現→作戰行動方案制定→作戰行動方案分析與評估→作戰行動方案生成［5］，其中，重心發現是實現作戰計劃制定的關鍵［4，6］。由此可見，重心發現對于作戰過程具有極其重要的作用。

目前，關于作戰重心的定義還沒有統一的概念。以美軍為例，美軍并沒有一個統一的作戰重心的概念，各軍種有關重心的定義各不相同，而且有些定義內涵相差較大。如，美空軍認為重心是敵人的主要弱點，是敵方作戰體系內的一些最薄弱環節，對這些薄弱環節的打擊將最有可能取得決定性的結果［4，7］。美陸軍認為，重心是一切力量與運動的中心，是一切事物的依靠，是敵方或己方可以從中獲得行動自由、物質力量和作戰意愿的一種特點、能力或地方。美海軍則認為重心是敵方的力量源泉，是敵方的強點，在作戰過程中，應該間接而不是直接地攻擊敵重心。在對重心概念眾說紛紜的情況下，美軍聯合作戰條令認為，重心是敵人總體能力的某些方面，它們一旦被攻擊、壓制或摧毀，從理論上講將會導致敵人不可避免地陷入失敗的境地，或者迫使敵人放棄其企圖或改變其行為［3］。

近些年來，對作戰重心的研究成果很多，文獻［8］對美軍基于重心理論的作戰籌劃方法進行了研究，分析了其理論來源、基本要素和推理過程。文獻［9］指出，在高科技條件下作戰重心已經發生了深刻的變化，呈現出重心目標配置分散化、重心目標群體系統化和重心目標性質多樣化等特點。文獻［4］研究了基于貝葉斯網絡的火力打擊重心分析建模問題，提出了相應的建模方法和流程。鑒于貝葉斯網絡在解決復雜系統決策問題方面的優勢，李正浩等［10］研究了一種基于貝葉斯網絡推理的作戰重心評估模型，并定量評估了各個作戰環節的重要程度。文獻［11］提出了基于作戰重心理論的體系構建和評估方法，并研究了基于重心分析的聯合作戰計劃制定過程。文獻［12］研究了網點空間作戰中的打擊重心分析過程，給出了打擊重心分析的基本原則。

綜合對相關文獻的分析，本文認為：作戰重心，是軍事網絡中保障作戰單元發揮其作戰能力的關鍵力量，是作戰活動中各種力量的合力點，是達成預定作戰目的關鍵所在，是整個作戰行動應解決的中心問題，也是軍事網絡中重要的組成部分，它是一個相對的概念，隨著作戰目的、打擊手段、戰場資源等因素的不同，作戰重心也將隨之改變。同時，還可以得出以下認識：

1）重心是敵方作戰系統的重點，確定敵方作戰重心是實施作戰指揮的關鍵。重心位于戰略和聯合戰役籌劃的頂層，是籌劃的基礎。通過打擊其作戰重心，可以有效動搖敵方的作戰決心、延緩敵方的作戰行動［4］。

2）在信息化作戰條件下，作戰目標關聯密切、種類繁多，如何在復雜戰場環境下快速找到關鍵目標，是指揮員關心的重要問題［13］。如有可能應盡可能對敵重心實施直接進攻，但在作戰過程中，敵重心可能不明顯或不易判斷，敵方也會竭力保護自己的重心，這使得直接攻擊重心變得非常困難和難以實現。

3）作戰重心是敵方保護的重中之重，很難直接進行火力打擊［4］。因此，火力打擊作戰重心應當是從基于效果的角度對影響重心的要素進行分析決策，從而得到一系列能夠使打擊效果最大化的打擊目標［4］。

4）作戰重心的分析選擇依賴于作戰網絡模型的構建，而作戰網絡模型根據作戰場景和研究領域的不同，將呈現出不同的模型形式［14-16］。文獻［17］在研究信息化條件下聯合作戰的作戰模型時，將所有作戰單元抽象為決策器（D）、傳感器（S）和影響器（I）3 類節點。陳士濤等［18］則將作戰網絡抽象為指揮類（D）、偵察類（U）、打擊類（A）和目標類（T）4 類節點。

1 問題描述

對于一般的作戰網絡結構，如果不考慮目標的打擊代價，則作戰網絡的重心可以理解為是作戰網絡中網絡影響力最大的節點或者邊，若將這些節點和邊刪除后，作戰網絡的最大連通度變化量最大，即對作戰網絡的結構最具破壞性。但是實際上，戰爭不可能沒有打擊代價（如彈藥消耗、人員傷亡、經費開支等），而且打擊代價對于戰爭勝負往往具有決定性作用。因此，在進行作戰重心分析時不能不考慮打擊代價。當考慮作戰網絡的打擊代價，并以總的打擊代價（包括彈藥消耗、經費開支）最小為重心選擇的依據時，問題將變得十分復雜，必須構建能反映打擊效果的作戰模型，采用科學有效的方法予以分析求解。

為此，本文構建了考慮打擊代價的目標重心分析與選擇模型，且設計了相應的求解算法，并通過實驗案例對模型和算法有效性及可行性進行了驗證。

2 模型構建

2.1 符號說明

2.1.1 集合

D：表示作戰任務允許消耗彈藥的上限，即作戰過程中的彈藥消耗不允許超過D 值；

E：表示參與作戰的人員數量上限，即作戰過程中的人員傷亡必須小于參戰人數；

F：表示作戰任務允許消耗的經費上限，即作戰過程中的所有經費開支必須不超過F 值；

2.1.3 決策變量

xm：為0-1 變量，值為1 時，表示作戰網絡中第m 個節點（火力單元、情報單元或指控單元）被摧毀；否則值為0；

ykl：為0-1 變量，值為1 時，表示作戰網絡中第k 個節點和第l 個節點之間連邊（火力單元與情報單元之間，指控單元與火力單元之間，或指控單元與情報單元之間的鏈路）被摧毀；否則值為0。

2.2 數學模型

目標函數式（1）以作戰網絡節點的重要度和節點間連邊的重要度之和最大化為優化目標，其中，函數式第1 項表示作戰網絡節點的重要度，第2 項表示節點間鏈路的重要度。目標函數式（2）以作戰網絡的節點和邊的打擊代價之和最小為優化目標，其中，函數式第1 項表示摧毀某作戰單元的打擊代價和毀傷概率，第2 項表示摧毀節點間通信鏈路時的打擊代價和毀傷概率。

約束條件式（3）表示作戰網絡節點和節點之間連邊的毀傷概率在［0，1］之間取值。約束條件式（4）表示彈藥消耗數、人員傷亡數和經費開支等因素，共同構成了作戰打擊代價的考慮因素，幾個因素的重要程度依據戰爭任務、專家評估及指揮決策的變化而定。式（5）～式（7）分別表示彈藥消耗、人員傷亡和經費開支的數量約束。另外，約束條件式（8）和式（9）分別表示xj和ykl是0-1 變量。

3 禁忌搜索算法設計

作戰網絡重心選擇優化模型是整數規劃問題，問題規模較小時可以用CPLEX 進行求解，但當問題的規模增大時，若繼續采用CPLEX 進行求解，計算時間將迅速增長。而且上述優化問題屬于多目標優化問題，求解多目標優化問題通常可以采用NSGA-II 算法。本文借鑒標準NSGA-II 的基本思想，采用禁忌搜索算法（Tabu Search，TS），針對作戰網絡重心選擇優化模型的特點進行了算法設計。

禁忌搜索算法是一種啟發式算法，它是一種全局逐步尋優的算法，是對局部鄰域搜索的擴展。禁忌搜索算法通過設計靈活的數據結構和對應的禁忌準則來有效避免重復搜索，并通過特赦準則來赦免某些被列入禁忌表的良好狀態［20］，且當前解還可以通過一定方式接受劣解［21］，從而保證搜索的多樣性，力求實現全局最優化［19］。禁忌搜索算法在解決全局優化問題和組合優化問題中展現了良好性能，已經被成功運用于求解車間調度問題、旅行商問題等［22-23］。本文結合作戰網絡的特點，采用禁忌搜索算法的良好特性［23］，設計一種解決作戰網絡重心分析問題的改進的禁忌搜索算法。

通常情況下，要設計禁忌搜索算法，需要確定以下環節：1）初始可行解及評價函數；2）鄰域結構和禁忌對象；3）候選解選擇［24］；4）禁忌表及其長度；5）特赦規則［24］；6）集中性和多樣性搜索策略；7）終止準則［25］。

3.1 初始解的構造

較好的初始可行解可提高算法在解空間搜素的效率［2］。在構造初始解時，先通過指標ω 對所有鏈路進行排序，選擇ω 值最大的n 條鏈路作為初始作戰重心，然后根據選定的n 個初始作戰重心作為初始解。

在構建指標ω 時，主要出于以下考慮，雖然作戰重心的選取與重要度、打擊代價和毀傷概率都有關系，但在這幾個因素中，僅有重要度因素與作戰網絡的網絡結構密切相關，而對作戰網絡結構的分析還原是一個動態的過程，作戰網絡結構的實時變化必將引起重要度的改變。因此，用重要度作為初始解構造指標可以較好地體現鏈路重要度變化特點。

3.2 評價函數

改進的禁忌搜索算法的評價函數用于對搜索狀態的評價，結合禁忌規則和特赦規則來選取新的當前解。為更好地描述評價函數的基本設計思想，引入下列數學符號：

Hk：表示第1 個優化目標函數的第k 次迭代所得解；

rfirst：表示當前解Hk中重要度最高的那個候選作戰重心；

rsecond：表示當前解Hk中重要度次高的那個候選作戰重心；

ΔZk+1：某個候選作戰重心的狀態發生變化時，第1 個目標函數值的變化量。

改進的禁忌搜索算法評價函數可使用如下規則［25］：

1）對于Add 過程，評價函數為

Add 過程具有如下性質：

性質1 如果在k+1 次迭代時加入一個候選作戰重心i，則目標函數變化量為［25］

證明：當向解Hk中加入一個候選作戰重心i時，目標函數變化量為

證畢。

2）對于Drop 過程，評價函數為過程，評價函數為

Drop 過程具有如下性質：

性質2 如果在k+1 次迭代時刪除一個候選作戰重心i 時，則目標函數變化量為［25］

證明：當從解Hk中刪除一個點i 時，目標函數變化量為

證畢。

3.3 鄰域結構及其候選解

鄰域結構是指從一個給定解跳轉到另一個解的規則［22］。鄰域解是由給定解經過一次跳轉所得到的，局部搜索過程中如何從一個解跳轉到另一個解是由其鄰域結構決定的，因此，鄰域結構的構造方式直接影響到局部搜索算法的效率［22］。結合作戰網絡重心分析問題的特點，本文的鄰域移動是針對候選作戰重心進行的。

3.4 禁忌長度及禁忌對象

3.5 特赦規則

本文采用的特赦規則是：1）假如某個禁忌的候選解優于當前最好解，則將此候選解解禁，并將其選為當前最好解［27］。2）假如禁忌候選解和非禁忌候選解都不優于當前最好解，則將最好的非禁忌解選為當前解。3）假如所有候選解都被禁忌，而且不存在優于當前最好解的候選解，則對最好的候選解進行解禁操作，并將其作為當前解，以便繼續搜索［21］。

3.6 停止規則

一般而言，禁忌搜索算法的常用停止規則有：1）迭代次數達到預設的最大迭代次數［19］。2）目標函數值持續未得到改善。3）運算時間達到預設的運行時間［28］。4）目標函數值達到預設值等［19，21］。本文將停止規則設定為運算達到預設的最大迭代次數［19，27］。

3.7 算法流程

至此，本文采用禁忌搜索算法的基本思想進行作戰網路作戰重心的重要度搜索，能有效地對具有大規模作戰單元的作戰網絡進行分析。但是，本文所構建的考慮打擊代價的作戰重心分析模型包含兩個優化目標：一是作戰單元或鏈路的重要度最大；二是打擊各作戰單元和鏈路的打擊代價最小。剛通過禁忌搜索算法進行的求解，僅解決了依靠重要度得到作戰網絡重心的優化目標，接下來還需要考慮打擊代價對于作戰網絡重心的影響。為此，本文借鑒標準的（Non-dominated Sorting Genetic Algorithm II，NSGA-II）算法思想，并結合考慮打擊代價的作戰重心分析問題的特點，進行了調整及改進，具體計算流程如下，算法流程圖如圖1 所示。

圖1 算法流程圖

Step 1 應用上述初始解的構造方法產生初始解，并設為當前解和當前最優解。

Step 2 依次將非候選作戰網絡重心與候選作戰網絡重心集合中的可行解作單一交換，產生候選解集。

Step 3 從候選解集中選擇最好的解，快速非支配排序，若此解優于當前最好解，轉至Step 6；否則轉至Step 4。

Step 4 判斷解是否為屬于禁忌名單，若屬于則轉至Step 5；否則轉至Step 6。

Step 5 假如所有的候選解都屬于禁忌名單，則把最好的候選解選作當前解，轉至Step 6；否則將非禁忌的最好候選解選作當前解，轉至Step 7［29］。

Step 6 對當前的解進行更新，并保留當前最好解。

Step 7 對禁忌名單進行更新。

Step 8 判斷是否達到算法停止條件，若是則輸出結果，計算結束；否則轉至Step 2。

4 實驗驗證

4.1 實驗設置

為檢驗模型及算法的有效性及合理性，設定如下背景：某場戰爭中，通過偵察等技術手段，還原和重構了敵方的作戰網絡，該作戰網絡包含有60 個作戰單元，大致區分為3 種類型：指控節點C2，火力節點F，情報節點I，各節點間的連接關系如圖2所示。

圖2 60 個作戰單元的作戰網絡示意圖

每個作戰單元的重要度、打擊代價和毀傷概率采用隨機生成的方式產生，列于表1 中。作戰網絡圖中各節點之間的連邊表示各作戰單元之間由信息交互關系。不失一般性，設“打擊代價”占節點（連邊）重心分析中的權重值α=0.5，設“毀傷概率”占節點（連邊）重心分析中的權重值β=0.5。

表1 60 個作戰單元的特征屬性值

利用前面給出的模型及求解方法，可以計算出該優化問題的最優解，即最優重心節點為第44 號節點，最優的作戰重心鏈路為：1→32→9→4→36→20→13→11→14→15→56→17→39→18→6→44→0，且該最優解的目標值1 為0.889，目標值2 為2 097，結果如表2 所示。

表2 最優作戰重心選擇方案及目標值

4.2 實驗分析

為了進一步分析“打擊代價”因素對于作戰網絡重心選擇的影響，按如下實驗步驟進行分析：

Step 1 在求解過程中，先計算考慮打擊代價時的可行解，并按可行解重要度降序排序，選取前30組可行解，將其定義為變量Opt01；

Step 2 在求解過程中，不考慮打擊代價，僅依據節點（連邊）重要度進行重心分析，按照重要度大小將可行解進行降序排序，選取前30 組可行解，將其定義為變量Opt02；

Step 3 運用IBM SPSS Statistics 19.0 對上述步驟所得樣本及變量進行統計分析。對變量Opt01 與變量Opt02 進行假設檢驗，用于檢驗打擊代價因素加入前后，兩組可行解之間的差異是否具有統計學意義［30］。本文選擇的假設檢驗的方法是成對樣本t 檢驗，且檢驗水平為0.05，檢驗結果如表3、表4 及圖3 所示。

表3 兩組可行解描述統計結果

如表3 所示，對于第1 個優化目標，當不考慮打擊代價時，30 個樣本的重要度平均值為0.60，而考慮打擊代價時，樣本的重要度平均值為0.48。顯然，不考慮打擊代價因素時，選出的作戰重心的重要度相對較高。對于第2 個優化目標，當不考慮打擊代價因素時，30 個樣本的實際打擊代價平均值為1 604，而考慮打擊代價因素時，樣本的實際打擊代價平均值為1 029。顯然，考慮打擊代價因素時，選出的作戰重心的實際打擊代價將大大降低。素時得出的實際打擊代價值遠低于不考慮打擊代價時的分析結果，可見，考慮打擊代價因素對于降低作戰單元實際打擊代價具有顯著意義。

圖3 考慮打擊代價因素前后兩組可行解的描述統計分析

表4 兩組可行解的獨立樣本t 檢驗結果

表4 則進一步反映了打擊代價因素加入前后，兩組可行解樣本之間的差異程度。如表可知，兩組樣本的重要度成對t 檢驗統計量為-2.196，打擊代價的成對t 檢驗統計量為-14.438，所對應的差異顯著性檢驗值分別為P=0.032，P=0.000 且均滿足P＜α=0.05，因此，認為兩組樣本的重要度之間以及打擊代價之間具有統計學意義。其中，打擊代價的成對t檢驗顯著性檢驗值為0.000，遠小于0.05，從而進一步印證了考慮打擊代價因素對于降低作戰單元實際打擊代價具有顯著意義。

5 結論

本文重點研究了考慮打擊代價的目標重心分析與選擇方法。首先給出了作戰重心的概念，然后建立了考慮打擊代價的作戰重心分析與選擇模型，并設計了模型的求解方法，最后通過一個隨機生成的作戰網絡對模型和方法進行驗證和分析。實驗結果顯示，本文設計的求解方法可以在短時間內給出很好的近似最優解。