基于Memetic算法的動態(tài)武器目標(biāo)分配問題研究＊

劉傳波

（武漢市74223信箱 武漢 430074）

1 引言

武器目標(biāo)分配（Weapon Target Assignment，WTA）問題的研究是目前防空領(lǐng)域作戰(zhàn)指揮決策所需解決的重點(diǎn)和難點(diǎn)問題。傳統(tǒng)意義上的靜態(tài)武器目標(biāo)分配（Static Weapon Target Assignment，SWTA）問題的研究已不滿足在實(shí)際作戰(zhàn)指揮決策的需求，由于目標(biāo)在時間和空間上出現(xiàn)的不確定性，使得部分武器不能及時投入戰(zhàn)斗，同時，新目標(biāo)的出現(xiàn)使得分配過程變得更加復(fù)雜?？紤]時間因素影響的動態(tài)武器目標(biāo)分配（Dynamic Weapon Target Assignment，DWTA）問題研究逐漸成為近年來研究的重要方向。

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

本文分析了動態(tài)武器目標(biāo)分配問題的特點(diǎn)，建立了具有時間和空間約束的DWTA數(shù)學(xué)模型，提出了一種自適應(yīng)Memetic算法來解決該問題，該算法結(jié)合遺傳算法和模擬退火算法的特性，有效提高全局和局部搜索的能力，并采用一種有限時間控制策略來提高滿意解的輸出質(zhì)量，能及時應(yīng)對隨機(jī)事件（新目標(biāo)的出現(xiàn)）對前期優(yōu)化過程的控制和重構(gòu)。

2 DWTA問題的描述和數(shù)學(xué)模型構(gòu)建

2.1 問題描述

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

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

若滿足，則可確定目標(biāo)j處在平臺集合N′的作戰(zhàn)空域內(nèi)，N′∈N。

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

則目標(biāo)到發(fā)射區(qū)近界的時間間隔ts為

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

2.2 數(shù)學(xué)模型的建立

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

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

則整個時間段K內(nèi)總的目標(biāo)函數(shù)為

3 Memetic算法的設(shè)計(jì)概述

3.1 Memetic算法概述

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

步驟1：根據(jù)具體優(yōu)化問題，選擇并確定全局和局部搜索策略。

步驟2：初始化種群。

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

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

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

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

3.2 關(guān)鍵參數(shù)和操作設(shè)計(jì)

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

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

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

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

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

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

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

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

5）終止準(zhǔn)則。以算法運(yùn)行到規(guī)定的時間截止期來輸出結(jié)果，或目標(biāo)函數(shù)在時間截止期內(nèi)達(dá)到規(guī)定的精度，則輸出結(jié)果。

3.3 一種自適應(yīng)的Memetic算法流程設(shè)計(jì)

該算法的設(shè)計(jì)包括如下步驟：

1）確定空間約束下武器目標(biāo)集合；

2）計(jì)算目標(biāo)對應(yīng)武器作戰(zhàn)空域的時間截止期，得出目標(biāo)集對應(yīng)的時間截止期遞增序列向量Tstop；

3）執(zhí)行Memetic算法，判斷算法執(zhí)行時間t是否到達(dá)Tstop（1），若到達(dá)，輸出對應(yīng)的分配方案，取Tstop（1）中目標(biāo)對應(yīng)武器位為禁止位，繼續(xù)執(zhí)行算法，依次輸出Tstop（2）…Tstop（N），目標(biāo)分配完畢后，算法停止。

算法對新目標(biāo)出現(xiàn)處理策略：

（1）新目標(biāo)出現(xiàn)時，未有武器空閑，則等待武器射擊完畢后再分配；

（2）新目標(biāo)出現(xiàn)時，有武器空閑，計(jì)算目標(biāo)對應(yīng)的時間截止期，依次按Memetic算法對其進(jìn)行分配。

4 實(shí)例

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

表1 目標(biāo)序列及截止期

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

表2 武器目標(biāo)分配方案

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

圖1 Memetic算法迭代曲線圖

圖2 三種算法收斂曲線圖

根據(jù)仿真輸出結(jié)果分析，本文提出的算法相比傳統(tǒng)智能算法具有任意時間輸出的特性。首先，它集中了GA的全局搜索能力和SA的局部搜索能力，能高效地跳出局部最優(yōu)解，算法性能高；其次，能在不破壞算法運(yùn)行狀態(tài)的情況下，及時輸出規(guī)定時間內(nèi)滿意解；同時，針對新目標(biāo)的出現(xiàn)，算法能夠動態(tài)地調(diào)整優(yōu)化過程，符合實(shí)際武器目標(biāo)分配需求。

5 結(jié)語

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

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

［2］陳英武，蔡懷平，邢立寧.SVNTS算法的動態(tài)武器目標(biāo)分配問題研究［J］.計(jì)算機(jī)工程與應(yīng)用，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，F(xiàn)axing 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.