反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度方法

趙新爽，汪厚祥，蔡益朝

（1．空軍預(yù)警學(xué)院空天預(yù)警實(shí)驗(yàn)室，湖北武漢430019；2．海軍工程大學(xué)電子工程學(xué)院，湖北武漢430033）

反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度方法

趙新爽1，2，汪厚祥2，蔡益朝1

（1．空軍預(yù)警學(xué)院空天預(yù)警實(shí)驗(yàn)室，湖北武漢430019；2．海軍工程大學(xué)電子工程學(xué)院，湖北武漢430033）

針對(duì)反導(dǎo)預(yù)警作戰(zhàn)中多部預(yù)警資源協(xié)同探測(cè)多批彈道導(dǎo)彈目標(biāo)的問(wèn)題，根據(jù)反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度的特點(diǎn)，提出了反導(dǎo)預(yù)警作戰(zhàn)任務(wù)分解策略，并以調(diào)度效益、交接次數(shù)和資源負(fù)載均衡度為目標(biāo)建立了多目標(biāo)優(yōu)化模型。通過(guò)重新設(shè)計(jì)粒子編碼方式以及對(duì)重新定義粒子群優(yōu)化算法中的位置更新公式，使其適用于求解離散變量?jī)?yōu)化問(wèn)題。針對(duì)粒子群優(yōu)化算法容易過(guò)早收斂的缺點(diǎn)，在進(jìn)行局部搜索時(shí)使用變鄰域搜索算法，從而增強(qiáng)算法的尋優(yōu)能力。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證，將兩種算法相結(jié)合能夠快速有效地解決反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度問(wèn)題。

資源調(diào)度；粒子群－變鄰域搜索；多目標(biāo)優(yōu)化問(wèn)題；反導(dǎo)預(yù)警

0 引 言

反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度面向的是對(duì)處于中段飛行的中遠(yuǎn)程彈道導(dǎo)彈進(jìn)行預(yù)警探測(cè)時(shí)，預(yù)警任務(wù)對(duì)資源的分配問(wèn)題。由于中遠(yuǎn)程彈道導(dǎo)彈飛行距離遠(yuǎn)，沒(méi)有一部地基雷達(dá)能夠單獨(dú)地完成整個(gè)飛行階段的預(yù)警探測(cè)任務(wù)，需要多部雷達(dá)對(duì)同一目標(biāo)進(jìn)行接力跟蹤。而如果同時(shí)出現(xiàn)多批目標(biāo)，在目標(biāo)與預(yù)警資源的可見(jiàn)關(guān)系改變、雷達(dá)跟蹤目標(biāo)容量限制以及目標(biāo)威脅程度變化等因素的作用下，如何有效地調(diào)度可用的預(yù)警資源，使其能最好地完成預(yù)警探測(cè)任務(wù)是一項(xiàng)必須解決而又棘手的問(wèn)題。

目前，對(duì)反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度方面的研究大部分集中在天基預(yù)警系統(tǒng)的資源調(diào)度上，文獻(xiàn)［1－4］對(duì)天基預(yù)警系統(tǒng)中的低軌衛(wèi)星資源調(diào)度問(wèn)題進(jìn)行了研究，建立了該問(wèn)題的約束滿足問(wèn)題模型，并設(shè)計(jì)了一些算法求解相應(yīng)的模型。而在利用地基預(yù)警裝備進(jìn)行彈道導(dǎo)彈預(yù)警探測(cè)的資源調(diào)度方面，目前極少有人研究。地基預(yù)警探測(cè)的資源調(diào)度與天基預(yù)警探測(cè)的資源調(diào)度有著很大的不同：首先，天基預(yù)警資源只有低軌衛(wèi)星一種，而地基預(yù)警資源有P波段遠(yuǎn)程預(yù)警雷達(dá)和X波段多功能地基雷達(dá)，在進(jìn)行預(yù)警探測(cè)時(shí)，這兩種雷達(dá)有不同的優(yōu)先級(jí)；其次，利用天基預(yù)警資源探測(cè)目標(biāo)時(shí)，需要多部資源同時(shí)探測(cè)一個(gè)目標(biāo)，而一部地基預(yù)警裝備可以同時(shí)探測(cè)多批目標(biāo)。而且，文獻(xiàn)［1］所建立的模型都是單目標(biāo)的優(yōu)化模型，不能夠很好地反映反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度的問(wèn)題。

針對(duì)此，本文建立了反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度的多目標(biāo)優(yōu)化模型，并設(shè)計(jì)一種粒子群－變鄰域搜索算法求解調(diào)度模型，進(jìn)而利用仿真實(shí)驗(yàn)驗(yàn)證該算法的性能。

1 反導(dǎo)預(yù)警任務(wù)分解

在預(yù)警探測(cè)任務(wù)的執(zhí)行過(guò)程中，預(yù)警任務(wù)必須指派到預(yù)警裝備上才可以直接執(zhí)行，而目標(biāo)與預(yù)警資源之間復(fù)雜的可見(jiàn)關(guān)系給預(yù)警任務(wù)的指派帶來(lái)了極大難度。任務(wù)分解是處理這種復(fù)雜關(guān)系很好的手段。任務(wù)分解是指將復(fù)雜的任務(wù)細(xì)化為能由作戰(zhàn)資源直接執(zhí)行和完成的元任務(wù)序列。這里的元任務(wù)是指不再進(jìn)行分解、可直接一次性執(zhí)行的最基本任務(wù)［5］。經(jīng)過(guò)任務(wù)分解后，每個(gè)元任務(wù)都會(huì)對(duì)應(yīng)一個(gè)可用的預(yù)警資源集合。預(yù)警任務(wù)分解極大地降低了任務(wù)與資源之間復(fù)雜的對(duì)應(yīng)可見(jiàn)關(guān)系，同時(shí)，將調(diào)度周期內(nèi)的預(yù)警任務(wù)分解為一系列的元任務(wù)，每個(gè)元任務(wù)都對(duì)應(yīng)一個(gè)或多個(gè)可用資源，只需從中選擇一個(gè)執(zhí)行該元任務(wù)即可。而對(duì)整個(gè)預(yù)警探測(cè)任務(wù)而言，在每個(gè)元任務(wù)對(duì)應(yīng)的可用資源集中挑出一個(gè)資源即可形成一個(gè)滿足預(yù)警探測(cè)任務(wù)需求的調(diào)度方案。

1．1 任務(wù)分解策略分析

不同的任務(wù)分解策略往往會(huì)得出不同的元任務(wù)集，最終導(dǎo)致調(diào)度方案也不同。目前，比較常見(jiàn)的任務(wù)分解策略有兩種，分別是“基于最長(zhǎng)觀測(cè)時(shí)間”和“基于均勻分割”。“基于最長(zhǎng)觀測(cè)時(shí)間”的任務(wù)分解策略的思想是在任意一個(gè)必須對(duì)目標(biāo)進(jìn)行交接的時(shí)間點(diǎn)處，在其可選的資源中，尋找一個(gè)對(duì)目標(biāo)觀測(cè)時(shí)間最長(zhǎng)的資源作為切換的對(duì)象。該分解策略的優(yōu)點(diǎn)是能減少目標(biāo)在預(yù)警資源之間的頻繁交接，而缺點(diǎn)是可能出現(xiàn)某些元任務(wù)的執(zhí)行時(shí)間過(guò)短的情況。預(yù)警資源在對(duì)目標(biāo)進(jìn)行探測(cè)時(shí)，需要一定的時(shí)間才能進(jìn)入穩(wěn)定跟蹤狀態(tài)，元任務(wù)對(duì)應(yīng)的時(shí)間區(qū)間過(guò)短可能導(dǎo)致預(yù)警資源還沒(méi)有對(duì)目標(biāo)形成穩(wěn)定航跡就必須放棄探測(cè)任務(wù)，從而導(dǎo)致該目標(biāo)丟失。“基于均勻分割”的任務(wù)分解策略的思想是設(shè)定一個(gè)最小的區(qū)間長(zhǎng)度Tm，每隔Tm時(shí)間對(duì)預(yù)警任務(wù)劃分一次，每個(gè)元任務(wù)對(duì)應(yīng)的區(qū)間長(zhǎng)度為Tm的整數(shù)倍。該分解策略優(yōu)點(diǎn)是分解方式簡(jiǎn)單，任務(wù)執(zhí)行的時(shí)間比較固定。但是在分解時(shí)，元任務(wù)對(duì)應(yīng)的最小區(qū)間長(zhǎng)度很難確定，太短則會(huì)引起頻繁的切換，太長(zhǎng)則可能導(dǎo)致沒(méi)有一個(gè)預(yù)警資源能獨(dú)立地執(zhí)行該元任務(wù)。

另外，文獻(xiàn)［3］設(shè)計(jì)了一種基于關(guān)鍵點(diǎn)的預(yù)警任務(wù)分解策略，但該策略針對(duì)的是天基預(yù)警系統(tǒng)資源調(diào)度過(guò)程，而且該分解過(guò)程復(fù)雜，可操作性不強(qiáng)，不適合本文預(yù)警資源調(diào)度的特點(diǎn)。以上3種任務(wù)分解策略都不適用于對(duì)反導(dǎo)預(yù)警作戰(zhàn)任務(wù)的分解。

1．2 反導(dǎo)預(yù)警作戰(zhàn)的任務(wù)分解策略

根據(jù)反導(dǎo)預(yù)警過(guò)程和反導(dǎo)預(yù)警資源的特點(diǎn)，結(jié)合后續(xù)資源調(diào)度建模的需要，在對(duì)預(yù)警任務(wù)進(jìn)行分解時(shí)，要遵守以下約束條件：

（1）兩個(gè)相鄰的元任務(wù)在時(shí)間上不要求是必須緊密銜接的，但是其間隔不能超過(guò)特定閾值T0，以保證在該時(shí)間間隔內(nèi)目標(biāo)不會(huì)丟失。

（2）每個(gè)元任務(wù)對(duì)應(yīng)時(shí)間區(qū)間內(nèi)的預(yù)警資源不發(fā)生變化，即在對(duì)預(yù)警資源進(jìn)行調(diào)度時(shí)，可以從每個(gè)元任務(wù)的可用資源集中任選一個(gè)來(lái)完成對(duì)該元任務(wù)的全程探測(cè)。

（3）每個(gè)元任務(wù)具有最短持續(xù)時(shí)間Tmin，以保證預(yù)警資源能進(jìn)入穩(wěn)定跟蹤狀態(tài)。

在以上約束的限制下，本文設(shè)計(jì)出反導(dǎo)預(yù)警作戰(zhàn)的任務(wù)分解策略，其步驟如下：

步驟1 計(jì)算所有預(yù)警資源同目標(biāo)的可見(jiàn)時(shí)間窗口。

步驟2 按可見(jiàn)時(shí)間窗口的端點(diǎn)進(jìn)行分割。找出每個(gè)可見(jiàn)時(shí)間窗口的端點(diǎn)，根據(jù)這些端點(diǎn)將整個(gè)預(yù)警任務(wù)涵蓋的時(shí)間區(qū)間進(jìn)行分割，由于每一個(gè)時(shí)間片是通過(guò)窗口的端點(diǎn)進(jìn)行劃分的，因此可以保證每個(gè)時(shí)間片對(duì)應(yīng)的可用預(yù)警資源不發(fā)生變化。

步驟3 檢查每?jī)蓚€(gè)相鄰端點(diǎn)之間的區(qū)間。如果該區(qū)間內(nèi)沒(méi)有預(yù)警資源可用，而且該區(qū)間長(zhǎng)度超過(guò)了T0，則無(wú)論采用何種任務(wù)分解策略，都會(huì)存在預(yù)警的盲區(qū)，只有增加或者重新部署預(yù)警資源，否則預(yù)警任務(wù)會(huì)失敗；如果不存在這樣的區(qū)間，則開(kāi)始預(yù)警資源的優(yōu)化調(diào)度。

預(yù)警任務(wù)經(jīng)過(guò)分解后，可以得到一系列的元任務(wù)，此時(shí)，預(yù)警資源的調(diào)度問(wèn)題就轉(zhuǎn)化為對(duì)這些元任務(wù)調(diào)度的問(wèn)題，即確定哪些元任務(wù)要執(zhí)行，如果執(zhí)行，應(yīng)該分配哪個(gè)預(yù)警資源進(jìn)行執(zhí)行。

2 調(diào)度模型

調(diào)度周期內(nèi)的每一個(gè)目標(biāo)對(duì)應(yīng)一個(gè)預(yù)警探測(cè)任務(wù)，按照反導(dǎo)預(yù)警作戰(zhàn)的任務(wù)分解策略進(jìn)行任務(wù)分解后，每個(gè)預(yù)警探測(cè)任務(wù)可以分解為多個(gè)元任務(wù)，而每個(gè)元任務(wù)都對(duì)應(yīng)著若干個(gè)可用的資源，因此，對(duì)該調(diào)度問(wèn)題存在著很多種可行的調(diào)度方案。對(duì)預(yù)警資源進(jìn)行調(diào)度并不是要找到一個(gè)可行的調(diào)度序列，而是找到能使整個(gè)系統(tǒng)調(diào)度的目標(biāo)完成得最好的調(diào)度序列。

2．1 符號(hào)說(shuō)明

為準(zhǔn)確描述反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度問(wèn)題，先定義以下一些符號(hào)：MS表示當(dāng)前所有預(yù)警探測(cè)任務(wù)的集合；NMS表示當(dāng)前預(yù)警探測(cè)任務(wù)的數(shù)量，即當(dāng)前目標(biāo)的數(shù)量；Rsc表示當(dāng)前可用預(yù)警資源的集合；NRsc表示當(dāng)前可用預(yù)警資源的數(shù)量；STsk（i）表示第i個(gè)預(yù)警探測(cè)任務(wù)經(jīng)過(guò)分解后得到的所有元任務(wù)的集合；Rsci［j］表示第i個(gè)任務(wù)的第j個(gè)元任務(wù)的可用預(yù)警資源集合；Ti表示第i個(gè)任務(wù)的持續(xù)時(shí)間；STimei［j］、ETimei［j］和Ti［j］分別表示第i個(gè)任務(wù)的第j個(gè)元任務(wù)的開(kāi)始時(shí)間、結(jié)束時(shí)間和持續(xù)時(shí)間；Pri［j］和Erri［j］分別表示第i個(gè)任務(wù)的第j個(gè)元任務(wù)的優(yōu)先權(quán)和探測(cè)精度；Err表示攔截武器系統(tǒng)要求預(yù)警系統(tǒng)提供的目標(biāo)指示精度；Benr表示預(yù)警資源r的優(yōu)先權(quán)；Nr表示資源r的最大跟蹤數(shù)量；WTr表示資源r的總計(jì)工作時(shí)長(zhǎng)；EWT表示當(dāng)前所有資源的平均工作時(shí)長(zhǎng)。

2．2 決策變量

2．3 目標(biāo)函數(shù)

反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度的目標(biāo)可以從以下3個(gè)方面進(jìn)行刻畫：

（1）從整個(gè)反導(dǎo)預(yù)警系統(tǒng)的角度來(lái)看，要盡可能提高調(diào)度產(chǎn)生的效益，即盡量多地完成優(yōu)先權(quán)高的元任務(wù)，而且盡量用優(yōu)先權(quán)高的預(yù)警資源完成。元任務(wù)的優(yōu)先權(quán)與目標(biāo)的探測(cè)精度和目標(biāo)距離落地時(shí)間有關(guān)，將其定義為

式中，ω1，ω2為目標(biāo)探測(cè)精度和距離落地時(shí)間對(duì)應(yīng)的權(quán)重，其中ω1＋ω2＝1。定義預(yù)警資源的優(yōu)先權(quán)為

于是

（2）從對(duì)每一個(gè)任務(wù)執(zhí)行的角度來(lái)看，要盡量減少目標(biāo)在不同預(yù)警資源間交接的次數(shù)，即

（3）從資源利用的角度來(lái)看，期望每個(gè)預(yù)警資源能得到最大限度的利用，同時(shí)又要盡量讓預(yù)警資源負(fù)載均衡，即

式中

2．4 約束條件

（1）預(yù)警資源的最大跟蹤目標(biāo)數(shù)量限制

（2）每個(gè)元任務(wù)只能在其備選資源集上選擇資源執(zhí)行

（

3）每個(gè)元任務(wù)只占用一個(gè)資源只被執(zhí)行一次

（4）當(dāng)時(shí)間跨度超過(guò)T0的元任務(wù)不能被成功執(zhí)行時(shí)，其后續(xù)的元任務(wù)也不能執(zhí)行

（5）當(dāng)某個(gè)元任務(wù)的持續(xù)時(shí)間小于要求的最短持續(xù)時(shí)間時(shí)，要求它與其緊前或者緊后的元任務(wù)使用同一預(yù)警資源進(jìn)行探測(cè)

3 基于粒子群－變鄰域搜索求解反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度模型

反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度問(wèn)題可以歸結(jié)為一個(gè)多目標(biāo)優(yōu)化模型，目前對(duì)于多目標(biāo)優(yōu)化模型的求解方法較多，其中，粒子群優(yōu)化（particle swarm optimization，PSO）算法在解決該類問(wèn)題上具有較大優(yōu)勢(shì)［6］。PSO算法中多個(gè)粒子同時(shí)進(jìn)行搜索，這種并行的搜索方式有助于快速地找到多目標(biāo)優(yōu)化問(wèn)題非支配解［7］，同時(shí)，PSO算法具有較強(qiáng)的通用性，對(duì)目標(biāo)函數(shù)和約束條件沒(méi)有過(guò)高的要求，而且容易與其他算法相結(jié)合，從而對(duì)自身的缺陷進(jìn)行改進(jìn)，快速有效地得到最優(yōu)解。但是，標(biāo)準(zhǔn)的PSO算法針對(duì)的是連續(xù)的實(shí)數(shù)型粒子編碼，而本文中模型的決策變量為整數(shù)變量，不能直接使用標(biāo)準(zhǔn)PSO算法中的公式對(duì)粒子位置和速度進(jìn)行更新。同時(shí)，與其他智能搜索算法一樣，PSO算法有早熟和易陷入局部最優(yōu)解的缺陷［8］。本文首先重新定義粒子的位置更新公式，然后將PSO算法與變鄰域搜索（variable neighborhood search，VNS）結(jié)合起來(lái)求解所建立的模型。

3．1 粒子編碼方式

本文建立的資源調(diào)度模型是一個(gè)多目標(biāo)整數(shù)規(guī)劃模型，如果按照離散粒子群算法常用的二進(jìn)制編碼方式進(jìn)行編碼［9］，需要判斷每個(gè)元任務(wù)與每一個(gè)可用資源之間的指派關(guān)系，從而導(dǎo)致粒子的維度巨大，嚴(yán)重影響算法的運(yùn)行效率，對(duì)此，重新設(shè)計(jì)編碼方式如下：

3．2 粒子位置更新策略

上述編碼方法簡(jiǎn)單、直接，但由于粒子在各個(gè)維度上的取值均為整數(shù)，所以不能直接使用標(biāo)準(zhǔn)粒子群算法中的公式對(duì)位置進(jìn)行更新［10］，本文對(duì)連續(xù)粒子群算法的公式進(jìn)行修改，定義位置更新公式如下：

式中，ω、c1、c2以及和gBk的定義與標(biāo)準(zhǔn)粒子群算法中相同；f1，f2和f3是操作算子。粒子位置更新公式（11）由3部分［11］組成。

（1）粒子根據(jù)自身當(dāng)前的狀態(tài)進(jìn)行調(diào)整的部分

該式的具體實(shí)現(xiàn)方法為：首先產(chǎn)生一個(gè)（0，1）之間的隨機(jī)數(shù)r，如果r＜ω，則定義ω?f1（）＝f1（），否則為。f1（）的實(shí)現(xiàn)方法為：針對(duì)粒子編碼，隨機(jī)產(chǎn)生一個(gè)1～L之間的整數(shù)a，其中L為粒子編碼長(zhǎng)度，在Xki中a位置對(duì)應(yīng)的可選預(yù)警資源中隨機(jī)選擇一個(gè)，替換原來(lái)的預(yù)警資源。

（2）粒子根據(jù)自身最優(yōu)位置pBki進(jìn)行調(diào)整的部分

該式的具體實(shí)現(xiàn)方法為：首先產(chǎn)生兩個(gè)（0，1）之間的隨機(jī)數(shù)r1和r2，如果r1＜c1，則執(zhí)行，其中采用POX（precedence preserving order based crossover）算子進(jìn)行操作［11］，首先隨機(jī)地將任務(wù)集劃分為兩個(gè)子集Q1和Q2，這兩個(gè)子集都非空；接著挑選出中與Q1有關(guān)的分量，將其復(fù)制到子代1，復(fù)制中針對(duì)任務(wù)Q1的分量到子代2，并都保持分量原來(lái)的位置順序不變；復(fù)制中針對(duì)Q2的分量到子代1，復(fù)制中針對(duì)Q2的分量到子代2，并都按照原來(lái)的位置順序進(jìn)行排列；最后選擇其中一個(gè)作為后代。如果r2＜c1，則執(zhí)行＝g（，），其中g(shù)（，）采用MPX（rand－point preservation crossover）算子進(jìn)行操作［12］，首先產(chǎn)生一個(gè)與粒子維數(shù)相等數(shù)組RA，RA中所有元素的值都為（0，1）區(qū)間內(nèi)的隨機(jī)數(shù)；接下來(lái)遍歷數(shù)組RA，若RA中的數(shù)小于p（p∈（0，1）），則記錄下相應(yīng)的位置，復(fù)制中同樣位置上的預(yù)警資源號(hào)到，這里，其中iter和gen分別為迭代次數(shù)和當(dāng)前運(yùn)行代數(shù)；利用MPX算子對(duì)g（，）進(jìn)行操作，其中p的值可以自適應(yīng)調(diào)整，從而對(duì)提高獲得最優(yōu)解的概率有一定的幫助。

（3）粒子根據(jù)全局最優(yōu)位置gBk進(jìn)行更新的部分

其中，對(duì)f3（，g）的操作與g（，p）相同。

3．3 多目標(biāo)全局搜索策略

為了避免粒子在全局搜索過(guò)程中快速趨同，引入粒子適應(yīng)度的概念。精英集中第i個(gè)粒子的適應(yīng)度的定義如下：

其中，E為精英集，而

式中，dij表示兩個(gè)粒子之間的空間距離；Rd為一個(gè)固定的值；α為調(diào)節(jié)參數(shù)。通過(guò)定義粒子的適應(yīng)度，并將其作為依據(jù)，可以對(duì)精英集中的粒子進(jìn)行篩選，從而使整個(gè)粒子群具有良好的學(xué)習(xí)信息。

3．4 多目標(biāo)局部搜索策略

采用式（11）的方式更新粒子位置時(shí)，粒子直接在離散域中進(jìn)行更新，收斂速度快，但是粒子的搜索容易出現(xiàn)停滯。對(duì)此，本文結(jié)合PSO算法與VNS算法，對(duì)局部搜索的過(guò)程進(jìn)行改進(jìn)。

VNS算法由Hansen［13］首次提出，其基本思想是：基于一定的初始解，設(shè)計(jì)若干種鄰域結(jié)構(gòu)，這些鄰域結(jié)構(gòu)產(chǎn)生的鄰域解對(duì)現(xiàn)有局部最優(yōu)解的擾動(dòng)不斷擴(kuò)大［14］，首先在第一個(gè)鄰域結(jié)構(gòu)內(nèi)搜索局部最優(yōu)解，當(dāng)這個(gè)最優(yōu)解無(wú)法得到有效更新時(shí)，改變鄰域結(jié)構(gòu)繼續(xù)搜索，直至獲得理想的最優(yōu)解或者達(dá)到最大迭代次數(shù)［15］。

對(duì)于本文所建立的反導(dǎo)預(yù)警資源調(diào)度模型，結(jié)合PSO算法，對(duì)每個(gè)局部最優(yōu)解執(zhí)行變鄰域搜索的過(guò)程為：

步驟1 初始解構(gòu)造。設(shè)定VNS算法以PSO算法最后一代群體中的部分優(yōu)秀個(gè)體極值作為初始解。

步驟2 產(chǎn)生鄰域解。根據(jù)反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度的特點(diǎn)設(shè)計(jì)3種鄰域，分別為：鄰域1是在局部最優(yōu)解對(duì)應(yīng)的調(diào)度方案中任選兩個(gè)元任務(wù)，交換他們所對(duì)應(yīng)的預(yù)警資源；鄰域2是在局部最優(yōu)解對(duì)應(yīng)的調(diào)度方案中任選兩個(gè)元任務(wù)，交換與之相鄰的兩個(gè)元任務(wù)（左或右）的對(duì)應(yīng)的預(yù)警資源；鄰域3是在局部最優(yōu)解對(duì)應(yīng)的調(diào)度方案中任選兩個(gè)元任務(wù)，交換與之相鄰的左右兩個(gè)元任務(wù)的對(duì)應(yīng)的預(yù)警資源。這3個(gè)鄰域結(jié)構(gòu)對(duì)現(xiàn)有調(diào)度方案的擾動(dòng)程度不斷變大，對(duì)于這3種鄰域的每次交換，首先要判斷交換之后是否能滿足模型中的約束條件，如果能則執(zhí)行交換；如果不能，則再次任選兩個(gè)元任務(wù)，以此為基準(zhǔn)再次進(jìn)行交換并判斷交換后能否滿足模型中的約束條件。

步驟3 局部搜索。按照鄰域1到鄰域3的順序依次選擇一種鄰域結(jié)構(gòu)，在該鄰域結(jié)構(gòu)內(nèi)采用窮舉的策略，搜索整個(gè)鄰域內(nèi)的可行解，運(yùn)用目標(biāo)函數(shù)評(píng)價(jià)局部搜索的效果，從而選取最優(yōu)解。

步驟4 當(dāng)前最優(yōu)解更新。比較原有最優(yōu)解與當(dāng)前獲得的最優(yōu)解，保留較好的一個(gè)作為當(dāng)前最優(yōu)解，并決定是否更換鄰域結(jié)構(gòu)繼續(xù)進(jìn)行搜索。

步驟5 當(dāng)任意鄰域都不能使當(dāng)前解得到進(jìn)一步的優(yōu)化時(shí)，重新選擇一個(gè)初始解，開(kāi)展新的搜索過(guò)程［16］，當(dāng)算法迭代的次數(shù)達(dá)到最大迭代次數(shù)MaxIter時(shí)，算法退出，輸出當(dāng)前最優(yōu)解。

將PSO與VNS結(jié)合起來(lái)求解預(yù)警探測(cè)任務(wù)周期重調(diào)度模型時(shí)，首先基于PSO算法得到模型的一個(gè)或多個(gè)較優(yōu)解，并將這個(gè)（些）解作為VNS算法的初始解，再進(jìn)行局部搜索得到最優(yōu)解。整個(gè)算法的具體流程如下：

步驟1 確定參數(shù)。設(shè)定粒子群中粒子的個(gè)數(shù)P，循環(huán)的代數(shù)G，進(jìn)化的周期數(shù)gen，PSO公式中的常量ω、c1和c2，VNS中的最大迭代次數(shù)MaxIter。

步驟2 種群初始化。初始化粒子群的位置為X1，X2，…，Xp。

步驟3 根據(jù)Pareto支配關(guān)系，將非支配解置入精英集中，并隨機(jī)選擇一個(gè)非支配解作為全局最優(yōu)值gB，同時(shí)，初始化局部最優(yōu)值pBi＝Xi（i＝1，2，…，P）。

步驟4 根據(jù)式（11）更新粒子位置。計(jì)算新種群中粒子的適應(yīng)度值，并更新精英集、pBi和gB。若精英集已滿，則剔除其中適應(yīng)度最小的一個(gè)粒子，并從精英集外選擇適應(yīng)度最大的粒子加入精英集。

步驟5 從所有的局部最優(yōu)解中選擇N個(gè)較優(yōu)的個(gè)體作為初始解，對(duì)每個(gè)解分別執(zhí)行VNS，同時(shí)更新粒子位置、局部最優(yōu)位置和全局最優(yōu)位置，輸出最優(yōu)解。

步驟6 若精英集連續(xù)gen代沒(méi)有改進(jìn)，則從精英集中隨機(jī)地挑選出若干個(gè)粒子替代種群中相同數(shù)量的粒子。

步驟7 若迭代的次數(shù)達(dá)到MaxIter，則輸出最優(yōu)值；否則，轉(zhuǎn)入步驟3。

這種將PSO的快速搜索能力和VNS的局部探索能力相結(jié)合的混合算法稱為粒子群－變鄰域搜索（PSO－VNS）算法。

4 仿真實(shí)例

以具體的仿真運(yùn)行為例，設(shè)置兩組不同的仿真場(chǎng)景，分別利用PSO－VNS算法、非支配排序遺傳算法（nondominatedsorting genetic algorithm，NSGA）以及多目標(biāo)粒子群優(yōu)化算法［17］（muti－objective PSO，MOPSO）對(duì)模型進(jìn)行求解，通過(guò)比較求解的結(jié)果和運(yùn)行的時(shí)間來(lái)對(duì)不同算法的性能進(jìn)行分析。兩組不同的仿真場(chǎng)景分別設(shè)定10枚（FBM＿1～FBM＿10）和20枚（FBM＿1～FBM＿20）同一型號(hào)的中遠(yuǎn)程彈道導(dǎo)彈目標(biāo)，從不同位置發(fā)射，同時(shí)攻擊某一地區(qū)。表1給出了10枚導(dǎo)彈的彈道參數(shù)（包括發(fā)落點(diǎn)的經(jīng)度和緯度、射程以及導(dǎo)彈飛行時(shí)間）。

表1 導(dǎo)彈彈道參數(shù)配置表

反導(dǎo)預(yù)警系統(tǒng)包含6部單陣面P波段遠(yuǎn)程預(yù)警雷達(dá)（P1～P6），分別部署在山東、湖南、安徽、江西、河北以及黑龍江，4部X波段多功能地基雷達(dá)（X1～X4），部署于P波段雷達(dá)周邊。表2給出了這10部預(yù)警資源對(duì)第一枚導(dǎo)彈的可見(jiàn)時(shí)間窗口。

表2 目標(biāo)1的可見(jiàn)時(shí)間窗口

多目標(biāo)優(yōu)化模型中目標(biāo)探測(cè)精度和距離落地時(shí)間對(duì)應(yīng)的權(quán)重取值ω1＝ω2＝0．5，攔截武器系統(tǒng)要求的目標(biāo)指示精度設(shè)定為Err＝300m。PSO－VNS中參數(shù)設(shè)置如下：設(shè)定種群的規(guī)模P＝20，最大循環(huán)代數(shù)G＝200，慣性常量ω＝0．9，學(xué)習(xí)因子c1＝c2＝2，精英集中解的個(gè)數(shù)N＝10，進(jìn)化停滯周期gen＝10，最大迭代次數(shù)MaxIter＝5。

在Pentium IV 2．8－GHz，內(nèi)存2GB的計(jì)算機(jī)上對(duì)每組場(chǎng)景進(jìn)行10次獨(dú)立實(shí)驗(yàn)，3種算法所獲得非支配解的數(shù)量、調(diào)度效益、任務(wù)平均交接次數(shù)、資源負(fù)載情況以及運(yùn)行時(shí)間如表3所示。非支配解的數(shù)量和運(yùn)行時(shí)間的計(jì)算方法為取10次實(shí)驗(yàn)結(jié)果的平均值；而調(diào)度效益、任務(wù)平均交接次數(shù)和資源負(fù)載的計(jì)算方法為先對(duì)每次得到的非支配解取平均，然后取10次實(shí)驗(yàn)的平均值。從實(shí)驗(yàn)結(jié)果可以看出，采用3種算法都能得到有效的調(diào)度方案，而利用本文提出的算法得到的結(jié)果在前4個(gè)指標(biāo)方面都明顯好于其他兩種算法。而且，隨著目標(biāo)數(shù)量的增加，3種算法的運(yùn)行時(shí)間都有所增加，得到的非支配解的數(shù)量有所減少，這與實(shí)際情況是吻合的。另外，與MOPSO算法的對(duì)比還可以說(shuō)明變鄰域搜索確實(shí)增強(qiáng)了算法的局部搜索性能，只是在運(yùn)行時(shí)間上有所增加，但處于可以接受的范圍以內(nèi)。

表3 不同場(chǎng)景下3種算法性能比較

5 結(jié) 論

本文對(duì)反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度問(wèn)題進(jìn)行一些探索性的研究，提出了適合反導(dǎo)預(yù)警任務(wù)分解的策略，并在此基礎(chǔ)上，建立了該問(wèn)題的模型，提出利用PSO－VNS算法求解該模型。仿真結(jié)果表明，PSO－VNS算法能夠快速地找到最優(yōu)調(diào)度方案，有效解決反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度問(wèn)題。不足的地方在于：所建立的資源調(diào)度模型還不夠完善，比如目標(biāo)在資源之間交接的約束條件沒(méi)有得到反映；同時(shí)，對(duì)兩種預(yù)警資源優(yōu)先權(quán)的賦值均為常量，沒(méi)有考慮相關(guān)因素的影響。下一步重點(diǎn)解決以下3個(gè)方面的問(wèn)題：①進(jìn)一步分析目標(biāo)交接的方式與條件，并在模型中加以反映；②分析影響預(yù)警資源優(yōu)先權(quán)的因素，并建立模型；③構(gòu)建更多的仿真場(chǎng)景，驗(yàn)證在不同場(chǎng)景下算法的性能。

［1］Du Z S，Yi X Q．Research on satellite scheduling of the spacebased early warning system［J］．Fire Control ＆Command Control，2009，34（7）：32－36．（杜占帥，易先清．天基預(yù)警系統(tǒng)資源調(diào)度方法［J］．火力與指揮控制，2009，34（7）：32－36．）

［2］Feng M Y，Tang S X，He J．Resource scheduling for spacebased early warning system based on improved particle swarm optimization［J］．Journal of China Academy of Electronics and Information Technology，2010，5（1）：97－101．（馮明月，湯紹勛，何俊．基于改進(jìn)粒子群算法的天基預(yù)警系統(tǒng)資源調(diào)度方法［J］．中國(guó)電子科學(xué)研究院學(xué)報(bào)，2010，5（1）：97－101．）

［3］Feng M Y，Li G H，Yi X Q．Sensor scheduling method for space－based early warning system［J］．Computer Engineering and Applications，2009，45（2）：225－228．（馮明月，李國(guó)輝，易先清．天基預(yù)警系統(tǒng)傳感器調(diào)度方法［J］．計(jì)算機(jī)工程與應(yīng)用，2009，45（2）：225－228．）

［4］Tang S X，Yi X Q，Luo X S．An improved particle swarm optimization algorithm for early warning satellites scheduling problems［J］．Systems Engineering，2012，30（1）：116－121．（湯紹勛，易先清，羅雪山．面向預(yù)警衛(wèi)星調(diào)度問(wèn)題的改進(jìn)粒子群算法［J］．系統(tǒng)工程，2012，30（1）：116－121．）

［5］Dong T，Liu F X，Li X．Task decomposition of terminal phrase multilayer antimissile operation［J］．Modern Defense Technology，2012，40（4）：17－20．（董濤，劉付顯，李響．末段多層反導(dǎo)作戰(zhàn)的任務(wù)分解［J］．現(xiàn)代防御技術(shù)，2012，40（4）：17－20．）

［6］Sharaf A M，El－Gammal A A A．Particle swarm optimization PSO：a new search tool in power system and electro technology［M］∥Panigrahi B K，Abraham A，Das S，ed．Computation Intelligence in Power Engineering．Berlin：Springer Verlag，2010：235－294．

［7］Lei D M．A pareto archive particle swarm optimization for multiobjective job shop scheduling［J］．The International Journal of Advanced Manufacturing Technology，2008，37（1／2）：157－165．

［8］Leong Y，Wen F，Gary G．PSO－based multi－objective optimiza－tion with dynamic population size and adaptive local archives［J］．IEEE Trans．on Systems，Man，and Cybernetics—Part B：Cybernetics，2008，38（5）：1270－1293．

［9］Cabrera J C F，Coello C A C．Handling constraints in particle swarm optimization using a small population size［C］∥Proc．of the 6th Mexican International Conference on Artificial Intelligence，2007：41－51．

［10］Alvarez－Benitez J E，Everson R M，F(xiàn)ieldsend J E．A MOPSO algorithm based exclusively on pareto dominance concepts［J］．Lecture Notes in Computer Science，2005，3410：459－473．

［11］Zhang J，Wang W L，Xu X L．Hybrid particle－swarm optimization for multi objective flexible job－shop scheduling problem［J］．Control Theory ＆Applications，2012，29（6）：715－722．（張靜，王萬(wàn)良，徐新黎．混合粒子群算法求解多目標(biāo)柔性作業(yè)車間調(diào)調(diào)度度問(wèn)題［J］．控制理論與應(yīng)用，2012，29（6）：715－722．）

［12］Tavakkoli－Moghaddam R，Azarkish M，Sadeghnejad－Barkousaraie A．A new hybrid multi－objective Pareto archive PSO algorithm for a bi－objective job shop scheduling problem［J］．Expert Systems with Applications，2011，38（9）：10812－10821．

［13］Hansen P，Mladenovic N．Variable neighborhood search：principles and applications［J］．European Journal of Operational Research，2001，130（3）：346－354．

［14］Burke E K，Li J P，Qu R．A hybrid model of integer programming and variable neighborhood search for highly－constrained nurse roistering problems［J］．European Journal of Operational Research，2010，203（2）：484－492．

［15］Chen T S，Tang K，Chen U，et al．Analysis of computational time of simple estimation of distribution algorithms［J］．IEEE Trans．on Evolutionary Computation，2010，14（1）：1－22．

［16］Polacek M，Doerner K，Hartl R．A variable neighborhood search for the capacitated arc routing problem with intermediate facilities［J］．Journal of Heuristics，2008，14（5）：405－423．

［17］Tripathi P，Bandyopad S．Multi－objective particle swarm optimization with time variant inertia and acceleration coefficients［J］．Information Sciences，2007，177（22）：5033－5049．

E－mail：xinsher＠163．com

汪厚祥（1960－），男，教授，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)應(yīng)用技術(shù)和分布式系統(tǒng)。

E－mail：hxwang＠163．com

蔡益朝（1976－），男，副教授，博士，主要研究方向?yàn)樾畔⒐芾砼c決策支持。

E－mail：cyc＠163．com

Resource scheduling method in antimissile early warning campaign

ZHAO Xin－shuang1，2，WANG Hou－xiang1，CAI Yi－chao2
（1．Space and Air Early Warning Lab，Air Force Early Warning Academy，Wuhan 430019，China；2．Electronic Engineering College，Naval University of Engineering，Wuhan 430033，China）

In order to solve the problem that several equipment detect multi－target in antimissile early warning campaign，the task decomposition strategy based on the endpoint is proposed，which is according to the characteristics of resource scheduling for antimissile early warning．A multi－objective optimization model is established based on this task decomposition strategy，and the objective of this model includes scheduling benefit，handover times and resource loading degree．By redesigning the particle encoding mode and redefinition the position updating formula in particle swarm optimization，the algorithm is suitable for solving the discrete optimization problem．Aiming at the problem of premature，a modified algorithm combining the particle swarm optimization－variable neighborhood search is presented．The experimental results show that this algorithm can resolve the problem of resource scheduling for antimissile early warning rapidly and effectively，and it has good application value．

resource scheduling；particle swarm optimization－variable neighborhood search；multi－objective optimization problem；antimissile early warning

E 844；N 945

A

10．3969／j．issn．1001－506X．2015．06．12

趙新爽（1980－），男，講師，博士，主要研究方向?yàn)橹笓]控制與優(yōu)化決策、系統(tǒng)建模與仿真。

1001－506X（2015）06－1300－06

2014－01－03；

2014－10－06；網(wǎng)絡(luò)優(yōu)先出版日期：2014－12－09。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141209．0122．007．html

國(guó)家自然科學(xué)基金（61302193）資助課題