劉傳波

（武漢市74223信箱 武漢 430074）

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

則整個(gè)時(shí)間段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)化問(wèn)題，選擇并確定全局和局部搜索策略。

步驟2：初始化種群。

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

步驟4：個(gè)體的局部搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例

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

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

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

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

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

圖1 Memetic算法迭代曲線圖

圖2 三種算法收斂曲線圖

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

5 結(jié)語(yǔ)

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

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

［2］陳英武，蔡懷平，邢立寧.SVNTS算法的動(dòng)態(tài)武器目標(biāo)分配問(wèn)題研究［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.