基于自適應(yīng)t分布的改進(jìn)粒子群實(shí)時(shí)任務(wù)調(diào)度算法

柳子來 王健敏

（1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院 云南省人工智能重點(diǎn)實(shí)驗(yàn)室；2.云南省農(nóng)村科技服務(wù)中心）

近年來，隨著社會(huì)智能化程度的提高和人工智能技術(shù)的發(fā)展， 信息物理融合系統(tǒng)（Cyber-Physical System，CPS）［1］這種分布式智能系統(tǒng)受到了廣泛關(guān)注。CPS以信息處理為核心，能夠?qū)崿F(xiàn)通信、計(jì)算與控制的高度融合［2］，滿足人類越來越復(fù)雜的智能化需求。

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

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

1 基本概念

1.1 CPS中的實(shí)時(shí)任務(wù)調(diào)度問題

CPS中的實(shí)時(shí)任務(wù)調(diào)度問題本質(zhì)上是多目標(biāo)優(yōu)化組合問題，基本思想是將完整的任務(wù)調(diào)度問題分解為較小的子任務(wù)， 建立任務(wù)與資源的映射，通過在計(jì)算資源上的并行處理，最終完成調(diào)度任務(wù)。 所以，調(diào)度問題的關(guān)鍵是在不同的需求之間進(jìn)行資源共享來減少任務(wù)的完成時(shí)間，使能耗和成本最低，同時(shí)兼顧被分配的計(jì)算資源的服務(wù)能力，實(shí)現(xiàn)整個(gè)系統(tǒng)的負(fù)載均衡。

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

圖1 有向無環(huán)圖任務(wù)調(diào)度模型

為了方便任務(wù)調(diào)度研究，通常會(huì)理想化地假設(shè)節(jié)點(diǎn)間的通信是暢通的，在研究過程中會(huì)重點(diǎn)考慮時(shí)間、成本和服務(wù)質(zhì)量這3個(gè)因素。

1.2 粒子群算法

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

通過適應(yīng)度函數(shù)來選取每次迭代過程中的個(gè)體最優(yōu)位置pi，j和群體最優(yōu)位置gj， 粒子速度與位置的更新公式如下：

其中，k為當(dāng)前迭代次數(shù)；ω為慣性權(quán)重因子，不同的ω值在粒子群進(jìn)化過程中有不同的作用；r1與r2為區(qū)間［0，1］上的隨機(jī)數(shù)；c1與c2為學(xué)習(xí)因子，具體數(shù)值需根據(jù)任務(wù)實(shí)際情況選取，其值代表粒子對自身和群體的學(xué)習(xí)能力的強(qiáng)弱，決定了調(diào)度任務(wù)解的好壞。 粒子的速度與位置需控制在一個(gè)合理的范圍內(nèi)以保證算法的嚴(yán)謹(jǐn)性。

2 基于自適應(yīng)t分布的改進(jìn)粒子群實(shí)時(shí)任務(wù)調(diào)度算法

粒子群算法在處理實(shí)時(shí)任務(wù)調(diào)度問題時(shí)具有效率高、收斂速度快、效果較好的優(yōu)點(diǎn)。 但是因?yàn)榇蟛糠址N群會(huì)在迭代過程中集中在最優(yōu)解的附近，導(dǎo)致種群的多樣性降低，容易陷入局部最優(yōu)， 使得算法在處理多QoS需求的任務(wù)調(diào)度問題時(shí)得不到最優(yōu)解。 為此，筆者通過在粒子群算法中引入自適應(yīng)t分布的變異策略來進(jìn)行粒子群位置的更新，同時(shí)采用改進(jìn)算法的適應(yīng)度函數(shù)與目標(biāo)函數(shù)來滿足任務(wù)調(diào)度的多QoS需求。

2.1 目標(biāo)函數(shù)與適應(yīng)度函數(shù)

CPS實(shí)時(shí)任務(wù)調(diào)度的最主要目標(biāo)是在盡可能短的時(shí)間內(nèi)完成任務(wù)與資源的關(guān)系映射。 基本的任務(wù)調(diào)度算法中，只將任務(wù)完成時(shí)間作為任務(wù)調(diào)度的唯一需求。 筆者在適應(yīng)度函數(shù)的選取上運(yùn)用了多QoS需求的思想，將任務(wù)完成時(shí)間、任務(wù)總成本和服務(wù)質(zhì)量三者作為任務(wù)評價(jià)標(biāo)準(zhǔn)。

任務(wù)完成時(shí)間Time是任務(wù)在整個(gè)CPS資源調(diào)度中花費(fèi)的時(shí)間，其計(jì)算式如下：

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

服務(wù)質(zhì)量Serve是用來衡量計(jì)算資源服務(wù)能力的標(biāo)準(zhǔn)， 好的服務(wù)質(zhì)量對應(yīng)著好的用戶滿意度，具體計(jì)算式如下：

為了實(shí)現(xiàn)對任務(wù)完成時(shí)間、任務(wù)總成本和服務(wù)質(zhì)量的統(tǒng)一權(quán)衡，在目標(biāo)函數(shù)中引入了加權(quán)模型：

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

其中，Dmax表示最大迭代次數(shù)，Dnow表示當(dāng)前迭代次數(shù)。 選取式（6）作為本文算法的適應(yīng)度函數(shù)，通過該函數(shù)來計(jì)算粒子每一次位置更新后的適應(yīng)度值，以此作為標(biāo)準(zhǔn)來進(jìn)行粒子群個(gè)體最優(yōu)與全局最優(yōu)的更新，迭代完成后，獲得的最優(yōu)群體即為最優(yōu)解。

2.2 自適應(yīng)t分布變異策略

t分布是統(tǒng)計(jì)學(xué)與概率論中的一類重要分布類型，目前廣泛應(yīng)用于諸多領(lǐng)域。 t分布的曲線形態(tài)與參數(shù)自由度有關(guān)：自由度nt越大，曲線形態(tài)表現(xiàn)越高聳，曲線接近于標(biāo)準(zhǔn)正態(tài)分布曲線；當(dāng)自由度nt無限大時(shí)，t分布為高斯分布，即t（nt→∞）→N（0，1）；自由度nt越小，曲線形態(tài)表現(xiàn)越低平；當(dāng)自由度nt=1時(shí)，t分布為柯西分布，即t（nt=1）→C（0，1）。

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

自適應(yīng)因子η的計(jì)算式為：

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

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

其中，t（D）是以算法迭代次數(shù)D為參數(shù)自由度的t分布。式（10）是在當(dāng)前粒子個(gè)體位置的基礎(chǔ)上增加了自適應(yīng)t分布的變異干擾項(xiàng)η·t（D）。迭代初期D值較小， 此時(shí)的變異干擾項(xiàng)可視為柯西變異，使得算法保持了粒子群種群的多樣性，具有良好的全局探索能力，此時(shí)變異干擾項(xiàng)發(fā)揮的作用最大，有助于算法跳出局部最優(yōu)；當(dāng)算法進(jìn)入運(yùn)行后期，變異干擾項(xiàng)變?yōu)楦咚狗植甲儺悾岣吡怂阉骶?，加快了收斂速度，此時(shí)算法擁有較強(qiáng)的局部探索能力，同時(shí)變異干擾項(xiàng)的作用逐漸減小，當(dāng)達(dá)到最大迭代次數(shù)時(shí)，變異干擾項(xiàng)的作用最小。

2.3 算法流程

基于自適應(yīng)t分布的改進(jìn)粒子群實(shí)時(shí)任務(wù)調(diào)度算法的基本執(zhí)行步驟如下：

a. 初始化粒子群調(diào)度算法的各項(xiàng)基本參數(shù)；

b. 將式（6）中加權(quán)模型的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)；

c. 根據(jù)適應(yīng)度函數(shù)對初始粒子進(jìn)行適應(yīng)度評價(jià)，找出群體當(dāng)前的pi，j與gj；

d. 隨機(jī)設(shè)定粒子的初始速度，初始位置則設(shè)為當(dāng)前的個(gè)體最優(yōu)，根據(jù)式（1）、（2）更新粒子速度與位置；

e. 根據(jù)式（10）對粒子位置進(jìn)行自適應(yīng)t分布變異；

f. 計(jì)算粒子進(jìn)行自適應(yīng)t分布變異后的適應(yīng)值，根據(jù)適應(yīng)值的好壞更新粒子群的個(gè)體最優(yōu)與群體最優(yōu)；

g. 判斷算法是否達(dá)到最大迭代次數(shù)，若沒達(dá)到則跳轉(zhuǎn)至步驟d，若達(dá)到則輸出CPS調(diào)度結(jié)果。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)仿真環(huán)境及參數(shù)設(shè)置

使用云計(jì)算仿真平臺CloudSim作為調(diào)度實(shí)驗(yàn)的仿真器，通過在Datacenter Broker類中添加調(diào)度算法來完成實(shí)驗(yàn)仿真。 為了避免仿真平臺在處理自定義任務(wù)時(shí)產(chǎn)生差異性， 實(shí)驗(yàn)利用CloudSim自帶的PlanLab工作流來進(jìn)行任務(wù)調(diào)度。 PlanLab工作流中共有9個(gè)調(diào)度任務(wù)，本實(shí)驗(yàn)隨機(jī)選取其中6個(gè)。 仿真實(shí)驗(yàn)采用樹狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，與實(shí)際云計(jì)算虛擬機(jī)資源拓?fù)浣Y(jié)構(gòu)保持一致。

3.2 性能分析

3.2.1 收斂性能及任務(wù)完成性能

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

圖2 收斂性能及任務(wù)完成性能仿真實(shí)驗(yàn)結(jié)果

3.2.2 調(diào)度性能

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

傳統(tǒng)的粒子群算法因?yàn)橹魂P(guān)注任務(wù)完成時(shí)間一個(gè)標(biāo)準(zhǔn)，導(dǎo)致在其他方面表現(xiàn)良好的部分粒子丟失， 因此在進(jìn)行多目標(biāo)優(yōu)化性能時(shí)表現(xiàn)不好。 柯西變異粒子群算法因?yàn)榭挛鞣植嫉木窒扌?，?dǎo)致算法不穩(wěn)定，在個(gè)別任務(wù)上出現(xiàn)了負(fù)優(yōu)化的情況。 而本文算法在目標(biāo)函數(shù)中加入了任務(wù)完成時(shí)間、 任務(wù)總成本和服務(wù)質(zhì)量這3個(gè)衡量標(biāo)準(zhǔn)，同時(shí)引入了自適應(yīng)t分布的變異策略，解決了粒子群算法存在的收斂過慢和容易陷入局部最優(yōu)的問題， 使得本文算法在處理CPS任務(wù)調(diào)度時(shí)具有更好的整體性能。

4 結(jié)束語

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