云計算任務(wù)調(diào)度的粒子雞群優(yōu)化算法研究*

許向陽，張芳磊

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

0 引 言

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

1 基本算法介紹

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

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

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

該算法由于參數(shù)少、計算效率高、快速搜索、容易編程等優(yōu)點，被應(yīng)用于許多方面的研究與優(yōu)化，如解決多目標問題、動態(tài)優(yōu)化、參數(shù)優(yōu)化和組合優(yōu)化等各類優(yōu)化問題中，以及模糊系統(tǒng)控制、電力分配系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、流水車間調(diào)度和生物醫(yī)學等領(lǐng)域。

1.2 雞群優(yōu)化算法基本原理

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

介紹算法前，首先將雞群的活動與任務(wù)調(diào)度相關(guān)聯(lián)。雞群中，雞的種類不同，遵循的活動規(guī)則也將不同。在雞群的等級制度下，雞之間也是存在競爭關(guān)系的[6-9]。

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

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

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

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

母雞位置更新公式為：

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

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

小雞的位置更新公式為：

其中，m為第i只小雞對應(yīng)的母雞媽媽，F(xiàn)為[0，2]的任意數(shù)。

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

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

2.1 C-SPSO算法的改進

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

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

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

2.2 C-SPSO算法適應(yīng)度函數(shù)

C-SPSO算法中整個群體分為若干小組，組之間存在競爭關(guān)系，組內(nèi)同種個體也存在競爭關(guān)系。這個競爭是由適應(yīng)度值決定的。適應(yīng)度值的優(yōu)劣決定了種群的搜索方向，影響整個任務(wù)的執(zhí)行時間和任務(wù)調(diào)度系統(tǒng)的資源利用率。因此，本文的適應(yīng)度函數(shù)是以總?cè)蝿?wù)完成時間和任務(wù)總執(zhí)行成本為基礎(chǔ)進行定義的。

適應(yīng)度函數(shù)如下：

2.3 C-SPSO算法執(zhí)行基本流程

C-SPSO算法解決云計算環(huán)境下任務(wù)調(diào)度的基本流程如下。

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

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

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

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

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

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

3 實驗與結(jié)果分析

本文通過Cloudsim-3.0進行實驗，將SPSO算法、CSO算法和C-SPSO算法在此平臺經(jīng)過擴展，基于總?cè)蝿?wù)完成時間和任務(wù)總執(zhí)行成本兩方面進行對比分析，每組實驗分別進行20次，計算平均值作為最終結(jié)果。

3.1 實驗過程

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

表1 實驗中算法參數(shù)設(shè)置

3.2 實驗結(jié)果對比及討論

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

在任務(wù)數(shù)不同的情況下，總?cè)蝿?wù)的執(zhí)行時間情況如圖1所示。

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

圖1 任務(wù)完成時間

在任務(wù)數(shù)不同的情況下，任務(wù)總的執(zhí)行成本情況如圖2所示。

圖2 任務(wù)執(zhí)行成本

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

4 結(jié) 語

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