基于集成改進蟻群算法的作戰(zhàn)環(huán)推薦方法

摘要： 作戰(zhàn)環(huán)推薦是依靠優(yōu)化算法從作戰(zhàn)網(wǎng)絡中為指揮員推薦最優(yōu)的作戰(zhàn)環(huán)，以對目標形成高質(zhì)量打擊。未來作戰(zhàn)中的作戰(zhàn)環(huán)推薦面臨體系規(guī)模大、決策節(jié)奏快的特點。對此，提出了一種集成改進的蟻群算法，能夠?qū)崿F(xiàn)高效、高質(zhì)的作戰(zhàn)環(huán)推薦優(yōu)化求解。首先，將作戰(zhàn)環(huán)推薦問題轉(zhuǎn)換為一種基于多倉庫路徑規(guī)劃的數(shù)學模型。然后，針對原始蟻群算法前期收斂速度慢、算法參數(shù)對結(jié)果影響大和容易陷入局部最優(yōu)的問題分別提出了3種改進策略：基于邊權(quán)重信息的信息素初始化、基于差分進化的蟻群算法參數(shù)自適應優(yōu)化和基于遺傳算子的全局搜索能力提升，并進行了集成改進。最后，在案例分析中對集成改進蟻群算法進行了分析和對比，驗證了所提算法在不需要大幅提高耗時的情況下，優(yōu)化結(jié)果要優(yōu)于未集成改進的蟻群算法，且相比于原始蟻群算法提升效果顯著。

關(guān)鍵詞： 作戰(zhàn)環(huán)推薦; 多倉庫路徑規(guī)劃; 智能優(yōu)化; 蟻群算法; 集成改進

中圖分類號： N 936

文獻標志碼： A

DOI：10.12305/j.issn.1001-506X.2024.06.18

Operation loop recommendation method based on integrated improved ant colony algorithm

LI Jie^*， TAN Yuejin

（College of Systems Engineering， National University of Defense Technology， Changsha 410073， China）

Abstract： Operation loop recommendation （OLR） is based on the optimization algorithm to recommend the optimal operation loop from the combat network for the commander，in order to strike the target with high quality. The OLR in the future operations is faced with the characteristics of large scale and fast decision-making pace. In this regard， an integrated improved ant colony （AC） algorithm is proposed， which can realize efficient and high-quality optimization solution on OLR. Firstly， the OLR problem is transformed into a mathematical model based on multi-warehouse path planning. Secondly， to solve the problems of the original AC algorithm， such as slow convergence speed in the early stage， the algorithm parameters have great influence on the results， and easy to fall into the local optimization， three improvement strategies are proposed and integrated： pheromone initialization based on edge weight information， adaptive optimization of AC algorithm parameters based on differential evolution， and improvement of global search ability based on genetic operator. Finally， the case study analyzes and compares the integrated improved AC algorithm， verifies that the optimization result of the proposed algorithm is better than that of the unintegrated improved AC algorithm without significantly increasement of the time consumption， and the effect is significantly improved compared with the original AC algorithm.

Keywords： operation loop recommendation （OLR）; multi-warehouse path planning; intelligent optimization; ant colony （AC） algorithm; integrated improvement

0 引 言

人工智能與新一代信息技術(shù)等一系列顛覆性技術(shù)的“爆發(fā)式”涌現(xiàn)，導致信息化戰(zhàn)爭加速演變，智能化戰(zhàn)爭初見端倪^［1］。智能化戰(zhàn)爭是在信息化作戰(zhàn)平臺的基礎(chǔ)上，以聯(lián)合作戰(zhàn)為指導思想，通過人工智能的輔助決策手段和機器自主控制技術(shù)，進行高度復雜、快節(jié)奏且通常是大規(guī)模體系對抗的一種以決策為中心的戰(zhàn)爭形式，其核心目的就是達成快速精準的決策^［2］。作戰(zhàn)環(huán)是一種公認成熟有效的描述聯(lián)合作戰(zhàn)過程的模型^［3］。如何從一個復雜的作戰(zhàn)體系中快速精準地推薦最有效的作戰(zhàn)環(huán)將是未來戰(zhàn)爭中的關(guān)鍵賦能器，也是本文研究的重點。

未來體系對抗將呈現(xiàn)出規(guī)模大、決策節(jié)奏快的基本特點，傳統(tǒng)的憑借人類指揮員進行決策的模式無法適應未來的作戰(zhàn)規(guī)模與強度，而必須依靠人機協(xié)同的方式^［4］。最近試驗的“適應性跨域殺傷網(wǎng)”項目正是一種基于人機協(xié)同的指控推薦系統(tǒng)，其目的是面對空中威脅，為指揮員推薦用于形成殺傷鏈的裝備和最佳指揮與控制戰(zhàn)術(shù)^［5］。在人機協(xié)同的作戰(zhàn)環(huán)推薦模式下，計算機主要用于運行作戰(zhàn)環(huán)推薦算法，為人類指揮員快速推薦備選的作戰(zhàn)環(huán)方案，而人類指揮員主要負責從備選方案中，根據(jù)經(jīng)驗選擇最佳方案^［6］。因此，有必要研究一種大規(guī)模情況下可求解、求解效率高和精度高的作戰(zhàn)環(huán)推薦算法。

考慮到作戰(zhàn)環(huán)推薦問題的大規(guī)模與非線性特點，傳統(tǒng)的數(shù)學規(guī)劃方法難以適用，而智能優(yōu)化算法的適用性強，且可以在有限時間內(nèi)近似求解大規(guī)模優(yōu)化問題。智能優(yōu)化算法有多種分類方式，一般可分為4大類：進化類（遺傳算法、差分進化算法、量子遺傳算法等）、群體智能類（蟻群算法、魚群算法、狼群算法等）、物理法則類（模擬退火算法、引力搜索算法等）和其他類（禁忌搜索算法、和聲搜索算法、免疫搜索算法等）。其中，蟻群算法利用螞蟻尋路原理進行優(yōu)化，在處理網(wǎng)絡路徑尋優(yōu)類問題中的表現(xiàn)尤為出色^［7-11］。本文研究的作戰(zhàn)環(huán)推薦問題正是從作戰(zhàn)網(wǎng)絡中尋找一條最優(yōu)的作戰(zhàn)環(huán)閉環(huán)路徑，因此正適合用蟻群算法進行求解。

根據(jù)文獻［12］，傳統(tǒng)蟻群算法在圖與網(wǎng)絡優(yōu)化問題上具有較快的后期收斂速度和較好的優(yōu)化效果，但也存在算法前期收斂速度慢、算法參數(shù)對結(jié)果影響大、容易陷入局部最優(yōu)的問題，因此很多學者對蟻群算法進行了改進研究。

針對蟻群算法前期收斂速度慢和容易陷入局部最優(yōu)的缺點，最早的改進是由Dorigo等^［13］提出的帶精英策略的螞蟻系統(tǒng)（ant system with elitist strategy， Aselite）。EAS通過提高精英螞蟻的信息素保留量，有效加快了算法的收斂速度，但也更容易陷入局部最優(yōu)。Bullnheimer等^［14］提出了排序蟻群系統(tǒng)，根據(jù)不同螞蟻的路徑長度排序設(shè)置不同信息素揮發(fā)系數(shù)。Stiitzl等^［15］提出了最大最小蟻群系統(tǒng)（max-min ant colony system， MMAS），只針對最優(yōu)螞蟻的路徑進行信息素更新，提升了收斂速度，并設(shè)置了信息素的上下限，避免陷入局部最優(yōu)。Dorigo等^［16］提出了蟻群系統(tǒng)，引入負反饋機制，螞蟻經(jīng)過路徑上的信息素會被消除一部分，以實現(xiàn)信息素的局部調(diào)整，從而減小已選擇過的路徑再次被選擇的概率。在上述4個經(jīng)典改進算法中，MMAS的性能改進最為有效，也被廣泛應用到后續(xù)的蟻群算法研究中。

近年來的蟻群算法改進依舊針對上述提到的原有算法的缺點出發(fā)，改進思路可分為以下幾個方面：① 針對全局搜索能力弱的缺點，文獻［17］等將遺傳算法與蟻群算法融合，提升蟻群算法的前期收斂速度。文獻［18-20］將A*算法與混合蟻群算法結(jié)合，利用A*算法的全局收斂性改善了蟻群算法易陷入局部最優(yōu)解的缺點。文獻［21］采用動態(tài)參數(shù)控制的偽隨機轉(zhuǎn)移策略，提出優(yōu)質(zhì)螞蟻信息素更新原則，自適應調(diào)整揮發(fā)系數(shù)，提高算法全局性。文獻［22］對蟻群進行角色劃分，不同角色的蟻群執(zhí)行各自不同的搜索策略，增強了蟻群的搜索能力，較大幅度地提高了求解質(zhì)量。文獻［23-25］研究了多蟻群協(xié)同進化算法，將復雜優(yōu)化任務分解為多個子問題的情況，提升算法求解效率。上述方法都能夠在一定程度上增強蟻群算法的性能，值得借鑒。② 針對蟻群算法的參數(shù)較多，從而導致不恰當?shù)膮?shù)選擇會降低算法尋優(yōu)能力的問題，文獻［26］采用自適應狀態(tài)轉(zhuǎn)移策略和自適應信息素更新策略調(diào)整信息素強度與啟發(fā)信息在算法迭代過程中的相對重要性。文獻［27］按照設(shè)定的參數(shù)變化規(guī)律自適應調(diào)整信息素揮發(fā)系數(shù)來提高算法的全局尋優(yōu)能力。文獻［28］動態(tài)調(diào)整信息素啟發(fā)因子與期望啟發(fā)因子，有效減少了螞蟻前期到達最優(yōu)路徑的迭代次數(shù)。文獻［29］提出了一種多信息素動態(tài)更新蟻群算法，通過改變蟻群算法中的狀態(tài)轉(zhuǎn)移概率以及信息素更新規(guī)則等提升算法的全局搜索能力。

上述研究通常是根據(jù)蟻群算法的優(yōu)化特征進行參數(shù)優(yōu)化，根據(jù)算法優(yōu)化情況自適應調(diào)整參數(shù)，或者根據(jù)迭代次數(shù)設(shè)計動態(tài)參數(shù)調(diào)整策略。這些方法將蟻群算法參數(shù)由常數(shù)變?yōu)閯討B(tài)調(diào)整模式，以較小的計算成本提高了算法的全局搜索能力，并降低了算法對參數(shù)的敏感性，但動態(tài)調(diào)整策略均需人為設(shè)定調(diào)整規(guī)則，無法保證參數(shù)的最優(yōu)性與合理性，同時也缺乏一定的通用性。

當前針對蟻群算法的改進大部分是針對單個缺陷進行的，少有將多種改進策略融合起來的研究。本文提出了一種集成改進蟻群算法的思路，分別針對原始蟻群算法前期收斂慢、容易陷入局部最優(yōu)、參數(shù)影響大的缺陷，提出了3種改進策略，并將這些策略融合，形成集成改進蟻群算法，應用到作戰(zhàn)環(huán)推薦問題中，形成作戰(zhàn)環(huán)推薦方法。

1 基于多倉庫路徑規(guī)劃的作戰(zhàn)環(huán)推薦問題建模

1.1 作戰(zhàn)環(huán)推薦問題描述

2012年，國內(nèi)學者在OODA（observation，orientation，decision，action）環(huán)的基礎(chǔ)上，基于系統(tǒng)工程的思想對作戰(zhàn)過程進行提煉，提出了作戰(zhàn)環(huán)的概念，并給出了明確定義：為了完成特定的作戰(zhàn)任務，武器裝備體系中的偵察類、決策類、影響類等武器裝備實體與藍方目標實體構(gòu)成的閉合回路^［30］。交戰(zhàn)雙方各自構(gòu)建紅方的作戰(zhàn)環(huán)，把藍方節(jié)點當成紅方作戰(zhàn)環(huán)中的目標。作戰(zhàn)環(huán)的示意圖如圖1所示。

圖1中涉及4類實體的具體表述如下。

目標類實體：作戰(zhàn)任務中需要被打擊、摧毀、干擾或者攔截的目標，可以是藍方的武器裝備、軍事設(shè)施或重要民用設(shè)施。

偵察類實體：紅方裝備中具有偵察、預警或者監(jiān)視功能、可以感知戰(zhàn)場信息的裝備或設(shè)施，如預警機、偵察機、相控陣雷達等。

決策類實體：紅方裝備中的具備信息處理能力的決策制定單元，如地面指揮所、預警機、臨時授命的指揮中心等。

打擊類實體：對目標類節(jié)點直接產(chǎn)生影響的紅方裝備實體，影響類節(jié)點可以是打擊類、干擾類以及任何能夠影響藍方目標功能的武器裝備。

圖1中涉及4類邊的具體表述如下。

偵察邊：藍方目標→偵察實體，紅方偵察類實體通過主動方式（發(fā)射雷達波）或被動方式（探測紅外信號）獲取藍方目標的信號。

通信邊：偵察實體→決策實體，紅方偵察類實體將探測到的目標信號傳輸給決策類實體，后者通過數(shù)據(jù)處理，將信號轉(zhuǎn)化為有效信息。

指控邊：決策實體→打擊實體，紅方?jīng)Q策類實體對目標的有效信息進行分析研判，制訂作戰(zhàn)方案，將作戰(zhàn)命令下發(fā)至相應影響類實體。

打擊邊：打擊實體→藍方目標，紅方影響類實體接受作戰(zhàn)命令后，根據(jù)命令指示，通過自身特有能力對藍方目標施加影響。

將作戰(zhàn)體系視為一個作戰(zhàn)網(wǎng)絡，用G=（V，E）表示，V是作戰(zhàn)網(wǎng)絡中所有裝備實體的節(jié)點， V^T是所有目標（藍方裝備）的節(jié)點集合，V^A是所有紅方裝備的節(jié)點集合，E是作戰(zhàn)網(wǎng)絡中所有連邊的權(quán)重，表示連邊的質(zhì)量。E由4個集合構(gòu)成： E={E¹，E²，E³，E⁴}，分別代表裝備之間的偵察、通信、指控和打擊邊的權(quán)重。作戰(zhàn)環(huán)推薦問題就是從作戰(zhàn)網(wǎng)絡的作戰(zhàn)環(huán)候選集中選擇最優(yōu)的作戰(zhàn)環(huán)，其本質(zhì)是從一個網(wǎng)絡中挑選一個子網(wǎng)絡。因此，作戰(zhàn)環(huán)推薦問題可以被視為一種組合優(yōu)化問題。

上述作戰(zhàn)環(huán)相關(guān)定義與描述是對實際作戰(zhàn)過程的一種抽象，能夠基本覆蓋交戰(zhàn)過程中的作戰(zhàn)循環(huán)過程，但也存在一些特例，如察打一體裝備發(fā)現(xiàn)目標即打擊。因此，本文研究對象限定于符合圖1所示過程的作戰(zhàn)環(huán)路。

1.2 作戰(zhàn)環(huán)推薦問題建模

首先，簡要介紹物流配送問題，物流配送是多個車輛由倉庫（配送中心）出發(fā)，為客戶配送貨物后返回倉庫的過程。對物流配送過程的優(yōu)化稱為物流車輛路徑規(guī)劃問題，即尋找滿足條件的最短配送路線，也稱為倉庫路徑規(guī)劃問題。

作戰(zhàn)環(huán)推薦是將藍方體系的裝備視為目標，針對各個目標推薦最優(yōu)作戰(zhàn)環(huán)的一種規(guī)劃問題，每個作戰(zhàn)環(huán)可以視為一種由目標T出發(fā)、又返回目標T的環(huán)路。作戰(zhàn)環(huán)推薦問題類似于一種特殊的物流配送問題，每個藍方目標相當于一個倉庫，紅方體系的裝備相當于客戶，紅方閉環(huán)過程相當于車輛配送過程，形成的作戰(zhàn)環(huán)相當于車輛配送路線。針對每個目標（倉庫），每條作戰(zhàn)環(huán)（配送路線）需要經(jīng)過探測、指控、打擊裝備（客戶）后，返回目標（倉庫），才完成一次閉環(huán)（配送）過程，如圖2所示。

更進一步，當作戰(zhàn)環(huán)推薦考慮時間約束時，可以將問題轉(zhuǎn)化為帶時間窗的多倉庫配送問題，針對每個倉庫的物資配送必須在規(guī)定時間內(nèi)完成。參照倉庫配送問題的數(shù)學模型，構(gòu)建基于作戰(zhàn)環(huán)推薦問題轉(zhuǎn)換的帶時間窗約束的多倉庫配送問題的數(shù)學規(guī)劃模型：

式中：藍方體系共包含m個目標（用k表示），x^k_ij為變量，表示針對目標k的閉環(huán)過程是否包含從裝備i到裝備j的鏈;q_ij表示裝備i與裝備j之間的連邊質(zhì)量;q^*_ij表示裝備i與裝備j之間連邊的理想值（一般取最大值1）;v_k為目標k的價值;time_j為閉環(huán)時間;time_k為目標的剩余有效打擊時間。

式（1）表示目標函數(shù)，為選中的裝備之間連邊的質(zhì)量距離理想點的歐氏距離;式（2）～式（4）約束每次閉環(huán)從目標k出發(fā)并最終返回目標k;式（5）約束閉環(huán)時間time_j小于目標的剩余有效打擊時間time_k;式（6）表示變量x^k_ij的取值范圍（取1表示針對目標k的閉環(huán)包含裝備i到裝備j，取0則表示相反）。

2 蟻群算法改進策略

原始蟻群算法存在前期收斂速度慢、受參數(shù)影響大、容易陷入局部最優(yōu)等問題，具體原因在于：① 信息素初始值設(shè)置為同一常數(shù)導致前期收斂速度較慢;② 算法的參數(shù)較多，參數(shù)的不同取值對算法效果有一定影響，不恰當?shù)膮?shù)選擇會降低算法的尋優(yōu)能力;③ 信息素的正反饋機制導致所有螞蟻的價值取向完全一致，從而導致蟻群的種群多樣性較差，容易陷入局部最優(yōu)。針對上述問題，借鑒現(xiàn)有研究針對蟻群算法的改進思想，結(jié)合作戰(zhàn)環(huán)推薦問題的特征，對傳統(tǒng)蟻群算法進行改進。

2.1 改進1——基于邊權(quán)重的信息素初始化

首先，針對相同信息素初始值導致算法前期收斂速度慢的問題，當前的改進策略主要有兩種：① 根據(jù)任務和問題特征進行信息素初始化;② 根據(jù)其他優(yōu)化算法得到的初始解進行信息素初始化。本文采用第①種方式，即根據(jù)殺傷網(wǎng)的邊權(quán)重確定信息素的初始值。

作戰(zhàn)環(huán)推薦問題的本質(zhì)就是要從作戰(zhàn)網(wǎng)絡G=（V，E）中推薦一條效能最優(yōu)的作戰(zhàn)環(huán)。直觀上看，連邊的權(quán)重越大，其所在的作戰(zhàn)環(huán)的效能就越有可能取得一個較大值。因此，可以根據(jù)E中的權(quán)重信息設(shè)計信息素的初始值。另一方面，為了增加信息素初始值分布的廣泛性，降低信息素矩陣中元素之間的關(guān)聯(lián)性，進而增加蟻群在優(yōu)化初期的搜尋范圍，可以在上述初始值的基礎(chǔ)上引入一定的擾動值，即

τ⁰_ij=e⁰_ij+λ_ij（7）

式中：τ⁰_ij為裝備i與裝備j之間的初始信息素;e⁰_ij為裝備i與裝備j之間的連邊權(quán)重;λ_ij為在一定取值區(qū)間內(nèi)的隨機數(shù)，通常遠小于τ_ij。

2.2 改進2——基于差分進化的蟻群算法參數(shù)自適應優(yōu)化

針對原始蟻群算法受參數(shù)影響較大的缺陷，以及現(xiàn)有研究改進的參數(shù)自適應調(diào)整多需要人工設(shè)計參數(shù)變化規(guī)則的不足，本文提出一種基于差分進化的參數(shù)自適應優(yōu)化策略，在蟻群進行尋優(yōu)的過程中嵌入?yún)?shù)優(yōu)化片段，實現(xiàn)蟻群算法參數(shù)的自適應優(yōu)化。該方法不必通過人工設(shè)定任何參數(shù)調(diào)整策略，而是利用蟻群尋優(yōu)信息自適應調(diào)整參數(shù)，因此是通用的，而且是“端到端”的，即無需考慮特定問題背景。

具體改進思想如下：將每個螞蟻個體同時也視為一個參數(shù)個體，在尋找最優(yōu)路徑的同時也在對參數(shù)進行優(yōu)化，每個回合都令找到本次迭代最優(yōu)解的螞蟻個體所采用的參數(shù)作為參數(shù)最優(yōu)解參與下個回合的差分進化，生成新的參數(shù)集合，并賦予每個螞蟻個體，螞蟻個體基于新的參數(shù)進行尋優(yōu)。

具體操作步驟如下。

步驟 1 針對蟻群算法中的所有參數(shù)，定義參數(shù)方案的染色體形式，由于參數(shù)是連續(xù)實數(shù)，因此采用實數(shù)編碼構(gòu)建參數(shù)方案的染色體，即（x₁，x₁，…x_n），x_i∈［x^-_i，x⁺_i］，i=1，2，…，n，其中x^-_i和x⁺_i分別表示參數(shù)x_i的取值范圍的上下限。

步驟 2 通過初始化操作獲取種群規(guī)模等于螞蟻數(shù)量N的初始參數(shù)種群P₁，可采用在取值范圍內(nèi)隨機取值的方式，也可以根據(jù)歷史經(jīng)驗進行人為設(shè)置。

步驟 3 用差分進化算子對初始種群P₁進行遺傳操作，得到規(guī)模大小為N的新種群P₂。

步驟 3.1 基于差分進化的變異操作

為豐富種群多樣性，對第g代的父代種群P₁（g）進行變異操作以得到新種群。本文選擇常用的一種差分變異算子，如下所示：

r′=r_gbest+rand·（r₁-r₂）（8）

式中：r₁和r₂是當前種群中隨機選擇的2個相異個體;r_gbest為目前的全局最優(yōu)解;r′為變異后新的臨時個體。

步驟 3.2 交叉操作

變異操作之后需要進行交叉操作，對父代染色體信息進行融合，增加種群多樣性。針對變異后的種群中的個體r′_i，其對應的當前父代種群的個體為r_i，交叉方式如下：

式中：r″_i是交叉后的新個體;C是交叉概率向量，由0或1組成;CR為交叉概率，意味著r_i中每一位編碼有CR的概率與r′_i的對應位置編碼進行交叉（被后者替換）。所有個體完成交叉操作后得到新種群P₃（g+1）。

步驟 3.3 解修正

經(jīng)過交叉變異后的種群個體可能有違反解約束的情況，檢查P₃（g+1）中的所有個體對應的解是否違反取值范圍約束，如有則進行解修正。假設(shè)個體解中一個元素x的取值范圍為［x^-，x⁺］，則解修正方法為

令修正后的種群為P₄（g+1）。

步驟 4 對新的種群P₄（g+1）進行排序，選擇其中作戰(zhàn)環(huán)效能最大的一個個體，意味著該個體在同樣的信息素分布下，能夠遵循該個體所對應的參數(shù)找到當前最優(yōu)的解，其對應的參數(shù)方案也是本輪迭代的蟻群中所有螞蟻的參數(shù)方案中最優(yōu)的，因此將其參數(shù)方案視為下一代參數(shù)優(yōu)化種群的r_gbest。如果有多個個體找到了同樣的當前最優(yōu)解，且這些個體對應的參數(shù)方案不同，那么從這些參數(shù)方案中隨機選擇一個作為r_gbest。

步驟 5 重復上述步驟，直到滿足蟻群算法的迭代停止條件。

2.3 改進3——基于遺傳算子的全局搜索能力提升

對任何智能算法而言，局部搜索能力和全局搜索能力都不可或缺。蟻群算法的核心思想是螞蟻按照路徑上信息素的強弱決定選擇路徑的概率，具有較強的局部尋優(yōu)能力。然而，蟻群算法探索未知空間的能力較弱，導致其全局收斂能力較差。一般而言，增強全局搜索能力的方法在于增加種群的多樣性，避免種群聚集，遺傳算法通過兩種遺傳算子（交叉和變異）大大提升了種群的多樣性。因此，本文將遺傳算子嵌入蟻群算法中，以提升蟻群的全局多樣性，同時又能夠保證其較強的局部搜索能力，嵌入遺傳算子的蟻群算法的思想如圖3所示。

圖3中，初始化蟻群分為兩個分支，一個基于信息素進行種群的優(yōu)化，另一個基于遺傳算子進行種群的優(yōu)化，兩個種群的最優(yōu)解被用作信息素更新的來源。這種方法利用信息素和遺傳算子同時驅(qū)動種群的優(yōu)化，以期獲取更優(yōu)的結(jié)果。

3 集成改進蟻群算法

本節(jié)對第2節(jié)提到的3種改進策略進行綜合集成，形成集成改進蟻群算法。同時，根據(jù)作戰(zhàn)環(huán)推薦問題的特征，對算法結(jié)構(gòu)進行相應的改造設(shè)計，使之適應作戰(zhàn)環(huán)推薦問題的特殊協(xié)同規(guī)則。

3.1 作戰(zhàn)環(huán)的解構(gòu)造算子

解構(gòu)造算子就是優(yōu)化算法中用于不斷生成新解的相應運算規(guī)則，蟻群算法的解構(gòu)造算子就是利用信息素尋找一條路徑的規(guī)則。與車輛路徑優(yōu)化中蟻群算法的解構(gòu)造過程不同，在作戰(zhàn)環(huán)推薦問題中，針對藍方目標尋找作戰(zhàn)環(huán)，不僅需要遵循信息素的指引進行解構(gòu)造，還需要滿足作戰(zhàn)環(huán)特有的裝備協(xié)同約束規(guī)則（目標→偵察→指控→打擊→目標）。因此，設(shè)計作戰(zhàn)環(huán)的解構(gòu)造算子，如算法1所示。

3.2 作戰(zhàn)環(huán)推薦方案的遺傳算子操作方法

對于傳統(tǒng)的路徑規(guī)劃問題，遺傳算子可以在直接交叉、變異后，對新解進行違反約束處理。但是對于作戰(zhàn)環(huán)推薦方案，直接進行交叉變異有可能破壞其本身的環(huán)結(jié)構(gòu)，比如將目標變異為某個紅方裝備，無法形成針對該目標的作戰(zhàn)環(huán)。因此，設(shè)計了一種保證環(huán)結(jié)構(gòu)穩(wěn)定的交叉變異遺傳方法，如圖4所示。

每個環(huán)的染色體都由5個基因位組成，分別代表“目標→偵察→指控→打擊→目標”的一條環(huán)，針對所有目標（假設(shè)有n個）的作戰(zhàn)環(huán)連接在一起，就構(gòu)成了一條針對所有目標的作戰(zhàn)環(huán)推薦方案的染色體，共有5n個基因位。執(zhí)行交叉操作時，從種群中隨機挑選兩個作戰(zhàn)環(huán)方案x₁和x₂，然后從對應的5n個基因位中隨機選擇5np^crossover個基因位（p^crossover為交叉概率），令x₁和x₂在這些選中的基因位上交換基因。由于每個基因位表示的裝備型號相同，因此對應基因位的交叉依然會保持“目標→偵察→指控→打擊→目標”的作戰(zhàn)環(huán)結(jié)構(gòu)。執(zhí)行變異操作時，避開表示目標類型裝備的基因位，從其他基因位上隨機選擇5np^crossover個基因進行變異，從與原有基因類型相同的紅方裝備集合中隨機挑選一個基因（與原有基因表示裝備不同）替換原有基因，可以避免對環(huán)結(jié)構(gòu)的破壞。

3.3 3種改進策略集成

將第3節(jié)中的3種改進策略集成到原始蟻群算法中，得到集成改進蟻群算法，期望可以分別改進原始蟻群算法存在的3方面缺陷（前期收斂速度慢、受參數(shù)影響大、容易陷入局部最優(yōu)），算法偽代碼如算法2所示。

4 示例分析

案例場景來源于“2020聯(lián)合作戰(zhàn)智能博弈挑戰(zhàn)賽”，數(shù)據(jù)來自“2020聯(lián)合作戰(zhàn)智能博弈挑戰(zhàn)賽白皮書”，該賽事為全國公開性比賽，賽事主辦方支持將數(shù)據(jù)用于非盈利性質(zhì)的學術(shù)研究，以促進相關(guān)領(lǐng)域的學術(shù)交流。

4.1 初始態(tài)勢設(shè)置

紅方共設(shè)置60個作戰(zhàn)單元，藍方共設(shè)置37個作戰(zhàn)單元。作戰(zhàn)環(huán)推薦問題就是針對藍方的37個目標，分別從紅方的60個作戰(zhàn)單元中構(gòu)成作戰(zhàn)環(huán)。將案例數(shù)據(jù)中雙方裝備態(tài)勢的位置信息輸入到對抗仿真模型中，形成的作戰(zhàn)網(wǎng)絡如圖5所示。

網(wǎng)絡連邊權(quán)重（連邊質(zhì)量）的數(shù)據(jù)可從文獻［31］下載。

4.2 原始蟻群算法優(yōu)化結(jié)果與分析

首先，設(shè)置原始蟻群算法的參數(shù)如下：種群數(shù)量為50;信息素重要程度因子為1;啟發(fā)函數(shù)重要程度因子為1;信息素揮發(fā)因子為0.1;信息素釋放總量為1。然后，在上述參數(shù)下迭代500次，收斂曲線如圖6所示。根據(jù)圖6，基于原始蟻群算法的作戰(zhàn)環(huán)推薦問題優(yōu)化在迭代300次左右時達到收斂，全局收斂速度較差。最終得到的最優(yōu)作戰(zhàn)效能為25.597 8，優(yōu)化效果一般。基于原始蟻群算法獲取的作戰(zhàn)環(huán)推薦優(yōu)化方案對應態(tài)勢如圖7所示。

根據(jù)圖7，基于原始蟻群算法獲取的最優(yōu)作戰(zhàn)環(huán)推薦方案態(tài)勢圖相對混亂，許多邊連接了距離較遠的裝備，從直觀上能夠判斷該方案的效果較差。分析其原因，原始蟻群算法的信息素初始化為全為1的矩陣。因此，算法在初期運行階段相當于隨機尋找作戰(zhàn)環(huán)，一旦找到一個相對較好的解（次優(yōu)解），則該解所在路徑的連邊上的信息素會逐漸積累，使算法陷入局部最優(yōu)。

4.3 3種改進策略下的蟻群算法優(yōu)化結(jié)果對比分析

首先，針對3種改進策略，分別求解改進后的優(yōu)化結(jié)果。除了改進2算法不需要設(shè)置參數(shù)，其他算法經(jīng)過實驗對比，選擇10次實驗中取得最佳結(jié)果的參數(shù)：種群數(shù)量為70，信息素重要程度因子為3，啟發(fā)函數(shù)重要程度因子為5，信息素揮發(fā)因子為0.4，信息素釋放總量為50。3種改進策略下算法的最大迭代次數(shù)設(shè)為300，在作戰(zhàn)環(huán)推薦問題上的優(yōu)化結(jié)果如圖8所示。根據(jù)圖8，相比原始蟻群算法，3種改進策略下的蟻群算法優(yōu)化結(jié)果均有提升，其中改進1型算法的提升效果最大，然后依次是改進3型和改進2型算法。改進1型算法能夠快速引導蟻群尋找到較優(yōu)秀的解，因而在算法初期就獲得很大的優(yōu)勢，在此基礎(chǔ)上進一步優(yōu)化，能夠獲得大幅優(yōu)于原始蟻群算法的優(yōu)化結(jié)果。

改進3型算法擴大了蟻群的搜索范圍，優(yōu)化結(jié)果相對傳統(tǒng)蟻群算法有較大提升。改進2型算法對蟻群算法參數(shù)進行了自適應優(yōu)化，雖然對蟻群算法效果的提升程度最小，但能在其他兩個改進策略的基礎(chǔ)上，對蟻群算法效果進行進一步提升。

4.4 與其他算法的對比

本節(jié)參照第4.3節(jié)，將3種改進策略綜合集成到原始蟻群算法上，并與其他3種公認較為有效的蟻群改進算法：ASelite^［32］、排序螞蟻系統(tǒng)（rank-based ant system， RAS）^［33］和最大最小蟻群算法（max-min ant colony algorithm， MACA）^［34］進行對比，每種算法運行10次，每次運行迭代100次，統(tǒng)計優(yōu)化結(jié)果如表1所示，優(yōu)化用時結(jié)果如表2所示。

根據(jù)表1和表2所列內(nèi)容，就平均值而言，集成改進算法的優(yōu)化結(jié)果最好，平均效能（距離理想點的距離）為4.559 22;就算法耗時而言，集成改進算法耗時最長，平均時間為209.399 s。

根據(jù)表1和表2所示10次運行的優(yōu)化結(jié)果，繪制4種算法10次運行結(jié)果和用時的箱型圖，如圖9和圖10所示。

可以看出，集成改進蟻群算法從值分布角度，要優(yōu)于其他3種算法。具體而言，4種算法結(jié)果之間的優(yōu)劣關(guān)系為：集成改進蟻群算法gt;MACAgt;ASelitegt;RAS。無論從算法優(yōu)化結(jié)果的平均值還是分布的角度，集成改進蟻群算法均表現(xiàn)最優(yōu)。

根據(jù)圖10，從算法耗時分布上看，4種算法的優(yōu)劣順序依次為：RAS＞ASelite＞改進3型蟻群算法＞MACA（集成改進蟻群算法的平均耗時雖然最長，但相比MACA，其耗時分布更為均勻）?？傮w而言，集成改進蟻群算法在效率上表現(xiàn)不如RAS和ASelite，與MACA基本持平。分析其原因，集成改進蟻群算法同時集成了3種改進策略，算法復雜度有所增加，但總體上集成改進算法的耗時與其他算法保持在同一量級下。

4.5 集成改進蟻群算法的最優(yōu)作戰(zhàn)環(huán)推薦方案

上述分析已經(jīng)證明了集成改進算法在小幅度增加耗時的情況下大幅提升了算法效果。本節(jié)根據(jù)第4.4節(jié)中集成改進算法的10次運行結(jié)果，從中選擇到理想點距離最小的值5.996 8，其對應作戰(zhàn)環(huán)推薦方案的態(tài)勢如圖11所示。

對比圖11所示態(tài)勢與第4.2節(jié)中圖7所示態(tài)勢，圖11中明顯減少了遠距離裝備之間的連邊，方案整體更合理，證明了集成改進蟻群算法的優(yōu)化結(jié)果有更好的實際效果。

5 結(jié)束語

本文面向作戰(zhàn)環(huán)推薦問題，提出了一種集成改進蟻群算法，在未明顯增加算法耗時的情況下大幅提升了算法效果。作戰(zhàn)環(huán)推薦是從作戰(zhàn)網(wǎng)絡中尋找路徑的問題，本文將其轉(zhuǎn)化為一種多倉庫路徑規(guī)劃的數(shù)學模型。然后，本文對原始蟻群算法做出了3點改進：基于邊權(quán)重信息的信息素初始化、基于差分進化的蟻群算法參數(shù)自適應優(yōu)化和基于遺傳算子的全局搜索能力提升，并進行了集成改進。改進后的算法在案例研究中被證明優(yōu)于單獨策略改進算法，并大幅優(yōu)于原始蟻群算法，同時在綜合性能上優(yōu)于其他3種改進蟻群算法（ASelite、RAS、MACA）。

本文研究為軍事運籌規(guī)劃提供了一種可求解大規(guī)模、非線性復雜問題的優(yōu)質(zhì)算法，可以在耗時方面將傳統(tǒng)人工決策的小時級提升到分鐘級，大大加速軍事運籌規(guī)劃的決策速度，具有重要意義。在未來的研究中，可結(jié)合軍事運籌領(lǐng)域中作戰(zhàn)環(huán)境時刻動態(tài)變化的獨有特征，研究應對動態(tài)環(huán)境的“增量式”優(yōu)化算法。

參考文獻

［1］孟二龍， 高桂清， 董浩， 等. 武器裝備智能化發(fā)展思考［J］. 兵工自動化， 2021， 40（6）： 12-15.

MENG E L， GAO G Q， DONG H， et al. Thinking on intelligent development of weapon equipment［J］. Ordnance Industry Automation， 2021， 40（6）： 12-15.

［2］MATTIS J. Summary of the 2018 national defense strategy of the United States of America［R］. Washington D.C.： Department of Defense， 2018.

［3］趙丹玲， 譚躍進， 李際超， 等. 基于作戰(zhàn)環(huán)的武器裝備體系貢獻度評估［J］. 系統(tǒng)工程與電子技術(shù)， 2017， 39（10）： 2239-2247.

ZHAO D L， TAN Y J， LI J C， et al. Armament system of systems contribution evaluation based on operation loop［J］. Systems Engineering and Electronics， 2017， 39（10）： 2239-2247.

［4］夏博遠， 楊克巍， 楊志偉， 等. 基于殺傷網(wǎng)評估的裝備組合多目標優(yōu)化［J］. 系統(tǒng)工程與電子技術(shù)， 2021， 43（2）： 399-409.

XIA B Y， YANG K W， YANG Z W， et al. Multi-objective optimization of equipment portfolio based on kill-web evaluation［J］. Systems Engineering and Electronics， 2021， 43（2）： 399-409.

［5］O’DONOUGHUE N A， MCBIRNEY S， PERSONS B. Distri-buted kill chains： drawing insights for mosaic warfare from the immune system and from the navy［R］. Arlington： Rand Corporation， 2021.

［6］The Mitchell Institute. Restoring America’s military competitiveness： mosaic warfare［EB/OL］. ［2022-04-11］. https：∥mitchellaerospacepower.org/restoring-americas-military-competitiveness-mosaic-warfare/.

［7］KHORRAM B， YAZDI M. A new optimized thresholding method using ant colony algorithm for MR brain image segmentation［J］. Journal of Digital Imaging， 2019， 32（1）： 162-174.

［8］TIAN X， LIU L， LIU S， et al. Path planning of mobile robot based on improved ant colony algorithm for logistics［J］. Mathematical Biosciences and Engineering， 2021， 18（4）： 3034-3045.

［9］YI N， XU J J， YAN L M， et al. Task optimization and scheduling of distributed cyber-physical system based on improved ant colony algorithm［J］. Future Generation Computer Systems， 2020， 109（1）： 134-148.

［10］CHU K C， HORNG D J， CHANG K C. Numerical optimization of the energy consumption for wireless sensor networks based on an improved ant colony algorithm［J］. IEEE Access， 2019， 7： 105562-105571.

［11］DI C D， EBRAHIMNEJAD A， ALREZAAMIRI H， et al. A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights［J］. Alexandria Engineering Journal， 2022， 61（5）： 3403-3415.

［12］張松燦， 普杰信， 司彥娜， 等. 蟻群算法在移動機器人路徑規(guī)劃中的應用綜述［J］.計算機工程與應用， 2020， 56（8）： 10-19.

ZHANG S C， PU J X， SI Y N， et al. Survey on application of ant colony algorithm in path planning of mobile robot［J］. Computer Engineering and Applications， 2020， 56（8）： 10-19.

［13］DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperating agents［J］. IEEE Trans.on Systems， Man， and Cybernetics， 1996， 26（1）： 29-41.

［14］BULLNHEIMER B， HARTL R F，STRAUSS C. A new rank based version of the ant central system-a computational study［J］. European Journal of Operations Research， 1999， 7（1）： 25-38.

［15］STUTZLE T， HOOS H H. Max-min ant system［J］. Future Generation Computer Systems， 1999， 16（9）： 889-914.

［16］DORIGO M， GAMBARDELLA L M. Ant colony system： a cooperative learning approach to the traveling salesman problem［J］. IEEE Trans.on Evolutionary Computation， 1997， 1（1）： 53-66.

［17］CIORNEI I， KYRIAKIDES E. Hybrid ant colony-genetic algorithm （GAAPI） for global continuous optimization［J］. IEEE Trans.on Systems， Man， and Cybernetics， Part B （Cybernetics）， 2011， 42（1）： 234-245.

［18］YU X， CHEN W N， GU T L， et al. ACO-A*： ant colony optimization plus A* for 3-D traveling in environments with dense obstacles［J］. IEEE Trans.on Evolutionary Computation， 2019， 23（4）： 617-631.

［19］SHAO J， CHENG J， XIA B Y， et al. A novel service system for long-distance drone delivery using the “ant colony+A*” algorithm［J］. IEEE Systems Journal， 2020， 15（3）： 3348-3359.

［20］DAI X L， LONG S， ZHANG Z W， et al. Mobile robot path planning based on ant colony algorithm with A* heuristic method［J］. Frontiers in Neurorobotics， 2019， 13（1）： 15-23.

［21］江明， 王飛， 葛愿， 等. 基于改進蟻群算法的移動機器人路徑規(guī)劃研究［J］. 儀器儀表學報， 2019， 40（2）： 113-121.

JIANG M， WANG F， GE Y， et al. Research on path planning of mobile robot based on improved ant colony algorithm［J］. Chinese Journal of Scientific Instrument， 2019， 40（2）： 113-121.

［22］杜鵬楨， 唐振民， 孫研. 一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解［J］. 控制與決策， 2014， 29（10）： 1729-1736.

DU P Z， TANG Z M， SUN Y. An object-oriented multi-role ant colony optimization algorithm for solving TSP problem［J］. Control and Decision， 2014， 29（10）： 1729-1736.

［23］JIANG W Y， LIN Y， CHEN M， et al. A co-evolutionary improved multi-ant colony optimization for ship multiple and branch pipe route design［J］. Ocean Engineering， 2015， 102（1）： 63-70.

［24］DENG W， XU J J， SONG Y J， et al. An effective improved co-evolution ant colony optimization algorithm with multi-strategies and its application［J］. International Journal of Bio-Inspired Computation， 2020， 16（3）： 158-170.

［25］韋銘燕， 陳彧， 張亮. 針對混合變量優(yōu)化問題的協(xié)同進化蟻群優(yōu)化算法［J］. 計算機應用， 2021， 41（5）： 1412-1418.

WEI M Y， CHEN Y， ZHANG L. Co-evolutionary ant colony optimization algorithm for mixed-variable optimization problem［J］. Journal of Computer Applications， 2021， 41（5）： 1412-1418.

［26］LUO Q， WANG H B， ZHENG Y， et al. Research on path planning of mobile robot based on improved ant colony algorithm［J］. Neural Computing and Applications， 2020， 32（6）： 1555-1566.

［27］DENG W， ZHAO H M， ZOU L， et al. A novel collaborative optimization algorithm in solving complex optimization problems［J］. Soft Computing， 2017， 21（15）： 4387-4398.

［28］LIU S， GE J K， CHENG W J， et al. Research on WSN routing based on pheromone factor of improved ant colony algorithm［C］∥Proc.of the IEEE International Conference on Emergency Science and Information Technology， 2021： 499-503.

［29］JIAO Z Q， MA K， RONG Y L， et al. A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs［J］. Journal of Computational Science， 2018， 25： 50-57.

［30］LIU P， LI J C， XIA B Y， et al. Weapons equipment portfolios selection based on equipment system contribution rates［J］. Journal of Systems Engineering and Electronics， 2021， 32（3）： 584-595.

［31］論文數(shù)據(jù)（作戰(zhàn)網(wǎng)絡連邊質(zhì)量）［EB/OL］. ［2022-04-11］. https：∥download.csdn.net/download/xz15873139854/19973235？spm=1001.2014.3001.5501.

［32］LU M L， XU B L， SHENG A D， et al. Modeling analysis of ant system with multiple tasks and its application to spatially adjacent cell state estimate［J］. Applied Intelligence， 2014， 41（1）： 13-29.

［33］TOMOKO S， KOTARO U， IKUO A. Rank-based ant system via the relative position in a local hierarchy［J］. Complexity， 2021， 2021： 8372318.

［34］BRODERICK C， RICARDO S， FRANKLIN J， et al. A max-min ant system algorithm to solve the software project scheduling problem［J］. Expert Systems with Applications， 2014， 41（15）： 6634-6645.

作者簡介

李 杰（1985—），男，博士研究生，主要研究方向為武器裝備體系建模、武器裝備體系論證。

譚躍進（1958—），男，教授，博士研究生導師，博士，主要研究方向為復雜系統(tǒng)理論、武器裝備體系論證。