一種改進的PSO網(wǎng)格調(diào)度算法

楊長興，胡 金

（中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙410083）

在網(wǎng)格計算中，任務(wù)管理、任務(wù)調(diào)度和資源管理是網(wǎng)格的3個基本功能。任務(wù)調(diào)度是網(wǎng)格系統(tǒng)的一個關(guān)鍵問題，關(guān)系到網(wǎng)格能否高效利用資源、快速完成任務(wù)以及實現(xiàn)系統(tǒng)負(fù)載均衡。同時它也是一個NP完全問題[1]，即得到一個最優(yōu)的調(diào)度方案或是在有限的時間里找出最優(yōu)(任務(wù),資源)的匹配方案是不可能的。目前多采用啟發(fā)式算法解決此類問題。

近年來，很多學(xué)者將啟發(fā)式算法應(yīng)用于任務(wù)調(diào)度中，并取得了較好的研究成果[2-5]。其中，GA算法可能找到最優(yōu)解，但選擇過程存在隨機性，不能確保得到最優(yōu)解，同時開銷大，運行時間長；AA算法雖然有正反饋機制能避免早熟現(xiàn)象，但容易收斂于局部最優(yōu)，而且算法復(fù)雜，搜索時間長；SA算法能以一定的概率接受差的解而可能跳出局部極小，是一種全局最優(yōu)算法，但是搜索時間比較長；PSO粒子群優(yōu)化算法[6]搜索速度快、操作簡單、效率高，但是易陷入局部極值，搜索精度不高。

針對PSO易早熟、求解質(zhì)量不高的問題，為實現(xiàn)最小化任務(wù)完成總時間(makespan)，本文提出一種基于獨立任務(wù)調(diào)度的改進PSO網(wǎng)格調(diào)度算法MCPSO(An improved PSO of grid scheduling algorithm under the meta task)。該算法的主要思想是：首先采用混沌[7]序列初始化粒子的位置，并在產(chǎn)生的大量粒子中擇優(yōu)選出初始種群；然后在粒子更新時引入混沌搜索，隨機產(chǎn)生若干混沌序列并把最優(yōu)混沌序列得到的位置和當(dāng)前粒子最優(yōu)位置比較，如果優(yōu)于當(dāng)前粒子，則更新當(dāng)前粒子的最優(yōu)位置，引導(dǎo)當(dāng)前粒子跳出局部最優(yōu)點，快速尋找最優(yōu)解。實驗表明，該算法改善了PSO算法易陷入局部最優(yōu)問題，同時兼顧更好的makespan和負(fù)載均衡，有效提高網(wǎng)格的性能。

1 問題定義

圖1所示是一個簡單的任務(wù)調(diào)度流程圖，其中MDS(Monitoring and Discovering Service)是資源監(jiān)控與發(fā)現(xiàn)服務(wù)，用于收集和發(fā)布系統(tǒng)狀態(tài)信息。

如圖1所示，首先任務(wù)劃分模塊將應(yīng)用程序劃分為若干個子任務(wù)，然后調(diào)度模塊從網(wǎng)格資源中的信息采集模塊MDS收集必要信息，最后按一定的策略對任務(wù)進行分發(fā)。

通常在網(wǎng)格環(huán)境下主要考慮一組相互獨立、任務(wù)之間沒有數(shù)據(jù)和通信依賴的獨立任務(wù)(metatask)。目前多數(shù)研究是基于此展開的。本文將主要研究獨立任務(wù)調(diào)度。

現(xiàn)假定虛擬組織VO中用戶提交了若干個任務(wù)，這些任務(wù)經(jīng)由圖1中的劃分模塊分成n個獨立子任務(wù)t1、t2、…、tn組成子任務(wù)集合 T，網(wǎng)格系統(tǒng)中有 m個節(jié)點(網(wǎng)格資源)r1、r2、…、rm構(gòu)成資源集合R。任一任務(wù) ti可以在任一節(jié)點rj上執(zhí)行，rj在同一時刻只能處理一個任務(wù)，而 ti不能同時在兩個節(jié)點上執(zhí)行，ti一旦開始，rj被獨占，直到ti完成后才能執(zhí)行其他任務(wù)。用一個n維向量(w1，w2，…，wn)表示任務(wù)的預(yù)計完成時間，其中 wi為任務(wù)i的預(yù)計完成時間。

定義1(任務(wù)映射集)n個任務(wù)映射到m個節(jié)點的映射方案T→R集合即任務(wù)映射集MAP。集合MAP={map1，map2，…，mapn}，其中 mapi表示第 i個任務(wù)在映射到的節(jié)點mapi上執(zhí)行。

定義2(節(jié)點工作時間)節(jié)點工作時間RCj是指節(jié)點j處理完所有分配給它的任務(wù)所花費的時間。如式(1)所示：

定義 3(時間跨度)時間跨度即 makespan，是指任務(wù)集合T中第一個任務(wù)開始執(zhí)行到最后一個任務(wù)完成的時間。在某調(diào)度算法下的makespan也稱為該算法的調(diào)度長度，makespan越小，調(diào)度策略越好。最優(yōu)跨度ω為網(wǎng)格當(dāng)前實際跨度的最好值，最優(yōu)調(diào)度的下界是將任務(wù)平均分到各個計算資源上，此時得到的ω值為理論最優(yōu)跨度ωmin即均衡負(fù)載。

定義4(負(fù)載均衡度)計算資源上的任務(wù)稱為負(fù)載。當(dāng)計算資源上的負(fù)載超過ωmin時該計算資源為重載資源，而當(dāng)負(fù)載低于ωmin時為輕載資源。任務(wù)調(diào)度的目標(biāo)是最小化資源上的負(fù)載，使得各個資源負(fù)載基本相同，這個過程也稱為負(fù)載均衡。負(fù)載均衡度β按式(5)計算，表示計算資源負(fù)載偏離均衡負(fù)載ωmin的程度，其數(shù)值越小，網(wǎng)格系統(tǒng)就越均衡。

獨立任務(wù)調(diào)度的數(shù)學(xué)模型為：

2 改進PSO的網(wǎng)格調(diào)度算法

2.1 標(biāo)準(zhǔn)PSO算法

粒子群優(yōu)化算法PSO(Particle Swarm Optimization)是由Eberhart和Kennedy于1995年發(fā)明的一種全局迭代優(yōu)化算法。PSO先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子代表著優(yōu)化問題的一個潛在可行解。每個粒子將在解空間中“飛行”，并由一個速度決定其方向和距離。通常粒子將追隨當(dāng)前的最優(yōu)粒子而動，并經(jīng)過多次迭代得到最優(yōu)解。在每一次迭代時，粒子將跟蹤兩個極值，一為粒子本身迄今找到的最優(yōu)解pbest，另一個為全種群迄今找到的最優(yōu)解gbest。

每一代粒子速度和位置更新公式如下：

式中，vij(t)、vij(t+1)表示第 i個粒子在第 j維方向上的當(dāng)前速度和更新后的速度；xij(t)、xij(t+1)表示第i個粒子在第j維方向上的當(dāng)前位置和更新后的位置；w為慣性因子，作用是控制和提高優(yōu)化效率；c1、c2為學(xué)習(xí)因子，通常在 0～2 間取值；r1～U(0，1)，r2～U(0，1)為兩個相互獨立的隨機函數(shù)；pij(t)表示第i個粒子經(jīng)歷過的最好位置矢量即個體最好位置在第j維方向上的位置；pgj(t)表示群體中所有粒子經(jīng)歷過的最好位置矢量即全局最好位置在第j維方向上的位置。

2.2 混沌優(yōu)化

由確定的運動方程得到的具有隨機性的運動狀態(tài)稱為混沌運動?；煦缡亲匀唤缰幸环N常見現(xiàn)象，其變化過程看似雜亂無章，但不是完全混亂，而是有一定的規(guī)律性。將方程中呈混沌狀態(tài)的變量稱為混沌變量，混沌變量對初值十分敏感?；煦缱兞烤哂袕娜我恻c(除不動點)出發(fā)，按確定公式遍歷所有狀態(tài)的特點，即確定性、遍歷性，表現(xiàn)形式如同隨機變量。一個典型的混沌系統(tǒng)是Logistic方程，其表達式為：式中，μ 為控制參數(shù)，0≤μ≤4；un∈[0，1]。

混沌搜索的主要思想是通過混沌系統(tǒng)如式(7)產(chǎn)生混沌序列，然后通過載波的方式

將其映射到優(yōu)化空間中，也就是將混沌變量的值域“放大”到優(yōu)化變量的取值范圍內(nèi)。

2.3 改進PSO的網(wǎng)格調(diào)度算法(MCPSO)

PSO具有很強的全局搜索能力，但不能保證全局收斂。當(dāng)粒子自身信息和個體極值信息占優(yōu)時，往往停滯于局部最優(yōu)解，且隨機初始化的種群質(zhì)量不高，甚至距離最優(yōu)解位置較遠(yuǎn)。而混沌具有良好的遍歷性、隨機性以及一定的突跳能力，易跳出局部極值點，最終可能得到最優(yōu)解。

因而可以利用混沌的遍歷性，在初始化時產(chǎn)生大量粒子，從中擇優(yōu)選出初始種群。同時在粒子位置和速度更新時，引入混沌搜索，并把最優(yōu)混沌序列得到的位置與當(dāng)前粒子最優(yōu)位置相比較，如果優(yōu)于當(dāng)前粒子則進行替換。這樣可以有效減少算法收斂于局部極值的現(xiàn)象。算法流程如下：

(1)給定種群大小 POPSIZE、最大迭代次數(shù)、慣性權(quán)值 w、學(xué)習(xí)因子 c1、c2及控制參數(shù) μ等。

(2)混沌初始化：

①隨機產(chǎn)生一個n維每個分量數(shù)值在[0，1]上的向量，z1=(z11，z12，…，z1n)，n 為種群的大小，根據(jù)式(8)，得 n個混沌序列 z1，z2，…，zn。

②利用式(9)將 zi，1≤i≤n分量載波到相應(yīng)的變量取值區(qū)間，選出較優(yōu)的POPSIZE個粒子作為初始種群。

(3)隨機初始化各個粒子的初始速度并計算其適應(yīng)值，設(shè)置各個粒子的初始極值并計算種群極值。

(4)根據(jù)式(6)、式(7)更新粒子位置和速度。

(5)啟動混沌搜索。隨機產(chǎn)生d個[0，1]上的隨機數(shù)，根據(jù)式(8)得到d個混沌序列，并把產(chǎn)生的混沌序列依次載波放大到對應(yīng)變量的取值范圍上，從中選出最優(yōu)位置。

(7)更新個體極值和群體極值。

(8)跳至步驟(4)直到算法到達最大迭代次數(shù)。

(9)輸出全局最優(yōu)值和全局最優(yōu)粒子、最優(yōu)跨度ω、負(fù)載平衡度β。

2.4 問題編碼

對于n個任務(wù)m個資源的調(diào)度，粒子的位置和速度均用n維向量表示，維數(shù)和任務(wù)數(shù)一致。如位置向量(x1，x2，…，xm)中第 i維分量 xi表示任務(wù) ti的權(quán)值，是[0，m)之間的一個隨機數(shù)。當(dāng)n=10，m=5時，各個節(jié)點對應(yīng)的權(quán)值范圍如表1。

表1 權(quán)值與節(jié)點序號對應(yīng)表

若某粒子的位置矢量表示如下：

上述粒子即為任務(wù)的一個調(diào)度方案，由表1可得任務(wù)與節(jié)點的映射關(guān)系如表2所示。

表2 基于節(jié)點編碼的任務(wù)分配方案

3 實驗與性能分析

以GridSim工具包為基礎(chǔ)構(gòu)建網(wǎng)格仿真環(huán)境，將本文提出的MCPSO算法與基于獨立任務(wù)的基本粒子群優(yōu)化算法MPSO算法進行對比分析。

PSO算法參數(shù)設(shè)置如下：種群大小POPSIZE=10，學(xué)習(xí)因子c1=c2=2.05，慣性因子ω=0.729，算法最大迭代次數(shù)為 1 000，混沌控制參數(shù) μ=4。測試運行 50次，取 50次實驗的平均結(jié)果作為實驗結(jié)果。

實驗中有5個節(jié)點，10個任務(wù)，各個任務(wù)的預(yù)計完成時間{10,42,34,27,56,79,77,62,81,51}，單位為 s。

實驗從調(diào)度方案的求解質(zhì)量、makespan、負(fù)載平衡度3個方面比較兩種算法的性能。

求解質(zhì)量如表3所示。

表3 實驗結(jié)果比較

比較可知，本文提出的MCPSO算法比MPSO有更好的性能，平均跨度值與最好解的偏差小，最好解的次數(shù)明顯多于MPSO算法，最差解也明顯優(yōu)于MPSO，MCPSO算法的求解質(zhì)量更好。

為了觀察算法的收斂特性，給出了兩種算法1 000次迭代的makespan變化曲線，如圖2所示。從圖2可以看出，MCPSO算法收斂速度優(yōu)于MPSO算法的情況，并能得到更好的解，而且改進的PSO算法初始解明顯更優(yōu)。

由圖3可知，兩種算法的負(fù)載均衡度隨著迭代次數(shù)的增加而減少，即負(fù)載均衡性能都有提升。而MCPSO算法的負(fù)載均衡性能大大好于MPSO算法。

通過實驗可以看出，基本粒子群能快速地找到較優(yōu)解，但是后期逐漸收斂于該解，并處于“停滯”狀態(tài)，很難得到更優(yōu)解。引入混沌機制的MCPSO算法，擁有基本粒子群算法快速收斂的特性，同時在未得到最優(yōu)解的情況下，逐漸向最優(yōu)解靠近，不斷得到更優(yōu)解甚至最優(yōu)解。

為改善網(wǎng)格調(diào)度性能，本文提出了基于獨立任務(wù)的改進PSO任務(wù)調(diào)度算法。該算法以時間跨度makespan為數(shù)學(xué)模型，結(jié)合粒子群算法和混沌優(yōu)化原理，首先通過混沌初始化得到較優(yōu)的初始種群，有效減少粒子飛向較優(yōu)點的迭代次數(shù)；在更新粒子位置和速度時，對粒子的最優(yōu)位置進行混沌搜索，試圖找出更優(yōu)的位置，使粒子飛向更優(yōu)位置而避免陷入局部最優(yōu)位置。實驗表明，與基本粒子群算法MPSO相比，MCPSO算法能有效提升任務(wù)調(diào)度問題的求解質(zhì)量，縮短了makespan，優(yōu)化了計算節(jié)點的負(fù)載均衡性能。下一步的研究工作是在關(guān)聯(lián)任務(wù)調(diào)度時，如何利用該算法有效提高任務(wù)調(diào)度的效率，以及如何讓算法在當(dāng)網(wǎng)格系統(tǒng)中用戶的實際需求多樣化時仍然有效。

[1]Dong Fangpeng,SELIM G.Scheduling algorithms for grid computing:state of the art and open problems[D].Technical Report.School of computing,Queen′s University.Kingston,Ontario,January,2006.

[2]賀曉雨.一種用于任務(wù)調(diào)度的廣義遺傳算法[J].計算機工程,2010,36(17):184-186.

[3]AGHDAM H,PAYVAR S.A Modified simulated annealing algorithm for static task scheduling in grid computing[C].International Conference on Computer Science and Information Technology，2008:623-627.

[4]Zhang Lei,Chen Yuehui,Yang Bo.Task scheduling based on PSO algorithm in computational grid[M].Intelligent System Design and Applications，2006.

[5]魏東，吳良杰，佐丹，等.基于混合蟻群算法的網(wǎng)格任務(wù)調(diào)度[J].計算機工程,2010,36(3):215-217.

[6]KENNEDY J,EBERHART R.Particle Swarm Op-timization[C].In proc.IEEE Int Conf on Neural Networks.Perth,1995.

[7]李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用,1997,14(4):613-615.