基于逆向?qū)W習(xí)行為粒子群算法的云計算大規(guī)模任務(wù)調(diào)度

賴兆林， 馮 翔， 虞慧群

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

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

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

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

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

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

1 云計算調(diào)度問題模型化

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

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

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

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

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

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

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

完成全部任務(wù)的總時間如下：

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

從式(3)可知，完成一組任務(wù)的可行調(diào)度總時間為Otime，由于一組任務(wù)的可行調(diào)度對應(yīng)于優(yōu)化算法中的一個解xi(粒子), 因此，完成全部任務(wù)的總時間轉(zhuǎn)換為優(yōu)化問題的目標(biāo)函數(shù)為

2 改進的粒子群算法

2.1 PSO算法

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

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

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

2.2 RLPSO算法

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

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

受文獻[26]中逆向?qū)W習(xí)行為啟發(fā)，生物個體具有逆向?qū)W習(xí)能力，因此，RLPSO算法內(nèi)個體除了正向?qū)W習(xí)之外，以一定概率進行逆向?qū)W習(xí)。

定義2 (個體學(xué)習(xí)目標(biāo)) 對于種群內(nèi)的任意個體i，其搜索行為受學(xué)習(xí)目標(biāo)個體影響。雄性個體的學(xué)習(xí)目標(biāo)為雄性子群內(nèi)最優(yōu)個體Mb及雌性子群內(nèi)最優(yōu)個體Fb，而雌性個體的學(xué)習(xí)目標(biāo)為雌性子群內(nèi)最優(yōu)個體Fb。

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

圖 3 個體的搜索方式及學(xué)習(xí)方向Fig. 3 Search mode and learning direction of individual

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

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

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

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

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

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

由式(11)可知，新生個體可在搜索空間內(nèi)任一位置產(chǎn)生。對于具有多個極值的問題（即多峰問題），當(dāng)算法收斂于某個非最優(yōu)的極值點附近時，借助于新生個體在搜索空間的其他區(qū)域產(chǎn)生的方式，可加強算法跳出局部最優(yōu)的能力。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 當(dāng)種群內(nèi)個體往逆向方向?qū)W習(xí)時，其位置更新公式滿足收斂性。

證明 設(shè)

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

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

根據(jù)動力系統(tǒng)理論，式(13)可重寫為

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

從動力學(xué)理論可知，其收斂性取決于狀態(tài)矩陣A的特征值。

其中，特征值為

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

引理2 當(dāng)種群內(nèi)個體往正向方向?qū)W習(xí)，其位置更新公式滿足收斂性。

證明 設(shè)

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

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

定理1 RLPSO算法是收斂的。

證明 根據(jù)引理1和引理2，可得RLPSO算法內(nèi)所有個體的移動都將收斂于穩(wěn)定狀態(tài)點，即算法滿足收斂性。

3 仿真實驗

3.1 實驗環(huán)境及算法參數(shù)設(shè)置

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

3.2 RLPSO參數(shù)擇優(yōu)

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

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

表 1 基準(zhǔn)測試函數(shù)Table 1 Benchmark functions

圖 5 基準(zhǔn)測試函數(shù)三維空間分布圖Fig. 5 Visualization of benchmark functions in three-dimensional space

3.3 任務(wù)調(diào)度實驗結(jié)果及分析

圖6(a)所示為任務(wù)數(shù)為100時5種優(yōu)化算法的總?cè)蝿?wù)完成時間收斂曲線。從圖中可以看到，在50次迭代時RLPSO搜索到的值已經(jīng)優(yōu)于其他4個優(yōu)化算法，直到200次迭代RLPSO都表現(xiàn)出了最優(yōu)的搜索性能，此時搜索到的最優(yōu)值為12.36 s。在50～200迭代區(qū)間，LSA算法僅次于RLPSO。ACO在100次迭代之后處于收斂狀態(tài)，無法搜索到更優(yōu)值，搜索曲線為直線狀態(tài)，此時搜索到的最優(yōu)值為19.05 s。此時PSO搜索精度略微提高，然而搜索到的最優(yōu)值遜于ACO。GA算法在50～100次迭代范圍內(nèi)無法搜索到更優(yōu)值，搜索曲線為直線，100～150次迭代時搜索到一次更優(yōu)值（29.41 s）之后，其搜索精度再也沒有發(fā)生變化?？梢钥闯觯谌蝿?wù)數(shù)為100的條件下，5種算法搜索性能按先后次序排名為：RLPSO、LSA、

ACO、PSO、GA。

表 2 不同的μ值時RLPSO算法的目標(biāo)函數(shù)值Table 2 Objective function values of RLPSO algorothm with different μ

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

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

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

表3所示為3種不同任務(wù)數(shù)條件下5種算法得到的數(shù)據(jù)結(jié)果?？梢钥闯?，RLPSO比其他算法能搜索到更優(yōu)的結(jié)果。圖7示出了3種不同任務(wù)數(shù)時總?cè)蝿?wù)完成時間的柱狀圖，從圖中可以直觀看到，在Tn=100時，RLPSO搜索到的總?cè)蝿?wù)完成時間最小，LSA次之，GA總?cè)蝿?wù)完成時間最大。在Tn=500和Tn=1 000時，依然是RLPSO的總?cè)蝿?wù)完成時間最小，GA的總?cè)蝿?wù)完成時間最大。

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

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

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

圖 7 5種算法3種不同任務(wù)數(shù)的完成時間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排名結(jié)果Table 5 Ranking results of Friedman test of five algorithms

從以上實驗結(jié)果圖分析得到，應(yīng)用RLPSO算法進行任務(wù)調(diào)度，可以搜索明顯更小的總?cè)蝿?wù)完成時間，從而表明RLPSO算法是一種云計算環(huán)境下的有效任務(wù)調(diào)度算法。

4 結(jié)束語

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