基于混沌擾動PSO算法的云計算任務調度

許向陽，張芳磊

(河北科技大學 信息科學與工程學院，河北 石家莊 050000)

0 引言

云計算環境下任務調度算法的執行效率直接影響到用戶對服務質量的體驗，而多數傳統的優化算法已經不能滿足現在的需求，因此許多研究學者提出了蟻群算法、遺傳算法等啟發式智能類的算法。本文主要研究的是智能算法中的粒子群優化(Particle Swarm Optimization，PSO)算法。粒子群算法的模型就是在一塊區域里讓距離食物最近的一只鳥去尋找食物，減少尋找時間，提高速率。PSO算法由于具有參數少、計算效率高、搜索快速、編程容易且應用廣泛等特點，從而被許多學者應用于云計算環境下任務調度算法的研究上。

許多專家和學者不斷分析和研究影響任務調度的因素，已經在此算法上研究出許多有價值的方案。文獻[1]通過分析粒子飛行軌跡提出廣義和狹義中心粒子的雙中心粒子群優化算法，改善粒子算法的精度和收斂速度。文獻[2]在滿足用戶多任務服務質量的要求下，提出一種多QoS約束離散粒子群的優化算法。文獻[3]將混合粒子群算法結合Pareto最優工作流調度解集合，解決沖突的三目標優化問題。文獻[4]提出一種反向學習和局部學習的粒子群優化算法，通過反向學習增加種群粒子的多樣性，降低算法局部最優的情況。文獻[5]通過自適應地調整慣性權重來平衡算法的全局收斂性和收斂速度，提高算法性能。

優化粒子群算法通常也會與其他粒子群算法相結合。文獻[6]利用遺傳算法中交、變異的特點，將遺傳算法與改進的粒子群算法相混合，增強了粒子的變異能力，又提高了粒子的搜索精度，大大降低了任務完成時間。文獻[7]結合粒子群算法和蟻群算法各自的優點，用粒子群算法使粒子群前期迭代產生的優良粒子生成初始信息素，再將信息素應用于蟻群算法上，最后得到最優解。

本文首先分析粒子群算法的基本原理和粒子群在解決任務調度問題時的缺點，針對缺點，對粒子群算法在慣性權重上進行改進，解決算法在前期出現“早熟”和后期收斂精度低的問題，并加入混沌擾動，通過給出的適應度函數，以不同任務數為研究對象，對比算法任務完成總時間，并觀察迭代次數的情況。

1 粒子群算法介紹

1.1 粒子群優化算法基本原理

傳統粒子群優化算法是由美國心理學家KENNEDY J和電氣工程師EBERHART RC于1995年根據魚群、鳥群覓食的活動提出的一種智能化算法[8]。但傳統粒子群優化算法不存在對粒子運動速度的調整，使算法對局部搜索和全局搜索的能力降低。因此為了彌補傳統粒子群優化算法的不足，SHI Y和EBERHART R C在此算法的前提下引入了慣性權重，并深入研究，使粒子的運動速度不再是單一固定不變的速度[9-10]。

粒子群中的所有粒子都有自己的位置、運動方向和速度。每個粒子都是一個個體，粒子本身在經歷多次迭代后出現的個體最優解叫做個體極值pbest，群粒子組成的群體會出現全局最優解，即全局極值gbest。所有的粒子都會尋找最佳位置，就是說粒子會向最優解進行搜索，這是由優化函數的一個適應值決定的。PSO算法首先要初始化粒子群，然后粒子通過在個體最優解和全局最優解反復更新自己的位置和速度，經過反復迭代，最終得到極值。

記粒子群中粒子個數為N，粒子在d維空間運動，則k時刻粒子i的位置和速度公式如下。

位置：

速度：

由優化函數適應值決定粒子個體最優位置和全局最優位置的公式如下。

個體最優位置：

全局最優位置：

在取得兩個極值之前，粒子會根據如下公式進行搜索，更新位置和速度：

其中，d為粒子搜索空間維數；k為迭代次數，也指當前時刻下；c1，c2為兩個正常數，即學習因子，也叫加速因子；α、β是兩個介于0和1之間的隨機數。

ω為慣性權重，SHI Y和EBERHART R C將慣性權重引入粒子群算法中，即

ω=ωmax-(ωmax-ωmin)×k/Kmax

(7)

其中，ωmax、ωmin分別是最大和最小慣性權重，k為此刻粒子迭代次數，Kmax為粒子最大迭代次數。

根據標準粒子群算法原理，影響PSO算法的主要參數有：粒子群規模、慣性權重、學習因子及粒子運動的最快速度等。

1.2 粒子群算法的應用及問題

PSO算法已經被廣泛應用于解決多目標問題、動態優化、參數優化、組合優化等各類優化問題，以及應用于模糊系統控制、電力分配系統、神經網絡、流水車間調度、生物醫學等各領域中。但是用在云計算環境解決任務調度的優化問題時，會出現陷入局部最優、后期收斂速度慢等問題；與其他啟發類智能算法一樣，這一種算法不可能解決所有的優化問題。PSO算法較適用于解決連續化的問題上對于任務調度這個離散型問題不能夠很好地發揮其優勢，因此需要在PSO算法的基礎上進一步改進算法性能，以去除算法在任務調度過程中存在的弊端，從而取得更好的實際效果，改善資源利用率和平臺的服務質量，提高用戶體驗。

2 改進型粒子群算法研究

在現實應用中，算法的優化提高不可能只是單方面的，通常情況下都是多個目標優化問題，但是多目標優化多數情況下是互相矛盾、存在沖突的，所以最好的優化只能是根據實際情況，權衡各個目標而得到相對的極值。本文以任務完成時間為算法性能優劣的主要依據。

2.1 適應度函數

設有r個資源，s個粒子，任務i在資源j上的執行時間用T(i,j)表示：

完成任務的總時間為：

定義適應度函數為:

2.2 慣性權重的計算

PSO算法在解決任務調度問題時容易出現的問題就是前期陷入局部最優，后期全局的搜索精度降低。所以為了平衡全局和局部搜索能力，在相關研究中權重的改進包括自適應權重、隨機權重等。本文采用指數形式的慣性權重ω的改進方法。慣性權重ω的取值較大，全局的搜索能力會提高，但局部的搜索能力會變差；若ω取值較小，算法的局部搜索能力會提高，但是全局的搜索能力不佳。根據慣性權重存在的問題，本文將慣性權重的表達式改進為：

ω=ωmin+exp[-((ωmax-ωmin)×k/Kmax)2]

(10)

由上式可知，式中ω會以指數的形式在迭代前期保持一個較大的值，從而使粒子群在迭代前期全局搜索能力增強；在迭代后期ω能夠保持一個較小且變化平緩的值，提高算法后期局部的搜索能力，加快收斂速度。依據前人相關研究，本文慣性權重取值范圍為[0.4～0.9]。

2.3 混沌擾動

混沌在一定范圍內可以等概率無重復遍歷所有狀態，算法在解決任務的過程中，其他粒子會因為種群中極少數最優粒子的引導向最優粒子迅速靠近，如果此粒子并沒有達到全局最優，則有可能導致算法陷入局部最優?；煦鐚αＷ映跏贾得舾校軌蛞罁煦绲膬炔恳巹t，隨機地遍歷所有的粒子。所以為了避免粒子陷入“早熟”時，需要加入一個外部擾動，讓粒子可以打破局部最優。

當粒子發生早熟時要存在一個外部擾動機制使粒子群跳出“早熟”。本文采用的混沌擾動公式為：

算法實現流程如圖1所示。

圖1 算法的實現流程圖

3 實驗仿真與分析

本實驗使用云計算工具Cloudsim-3.0作為實驗平臺，MyEclipse為開發工具，Java為開發語言。實驗基本流程為：搭建實驗環境，初始化Cloudsim，創建數據中心、服務代理，設置虛擬機資源及任務的參數，擴展并調用任務調度算法，啟動Cloudsim，最后進行實驗結果分析。

3.1 仿真實驗過程

用Cloudsim部署實驗環境，在DatacenterBroker中擴展新算法，將任務數分別設置為50，100,200,500，實驗將改進后的算法與標準粒子群算法(SPSO)進行實驗仿真，并對這兩個算法在任務完成時迭代次數的情況進行分析對比。文中提出的算法的參數設置如表1所示。

表1 SPSO和改進后算法的參數設置

3.2 實驗結果比較及討論

根據表1設置實驗參數，為保證實驗的準確性，每組實驗進行20次，最后取20次實驗的平均值進行比較分析。實驗比較兩種算法在任務數不同時，完成時間最短時的迭代次數的情況，實驗結果對比如圖2～5所示。

圖2 任務數為50時的任務總完成時間

圖3 任務數為100時的任務總完成時間

圖4 任務數為200時的任務總完成時間

圖5 任務數為500時的任務總完成時間

通過上述實驗結果對比可以得出，在迭代前期NPSO算法比SPSO算法收斂能力更強，但是在任務數相同時NPSO算法比NPSO算法完成任務所用的總時間有所減少，且后期的收斂性較強，通過對比可知，改進后的算法有更好的執行效率，在實際應用中能更好地改善用戶的使用體驗。

4 結論

許多研究人員針對任務調度算法開展了許多相關研究，本文在前人的基礎上對標準粒子群算法進行進一步進行改進。通過優化慣性權重，并且在粒子群算法的過程中加入混沌擾動，遍歷粒子狀態，根據給出的適應度函數，對新算法的性能與其他任務調度算法進行對比。實驗結果表明，本文方案有效地降低了任務執行時間，降低了資源消耗成本，具有可行性。