基于自適應t分布的改進粒子群實時任務調度算法

柳子來 王健敏

（1.昆明理工大學信息工程與自動化學院 云南省人工智能重點實驗室；2.云南省農村科技服務中心）

近年來，隨著社會智能化程度的提高和人工智能技術的發展， 信息物理融合系統（Cyber-Physical System，CPS）［1］這種分布式智能系統受到了廣泛關注。CPS以信息處理為核心，能夠實現通信、計算與控制的高度融合［2］，滿足人類越來越復雜的智能化需求。

CPS相較于傳統的分布式系統具有資源異構性強［3］、感知實時性高和網絡動態拓撲的特點，這使得傳統任務調度算法無法滿足CPS中實時任務調度與分配的需求。隨著CPS應用環境的擴展，如何高效地完成調度任務，同時滿足用戶多種服務質量（Quality of Services，QoS）需求，成為了目前CPS中亟待解決的問題。近年來，許多啟發式算法都被用來解決此類任務調度問題。 文獻［4］使用粒子群算法來處理CPS的資源調度問題， 通過在粒子更新中使用自適應的萊維飛行策略來進一步更新位置，提高全局搜索能力，達到優化的目的。 文獻［5］通過結合果蠅算法與遺傳算法的優點，提出了一種融合調度算法，該算法針對果蠅種群采用正交數組和量化技術進行初始化，對探索步長進行動態調整，并使用遺傳算法對個體進行了選擇處理，改進后的算法具有更高的效率和資源利用率。 文獻［6］提出了一種基于改進粒子群優化算法的任務調度算法，通過考察任務調度中的平均調度長度與成功執行的比率來生成最優解。 但是上述調度算法普遍存在用戶QoS研究單一、各性能指標考慮不足的問題，而優化算法也存在優化性能不足的問題，沒有達到同時提高收斂速度與避免局部最優的目的。

為此，筆者提出一種基于自適應t分布的改進粒子群實時任務調度算法。 以經典粒子群算法為基礎，在粒子位置更新時引入了自適應t分布的變異策略，借此來提高收斂速度并避免算法陷入局部最優。 同時在充分考慮任務調度多QoS需求的條件下，以任務完成時間、任務總成本和服務質量為衡量標準來設置適應度函數，在優化任務完成時間的前提下， 盡可能地控制任務總成本、降低資源消耗、減少資源傳輸成本，同時提高資源的服務質量，使得算法在處理任務調度問題時表現出更好的性能。

1 基本概念

1.1 CPS中的實時任務調度問題

CPS中的實時任務調度問題本質上是多目標優化組合問題，基本思想是將完整的任務調度問題分解為較小的子任務， 建立任務與資源的映射，通過在計算資源上的并行處理，最終完成調度任務。 所以，調度問題的關鍵是在不同的需求之間進行資源共享來減少任務的完成時間，使能耗和成本最低，同時兼顧被分配的計算資源的服務能力，實現整個系統的負載均衡。

CPS實時任務調度問題可以通過構建有向無環圖（Directed Acyclic Graph，DAG）任務調度模型 表 示［7］，如 圖1 所 示。 一 般 表 示 為DAG=（T，E），其中T=｛t1，t2，t3，…，tm｝是執行任務節點的集合，m是需要執行的任務總數；E=｛eij｜eij=＜ti，tj＞，eij∈T×T｝是DAG任務調度模型中的有向邊，有向邊連接的兩個節點具有依賴關系。 如果eij∈E，則表示任務ti與tj之間存在依賴關系，tj必須在ti之前完成。在CPS中，DAG中的邊就代表一個通信開銷。

圖1 有向無環圖任務調度模型

為了方便任務調度研究，通常會理想化地假設節點間的通信是暢通的，在研究過程中會重點考慮時間、成本和服務質量這3個因素。

1.2 粒子群算法

粒子群算法［8］是一種受到自然界動物行為啟發而產生的智能優化算法。 粒子群算法在處理實時任務調度問題時，可以把每一個粒子看成是調度過程中一個合理的調度方案，通過在尋優過程中對每一個粒子的適應度值進行計算與評價，并根據結果來進行速度與位置更新，以獲取粒子種群和個體的最優位置，最終逼近任務調度的最優調度方案。根據CPS任務調度的實際需要，用粒子群算法處理任務調度問題時，需要將粒子位置和速度進行實例化定義， 假設粒子在一個K維任務空間搜索最優解，則任務調度的可行解可以用粒子的位置和速度來表示，即Xi=（xi1，xi2，xi3，…，xiK），Vi，j=（v1，1，v1，2，v1，3，…，vi，j）。

通過適應度函數來選取每次迭代過程中的個體最優位置pi，j和群體最優位置gj， 粒子速度與位置的更新公式如下：

其中，k為當前迭代次數；ω為慣性權重因子，不同的ω值在粒子群進化過程中有不同的作用；r1與r2為區間［0，1］上的隨機數；c1與c2為學習因子，具體數值需根據任務實際情況選取，其值代表粒子對自身和群體的學習能力的強弱，決定了調度任務解的好壞。 粒子的速度與位置需控制在一個合理的范圍內以保證算法的嚴謹性。

2 基于自適應t分布的改進粒子群實時任務調度算法

粒子群算法在處理實時任務調度問題時具有效率高、收斂速度快、效果較好的優點。 但是因為大部分種群會在迭代過程中集中在最優解的附近，導致種群的多樣性降低，容易陷入局部最優， 使得算法在處理多QoS需求的任務調度問題時得不到最優解。 為此，筆者通過在粒子群算法中引入自適應t分布的變異策略來進行粒子群位置的更新，同時采用改進算法的適應度函數與目標函數來滿足任務調度的多QoS需求。

2.1 目標函數與適應度函數

CPS實時任務調度的最主要目標是在盡可能短的時間內完成任務與資源的關系映射。 基本的任務調度算法中，只將任務完成時間作為任務調度的唯一需求。 筆者在適應度函數的選取上運用了多QoS需求的思想，將任務完成時間、任務總成本和服務質量三者作為任務評價標準。

任務完成時間Time是任務在整個CPS資源調度中花費的時間，其計算式如下：

任務總成本Cost包括任務執行成本和任務傳輸成本，CPS中的任務要盡可能消耗最低的成本來保證任務的完成，具體計算式如下：

服務質量Serve是用來衡量計算資源服務能力的標準， 好的服務質量對應著好的用戶滿意度，具體計算式如下：

為了實現對任務完成時間、任務總成本和服務質量的統一權衡，在目標函數中引入了加權模型：

其中，α、β、γ 分別表示任務完成時間、任務總成本和服務質量的加權系數。 考慮算法在迭代過程中，前期以任務完成時間為主要目標，而隨著迭代的進行，任務總成本和服務質量成為了更重要的目標， 所以針對算法各階段的不同目標，對加權系數進行進一步的調整與改進，具體如下：

其中，Dmax表示最大迭代次數，Dnow表示當前迭代次數。 選取式（6）作為本文算法的適應度函數，通過該函數來計算粒子每一次位置更新后的適應度值，以此作為標準來進行粒子群個體最優與全局最優的更新，迭代完成后，獲得的最優群體即為最優解。

2.2 自適應t分布變異策略

t分布是統計學與概率論中的一類重要分布類型，目前廣泛應用于諸多領域。 t分布的曲線形態與參數自由度有關：自由度nt越大，曲線形態表現越高聳，曲線接近于標準正態分布曲線；當自由度nt無限大時，t分布為高斯分布，即t（nt→∞）→N（0，1）；自由度nt越小，曲線形態表現越低平；當自由度nt=1時，t分布為柯西分布，即t（nt=1）→C（0，1）。

為了在粒子群算法中引入自適應t分布的變異策略，筆者先設置自適應因子η，然后在算法中粒子位置更新時進行t分布的變異操作，利用自適應因子η來控制變異程度， 最終通過這種自適應變異策略來達到優化效果。

自適應因子η的計算式為：

其中，D為算法迭代次數；pk為限制因子，用于控制迭代開始階段的變異幅度， 避免幅度過大，造成結果的不可控；在迭代過程中η的值在1到0之間非線性減小，在迭代初期，自適應因子η發揮作用最大，隨著迭代的進行，自適應因子η的作用逐漸減小。

對粒子群中粒子個體Xi，j=（x1，1，x1，2，x1，3，…，xi，j）采用自適應t分布的變異策略，具體如下：

其中，t（D）是以算法迭代次數D為參數自由度的t分布。式（10）是在當前粒子個體位置的基礎上增加了自適應t分布的變異干擾項η·t（D）。迭代初期D值較小， 此時的變異干擾項可視為柯西變異，使得算法保持了粒子群種群的多樣性，具有良好的全局探索能力，此時變異干擾項發揮的作用最大，有助于算法跳出局部最優；當算法進入運行后期，變異干擾項變為高斯分布變異，提高了搜索精度，加快了收斂速度，此時算法擁有較強的局部探索能力，同時變異干擾項的作用逐漸減小，當達到最大迭代次數時，變異干擾項的作用最小。

2.3 算法流程

基于自適應t分布的改進粒子群實時任務調度算法的基本執行步驟如下：

a. 初始化粒子群調度算法的各項基本參數；

b. 將式（6）中加權模型的目標函數作為適應度函數；

c. 根據適應度函數對初始粒子進行適應度評價，找出群體當前的pi，j與gj；

d. 隨機設定粒子的初始速度，初始位置則設為當前的個體最優，根據式（1）、（2）更新粒子速度與位置；

e. 根據式（10）對粒子位置進行自適應t分布變異；

f. 計算粒子進行自適應t分布變異后的適應值，根據適應值的好壞更新粒子群的個體最優與群體最優；

g. 判斷算法是否達到最大迭代次數，若沒達到則跳轉至步驟d，若達到則輸出CPS調度結果。

3 實驗結果及分析

3.1 實驗仿真環境及參數設置

使用云計算仿真平臺CloudSim作為調度實驗的仿真器，通過在Datacenter Broker類中添加調度算法來完成實驗仿真。 為了避免仿真平臺在處理自定義任務時產生差異性， 實驗利用CloudSim自帶的PlanLab工作流來進行任務調度。 PlanLab工作流中共有9個調度任務，本實驗隨機選取其中6個。 仿真實驗采用樹狀網絡拓撲結構，與實際云計算虛擬機資源拓撲結構保持一致。

3.2 性能分析

3.2.1 收斂性能及任務完成性能

分別采用PSO、Cauchy-PSO［9］和t-PSO這3種算法進行收斂性能與任務完成性能的對比實驗，以此對算法的性能作出判斷，并根據結果來衡量算法的優化程度，結果如圖2所示。 可以看出，隨著迭代次數的增加，t-PSO的收斂速度與收斂時間都優于PSO、Cauchy-PSO算法。 而在任務完成性能上，t-PSO更是表現出極大的優勢， 具有更短的任務完成時間。 可見，在粒子群算法中加入自適應t分布變異策略，可使改進后的算法表現出更好的收斂性，具有更短的任務完成時間，能有效解決PSO算法易陷入局部最優的問題。

圖2 收斂性能及任務完成性能仿真實驗結果

3.2.2 調度性能

圖3分別比較了3種算法的執行成本、總成本和服務質量。 總成本與服務質量是衡量本文算法調度性能的兩個重要因素。 通過圖3可知，在處理不同的CPS實時任務調度問題時，t-PSO算法更能滿足用戶的多QoS需求， 在各個方面的尋優性能均優于PSO、Cauchy-PSO算法。

傳統的粒子群算法因為只關注任務完成時間一個標準，導致在其他方面表現良好的部分粒子丟失， 因此在進行多目標優化性能時表現不好。 柯西變異粒子群算法因為柯西分布的局限性，導致算法不穩定，在個別任務上出現了負優化的情況。 而本文算法在目標函數中加入了任務完成時間、 任務總成本和服務質量這3個衡量標準，同時引入了自適應t分布的變異策略，解決了粒子群算法存在的收斂過慢和容易陷入局部最優的問題， 使得本文算法在處理CPS任務調度時具有更好的整體性能。

4 結束語

筆者對CPS實時任務調度問題進行了研究，提出了一種改進的任務調度算法。 針對傳統粒子群算法存在容易陷入局部最優的問題，通過引入自適應t分布的變異策略對算法做了改進；CPS實時任務調度中通常只以單一的任務完成時間為標準， 筆者將改進后的粒子群算法作為調度策略，然后從任務完成時間、任務總成本和服務質量3個因素出發去完成任務調度。 實驗結果表明：本文算法在處理CPS任務調度問題時具有良好的效果，在任務完成時間、任務總成本和服務質量3個方面都有所優化，滿足了CPS任務調度的多QoS需求。 另外，針對算法中出現的傳輸成本優化問題，今后將作進一步的研究與改進。