自適應(yīng)CPSO算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用

張曉麗

(西安航空學(xué)院 計(jì)算機(jī)學(xué)院,陜西 西安 710077)

自適應(yīng)CPSO算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用

張曉麗

(西安航空學(xué)院 計(jì)算機(jī)學(xué)院,陜西 西安 710077)

云計(jì)算環(huán)境中的任務(wù)調(diào)度問題一直是云計(jì)算研究的重點(diǎn)。為了克服傳統(tǒng)PSO算法易陷入局部最優(yōu)的缺陷，針對(duì)云計(jì)算的編程模型框架，將混沌優(yōu)化搜索技術(shù)應(yīng)用于粒子群優(yōu)化算法，提出一種基于Tent映射的自適應(yīng)混沌粒子群任務(wù)調(diào)度算法。該算法結(jié)合了PSO算法的快速收斂性和混沌運(yùn)動(dòng)的遍歷性、隨機(jī)性，在初始化粒子的位置時(shí)采用混沌賦值的方式產(chǎn)生一系列初始解，再根據(jù)每個(gè)粒子個(gè)體的適應(yīng)值來自適應(yīng)地調(diào)整其慣性權(quán)重，對(duì)陷入局部最優(yōu)的粒子群個(gè)體位置進(jìn)行混沌更新，幫助其跳出局部最優(yōu)。通過在CloudSim平臺(tái)進(jìn)行仿真對(duì)比實(shí)驗(yàn)，表明該改進(jìn)算法有效地縮小了總?cè)蝿?wù)的完成時(shí)間，具有較好的尋優(yōu)能力和實(shí)時(shí)性，是一種有效的云計(jì)算任務(wù)調(diào)度算法。

云計(jì)算；任務(wù)調(diào)度；粒子群優(yōu)化算法；混沌

0 引 言

云計(jì)算[1-2]作為一種新型的計(jì)算服務(wù)商業(yè)模式，集成了網(wǎng)格計(jì)算、分布式計(jì)算和并行計(jì)算等技術(shù)，自提出以來就成為一個(gè)熱點(diǎn)研究方向。云計(jì)算提供了基礎(chǔ)設(shè)施、平臺(tái)和軟件的服務(wù)，可以將用戶提交的任務(wù)按照適當(dāng)?shù)乃惴ǚ峙涞教摂M計(jì)算資源上進(jìn)行合理調(diào)度，之后再將服務(wù)器的計(jì)算分析處理結(jié)果發(fā)送給用戶。

由于云計(jì)算中存在諸多形態(tài)不同的云端，且面對(duì)的計(jì)算資源種類眾多、提供服務(wù)效率不一、計(jì)算任務(wù)數(shù)量巨大，因此在“云”中如何將眾多任務(wù)進(jìn)行合理調(diào)度以滿足用戶對(duì)服務(wù)質(zhì)量的要求，并且更有效利用云計(jì)算系統(tǒng)中的資源，一直是一個(gè)熱點(diǎn)問題[2-3]。云計(jì)算任務(wù)調(diào)度是云計(jì)算研究的重點(diǎn)，它主要解決的問題是如何以最優(yōu)的調(diào)度策略實(shí)現(xiàn)用戶任務(wù)的有效調(diào)度。云計(jì)算任務(wù)調(diào)度問題實(shí)際上是一個(gè)NP難題[4]。針對(duì)該問題，國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究，提出了眾多云計(jì)算任務(wù)調(diào)度算法。如最小最小(Min-Min)[5]、Sufferage算法[6]、蟻群算法[7]、遺傳算法[8]、粒子群優(yōu)化算法[9]等。

PSO算法[10]是一種基于群體的智能優(yōu)化算法，從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解。相比較于遺傳算法或蟻群算法等全局優(yōu)化算法，PSO算法具有設(shè)置參數(shù)少、易實(shí)現(xiàn)、精度高、收斂快等優(yōu)點(diǎn)，在求解云計(jì)算任務(wù)調(diào)度問題上具有天然的優(yōu)勢(shì)。但是同其他一些智能優(yōu)化算法一樣，PSO算法也存在著容易出現(xiàn)早熟收斂、陷入局部最優(yōu)等缺點(diǎn)。

為了克服傳統(tǒng)PSO算法易陷入局部最優(yōu)解的缺陷，文中通過對(duì)如何充分利用“云”中的資源使其中的任務(wù)進(jìn)行高效合理的調(diào)度進(jìn)行了研究，利用云模型的隨機(jī)性和穩(wěn)定性的特點(diǎn)，在傳統(tǒng)PSO優(yōu)化算法的基礎(chǔ)上提出了一種基于云模型的自適應(yīng)CPSO任務(wù)調(diào)度算法，采用混沌變量來優(yōu)化粒子的位置和速度，并對(duì)每次混沌搜索的范圍采用自適應(yīng)調(diào)整方法，從當(dāng)前群體中擇優(yōu)選擇部分粒子進(jìn)行混沌優(yōu)化。

1 云計(jì)算中的任務(wù)調(diào)度模型

目前，大部分云計(jì)算平臺(tái)都采用Google提出的Map/Reduce分布式計(jì)算編程模型[11]。這是一種用于大規(guī)模數(shù)據(jù)集的并行編程架構(gòu)，分為Map和Reduce兩個(gè)階段，實(shí)現(xiàn)將一個(gè)較大的任務(wù)切分為多個(gè)較小的子任務(wù)，交給n臺(tái)計(jì)算機(jī)并行執(zhí)行，再并行遞歸并返回結(jié)果，最后得到運(yùn)算結(jié)果。

云計(jì)算環(huán)境下的任務(wù)調(diào)度是以任務(wù)為出發(fā)點(diǎn)，根據(jù)一定的任務(wù)調(diào)度策略，將相互獨(dú)立的多個(gè)任務(wù)以最合理的方案分配到可用的計(jì)算資源上，使得任務(wù)的總執(zhí)行時(shí)間跨度最短同時(shí)能夠充分利用現(xiàn)有資源。因此云計(jì)算任務(wù)調(diào)度算法的優(yōu)劣直接影響任務(wù)的執(zhí)行效率，從而影響整個(gè)云的性能和用戶的滿意度。根據(jù)云計(jì)算任務(wù)調(diào)度的特點(diǎn)，定義如下的數(shù)學(xué)參數(shù)模型：G=(T,R,F,P)。

其中，T={T1,T2,…,Tn}表示任務(wù)模型，包括n個(gè)相互獨(dú)立的任務(wù)；R={R1,R2,…,Rm}表示由m個(gè)可用于執(zhí)行任務(wù)的高性能計(jì)算資源組成的計(jì)算資源模型，其中m

定義了以上的任務(wù)調(diào)度模型，使用n×m的ETC矩陣來描述各個(gè)計(jì)算資源上任務(wù)隊(duì)列運(yùn)行完成所需要的時(shí)間。其中，ETC(i,j)表示第j個(gè)計(jì)算資源上執(zhí)行第i個(gè)子任務(wù)所需要的時(shí)間。

假設(shè)第j個(gè)資源上分配的的子任務(wù)的個(gè)數(shù)為M，那么資源j上的所有子任務(wù)執(zhí)行完成所需要的時(shí)間應(yīng)該為：

(1)

可以得到完成所有任務(wù)的總時(shí)間為：

(2)

則任務(wù)的平均完成時(shí)間為：

Tavg=SumTime/n

(3)

2 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化算法[10]是Kennedy和Eberhart在1995年受飛鳥集群活動(dòng)的規(guī)律性啟發(fā)提出的一種全局優(yōu)化進(jìn)化算法。該算法通過目標(biāo)函數(shù)適應(yīng)度的值來分配相關(guān)資源。由于該算法簡(jiǎn)單易實(shí)現(xiàn)且沒有太多參數(shù)需要調(diào)整，因而在求解云計(jì)算任務(wù)調(diào)度這個(gè)大規(guī)模、實(shí)時(shí)問題時(shí)能得到較好的效果。

PSO同遺傳算法類似，是一種基于迭代的優(yōu)化算法。傳統(tǒng)PSO算法中，每一個(gè)粒子代表一個(gè)可行解，且每一個(gè)粒子均有一個(gè)初始位置和速度，粒子的優(yōu)劣程度取決于待優(yōu)化問題目標(biāo)函數(shù)確定的適應(yīng)度值。系統(tǒng)初始化為一組隨機(jī)解，通過迭代在解空間追隨最優(yōu)的粒子進(jìn)行搜索，從而找到最優(yōu)值。在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”來更新自己，其中一個(gè)就是粒子本身所找到的最優(yōu)解，即個(gè)體極值pbest，另一個(gè)則是整個(gè)種群目前找到的最優(yōu)解，即全局極值gbest。在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)式(4)和式(5)來更新自己的速度和位置：

v(t+1)=wv(t)+c1r1(pbest(t)-x(t))+ c2r2(gbest(t)-x(t))

(4)

x(t+1)=x(t)+v(t+1)

(5)

其中，v為粒子的速度；x為粒子的位置；c1和c2為加速因子；r1和r2為[0,1]的隨機(jī)數(shù)；w為慣性權(quán)重。

3 自適應(yīng)CPSO算法

3.1 CPSO算法

混沌是存在于非線性系統(tǒng)中的一種無規(guī)則的運(yùn)動(dòng)現(xiàn)象，混沌優(yōu)化算法的基本思想是把混沌變量從混沌空間映射到解空間。由于混沌變量具有遍歷性、隨機(jī)性和規(guī)律性，利用混沌變量進(jìn)行優(yōu)化搜索能加速算法搜索速度、避免算法陷入局部最優(yōu)，從而提高算法的搜索性能。

標(biāo)準(zhǔn)PSO算法是一種簡(jiǎn)潔高效的智能優(yōu)化算法，但是由于算法隨機(jī)性很大，仍有很多不完善的地方，例如容易出現(xiàn)收斂過早、陷入局部最優(yōu)等問題。為彌補(bǔ)該缺陷，文中將混沌思想引入粒子群優(yōu)化算法，提出一種混沌粒子群優(yōu)化算法。

在算法初始化時(shí)利用混沌賦值的方式對(duì)粒子群進(jìn)行初始化，同時(shí)在算法搜索過程中將混沌范圍擴(kuò)大到優(yōu)化變量的取值范圍中，充分利用PSO算法收斂速度快以及混沌運(yùn)動(dòng)遍歷性、隨機(jī)性和規(guī)律性的優(yōu)點(diǎn)，對(duì)種群中處于最差位置的粒子個(gè)體進(jìn)行混沌優(yōu)化,從而提高傳統(tǒng)粒子群算法的收斂速度和尋優(yōu)效率。不同的混沌映射方程對(duì)混沌尋優(yōu)過程有很大的影響。文獻(xiàn)[12]通過比較指出，相比Logistic映射，Tent映射具有更快的迭代速度和更高的遍歷均勻性，因此文中采用Tent映射作為混沌優(yōu)化模型，其表達(dá)式為:

(6)

文中提出的基于Tent映射的混沌粒子群(CPSO)算法的基本思想是：當(dāng)PSO算法出現(xiàn)早熟收斂時(shí),引入混沌Tent映射,對(duì)全局最優(yōu)粒子進(jìn)行混沌搜索，通過改變粒子個(gè)體位置的更新策略來引導(dǎo)粒子群進(jìn)行一定次數(shù)的混沌更新,使其快速跳出局部最優(yōu)。當(dāng)算法出現(xiàn)早熟收斂時(shí)，使用式(7)對(duì)位置變量進(jìn)行更新：

x(t+1)=xmin+zk+1×(xmax-xmin)

(7)

3.2 自適應(yīng)慣性權(quán)重

PSO算法的性能優(yōu)劣與參數(shù)慣性權(quán)重w的取值有著密切的關(guān)系。w取值越小越有利于局部搜索，并且能得到較為精確的解，但搜索時(shí)不易跳出局部極值點(diǎn)；相反，w取值越大越有利于全局搜索，但不易得到精確的解。對(duì)此，為了加強(qiáng)算法在全局和局部搜索之間的平衡，文中結(jié)合CPSO優(yōu)化算法，提出一種基于粒子個(gè)體適應(yīng)值的自適應(yīng)慣性權(quán)重：

(8)

其中，wmax為慣性權(quán)重的最大值；wmin為慣性權(quán)重的最小值；t為當(dāng)前的迭代次數(shù)；G為最大迭代次數(shù)。

可見，通過式(8)來計(jì)算每個(gè)粒子的慣性權(quán)重系數(shù)，對(duì)每次混沌搜索的范圍采用自適應(yīng)調(diào)整方法。在算法初期w取較大的值，使算法具有較強(qiáng)的全局搜索能力；而算法后期w使用較小的值，從而提高算法的局部搜索能力。

3.3 適應(yīng)度函數(shù)的選取

在PSO算法中，適應(yīng)度函數(shù)的選取是相當(dāng)重要的。適應(yīng)度函數(shù)直接影響算法的收斂速度與最優(yōu)解的查找，適應(yīng)度值越大，表示相對(duì)應(yīng)粒子質(zhì)量越好。云計(jì)算任務(wù)調(diào)度目標(biāo)是總?cè)蝿?wù)完成時(shí)間最短，文中根據(jù)任務(wù)總完成時(shí)間來定義適應(yīng)度函數(shù)：

(9)

文中采用類似遺傳算法的選擇思想，優(yōu)先選擇適應(yīng)度高的粒子。由式(9)可知，任務(wù)總完成時(shí)間越小的粒子，適應(yīng)度值越大，則越容易被選擇。

3.4 算法流程

文中將混沌優(yōu)化思想用于粒子群優(yōu)化算法，并結(jié)合動(dòng)態(tài)慣性權(quán)值因子，提出一種自適應(yīng)的混沌粒子群優(yōu)化算法。以粒子變量為基礎(chǔ)，在初始化粒子群中粒子的位置時(shí)采用混沌賦值的方式，對(duì)粒子產(chǎn)生混沌擾動(dòng)形成混沌序列，以此替換原有粒子，提高粒子性能。算法在初始化粒子位置時(shí)采用混沌賦值的方式產(chǎn)生一系列初始解，從中擇優(yōu)選出初始群體，提高粒子群的多樣性和粒子搜索的遍歷性。其次在粒子群優(yōu)化過程中，根據(jù)每個(gè)粒子個(gè)體的適應(yīng)值來自適應(yīng)地調(diào)整其慣性權(quán)重，對(duì)粒子群個(gè)體位置進(jìn)行混沌更新，幫助其跳出局部極值區(qū)間，提高了算法的收斂速度和精度。

具體實(shí)現(xiàn)步驟如下：

(1)采用混沌理論產(chǎn)生初始群體。利用混沌優(yōu)化的隨機(jī)性、遍歷性特點(diǎn)對(duì)粒子群算法進(jìn)行混沌初始化，從中擇優(yōu)選擇粒子作為初始粒子，在保證隨機(jī)性的前提下使初始粒子盡可能分布均勻。

(2)混沌初始化各粒子的位置和速度，根據(jù)式(9)計(jì)算粒子群的適應(yīng)度值。

(3)根據(jù)式(8)自適應(yīng)地調(diào)整粒子的慣性權(quán)重。

(4)對(duì)于每個(gè)粒子的適應(yīng)度值與原來的個(gè)體極值pbest和全局極值gbest進(jìn)行比較，如果粒子的適應(yīng)度值優(yōu)于pbest，那么將其作為當(dāng)前的個(gè)體極值；如果粒子的適應(yīng)度值優(yōu)于gbest，則將其作為當(dāng)前的全局極值點(diǎn)。

(5)對(duì)每個(gè)粒子，按式(4)更新速度,按式(5)和式(7)更新位置。

(8)判斷是否滿足停止條件，如果滿足則停止搜索，輸出全局最優(yōu)位置，否則返回步驟(4)。

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

為了檢測(cè)文中算法的有效性，采用墨爾本大學(xué)開發(fā)的云仿真平臺(tái)CloudSim[13]來模擬一個(gè)云計(jì)算的局部環(huán)境，在相同實(shí)驗(yàn)條件下，對(duì)傳統(tǒng)PSO算法和文中算法進(jìn)行了云計(jì)算環(huán)境下的仿真對(duì)比實(shí)驗(yàn)，分別從收斂性和任務(wù)完成時(shí)間兩個(gè)方面對(duì)算法性能進(jìn)行對(duì)比。

(1)算法的收斂性對(duì)比。

在云計(jì)算資源數(shù)為10,調(diào)度任務(wù)數(shù)為100的環(huán)境下,基本參數(shù)設(shè)置一致，對(duì)文中算法和基本PSO算法調(diào)度方案的收斂性進(jìn)行仿真實(shí)驗(yàn)，收斂曲線如圖1所示。

由圖1可知,相較于基本PSO算法而言，文中方法的收斂速度明顯占據(jù)優(yōu)勢(shì)，并且比基本PSO算法優(yōu)先達(dá)到最優(yōu)方案。這是因?yàn)樵诘^程中，由于文中方法引入混沌機(jī)制對(duì)基本的粒子群進(jìn)行混沌擾動(dòng)，避免粒子陷入局部最優(yōu)，并且在迭代中采用了動(dòng)態(tài)自適應(yīng)的慣性權(quán)重機(jī)制，提高了算法的尋優(yōu)能力。

圖1 算法改進(jìn)前后的收斂曲線圖

(2)總?cè)蝿?wù)完成時(shí)間對(duì)比。

考慮到云環(huán)境任務(wù)具有動(dòng)態(tài)性的特點(diǎn)，分別模擬10個(gè)計(jì)算資源、50個(gè)子任務(wù)以及10個(gè)計(jì)算資源、500個(gè)子任務(wù)兩種實(shí)驗(yàn)環(huán)境，對(duì)基本PSO算法和文中算法的性能進(jìn)行了對(duì)比實(shí)驗(yàn)。兩種算法分別運(yùn)行100次，取100次實(shí)驗(yàn)的平均結(jié)果作為實(shí)驗(yàn)的最終結(jié)果。根據(jù)文獻(xiàn)[14]的參數(shù)調(diào)整原則，設(shè)置兩種算法的基本參數(shù)，如表1和表2所示。

表1 文中算法主要參數(shù)設(shè)置

表2 PSO算法主要參數(shù)設(shè)置

在參數(shù)設(shè)置基本一樣的情況下，分別進(jìn)行200次迭代，兩種調(diào)度算法的對(duì)比結(jié)果如圖2和圖3所示。

圖2 任務(wù)較少時(shí)，兩種算法總?cè)蝿?wù)完成時(shí)間比較

從圖2和圖3可以看出，基本PSO算法和文中算法在迭代初期任務(wù)的總完成時(shí)間相差不大，隨著迭代次數(shù)的增大，兩種算法的任務(wù)總完成時(shí)間都在不斷減小。相比而言，由于基本PSO算法只重視總?cè)蝿?wù)的完成時(shí)間，在迭代初期收斂速度快，但在運(yùn)行過程中由于無法有效跳出局部最優(yōu)而出現(xiàn)了早熟收斂，過早地收斂到局部最優(yōu)的任務(wù)調(diào)度結(jié)果。因此采用基本PSO算法的調(diào)度優(yōu)化效果，迭代初期比較明顯，但是隨著迭代次數(shù)的增加，探索能力不足，在進(jìn)化前期迅速地探索到局部最優(yōu)解后就沒能再跳出。而文中算法將混沌機(jī)制引入基本PSO算法，在迭代過程中不斷優(yōu)化調(diào)度結(jié)果。對(duì)比圖2和圖3可以看出，當(dāng)任務(wù)數(shù)增加到100時(shí)，使用文中算法得到的總?cè)蝿?wù)完成時(shí)間明顯優(yōu)于使用基本PSO算法調(diào)度的總?cè)蝿?wù)完成時(shí)間，且收斂速度也優(yōu)于傳統(tǒng)的PSO調(diào)度算法。

圖3 任務(wù)較多時(shí)，兩種算法總?cè)蝿?wù)完成時(shí)間比較

(3)任務(wù)平均完成時(shí)間對(duì)比。

為了更好地驗(yàn)證和評(píng)價(jià)文中算法的性能，將其與改進(jìn)遺傳算法(GA)[7]、改進(jìn)蟻群算法(ACO)[15]進(jìn)行對(duì)比試驗(yàn)。設(shè)置計(jì)算資源節(jié)點(diǎn)數(shù)為10，待調(diào)度的子任務(wù)數(shù)為100，在相同的實(shí)驗(yàn)環(huán)境下，分別測(cè)試三種算法迭代100次后得到的任務(wù)平均完成時(shí)間，對(duì)比結(jié)果如圖4所示。

圖4 任務(wù)平均完成時(shí)間比較

從圖中可以看出，文中的CPSO算法結(jié)合了PSO算法的快速收斂能力以及混沌優(yōu)化算法的遍歷性和隨機(jī)性特點(diǎn)，能夠有效降低算法陷入局部極小的概率，在迭代過程體現(xiàn)了均衡的探索能力和開發(fā)能力，在三種調(diào)度算法中表現(xiàn)最優(yōu)。ACO算法在整個(gè)迭代過程中，迭代初期優(yōu)化效果比較明顯，但是在迭代后期優(yōu)化效果變?nèi)?，任?wù)平均完成時(shí)間大于遺傳算法和文中算法，調(diào)度效果相對(duì)較差。GA算法在整個(gè)迭代過程中優(yōu)化能力比較均衡，但是收斂速度相對(duì)較慢。因此，無論是任務(wù)的平均完成時(shí)間還是算法的收斂速度，文中提出的CPSO算法都優(yōu)于ACO算法和GA算法。

5 結(jié)束語

針對(duì)當(dāng)前云計(jì)算任務(wù)調(diào)度算法存在收斂速度慢、資源利用率不足等缺陷，利用PSO算法控制參數(shù)少、易于實(shí)現(xiàn)、計(jì)算簡(jiǎn)單等優(yōu)點(diǎn)，文中提出一種云計(jì)算環(huán)境下基于混沌粒子群優(yōu)化的任務(wù)調(diào)度算法。在PSO算法中引入混沌搜索，采用混沌賦值的方式初始化種群，并使用自適應(yīng)的慣性權(quán)值控制粒子的搜索范圍，使粒子自適應(yīng)地進(jìn)行搜索。通過對(duì)比實(shí)驗(yàn)可知，文中提出的基于Tent映射的自適應(yīng)CPSO算法很好地解決了標(biāo)準(zhǔn)PSO算法容易“早熟”的問題，提高了任務(wù)和資源之間的匹配度，并且有效縮短了總?cè)蝿?wù)的完成時(shí)間，具有較好的尋優(yōu)能力，能夠有效地解決云計(jì)算環(huán)境下的任務(wù)調(diào)度問題。

[1]FosterI,ZhaoYong,RaicuI,etal.Cloudcomputingandgridcomputing360-degreecompared[C]//Procofgridcomputingenvironmentsworkshop.WashingtonD.C.,USA:IEEEComputerSociety,2008:1-10.

[2]ArmbrustM,FoxA,GriffithR,etal.Abovetheclouds:aberkeleyviewofcloudcomputing[EB/OL].2009-11-21.http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.

[3] 鄒永貴，萬建斌．云計(jì)算環(huán)境下的資源管理研究[J]．?dāng)?shù)字通信，2012(4):39-43．

[4]ArfeenMA，PawlikowskiK，WilligA．Aframeworkforresourceallocationstrategiesincloudcomputingenvironment[C]//ProcofIEEE35thannualcomputersoftwareandapplicationsconferenceworkshops.[s.l.]:IEEE,2011:261-266．

[5] 羅 紅，慕德俊，鄧智群，等.網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2005,22(5):16-19.

[6]BuyyaR.Economic-baseddistributedresourcemanagementandschedulingforgridcomputing[D].Melbourne,Australia:MonashUniversity,2002.

[7] 王 芳，李美安,段衛(wèi)軍.基于動(dòng)態(tài)自適應(yīng)蟻群算法的云計(jì)算任務(wù)調(diào)度[J].計(jì)算機(jī)應(yīng)用，2013，33(11):3160-3162.

[8] 林劍檸,吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2004，41(12):2195-2199.

[9] 季一木，王汝傳.基于粒子群的網(wǎng)格任務(wù)調(diào)度算法研究[J].通信學(xué)報(bào)，2007，28(10)：60-66.

[10]KennedyJ,EberhartR.Particleswarmoptimization[C]//ProcofIEEEinternationalconferenceonneuralnetworks.Piscataway,NJ:IEEE,1995:1942-1948.

[11]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[C]//Proceedingsofthe6thsymposiumonoperatingsystemdesignandimplementation.NewYork:ACM,2004:137-150.

[12] 單 梁，強(qiáng) 浩，李 軍,等．基于Tent映射的混沌優(yōu)化算法[J]．控制與決策，2005，20(2):179-182．

[13]CalheirosRN,RanjanR,BeloglazovA,etal.CloudSim:atoolkitformodelingandsimulationofcloudcomputingenvironmentsandevaluationofresourceprovisioningalgorithms[J].Software:PracticeandExperience,2011,41(1):23-50.

[14] 段海濱,張祥銀,徐春芳.仿生智能計(jì)算[M].北京：科學(xué)出版社,2011:63-85.

[15] 李建鋒,彭 艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31(1):184-186.

Application of Self-adaptive Chaos Particle Swarm Optimization in Task Scheduling for Cloud Computing

ZHANG Xiao-li

(School of Computer,Xi’an Aerotechnical University,Xi’an 710077,China)

Tasks scheduling is an important issue to be resolved in cloud computing research.In order to overcome the defects of traditional PSO easy to fall into local optimum,in view of procedure model framework of cloud computing,the chaos optimization search technique is applied to the particle swarm optimization，and an adaptive chaotic particle swarm algorithm of task scheduling based on Tent mapping is presented.It combines the fast convergence of PSO and the ergodic property of chaotic motion,with chaotic assignment way in initializing particle position,and then adaptively adjusts its inertia weight according to the fitness value of each individual particle,updating chaos location for particle swarm individual to help themselves escape from local optima.Through simulation experiment on the CloudSim platform,the results show that the ACPOS,with a good real-time performance and optimization ability,significantly reduces the completion time of the task,which is an efficient task scheduling algorithm.

cloud computing;task scheduling;Particle Swarm Optimization (PSO);chaos

2015-10-28

2016-01-28

時(shí)間：2016-06-22

西安市科技計(jì)劃項(xiàng)目資助(CXY1518(1))

張曉麗(1980-),女,講師，碩士,研究方向?yàn)樵朴?jì)算、分布式計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.032.html

TP393

A

1673-629X(2016)08-0161-05

10.3969/j.issn.1673-629X.2016.08.034