基于自適應遺傳算法的戰(zhàn)場資源動態(tài)調度模型及算法

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

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

0 引 言

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

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

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

1 平臺資源調度問題的相關概念

1.1 作戰(zhàn)任務

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

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

1.2 平臺資源

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

1.3 平臺資源調度方案

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

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

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

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

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

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

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

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

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

(1)

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

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

≤M

(2)

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

,Tk∈Tnomal

(3)

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

(4)

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

(5)

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

任務集中的每一個任務都必須達到一定的任務完成質量要求,即

Qk≥δ,Tk∈T(t′)

(6)

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

min TFT

Qk≥δ,Tk∈T(t′)

(7)

3 模型求解算法

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

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

3.1 染色體的編碼方法

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

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

3.2 適應度函數(shù)

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

(8)

3.3 遺傳算子

3.3.1 交叉、變異算子

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

因此,交叉概率為

Pc=

(9)

變異概率為

Pm=

(10)

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

(11)

(12)

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

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

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

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

3.3.3 SGA的整體步驟

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

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

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

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

4 算例分析

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

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

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

表2 平臺資源屬性表

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 算法比較Fig.5 Algorithm comparison

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

5 結 論

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