基于rollout策略下的決策實體配置問題求解方法

廖夢琛, 孫 鵬,2, 張杰勇, 武君勝

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077; 2. 西北工業大學計算機學院,陜西 西安 710077;3. 西北工業大學軟件與微電子學院, 陜西 西安 710077)

0 引 言

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

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

層次聚類法是平臺與決策實體配置關系設計的主要方法,考慮到采用傳統層次聚類法在合并過程中采用了貪婪策略,即每一層的合并過程都選擇當前層的最優合并方案,并未從全局的角度考慮解的最優性,得到的最終聚類方案可能不是全局最優方案。因此,本文將采用rollout策略對層次聚類法進行改進優化,以作戰任務的執行時間作為決策實體工作負載的測度標準,建立平臺與決策實體配置問題的數學模型,以工作負載的最小RMS值為模型目標函數,在平臺合并過程中采用基于最小RMS合并準則并使用rollout策略下的層次聚類法以對該問題進行求解,通過仿真算例說明該方法能夠降低工作負載的RMS值,并且能均衡每個決策實體之間的工作負載,驗證了該方法的適用性,并通過和傳統層次聚類法的對比分析驗證了該方法的優越性。

1 問題描述及建模

1.1 變量定義

戰場環境中,所有被用于作戰的平臺資源將被決策實體DMm控制和指揮,決策實體作為戰場要素中的核心要素,負責控制平臺Pj完成相應的作戰任務Ti。平臺與決策實體配置關系的構建的實質就是平臺聚類問題。對平臺聚類問題進行數學描述和建模,首先對變量作如下定義。

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

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

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

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

1.2 約束條件分析

(1) 任何一個平臺P有且只有一個決策實體DMm對其進行控制,即不存在多個決策實體控制同一個平臺的情況,同時配置給任意一個平臺的決策實體數量都不為0,描述為

(1)

(2) 每個決策實體至少控制一個平臺,即

(2)

(3) 對于每個決策實體而言,DMm控制的每一個平臺均只執行該平臺分配到的任務,隸屬于同一決策實體的不同平臺之間的任務互不影響,即

umi≥ωij·xmj

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

(3)

已知當ymni=1時，表明決策實體DMm和DMn在任務Ti上存在協作,可以得到協作變量ymni與分配變量umi和uni之間的關系為

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

(4)

1.3 決策實體配置問題的目標函數和模型建立

1.3.1 決策實體工作負載的定義

決策實體的工作負載反應了隸屬于該決策實體的平臺資源對作戰任務的執行情況。在考慮決策實體的工作負載時,選擇以面向作戰任務的形式,將作戰任務的執行時間作為工作負載的測度標準,從內部工作負載I(m)和外部工作負載E(m)兩個方面對工作負載進行描述[8]。

(1) 決策實體DMm的內部工作負載I(m)

決策實體的內部負載表示決策實體控制的平臺所承擔的工作負載,數值上表示為所控制平臺處理的全部作戰任務的時間之和,即

(5)

式中,ti為任務Ti的執行時間。

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

決策實體的外部工作負載表示決策實體所控制的平臺和其他決策實體協作處理任務時承擔的工作負載,數值上表示為與其他不屬于該決策實體的平臺協作執行的全部作戰任務的時間之和,即

(6)

式中,R(m,n)表示決策實體DMm與DMn協作處理作戰任務的時間之和

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

(7)

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

(8)

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

決策實體的總工作負載以內部工作負載I(m)與外部工作負載E(m)加權和的形式表示,即

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

(9)

式中,WI表示內部工作負載權重；WE表示外部工作負載權重。WI和WE分別表示對總工作負載的影響程度。一般地,取WI=WE=1。

1.3.2 目標函數的構造

在平臺與決策實體配置問題中,已知的輸入信息為平臺-任務的調度關系,當平臺-任務的調度方案生成后,初始的決策實體工作負載的內部負載部分將不再發生變化,因此對于該平臺聚類過程實質上就是最小化外部工作負載的過程。

由于每個決策實體的能力有限,如何對平臺進行合理地分組、將分組的平臺配置給有限數量的決策實體,是實現決策實體對平臺的指揮控制的關鍵。在這一問題中,一方面要求所有決策實體的平均工作負載盡可能小,另一方面要求所有決策實體的工作負載盡可能均衡。因此,目標函數從均值和方差兩個方面進行描述:

(1) 工作負載的均值

(10)

式中,D表示決策實體的個數,對于該問題的目標函數而言,工作負載的均值μ越小越好。

(2) 工作負載的方差

(11)

工作負載的方差σ2體現了每個決策實體工作負載的差異,因此對于該問題工作負載之間的方差σ2越小，表示每個決策實體的工作負載越均衡。

因此,決策實體工作負載的RMS可以表示為

(12)

1.3.3 數學模型建立

由式(12)可知,工作負載的RMS值綜合了工作負載的均值和方差兩個方面，充分體現了每個決策實體工作負載的水平,因此,本文構建的平臺與決策實體配置問題的數學模型為

(13)

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

2.1 rollout策略

平臺聚類的問題即將不同的平臺分配給一定數量的決策實體,由決策實體控制各個平臺執行既定的作戰任務。在聚類過程中,要在滿足問題約束條件的同時得到符合問題模型目標函數的最優解,因此平臺聚類方案體現了所設計的平臺與決策實體之間配置關系的合理性。使用層次聚類法實現平臺聚類的過程可以描述為:將當前的J個平臺按照某一合并規則進行合并,選擇合并后使目標函數值滿足問題模型的需求的兩個平臺進行合并,逐層合并直至平臺個數J與決策實體數量D相同時合并結束。

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

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

2.2 最小RMS的平臺合并準則下的聚類過程

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

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

步驟1選擇任意的兩個平臺進行合并

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

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

(14)

經過合并后,其他決策實體DMm的工作負載也要進行相應地更新,具體體現為消除合并后的兩個決策實體對于其他決策實體而言產生重疊的外部工作負載。更新后的決策實體DMm的工作負載表示為

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

(15)

步驟2計算合并后的所有決策實體工作負載RMS值

平臺合并后當前的決策實體數量為Dnow-1,計算此時決策實體工作負載的RMS值為

(16)

步驟3建立備選平臺合并方案集

計算合并后工作負載的RMS值后,根據RMS(h,k)矩陣中的結果按升序進行排列,生成備選合并方案集M={1-best, 2-best, …,m-best},其中1-best對應平臺合并后RMS值最小的合并選項(r1,s1),2-best對應平臺合并后RMS值次小的合并選項(r2,s2),集合M中包含了m個互不相同的備選平臺合并方案。

步驟4確定最佳合并選項

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

2.3 合并過程中的變量更新法則

(1) 兩個決策實體DMr與DMs合并形成新的決策實體DMG,更新平臺與決策實體的隸屬關系、任務與決策實體的執行關系:

xGj=max(xrj,xsj)

(17)

uGi=max(uri,usi)

(18)

(2) 更新其他決策實體與新決策實體DMG之間的協作工作負載:

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

(19)

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

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

(20)

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

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

(21)

(5) 計算合并后的決策實體總工作負載的RMS值:

(22)

3 算例分析

3.1 特殊算例分析

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

圖3 平臺調度方案甘特圖Fig.3 Gantt chart of platform scheduling scheme

針對該算例,作以下仿真實驗:

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

圖4 RMS值隨備選方案個數m的變化曲線Fig.4 RMS value with change of scheme number m

通過對仿真過程的分析能得出,當m的取值為3～6時,由11個平臺分組聚類為10個平臺分組的過程中產生了使RMS值達到最小值248.937 7的聚類方案,因此最終聚類后工作負載的RMS值為248.937 7。而當m>6時,在12個平臺分組聚類為11個平臺分組時產生能使工作負載RMS值達到最小值249.238 8的平臺合并方案,后續的逐層的合并方案中將不再產生使RMS值小于該值的合并方案,因此當m>6時,工作負載穩定在249.238 8。實驗結果說明,rollout策略下的層次聚類法具有可行性,能改善最終聚類的效果。

為驗證該方法的優越性,令平臺備選方案個數m=4,其余參數不變,與傳統貪婪策略下的層次聚類法[10]在基于最小RMS的合并規則下對所得聚類方案進行對比,從每個決策實體的工作負載、聚類后的RMS值以及方差3個方面進行比較分析,最終的聚類結果如表1、表2所示。

表1 貪婪策略下的層次聚類結果

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

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

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

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

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

3.2 一般算例分析

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

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

4 結 論

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

工作負載的定義方式將影響最終的聚類方案的生成,不同的定義產生不同的決策實體與平臺之間的指控關系,因此充分考慮戰場環境的綜合因素,從作戰任務難度、作戰激烈程度等方面綜合考慮對工作負載進行測度,會使工作負載的設計更加符合實際需求。同時,決策實體的差異性、決策實體的知識約束也是會對平臺聚類結果產生影響的重要因素,后續工作過程中將對上述問題進一步研究。

參考文獻：

[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] 陽東升, 張維明, 劉忠, 等. 指控組織設計方法[M]. 北京: 國防工業出版社, 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] 孫昱,姚佩陽,張杰勇.C2組織信息結構效能測度及綜合評估[J]. 系統工程與電子技術,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] 周翔翔, 姚佩陽, 尹忠海. 指揮決策實體層次結構設計方法[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] 劉宏芳, 陽東升, 劉忠, 等. 兵力編成裁剪算法研究:決策節點裁剪[J]. 系統工程與理論實踐, 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] 張杰勇,姚佩陽.C2組織決策實體配置問題建模與求解方法[J].系統工程與電子技術,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] 吳瑞杰,孫鵬,孫昱,等.自適應量子遺傳算法在指揮控制結構設計中的應用[J].計算機應用與研究,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] 孫昱, 姚佩陽, 吳吉祥, 等. 兵力組織扁平化指揮控制結構設計方法[J]. 系統工程與電子技術, 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.