基于rollout策略下的決策實(shí)體配置問(wèn)題求解方法

廖夢(mèng)琛, 孫 鵬,2, 張杰勇, 武君勝

(1. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077; 2. 西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,陜西 西安 710077;3. 西北工業(yè)大學(xué)軟件與微電子學(xué)院, 陜西 西安 710077)

0 引 言

在信息化軍事對(duì)抗中,如何建立戰(zhàn)場(chǎng)環(huán)境下平臺(tái)資源、作戰(zhàn)任務(wù)、決策實(shí)體三者之間的關(guān)系是指揮控制(command and control, C2)組織設(shè)計(jì)中的關(guān)鍵問(wèn)題[1-4]。當(dāng)平臺(tái)-任務(wù)匹配關(guān)系生成后,大量的平臺(tái)資源將通過(guò)一定的規(guī)則和方法劃分給有限個(gè)決策實(shí)體,建立平臺(tái)與決策實(shí)體之間的配置關(guān)系RDM-P,這種關(guān)系的構(gòu)建過(guò)程實(shí)質(zhì)上是平臺(tái)資源的聚類過(guò)程[5-6],也就是C2組織三階段設(shè)計(jì)方法[7]中的第二階段設(shè)計(jì)內(nèi)容。

在平臺(tái)聚類問(wèn)題中,高效、準(zhǔn)確的決策實(shí)體與平臺(tái)之間的指揮控制關(guān)系是確保敵我對(duì)抗過(guò)程中取得優(yōu)勢(shì)的關(guān)鍵因素。文獻(xiàn)[8]以最小化決策實(shí)體的最大工作負(fù)載為目標(biāo)函數(shù)建立了數(shù)學(xué)模型,從平臺(tái)、任務(wù)數(shù)量的角度衡量工作負(fù)載,并提出了基于最小工作負(fù)載的合并準(zhǔn)則。文獻(xiàn)[9]進(jìn)一步研究了每層聚類的合并規(guī)則,定義了平臺(tái)分組之間的矢量距離,提出了基于最小矢量距離的合并規(guī)則。文獻(xiàn)[10]以作戰(zhàn)任務(wù)的執(zhí)行時(shí)間作為決策實(shí)體工作負(fù)載的測(cè)度標(biāo)準(zhǔn),建立了以工作負(fù)載的最小均方根(root mean square,RMS)值為目標(biāo)函數(shù)的數(shù)學(xué)模型,利用層次聚類法求解了該問(wèn)題。文獻(xiàn)[11]定義了指控復(fù)雜度,利用自適應(yīng)量子遺傳算法生成平臺(tái)聚類方案。文獻(xiàn)[12]從多個(gè)方面考慮工作負(fù)載的測(cè)度建立了多目標(biāo)優(yōu)化模型,通過(guò)對(duì)一系列前沿解的篩選得到符合要求的聚類方案。

層次聚類法是平臺(tái)與決策實(shí)體配置關(guān)系設(shè)計(jì)的主要方法,考慮到采用傳統(tǒng)層次聚類法在合并過(guò)程中采用了貪婪策略,即每一層的合并過(guò)程都選擇當(dāng)前層的最優(yōu)合并方案,并未從全局的角度考慮解的最優(yōu)性,得到的最終聚類方案可能不是全局最優(yōu)方案。因此,本文將采用rollout策略對(duì)層次聚類法進(jìn)行改進(jìn)優(yōu)化,以作戰(zhàn)任務(wù)的執(zhí)行時(shí)間作為決策實(shí)體工作負(fù)載的測(cè)度標(biāo)準(zhǔn),建立平臺(tái)與決策實(shí)體配置問(wèn)題的數(shù)學(xué)模型,以工作負(fù)載的最小RMS值為模型目標(biāo)函數(shù),在平臺(tái)合并過(guò)程中采用基于最小RMS合并準(zhǔn)則并使用rollout策略下的層次聚類法以對(duì)該問(wèn)題進(jìn)行求解,通過(guò)仿真算例說(shuō)明該方法能夠降低工作負(fù)載的RMS值,并且能均衡每個(gè)決策實(shí)體之間的工作負(fù)載,驗(yàn)證了該方法的適用性,并通過(guò)和傳統(tǒng)層次聚類法的對(duì)比分析驗(yàn)證了該方法的優(yōu)越性。

1 問(wèn)題描述及建模

1.1 變量定義

戰(zhàn)場(chǎng)環(huán)境中,所有被用于作戰(zhàn)的平臺(tái)資源將被決策實(shí)體DMm控制和指揮,決策實(shí)體作為戰(zhàn)場(chǎng)要素中的核心要素,負(fù)責(zé)控制平臺(tái)Pj完成相應(yīng)的作戰(zhàn)任務(wù)Ti。平臺(tái)與決策實(shí)體配置關(guān)系的構(gòu)建的實(shí)質(zhì)就是平臺(tái)聚類問(wèn)題。對(duì)平臺(tái)聚類問(wèn)題進(jìn)行數(shù)學(xué)描述和建模,首先對(duì)變量作如下定義。

定義1任務(wù)與平臺(tái)的分配變量ωij(i=1,2,…,I;j=1,2,…,J):如果任務(wù)Ti被分配給平臺(tái)Pj執(zhí)行,則ωij=1,否則ωij=0。在平臺(tái)與決策實(shí)體關(guān)系設(shè)計(jì)階段,任務(wù)與平臺(tái)的分配關(guān)系作為該問(wèn)題的輸入信息,因此分配變量為已知量。

定義2平臺(tái)與決策實(shí)體的配置變量xmj(j=1,2,…,J;m=1,2,…,D):平臺(tái)需要在決策實(shí)體的指揮控制下才能執(zhí)行既定作戰(zhàn)任務(wù),當(dāng)平臺(tái)Pj隸屬于決策實(shí)體DMm時(shí),xmj=1,否則xmj=0。

定義3任務(wù)與決策實(shí)體的分配變量umi(i=1,2,…,I;m=1,2,…,D):當(dāng)平臺(tái)與決策實(shí)體的配置關(guān)系生成后,決策實(shí)體繼承了平臺(tái)對(duì)任務(wù)的執(zhí)行關(guān)系,即平臺(tái)Pj被分配執(zhí)行任務(wù)Ti,當(dāng)Pj隸屬于決策實(shí)體DMm時(shí),決策實(shí)體DMm即執(zhí)行任務(wù)Ti,umi=1,否則umi=0。

定義4決策實(shí)體在任務(wù)中的協(xié)作變量ymni(m,n=1,2,…,D,m≠n;i=1,2,…,I):當(dāng)決策實(shí)體DMm與DMn共同執(zhí)行任務(wù)Ti時(shí),ymni=1,否則ymni=0。

1.2 約束條件分析

(1) 任何一個(gè)平臺(tái)P有且只有一個(gè)決策實(shí)體DMm對(duì)其進(jìn)行控制,即不存在多個(gè)決策實(shí)體控制同一個(gè)平臺(tái)的情況,同時(shí)配置給任意一個(gè)平臺(tái)的決策實(shí)體數(shù)量都不為0,描述為

(1)

(2) 每個(gè)決策實(shí)體至少控制一個(gè)平臺(tái),即

(2)

(3) 對(duì)于每個(gè)決策實(shí)體而言,DMm控制的每一個(gè)平臺(tái)均只執(zhí)行該平臺(tái)分配到的任務(wù),隸屬于同一決策實(shí)體的不同平臺(tái)之間的任務(wù)互不影響,即

umi≥ωij·xmj

i=1,2,…,I;j=1,2,…,J;m=1,2,…,D

(3)

已知當(dāng)ymni=1時(shí)，表明決策實(shí)體DMm和DMn在任務(wù)Ti上存在協(xié)作,可以得到協(xié)作變量ymni與分配變量umi和uni之間的關(guān)系為

ymni=min(umi,uni),m≠n;i=1,2,…,I

(4)

1.3 決策實(shí)體配置問(wèn)題的目標(biāo)函數(shù)和模型建立

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

決策實(shí)體的工作負(fù)載反應(yīng)了隸屬于該決策實(shí)體的平臺(tái)資源對(duì)作戰(zhàn)任務(wù)的執(zhí)行情況。在考慮決策實(shí)體的工作負(fù)載時(shí),選擇以面向作戰(zhàn)任務(wù)的形式,將作戰(zhàn)任務(wù)的執(zhí)行時(shí)間作為工作負(fù)載的測(cè)度標(biāo)準(zhǔn),從內(nèi)部工作負(fù)載I(m)和外部工作負(fù)載E(m)兩個(gè)方面對(duì)工作負(fù)載進(jìn)行描述[8]。

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

決策實(shí)體的內(nèi)部負(fù)載表示決策實(shí)體控制的平臺(tái)所承擔(dān)的工作負(fù)載,數(shù)值上表示為所控制平臺(tái)處理的全部作戰(zhàn)任務(wù)的時(shí)間之和,即

(5)

式中,ti為任務(wù)Ti的執(zhí)行時(shí)間。

(2) 決策實(shí)體DMm的外部工作負(fù)載E(m)

決策實(shí)體的外部工作負(fù)載表示決策實(shí)體所控制的平臺(tái)和其他決策實(shí)體協(xié)作處理任務(wù)時(shí)承擔(dān)的工作負(fù)載,數(shù)值上表示為與其他不屬于該決策實(shí)體的平臺(tái)協(xié)作執(zhí)行的全部作戰(zhàn)任務(wù)的時(shí)間之和,即

(6)

式中,R(m,n)表示決策實(shí)體DMm與DMn協(xié)作處理作戰(zhàn)任務(wù)的時(shí)間之和

n=1,2,…,D;m≠n

(7)

結(jié)合式(6)、式(7),決策實(shí)體的外部工作負(fù)載可以表示為

(8)

(3) 總工作負(fù)載CW(m)

決策實(shí)體的總工作負(fù)載以內(nèi)部工作負(fù)載I(m)與外部工作負(fù)載E(m)加權(quán)和的形式表示,即

CW(m)=WI·I(m)+WE·E(m)

(9)

式中,WI表示內(nèi)部工作負(fù)載權(quán)重；WE表示外部工作負(fù)載權(quán)重。WI和WE分別表示對(duì)總工作負(fù)載的影響程度。一般地,取WI=WE=1。

1.3.2 目標(biāo)函數(shù)的構(gòu)造

在平臺(tái)與決策實(shí)體配置問(wèn)題中,已知的輸入信息為平臺(tái)-任務(wù)的調(diào)度關(guān)系,當(dāng)平臺(tái)-任務(wù)的調(diào)度方案生成后,初始的決策實(shí)體工作負(fù)載的內(nèi)部負(fù)載部分將不再發(fā)生變化,因此對(duì)于該平臺(tái)聚類過(guò)程實(shí)質(zhì)上就是最小化外部工作負(fù)載的過(guò)程。

由于每個(gè)決策實(shí)體的能力有限,如何對(duì)平臺(tái)進(jìn)行合理地分組、將分組的平臺(tái)配置給有限數(shù)量的決策實(shí)體,是實(shí)現(xiàn)決策實(shí)體對(duì)平臺(tái)的指揮控制的關(guān)鍵。在這一問(wèn)題中,一方面要求所有決策實(shí)體的平均工作負(fù)載盡可能小,另一方面要求所有決策實(shí)體的工作負(fù)載盡可能均衡。因此,目標(biāo)函數(shù)從均值和方差兩個(gè)方面進(jìn)行描述:

(1) 工作負(fù)載的均值

(10)

式中,D表示決策實(shí)體的個(gè)數(shù),對(duì)于該問(wèn)題的目標(biāo)函數(shù)而言,工作負(fù)載的均值μ越小越好。

(2) 工作負(fù)載的方差

(11)

工作負(fù)載的方差σ2體現(xiàn)了每個(gè)決策實(shí)體工作負(fù)載的差異,因此對(duì)于該問(wèn)題工作負(fù)載之間的方差σ2越小，表示每個(gè)決策實(shí)體的工作負(fù)載越均衡。

因此,決策實(shí)體工作負(fù)載的RMS可以表示為

(12)

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

由式(12)可知,工作負(fù)載的RMS值綜合了工作負(fù)載的均值和方差兩個(gè)方面，充分體現(xiàn)了每個(gè)決策實(shí)體工作負(fù)載的水平,因此,本文構(gòu)建的平臺(tái)與決策實(shí)體配置問(wèn)題的數(shù)學(xué)模型為

(13)

2 基于rollout策略下的層次聚類法求解方法

2.1 rollout策略

平臺(tái)聚類的問(wèn)題即將不同的平臺(tái)分配給一定數(shù)量的決策實(shí)體,由決策實(shí)體控制各個(gè)平臺(tái)執(zhí)行既定的作戰(zhàn)任務(wù)。在聚類過(guò)程中,要在滿足問(wèn)題約束條件的同時(shí)得到符合問(wèn)題模型目標(biāo)函數(shù)的最優(yōu)解,因此平臺(tái)聚類方案體現(xiàn)了所設(shè)計(jì)的平臺(tái)與決策實(shí)體之間配置關(guān)系的合理性。使用層次聚類法實(shí)現(xiàn)平臺(tái)聚類的過(guò)程可以描述為:將當(dāng)前的J個(gè)平臺(tái)按照某一合并規(guī)則進(jìn)行合并,選擇合并后使目標(biāo)函數(shù)值滿足問(wèn)題模型的需求的兩個(gè)平臺(tái)進(jìn)行合并,逐層合并直至平臺(tái)個(gè)數(shù)J與決策實(shí)體數(shù)量D相同時(shí)合并結(jié)束。

傳統(tǒng)的層次聚類方法在逐層合并的過(guò)程中均采用了貪婪策略,最終形成決策實(shí)體與平臺(tái)的指揮關(guān)系。然而,這種每層合并都基于貪婪策略的解只考慮了當(dāng)前層的最優(yōu)性,得到的最終聚類結(jié)果可能不是全局最優(yōu)解。為了改善最終聚類結(jié)果的性能和效果,本文將采用rollout策略[13-15]對(duì)層次聚類法的合并過(guò)程進(jìn)行改進(jìn)?；趓ollout策略改進(jìn)的層次聚類法的基本思想是:每一層生成m個(gè)備選合并方案,這些方案按照目標(biāo)函數(shù)值大小排序,令當(dāng)前層的合并方案分別為1,2,…,m,后續(xù)的平臺(tái)合并過(guò)程均采用貪婪策略生成最終聚類方案,若當(dāng)前層的第p個(gè)合并方案使最終目標(biāo)函數(shù)值最小,則選用p方案作為當(dāng)前層的合并方案,進(jìn)入下一層合并重復(fù)該過(guò)程,直至滿足結(jié)束條件。合并過(guò)程如圖1所示。

圖1 rollout策略下的層次聚類法的合并過(guò)程Fig.1 Merge processing of hierarchical clustering algorithm based on rollout strategy

2.2 最小RMS的平臺(tái)合并準(zhǔn)則下的聚類過(guò)程

本文提出了基于rollout策略下的層次聚類法對(duì)該問(wèn)題進(jìn)行求解。根據(jù)式(13)中的問(wèn)題目標(biāo)函數(shù),選擇任意兩個(gè)平臺(tái)進(jìn)行合并,合并后計(jì)算生成的所有決策實(shí)體的工作負(fù)載的RMS值,根據(jù)聚類后的RMS值生成m個(gè)當(dāng)前層的備選合并方案,每個(gè)方案后續(xù)的合并過(guò)程均采用貪婪算法,利用rollout策略確定當(dāng)前層的最佳合并項(xiàng)。滿足該條件的平臺(tái)合并規(guī)則稱為基于最小RMS平臺(tái)分組合并規(guī)則[10],基于rollout策略的層次聚類法在該合并規(guī)則下的聚類流程如圖2所示。

圖2 rollout策略下的層次聚類法聚類流程圖Fig.2 Flowchart of hierarchical clustering based on rollout strategy

步驟1選擇任意的兩個(gè)平臺(tái)進(jìn)行合并

平臺(tái)聚類開(kāi)始前,假設(shè)每一個(gè)平臺(tái)由一個(gè)決策實(shí)體控制,此時(shí)的決策實(shí)體的數(shù)量Dnow與平臺(tái)數(shù)量J相等。聚類開(kāi)始時(shí),選擇任意兩個(gè)決策實(shí)體DMh與DMk進(jìn)行分組合并(h,k=1,2,…,Dnow, 且h≠k),合并后的形成新的決策實(shí)體DMg,此時(shí)新決策實(shí)體的DMg的總工作負(fù)載為

CW(g)=CW(h)+CW(k)-

(14)

經(jīng)過(guò)合并后,其他決策實(shí)體DMm的工作負(fù)載也要進(jìn)行相應(yīng)地更新,具體體現(xiàn)為消除合并后的兩個(gè)決策實(shí)體對(duì)于其他決策實(shí)體而言產(chǎn)生重疊的外部工作負(fù)載。更新后的決策實(shí)體DMm的工作負(fù)載表示為

CW(m)=CW(m)-WE·Δ(m,h,k),m≠h,k

(15)

步驟2計(jì)算合并后的所有決策實(shí)體工作負(fù)載RMS值

平臺(tái)合并后當(dāng)前的決策實(shí)體數(shù)量為Dnow-1,計(jì)算此時(shí)決策實(shí)體工作負(fù)載的RMS值為

(16)

步驟3建立備選平臺(tái)合并方案集

計(jì)算合并后工作負(fù)載的RMS值后,根據(jù)RMS(h,k)矩陣中的結(jié)果按升序進(jìn)行排列,生成備選合并方案集M={1-best, 2-best, …,m-best},其中1-best對(duì)應(yīng)平臺(tái)合并后RMS值最小的合并選項(xiàng)(r1,s1),2-best對(duì)應(yīng)平臺(tái)合并后RMS值次小的合并選項(xiàng)(r2,s2),集合M中包含了m個(gè)互不相同的備選平臺(tái)合并方案。

步驟4確定最佳合并選項(xiàng)

分別令當(dāng)前層的平臺(tái)合并方案為集合M中的p-best(p=1,2,…,m),后續(xù)聚類過(guò)程采用貪婪策略得到最終的平臺(tái)聚類方案,比較m個(gè)不同方案最終的工作負(fù)載RMS值,選擇使最終聚類RMS值最小的平臺(tái)合并選項(xiàng)(r,s)作為當(dāng)前層的平臺(tái)合并方案。若Dnow=Dstop,則合并結(jié)束,否則Dnow=Dnow-1,重復(fù)步驟1。

2.3 合并過(guò)程中的變量更新法則

(1) 兩個(gè)決策實(shí)體DMr與DMs合并形成新的決策實(shí)體DMG,更新平臺(tái)與決策實(shí)體的隸屬關(guān)系、任務(wù)與決策實(shí)體的執(zhí)行關(guān)系:

xGj=max(xrj,xsj)

(17)

uGi=max(uri,usi)

(18)

(2) 更新其他決策實(shí)體與新決策實(shí)體DMG之間的協(xié)作工作負(fù)載:

R(m,G)=R(m,r)+R(m,s)-Δ(m,r,s)

(19)

(3) 更新合并后的決策實(shí)體DMG的總工作負(fù)載CW(G):

CW(G)=CW(r)+CW(s)-

(20)

(4) 更新其他決策實(shí)體DMm的總工作負(fù)載CW(m):

CW(m)=CW(m)-WE·Δ(m,r,s)

(21)

(5) 計(jì)算合并后的決策實(shí)體總工作負(fù)載的RMS值:

(22)

3 算例分析

3.1 特殊算例分析

本文選用文獻(xiàn)[16]中的聯(lián)合作戰(zhàn)的戰(zhàn)役想定作為特殊算例,對(duì)基于rollout策略下的層次聚類法的可行性和有效性進(jìn)行驗(yàn)證。在該算例中,任務(wù)數(shù)量I=18,平臺(tái)數(shù)量P=20,具體的平臺(tái)、任務(wù)屬性詳細(xì)描述見(jiàn)參考文獻(xiàn)[16]。該戰(zhàn)役想定中的平臺(tái)調(diào)度方案的甘特圖(平臺(tái)與任務(wù)的匹配關(guān)系在聚類開(kāi)始前是已知的輸入信息)如圖3所示。

圖3 平臺(tái)調(diào)度方案甘特圖Fig.3 Gantt chart of platform scheduling scheme

針對(duì)該算例,作以下仿真實(shí)驗(yàn):

在基于rollout策略下的層次聚類法的參數(shù)設(shè)置中,內(nèi)部工作負(fù)載與外部工作負(fù)載分別為WI=1、WE=1,決策實(shí)體的數(shù)量D=5,平臺(tái)備選合并方案?jìng)€(gè)數(shù)m的取值為m=1,2,…,10,得到在該方法下的基于最小RMS合并準(zhǔn)則的決策實(shí)體的工作負(fù)載RMS值(問(wèn)題模型的目標(biāo)函數(shù))與m值關(guān)系的變化曲線,如圖4所示。由圖4可知,隨著m值的增大,聚類后工作負(fù)載的RMS值將減小,當(dāng)m>3時(shí),RMS值趨于穩(wěn)定,隨著m值繼續(xù)增大RMS值穩(wěn)定在249.238 8。

圖4 RMS值隨備選方案?jìng)€(gè)數(shù)m的變化曲線Fig.4 RMS value with change of scheme number m

通過(guò)對(duì)仿真過(guò)程的分析能得出,當(dāng)m的取值為3～6時(shí),由11個(gè)平臺(tái)分組聚類為10個(gè)平臺(tái)分組的過(guò)程中產(chǎn)生了使RMS值達(dá)到最小值248.937 7的聚類方案,因此最終聚類后工作負(fù)載的RMS值為248.937 7。而當(dāng)m>6時(shí),在12個(gè)平臺(tái)分組聚類為11個(gè)平臺(tái)分組時(shí)產(chǎn)生能使工作負(fù)載RMS值達(dá)到最小值249.238 8的平臺(tái)合并方案,后續(xù)的逐層的合并方案中將不再產(chǎn)生使RMS值小于該值的合并方案,因此當(dāng)m>6時(shí),工作負(fù)載穩(wěn)定在249.238 8。實(shí)驗(yàn)結(jié)果說(shuō)明,rollout策略下的層次聚類法具有可行性,能改善最終聚類的效果。

為驗(yàn)證該方法的優(yōu)越性,令平臺(tái)備選方案?jìng)€(gè)數(shù)m=4,其余參數(shù)不變,與傳統(tǒng)貪婪策略下的層次聚類法[10]在基于最小RMS的合并規(guī)則下對(duì)所得聚類方案進(jìn)行對(duì)比,從每個(gè)決策實(shí)體的工作負(fù)載、聚類后的RMS值以及方差3個(gè)方面進(jìn)行比較分析,最終的聚類結(jié)果如表1、表2所示。

表1 貪婪策略下的層次聚類結(jié)果

表2 基于rollout策略下的層次聚類

由表1、表2可知,當(dāng)決策實(shí)體數(shù)量為5時(shí),對(duì)比貪婪策略下的層次聚類法與基于rollout策略的層次聚類法的聚類方案,決策實(shí)體工作負(fù)載的最大值由340降低至300,決策實(shí)體工作負(fù)載的最小值由170提高至185,RMS方差整體降低了25.457 6,表明每個(gè)決策實(shí)體的工作負(fù)載更加均衡,并且問(wèn)題的目標(biāo)函數(shù)值更小,驗(yàn)證了該方法具有有效性和優(yōu)越性。

為了驗(yàn)證該方法的適用性,設(shè)置不同的工作負(fù)載系數(shù)進(jìn)行仿真實(shí)驗(yàn)分析。令外部工作負(fù)載系數(shù)WE=1,設(shè)置內(nèi)部工作負(fù)載系數(shù)分別為WI=1,2,3,4,在這4種不同負(fù)載系數(shù)情況下,決策實(shí)體的數(shù)量D的取值為D=1,2,…,8,分別使用一般層次聚類法和基于rollout策略的層次聚類法(令m=4)在基于最小RMS的合并規(guī)則下生成平臺(tái)聚類方案,得到D個(gè)決策實(shí)體工作負(fù)載的RMS值在不同負(fù)載系數(shù)下的變化曲線,如圖5所示。

圖5 不同工作負(fù)載系數(shù)下RMS值隨決策實(shí)體數(shù)量D值變化曲線圖Fig.5 RMS value with change of decsion makes’ number D under different work load factor

由圖5中的4幅曲線變化圖可知,在不同外部工作負(fù)載條件下,使用rollout策略下的層次聚類法都能得到優(yōu)于一般層次聚類法的聚類結(jié)果,該方法下的工作負(fù)載RMS值普遍小于一般層次聚類法的RMS值。并且決策實(shí)體的數(shù)量D越少,基于rollout策略的層次聚類法所得到的聚類方案的效果越好,該結(jié)論體現(xiàn)了本文所提方法的優(yōu)越性,也說(shuō)明該方法在不同工作負(fù)載系數(shù)下的適用性。

3.2 一般算例分析

為進(jìn)一步驗(yàn)證基于rollout策略的層次聚類法對(duì)聚類結(jié)果具有改善效果,本文將引入一般算例進(jìn)行仿真分析。設(shè)計(jì)一般案例的任務(wù)數(shù)量I=18,平臺(tái)數(shù)量P=20,任務(wù)處理時(shí)間和不同任務(wù)設(shè)定下的平臺(tái)-平臺(tái)匹配關(guān)系均在所引用特殊算例的基礎(chǔ)上通過(guò)蒙特卡羅方法隨機(jī)生成。分別使用一般層次聚類法和基于rollout策略的層次聚類法計(jì)算聚類方案工作負(fù)載的RMS值并進(jìn)行對(duì)比分析,以一般層次聚類法打得到的RMS值作為基準(zhǔn),對(duì)比算法改進(jìn)前后得到的RMS值相對(duì)于該基準(zhǔn)的優(yōu)化率(本文優(yōu)化率指當(dāng)前算法與一般層次聚類法目標(biāo)函數(shù)值的比值,體現(xiàn)優(yōu)化程度),通過(guò)200次蒙特卡羅仿真實(shí)驗(yàn)得到的優(yōu)化率統(tǒng)計(jì)盒須圖對(duì)比如圖6所示。由圖6中的兩種不同算法下的優(yōu)化率盒須圖可知,采用基于rollout策略的層次聚類法所得到的優(yōu)化率平均值為1.083 1,使用該方法得到的優(yōu)化率普遍大于一般層次聚類法。因此對(duì)于該聚類問(wèn)題,本文所提出的基于rollout策略的層次聚類法在統(tǒng)計(jì)意義上要優(yōu)于一般層次聚類法,表明使用該方法能夠得到更優(yōu)的平臺(tái)聚類方案,充分體現(xiàn)了使用方法的優(yōu)越性。

圖6 蒙特卡羅仿真兩種算法優(yōu)化率盒須圖Fig.6 Boxplot of different algorithm optimization rate under Monte Carlo simulation

4 結(jié) 論

本文提出了一種改進(jìn)的傳統(tǒng)C2組織平臺(tái)與決策實(shí)體配置求解方法,針對(duì)一般的層次聚類法在聚類時(shí)每一層平臺(tái)合并均采用了貪婪策略可能導(dǎo)致聚類結(jié)果無(wú)法達(dá)到全局最優(yōu)的情況,提出rollout策略對(duì)層次聚類過(guò)程進(jìn)行改進(jìn),在每一層合并選項(xiàng)確定前生成該層的m個(gè)平臺(tái)合并備選方案,根據(jù)最小RMS合并準(zhǔn)則通過(guò)rollout策略選擇當(dāng)前層的最佳合并項(xiàng)進(jìn)行合并,聚類直至平臺(tái)分組數(shù)量與決策實(shí)體個(gè)數(shù)相等時(shí)結(jié)束。通過(guò)特殊案例分析可知,基于rollout策略的層次聚類法可以有效的從整體上降低決策實(shí)體的工作負(fù)載,并且能進(jìn)一步均衡決策實(shí)體之間的工作負(fù)載,減小每個(gè)決策實(shí)體工作負(fù)載之間的差異,使最終得到的聚類方案更加符合實(shí)際需求,最后再通過(guò)一般案例進(jìn)一步驗(yàn)證了該方法的適用性與優(yōu)越性。

工作負(fù)載的定義方式將影響最終的聚類方案的生成,不同的定義產(chǎn)生不同的決策實(shí)體與平臺(tái)之間的指控關(guān)系,因此充分考慮戰(zhàn)場(chǎng)環(huán)境的綜合因素,從作戰(zhàn)任務(wù)難度、作戰(zhàn)激烈程度等方面綜合考慮對(duì)工作負(fù)載進(jìn)行測(cè)度,會(huì)使工作負(fù)載的設(shè)計(jì)更加符合實(shí)際需求。同時(shí),決策實(shí)體的差異性、決策實(shí)體的知識(shí)約束也是會(huì)對(duì)平臺(tái)聚類結(jié)果產(chǎn)生影響的重要因素,后續(xù)工作過(guò)程中將對(duì)上述問(wèn)題進(jìn)一步研究。

參考文獻(xiàn)：

[1] BUI H, HAN X, MANDAL S, et al. Optimization-based decision support algorithm for a team-in-the-loop planning experiment[C]∥Proc.of the IEEE International Conference on Systems, Man, and Cybernetics, 2009: 4685-4689.

[2] 陽(yáng)東升, 張維明, 劉忠, 等. 指控組織設(shè)計(jì)方法[M]. 北京: 國(guó)防工業(yè)出版社, 2010: 161-189.

YANG D S, ZHANG W M, LIU Z, et al. Designing of command and control organization[M]. Beijing: Nation Defense Industry Press, 2010: 161-189.

[3] HAN X, MANDAL S, PATTIPATI K R, et al. An optimization-based distributed planning algorithm: a blackboard-based colla-borative framework[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A:Systems and Humans,2017,48(6):673-684.

[4] 孫昱,姚佩陽(yáng),張杰勇.C2組織信息結(jié)構(gòu)效能測(cè)度及綜合評(píng)估[J]. 系統(tǒng)工程與電子技術(shù),2015,37(6): 1313-1318.

SUN Y, YAO P Y, ZHANG J Y. Measurement and comprehensive evaluation of C2 organizational information structure efficiency[J]. Systems Engineering and Electronics, 2015, 37(6): 1313-1318.

[5] 周翔翔, 姚佩陽(yáng), 尹忠海. 指揮決策實(shí)體層次結(jié)構(gòu)設(shè)計(jì)方法[J]. 電光與控制, 2012, 19(2): 68-72.

ZHOU X X, YAO P Y, YIN Z H. A method for design of command decision-making entity’s hiberarchy architecture[J]. Electronics Optics & Control, 2012, 19(2): 68-72.

[6] SCHEIDT D, SCHULTZ K. On optimizing command and control structures[C]∥Proc.of the 16th International Command and Control Research Symposium, 2011: 1-10.

[7] LEVCHUK G M, LEVCHUK Y N, LUO J, et al. Normative design of organizations—Part Ⅰ: mission planning[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2002, 32(3): 346-359.

[8] LEVCHUK G M, LEVCHUK Y N, LUO J, et al. Normative design of organizations—Part Ⅱ: organizational structure[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2002, 32(3): 360-375.

[9] 劉宏芳, 陽(yáng)東升, 劉忠, 等. 兵力編成裁剪算法研究:決策節(jié)點(diǎn)裁剪[J]. 系統(tǒng)工程與理論實(shí)踐, 2007, 27(5): 106-112.

LIU H F, YANG D S, LIU Z, et al. Research on algorithm of tailoring military force tailoring nodes of decision-making[J]. Systems Engineering-Theory & practice,2007,27(5):106-112.

[10] 張杰勇,姚佩陽(yáng).C2組織決策實(shí)體配置問(wèn)題建模與求解方法[J].系統(tǒng)工程與電子技術(shù),2012,34(4):737-742.

ZHANG J Y, YAO P Y. Model and solving method of collocating problem of decision-makers in C2 organization[J]. Systems Engineering and Electronics, 2012, 34(4): 737-742.

[11] 吳瑞杰,孫鵬,孫昱,等.自適應(yīng)量子遺傳算法在指揮控制結(jié)構(gòu)設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與研究,2016,33(7):113-119.

WU R J, SUN P, SUN Y, et al. Self-adaptation quantum genetic algorithm used in design of command and control structure[J]. Application Research of Computers, 2016, 33(7): 113-119.

[12] 孫昱, 姚佩陽(yáng), 吳吉祥, 等. 兵力組織扁平化指揮控制結(jié)構(gòu)設(shè)計(jì)方法[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(8): 1833-1839.

SUN Y, YAO P Y, WU J X, et al. Design method of flattening command and control structure of army organization[J].Systems Engineering and Electronics,2016,38(8):1833-1839.

[13] TU F, PATTIPATI K R. Rollout strategies for sequential fault diagnosis[J]. IEEE Trans.on Systems Man & Cybernetics-Part A: Systems & Humans, 2002, 33(1):86-99.

[14] TIAN X, BAR-SHALOM Y, PATTIPATI K R. Multi-step look-ahead policy for autonomous cooperative surveillance by UAVs in hostile environments[C]∥Proc.of the 37th IEEE Conference Decision Control, 2008, 16(5): 2438-2443.

[15] HAN X, BUI H, MANDAL S, et al. Optimization-based decision support software for a team-in-the-loop experiment: asset package selection and planning[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A:Systems and Humans,2013,44(3): 237-251.

[16] YU F, TU F, PATTIPATI K R. A novel congruent organizational design methodology using group technology and a nested genetic algorithm[J]. IEEE Trans.on Systems, Man, and Cybernetics-Part A: Systems and Humans,2005,36(1):5-18.