云計算任務調度的粒子雞群優化算法研究*

許向陽，張芳磊

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

0 引 言

云計算是一種將人們所需的數據資源任務分布在計算機構成的資源池上，使使用者能夠根據自身需求來獲取資源的服務[1]。在大數據時代，云計算是處理數據的一種手段，對數據的處理有很高的要求。所以，云計算在任務調度過程中，算法執行的效率至關重要。多數傳統的優化算法已經不能滿足現在的需求，為此許多學者在不斷的研究中提出了很多啟發類的智能群算法。本文以參數少、易編程的粒子群算法融合雞群優化算法，改進粒子群算法在應用過程中的不足，使新算法能夠更好地滿足云計算任務調度的需求。

1 基本算法介紹

1.1 標準粒子群算法基本原理

標準粒子群（SPSO）算法是由James Kennedy和Russel Eberhart提出粒子群（PSO）算法后，由Shi和Eberhart等研究人員不斷完善、發展得來的[2-4]。在取得個體和全局最優位置前，粒子位置和速度更新公式分別為：

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

該算法由于參數少、計算效率高、快速搜索、容易編程等優點，被應用于許多方面的研究與優化，如解決多目標問題、動態優化、參數優化和組合優化等各類優化問題中，以及模糊系統控制、電力分配系統、神經網絡、流水車間調度和生物醫學等領域。

1.2 雞群優化算法基本原理

雞群優化（CSO）算法在2014年由Xianbing Meng提出，是模擬雞群等級的一種仿生學算法[5]。

介紹算法前，首先將雞群的活動與任務調度相關聯。雞群中，雞的種類不同，遵循的活動規則也將不同。在雞群的等級制度下，雞之間也是存在競爭關系的[6-9]。

（1）雞群分為幾個組，每組都包含一只領頭的公雞、幾只母雞和若干小雞。（2）通過適應值的優劣將雞群分為若干組，且區分每組中個體的種類。雞群中適應值最優的若干個體作為每組中的頭雞，并帶領適應值最差的小雞和剩余的母雞。母子之間的關系是隨機確定的，母雞歸屬哪組也是隨機的。（3）每隔相同的時間，組內的支配關系和母子關系會更新一次。（4）母雞依據公雞的足跡尋找食物，小雞跟隨母雞。雞會隨機偷取別人發現的食物，占主導地位的雞對食物的獲取具有優先權。

假設整個雞群個體為N，其中公雞、母雞、小雞和媽媽母雞的個數分別為Nr、Nh、Nc和Nm。每個個體的位置表示為xidk，整個雞群的位置更新公式分為三種。

公雞在整個群體中適應度值最優，搜索空間最大，對應的位置更新公式為：

randn(0,σ2)是高斯分布函數，f為適應度函數，r為公雞中去除i的任一公雞個體。

母雞位置更新公式為：

其中，randn是0～1的隨機數。C1、C2為學習因子：

j1為第i只母雞所在小組中的公雞，j2為整個雞群中公雞和母雞任意選取的個體，且j1≠j2。

小雞的位置更新公式為：

其中，m為第i只小雞對應的母雞媽媽，F為[0，2]的任意數。

2 SPSO算法與CSO算法的融合算法

SPSO算法容易陷入局部最優，整個種群在搜索過程中趨于單一性，降低了種群多樣性，使算法“早熟”；而CSO算法在種群多樣性方面占有優勢。因此，提出在粒子群算法基礎上加入CSO算法形成新算法（C-SPSO），避免粒子陷入局部最優的同時，提高算法全局搜索能力，更好地完成云計算環境下的任務調度，降低任務完成時間與成本，提高用戶服務質量。

2.1 C-SPSO算法的改進

算法容易陷入早熟，導致出現局部最優的問題。因此，本文在粒子初始化時加入混沌擾動，利用擾動遍歷粒子群，降低局部最優問題的出現概率[10]。混沌擾動公式如下：

根據式（8）小雞的位置更新公式可知，小雞只向自己的媽媽學習。文獻[11]為了克服小雞在雞群算法中的不足，也對小雞的位置狀態更新進行了優化。本文由SPSO算法和文獻[7]的啟示，基于CSO算法，對小雞的位置更新公式進行改進。小雞在運動過程中除了向自己的媽媽學習外，還會自我學習。因此，小雞的位置更新公式可改進為：

式中，ω為小雞自身學習的系數。根據SPSO算法中慣性權重的取值，本文ω的計算公式如下：

2.2 C-SPSO算法適應度函數

C-SPSO算法中整個群體分為若干小組，組之間存在競爭關系，組內同種個體也存在競爭關系。這個競爭是由適應度值決定的。適應度值的優劣決定了種群的搜索方向，影響整個任務的執行時間和任務調度系統的資源利用率。因此，本文的適應度函數是以總任務完成時間和任務總執行成本為基礎進行定義的。

適應度函數如下：

2.3 C-SPSO算法執行基本流程

C-SPSO算法解決云計算環境下任務調度的基本流程如下。

步驟1：建立規模為N的粒子群，根據混沌擾動公式，對粒子的速度和位置進行初始化，篩選粒子，并定義相關參數；

步驟2：計算粒子的初始適應值，找到粒子當前個體與全局的最優距離，并對種群所有粒子的適應度值進行排序；

步驟3：判別種群是否滿足雞群的等級分配，滿足則對種群進行分配并繼續執行，否則分別根據式（3）、式（5）和式（10）對公雞、母雞和小雞的位置進行更新；

步驟4：對滿足雞群等級的種群進行分配，確定公雞、母雞、小雞的等級，同時確立公雞的領導地位和母雞與小雞的母子關系；

步驟5：種群進行迭代及位置更新，計算更新后粒子的適應度值，并與之前適應度值進行比較，更新至雞群個體和全局最好的位置；

步驟6：種群進行迭代，若種群達到最大迭代次數，算法停止；否則，返回步驟3。

3 實驗與結果分析

本文通過Cloudsim-3.0進行實驗，將SPSO算法、CSO算法和C-SPSO算法在此平臺經過擴展，基于總任務完成時間和任務總執行成本兩方面進行對比分析，每組實驗分別進行20次，計算平均值作為最終結果。

3.1 實驗過程

首先新建Cloudsim的數據中心，設置平臺實驗的帶寬、主機數、任務數量及長度等參數，創建虛擬機，在DatacenterBroker中擴展算法，最后開始仿真，并在實驗結束后停止仿真。3種算法中，最大迭代次數Kmax=1 000。實驗中算法所需參數設置如表1所示。

表1 實驗中算法參數設置

3.2 實驗結果對比及討論

根據表1參數進行實驗設置，任務數設置為10～80。為降低實驗結果的誤差，本文每組實驗進行20次，最后取實驗結果的平均值。

在任務數不同的情況下，總任務的執行時間情況如圖1所示。

由圖1可知，在任務數較少時，3種算法完成任務的時間相差不大，但隨著任務數的增加，任務完成時間有顯著差異。通過對比任務完成時間發現，本文提出的C-SPSO算法時間明顯縮短。

圖1 任務完成時間

在任務數不同的情況下，任務總的執行成本情況如圖2所示。

圖2 任務執行成本

由圖2分析可得，3種算法隨著任務數的增多，執行成本都在上升。但是，SPSO算法、CSO算法與C-SPSO算法相比，后者的增長速度慢，且任務數越多越明顯。

4 結 語

本文為了解決標準粒子群算法在任務調度時的缺點，首先對標準粒子群算法的慣性權重進行指數形式改進，以提高粒子群后期局部搜索能力；其次融合雞群優化算法，增強群體的多樣性，并對小雞位置更新部分引入小雞的自我學習參數，提高算法的收斂速度，并在粒子的選取上加入了混沌擾動；最后，通過實驗結果分析可以直觀看出，新算法在任務完成時間和任務總執行成本上的優勢，驗證了算法的可行性。