改進(jìn)松鼠搜索算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度

陳孝如，曾碧卿

(1.廣州軟件學(xué)院 軟件工程系，廣東 廣州 510990；2.華南師范大學(xué) 軟件學(xué)院，廣東 佛山 528225)

0 引 言

近年來，為了滿足大規(guī)模應(yīng)用程序的計(jì)算需求，云計(jì)算憑借其計(jì)算資源的高效性和靈活性得到了大規(guī)模部署[1]。云計(jì)算提供服務(wù)的主要形式有3種，分別為：基礎(chǔ)設(shè)施即服務(wù)(infrastructure as a service，IaaS)、平臺即服務(wù)(platform as a service，PaaS)以及軟件即服務(wù)(software as a service，SaaS)[2,3]。其中，IaaS可實(shí)現(xiàn)大規(guī)模應(yīng)用程序部署，能夠提供靈活和可擴(kuò)展計(jì)算資源的訪問[4]。然而，在IaaS云上高效且有效的執(zhí)行大規(guī)模任務(wù)調(diào)度，仍然是一個(gè)亟待解決的問題[5]。

近年來，各種啟發(fā)式算法被用于求解任務(wù)調(diào)度問題，取得了一定的成效[6]。然而，面對大規(guī)模計(jì)算任務(wù)時(shí)，元啟發(fā)式算法的計(jì)算時(shí)間較長，由于局部搜索與全局搜索過早收斂和失衡的影響，可能會使算法陷入局部最優(yōu)解。不同于傳統(tǒng)的元啟發(fā)式算法，松鼠搜索算法(squirrel search algorithm，SSA)[7]具有魯棒性和更快的收斂速度，在處理多目標(biāo)約束優(yōu)化問題的同時(shí)，可對復(fù)雜的多維搜索空間進(jìn)行有效地優(yōu)化。由于無需特定的算法參數(shù)，SSA已被用于解決任務(wù)調(diào)度、無線通信以及經(jīng)濟(jì)調(diào)度等優(yōu)化問題[8]。

基于上述分析，針對云計(jì)算中大規(guī)模應(yīng)用程序的任務(wù)調(diào)度問題，提出一種改進(jìn)SSA的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法，以對搜索空間進(jìn)行有效的優(yōu)化，合理調(diào)度多目標(biāo)任務(wù)。所提方法的創(chuàng)新點(diǎn)總結(jié)如下：

(1)為了實(shí)現(xiàn)任務(wù)的高效調(diào)度，構(gòu)建IaaS云模型，基于該模型設(shè)計(jì)多目標(biāo)任務(wù)調(diào)度算法框架，并將成本和執(zhí)行時(shí)間的最小化作為目標(biāo)函數(shù)，從而有效地將用戶任務(wù)分配給各種可用的處理單元；

(2)由于傳統(tǒng)SSA存在容易陷入局部最優(yōu)的問題，所提方法將入侵雜草優(yōu)化算法(invasive weed optimization，IWO)的空間變異和擴(kuò)散機(jī)制應(yīng)用于SSA，并利用改進(jìn)型SSA求解多目標(biāo)優(yōu)化問題，從而在最短時(shí)間內(nèi)尋得最優(yōu)調(diào)度方案。

1 相關(guān)研究

任務(wù)調(diào)度優(yōu)化分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化。單目標(biāo)優(yōu)化方法只對完工時(shí)間或成本進(jìn)行優(yōu)化。然而，由于云計(jì)算的快速發(fā)展，需要考慮到多個(gè)服務(wù)質(zhì)量(quality of service，QoS)目標(biāo)，使得任務(wù)調(diào)度成為一個(gè)多目標(biāo)優(yōu)化問題[9]。由于用戶和提供者各自具有不同的優(yōu)化目標(biāo)，故多目標(biāo)任務(wù)優(yōu)化問題較為復(fù)雜[10]。就目前的研究現(xiàn)狀而言，針對云環(huán)境下的多目標(biāo)任務(wù)調(diào)度優(yōu)化問題的求解，主要采用的方法有啟發(fā)式算法、分層方法以及帕累托優(yōu)化等[11,12]。

文獻(xiàn)[13]提出一種改進(jìn)的非支配排序遺傳算法得出Pareto最優(yōu)解集，并利用模糊優(yōu)選法對該解集進(jìn)行選優(yōu)，確定了產(chǎn)品開發(fā)任務(wù)調(diào)度的最優(yōu)執(zhí)行方案。通過兩個(gè)經(jīng)典多目標(biāo)測試函數(shù)的求解及對比分析結(jié)果表明了改進(jìn)算法的有效性和優(yōu)越性。但在優(yōu)化應(yīng)用程序的執(zhí)行時(shí)間、可靠性和負(fù)載平衡時(shí)未考慮計(jì)算資源的異構(gòu)性。文獻(xiàn)[14]提出了一種蟻群算法的測試任務(wù)并行任務(wù)調(diào)度優(yōu)化方法，對測試問題進(jìn)行描述并與蟻群算法結(jié)合，設(shè)計(jì)了啟發(fā)函數(shù)、狀態(tài)轉(zhuǎn)移規(guī)則；通過依據(jù)算法流程來得到測試速度最快的任務(wù)調(diào)度序列；在任務(wù)序列多解的問題上，主要是通過提出資源均衡度的評價(jià)標(biāo)準(zhǔn)，得到最優(yōu)的資源任務(wù)調(diào)度序列。然而，不同目標(biāo)的結(jié)果取決于所分配權(quán)重的值，這些權(quán)重值也許不能充分代表用戶的決策。此外，該方法只產(chǎn)生不適合多目標(biāo)決策問題的解決方案。

分層方法按順序優(yōu)化任務(wù)調(diào)度目標(biāo)，根據(jù)目標(biāo)的重要性確定任務(wù)調(diào)度目標(biāo)的優(yōu)化次序，并根據(jù)目標(biāo)的排序交替求解[15]。例如，文獻(xiàn)[16]提出一種基于蟻群算法的分層調(diào)度算法，將調(diào)度過程分為預(yù)分配、粗略調(diào)度和精細(xì)調(diào)度3個(gè)步驟，對目標(biāo)函數(shù)進(jìn)行順序優(yōu)化。測試結(jié)果表明，使用這種新機(jī)制可以有效地減少計(jì)算時(shí)間。文獻(xiàn)[17]提出一種基于離散粒子群算法的靜態(tài)任務(wù)調(diào)度方法；求解過程中假定任務(wù)是非優(yōu)先并且獨(dú)立的，使用負(fù)載平衡技術(shù)提高了方法的性能。然而，該方法時(shí)效性較差，優(yōu)化過程需要多次迭代，尤其是當(dāng)有多個(gè)目標(biāo)約束時(shí)[18]。

為了克服聚合和分層方法的缺點(diǎn)，提出了基于帕累托的優(yōu)化方法，以解決多目標(biāo)任務(wù)調(diào)度問題。帕累托方法為優(yōu)化問題的目標(biāo)找到了幾個(gè)最優(yōu)的折衷方案。使用帕累托支配的概念來為個(gè)體分配適應(yīng)度。帕累托方法不需要將多個(gè)目標(biāo)轉(zhuǎn)化為單目標(biāo)公式，并在一個(gè)單一的過程中產(chǎn)生多個(gè)權(quán)衡解決方案。文獻(xiàn)[19]提出了工作流任務(wù)調(diào)度問題的多目標(biāo)遺傳算法，在考慮任務(wù)優(yōu)先級的同時(shí)還兼顧了云計(jì)算中的任務(wù)能耗。使任務(wù)的完工時(shí)間和成本達(dá)到最小化。采用遺傳算法解決了完工時(shí)間、成本和能耗之間的帕累托最優(yōu)權(quán)衡問題，仿真結(jié)果表明了該方法的有效性。同樣，文獻(xiàn)[20]基于包括車輛云、路邊小云和集中式云三層體系結(jié)構(gòu)，提出一種混合自適應(yīng)粒子群優(yōu)化(hybrid adaptive particle swarm optimization，HAPSO)算法資源分配和任務(wù)優(yōu)化調(diào)度算法，可以有效地滿足來自道路用戶的大量任務(wù)請求，同時(shí)保持改進(jìn)的服務(wù)質(zhì)量。結(jié)果表明，對于多目標(biāo)優(yōu)化調(diào)度問題，HAPSO的收斂速度比標(biāo)準(zhǔn)粒子群優(yōu)化和自適應(yīng)粒子群優(yōu)化更具優(yōu)勢。然而，在帕累托任務(wù)調(diào)度方法中，由于帕累托優(yōu)勢是一個(gè)偏序，很難為下一代選擇合適的個(gè)體。因此，如果選擇算子不能保持足夠的多樣性，所得到的解可能無法覆蓋整個(gè)帕累托前沿，則在開發(fā)多目標(biāo)任務(wù)調(diào)度有效分配個(gè)體適應(yīng)度的同時(shí)保持對整個(gè)優(yōu)化方案的有效估計(jì)，仍是一個(gè)具有挑戰(zhàn)性的研究課題。

Jain M提出了SSA[21]，該算法模仿了飛松鼠的動態(tài)跳躍策略和特征，對于優(yōu)化問題的最優(yōu)搜索具有易于實(shí)現(xiàn)的優(yōu)點(diǎn)，并且不易陷入局部最優(yōu)。其數(shù)學(xué)模型主要包括食物和捕食者的位置，整個(gè)優(yōu)化過程包括夏季和冬季兩個(gè)階段。然而，與其它智能進(jìn)化算法相似，SSA也存在收斂精度低、收斂速度慢等缺點(diǎn)。根據(jù)SSA，全局搜索能力的單冬搜索方法不夠，使得算法容易陷入局部最優(yōu)。此外，隨機(jī)夏季搜索方法降低了收斂速度，收斂精度也降低[22]。為了提高算法的收斂精度和收斂速度，提出了一種改進(jìn)的松鼠搜索算法(improved squirrel search algorithm，ISSA)，包括跳躍搜索法和漸進(jìn)搜索法。當(dāng)松鼠與捕食者相遇時(shí)，將“逃逸”和“死亡”操作引入跳躍搜索方法，將“突變”操作引入漸進(jìn)搜索方法。在優(yōu)化過程中，ISSA還通過線性回歸選擇策略選擇合適的搜索方法。

2 系統(tǒng)模型與問題建模

2.1 IaaS云模型

(1)

2.2 多目標(biāo)調(diào)度的目標(biāo)函數(shù)

(2)

只考慮一個(gè)實(shí)例序列和一個(gè)定價(jià)方案，其中實(shí)例序列類型是計(jì)算密集型的。則任務(wù)調(diào)度 (ET,C) 的目標(biāo)函數(shù)為

minf=(ET,cost)e

(3)

2.3 調(diào)度算法框架

在整個(gè)調(diào)度過程中，如果計(jì)算資源(包括CPU和存儲系統(tǒng))無法滿足用戶的任務(wù)需求，則可以通過任務(wù)管理器進(jìn)行采集和處理任務(wù)數(shù)據(jù)。任務(wù)管理器具有接受和管理任務(wù)的功能，需要向調(diào)度器提供數(shù)據(jù)。任務(wù)管理器將通過成本、存儲和時(shí)間限制進(jìn)行工作分配，并且通過全局資源管理系統(tǒng)對分配的資源進(jìn)行了標(biāo)記。整個(gè)調(diào)度算法是在云計(jì)算平臺中進(jìn)行，兼容不同的物理服務(wù)器[23]。同時(shí)，可以訪問本地服務(wù)器資源管理(local server resource management，LRM)，每個(gè)LRM都支持許多虛擬機(jī)。IaaS云環(huán)境下的任務(wù)調(diào)度算法結(jié)構(gòu)如圖1所示。

圖1 IaaS云環(huán)境下的任務(wù)調(diào)度

云計(jì)算系統(tǒng)由多個(gè)數(shù)據(jù)中心組成，這些數(shù)據(jù)中心可以通過使用來自世界各地的互聯(lián)網(wǎng)進(jìn)行訪問，每個(gè)數(shù)據(jù)中心都有許多計(jì)算、存儲以及其它的資源。在每個(gè)服務(wù)器集群中，處理單元通過高帶寬連接網(wǎng)絡(luò)。在所提調(diào)度模型中，有效地將用戶任務(wù)分配給各種可用的處理單元，以優(yōu)化用戶成本和時(shí)間。

3 改進(jìn)型松鼠搜索算法

SSA是模擬飛行松鼠為躲避捕食者、尋找捕食的最佳地點(diǎn)以及以較小的代價(jià)進(jìn)行捕食的滑翔行為。飛行松鼠的覓食策略靈活多變，這可以幫助飛行松鼠以最佳的方式應(yīng)對食物資源。相比于其它搜索優(yōu)化算法，SSA對搜索空間要求較少，且搜索效率較高，但在優(yōu)化過程中也存在易陷入局部最優(yōu)解，收斂速度較慢的問題。

3.1 松鼠搜索算法

松鼠是一種多樣的樹棲和夜間活動的嚙齒動物，其類似降落傘的薄膜特別適合滑翔。其滑翔搜索能力可以幫助其躲避捕食者、尋找捕食的最佳地點(diǎn)和以較小的代價(jià)進(jìn)行捕食。松鼠可以通過展示動態(tài)覓食行為來優(yōu)化食物資源的利用[24]。

在溫暖的秋天，由于橡樹籽數(shù)量多，且能夠滿足松鼠在秋天的營養(yǎng)需要，當(dāng)它們發(fā)現(xiàn)橡樹籽后，會立即食用。在滿足了每天的能量需求后，開始尋找冬天的最佳食物來源；而在冬季，森林中樹葉的脫落增加了被捕食的風(fēng)險(xiǎn)，因此它們變得不活躍，但不冬眠。由于較低的溫度會導(dǎo)致更高的營養(yǎng)需求，儲存山核桃仁將有助于它們在極端天氣條件下維持能量需求，從而提高存活概率。因此，根據(jù)營養(yǎng)需要，有選擇地吃一些堅(jiān)果，而將其它堅(jiān)果儲存起來，這使得兩種堅(jiān)果得到了充分利用。到冬季末，松鼠又活躍起來了開始覓食。如此循環(huán)往復(fù)，一直延續(xù)到松鼠生命的結(jié)束。在這個(gè)過程中，它們通過改變位置來探索不同的森林區(qū)域。SSA的尋優(yōu)流程如圖2所示。

圖2 SSA的流程

為了簡化數(shù)學(xué)模型，需要考慮以下假設(shè)[25]：

(1)森林里有n只會飛的松鼠，假設(shè)樹上只有一只會飛的松鼠；

(2)每只松鼠都獨(dú)立地尋找食物，并通過表現(xiàn)出動態(tài)的覓食行為來優(yōu)化現(xiàn)有食物資源的利用；

(3)在森林中，只有3種樹可供選擇，如普通樹、橡樹(橡樹籽的來源)和山核桃樹(山核桃仁的來源)；

(4)假設(shè)森林區(qū)域由k橡樹和一棵山核桃樹組成。

在SSA中，對于d維優(yōu)化問題，每個(gè)松鼠的位置可以用一個(gè)d維向量來表示

Xi=[xi1,xi2,…,xij,…,xid],i=1,2,…,nxij=xmin+δ(0,1)·(xmax-xmin),j=1,2,…,d

(4)

式中：xmax和xmin分別是飛行松鼠位置的上下限，δ(0,1) 是[0,1]范圍內(nèi)的均勻分布隨機(jī)數(shù)。

根據(jù)用戶定義的適應(yīng)度函數(shù)，計(jì)算出每只飛鼠所在地的適應(yīng)度值f(Xi)， 對應(yīng)的值描述了可供搜索的食物源的質(zhì)量，即最佳食物源(山核桃樹)、正常食物源(橡樹)和無食物源(普通樹)。

3.2 引入空間變異與擴(kuò)散機(jī)制

SSA算法在優(yōu)化過程中不可避免地陷入局部最優(yōu)解，收斂速度較慢。因此，受IWO的啟發(fā)，將空間變異和擴(kuò)散行為結(jié)合到SSA中，提出了一種ISSA。

第i只飛行的松鼠在一定范圍內(nèi)選擇樹Ni上降落，以確保在該范圍內(nèi)找到最佳食物來源，這個(gè)過程被稱為空間變異。Ni的個(gè)數(shù)由IWO算法中的生長和再生思想決定

(5)

式中：dmax和dmin分別是空間變化的最大和最小數(shù)量。f(·) 是適應(yīng)度函數(shù)，fmax、fmin分別是f(·) 的最大值和最小值。

然后，由正態(tài)分布的空間擴(kuò)散產(chǎn)生Ni隨機(jī)位置，平均值為第i只飛行松鼠的當(dāng)前位置，標(biāo)準(zhǔn)差為σt， 其中σt的值根據(jù)迭代次數(shù)確定為

(6)

式中：σinitial為初始標(biāo)準(zhǔn)差，σfinal為最終標(biāo)準(zhǔn)差，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，n為非線性調(diào)和指數(shù)，常取3。

由上可知，空間擴(kuò)散產(chǎn)生的新Ni位置可以表示為

(7)

式中：N(0,1) 是標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)。

對隨機(jī)生成的Ni適應(yīng)度函數(shù)值進(jìn)行排序，選擇適應(yīng)度函數(shù)值最小的位置作為第i只飛行松鼠的當(dāng)前新位置。式(7)描述了ISSA的基本特征，即早期強(qiáng)調(diào)全局搜索，后期強(qiáng)調(diào)局部搜索。

ISSA的偽代碼如算法1所示。

算法1：ISSA的偽代碼。

Begin

定義輸入?yún)?shù)：εg是隨機(jī)滑行距離；R是[0,1]范圍內(nèi)的隨機(jī)數(shù)；Gc是滑動常數(shù)，常取1.9；Pd為捕食者存在概率。

(1) 生成n只飛行松鼠的隨機(jī)位置：

Xi=[xi1,xi2,…,xid],i=1,2,…,n

(2) 評估每只飛行松鼠的位置是否適合。

(3) 通過空間變化和擴(kuò)散進(jìn)行重新定位：

(4) 根據(jù)它們的適應(yīng)值， 按升序排列飛行松鼠的位置。

(5) 上報(bào)山核桃樹、 橡樹和普通樹上的飛行松鼠。

(6) 隨機(jī)選擇一些在正常樹上的飛行松鼠向山核桃樹移動， 其余的向橡樹移動。

(7) While 不滿足停止條件

(8) Fort=1 ton1(在橡樹上向山核桃樹飛去的松鼠總數(shù))

(9) ifR1≥Pd

(12) end

(13) end

(14) Fort=1 ton2(在正常樹上向橡樹移動的飛行松鼠的總數(shù))

(15) ifR2≥Pd

(18) end

(19) end

(20) Fort=1 ton3(在普通樹上向山核桃樹移動的飛行松鼠總數(shù))

(21) ifR3≥Pd

(24) end

(25) end

(27) 使用更新季節(jié)常數(shù)Smin的最小值:

(28) 通過空間變化和擴(kuò)散進(jìn)行重新定位：

(29) 松鼠在山核桃樹上的位置是最終的最優(yōu)解。

End

4 仿真及分析

4.1 仿真設(shè)置

CloudSim仿真工具包支持模擬云計(jì)算場景，支持大規(guī)模計(jì)算環(huán)境的建模和仿真，可為數(shù)據(jù)中心、物理主機(jī)、云服務(wù)代理和調(diào)度系統(tǒng)提供建模支持，因此，在IaaS云環(huán)境下使用CloudSim 3.0.3仿真工具包實(shí)現(xiàn)所提方法的調(diào)度方案。在實(shí)驗(yàn)中，一個(gè)IaaS云提供商擁有一個(gè)數(shù)據(jù)中心、兩個(gè)主機(jī)和20個(gè)不同配置的虛擬機(jī)。數(shù)據(jù)中心和主機(jī)的配置見表1。虛擬機(jī)(virtual machine，VM)配置基于當(dāng)前amazonec2產(chǎn)品，見表2，虛擬機(jī)的處理能力(即工作負(fù)載參數(shù))見表3。

此外，ISSA算法的參數(shù)見表4。

4.2 性能指標(biāo)

將完工時(shí)間、成本(財(cái)務(wù)成本)、超體積作為性能指標(biāo)。ET是虛擬機(jī)最晚的完成時(shí)間，最小ET意味著用戶在執(zhí)行任務(wù)時(shí)要付出適度的成本，因?yàn)樵品?wù)中用戶通常是按每小時(shí)的虛擬機(jī)使用量收費(fèi)的。成本是從IaaS云提供商租賃VMs獲得的。

表1 IssA云環(huán)境的參數(shù)設(shè)置

表2 虛擬機(jī)的配置與類型

表3 工作負(fù)載參數(shù)

表4 ISSA算法的參數(shù)設(shè)置

ET也稱為總執(zhí)行時(shí)間，是執(zhí)行任務(wù)集合時(shí)使用的所有VMs最新完成時(shí)間，表示如下

(8)

成本是VMs成本與ET的乘積之和，四舍五入得最接近的整數(shù)表示為

(9)

超體積(hypervolume，HV)指標(biāo)是通過計(jì)算得到非支配解決方案和參考點(diǎn)之間目標(biāo)函數(shù)的空間體積，通過提供解集收斂性和多樣性之間的關(guān)系獲得的，是衡量多目標(biāo)優(yōu)化方法求解質(zhì)量的一種綜合指標(biāo)，計(jì)算如下

(10)

為了獲得HV值，每個(gè)方法在所有工作負(fù)載實(shí)例上獨(dú)立運(yùn)行30次，并將每個(gè)算法獲得的30次運(yùn)行的解合并成一個(gè)參考集，然后，在參考集上選取非支配解，形成帕累托前沿(pareto front，PF)，剔除由真PF支配的結(jié)果。將制造周期和成本標(biāo)準(zhǔn)化，使用參考點(diǎn)(1.1,1.1)計(jì)算HV值，該值越大，說明解決方案與參考點(diǎn)的相對空間體積越大，解的質(zhì)量越高。

4.3 調(diào)度性能對比及分析

為了驗(yàn)證所提方法在成本和時(shí)間方面的性能，將其與文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]中的方法進(jìn)行對比分析。其中文獻(xiàn)[17]提出一種基于PSO算法的靜態(tài)任務(wù)調(diào)度方法，求解過程中假定任務(wù)是非優(yōu)先并且獨(dú)立的，使用負(fù)載平衡技術(shù)提高了方法的性能。文獻(xiàn)[19]采用遺傳算法(genetic algorithm，GA)算法解決了完工時(shí)間、成本和能耗之間的帕累托最優(yōu)權(quán)衡問題，在考慮任務(wù)優(yōu)先級的同時(shí)還兼顧了云計(jì)算中的任務(wù)能耗，使任務(wù)的完工時(shí)間和成本達(dá)到最小化。文獻(xiàn)[21]提出了SSA算法，模仿了飛松鼠的動態(tài)跳躍策略和特征，對于優(yōu)化問題的最優(yōu)搜索具有易于實(shí)現(xiàn)的優(yōu)點(diǎn)。

為了確保不同方法之間的公平比較，工作負(fù)載實(shí)例的初始生態(tài)系統(tǒng)(總體)、生成數(shù)、停止條件和硬件資源都是相同的。并且NASA Ames iPSC/860是一些標(biāo)準(zhǔn)格式的工作負(fù)載，用于評估分布式系統(tǒng)的性能，而Uniform是合成工作負(fù)載。

4.3.1 不同并行任務(wù)種類下的執(zhí)行時(shí)間和成本

對于所有測試的工作負(fù)載實(shí)例，將所提方法獲得最佳結(jié)果所耗費(fèi)的執(zhí)行時(shí)間(以秒為單位)與文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]進(jìn)行比較，結(jié)果如圖3所示。

圖3 執(zhí)行時(shí)間的對比結(jié)果

從圖3可以看出，對于所有測試的工作負(fù)載實(shí)例，所提方法的執(zhí)行時(shí)間均少于其它對比方法。所提方法利用改進(jìn)ISSA能夠在較短的計(jì)算時(shí)間內(nèi)獲得更高質(zhì)量的解決方案，優(yōu)于文獻(xiàn)[21]中傳統(tǒng)的SSA。文獻(xiàn)[17]和文獻(xiàn)[19]分別使用GA和PSO算法，雖能夠在一定程度上縮短執(zhí)行時(shí)間，但隨著任務(wù)數(shù)量的增加，算法處理效率不高，導(dǎo)致執(zhí)行時(shí)間較長。由此可驗(yàn)證所提方法是求解多目標(biāo)任務(wù)調(diào)度優(yōu)化問題的有效方法。

此外，由5000個(gè)大小的工作負(fù)載實(shí)例的非支配解決方案如圖4所示。

由圖4可知，無論在NASA標(biāo)準(zhǔn)或是Uniform標(biāo)準(zhǔn)下，所提方法的性能明顯優(yōu)于其它對比方法。如圖4(a)所示，在NASA標(biāo)準(zhǔn)下，所提方法的顯著性能歸功于其底層SSA算法的全局收斂性，并且引入空間變異與擴(kuò)散機(jī)制，從而使其能夠獲得更好的收斂性，有效地處理大的搜索空間，因此，其對于成本的控制優(yōu)于其它文獻(xiàn)所提方法；其中，文獻(xiàn)[17]所提方法由于缺乏全局搜索能力，因此其性能相對較差；而文獻(xiàn)[21]和文獻(xiàn)[19]所提方法則處于中等水平。在Uniform標(biāo)準(zhǔn)下，如圖4(b)所示，文獻(xiàn)[17]的GA和文獻(xiàn)[19]的PSO算法在處理多目標(biāo)調(diào)度問題，處理效率一般，且全局收斂性有待提高；文獻(xiàn)[21]方法與所提方法性能較為接近，但所提方法憑借其變異與擴(kuò)散機(jī)制帶來的更好的收斂性，具有更好的性能，因此略優(yōu)于文獻(xiàn)[21]所提方法。

4.3.2 不同任務(wù)數(shù)量下的HV指標(biāo)提升

對于不同任務(wù)數(shù)量，幾種方法在HV指標(biāo)方面的對比結(jié)果見表5。

從表5中可以看出，對于所有工作負(fù)載實(shí)例，相比文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]提出的方法，所提方法的HV值有顯著提高。在不同的工作負(fù)載下，所提方法的HV值比文獻(xiàn)[21]的SSA算法提高了16.32%～35.51%，而相比文獻(xiàn)[19]的PSO算法性能提升了37.75%～63.89%，與文獻(xiàn)[17]中的GA相比，提高了94.40%～120.24%。由此可見，所提方法具有較好的收斂性和解決方案的多樣性，從而得到全局最優(yōu)解決方案，完成多目標(biāo)任務(wù)調(diào)度，實(shí)現(xiàn)成本和執(zhí)行時(shí)間最小化。

圖4 非支配解決方案的對比

表5 不同任務(wù)數(shù)量的HV指標(biāo)對比結(jié)果

5 結(jié)束語

針對云環(huán)境中多目標(biāo)任務(wù)調(diào)度優(yōu)化所存在的收斂慢且易陷入局部最優(yōu)的問題，提出一種改進(jìn)SSA的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法?；贗aaS云模型，設(shè)計(jì)了多目標(biāo)任務(wù)調(diào)度算法框架，并且將成本和執(zhí)行時(shí)間的最小化作為目標(biāo)函數(shù)，利用ISSA進(jìn)行問題求解，其中引入空間變異與擴(kuò)散機(jī)制改進(jìn)傳統(tǒng)的SSA。此外，在CloudSim模擬器工具包中，使用NASA標(biāo)準(zhǔn)工作負(fù)載和Uniform合成工作負(fù)載對所提方法進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明，所提方法的成本、執(zhí)行時(shí)間和HV均少于其它對比方法，以NASA為例，當(dāng)任務(wù)數(shù)量為5000時(shí)，其執(zhí)行時(shí)間和HV分別是32.12 s和21.50，并且當(dāng)執(zhí)行時(shí)間達(dá)到2500 s時(shí)，所提方法快速收斂，且成本僅約為10元。

所提方法具有較大的服務(wù)質(zhì)量提升空間，可以對其進(jìn)行擴(kuò)展，以處理對可靠性和安全性需求較高的大型負(fù)載實(shí)例。此外，實(shí)驗(yàn)僅考慮了NASA和Uniform兩種工作實(shí)例，后續(xù)工作中將考慮更多實(shí)例類型，以提高所提方法的普適性。