VNS和SA相結(jié)合的指揮控制資源部署*

胡詩(shī)駿，姚佩陽(yáng)，孫昱，李鍇

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安710077）

VNS和SA相結(jié)合的指揮控制資源部署*

胡詩(shī)駿，姚佩陽(yáng)，孫昱，李鍇

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安710077）

針對(duì)指揮控制資源部署問(wèn)題，引入任務(wù)復(fù)雜度來(lái)定義決策實(shí)體的工作負(fù)載，并建立以最小化決策實(shí)體工作負(fù)載的均方根為目標(biāo)的優(yōu)化模型。針對(duì)傳統(tǒng)的層次聚類(lèi)法容易陷入局部最優(yōu)，提出了一種變鄰域搜索（Variable Neighborhood Search，VNS）和模擬退火（Simulated Annealing，SA）相結(jié)合的具有全局性的求解方法，使用VNS進(jìn)行全局尋優(yōu)，使用SA對(duì)VNS中的鄰域進(jìn)行局部尋優(yōu)。最后通過(guò)一個(gè)聯(lián)合作戰(zhàn)案例的平臺(tái)調(diào)度方案，驗(yàn)證了所提方法的優(yōu)越性。

資源部署，決策實(shí)體，任務(wù)復(fù)雜度，層次聚類(lèi)法，變鄰域搜索

0 引言

指揮控制資源部署問(wèn)題［1-2］就是依據(jù)平臺(tái)資源調(diào)度方案（即決策什么平臺(tái)在什么時(shí)間去執(zhí)行什么任務(wù)），將各個(gè)平臺(tái)進(jìn)行分組，為每一個(gè)分組配置一個(gè)決策實(shí)體，實(shí)質(zhì)上這是一個(gè)平臺(tái)聚類(lèi)問(wèn)題，也是三階段設(shè)計(jì)方法第二階段所要研究的內(nèi)容——組織協(xié)作網(wǎng)的設(shè)計(jì)。一個(gè)良好的平臺(tái)分組減少了決策實(shí)體之間不必要的交互協(xié)作，提高組織的運(yùn)作效率，反之則增加了決策實(shí)體的工作負(fù)載，降低了組織運(yùn)作效率［3］。

層次聚類(lèi)法［4］是解決指揮控制資源部署問(wèn)題的較普遍的方法。文獻(xiàn)［5］提出了基于最小化工作負(fù)載合并原則的層次聚類(lèi)法；文獻(xiàn)［6］提出了基于最小化矢量距離合并規(guī)則的層次聚類(lèi)法；文獻(xiàn)［5-6］均以所控制的平臺(tái)數(shù)量來(lái)定義內(nèi)部工作負(fù)載，以協(xié)作完成的任務(wù)數(shù)量作為外部協(xié)作負(fù)載，不能將平臺(tái)和任務(wù)兩個(gè)不同的概念經(jīng)過(guò)簡(jiǎn)單的相加來(lái)定義工作負(fù)載，對(duì)此文獻(xiàn)［7］以任務(wù)的執(zhí)行時(shí)間來(lái)衡量工作負(fù)載，設(shè)計(jì)了N-best備選策略來(lái)減小搜索空間，提出了基于最小化工作負(fù)載均方根的改進(jìn)層次聚類(lèi)法。層次聚類(lèi)法都是以某種規(guī)則進(jìn)行層次遞進(jìn)式的兩兩合并，產(chǎn)生的解是短視的，不一定能獲得全局最優(yōu)解。

本文引入任務(wù)復(fù)雜度來(lái)重新定義工作負(fù)載，并且針對(duì)層次聚類(lèi)法的短視性，引入變鄰域搜索［8-9］和模擬退火算法［10-11］這兩種全局性算法，獲得所求解問(wèn)題的最優(yōu)解。

1 問(wèn)題的數(shù)學(xué)描述

1.1 基本概念

①?zèng)Q策實(shí)體（Decision-makers，DM）：聯(lián)合作戰(zhàn)的指揮官，通過(guò)所控制的平臺(tái)資源來(lái)完成作戰(zhàn)任務(wù)，其集合記為DM={DM1，DM2，…，DMD}，D為可配置的決策實(shí)體數(shù)目。

②平臺(tái)（Platform，P）：決策實(shí)體所控制的物力資源實(shí)體，記平臺(tái)集為P={P1，P2，…，PQ}，Q為平臺(tái)的數(shù)目。

③任務(wù)（Task，T）：部隊(duì)為完成預(yù)定的作戰(zhàn)目的所執(zhí)行的任務(wù)，由作戰(zhàn)使命分解形成，通常由決策實(shí)體控制的平臺(tái)資源協(xié)作完成，記任務(wù)集T={T1，T2，…，TN}，N為任務(wù)數(shù)量。任務(wù)Tn所需要的資源能力需求Pren=（Rn1，Rn2，…，RnL），Rnl［11］（l=1，2，…，L）是指成功執(zhí)行Tn所需第l種資源能力的大??；任務(wù)激烈度［12］Sdn，即任務(wù)對(duì)抗的激烈程度，通常Sdk∈{0，1，2，3，4，5，6，7，8，9}。

④組織協(xié)作網(wǎng)：如圖1所示，以?xún)蓚€(gè)決策實(shí)體、5個(gè)平臺(tái)和兩個(gè)作戰(zhàn)任務(wù)的指揮控制組織來(lái)直觀地認(rèn)識(shí)組織協(xié)作網(wǎng)。

圖1 組織協(xié)作網(wǎng)

1.2 變量定義

①平臺(tái)-任務(wù)分配矩陣PT。即若平臺(tái)Pm被分配執(zhí)行任務(wù)Tn，則PTm×n=1；否則PTm×n=0。該矩陣已由平臺(tái)資源調(diào)度問(wèn)題［12］求出，在指揮控制資源部署問(wèn)題中是輸入變量。

②平臺(tái)-決策實(shí)體聚類(lèi)矩陣PDM。即若決策實(shí)體DMd控制平臺(tái)Pm，則PDMm×d=1；否則PDMm×d=0。該矩陣也是本文所要求解的矩陣。

③任務(wù)-決策實(shí)體分配矩陣TDM。即若決策實(shí)體DMd協(xié)作完成任務(wù)Tn，則TDMn×d=1；否則TDMn×d=0。

④決策實(shí)體之間的協(xié)作變量COdbn。即若決策實(shí)體DMd和決策實(shí)體DMb協(xié)作完成任務(wù)Tn，則COdbn=1；否則COdbn=0。

1.3 決策實(shí)體的工作負(fù)載定義

決策實(shí)體的工作負(fù)載由兩部分組成，即內(nèi)部工作負(fù)載和外部協(xié)作負(fù)載。內(nèi)部工作負(fù)載是決策實(shí)體控制的平臺(tái)資源來(lái)完成任務(wù)產(chǎn)生的工作負(fù)載，外部協(xié)作負(fù)載是決策實(shí)體之間協(xié)作完成某一任務(wù)產(chǎn)生的工作負(fù)載。在以往的決策實(shí)體工作負(fù)載定義時(shí)，通常將決策實(shí)體控制的平臺(tái)資源數(shù)量作為內(nèi)部負(fù)載，將協(xié)作完成的任務(wù)數(shù)作為外部協(xié)作負(fù)載，以?xún)烧叩暮?jiǎn)單相加作為總的工作負(fù)載。這種定義方式簡(jiǎn)單地將平臺(tái)和任務(wù)這兩個(gè)不相關(guān)的概念相加，無(wú)法真正反映決策實(shí)體的工作負(fù)載。

本文考慮到任務(wù)的激烈程度、執(zhí)行時(shí)間及功能需求3個(gè)方面因素對(duì)決策實(shí)體工作負(fù)載的影響，定義任務(wù)的復(fù)雜度作為負(fù)載的測(cè)度。記任務(wù)Tn的復(fù)雜度為CxDn，其定義如下：

其中，Sdn為任務(wù)Tn的激烈度，TSn為任務(wù)Tn的執(zhí)行時(shí)間因素，PrSn為任務(wù)Tn的功能需求因素。

任務(wù)Tn的執(zhí)行時(shí)間因素定義為任務(wù)Tn的執(zhí)行時(shí)間與整個(gè)使命完成時(shí)間的比值，即

其中，tn為任務(wù)Tn的執(zhí)行時(shí)間，tsum為整個(gè)使命的完成時(shí)間。

任務(wù)Tn的功能需求因素定義為任務(wù)Tn的資源能力需求中的各項(xiàng)能力與完成整個(gè)使命所需該項(xiàng)能力比值的均值，即

1.3.1 決策實(shí)體的內(nèi)部工作負(fù)載

決策實(shí)體DMd通過(guò)所控制平臺(tái)完成任務(wù)產(chǎn)生的工作負(fù)載定義為其內(nèi)部工作負(fù)載，記為，即

1.3.2 決策實(shí)體的外部協(xié)作負(fù)載

決策實(shí)體DMd與其他決策實(shí)體協(xié)作完成任務(wù)產(chǎn)生的工作負(fù)載定義為其外部協(xié)作負(fù)載，記為，即

1.3.3 決策實(shí)體的工作負(fù)載

決策實(shí)體DMd的工作負(fù)載定義為其內(nèi)部工作負(fù)載與外部協(xié)作負(fù)載的加權(quán)和，記為，即：

其中，Wi為內(nèi)部工作負(fù)載的權(quán)重，Wo為外部協(xié)作負(fù)載的權(quán)重。

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

①?zèng)Q策實(shí)體可以控制多個(gè)平臺(tái)，但某個(gè)平臺(tái)只能是受某個(gè)決策實(shí)體控制，即：

②每個(gè)決策實(shí)體都至少控制一個(gè)平臺(tái)資源，否則沒(méi)有存在意義，即：

③只有當(dāng)TDMn×d=1且TDMn×b=1時(shí)，COdbn=1。由此可得：

綜合式（9）和式（10）可得：

④指揮控制資源部署設(shè)計(jì)的目標(biāo)主要是在減小整個(gè)C2組織總工作負(fù)載的同時(shí)，兼顧各個(gè)決策實(shí)體的工作負(fù)載盡可能差異小。本文采用所有決策實(shí)體工作負(fù)載的均方根作為目標(biāo)函數(shù)的測(cè)度，則目標(biāo)函數(shù)為：

綜合以上分析，指揮控制資源部署問(wèn)題的數(shù)學(xué)模型如下：

2 問(wèn)題求解

針對(duì)式（8）所描述的數(shù)學(xué)模型，采用在變鄰域搜索方法中嵌入模擬退火算法來(lái)求解指揮控制資源部署問(wèn)題，其流程圖如圖2所示。

2.1 變鄰域搜索算法

變鄰域搜索算法的基本思路如圖3所示。

圖3 VNS的基本思路圖

由上圖可以直觀地發(fā)現(xiàn)變鄰域搜索正是通過(guò)鄰域的擴(kuò)展來(lái)進(jìn)行全局搜索，達(dá)到全局最優(yōu)。VNS算法的具體步驟如下：

Step1初始化。設(shè)計(jì)一組鄰域結(jié)構(gòu)Nk（k=1，2，…，Nmax），隨機(jī)生成一個(gè)初始解x；

Step2令迭代計(jì)數(shù)器i=1，直至i＞M；

Step3令k=1，直至k=Nmax；

Step3.1擾動(dòng)產(chǎn)生的x第k個(gè)鄰域中的一個(gè)點(diǎn)xl；

Step3.2找出點(diǎn)xl周?chē)木植孔顑?yōu)解點(diǎn)xb；

Step3.3解更新。若局部最優(yōu)解優(yōu)于當(dāng)前解，則令x=xb，k=1，轉(zhuǎn)Step3；否則k=k+1；

Step4令i=i+1，轉(zhuǎn)Step2。

2.1.1 初始解構(gòu)造

針對(duì)設(shè)置的D個(gè)決策實(shí)體，Q個(gè)平臺(tái)資源，隨機(jī)產(chǎn)生Q個(gè)1～D之間的隨機(jī)整數(shù)，組成一組排列數(shù)作為初始解x，即（x1，x2，…，xk，…，xQ）。

由于產(chǎn)生的隨機(jī)數(shù)可能存在不可行解，會(huì)產(chǎn)生很多不必要的搜索，為了縮小搜索空間，提出如下修正策略：

Step1初始化。令D個(gè)決策實(shí)體控制的平臺(tái)資源數(shù)目分別為y1，y2，…，yD，并設(shè)初始所有決策實(shí)體控制數(shù)目均為0，令i=1，k=1；

Step2若xk=yi，則yi=yi+1，k=k+1；否則k=k+1；

Step3若k＞Q+1，則i=i+1，轉(zhuǎn)Step4；否則轉(zhuǎn)Step2；

Step4若i＞D+1，則轉(zhuǎn)Step5；否則轉(zhuǎn)Step2；

Step5令a=1；

Step6若ya=0，從決策實(shí)體控制數(shù)目不為0對(duì)應(yīng)的初始解x中的位置用a取代原先的值，a=a+1；否則a=a+1；

Step7若a＞D+1，則轉(zhuǎn)Step8；否則轉(zhuǎn)Step6；

Step8輸出新的初始解x'。

2.1.2 鄰域構(gòu)造

擾動(dòng)機(jī)制的設(shè)計(jì)也就是鄰域結(jié)構(gòu)的構(gòu)造，本文引入遺傳中變異、交叉的思想來(lái)構(gòu)建兩種可供隨機(jī)選擇的鄰域結(jié)構(gòu)：變異鄰域和交叉鄰域。

變異鄰域就是在當(dāng)前解中隨機(jī)一個(gè)位于1～Q之間的數(shù)作為需要變異的位置，然后隨機(jī)一個(gè)位于1～D之間的數(shù)取代該位置原先的值，如此產(chǎn)生的解集，如圖4所示。

圖4 變異鄰域圖

交叉鄰域就是在當(dāng)前解中隨機(jī)出兩個(gè)不同的位于1～Q之間的數(shù)作為待交叉的兩個(gè)位置，將這兩個(gè)位置的值進(jìn)行互換，如此產(chǎn)生的解集，如圖5所示。

圖5 交叉鄰域圖

2.1.3 基于模擬退火的局部搜索

本章變鄰域搜索算法采用模擬退火進(jìn)行局部搜索，不僅能獲得局部最優(yōu)解，還能一定程度跳出局部最優(yōu)，其步驟如下：

Step1變鄰域搜索中求得的xk作為模擬退火的初始解，設(shè)置初始溫度T0、終止溫度Tf、溫度更新參數(shù)a、Markov鏈長(zhǎng)度為M，令T=T0，i=1，局部最優(yōu)解xl=xk；

Step2由解xl擾動(dòng)產(chǎn)生新解xn，令B=TF（xn）-TF（xk），若B＜0，則xk=xn；否則按一定概率準(zhǔn)則接受xn為當(dāng)前解；

Step3C=TF（xn）-TF（xl），若C＜0，則xl=xn；

Step4令i=i+1，直至i＞M，轉(zhuǎn)Step2；

Step5令T=aT，直至T＞Tf，轉(zhuǎn)Step2。

1）擾動(dòng)機(jī)制

采用遺傳中變異的思想進(jìn)行擾動(dòng)產(chǎn)生新解，與變鄰域搜索鄰域構(gòu)造中的第一個(gè)變異鄰域相同。

2）概率準(zhǔn)則

對(duì)于T溫度下解xl擾動(dòng)產(chǎn)生新解xn，令B=TF（xn）-TF（xk），若B＜0，則xk=xn；否則按式（14）準(zhǔn)則接受xn為當(dāng)前解。

2.1.4 劣解接受準(zhǔn)則

圖2中，當(dāng)TF（xl）＜TF（x）不滿(mǎn)足時(shí)，此時(shí)按如下解接受準(zhǔn)則接受劣解，以防止變鄰域搜索過(guò)早陷入局部最優(yōu)。

其中，i為圖2中的迭代計(jì)數(shù)器。

3 算例分析

為了驗(yàn)證所提方法的優(yōu)越性，以文獻(xiàn)［3］中的聯(lián)合登島作戰(zhàn)為例，以其中的一個(gè)平臺(tái)調(diào)度方案為輸入，取各個(gè)任務(wù)對(duì)抗的激烈程度為Sdn=1（n=1，2，…，18），進(jìn)行仿真實(shí)驗(yàn)，平臺(tái)調(diào)度方案如下頁(yè)圖6所示。

仿真實(shí)驗(yàn)1當(dāng)Wi=0.4，Wo=0.6，決策實(shí)體數(shù)目為D=6時(shí)，分別使用基于最小矢量距離的層次聚類(lèi)法、基于N-best備選策略合并規(guī)則的層次聚類(lèi)法和本文提出的方法進(jìn)行算例求解，其結(jié)果如下頁(yè)表1所示。

從表1中可以看出，本文所提的VNS和SA相結(jié)合的平臺(tái)聚類(lèi)方法比基于矢量距離的層次聚類(lèi)法、基于N-best備選策略的層次聚類(lèi)法的結(jié)果都要好，總的工作負(fù)載更小，同時(shí)各決策實(shí)體的工作負(fù)載比較均衡。

圖6 平臺(tái)資源調(diào)度方案甘特圖

表1 3種不同方法的平臺(tái)聚類(lèi)結(jié)果

仿真實(shí)驗(yàn)2當(dāng)Wi=0.4，Wo=0.6，決策實(shí)體數(shù)目D取1～15時(shí)，分別使用基于最小矢量距離的層次聚類(lèi)法、基于N-best備選策略合并規(guī)則的層次聚類(lèi)法和本文提出的方法進(jìn)行算例求解，其結(jié)果如圖7所示。

圖7 3種算法均方根隨決策實(shí)體數(shù)目變化曲線

由圖7可知，隨著決策實(shí)體數(shù)目D的變化，VNS和SA相結(jié)合的平臺(tái)聚類(lèi)方法所求得的結(jié)果中各決策實(shí)體工作負(fù)載的均方根值都要比基于最小矢量距離的層次聚類(lèi)法和基于N-best備選策略合并規(guī)則的層次聚類(lèi)法所求出的值小，也就是說(shuō)本文采用的方法總工作負(fù)載較小，同時(shí)各決策實(shí)體工作負(fù)載更加均衡。同時(shí)，對(duì)于決策實(shí)體大于9時(shí)，基于N-best備選策略合并規(guī)則的層次聚類(lèi)法的效果相對(duì)來(lái)說(shuō)反而更差，而本文設(shè)計(jì)方法始終能找到更好的解。

仿真實(shí)驗(yàn)3當(dāng)決策實(shí)體數(shù)目為D=6，在0.05到0.5之間取不同值時(shí)，分別使用基于最小矢量距離的層次聚類(lèi)法、基于N-best備選策略合并規(guī)則的層次聚類(lèi)法和本文提出的方法進(jìn)行算例求解，其結(jié)果如圖8所示。

圖8 3種算法均方根隨內(nèi)部工作負(fù)載變化曲線

圖8中，內(nèi)部工作負(fù)載Wi從0.05以0.05的間隔逐漸增加到0.5，可以看出當(dāng)內(nèi)部工作負(fù)載權(quán)重逐漸增大的情況下，外部協(xié)作負(fù)載權(quán)重逐漸減小，相對(duì)于基于矢量距離的層次聚類(lèi)法，后兩種方法有較大的優(yōu)勢(shì)，但優(yōu)勢(shì)越來(lái)越不明顯。這是因?yàn)榭偟膬?nèi)部工作負(fù)載都是相同的，通過(guò)減小外部協(xié)作負(fù)載來(lái)實(shí)現(xiàn)平臺(tái)聚類(lèi)優(yōu)化。因此，隨著外部協(xié)作負(fù)載的權(quán)重越來(lái)越小，后兩種效果也隨之不明顯。同時(shí)，本文設(shè)計(jì)的全局性的VNS和SA相結(jié)合的平臺(tái)聚類(lèi)方法在效果上始終優(yōu)于基于N-best備選策略合并規(guī)則的層次聚類(lèi)法。

4 結(jié)論

指揮控制資源部署問(wèn)題作為三階段設(shè)計(jì)方法的第二階段，是指揮控制組織設(shè)計(jì)中的重要工作之一。本文通過(guò)引入任務(wù)復(fù)雜度進(jìn)行工作負(fù)載的定義，建立以最小化所有決策實(shí)體的均方根為目標(biāo)函數(shù)的數(shù)學(xué)模型，同時(shí)提出了一種VNS和SA相結(jié)合的具有全局性的問(wèn)題求解方法。針對(duì)聯(lián)合登島作戰(zhàn)案例中的一個(gè)平臺(tái)調(diào)度方案進(jìn)行了實(shí)驗(yàn)仿真，仿真結(jié)果驗(yàn)證了所提方法的優(yōu)越性。

［1］BUI H，HAN X，MANDAL S，et al.Optimization-based decision support algorithms for a team-in-the-loop planning experiment［C］//Proceedings of the 2009 IEEE International Conference on Systems，Man，and Cybernetics.TX：IEEE Press，2009：4684-4689.

［2］YAN J J，DUANMU Z Y，ZHOU X M，et al.A plan-driven dynamic reconfiguration mechanism for C2 communities ofinterest［C］//Proceedings of the 15th International Command and Control Research and Technology Symposium，2010.

［3］陽(yáng)東升，張維明，劉忠，等.指控組織設(shè)計(jì)方法［M］.北京：國(guó)防工業(yè)出版社，2010.

［4］KASHEF R，KAMEL M S.Cooperative clustering［J］.Pattern Recognition，2010，43（6）：2315-2329.

［5］LEVCHUK G M，LEVCHUK Y N，LUO J，et al.Normative design of organizations-PartII：Organizational structure［J］. IEEE Transactions on Systems，Man，and Cybernetics—Part A：Systems and Humans，2002，32（3）：360-375.

［6］劉宏芳，陽(yáng)東升，劉忠，等.兵力編成裁剪算法研究：決策結(jié)點(diǎn)裁剪［J］.系統(tǒng)工程理論與實(shí)踐，2007，27（5）：106-112.

［7］周翔翔，姚佩陽(yáng)，王欣.基于改進(jìn)層次聚類(lèi)法的指揮控制資源部署［J］.系統(tǒng)工程與電子技術(shù)，2012，34（3）：523-528.

［8］BOUHMALA N，HJELMERVIK K，VERGAARD K I.A generalized variable neighborhood search for combinatorial optimization problems［J］.Electronic Notes in Discrete Mathematics，2015，32（3）：360-375.

［9］董紅宇，黃敏，王興偉，等.變鄰域搜索算法綜述［J］.控制工程，2009，16（S2）：1-5.

［10］SUMAN B，KUMAR P.A survey of simulated annealing as a tool for single and multiobjective optimization［J］.Journal of theOperationalResearchSociety，2006，57（10）：1143-1160（18）.

［11］朱顥東，鐘勇.一種改進(jìn)的模擬退火算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（6）：32-35.

［12］李小全，詹海洋，程懿.面向任務(wù)的炮兵指揮控制建模仿真［J］.火力與指揮控制，2014，39（8）：34-37.

［13］胡詩(shī)駿，姚佩陽(yáng)，孫昱，等.DLA和NGA結(jié)合的平臺(tái)資源調(diào)度方法［J］.空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，16（2）：82-86.

Command and Control Resource Deployment Based on VNS and SA

HU Shi-jun，YAO Pei-yang，SUN Yu，LI Kai
（School of Information and Navigation，Air Force Engineering University，Xi’an 710077，China）

To solve the command and control resource deployment problem，the complexity of a task is introduced to measure decision-makers’workload and a mathematical model whose objective function features the minimization of root mean square value of the decision-makers’workload is built. Aimed at the hierarchical clustering algorithm that is liable to plunge into local optimum，this paper presents an approach with overall importance to solve the problem based on Variable Neighborhood Search（VNS）and Simulated Annealing（SA）.VNS is used to find out global optimum with using SA to find local optimum in the neighborhood.Finally，the superiority of this algorithm are illuminated through a platform resource scheduling scheme which is in a case of joint campaign.

resource deployment，decision-makers，complexity of a task，hierarchical clustering algorithm，variable neighborhood search

TP391.9

A

1002-0640（2016）12-0020-05

2015-10-07

2015-12-13

國(guó)家自然科學(xué)基金資助項(xiàng)目（61573017）

胡詩(shī)駿（1990-），男，浙江杭州人，碩士研究生。研究方向：組織結(jié)構(gòu)模型設(shè)計(jì)。