基于Memetic算法的動態武器目標分配問題研究＊

劉傳波

（武漢市74223信箱 武漢 430074）

1 引言

武器目標分配（Weapon Target Assignment，WTA）問題的研究是目前防空領域作戰指揮決策所需解決的重點和難點問題。傳統意義上的靜態武器目標分配（Static Weapon Target Assignment，SWTA）問題的研究已不滿足在實際作戰指揮決策的需求，由于目標在時間和空間上出現的不確定性，使得部分武器不能及時投入戰斗，同時，新目標的出現使得分配過程變得更加復雜。考慮時間因素影響的動態武器目標分配（Dynamic Weapon Target Assignment，DWTA）問題研究逐漸成為近年來研究的重要方向。

目前對DWTA問題的研究主要集中在尋求一種有效的智能算法來解決時間因素對分配過程的影響，提高動態分配的及時性和合理性。文獻［1］提出了“時間窗（Time-Window）”的概念用以描述時間約束，用一種混合遺傳算法來解決DWTA問題；文獻［2］運用約束規劃方法建立了DWTA問題的約束滿足問題，并提出了一種隨機變鄰域禁忌搜索算法對模型進行求解；文獻［3］和［4］針對有截止期的DWTA問題，利用元級控制過程控制改進型遺傳算法的響應時間，提出一種元級控制策略來提高解的效用。文獻［5］和［6］分別提出了基于貪婪局部搜索的 Memetic算法和基于禁忌搜索拍賣算法來解決具有帶約束的DWTA問題。上述研究結果要么仍局限于靜態分配的思想，要么未從分配的動態過程來解決該問題。盡管DWTA問題并未得到完整解決，但在許多實際應用中，通過放寬某些約束條件或增加某些假設條件可以得到一些特殊情況（如所有武器完全一樣的情況）下的最優解，或一般情況下的近似解。同時必須注意到只有把分配過程中的動態隨機事件考慮在內，才能得到對實際應用更為有效的武器目標分配算法。

本文分析了動態武器目標分配問題的特點，建立了具有時間和空間約束的DWTA數學模型，提出了一種自適應Memetic算法來解決該問題，該算法結合遺傳算法和模擬退火算法的特性，有效提高全局和局部搜索的能力，并采用一種有限時間控制策略來提高滿意解的輸出質量，能及時應對隨機事件（新目標的出現）對前期優化過程的控制和重構。

2 DWTA問題的描述和數學模型構建

2.1 問題描述

由于目標群的出現是一個隨機過程，且武器系統的空間分布存在不同的狀態，不同類型目標出現的時空分布不同，因此，對于DWTA問題的研究十分復雜，目前的研究主要針對特定的作戰態勢，作一定的假設條件來簡化問題的復雜性，由淺入深的思路來分析該問題。本文假設防空武器系統由分布在n個平臺的m個同類武器單元組成，武器總數為W＝n·m，且各單元類型相同；目標類型和速度相同，均處于勻速直線飛行的巡航段。初始狀態下，系統根據武器單元狀態和已探測到的目標狀態信息，計算并輸出優化分配方案對目標攔截作為一個時間階段。因此防空作戰過程可劃分為不確定的K個階段，DWTA優化過程是通過有限時間內合理分配各個階段的“武器目標對”方案，最終實現最小化目標群的突防概率，或最大化系統防空攔截效率。

1）目標的空間約束。設目標j對應N個平臺的航路捷徑向量Pj＝［pj1pj2… pjn］，目標對應各武器平臺所在位置的航路捷徑Pji是否小于其最大航路捷徑Pimax，且i＝1，2，…，n。即滿足條件：

若滿足，則可確定目標j處在平臺集合N′的作戰空域內，N′∈N。

2）目標的時間約束。目標的時間約束是建立在滿足目標空間約束的基礎上，進入同一平臺武器發射區內的目標集合，從分配決策開始，按目標到達發射區近界的時間，分別進行排序，選擇最先到達的目標所需時間為分配的截止期。其中，目標截止期計算的近似方法如下：取武器目標分配決策開始時刻，目標j所在位置點為（x，y），對應平臺航路角為α，則根據幾何關系，（x，y）與到達發射區近界位置點（x′，y′）有如下關系：

則目標到發射區近界的時間間隔ts為

假設有四個目標T1～T4被探測到時正處于武器的發射區之外，它們到達發射區近界的所需時間分別是t1～t4，因而ti（i＝1，…，4）是完成對目標Ti（i＝1，…，4）分配武器的截止期。假設t4＜t3＜t1＜t2，按照到來時間的先后順序建立所有正在處理中的目標的截止期，則最先到來的截止期是t4，它所對應的目標是T4，因此算法應以完成對目標T4的武器分配為停止準則。而針對該態勢下的靜態的武器目標分配則是不考慮有效打擊時間，將四個武器同時分配給四個目標。

2.2 數學模型的建立

將攔截之后的目標的總期望剩余威脅值作為目標函數，假設武器對目標的攔截和毀傷都是相互獨立的，則在第k（k＝1，2，…，K）時間段的武器目標分配數學描述如下：

其中，NW（k）為武器數量，NT（k）為目標數量，Vi為第i個目標的威脅值，Pij為第j個武器用于攔截第i個目標的毀傷概率；Xij（k）為布爾值，表示第j個武器對第i個目標的分配決策變量，若分配則為1，否則為0。式（5）表示一個武器只能攔截一個目標，式（6）表示最多可攔截的目標數量不大于武器數量NW（k）。

則整個時間段K內總的目標函數為

3 Memetic算法的設計概述

3.1 Memetic算法概述

Memetic算法是Moscato等人于1989年首先提出的一種較寬松的優化算法框架，或算法設計思想［7］。采用不同的搜索策略可構成不同的 Memetic算法，如全局搜索策略采用遺傳算法、進化策略、粒子群算法、魚群算法等，局部搜索策略采用爬山搜索、模擬退火、貪婪算法、禁忌搜索、導引式局部搜索等［8～10］。其實現遵循如下框架：

步驟1：根據具體優化問題，選擇并確定全局和局部搜索策略。

步驟2：初始化種群。

步驟3：種群的全局搜索。

步驟4：個體的局部搜索。

步驟5：種群的局部更新。

步驟6：判斷終止條件。若滿足，算法停止；否則，返回步驟3。

3.2 關鍵參數和操作設計

Memetic算法作為一種混合算法框架，其各個環節存在多種可實施的策略，根據上述DWTA問題的描述，本文提出一種自適應的Memetic算法來解決該問題。其中，適應度函數為目標函數，全局搜索策略采用遺傳算法，局部搜索策略采用模擬退火算法。下面分別從五個方面進行設計：

1）種群的產生。通常的算法而言初始種群是隨機產生的，若按隨機的方式生成初始群體，則在搜索的過程中耗時長且可能得不到最優解。對于DWTA問題，則可根據給定目標群初始狀態，計算對應的空間約束，來確定可選的種群，排除無效個體，從而提高種群的優化效率；

2）進化操作。進化操作分別采用遺傳算法中的交叉和變異算子，以確保子代能夠遺傳父代的主要特征。

初始狀態下，交叉操作選擇單點順序交叉法，該方法具體過程為：設兩父串為A、B，隨機選擇交叉點，定義交叉點后為匹配區域，將A和B的匹配區域分別加到B和A的前面，然后分別在匹配區域后依次刪除與匹配區域相同的碼得新的子串，如：

變異操作選擇對換變異法，即隨機選擇串中非禁止位的兩點，交換其值獲得新串。如：當分配過程達到初始目標時間截止期時，設定對應武器目標對為禁止位，單點順序交叉后，變：如目標3分配給武器4，則A［4］＝B［4］＝3為禁止位，有：

變異操作選擇對換變異法，即隨機選擇串中除禁止位以外的兩點，交換其值獲得新串。

3）局部搜索。局部搜索的過程是優選局部優秀個體的過程，其關鍵問題主要在于：鄰域空間的選擇要使得優化效率和優化時間兩者的折中，局部搜索策略的選擇要針對具體問題的特點進行考慮，局部搜索在算法流程中的位置需保證優化效率為前提。因此，本文采用一種改進的模擬退火算法來進行鄰域搜索，其偽代碼如下：

4）種群的選擇與更新。經過進化操作和局部搜索后，采用錦標賽選擇等方法優選出新的個體來更新種群。錦標賽法在選擇時，從種群中隨機地選取k個個體，找出這k個個體中適應值最好的個體作為最優個體，這個最優個體就是下一代種群中的一個個體，這個過程重復n次就產生了新的種群。盡管該方法隨機性更強，存在更大的隨機誤差，但是有較大概率保證最優個體被選擇，最差的個體被淘汰。

5）終止準則。以算法運行到規定的時間截止期來輸出結果，或目標函數在時間截止期內達到規定的精度，則輸出結果。

3.3 一種自適應的Memetic算法流程設計

該算法的設計包括如下步驟：

1）確定空間約束下武器目標集合；

2）計算目標對應武器作戰空域的時間截止期，得出目標集對應的時間截止期遞增序列向量Tstop；

3）執行Memetic算法，判斷算法執行時間t是否到達Tstop（1），若到達，輸出對應的分配方案，取Tstop（1）中目標對應武器位為禁止位，繼續執行算法，依次輸出Tstop（2）…Tstop（N），目標分配完畢后，算法停止。

算法對新目標出現處理策略：

（1）新目標出現時，未有武器空閑，則等待武器射擊完畢后再分配；

（2）新目標出現時，有武器空閑，計算目標對應的時間截止期，依次按Memetic算法對其進行分配。

4 實例

假設防御方探測到一批目標來襲，根據目標航跡信息計算目標群的空間約束，其中，有20個目標即進入某作戰空域，由分配在不同平臺的20個武器單元對目標進行攔截，目標威脅程度分別在［0.2 0.9］內隨機生成，武器對目標的毀傷概率在［0.2 0.9］隨機生成。初始狀態計算目標的截止期，并升序排列，如表1所示：

表1 目標序列及截止期

根據目標截止期，依次執行Memetic算法，分別獲得武器目標分配方案，至第20個目標分配完畢，最終分配方案如表2所示。

表2 武器目標分配方案

如圖1所示為最優適應度值隨進化代數和算法運行時間變化的曲線圖，其中，曲線中分布的圓點為每一個目標截止期對應的最優適應度值和進化代數值，該算法最終執行完畢獲得的最優適應度值為9.6009。如圖2所示為Memetic算法與單純遺傳算法和模擬退火算法的最優適應度值隨時間變化的迭代曲線。在給定的時間截止期，Memetic算法的最優適應度值優于其他兩種算法，而單純遺傳算法和模擬退火算法易陷入局部最優解。

圖1 Memetic算法迭代曲線圖

圖2 三種算法收斂曲線圖

根據仿真輸出結果分析，本文提出的算法相比傳統智能算法具有任意時間輸出的特性。首先，它集中了GA的全局搜索能力和SA的局部搜索能力，能高效地跳出局部最優解，算法性能高；其次，能在不破壞算法運行狀態的情況下，及時輸出規定時間內滿意解；同時，針對新目標的出現，算法能夠動態地調整優化過程，符合實際武器目標分配需求。

5 結語

本文針對帶空間和時間約束的DWTA問題，首先建立平臺武器對目標的空間約束，計算帶空間約束下目標對武器發射區的時間截止期，并在此基礎上，提出了一種Memetic算法解決帶時間截止期的動態分配過程。該算法在運行過程具備Anytime特性，能有效輸出有效時間約束下的滿意解，同時能夠靈活地處理新目標出現對前一階段武器目標分配過程的影響。該問題的解決對于深入研究滿足實際應用條件的武器目標分配問題具有深刻的現實意義，提高算法處理的時效性和靈活性是下一步研究的重點問題。

［1］Khosla D.Hybrid genetic approach for the dynamic weapon-target allocation problem［C］.Proceeding of SPIE，2001，4396：248-263.

［2］陳英武，蔡懷平，邢立寧.SVNTS算法的動態武器目標分配問題研究［J］.計算機工程與應用，2006（31）：7-10.

［3］Cai Huaiping，Liu Jingxu，Chen Yingwu，et al.Survey of the research on dynamic weapon-target assignment problem［J］.Journal of Systems Engineering and Electronics，2006，17（3）：559-565.

［4］Wu Ling，Wang H，Lu Faxing.An anytime algorithm based on modified GA for dynamic weapon-target allocation problem［C］.WCCI，Hong Kong，China，2008：234-238.

［5］Peng Li，Ling Wu，Faxing Lu.Analysis on influential factors for meta-level control of the anytime algorithm for dynamic WTA problem［C］.ISA，Wuhan，China，2009：1-4.

［6］Chen Jie，Xin Bin，Peng Zhihong，et al.Evolutionary decisionmaking for the dynamic weapon-target assignment problem，Sci China Ser F-inf Sci，2009，52（11）：2006-2018.

［7］Moscato P.On evolution，search，optimization，genetic algorithms and martial arts：towards Memetic algorithms［R］.California：California Institute of Technology，1989.

［8］Paulo V W，Wong T，Sabourin R.A multi-objective memetic algorithm for intelligent feature extraction［C］.Proceeding of the Third International Conference on Evolutionary Multi-Criterion Optimization.Mexico：Guanajuato，2005：663-672.

［9］Berreta R，Rodrigues L F.A memetic algorithm for a multistage capacitated lot-sizing problem ［J］.Int.J.Production Economics，2004，87（1）：67-81.

［10］Xiuping Guo，Genke Yang，Zhiming Wu.A hybrid self-adjusted memetic alogorithm for multi-objective optimization ［C］.Fourth Mexican International Conference on Artficial Intelligence.Berlin：Springer Verlag，2004：542-548.