基于逆向學習行為粒子群算法的云計算大規模任務調度

賴兆林， 馮 翔， 虞慧群

（華東理工大學計算機科學與工程系，上海 200237）

云計算是一種新的計算模型和服務模式[1]，融合了網絡及計算機技術，實現資源共享和按需訪問，并為基礎設施、平臺和軟件(應用)服務。當用戶應用程序需要服務時，它可動態地提供盡可能多的計算資源。與此同時，應用程序可以選擇其數據存儲在哪些服務器上，使得用戶能更好地掌控自己的數據。云計算的原理是以網絡的方式將較大的計算程序拆分成一系列小的子程序，然后通過服務器集群計算后的結果傳給用戶[2]。例如Google的Map/Reduce框架就是采用這種技術，TB級的數據可在數秒內被處理完成，從而實現了與超級計算機同樣功效的服務[3]。

在商業應用中，可采用離線方式的有數據挖掘和數據存儲等，而對于實時性要求較高的應用，例如交易處理及電子商務，都要求系統盡可能在較短時間內處理完提交的任務。然而，通常情況下，用戶所請求的服務數量比較大，因此，為了使系統能快速響應用戶請求，任務調度算法起著至關重要的作用。與此同時，設計有效的調度算法，使得整個系統達到最優，成為云計算研究的難點[4]。

云計算中的任務調度問題屬于NP完全問題[5]。智能優化算法很適合求解此類問題[6]，例如遺傳算法（GA）、蟻群優化(ACO)算法、粒子群優化(PSO)算法和布谷鳥搜索算法(CSA)等，且這些算法已被應用于解決云計算任務調度問題，并取得一定的效果。文獻[7]采用GA算法實現了云計算中獨立任務的有效調度。文獻[8]利用ACO算法優化了云計算的總任務及平均任務完成時間；文獻[9]提出了基于PSO的調度算法，使得云計算任務的處理時間及傳輸時間最小；文獻[10]使用布谷鳥搜索算法對云計算任務的總響應時間進行了優化。任何優化算法都有其優點和不足。例如，GA算法的時間開銷小及魯棒性高，而不足之處是容易陷入早熟收斂[11]；ACO算法具有較好的搜索能力，但計算量大，收斂速度慢[12]；PSO算法實現容易、需要設置的參數少及收斂速度快，但迭代后期局部尋優性能不足[13]；CSA算法計算速度快，但存在全局尋優性能與局部尋優性能不平衡的缺陷[14]。

智能優化算法的共同特征在于模擬自然行為，且每一個算法都具有其優缺點[15]。此外，文獻[15]指出不存在任何一個算法可以解決所有的優化問題，某一算法可能在某些問題上表現出色，但是在另一問題上其性能不佳。因此，為了提升智能優化算法的優化性能，一些研究者提出了新的優化算法。Li等[16]受動物遷徙行為啟發，提出了動物遷徙優化(BBO)算法；Zhang等[17]通過模擬自然界中植物根系生長行為，提出了根生算法(RGA)；Feng 等[18]以社會群理論為基礎，提出了社會群熵優化(SGEO)算法。還有一些學者通過改進已有算法來提升優化算法的性能。Zhan等[19]在PSO算法基礎上采用正交學習策略，提出了正交學習粒子群(OLPSO)算法；Chen等[20]把衰老機制引入PSO算法中，提出了老化領導者的PSO(ALC-PSO)算法；Qin等[21]基于PSO引入群內交互學習策略，提出了群內交互學習PSO (IILPSO)算法。PSO算法作為較為經典的智能優化算法，最近幾年依然有不少學者對其進行研究并改進。Dong等[22]受機器學習中的監督學習和控制領域中的預測控制策略啟發，提出了一種基于監督學習控制的自適應粒子群優化(APSO-SLC)算法；Gong等[23]通過采用遺傳算子來生成粒子學習的范例，提出了一種遺傳學習粒子群(GL-PSO)算法；Lin等[24]通過設計一種平衡適應度估計方法和一種新的粒子速度更新公式，提出了一種新的多目標粒子群優化(NMPSO)算法。

本文受文獻[25]中生物以性別分群及文獻[26]中蜜蜂逆向學習行為的啟發，提出了一種逆向學習行為粒子群優化(RLPSO)算法，并應用到云計算任務調度問題上。該算法在傳統粒子群算法基礎上，首先把整個種群劃分為雄性群體和雌性群體，然后引入逆向學習行為。這兩種機制有助于提升算法搜索能力，并且可以加快算法收斂速度。在云計算任務調度問題上，與4個經典的智能優化算法相比，RLPSO算法在大規模任務調度時，總任務時間減少，并且提升了任務調度效率。

1 云計算調度問題模型化

粒子的編碼主要有兩種方式，一種是直接編碼(即一個粒子代表一個可行解)；另一種是間接編碼(即一個粒子表示一種任務調度策略), 本文使用間接編碼。

假設云計算下的任務數為Tn，資源數為Rn，子任務總數為Sn。由于每個任務劃分為多個子任務，從而有子任務的總數大于任務數。子任務數與每個任務數的關系如式(1)所示：

其中，Hn(i)表示第i個任務包含子任務的數目。

使用順序法對子任務進行編碼，其公式如下：

其中，D[r, c]表示第c個任務中的第r個子任務。

假設Tn=3，Rn=3，Sn=10，并且粒子(2, 1, 3, 1, 3, 1,2, 1, 3, 2)是可行的調度，圖1示出了粒子編碼及解碼示意圖。對于編碼過程，其任務、子任務對(2, 6)表示第2個任務的第3個子任務編號為6；子任務、資源對(6, 1)表示把子任務6分配給資源1執行。對于解碼過程，資源1上執行的子任務是{2, 4, 6, 8}，資源2上執行的子任務是{1, 7, 10}，資源3上執行的子任務是{3, 5, 9}。

圖 1 粒子編碼解碼示例圖Fig. 1 Example of particle coding and decoding

完成全部任務的總時間如下：

其中：Utime(k, i)表示第k個資源執行第i個子任務所需的時間開銷；m表示分配給該資源的子任務數目。

從式(3)可知，完成一組任務的可行調度總時間為Otime，由于一組任務的可行調度對應于優化算法中的一個解xi(粒子), 因此，完成全部任務的總時間轉換為優化問題的目標函數為

2 改進的粒子群算法

2.1 PSO算法

PSO算法[27]是研究者受鳥群的集體行為啟發提出的一種自然啟發式算法。該算法模擬了自然界中鳥群捕食行為，從而建立具有群體智能的簡單模型。整個群體中的個體共享最優個體信息，其他個體往最優個體方向移動，使得種群逐步趨于最優。

PSO算法把待優化的目標函數的解看作是搜索空間里的一個粒子，在搜索過程中，通過適應值來評價個體的優劣。每個個體的位置更新由其速度和距離決定。初始狀態下，PSO中的個體隨機分布在搜索空間內，通過迭代的方式搜索最優解。每次迭代時，個體在更新自己的位置之前，獲取群體當前最優個體位置及本身歷史最優位置，以此調整自己的飛行方向。隨著迭代次數的增加，群體內的其他個體逐漸接近最優個體。當達到終止條件時，整個算法停止搜索，此時，群體內最優個體位置即是該算法得到的最優解。個體位置更新公式如下:

其中： xk(t) 為個體k在第t次迭代時的位置；Vk(t)為該個體的速度；pk(t)為個體k搜索到的局部最優位置；G(t)為全局最優位置；w為慣性權重；c1和c2表示加速常數；r1和r2表示[0, 1]范圍的均勻隨機數[28]。

2.2 RLPSO算法

文獻[25]對物種的多樣性及雌雄個體之間繁殖后代時的擇偶條件等進行了研究，本文以此作為劃分粒子群算法的依據，把粒子群中的個體按照生物性別劃分為兩個群，即雄性子群和雌性子群，不同子群內的個體將執行不同的學習行為。

定義1 (個體分群) 設M表示雌性，F表示雌性，I表示整個種群個體。對于 ? i∈I ，則有(gender(i)∈M)∧(gender(i) ? F)或 者(gender(i) ∈F)∧(gender(i) ?M)成立。即個體性別具有唯一性，任意一個個體，或者被劃分到雄性子群，或者被劃分到雌性子群，不能同時存在于兩個不同子群。若整個種群內個體數為N，則雄性子群內個體數Nm=[N/2]，雌性子群內個體數Nf=N-Nm。分群機制如圖2所示。

受文獻[26]中逆向學習行為啟發，生物個體具有逆向學習能力，因此，RLPSO算法內個體除了正向學習之外，以一定概率進行逆向學習。

定義2 (個體學習目標) 對于種群內的任意個體i，其搜索行為受學習目標個體影響。雄性個體的學習目標為雄性子群內最優個體Mb及雌性子群內最優個體Fb，而雌性個體的學習目標為雌性子群內最優個體Fb。

定義3 (個體學習方向) 對于種群內的任意個體i，不管是雄性個體還是雌性個體，都有正向學習行為和逆向學習行為兩種模式。設μ(0＜μ＜1)為種群內個體的方向選擇概率，rand為產生均勻分布隨機數的函數。若rand＞μ，個體選擇逆向學習方向；反之，個體選擇正向學習方向。在搜索空間內，個體搜索方式及學習方向的選擇如圖3所示。

圖 3 個體的搜索方式及學習方向Fig. 3 Search mode and learning direction of individual

定義4（雄性個體搜索行為） 由定義2可知，雄性個體選擇個體Mb和Fb作為學習目標，由定義3可知，個體有兩種學習方向。從而有，當rand＞μ時，個體根據式(7)進行更新位置；當rand≤μ時，個體根據式(8)進行更新位置。

定義5（雌性個體搜索行為） 由定義2可知，雌性個體只選擇個體Fb作為學習目標，即學習目標單一性。雌性個體與雄性個體位置更新方式類似，當rand＞μ時，個體根據式(9)進行更新位置；當rand≤μ時，個體根據式(10)進行更新位置。

定義6（繁殖行為） 種群內個體繁殖的目的在于通過產生更優的新生個體替換劣解個體，使得整個種群往更優趨勢演化。對于每一輪迭代，任意選擇一個雄性個體i，與此同時，個體i將等概率地從雌性子群中選擇一個雌性個體j作為繁殖對象，通過繁殖操作，將有一個新的個體xnew產生。繁殖行為如圖4所示。

圖 4 個體繁殖行為Fig. 4 Reproductive behavior of individual

假設搜索空間內最小邊界為Lb，最大邊界為Ub，則新生個體在搜索空間中的位置計算公式如下：

若新生個體的適應值fobejct(xnew)優于種群內最差個體fobejct(xworst)，則淘汰最差個體xworst，并用新生個體xnew替換。反之，若新生個體適應值遜于最差個體，則拋棄新生個體。

由式(11)可知，新生個體可在搜索空間內任一位置產生。對于具有多個極值的問題（即多峰問題），當算法收斂于某個非最優的極值點附近時，借助于新生個體在搜索空間的其他區域產生的方式，可加強算法跳出局部最優的能力。RLPSO算法的偽代碼如下：

Input：population size N，iterative number Gn, and parameter μ

Output：The best fitness value and the best task sequence

（1）Initialization；

（2）Generate N individuals randomly；

（3）Set the numbers of females equal to males；

（4）Encoding initial task sequences；

（5）For k=1 to Gn

（6） For i=1 to N

（7） If xiis a male individual

（8） If rand＞μ

（9） Updating position by Eq. (8)；

（10） Else

（11） Updating position by Eq. (9)；

（12） End if

（13） If xiis a female individual

（14） If rand＞μ

（15） Updating position by Eq. (10)；

（16） Else

（17） Updating position by Eq. (11)；

（18） End if

（19） End For

（20） Performing reproductive operation；

（21） Recording the best fitness value and the best position of individual

（22）End For

（23）Decoding the best position；

（24）Return

2.3 收斂性證明

式(7)～式(10)中 Vk(t+1) 和 xk(t+1) 是 多 維 變量，每個維度之間相互獨立，故可簡化到一維進行證明，并且變量 c1r1可表示成 K1, c2r2可表示成 K2。

引理1 當種群內個體往逆向方向學習時，其位置更新公式滿足收斂性。

證明 設

式(8)和式(10)可簡化為

當式(12)中的K2及Mb都等于0時，式(13)即為簡化的式(9)。即通過式(13)來同時代表簡化的式(7)和式(9)是合理的。

根據動力系統理論，式(13)可重寫為

在動力系統y(t+1)中， 若存在一個穩定值 y*，對于 任 意 的t，滿 足 y*(t+1)=y*(t) ，則 y*可 根 據 式(12)和式(13)計算得

從動力學理論可知，其收斂性取決于狀態矩陣A的特征值。

其中，特征值為

動力系統收斂的充分必要條件是 | λ1|＜1 和 | λ2|＜1 ，由 w ＞0 ， c1r1＞0 ， c2r2＞0 ，可 得 | λ1|＜1 且 | λ2|＜1 。從而可證個體進行逆向學習時，其位置移動公式是收斂的。

引理2 當種群內個體往正向方向學習，其位置更新公式滿足收斂性。

證明 設

與引理1證明過程相似，其狀態矩陣的特征值與 式（17）相似，不同的是， θ 的負值即 θ′，如式（19）所示。

動力系統收斂的充分必要條件是 | λ1′|＜1 和 | λ2′|＜1 ，由 w ＞0 ， c1r1＞0 ， c2r2＞0 ，可 得 | λ1′|＜1 且 | λ2′|＜1 ，即成熟個體位置相斥移動公式是收斂的，從而可證個體進行逆向學習時，其位置移動公式是收斂的。

定理1 RLPSO算法是收斂的。

證明 根據引理1和引理2，可得RLPSO算法內所有個體的移動都將收斂于穩定狀態點，即算法滿足收斂性。

3 仿真實驗

3.1 實驗環境及算法參數設置

采用云計算仿真通用平臺CloudSim，仿真環境中，計算機的配置環境:操作系統為Windows 10, 內存16 GB，硬盤1TB。資源數量Rn為50, 任務數量Tn分別為100、500、1 000。將RLPSO算法分別與閃電搜索算法(LSA)、粒子群算法(PSO)、遺傳算法(GA)、蟻群算法(ACO)4個經典智能優化算法進行比較。5種優化算法的種群規模都為50，迭代次數為200，每個算法分別運行25次。其余參數設置為：(1)PSO算法，慣性權重因子w=1.0，c1和c2取值為2.0[29]；(2)LSA的通道時間設置為10[30]；(3)ACO算法的信息素因子為1.0×10-6、啟發函數因子為0.9、信息素揮發因子為0.5、信息素常數為20[31]；(4)GA算法的交叉概率為0.65，變異概率為0.01[32]；(5)為了比較RLPSO與經典PSO的性能，RLPSO的參數w、c1、c2設置與PSO的相同。此外，RLPSO的方向選擇概率μ設為0.6。為了客觀評價本文算法的性能，采用兩個非參數統計技術(Wilcoxon's Test和Friedman Test)對5種算法得到的數據進行性能分析，顯著性水平為0.05[33]。

3.2 RLPSO參數擇優

經典PSO有3個參數（w、c1、c2），而RLPSO比經典PSO多一個參數(即方向選擇概率μ)。RLPSO中w、c1、c2的設置與文獻[30]相同，因此，本文只對參數μ進行擇優。選用8個基準測試函數作為案例。為了盡量覆蓋不同屬性的基準測試函數，選擇了4個單模函數(f1～f4)和4個多模函數(f5～f8)，即不同屬性的測試函數各占一半。這些基準測試函數的詳細描述如表1所示。圖5示出了8個基準測試函數在三維空間的分布。從圖中可以看到，單模函數只有一個最小值，而多模函數有多個極值。

由定義3可知，RLPSO的方向選擇概率μ的取值范圍為(0,1)，因此，在參數擇優過程中，把μ分別設成0.1～0.9(間隔大小為0.1)。對于每個不同的μ，RLPSO在基準測試函數上得到的目標函數值如表2所示。可以看到，當μ=0.6時，RLPSO在f1、f3、f4、f5、f6、f86個函數上表現出最佳性能。對于f2函數，μ=0.7時RLPSO搜索到最優值為3.04×10-2，而μ=0.6時RLPSO得到的最優值為3.47 ×10-2，只比3.04 ×10-2稍微遜色一點。對于f7函數，μ=0.5時結果最好，μ=0.6次之。由于μ=0.6時在大部分函數上都能得到最優結果，表明在該參數值下，RLPSO的搜索性能最好，因此，本文將參數μ設成0.6。

表 1 基準測試函數Table 1 Benchmark functions

圖 5 基準測試函數三維空間分布圖Fig. 5 Visualization of benchmark functions in three-dimensional space

3.3 任務調度實驗結果及分析

圖6(a)所示為任務數為100時5種優化算法的總任務完成時間收斂曲線。從圖中可以看到，在50次迭代時RLPSO搜索到的值已經優于其他4個優化算法，直到200次迭代RLPSO都表現出了最優的搜索性能，此時搜索到的最優值為12.36 s。在50～200迭代區間，LSA算法僅次于RLPSO。ACO在100次迭代之后處于收斂狀態，無法搜索到更優值，搜索曲線為直線狀態，此時搜索到的最優值為19.05 s。此時PSO搜索精度略微提高，然而搜索到的最優值遜于ACO。GA算法在50～100次迭代范圍內無法搜索到更優值，搜索曲線為直線，100～150次迭代時搜索到一次更優值（29.41 s）之后，其搜索精度再也沒有發生變化。可以看出，在任務數為100的條件下，5種算法搜索性能按先后次序排名為：RLPSO、LSA、

ACO、PSO、GA。

表 2 不同的μ值時RLPSO算法的目標函數值Table 2 Objective function values of RLPSO algorothm with different μ

當任務數為500時，5種優化算法的總任務完成時間收斂曲線如圖6(b)所示。由于任務數比較大，在50次迭代時，5種算法的搜索曲線已經表現出比較明顯的區別，此時算法搜索到的最優值分別為：RLPSO為62.88 s，LSA為82.37 s，PSO為102.33 s，ACO為105.64 s，GA為134.10 s。在50次迭代之后，RLPSO基本處于收斂狀態，當迭代次數為200時，其搜索到的最優值為62.50 s，與其他4個優化算法相比，RLPSO呈現出的是快速收斂的能力。LSA算法搜索性能次于RLPSO，其搜索曲線在100次迭代之后接近于收斂狀態。PSO和ACO在整個迭代區間的搜索性能都比較接近，直到迭代結束時，PSO搜索到的最優值為88.97 s，而ACO搜索到的最優值為96.18 s。GA算法50～200次搜索到的最優值都遜于其他4個算法，當迭代結束時，其搜索到的最優值為108.93 s。在任務數為500的條件下，5種算法的搜索性能按先后次序排名為: RLPSO、LSA、PSO、ACO、GA。

從圖6(c)可以看到，當任務數增加到1 000時，RLPSO的尋優效果最好，搜索到的總任務完成時間為149.34 s。在經過150次迭代之后，LSA、PSO、ACO、GA算法基本處于早熟收斂狀態，而RLPSO的尋優曲線還在略微變化，即隨著迭代次數的增加，其搜索到更優的值。5個算法中，GA算法的尋優效果最差，在迭代次數為100時，無法再搜索到更優值，并進入收斂狀態，此時，GA搜索到總任務完成時間為217.19 s，約為RLPSO搜索到的值的1.5倍。在任務數為1 000時，5種算法的搜索性能按先后次序排名為: RLPSO、LSA、PSO、ACO、GA。

從圖6可知，任務數為100、500、1 000時，RLPSO具有最優的尋優效果，特別是任務數為1 000時，RLPSO明顯優于其他4個對比算法。

表3所示為3種不同任務數條件下5種算法得到的數據結果。可以看出，RLPSO比其他算法能搜索到更優的結果。圖7示出了3種不同任務數時總任務完成時間的柱狀圖，從圖中可以直觀看到，在Tn=100時，RLPSO搜索到的總任務完成時間最小，LSA次之，GA總任務完成時間最大。在Tn=500和Tn=1 000時，依然是RLPSO的總任務完成時間最小，GA的總任務完成時間最大。

圖 6 5種算法在不同任務數下的收斂曲線Fig. 6 Convergence curves of five algorithms under different numbers of tasks

表 3 5種算法3種不同任務數的完成時間Table 3 Completion time of five algorithms under three different numbers of tasks

RLPSO算法與4個對比算法的Wilcoxon's test結果如表4所示。從該表中可以看到p值都小于顯著性值（0.05），即RLPSO顯著優于4個對比算法。表5給出了5個算法的Friedman test結果，在任務數分別為100、500、1 000時，RLPSO的排名值都是1.00，結果表明本文算法性能最好。

圖 7 5種算法3種不同任務數的完成時間Fig. 7 Completion time of five algorithms under three different numbers of tasks

表 4 5種算法Wilcoxon's test的p值Table 4 p-Values of Wilcoxon's test of five algorithms

表 5 5種算法的Friedman test排名結果Table 5 Ranking results of Friedman test of five algorithms

從以上實驗結果圖分析得到，應用RLPSO算法進行任務調度，可以搜索明顯更小的總任務完成時間，從而表明RLPSO算法是一種云計算環境下的有效任務調度算法。

4 結束語

本文提出的RLPSO算法通過對粒子進行群劃分，引入逆向學習行為，并設計繁殖行為，從而提升整個算法的全局搜索能力和局部搜索能力。在云計算環境下，在任務數分別為100、500、1 000的條件下對RLPSO算法進行了優化性能測試。仿真實驗結果表明，與4個傳統優化算法(即GA、PSO、ACO、LSA)相比，本文算法具有更優的尋優性能，并且能明顯提高對總任務調度時間尋優的效率。目前大部分的優化算法，其靈感主要來源于自然界中的動物生存或植物生長行為。下一步工作將在此改進的粒子群算法的基礎上引入粒子競爭行為，從而使得優化算法不再是簡單的模擬自然界中存在的現象，而是豐富算法的內部機制，以此形成更具有智能性的優化算法；設計并行計算結構，使得算法在求解大規模問題時能加快計算速度；把改進的算法應用于解決實際問題。