基于遺傳和粒子群算法的天基資源調度策略

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

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

0 引言

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

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

1 資源調度問題模型抽象

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

圖1 任務資源調度問題示意圖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 范圍內,盡可能多地滿足任務資源需求,即追求時間、頻率資源利用率最高。 將問題抽象在圖1(b)所示的藍色透明區域D 內,盡可能多地擺放任務塊,使D 內的剩余面積最小。 為便于描述,將任務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

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

調度算法(Algorithm①)

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

① k=1;

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

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

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

⑤ k=k+1,轉②;

⑥ 結束;

輸出：SEQ=?,NSEQ={不可擺放任務},為當前序列任務調度結果。

2 基于遺傳和粒子群的資源調度改進方法

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

2.1 編碼方案選擇

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

2.2 進化策略設計

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

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

2.2.1 遺傳算法進化策略

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

(1) 選擇算子

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

(2) 交叉算子

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

其中,右上角的數字代表進化代數,定義交叉點為2 個數字間的位置,對于具有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) 變異算子

一次變異行為發生在2 個基因之間,個體變異時隨機選取2 個基因位,2 個基因位上的基因互相交換位置產生一個新個體,如圖5 所示。 以第一代個體= {5,8,4,1,3,6,7,2,10,9} 為例,若此時隨機產生的變異基因位為(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 種遺傳算子既保留了父代群體中的優秀基因,也使子代具有產生新優秀基因的可能性。 每一次進化產生的子代群體在總體上都優于父代群體,隨著進化代數增加,群體向最優解方向收斂。

2.2.2 粒子群算法進化策略

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

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

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

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

2.3 遺傳-粒子群算法

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

(1) 遺傳算法(Algorithm②)

① 編碼并生成初代種群;

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

③ 若適應度達到滿意程度,轉⑥,否則轉④;

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

⑤ 轉②;

⑥ 結束。

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

① 編碼并生成初代種群;

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

③ 若適應度達到滿意程度,轉⑥,否則轉④;

④ 向當前最優個體進化,得到子代種群;

⑤ 轉②;

⑥ 結束。

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

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

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

① 編碼并生成初代種群;

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

③ 適應度達到滿意程度,轉⑥,否則轉④;

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

⑤ 轉②;

⑥ 結束。

3 實驗及結果分析

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

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

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

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

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

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

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

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

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

4 結束語

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