郭 磊 ,雪 晴 ,董彥磊 ,耿紀昭,尹 展?

(1.軍事科學院系統(tǒng)工程研究院,北京 100141;2.中國電子科技集團公司第五十四研究所,河北 石家莊 050081)

0 引言

天基信息網(wǎng)絡[1](Space-Based Information Network,SBIN)是以衛(wèi)星為通信手段,采用星地一體技術構(gòu)成的空間通信網(wǎng)絡[2]。 天基資源特指天基信息網(wǎng)絡中分布的各型高、中、低軌衛(wèi)星資源。 由于頻率協(xié)調(diào)和星載平臺技術限制,目前衛(wèi)星頻率和功率資源受限,如何在有限衛(wèi)星資源前提下實現(xiàn)資源快速高效調(diào)度,最大限度滿足地面通信任務對星上資源的需求是天基信息網(wǎng)絡面臨的關鍵技術之一。 使用傳統(tǒng)遺傳算法進行基于任務的衛(wèi)星資源調(diào)度能夠得到全局最優(yōu)解,但存在收斂速度慢、計算過程耗時等問題;使用傳統(tǒng)粒子群算法進行任務資源調(diào)度能夠快速計算結(jié)果,但易陷入局部最優(yōu)解[3]。 針對以上問題,本文提出了一種基于遺傳和粒子群算法的天基資源調(diào)度改進方法,將天基資源調(diào)度問題抽象為數(shù)學上的裝箱問題[4],通過重新定義遺傳算法中選擇、交叉和變異算子的進化行為以及粒子群算法的速度方向,結(jié)合遺傳算法全局最優(yōu)搜索、粒子群算法局部快速收斂優(yōu)點,避免傳統(tǒng)方法的局部最優(yōu)、無法快速收斂等缺陷,提升天基資源規(guī)劃調(diào)度效能。

天基資源調(diào)度問題是指在限定約束條件下,通過對任務、資源進行快速合理調(diào)度,實現(xiàn)衛(wèi)星資源使用效能最大化。 多約束條件下資源調(diào)度問題已經(jīng)被證明是NP 完全問題[5],近年來資源調(diào)度成為眾多學者的熱門研究。 文獻[6]在衛(wèi)星資源調(diào)度問題中應用簡單啟發(fā)式算法、局部搜索算法和遺傳算法進行求解,結(jié)果表明遺傳算法總體效果最好。 文獻[7]以此為基礎提出了一種遺傳模擬退火算法,提高了算法的尋優(yōu)能力。 文獻[8]從調(diào)度任務特點出發(fā)建立了改進粒子群調(diào)度模型,但同傳統(tǒng)粒子群算法相比,改進效果不明顯。 本文針對衛(wèi)星資源調(diào)度問題重新設計進化策略,將遺傳算法和粒子群算法相結(jié)合,克服了傳統(tǒng)遺傳算法收斂速度慢,在實際工程應用中相對耗時,傳統(tǒng)二進制編碼方式不適合解決所有問題,而十進制編碼方式又受到進化策略的制約,同時結(jié)合了傳統(tǒng)粒子群算法快速收斂的優(yōu)點,因此,本文所提算法能在保證全局最優(yōu)搜索的同時具備快速收斂能力。

1 資源調(diào)度問題模型抽象

針對多約束條件下天基資源調(diào)度問題,采用基于任務驅(qū)動的資源調(diào)度模式,將問題抽象成待解模型。 假設一組任務(Task List,TL)總是和一組衛(wèi)星轉(zhuǎn)發(fā)器資源(Transponder Resource,TR)相關聯(lián),TL的任務只能使用TR 的資源,且所有使用TR 的任務都在TL 中,TR 和TL 都帶有時間屬性,資源調(diào)度問題數(shù)學模型如圖1 所示。

圖1 任務資源調(diào)度問題示意圖Fig.1 Schematic diagram of task resour ce scheduling problem

圖1(a)中,一組任務TL = {tl1,tl2,…,tln} ,以n = 10 為例闡述問題模型,假設n 個任務的資源需求如表1 所示。

表1 任務所需資源Tab.1 Resources required for the task

表1 中,t 為任務所需時間,f 為任務所需頻率資源。 假設要求在0 ≤t ≤8、0 ≤f ≤8 范圍內(nèi),盡可能多地滿足任務資源需求,即追求時間、頻率資源利用率最高。 將問題抽象在圖1(b)所示的藍色透明區(qū)域D 內(nèi),盡可能多地擺放任務塊,使D 內(nèi)的剩余面積最小。 為便于描述,將任務k 的占用資源范圍表示為(mk,nk,pk,qk) ,如圖2 所示。 其中,(mk,nk) 為任務k 占用資源左下角坐標,(pk,qk) 為任務k 占用資源右上角坐標。

圖2 任務k 占用資源描述坐標示意圖Fig.2 Schematic diagram of task k occupation resource description coordinate

調(diào)度模型為尋找TL 最優(yōu)調(diào)度序列SEQ ={seq1,seq2,…seqn}(n = 10) ,按SEQ 中的順序?qū)θ蝿諌K進行擺放,擺放范圍限制在圖1(b)中的藍色透明區(qū)域D 內(nèi),擺放規(guī)則為從坐標(0,0) 處開始,沿橫坐標找到能放下seqk(即任務占用資源不越界)的最小時間點tmin,再沿縱坐標在tmin時間線上找到最小可用頻點ftmin,將(mk,nk) 擺放在(tmin,ftmin)處,然后將seqk從隊列SEQ 中刪除,若當前任務已不存在可用空間,則將其視為不可擺放任務,將其從SEQ 刪除并加入不可擺放隊列NSEQ,進行下一個任務的擺放,直至所有任務遍歷完成,具體算法如下。

調(diào)度算法(Algorithm①)

輸入：SEQ = {seq1,seq2,…,seqn} (n = 10),NSEQ=?。

① k=1;

② 判斷k≤n,若為真,轉(zhuǎn)③,否則轉(zhuǎn)⑥;

③ seqk存在擺放空間,找到當前任務擺放點(tmin,ftmin),并將其從SEQ 中刪除;

④ seqk不存在擺放空間,則將其從SEQ 中刪除并加入NSEQ;

⑤ k=k+1,轉(zhuǎn)②;

⑥ 結(jié)束;

輸出：SEQ=?,NSEQ={不可擺放任務},為當前序列任務調(diào)度結(jié)果。

2 基于遺傳和粒子群的資源調(diào)度改進方法

遺傳算法和粒子群算法是目前成熟的群體優(yōu)化算法,通過初始化種群,設計進化策略,使種群向最優(yōu)解方向進化[9]。 遺傳算法的進化策略來源于自然界生物的進化規(guī)律,即父代通過選擇、交叉和變異3 種遺傳算子產(chǎn)生子代個體,子代具有優(yōu)于父代的生物特性[10]。 粒子群算法的進化策略來源于自然界動物覓食,動物在覓食過程中,依據(jù)氣味等信息向可能存在食物的方向移動[11]。 進化策略的合理性決定最終搜索結(jié)果的優(yōu)劣,因此2 種算法進行應用的關鍵是對具體問題設計合理的編碼方案和進化策略。

2.1 編碼方案選擇

傳統(tǒng)的遺傳算法和粒子群算法一般采用二進制編碼方案,本文將天基資源調(diào)度問題抽象成任務排序擺放問題,故傳統(tǒng)編碼方案不再適用。 針對任務排序問題,設計十進制編碼方案,對于一組待調(diào)度任務TL = {tl1,tl2,…,tln} ,用十進制編碼集合SEQ ={seq1,seq2,…,seqn} 表示該組任務的一種調(diào)度順序,其中seqi與tlseqi一一對應,代表一個待調(diào)度任務編號,且seqi∈{1,2,…,n - 1,n} 。SEQ 對應一組待調(diào)度任務的執(zhí)行順序,同時對應一個資源分配方案和相應的資源利用率,資源利用率越高,表明編碼方案越優(yōu)。

2.2 進化策略設計

群體優(yōu)化算法進化的基本思想是依據(jù)進化策略產(chǎn)生的子代群體總體上應優(yōu)于父代群體,進化后群體向著越來越優(yōu)的方向發(fā)展[12]。 進化策略的設計原則是子代在繼承父代優(yōu)秀基因基礎上保留產(chǎn)生新優(yōu)秀基因的可能性,同時摒棄父代中的非優(yōu)秀基因。

對于資源調(diào)度問題,優(yōu)秀基因定義是進化策略設計的核心[13]。 本文用待分配任務序列表示一個資源調(diào)度方案,即優(yōu)秀的任務序列具有更高的資源利用率。 在此將基因定義為任務調(diào)度的相對順序,優(yōu)秀基因代表隊列中任務的相對順序能產(chǎn)生更高的資源利用率。 例如,有2 個待分配任務A 和B ,若有序集合{A,B} 的資源利用率高于有序集合{B,A} ,則認為基因{A,B} 優(yōu)于基因{B,A} 。 依此原則,分別設計遺傳算法和粒子群算法的進化策略。

2.2.1 遺傳算法進化策略

遺傳算法進化策略包含3 個算子：選擇、交叉和變異。 選擇算子將父代群體中的優(yōu)秀基因保留下來;交叉算子將父代群體基因進行雜交,產(chǎn)生新的更優(yōu)秀基因;變異算子保留子代產(chǎn)生新優(yōu)秀基因的可能性,使進化不受父代群體限制,能夠在全局范圍內(nèi)搜索問題最優(yōu)解[14]。 本文以優(yōu)秀基因定義為原則,設計了3 種進化算子。

(1) 選擇算子

假設父代種群有r 個個體{SEQ1,SEQ2,…,SEQr} ,設定參數(shù)θ ∈(0,1) ,保留r 個個體中最優(yōu)的r × θ 個個體作為子代群體的一部分,即選擇算子。

(2) 交叉算子

以n = 10 為例,假設有2 個父代個體,如式(1)和式(2)所示。

其中,右上角的數(shù)字代表進化代數(shù),定義交叉點為2 個數(shù)字間的位置,對于具有n = 10 個任務的隊列來說,有9 個不同的交叉點,如圖3 所示。

圖3 n=10 任務隊列交叉點示意圖Fig.3 Schematic diagram of task queue intersection when n=10

圖4 交叉算子進化行為示意圖Fig.4 Evolutionary behavior of Crossover operators

(3) 變異算子

一次變異行為發(fā)生在2 個基因之間,個體變異時隨機選取2 個基因位,2 個基因位上的基因互相交換位置產(chǎn)生一個新個體,如圖5 所示。 以第一代個體= {5,8,4,1,3,6,7,2,10,9} 為例,若此時隨機產(chǎn)生的變異基因位為(3,9),則將3 號基因位的基因“4”與9 號基因位的基因“10”交換位置,得到子代個體= {5,8,10,1,3,6,7,2,4,9} 。

圖5 變異算子進化行為示意圖Fig.5 Schematic diagram of evolution behavior of mutation operators

以上3 種遺傳算子既保留了父代群體中的優(yōu)秀基因,也使子代具有產(chǎn)生新優(yōu)秀基因的可能性。 每一次進化產(chǎn)生的子代群體在總體上都優(yōu)于父代群體,隨著進化代數(shù)增加,群體向最優(yōu)解方向收斂。

2.2.2 粒子群算法進化策略

不同于遺傳算法,粒子群算法不通過選擇、交叉和變異產(chǎn)生子代個體,而是通過更新個體位置和速度的方式進行迭代[15]。

假設有r 個個體的第n 代群體SEQn= {} ,針對每個個體,要找到最佳速度vi,使+vi。 傳統(tǒng)粒子群算法中,速度vi由歷代最優(yōu)個體和當代最優(yōu)個體得到。集合{,} 為歷代的最優(yōu)個體,集合{,…} 為第n 代所有個體,為了得到當前進化速度,從{} ∪{,…} 中選取最優(yōu)個體,即第g 代的第h 個個體,其中g ∈[1,n] ,h ∈[1,r] ,且均為整數(shù)。 定義vi=,由+ vi可得下一代個體,該設計思想可使當前個體每次進化時都向更優(yōu)方向前進。

對于資源調(diào)度問題,由于每個個體是一組待調(diào)度任務序列,所以進化速度無法通過簡單的數(shù)學運算得出[16],據(jù)此設計進化策略如圖6 所示。 隨機生成一個基因數(shù)β,在此取β=2 代表每次從最優(yōu)個體中拷貝的連續(xù)基因數(shù)量上限,如圖6 左側(cè)的紅色方框所示。 取父代個體中的第一個基因擺在子代個體基因位1 的位置,在當前最優(yōu)個體中找到該基因,并順位取包括該基因在內(nèi)的連續(xù)β 個基因加入子代個體,然后將加入子代的基因分別從父代個體和當前最優(yōu)個體中刪除,完成一輪循環(huán)。 順位取父代個體中的下一個基因,重復以上操作,直至所有基因全部取完,此時得到子代個體。 依此策略得到的子代個體既保留了父代的部分基因,也學習了當前最優(yōu)個體中的部分基因。 在資源調(diào)度問題中,已將優(yōu)秀基因定義為能得到高資源利用率的基因相對位置[17]。 在圖6 中,學習到了當前最優(yōu)個體中紅框內(nèi)的相對基因位置,即有序集合{2,10},{8,4},{6,7},{3,9},{1},{5} ,同時也保留了父代個體的部分相對基因,即黃色基因序列{2,8,6,3,1,5} ,因此子代個體是在父代個體的基礎上向當前最優(yōu)個體收斂。

圖6 粒子群算法進化示意圖Fig.6 Evolution of PSO

2.3 遺傳-粒子群算法

首先定義個體適應度為特定任務調(diào)度序列下的資源利用率,資源利用率越高,個體適應度值越高,總結(jié)遺傳算法流程、粒子群算法流程如下所示。

(1) 遺傳算法(Algorithm②)

① 編碼并生成初代種群;

② 利用Algorithm①計算種群中個體適應度;

③ 若適應度達到滿意程度,轉(zhuǎn)⑥,否則轉(zhuǎn)④;

④ 對初代種群進行選擇、交叉和變異,得到子代種群;

⑤ 轉(zhuǎn)②;

⑥ 結(jié)束。

(2) 粒子群算法(Algorithm③)

① 編碼并生成初代種群;

② 利用Algorithm①計算種群中個體適應度;

③ 若適應度達到滿意程度,轉(zhuǎn)⑥,否則轉(zhuǎn)④;

④ 向當前最優(yōu)個體進化,得到子代種群;

⑤ 轉(zhuǎn)②;

⑥ 結(jié)束。

遺傳-粒子群算法的整體流程與Algorithm②和Algorithm③一致,不同點是在進化過程中將父代個體按照適應度進行排序,取較優(yōu)部分使用粒子群算法進行進化,其余部分使用遺傳算法進行進化,完成后計算子代個體適應度并排序,將子代個體作為父代個體重新進行迭代計算直到獲得最優(yōu)值,算法示意如圖7 所示,算法流程如下所示。

圖7 遺傳-粒子群算法示意圖Fig.7 Schematic diagram of the genetic-PSO algorithm

(3) 遺傳-粒子群算法(Algorithm④)

① 編碼并生成初代種群;

② 用Algorithm①計算種群中個體適應度;

③ 適應度達到滿意程度,轉(zhuǎn)⑥,否則轉(zhuǎn)④;

④ 較優(yōu)個體使用粒子群算法進行進化,剩余個體使用遺傳算法進行進化,完成后組合得到子代種群;

⑤ 轉(zhuǎn)②;

⑥ 結(jié)束。

3 實驗及結(jié)果分析

針對天基信息網(wǎng)絡資源調(diào)度計算量大、無法快速收斂到最優(yōu)解問題[18],利用傳統(tǒng)遺傳算法、粒子群算法和改進遺傳-粒子群算法分別進行資源調(diào)度實驗,通過對實驗結(jié)果進行分析比較,驗證本文提出的遺傳-粒子群算法具有全局最優(yōu)搜索、計算快速收斂等優(yōu)點。

以表1 所示的任務模型為例,首先使用傳統(tǒng)遺傳算法進行任務調(diào)度,隨機生成100 個任務調(diào)度序列作為初始種群,分三輪進化,每輪在上一輪基礎上進化100 代。 第一輪進化后的最優(yōu)個體為{1,2,3,4,5,6,7,8,9,10} ,剩余任務為{9,10} ,資源利用率為78.125%,如圖8(a)、圖8(d)和圖8(g)所示;第二輪進化后的最優(yōu)個體為{2,9,3,7,5,8,6,1,4,10} ,剩余任務為{4} ,資源利用率為81.25%,如圖8(b),圖8(e)和圖8(h)所示;第三輪進化后得到全局最優(yōu)個體{7,5,1,9,8,2,3,4,6,10} ,無剩余任務,資源利用率為96. 875%,如圖8(c)和圖8(f)所示。

圖8 遺傳算法進化結(jié)果Fig.8 Results of genetic algorithm evolution

任務模型保持不變,初始種群個體數(shù)量保持不變,但分別生成2 個不同的初始種群使用傳統(tǒng)粒子群算法進行任務調(diào)度。 初始種群1 中初代最優(yōu)個體為{3,4,10,7,1,5,8,9,6,2} ,剩余任務為{9,6,2} ,資源利用率為73.437 5%,使用粒子群算法進化,當進化到100 代時結(jié)果已經(jīng)收斂,此時最優(yōu)個體為{1,3,10,7,6,5,2,9,8,4} ,剩余任務為{4,9} ,資源利用率為76.562 5%,如圖9 (a)、圖9(c)和圖9(e)所示。 初始種群2 中初代最優(yōu)個體為{10,1,2,9,5,8,4,3,6,7} ,剩余任務為{7} ,資源利用率為81.25%,使用粒子群算法進化100 代時結(jié)果同樣收斂,此時最優(yōu)個體為{7,9,8,2,3,10,4,1,5,6} ,剩余任務為{6} ,資源利用率為87.5%,如圖9 (b)、圖9(d)和圖9(f)所示。

任務模型保持不變,初始種群個體數(shù)量保持不變,使用改進后的遺傳-粒子群算法進行任務調(diào)度,結(jié)果如圖10(a)和圖10 (b)所示。

種群在第83 代時收斂到最優(yōu)解,到100 代時最優(yōu)解不變,此時的資源利用率為96. 875%,對應任務調(diào)度序列為{7,5,1,9,8,2,3,4,6,10},所有任務均在規(guī)定的時間和頻率范圍內(nèi)獲得相應的資源。

圖9 粒子群算法進化結(jié)果Fig.9 Results of PSO algorithm evolution

圖10 遺傳-粒子群算法進化結(jié)果Fig.10 Results of genetic-PSO algorithm evolution

綜上比較,使用傳統(tǒng)遺傳算法雖然能夠計算得到最優(yōu)解,但受限于進化策略,收斂速度較慢,收斂所需時間至少是遺傳-粒子群算法的3 倍。 粒子群算法雖然能夠快速收斂,但局限于進化策略,整個進化過程受初始種群優(yōu)劣限制,容易陷入局部最優(yōu)解。遺傳-粒子群算法不受初始種群優(yōu)劣限制,具有全局最優(yōu)搜索,高效快速收斂優(yōu)點。

4 結(jié)束語

以天基信息網(wǎng)絡資源調(diào)度問題為背景,針對傳統(tǒng)遺傳算法局部最優(yōu)、無法快速收斂等局限性,提出了一種改進的遺傳-粒子群天基資源調(diào)度算法,將資源調(diào)度問題抽象為任務排序問題,以傳統(tǒng)遺傳算法和粒子群算法為基礎,設計新的十進制編碼方案和種群進化策略以適應資源調(diào)度問題模型,重新定義遺傳算法的選擇、交叉、變異行為以及粒子群算法的進化速度。 通過實驗仿真,將傳統(tǒng)遺傳算法、粒子群算法和改進遺傳-粒子群算法進行對比,結(jié)果證明,改進后的遺傳-粒子群算法具有全局最優(yōu)搜索能力且具有較快的收斂速度,能夠應用于天基資源調(diào)度領域。