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

(1. 西北工業(yè)大學(xué)計算機學(xué)院,陜西 西安 710072; 2. 西北工業(yè)大學(xué)軟件與微電子學(xué)院,陜西 西安 710072; 3. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西 西安 710077; 4. 中國人民解放軍95445部隊,云南 大理 672100)

0 引 言

戰(zhàn)場平臺資源調(diào)度問題研究在一系列約束條件下如何將軍事組織擁有的平臺資源合理的分配給作戰(zhàn)任務(wù),以實現(xiàn)作戰(zhàn)目標(biāo)的最優(yōu)化[1-3]。如何靈活有序的調(diào)度作戰(zhàn)資源是現(xiàn)代戰(zhàn)爭取得勝利的關(guān)鍵要素,也是實現(xiàn)作戰(zhàn)任務(wù)規(guī)劃的重要內(nèi)容。

關(guān)于戰(zhàn)場平臺資源調(diào)度問題的優(yōu)化模型和求解方法,Levchuk等人建立了以最小化使命完成時間為目標(biāo)的問題模型,提出了多維動態(tài)列表規(guī)劃(multidimensional dynamic list scheduling, MDLS)求解算法[4];文獻[5-6]在此基礎(chǔ)上分別考慮了完成時間約束和時間窗口約束,提出了循環(huán)MDLS和擴展MDLS求解算法;文獻[7]以任務(wù)執(zhí)行效率為目標(biāo)函數(shù)建立了問題模型,通過量子遺傳算法對問題進行求解,文獻[8]建立了以最小化全部任務(wù)的完成時間和最大化平臺資源利用率為目標(biāo)的數(shù)學(xué)模型,結(jié)合蟻群算法解決平臺資源的調(diào)度問題;文獻[9]考慮了作戰(zhàn)過程中戰(zhàn)場環(huán)境中執(zhí)行時間不確定、平臺資源能力損耗不確定等因素,建立了以最大化使命成功概率為目標(biāo)的機會約束規(guī)劃模型,并提出了分散搜索算法求解該問題;文獻[10]針對資源不確定性提出了資源緩沖區(qū)預(yù)測調(diào)度算法,為組織提供多個資源緩沖區(qū)分配方案;文獻[11]進一步從多個方面考慮不確定因素,建立了以任務(wù)執(zhí)行效率為目標(biāo)函數(shù)的數(shù)學(xué)模型,求解不確定環(huán)境下的資源動態(tài)調(diào)度問題。

隨著作戰(zhàn)環(huán)境日趨復(fù)雜多變[12-13],戰(zhàn)場平臺資源調(diào)度問題的研究方向正逐漸從戰(zhàn)前的預(yù)先調(diào)度向戰(zhàn)時的實時調(diào)整轉(zhuǎn)變[14-16],戰(zhàn)場平臺資源的動態(tài)調(diào)度成為了當(dāng)前研究的重點。為此,本文研究了不確定環(huán)境下的戰(zhàn)場資源動態(tài)調(diào)度問題,以最小作戰(zhàn)完成時間為目標(biāo)建立戰(zhàn)場平臺資源動態(tài)調(diào)度數(shù)學(xué)模型,并針對該問題模型的特點,基于自適應(yīng)遺傳算法進行求解。

1 平臺資源調(diào)度問題的相關(guān)概念

1.1 作戰(zhàn)任務(wù)

作戰(zhàn)任務(wù)是指由作戰(zhàn)使命分解得到需要執(zhí)行的一系列子任務(wù)。記包含N個任務(wù)的任務(wù)集為T={T1,T2,…,TN},每個任務(wù)均具備以下屬性:①任務(wù)持續(xù)時間LTi;②任務(wù)的地理坐標(biāo)位置TPi=(xi,yi);③任務(wù)資源需求向量Ri={Ri1,Ri2,…,RiL},其中Ril表示成功處理任務(wù)Ti所需要的第l種類型資源的數(shù)量,L表示處理該任務(wù)所需要的不同類型資源的數(shù)量。

任務(wù)集合T中,任務(wù)之間通常存在一定的時序關(guān)系,即一個任務(wù)必須滿足以下兩個條件才能被處理:①該任務(wù)的所有前序任務(wù)已經(jīng)全部完成;②處理該任務(wù)的所有平臺資源已經(jīng)到達該任務(wù)所處的位置。

1.2 平臺資源

平臺資源是指軍事組織所擁有的具備處理作戰(zhàn)任務(wù)的能力的基本單元。記包含J個平臺的平臺集為P={P1,P2,…,PJ},每個平臺具備以下屬性:①平臺的初始地理坐標(biāo)位置PPi=(xj,yj);②平臺在不同任務(wù)之間轉(zhuǎn)移時的移動速度vpj;③平臺資源能力向量rj={rj1,rj2,…,rjL},其中rjl表示平臺Pj提供的第l種類型資源的數(shù)量。若rjl=0,則說明該平臺不提供第l種類型的資源。當(dāng)平臺Pk執(zhí)行完任務(wù)Tm后被分配執(zhí)行任務(wù)Tn,則平臺從坐標(biāo)(xmi,ymi)轉(zhuǎn)移到坐標(biāo)(xni,yni)所花費的時間((xni—xmi)2+(yni—ymi)2)1/2/vpj,當(dāng)平臺Pk到達所要執(zhí)行的任務(wù)Tn的位置后,如果該任務(wù)只由一個平臺Pk執(zhí)行,則任務(wù)Tn在平臺Pk到達后立刻開始執(zhí)行;否則,Pk將等待其他平臺達到后才能執(zhí)行任務(wù)Tn。

1.3 平臺資源調(diào)度方案

平臺資源調(diào)度方案體現(xiàn)了軍事組織所擁有的平臺資源與作戰(zhàn)任務(wù)之間的匹配關(guān)系,反應(yīng)了作戰(zhàn)任務(wù)被執(zhí)行的情況。資源調(diào)度方案可用矩陣t′表示,其中t′表示任務(wù)Ti與平臺Pj的處理關(guān)系,若Pj執(zhí)行任務(wù)Ti,則t′=1,否則t′=0。本文選用作戰(zhàn)使命的完成時間TFT為衡量資源調(diào)度方案優(yōu)劣的測度值,對于任意任務(wù)Ti,任務(wù)的開始時間為BTi,任務(wù)的持續(xù)時間為LTi,則任務(wù)的結(jié)束時間ETi=BTi+LTi,因此,作戰(zhàn)使命的完成時間與最后一個任務(wù)的完成時間有關(guān),表示為

TFT=max(ET1,ET2,…,ETN)

2 平臺資源動態(tài)調(diào)度模型

2.1 使命環(huán)境中不確定性的表示

受到戰(zhàn)場的復(fù)雜環(huán)境的影響,使命在執(zhí)行過程中可能會因為諸多不確定因素而使平臺資源的屬性、作戰(zhàn)任務(wù)的屬性發(fā)生變化。不確定性引起的變化可能導(dǎo)致初始的資源調(diào)度方案不能按照原計劃執(zhí)行,或是執(zhí)行效果與預(yù)期效果存在較大的偏差,因此需要對作戰(zhàn)方案進行調(diào)整,使其滿足當(dāng)前的作戰(zhàn)需求。作戰(zhàn)過程中,本文設(shè)計只考慮以下兩方面的不確定性事件:

(1)突發(fā)任務(wù)。突發(fā)任務(wù)是指在使命執(zhí)行過程中某一時刻臨時增加的不屬于初始任務(wù)集中的任務(wù)。這一任務(wù)的出現(xiàn),要求使命執(zhí)行過程中必須臨時分配新的平臺資源來執(zhí)行該任務(wù)。

(2)平臺失效。平臺失效指隨著作戰(zhàn)進程的繼續(xù),平臺資源出現(xiàn)故障或受到敵方打擊而無法繼續(xù)提供任務(wù)需求的各項資源能力的情況。

當(dāng)以上兩方面不確定事件發(fā)生后初始的資源調(diào)度方案可能已不再滿足當(dāng)前作戰(zhàn)實際情況的需求,因此需要對資源調(diào)度方案進行調(diào)整。調(diào)整過程也要滿足兩方面的需求:①盡量降低資源調(diào)度方案的調(diào)整幅度,以維持原有調(diào)度方案的穩(wěn)定性;②未受到影響的作戰(zhàn)任務(wù)維持原始的資源調(diào)度方案不變,以降低軍事組織的結(jié)構(gòu)調(diào)整代價。

2.2 約束條件分析及模型建立

(1)

為了使組織調(diào)度方案的代價盡可能小,調(diào)整過程必須滿足以下約束條件:

(1) 受不確定事件影響的任務(wù)集合記為T(t′),此時新增加的任務(wù)集合為Tnew=T(t′)-T(t)。為了盡量降低組織結(jié)構(gòu)調(diào)整代價,對新增加的作戰(zhàn)任務(wù)能分配到的平臺資源數(shù)量進行限制,表示為

≤M

(2)

(2) 未受到影響的任務(wù)集合表示為Tnomal=T(t′)-Tnew-Tdestroy,其中Tdestroy表示因平臺摧毀而受影響無法正常執(zhí)行的任務(wù)。未受影響的任務(wù)對應(yīng)的平臺資源調(diào)度方案按照原始分配方案繼續(xù)執(zhí)行,表示為

,Tk∈Tnomal

(3)

(3) 任務(wù)的資源滿足度指作戰(zhàn)平臺實際提供的資源能力與任務(wù)預(yù)計需求的資源能力之間的比值,表示為

(4)

平臺資源在處理作戰(zhàn)任務(wù)時,平臺提供的各項資源能力與任務(wù)各項資源需求的比值,體現(xiàn)了任務(wù)的完成質(zhì)量,表示為

(5)

式中,γ(i)表示處理任務(wù)i所需要的不同類型的資源;‖γ(i)‖表示任務(wù)Ti所需要的資源類型總數(shù)。

任務(wù)集中的每一個任務(wù)都必須達到一定的任務(wù)完成質(zhì)量要求,即

Qk≥δ,Tk∈T(t′)

(6)

綜合上述約束條件,以最小使命完成時間為優(yōu)化目標(biāo),建立的平臺資源動態(tài)調(diào)度模型可以描述為

min TFT

Qk≥δ,Tk∈T(t′)

(7)

3 模型求解算法

由式(7)可知,平臺資源的動態(tài)調(diào)度是一個組合優(yōu)化問題,考慮到智能搜索算法能夠較好地求解該類問題,因此,本文選擇基于自適應(yīng)遺傳算法進行模型求解。

自適應(yīng)遺傳算法是基于遺傳學(xué)原理的隨機并行搜索算法,該算法能在不需要任何初始化信息的條件下實現(xiàn)對最優(yōu)解的全局搜索,可以有效解決帶約束條件的二元規(guī)劃問題,與傳統(tǒng)遺傳算法不同,自適應(yīng)遺傳算法根據(jù)每代個體的適應(yīng)度值適應(yīng)的調(diào)整交叉、變異概率,一方面保證了種群的多樣性,另一方面保護了種群中的優(yōu)良個體不受到破壞。打破傳統(tǒng)遺傳算法容易陷入局部最優(yōu)的僵局,使算法的全局搜索能力更強。

3.1 染色體的編碼方法

當(dāng)突發(fā)事件發(fā)生后,將受到影響或新增的任務(wù)放入待優(yōu)化任務(wù)集合δ中。此時待優(yōu)化任務(wù)集中存在δ個任務(wù)等待分配平臺資源,其中,每個任務(wù)Ti(i=1,2,…,δ)對應(yīng)的編號為i。若集合δ中有多個任務(wù),則集合中任務(wù)的優(yōu)先權(quán)按照任務(wù)的開始時間BTi進行排序,開始時間越早優(yōu)先級越高。對于每一個平臺Pj(j=1,2,…,J)而言,它的狀態(tài)s(j)有兩種,若該平臺被分配執(zhí)行當(dāng)前待優(yōu)化的任務(wù)Ti,則狀態(tài)s(j)=1,若未分配給當(dāng)前的待優(yōu)化任務(wù)Ti,則狀態(tài)s(j)=0。

一個染色體對應(yīng)一種當(dāng)前待優(yōu)化任務(wù)Ti的平臺調(diào)度方案,并且每個平臺被分配執(zhí)行任務(wù)的編碼是不連續(xù)的一串0-1二元變量,因此,可以采用離散二元0-1整型的編碼方式對GA的染色體進行編碼:一個染色體是一個由J個0-1二元整數(shù)構(gòu)成的有序序列S={s(1),s(2),…,s(J)},其中,s(j)∈{0,1}。

3.2 適應(yīng)度函數(shù)

根據(jù)上述對染色體編碼的方式可知,染色體中可能存在一部分不可行的平臺資源調(diào)度方案,即當(dāng)前待優(yōu)化任務(wù)Ti的完成質(zhì)量在新的調(diào)度方案下無法達到最低質(zhì)量δ的要求。因此,在計算各個染色體的適應(yīng)度之前,要對每一個染色體對應(yīng)的資源調(diào)度方案的可行性進行判斷,如果在該方案下當(dāng)前待優(yōu)化任務(wù)Ti的完成質(zhì)量未達到最低質(zhì)量δ的要求,則將該染色體的適應(yīng)度值設(shè)置為0。對于可行的染色體,選擇模型中目標(biāo)函數(shù)的倒數(shù)作為其適應(yīng)度函數(shù)。由此可知,本文自適應(yīng)遺傳算法(self-adaptive genetic algorithm, SGA)算法的適應(yīng)度函數(shù)表示為

(8)

3.3 遺傳算子

3.3.1 交叉、變異算子

種群的交叉概率Pc、變異概率Pm與種群的規(guī)模、適應(yīng)度值分布相關(guān)。在算法前期,交叉、變異概率較大,以豐富種群的多樣性,提高搜索能力,算法后期,降低交叉、變異概率以保護最優(yōu)個體不受到破壞。

因此,交叉概率為

Pc=

(9)

變異概率為

Pm=

(10)

式中,Pc2和Pm2是固定值,交叉概率參數(shù)Pc1和變異參數(shù)Pm1是隨進化代數(shù)N變化的參數(shù),滿足

(11)

(12)

式中,N為進化代數(shù),參數(shù)φ和φ表示交叉概率參數(shù)和變異概率參數(shù)的收斂極限。

通過引入正弦變化形式對交叉變異概率進行自適應(yīng)調(diào)整,可以避免當(dāng)適應(yīng)度值接近最大適應(yīng)度值或者平均適應(yīng)度值時交叉、變異概率過大或者過小,克服種群“停滯”而陷入局部最優(yōu)的情況。同時,在算法初期,較大的交叉概率能夠保證種群的多樣性,全局搜索能力更強;算法后期降低交叉概率提高變異概率,在維持種群最優(yōu)個體的同時從一定程度上抑制算法的過早收斂。

3.3.2 選擇算子和精英保留策略

本文通過輪盤賭選擇法保留適應(yīng)度值較高的個體,在由初始種群、經(jīng)過交叉、變異得到的種群合并成為新的種群中進行篩選,淘汰適應(yīng)度值較低的個體。同時采用精英保留策略,遺傳操作過程中繼承父代的優(yōu)良個體,保證每一代產(chǎn)生的最佳染色體能夠保留下來。

3.3.3 SGA的整體步驟

步驟1采用本文設(shè)計的染色體編碼方式,隨機產(chǎn)生初始種群GI,種群規(guī)模為Num;

步驟2采用本文設(shè)計的交叉算子和變異算子,對GI進行概率為Pc的交叉操作、行概率為Pm的變異操作,分別產(chǎn)生交叉種群Gc和Gm;

步驟3將GI、Gc和Gm合并一個種群,采用本文設(shè)計的選擇算子,進行選擇操作,產(chǎn)生種群規(guī)模為Num的新一代種群,并將其替代初始種群GI;

步驟4重復(fù)步驟2至步驟3直至達到最大迭代次數(shù)N。

4 算例分析

本文以一個聯(lián)合作戰(zhàn)想定為算例進行模型合理性和算法有效性的驗證,作戰(zhàn)任務(wù)的屬性與組織擁有的平臺資源屬性分別如表1、表2所示,共包含作戰(zhàn)任務(wù)N=8個,平臺資源J=12個。

初始平臺資源調(diào)度方案如圖1所示,設(shè)置新增任務(wù)的平臺資源限制數(shù)M=3個。

表1 作戰(zhàn)任務(wù)屬性表

表2 平臺資源屬性表

算例中SGA算法的參數(shù)設(shè)置為初始種群規(guī)模Num=40,初始交叉概率Pc2=0.8,初始變異概率Pm2=0.1,交叉概率參數(shù)φ=0.8,變異概率參數(shù)φ=0.13,進化代數(shù)N=100。

針對以上算例,進行下仿真實驗:

仿真實驗1令任務(wù)的質(zhì)量最低完成參數(shù)δ=0.8,作戰(zhàn)使命按照初始資源調(diào)度方案執(zhí)行至t=50時刻時,突發(fā)事件1發(fā)生,新增任務(wù)T9出現(xiàn),出現(xiàn)的位置在任務(wù)時序列表中的任務(wù)T8執(zhí)行完成后、任務(wù)T2執(zhí)行開始前,任務(wù)位置的坐標(biāo)TP9=(32,59),任務(wù)持續(xù)時間LT9=10,資源能力需求向量R9={0,7,3,0,6,2,0,2}。作戰(zhàn)使命執(zhí)行至t=77時刻時,突發(fā)事件2發(fā)生,平臺P6被摧毀。利用SGA算法對兩種突發(fā)事件情況下的資源調(diào)度方案進行調(diào)整。調(diào)整后的平臺資源調(diào)度方案甘特圖如圖2所示。

圖2 突發(fā)事件1發(fā)生后的平臺資源調(diào)度方案Fig.2 Platform resource scheduling plan after incident 1 occurs

當(dāng)突發(fā)事件1發(fā)生時,任務(wù)T9將被分配平臺資源以保證執(zhí)行。通過SGA算法得到的最優(yōu)解染色體編碼為{1,0,1,0,0,0,0,0,0,0,0,0},適應(yīng)度值為0.007 81,函數(shù)值TFT=127.97,從結(jié)果可知,對于新增任務(wù)T9選用平臺P3、P6執(zhí)行能使調(diào)整后的整體使命完成時間比較調(diào)整前增加了9.84,此時任務(wù)T9的完成質(zhì)量為0.96。

當(dāng)突發(fā)事件2發(fā)生時,平臺P6被摧毀。在t=77這個時刻P6沒有執(zhí)行任務(wù),但是后續(xù)T5任務(wù)已經(jīng)分配平臺P6,且P6摧毀后該任務(wù)的完成質(zhì)量為0.77,不滿足最低任務(wù)完成質(zhì)量要求,因此需要為T5分配新平臺資源。通過SGA算法得到的最優(yōu)染色體編碼為{0,0,0,1,0,0,0,1,1,0,0,0},表示新增平臺P9,和原方案中的P4、P8共同執(zhí)行任務(wù)T5,該染色體的適應(yīng)度值為0.007 64,函數(shù)值TFT=130.82,調(diào)整后的平臺資源調(diào)度方案如圖3所示。

以上結(jié)果表明,當(dāng)突發(fā)事件發(fā)生后,為了保證受影響任務(wù)的完成質(zhì)量,同時又要保證整體使命執(zhí)行時間最短,調(diào)整執(zhí)行受影響任務(wù)的平臺資源必須滿足以下兩個方面要求:一是單個平臺盡可能的滿足當(dāng)前待處理任務(wù)的資源需求;二是平臺此時的坐標(biāo)位置與當(dāng)前待處理任務(wù)的坐標(biāo)位置距離相近,這樣能夠保證平臺移動的時間最短。

圖3 突發(fā)事件2發(fā)生后的平臺資源調(diào)度方案Fig.3 Platform resource scheduling plan after incident 2 occurs

仿真實驗2當(dāng)t時刻觸發(fā)資源動態(tài)調(diào)度時,隨機生成突發(fā)事件及相應(yīng)屬性,采用SGA算法對該模型進行求解,將最低任務(wù)完成質(zhì)量δ設(shè)置在區(qū)間[0.5,1]內(nèi),Δδ=0.5,隨機進行4組實驗,所得到的使命完成時間TFT與最低完成質(zhì)量δ之間的變化曲線如圖4所示。

圖4 最低任務(wù)完成質(zhì)量與作戰(zhàn)完成時間的變化曲線Fig.4 Operational completion time curve with the minimummission completion quality

圖4中,每條不同的曲線代表不同的實驗組。從圖中4條曲線變化的趨勢可以看出,隨著任務(wù)完成質(zhì)量要求δ的不斷提高,使命完成時間均不斷延長,這是因為隨著任務(wù)完成質(zhì)量要求的改變,更多的平臺資源需要向受到影響的任務(wù)移動,平臺在移動過程中會增加使命完成的耗時。并且為了降低軍事組織的組織調(diào)整代價,使未受到影響的作戰(zhàn)任務(wù)的資源調(diào)度方案維持初始不變,當(dāng)一些平臺資源被分配執(zhí)行突發(fā)任務(wù)時,初始分配的任務(wù)則后延執(zhí)行,因此使命完成時間普遍增加。受到組織擁有的平臺資源數(shù)量的限制,沒有足夠的冗余平臺執(zhí)行突發(fā)任務(wù)時,使命整體完成時間被延長的現(xiàn)象較為嚴重,這也進一步反映出當(dāng)平臺資源不充足而任務(wù)完成質(zhì)量要求又較高時,難以維持組織的魯棒性。

從圖4中也可以看出,隨著任務(wù)完成質(zhì)量要求的不斷增加,使命完成時間并不總是延長的,這是因為平臺資源能力與任務(wù)資源需求均為離散的數(shù)值,在任務(wù)執(zhí)行過程中其完成質(zhì)量在一定范圍內(nèi)變化時并不需要對資源調(diào)度方案進行反復(fù)調(diào)整,因此使命完成時間對應(yīng)某些要求時可能不發(fā)生變化。

仿真實驗3為了驗證本文所提的SGA算法在解決資源動態(tài)調(diào)度問題上的優(yōu)越性,將SGA算法與模擬退火算法(simulated annealing, SA)進行對比,設(shè)置最低任務(wù)完量δ=0.8,突發(fā)事件的發(fā)生時刻用蒙特卡羅方法隨機生成,隨機進行10組仿真實驗,所得結(jié)果如圖5所示。

圖5 算法比較Fig.5 Algorithm comparison

從圖5中可知,SGA算法得到的平均使命完成時間TFT=101.53,SA算法得到的平均使命完成時間TFT=107.41,雖然在部分實驗組中,兩種算法得到的結(jié)果相同,但整體而言,SGA得到的使命完成時間優(yōu)于SA算法的結(jié)果,也即本文算法在解決平臺資源動態(tài)調(diào)度問題時更為有效和優(yōu)越。

5 結(jié) 論

本文描述了作戰(zhàn)環(huán)境中的不確定性,分析了資源動態(tài)調(diào)度的約束條件,構(gòu)建了以最小整體使命完成時間為目標(biāo)函數(shù)的資源動態(tài)調(diào)度模型,通過SGA算法對由不確定性引起的作戰(zhàn)任務(wù)或平臺資源變化的突發(fā)事件進行資源調(diào)度方案的調(diào)整?；诼?lián)合作戰(zhàn)算例的仿真結(jié)果表明,所建模型及其求解算法能有效的解決戰(zhàn)場資源動態(tài)調(diào)度問題,并且可以有效的應(yīng)對由戰(zhàn)場不確定性引起的突發(fā)事件為目標(biāo)的動態(tài)優(yōu)化模型,設(shè)計了模型求解的SGA算法?；诼?lián)合作戰(zhàn)算例的仿真結(jié)果表明,所建模型及其求解算法能有效解決戰(zhàn)場資源動態(tài)調(diào)度問題,可以較好應(yīng)對和處理戰(zhàn)場的突發(fā)事件。下一步研究重點將從多個優(yōu)化目標(biāo)如任務(wù)執(zhí)行精度、成功執(zhí)行概率等角度考慮優(yōu)化模型的構(gòu)建,并進一步考慮資源的動態(tài)調(diào)整。