汪婷, 邵鵬, 李光泉, 劉珊慧

(江西農(nóng)業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院, 南昌 330045)

云計(jì)算(cloud computing,CC)是以互聯(lián)網(wǎng)為核心,根據(jù)用戶需求,動(dòng)態(tài)存儲(chǔ)、整合相關(guān)資源,向用戶提供高性能服務(wù)的一種新興技術(shù)。調(diào)度技術(shù)作為云計(jì)算的關(guān)鍵技術(shù),能夠?qū)ξ锢碣Y源進(jìn)行高效管理,以獲得更好的資源配置方案。Bisht等[1]綜合考慮異構(gòu)環(huán)境下的成本、最大完成時(shí)間等因素,提出改進(jìn)Min-Min工作調(diào)度算法。Alworafi等[2]基于最短作業(yè)優(yōu)先,以最小化任務(wù)完成時(shí)間和平均響應(yīng)時(shí)間為目標(biāo)提出改進(jìn)算法,同時(shí)最大化資源利用率。Alhuidari等[3]利用輪詢算法,根據(jù)時(shí)間量子平均值自適應(yīng)更新,提高云計(jì)算系統(tǒng)吞吐量。然而,傳統(tǒng)的先來(lái)先服務(wù)、短作業(yè)優(yōu)先等確定性調(diào)度算法因時(shí)間開(kāi)銷大,可靠性低,通常無(wú)法獲得最佳調(diào)度方案。

現(xiàn)有方法表明,啟發(fā)式算法可通過(guò)預(yù)測(cè)獲得時(shí)間復(fù)雜度低的近似最優(yōu)解[4]。Liu等[5]針對(duì)云計(jì)算任務(wù)調(diào)度中普遍存在的資源利用率低這一缺點(diǎn),提出基于不同信息顆粒的貪心調(diào)度策略,并針對(duì)不同特征的任務(wù)分配不同的調(diào)度策略。由于處理任務(wù)的成本和能耗較高,啟發(fā)式算法不適用于處理云計(jì)算任務(wù)調(diào)度問(wèn)題。而元啟發(fā)式算法能夠在不預(yù)先告知任務(wù)和資源的條件下直接獲得最優(yōu)解,且結(jié)果優(yōu)于啟發(fā)式算法,因此被廣泛用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題,包括鯨魚優(yōu)化算法[6]、遺傳算法[7-9]、人工蜂群算法[10-11]以及粒子群優(yōu)化算法[12-14](particle swarm optimization,PSO)等。其中,PSO算法是Kennedy和Eberhart于1995年提出的基于群體協(xié)作的隨機(jī)搜索算法,具有原理簡(jiǎn)單、收斂速度快等特點(diǎn),被認(rèn)為是求解云計(jì)算任務(wù)調(diào)度問(wèn)題最具潛力的方法之一。

從已有的研究成果中可以發(fā)現(xiàn),傳統(tǒng)PSO算法在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中存在收斂速度慢、精度低等缺陷[15]。Dubey等[16]受化學(xué)反應(yīng)優(yōu)化算法啟發(fā),通過(guò)迭代算子保存具有高適應(yīng)度值的次優(yōu)解,并用于下一次迭代,以提高PSO算法解的質(zhì)量,加快粒子收斂速度。張思豪等[17]引入資源狀態(tài)指標(biāo),分批處理任務(wù)尋求最優(yōu)解,縮短任務(wù)完工時(shí)間。Nanjappan等[18]通過(guò)冠狀模糊均值算法對(duì)獨(dú)立任務(wù)進(jìn)行聚類并調(diào)度至各虛擬機(jī)中執(zhí)行,最后通過(guò)PSO算法計(jì)算特征值,有效提高結(jié)果精度。馬學(xué)森等[19]提出一種多策略融合的改進(jìn)PSO算法,首先引入非線性慣性權(quán)重策略提高粒子尋優(yōu)能力,接著通過(guò)花朵授粉算法平衡算法的探索與開(kāi)發(fā),最后利用螢火蟲算法產(chǎn)生“精英解”對(duì)粒子位置進(jìn)行擾動(dòng),跳出局部收斂,改進(jìn)算法在收斂速度和精度上都獲得明顯提升,但存在尋優(yōu)效率低等問(wèn)題。因此孫長(zhǎng)亞等[20]利用動(dòng)態(tài)更新慣性權(quán)重策略提高PSO算法的自適應(yīng)搜索能力,同時(shí)引入微生物遺傳算法,在算法前期縮小目標(biāo)搜索空間,并在算法后期利用PSO算法快速收斂,獲得全局最優(yōu)解,提高算法尋優(yōu)效率。

此外,為降低算法陷入局部極值的概率,Nabi等[21]基于線性遞減自適應(yīng)慣性權(quán)重策略提出一種自適應(yīng)粒子群優(yōu)化算法,以平衡算法的局部搜索和全局搜索能力,避免算法陷入局部極值。朱琳等[22]采用非線性遞減慣性權(quán)重更新策略提高算法后期收斂能力。譚鶴毅等[23]利用天牛須搜索算法實(shí)現(xiàn)多個(gè)個(gè)體同步計(jì)算,提高種群間信息交互能力,幫助粒子跳出局部極值。盡管眾多學(xué)者針對(duì)PSO算法在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中存在的收斂速度慢、精度低、易陷入局部極值等缺陷,分別開(kāi)展了大量的研究工作并且提出了相應(yīng)的改進(jìn)算法。然而,針對(duì)PSO算法存在的以上3種缺陷進(jìn)行同時(shí)改進(jìn),并將其應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題,仍將是一個(gè)極富挑戰(zhàn)的任務(wù)。

綜上,針對(duì)PSO算法在求解云計(jì)算任務(wù)調(diào)度問(wèn)題上的缺陷,綜合考慮最大完成時(shí)間最少、任務(wù)執(zhí)行總時(shí)間最優(yōu)兩個(gè)優(yōu)化目標(biāo),在PSO算法中融合模擬退火算法[24](simulated annealing, SA)、饑餓游戲搜索[25](hungary games search,HGS)及雙重變異限制策略[26](double restrictions),現(xiàn)提出一種融合多種策略的粒子群優(yōu)化算法(multi-strategy particle swarm optimization, MSPSO)。引入模擬退火算法動(dòng)態(tài)更新粒子慣性權(quán)重,平衡算法的探索和開(kāi)發(fā),避免算法陷入局部極值。引入饑餓游戲搜索算法優(yōu)化粒子位置更新策略,加快粒子收斂速度,提高結(jié)果精度(更優(yōu)數(shù)量級(jí))。引入雙重變異限制策略同時(shí)限制粒子速度和位置,避免粒子發(fā)生越界,提高算法尋優(yōu)效率。將所提算法MSPSO應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題,在不同任務(wù)量下進(jìn)行對(duì)比實(shí)驗(yàn),以驗(yàn)證MSPSO算法在實(shí)際應(yīng)用中的可靠性和實(shí)用性。

1 云計(jì)算任務(wù)調(diào)度描述

云計(jì)算是一種全新的、基于并高度依賴Internet、自助式使用遠(yuǎn)程計(jì)算資源的技術(shù),具有按需服務(wù)、動(dòng)態(tài)可拓展、虛擬化等特點(diǎn),它主要包括3種服務(wù)模式:基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)和軟件即服務(wù)(SaaS)。通常在云計(jì)算環(huán)境中,一個(gè)用戶任務(wù)被切分成n個(gè)不同大小、相互獨(dú)立的子任務(wù),子任務(wù)集合可以用字母N表示為:N={n1,n2,…,nn},假設(shè)所有的子任務(wù)被分配到m個(gè)虛擬機(jī)上執(zhí)行,虛擬機(jī)擁有CPU、內(nèi)存、存儲(chǔ)等資源,用VM表示為:VM={vm1,vm2,…,vmm}。其中,n>m,ni(1≤i≤n)表示第i個(gè)任務(wù),vmj(1≤j≤m)表示第j個(gè)虛擬機(jī)。任務(wù)調(diào)度即將n個(gè)子任務(wù)調(diào)配到m個(gè)虛擬機(jī)中執(zhí)行,并獲得最佳調(diào)度方案,實(shí)現(xiàn)任務(wù)執(zhí)行的最大完成時(shí)間最小、任務(wù)執(zhí)行總時(shí)間最優(yōu)等目標(biāo)。云計(jì)算任務(wù)調(diào)度的框架可簡(jiǎn)化為圖1。

圖1 云計(jì)算任務(wù)調(diào)度框架Fig.1 Cloud computing task scheduling framework

為了便于計(jì)算每個(gè)任務(wù)完成調(diào)度所需要的時(shí)間,分別定義一個(gè)n×m的矩陣E,T。其中,E為子任務(wù)在各虛擬機(jī)上的執(zhí)行時(shí)間矩陣,如式(1)所示。T為將子任務(wù)數(shù)據(jù)傳輸?shù)礁魈摂M機(jī)上的傳輸時(shí)間矩陣,如式(2)所示。

(1)

(2)

2 多策略融合的粒子群優(yōu)化算法

2.1 粒子群優(yōu)化算法

(3)

(4)

(5)

式(5)中:wmax為最大慣性權(quán)重;wmin為最小慣性權(quán)重。

2.2 改進(jìn)的粒子群優(yōu)化算法

為克服PSO算法在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中存在的早熟收斂、易陷入局部極值等缺陷,基于PSO算法,融合饑餓游戲搜索、模擬退火算法和雙重變異限制策略,提出了一種多策略融合的粒子群優(yōu)化算法MSPSO,運(yùn)行機(jī)制如圖2所示。首先使用模擬退火算法動(dòng)態(tài)更新慣性權(quán)重,平衡算法的探索與開(kāi)發(fā);其次通過(guò)饑餓游戲搜索優(yōu)化粒子的位置更新策略,加快粒子收斂速度,提高結(jié)果精度;最后采用雙重變異限制策略防止粒子越界,提高算法尋優(yōu)效率。

圖2 MSPSO算法的運(yùn)行機(jī)制Fig.2 The operation mechanism of MSPSO algorithm

2.2.1 慣性權(quán)重更新策略

在MSPSO中,首先隨機(jī)初始化粒子的位置和速度,通過(guò)計(jì)算粒子適應(yīng)度值,獲得全局最佳位置gbest和局部最佳位置pbest。慣性權(quán)重w是PSO算法的重要參數(shù)之一,當(dāng)w較大時(shí),算法的全局尋優(yōu)能力增強(qiáng),粒子更容易跳出局部極值,但同時(shí)會(huì)降低搜索效率,不易收斂;反之亦然。模擬退火算法[24]是一種基于概率的算法,通過(guò)設(shè)置模擬退火概率P來(lái)動(dòng)態(tài)調(diào)整慣性權(quán)重。若當(dāng)前迭代次數(shù)t是正整數(shù)k的整數(shù)倍時(shí),調(diào)用模擬退火算法,慣性權(quán)重更新公式為

(6)

式(6)中:α1、α2為[0,1]內(nèi)常數(shù),且α1>α2;r為[0,1]內(nèi)常數(shù),模擬退火概率P公式為

(7)

2.2.2 位置更新策略

饑餓游戲搜索算法[25]受動(dòng)物社會(huì)行為的影響,將個(gè)體的饑餓程度h作為個(gè)體饑餓特征進(jìn)行數(shù)學(xué)模擬。將算法用于優(yōu)化粒子位置更新策略,可以提高粒子間的信息交互能力,在算法后期加快粒子的收斂速度,改進(jìn)后的粒子位置公式為

(8)

(9)

2.2.3 邊界限制策略

PSO算法在搜索空間尋找最優(yōu)解過(guò)程中,容易發(fā)生粒子越界。在已有研究中,大部分策略采用限定粒子位置、降低粒子飛行速度等方式限制粒子行為,然而當(dāng)粒子飛出搜索空間且速度很大時(shí),只限制粒子位置而不降低粒子速度,仍可能發(fā)生越界行為。采用雙重變異限制策略[26],可同時(shí)限制粒子位置和速度,將粒子控制在搜索空間內(nèi),其限定因子χ公式為

(10)

式(10)中:φ=0.5。則χ被限制在[0,0.5]范圍內(nèi),可有效解決算法由于加入過(guò)多隨機(jī)性而導(dǎo)致的收斂速度過(guò)快和收斂精度不足的問(wèn)題。

MSPSO的偽代碼如表1所示?，F(xiàn)對(duì)MSPSO的時(shí)間復(fù)雜度進(jìn)行分析,標(biāo)準(zhǔn)粒子群優(yōu)化算法的時(shí)間復(fù)雜度為O(M×Tmax×D),其中M為粒子總數(shù),Tmax為最大迭代次數(shù),D為維度。慣性權(quán)重更新策略、位置更新策略、邊界限制策略為O(M×D),故MSPSO的時(shí)間復(fù)雜度約為O(M×Tmax×D)。

表1 MSPSO的偽代碼

3 MSPSO算法性能對(duì)比

為驗(yàn)證所提算法的優(yōu)越性,分別在30、50、100、1 000共4種維度下,將MSPSO算法與PSO、QUAPSO[27]、ADPSO[21]這3種算法進(jìn)行對(duì)比實(shí)驗(yàn),其參數(shù)設(shè)置為:粒子總數(shù)M=100、最大迭代次數(shù)Tmax=500?？紤]到粒子群優(yōu)化算法的隨機(jī)行為,在運(yùn)行100次后取平均值作為最終結(jié)果。

選取了13個(gè)基準(zhǔn)測(cè)試函數(shù)驗(yàn)證所提算法的有效性,如表2所示,其中f1～f5為單模態(tài)函數(shù),f6～f10為多模態(tài)函數(shù),f11～f13為固定維數(shù)函數(shù)。

表2 基準(zhǔn)函數(shù)

為了評(píng)估算法的效率和性能,分別從適應(yīng)度平均值A(chǔ)vg、最小值Min、標(biāo)準(zhǔn)差SD 3個(gè)方面進(jìn)行評(píng)估。表3為各算法在求解高維問(wèn)題(D=1 000)時(shí)獲得的適應(yīng)度Avg、Min、SD。

表3 各算法求解高維問(wèn)題的最優(yōu)值統(tǒng)計(jì)

如表3所示,在求解單模態(tài)問(wèn)題f1～f5時(shí),MSPSO算法相比其他算法,能夠獲得更優(yōu)數(shù)量級(jí)的最優(yōu)解。以Dixon Price函數(shù)為例,MSPSO適應(yīng)度平均值分別比PSO、ADPSO、QUAPSO低99.94%、99.76%、99.58%,最小值低99.99%、99.98%、99.97%,標(biāo)準(zhǔn)差低99.58%、97.57%、95.63%。這得益于饑餓游戲搜索算法在MSPSO算法后期引導(dǎo)最優(yōu)粒子快速靠近全局最優(yōu)解,加快算法收斂速度,提高結(jié)果精度。在求解多模態(tài)問(wèn)題f6～f10時(shí),MSPSO相比其他算法,同樣可以獲得更優(yōu)解,表明MSPSO算法中慣性權(quán)重更新策略在保持種群多樣性,平衡算法的探索與開(kāi)發(fā)方面效果顯著。圖3表示當(dāng)維度D=1 000時(shí),各算法在Sphere、Dixon Price、F10中的適應(yīng)度平均值對(duì)比,可以看出MSPSO在收斂性、跳出局部極值等方面都明顯優(yōu)于其他算法。各算法求解低維(D為30、50、100)及固定維數(shù)問(wèn)題獲得的適應(yīng)度Avg、Min、SD如表4所示。

表4 各算法求解低維及固定維數(shù)問(wèn)題的最優(yōu)值統(tǒng)計(jì)

圖3 各算法在3個(gè)基準(zhǔn)函數(shù)中的適應(yīng)度平均值對(duì)比Fig.3 Comparison of the fitness of each algorithm in three benchmark functions

4 MSPSO用于云計(jì)算任務(wù)調(diào)度

4.1 粒子編碼

PSO算法是一種解決連續(xù)問(wèn)題的元啟發(fā)式算法,將其應(yīng)用于求解任務(wù)調(diào)度問(wèn)題,首先需要構(gòu)建有效的粒子編碼方案。采用間接編碼方式,設(shè)粒子位置編碼長(zhǎng)度為子任務(wù)個(gè)數(shù),一個(gè)子任務(wù)對(duì)應(yīng)一個(gè)虛擬機(jī)。舉例說(shuō)明,若子任務(wù)數(shù)N=10,虛擬機(jī)數(shù)VM=5,則粒子i的位置編碼長(zhǎng)度為10,可以表示為xi={2,4,5,1,3,4,2,5,1,4},其第1位編碼表示子任務(wù)n1在虛擬機(jī)vm2上執(zhí)行,第2位編碼表示子任務(wù)n2在虛擬機(jī)vm4上執(zhí)行,依此類推。其映射關(guān)系如表5所示。

表5 子任務(wù)與虛擬機(jī)間映射關(guān)系

4.2 適應(yīng)度函數(shù)設(shè)計(jì)

綜合考慮最大完成時(shí)間最小、任務(wù)執(zhí)行總時(shí)間最優(yōu)兩個(gè)優(yōu)化目標(biāo),MSPSO的數(shù)學(xué)模型描述如下。

定義1任務(wù)執(zhí)行總時(shí)間。

任務(wù)執(zhí)行總時(shí)間Tsum指按調(diào)度方案,各虛擬機(jī)完成其分配子任務(wù)的總時(shí)間,Tj表示虛擬機(jī)VMj完成分配子任務(wù)的總時(shí)間,公式如下。

(11)

(12)

定義2最大完成時(shí)間。

任務(wù)的最大完成時(shí)間Tmax表示最后一個(gè)子任務(wù)的完成時(shí)間,公式為

(13)

適應(yīng)度函數(shù)由式(14)獲得。

Fitness=αTsum+(1-α)Tmax

(14)

式(14)中:α為優(yōu)化目標(biāo)對(duì)適應(yīng)度函數(shù)的影響權(quán)重。將云計(jì)算任務(wù)調(diào)度問(wèn)題轉(zhuǎn)變?yōu)檎业竭m應(yīng)度最小值的任務(wù)調(diào)度方案。

4.3 任務(wù)調(diào)度流程

融合多策略粒子群優(yōu)化算法的云計(jì)算任務(wù)調(diào)度部署流程如下。

步驟1初始化云計(jì)算數(shù)據(jù)中心的物理主機(jī)列表和虛擬機(jī)列表。

步驟2初始化算法參數(shù),設(shè)置慣性權(quán)重w、最大迭代次數(shù)Tmax、常數(shù)l等。

步驟3粒子編碼,初始化粒子位置和速度。

步驟4迭代次數(shù)t=t+1。

步驟5根據(jù)式(14)計(jì)算粒子適應(yīng)度值,更新gbest和pbest。

步驟6維度d=d+1。

步驟7判斷當(dāng)前迭代次數(shù)t是否為正整數(shù)k的整數(shù)倍,若是,則調(diào)用隨機(jī)慣性權(quán)重策略根據(jù)式(6)動(dòng)態(tài)更新慣性權(quán)重w,否則根據(jù)式(5)更新。

步驟8根據(jù)式(3)更新粒子速度。

步驟9判斷當(dāng)前維度d是否為整數(shù)z的整數(shù)倍,若是,則調(diào)用饑餓游戲搜索算法,根據(jù)式(8)更新粒子位置;否則調(diào)用式(4)。

步驟10更新后,粒子的編碼序列范圍可能超出設(shè)定閾值,此時(shí)調(diào)用雙重變異限制策略,同時(shí)限定粒子位置和速度,防止粒子發(fā)生越界。

步驟11若當(dāng)前維度d

步驟12若當(dāng)前迭代次數(shù)t

4.4 實(shí)驗(yàn)設(shè)置

使用Cloudsim模擬云計(jì)算環(huán)境,包括數(shù)據(jù)中心、物理主機(jī)、虛擬機(jī)及云服務(wù)代理等。實(shí)驗(yàn)環(huán)境:Eclipse Kepler Release、Intel(R) Core(TM) i5-7200U CPU @ 2.50 GHz 2.71 GHz處理器,4 GB內(nèi)存。實(shí)驗(yàn)環(huán)境的配置如表6所示。

表6 實(shí)驗(yàn)環(huán)境配置

為確保實(shí)驗(yàn)結(jié)果的公平性,所有算法的參數(shù)設(shè)置都相同:種群規(guī)模為25,最大迭代次數(shù)為2 000,任務(wù)數(shù)分別設(shè)置為40、60、80和100,實(shí)驗(yàn)結(jié)果在算法運(yùn)行100次后取平均值作為最終結(jié)果。詳細(xì)參數(shù)設(shè)置如表7所示。

表7 參數(shù)設(shè)置

4.5 性能指標(biāo)

任務(wù)調(diào)度的性能指標(biāo)由總成本C來(lái)衡量,即各子任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間Eij與云計(jì)算資源中任務(wù)的執(zhí)行成本c的乘積之和。其計(jì)算公式為

(15)

4.6 結(jié)果分析

為驗(yàn)證MSPSO在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中的有效性,分別從適應(yīng)度值、總成本兩個(gè)角度,將所提算法MSPSO與LWPSO[28]、GWOPSO[29]及EEAPSO[30]3種改進(jìn)粒子群優(yōu)化算法進(jìn)行比較。

為測(cè)試本文算法在總成本上的優(yōu)劣,分別將MSPSO與LWPSO、GWOPSO、EEAPSO在任務(wù)數(shù)為40、60、80、100的條件進(jìn)行實(shí)驗(yàn)對(duì)比,對(duì)比結(jié)果如圖4所示?？梢钥闯?對(duì)于所有測(cè)試用例,MSPSO的總成本均遠(yuǎn)低于其他3種對(duì)比算法。這是因?yàn)镸SPSO中引入了饑餓游戲搜索算法,通過(guò)粒子的“饑餓程度”(它們對(duì)尋找最優(yōu)解的影響)動(dòng)態(tài)選擇位置更新策略,可以提高粒子間信息交互能力,加快粒子收斂速度。同時(shí),引入雙重變異限制策略提高了算法尋優(yōu)效率,有效降低任務(wù)執(zhí)行時(shí)間,實(shí)現(xiàn)總成本最小化。當(dāng)任務(wù)數(shù)為40時(shí),MSPSO總成本比LWPSO、GWOPSO、EEAPSO低14.4%、15.3%、11.2%。隨著任務(wù)數(shù)逐漸增多,各算法的總成本差額有所減小,當(dāng)任務(wù)達(dá)到100時(shí),MSPSO總成本比LWPSO、GWOPSO、EEAPSO低13.5%、12.8%、10.6%。

圖4 不同算法在不同任務(wù)量下的成本比較Fig.4 Cost comparison of different algorithms for different task volumes

此外,綜合考慮最大完成時(shí)間最少、任務(wù)執(zhí)行總時(shí)間最優(yōu)兩個(gè)目標(biāo),將尋找最佳調(diào)度方案問(wèn)題轉(zhuǎn)化為尋找適應(yīng)度最小值問(wèn)題。通過(guò)比較MSPSO與其他3種算法在適應(yīng)度值方面的表現(xiàn)來(lái)進(jìn)一步評(píng)價(jià)算法性能,在不同任務(wù)量下的對(duì)比實(shí)驗(yàn)結(jié)果如圖5所示。對(duì)于所有測(cè)試用例,MSPSO的適應(yīng)度值均遠(yuǎn)低于其他對(duì)比算法,且隨著迭代次數(shù)的增加,MSPSO與其他對(duì)比算法的適應(yīng)度差值逐漸增加,驗(yàn)證了MSPSO在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中的有效性。原因在于算法中引入了模擬退火算法,在調(diào)度過(guò)程中動(dòng)態(tài)更新粒子慣性權(quán)重,有效平衡了算法的全局搜索和局部搜索能力,避免粒子在算法后期陷入局部極值。在圖5 (a)中,MSPSO的適應(yīng)度值分別比LWPSO、GWOPSO、EEAPSO低10.5%、10.6%、7.6%。隨著任務(wù)數(shù)逐漸增多,各算法間的適應(yīng)度差值有所減小。在圖5 (d)中,MSPSO的適應(yīng)度值分別比LWPSO、GWOPSO、EEAPSO低9.9%、8.3%、6.5%。

圖5 不同算法在不同任務(wù)量下的適應(yīng)度值比較Fig.5 Comparison of fitness values of different algorithms under different tasks

綜合以上分析,MSPSO相比其他3種對(duì)比算法,在適應(yīng)度值、總成本兩個(gè)方面均表現(xiàn)出明顯優(yōu)勢(shì),適用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題。

5 結(jié)論

針對(duì)粒子群優(yōu)化算法在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中存在的不足,提出一種新的融合模擬退火算法、饑餓游戲搜索和雙重變異限制策略的多策略粒子群優(yōu)化算法(MSPSO)。模擬退火算法依概率動(dòng)態(tài)更新慣性權(quán)重,平衡算法的探索與開(kāi)發(fā);饑餓游戲搜索算法根據(jù)粒子的“饑餓程度”(對(duì)尋找最優(yōu)解的影響)優(yōu)化粒子位置公式,加快粒子收斂;雙重變異限制策略同時(shí)約束粒子位置和速度,避免粒子越界。通過(guò)與其他3種粒子群算法進(jìn)行對(duì)比實(shí)驗(yàn),在求解單模態(tài)問(wèn)題時(shí),MSPSO在適應(yīng)度平均值、最小值、標(biāo)準(zhǔn)差3個(gè)方面能夠獲得更優(yōu)數(shù)量級(jí)最優(yōu)解,在求解多模態(tài)和固定維數(shù)問(wèn)題時(shí),MSPSO同樣能獲得更優(yōu)值。此外,在求解云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí),在總成本、適應(yīng)度值最小化兩方面MSPSO均表現(xiàn)出明顯優(yōu)勢(shì)。當(dāng)任務(wù)數(shù)為40時(shí),MSPSO總成本比LWPSO、GWOPSO、EEAPSO低14.4%、15.3%、11.2%,這得益于動(dòng)態(tài)的位置更新策略提高了粒子間信息交互能力,加快算法尋優(yōu)效率,縮短任務(wù)執(zhí)行時(shí)間。MSPSO適應(yīng)度值分別低10.5%、10.6%、7.6%,這表明模擬退火算法在平衡算法探索與開(kāi)發(fā)、避免陷入局部極值的有效性。在其他維度中,MSPSO在適應(yīng)度值、總成本兩個(gè)方面也表現(xiàn)出明顯優(yōu)勢(shì),驗(yàn)證了MSPSO在求解云計(jì)算任務(wù)調(diào)度問(wèn)題中的有效性。

然而,隨著任務(wù)數(shù)的增加,MSPSO在執(zhí)行任務(wù)總成本方面的優(yōu)越性有所降低。在未來(lái)工作中將考慮在負(fù)載均衡、資源利用率等方面進(jìn)行改進(jìn),進(jìn)一步優(yōu)化算法性能,使其能夠在大規(guī)模任務(wù)的場(chǎng)景中也表現(xiàn)出明顯的優(yōu)勢(shì)。