丁岳偉,竇飛飛

(1.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海　200093;2.上海理工大學(xué) 計(jì)算機(jī)軟件技術(shù)研究所,上海　200093)

?

多目標(biāo)貓群優(yōu)化算法支持下的云計(jì)算任務(wù)調(diào)度

丁岳偉1,竇飛飛2

(1.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200093;2.上海理工大學(xué) 計(jì)算機(jī)軟件技術(shù)研究所,上海200093)

摘要針對云環(huán)境下任務(wù)調(diào)度易出現(xiàn)多目標(biāo)沖突的問題,提出一種改進(jìn)的基于貓群的多目標(biāo)優(yōu)化算法。該算法模擬貓的行為模式,采用基于線性混合比率的貓行為選擇方式來提高全局搜索和局部尋優(yōu)能力;并在迭代過程中結(jié)合任務(wù)完成時(shí)間和任務(wù)費(fèi)用支出,引入一個(gè)可調(diào)節(jié)的多目標(biāo)集成效用函數(shù),實(shí)現(xiàn)了資源與任務(wù)的智能調(diào)度。實(shí)驗(yàn)結(jié)果表明,所提算法不僅求解質(zhì)量高,且在求解速度和調(diào)度消耗方面均優(yōu)于多目標(biāo)遺傳算法和多目標(biāo)粒子群算法。

關(guān)鍵詞多目標(biāo)貓群算法;線性混合比率;多目標(biāo)集成效用函數(shù);智能調(diào)度

云計(jì)算作為一種新技術(shù),近年來成為信息領(lǐng)域的研究熱點(diǎn),其將通過Internet連接的各類資源整合,構(gòu)成共享虛擬資源池,為用戶提供便捷、優(yōu)質(zhì)的服務(wù)[1-2]。在這種模式下,如何快速實(shí)現(xiàn)資源與用戶需求的智能匹配和多目標(biāo)優(yōu)化調(diào)度尤為重要[3]。

目前,云計(jì)算調(diào)度中多目標(biāo)優(yōu)化問題通常采用啟發(fā)式算法,其中較典型的有多目標(biāo)遺傳算法、多目標(biāo)粒子群法等。但多目標(biāo)遺傳算法具有參數(shù)復(fù)雜、局部搜索能力不足、搜索速度慢等缺點(diǎn)[4];多目標(biāo)粒子群收斂速度快,但由于自身機(jī)制更新的限制,求解離散問題時(shí)易陷入局部最優(yōu)[5]。

貓群算法(Cat Swarm Optimization,CSO)是由Shu-Chuan Chu等人在2006年提出的一種基于貓的群體智能算法[6]。在貓群算法應(yīng)用方面,Santosa[7]提出利用貓群算法來解決聚類問題;劉瓊等人[8]提出利用多目標(biāo)貓群算法來求解混流裝配線排序問題。雖然貓群算法在眾多問題上取得了較好的應(yīng)用,但在云計(jì)算任務(wù)調(diào)度方面的研究并不多,其具有較強(qiáng)的研究意義。

本文在研究了云計(jì)算任務(wù)調(diào)度和貓群算法的基礎(chǔ)上提出了一種多目標(biāo)貓群調(diào)度方案(MO-CSO),使用加權(quán)方法定義了一個(gè)基于Makespan和Total Cost的多目標(biāo)模型并針對目前CSO算法進(jìn)化過程中一般采用固定的混合比率,而不能根據(jù)進(jìn)化程度有效分配全局貓和局部貓的問題,提出了一種基于線性混合比率的貓行為模式選擇方法。MO-CSO算法能夠同時(shí)進(jìn)行全局搜索和局部尋優(yōu),不但解決了多目標(biāo)遺傳算法局部搜索能力不足以及多目標(biāo)粒子群算法在解決離散問題時(shí)易陷入局部最優(yōu)的問題,而且具有良好的收斂速度。

1相關(guān)模型

1.1任務(wù)調(diào)度模型

云環(huán)境下使用加權(quán)有向無環(huán)圖(Directed Acyclic Graph,DAG)來描述任務(wù)調(diào)度算法,節(jié)點(diǎn)表示任務(wù),邊表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系。其各參數(shù)的描述如下:

(1)任務(wù)列表。定義G(T,E),T(x)={T1,T2,…,Tx}為n個(gè)任務(wù)序列,E代表任務(wù)之間的數(shù)據(jù)相關(guān)性;

(2)虛擬機(jī)資源列表。定義VM(y)={VM1,VM2,…,VMy}為存儲(chǔ)于數(shù)據(jù)中心的虛擬機(jī)資源,這些資源要跟來自網(wǎng)絡(luò)的用戶的任務(wù)需求進(jìn)行映射;

(3)定義可利用資源間的數(shù)據(jù)傳輸開銷為d_cost(mn),m,n分別表示任務(wù)Tm和任務(wù)Tn,其中m

圖1　任務(wù)調(diào)度結(jié)構(gòu)模型

假定每項(xiàng)任務(wù)對應(yīng)所有資源的執(zhí)行時(shí)間和開銷均已知,其取值均在一些價(jià)格策略的規(guī)定范圍之內(nèi)。同樣,任務(wù)之間數(shù)據(jù)傳遞的開銷也是已知的。

1.2多目標(biāo)調(diào)度模型

為實(shí)現(xiàn)基于Makespan和資源有效利用的多目標(biāo)任務(wù)調(diào)度算法,本文使用加權(quán)方法定義了一個(gè)衡量開銷的多目標(biāo)函數(shù),即運(yùn)行時(shí)間和所需計(jì)算資源費(fèi)用的加權(quán)之和[9],而系統(tǒng)調(diào)度的目的即滿足

min(wc×T_cost(VMi)+wt×T_time(VMi))

(1)

定義T_cost(VMi)為可用資源VMi上的所有開銷,包括對應(yīng)所有任務(wù)的執(zhí)行開銷,以及這些任務(wù)與其相互依賴的任務(wù)間進(jìn)行數(shù)據(jù)傳輸?shù)拈_銷。e_cost(mi)是指任務(wù)Tm使用資源VMi的開銷,d_cost(mn)表示處于不同虛擬機(jī)資源上的任務(wù)Tm和Tn進(jìn)行數(shù)據(jù)傳輸?shù)拈_支,則有

(2)

定義T_time(VMi)虛擬機(jī)資源VMi上的所有任務(wù)的執(zhí)行時(shí)間,etmi表示在資源VMi的任務(wù)Tm的執(zhí)行時(shí)間,則有

(3)

基于之前的描述,本文將目標(biāo)函數(shù)定義為

(4)

其中,權(quán)重因子wm,wt∈[0,1],且wm+wt=1。wm表示費(fèi)用的權(quán)重;wt表示運(yùn)行時(shí)間的權(quán)重;權(quán)重是一個(gè)偏好參數(shù),用戶可根據(jù)需要加以改變。

2CSO算法

貓群算法是一種建立在貓行為模式和群體智能基礎(chǔ)上的新型仿生算法。該算法模擬貓的追蹤過程來搜索優(yōu)化問題的全局最優(yōu)解,再通過貓的搜尋模式來確定局部最優(yōu)解,貓的位置信息即為待求優(yōu)化問題的最優(yōu)解或可能解。該算法具有較好的收斂速度,在迭代過程中淘汰自適應(yīng)性較差的個(gè)體,減少了無效搜索的開銷。

3MO-CSO算法描述

云計(jì)算任務(wù)調(diào)度是一個(gè)任務(wù)和虛擬機(jī)資源進(jìn)行相互尋找,動(dòng)態(tài)匹配的過程。因此,在該算法中,可將任務(wù)和虛擬機(jī)資源分別模擬為目標(biāo)所在的維度空間和貓群。貓群執(zhí)行MO-CSO算法尋找到目標(biāo)所在位置并進(jìn)行追捕,直至輸出最優(yōu)解,即找到最佳調(diào)度方案。

標(biāo)準(zhǔn)CSO算法采用固定比率(MR)來分配整個(gè)貓群在執(zhí)行搜尋模式和追蹤模式上的數(shù)量,但這種分配方式不能根據(jù)算法的進(jìn)化程度調(diào)整全局搜索和局部搜索的比重。研究發(fā)現(xiàn),算法前期追蹤貓的比率增大可提高的全局搜索能力,促進(jìn)算法收斂到Pareto前沿的速度;后期若加大搜索貓的比率則會(huì)提高局部搜索能力,有效搜索出非支配解,保證算法的收斂性[10]。本文針對此問題提出一種基于線性混合比率的貓行為模式分配公式

(5)

其中,算法采取的最大混合比率為MRmax,最小混合比率MRmin。n為當(dāng)前運(yùn)行代數(shù);IT_max為最大迭代次數(shù)。

MO-CSO算法具體過程如下:

輸入貓群數(shù)量和D維坐標(biāo)

輸出貓的位置與任務(wù)調(diào)度方案

1./*initial N,D*/ //初始化貓群數(shù)量和D維坐標(biāo);

2.Assess FV of all cats and store non-dominated cats;

3.Divide all cats into SM and TM by MR;

4.While (FV !=min(OF)) do{

5.Update MR;

6.If(cat ∈ SM){

7.SMP←generate replicas of cat;

8.FV← check all replicas fitness value;}

9.Eles (cat ∈TM){

10.V←get velocity of cat;

11.Update D_location;

12.If (D_location>Max_space){

13. D_location=-D_location;

14.Else;

15.SF← check all replicas fitness value;}

16.Output D_location;}

MO-CSO算法中貓群有兩種狀態(tài)模式,搜尋模式(Seeking Mode(SM))和追蹤模式(Tracing Mode(TM))。

3.1貓群搜尋模式

搜尋模式中的貓群處于休息狀態(tài),但其卻不會(huì)放松警惕,會(huì)對四周環(huán)境進(jìn)行觀察和搜尋。在搜尋模式下涉及到的參數(shù)有:

搜尋記憶池(Seeking Memory Pool,SMP):貓群在搜尋過程中,每個(gè)個(gè)體會(huì)進(jìn)行自身搜尋操作,并復(fù)制出新的個(gè)體來填充搜尋記憶池。

自適應(yīng)度值(Fitness Value,FV):根據(jù)Pareto前沿來判定貓的自適應(yīng)度值。

搜尋模式的具體步驟如下:

步驟1每只貓進(jìn)行自身搜尋,并復(fù)制多份當(dāng)前位置用來填滿搜尋記憶池;

步驟2隨機(jī)的初始化每只貓的維數(shù);

步驟3評估每個(gè)副本的自適應(yīng)值;

步驟4從記憶池非支配解中找出最優(yōu)復(fù)制位置;

步驟5將最優(yōu)的復(fù)制位置替換當(dāng)前的個(gè)體位置。

3.2貓群追蹤模式

追蹤模式下,貓群會(huì)以很快的速度向搜尋模式中發(fā)現(xiàn)的目標(biāo)移動(dòng)。追蹤模式類似粒子群算法,即用個(gè)體的位置(D_location)來表示優(yōu)化問題的解,根據(jù)速度-位移模型來更新每一維個(gè)體的值。定義第i只貓?jiān)贒維空間中位置和速度的具體步驟如下:

(1)根據(jù)下面的公式計(jì)算出第i只貓最新的速度

(6)

(2)根據(jù)式(7)計(jì)算更新第n只貓的位置

(7)

(3)判斷第n只貓的當(dāng)前位置中的任一維位置是否超出了搜索空間,若超出則將該值作為相應(yīng)的邊界值,觸到邊界值后反方向進(jìn)行搜索;

(4)計(jì)算每只貓的自適應(yīng)度值;

(5)用非支配解的貓來更新解集。

圖2　MO-CSO 算法流程

4實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)是在CloudSim的仿真平臺(tái)上完成的,為確保數(shù)據(jù)的可靠性進(jìn)行了多組仿真實(shí)驗(yàn),每組運(yùn)行了10次,將20次實(shí)驗(yàn)結(jié)果取平均值得到最后效果。

4.1實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)?zāi)M了10個(gè)具有相互依賴關(guān)系的任務(wù)在3個(gè)VM資源上的調(diào)度,為使實(shí)驗(yàn)結(jié)果更加直觀,省略了描述云任務(wù)和虛擬機(jī)資源的部分參數(shù),比如處理能力,存儲(chǔ)能力、帶寬等。可用虛擬機(jī)資源與對應(yīng)任務(wù)之間的開銷和執(zhí)行時(shí)間值如表1所示。

表1　虛擬機(jī)資源與任務(wù)之間的執(zhí)行開銷

可用虛擬機(jī)資源之間數(shù)據(jù)傳輸開銷如表2所示。

表2　可用虛擬機(jī)資源之間的傳輸開銷

4.2實(shí)驗(yàn)結(jié)果分析

在保持測試條件和環(huán)境相同的情況下,本文分別實(shí)現(xiàn)了MO-GA算法、MO-PSO算法、MO-CSO算法,并結(jié)合各類算法的總?cè)蝿?wù)平均完成時(shí)間Makespan 和總?cè)蝿?wù)平均開銷Totalcosts 兩大指數(shù)進(jìn)行了對比測試。

圖3為Mo-GA算法在應(yīng)用本文多目標(biāo)函數(shù)后的實(shí)驗(yàn)結(jié)果。

圖3　MO-GA算法實(shí)驗(yàn)結(jié)果

圖4為Mo-PSO算法在應(yīng)用了本文多目標(biāo)函數(shù)后的實(shí)驗(yàn)結(jié)果。

圖4　MO-PSO算法實(shí)驗(yàn)結(jié)果

圖5為本文所提算法Mo-CSO的實(shí)驗(yàn)結(jié)果。

圖5　MO-CSO算法實(shí)驗(yàn)結(jié)果

通過對比不同的迭代次數(shù)中3種算法的多目函數(shù)min(OF)的取值,可得到較直觀的優(yōu)化效果,如圖6所示,MO-CSO算法的min(OF)值相比另外兩種算法較小,即任務(wù)調(diào)度的時(shí)間和開銷均得到了優(yōu)化,且這種優(yōu)化效果會(huì)隨著迭代次數(shù)的增大更加明顯。

圖6　3種算法min(OF)值對比

5結(jié)束語

本文算法相對于多目標(biāo)貓群算法,不再采用固定的比率分配整個(gè)貓群在執(zhí)行搜尋模式和追蹤模式上的數(shù)量,而是采用一種線性混合比率,這種改進(jìn)提高了全局搜索和局部尋優(yōu)的能力。此外,算法設(shè)計(jì)了一個(gè)基于調(diào)度時(shí)間和費(fèi)用的多目標(biāo)集成效用函數(shù)作為評價(jià)算法優(yōu)劣的指標(biāo)。實(shí)驗(yàn)分別對MO—CSO 和MO-GA和MO-PSO算法進(jìn)行測試,通過對比可知本文所提算法MO—CSO在解決云計(jì)算任務(wù)調(diào)度問題中具有良好的性

能,尤其在迭代次數(shù)較多時(shí)優(yōu)勢更加明顯。下一步工作將研究建立更加符合云計(jì)算調(diào)度中的多目標(biāo)調(diào)度模型,達(dá)到高效的優(yōu)化效果[11]。

參考文獻(xiàn)

[1]Stanoevska-Slabeva K,Wozniak T.Cloud basics-an introduction to cloud computing[J].Berlin Heidelberg:Springer,2010,8(4):47-61.

[2]Kwon T,Won Gi Yoo,Won-Ja Lee.Next-generation sequencing data analysis on cloud computing[J].Genes & Genomics,2015,37(3):489-501.

[3]Ghanbari S,Orhman M.A priority based job scheduling algorithm in cloud computing[J].Procedia Engineering,2012,50(9):778-785.

[4]Marjan Abdeyazdan,Amir Masoud Rahmani.Multiprocessor task scheduling using a new prioritizing genetic algorithm based on number of task children[M].New York:Distributed and Parallel Systems,2008.

[5]郭力爭,耿永軍,姜長源,等.云計(jì)算環(huán)境下基于粒子群算法的多目標(biāo)優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,33(7):2358-2362.

[6]Chu S C,Tsai P W,Pan J S.Cat swarm optimization[C].Berlin,Germany:9th Pacific Rim International Conference on Artificial Intelligence,Springer Verlag,2006.

[7]Santosa B,Ningrum M K.Cat swarm optimization for clustering[C].Malaysia:IEEE International Conference for Soft Computing and Pattern Recognition(SOCPAR),2009.

[8]劉瓊,范正偉,張超勇,等.基于多目標(biāo)貓群算法的混流裝配線排序問題[J].計(jì)算機(jī)集成制造系統(tǒng),2014,19(2):333-342.

[9]Wang X,Yeo C S,Buyya R,et al.Optimizing the makespan and reliability for workflow applications with reputation and a look-head genetic algorithm[J].Future Generation Computer Systems,2011,27(8):1124-1134.

[10]Panda Ganapati,Pradhan Pyari Mohan,Majhi Babita.IIR System identification using cat swarm optimization[J].Experiment Systems with Applications,2011,38(10):12671-12683.

[11]Pradhan Pyari Mohan,Panda Ganapati.Solving multi-objective problems using cat swarm optimization[J].Experiment Systems with Applications,2012,39(3):2956-2964.

Task Scheduling in Cloud Computing Based on Optimized Multi-objective Cat Swarm Algorithm

DING Yuewei1,DOU Feifei2

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200093,China;2.Institute of Computer Software Technology,

University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractConsidering the multi-objective conflict problem for job scheduling in cloud computing environment,this paper proposes an optimized multi-objective cat swarm algorithm (MO-CSO) based on cat behavior using the linear mixture ratio selection method to improve the global search and local optimization ability.The algorithm combines the makespan and total cost to propose an adjustable multi-objective integrated utility function,which implements the intelligent dispatching of resources and task.The experimental results show that the optimized MO-CSO not only has high quality,but also are superior in solving speed and scheduling costs to the multi-objective genetic algorithm (MO-GA) and the multi-objective particle swarm optimization (MO-PSO) algorithm.

Keywordsmulti-objective cat swarm algorithm;linear mixing ratio;a multi-objective integrated utility function;intelligent scheduling

中圖分類號TP306.1

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)02-004-05

doi:10.16180/j.cnki.issn1007-7820.2016.02.002

作者簡介:丁岳偉(1961—),男,教授,碩士生導(dǎo)師。研究方向:計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用等。竇飛飛(1990—),女,碩士研究生。研究方向:云計(jì)算等。

基金項(xiàng)目:上海市自然科學(xué)基金資助項(xiàng)目(14ZR1440100);上海市教委科研創(chuàng)新重點(diǎn)基金資助項(xiàng)目(14ZS167)

收稿日期:2015- 08- 25