摘 要： 提出了一種基于獨(dú)立任務(wù)的改進(jìn)PSO網(wǎng)格調(diào)度算法(MCPSO)。該算法結(jié)合粒子群優(yōu)化算法和混沌機(jī)制，在保證尋優(yōu)速度的同時(shí)又能兼顧“跳出”局部最優(yōu)的能力。實(shí)驗(yàn)結(jié)果表明，與基本粒子群優(yōu)化算法相比，該算法具有更好的收斂速度和求解質(zhì)量。
關(guān)鍵詞： 網(wǎng)格調(diào)度；獨(dú)立任務(wù)；PSO；混沌優(yōu)化
在網(wǎng)格計(jì)算中，任務(wù)管理、任務(wù)調(diào)度和資源管理是網(wǎng)格的3個(gè)基本功能。任務(wù)調(diào)度是網(wǎng)格系統(tǒng)的一個(gè)關(guān)鍵問題，關(guān)系到網(wǎng)格能否高效利用資源、快速完成任務(wù)以及實(shí)現(xiàn)系統(tǒng)負(fù)載均衡。同時(shí)它也是一個(gè)NP完全問題[1]，即得到一個(gè)最優(yōu)的調(diào)度方案或是在有限的時(shí)間里找出最優(yōu)(任務(wù),資源)的匹配方案是不可能的。目前多采用啟發(fā)式算法解決此類問題。
近年來，很多學(xué)者將啟發(fā)式算法應(yīng)用于任務(wù)調(diào)度中，并取得了較好的研究成果[2-5]。其中，GA算法可能找到最優(yōu)解，但選擇過程存在隨機(jī)性，不能確保得到最優(yōu)解，同時(shí)開銷大，運(yùn)行時(shí)間長(zhǎng)；AA算法雖然有正反饋機(jī)制能避免早熟現(xiàn)象，但容易收斂于局部最優(yōu)，而且算法復(fù)雜，搜索時(shí)間長(zhǎng)；SA算法能以一定的概率接受差的解而可能跳出局部極小，是一種全局最優(yōu)算法，但是搜索時(shí)間比較長(zhǎng)；PSO粒子群優(yōu)化算法[6]搜索速度快、操作簡(jiǎn)單、效率高，但是易陷入局部極值，搜索精度不高。
針對(duì)PSO易早熟、求解質(zhì)量不高的問題，為實(shí)現(xiàn)最小化任務(wù)完成總時(shí)間(makespan)，本文提出一種基于獨(dú)立任務(wù)調(diào)度的改進(jìn)PSO網(wǎng)格調(diào)度算法MCPSO(An improved PSO of grid scheduling algorithm under the meta task)。該算法的主要思想是：首先采用混沌[7]序列初始化粒子的位置，并在產(chǎn)生的大量粒子中擇優(yōu)選出初始種群；然后在粒子更新時(shí)引入混沌搜索，隨機(jī)產(chǎn)生若干混沌序列并把最優(yōu)混沌序列得到的位置和當(dāng)前粒子最優(yōu)位置比較，如果優(yōu)于當(dāng)前粒子，則更新當(dāng)前粒子的最優(yōu)位置，引導(dǎo)當(dāng)前粒子跳出局部最優(yōu)點(diǎn)，快速尋找最優(yōu)解。實(shí)驗(yàn)表明，該算法改善了PSO算法易陷入局部最優(yōu)問題，同時(shí)兼顧更好的makespan和負(fù)載均衡，有效提高網(wǎng)格的性能。
1 問題定義
圖1所示是一個(gè)簡(jiǎn)單的任務(wù)調(diào)度流程圖，其中MDS(Monitoring and Discovering Service)是資源監(jiān)控與發(fā)現(xiàn)服務(wù)，用于收集和發(fā)布系統(tǒng)狀態(tài)信息。
如圖1所示，首先任務(wù)劃分模塊將應(yīng)用程序劃分為若干個(gè)子任務(wù)，然后調(diào)度模塊從網(wǎng)格資源中的信息采集模塊MDS收集必要信息，最后按一定的策略對(duì)任務(wù)進(jìn)行分發(fā)。
通常在網(wǎng)格環(huán)境下主要考慮一組相互獨(dú)立、任務(wù)之間沒有數(shù)據(jù)和通信依賴的獨(dú)立任務(wù)(metatask)。目前多數(shù)研究是基于此展開的。本文將主要研究獨(dú)立任務(wù)調(diào)度。
現(xiàn)假定虛擬組織VO中用戶提交了若干個(gè)任務(wù)，這些任務(wù)經(jīng)由圖1中的劃分模塊分成n個(gè)獨(dú)立子任務(wù)t1、t2、…、tn組成子任務(wù)集合T，網(wǎng)格系統(tǒng)中有m個(gè)節(jié)點(diǎn)(網(wǎng)格資源)r1、r2、…、rm構(gòu)成資源集合R。任一任務(wù)ti可以在任一節(jié)點(diǎn)rj上執(zhí)行，rj在同一時(shí)刻只能處理一個(gè)任務(wù)，而ti不能同時(shí)在兩個(gè)節(jié)點(diǎn)上執(zhí)行，ti一旦開始，rj被獨(dú)占，直到ti完成后才能執(zhí)行其他任務(wù)。用一個(gè)n維向量(w1，w2，…，wn)表示任務(wù)的預(yù)計(jì)完成時(shí)間，其中wi為任務(wù)i的預(yù)計(jì)完成時(shí)間。
定義1 (任務(wù)映射集)n個(gè)任務(wù)映射到m個(gè)節(jié)點(diǎn)的映射方案T→R集合即任務(wù)映射集MAP。集合MAP={map1，map2，…，mapn}，其中mapi表示第i個(gè)任務(wù)在映射到的節(jié)點(diǎn)mapi上執(zhí)行。
定義2 (節(jié)點(diǎn)工作時(shí)間)節(jié)點(diǎn)工作時(shí)間RCj是指節(jié)點(diǎn)j處理完所有分配給它的任務(wù)所花費(fèi)的時(shí)間。如式(1)所示：
式中，μ為控制參數(shù)，0≤μ≤4；un∈[0，1]。
混沌搜索的主要思想是通過混沌系統(tǒng)如式(7)產(chǎn)生混沌序列，然后通過載波的方式
xni=ai+uni(bi-ai)(9)
將其映射到優(yōu)化空間中，也就是將混沌變量的值域“放大”到優(yōu)化變量的取值范圍內(nèi)。
2.3 改進(jìn)PSO的網(wǎng)格調(diào)度算法(MCPSO)
PSO具有很強(qiáng)的全局搜索能力，但不能保證全局收斂。當(dāng)粒子自身信息和個(gè)體極值信息占優(yōu)時(shí)，往往停滯于局部最優(yōu)解，且隨機(jī)初始化的種群質(zhì)量不高，甚至距離最優(yōu)解位置較遠(yuǎn)。而混沌具有良好的遍歷性、隨機(jī)性以及一定的突跳能力，易跳出局部極值點(diǎn)，最終可能得到最優(yōu)解。
因而可以利用混沌的遍歷性，在初始化時(shí)產(chǎn)生大量粒子，從中擇優(yōu)選出初始種群。同時(shí)在粒子位置和速度更新時(shí)，引入混沌搜索，并把最優(yōu)混沌序列得到的位置與當(dāng)前粒子最優(yōu)位置相比較，如果優(yōu)于當(dāng)前粒子則進(jìn)行替換。這樣可以有效減少算法收斂于局部極值的現(xiàn)象。算法流程如下：
(1)給定種群大小POPSIZE、最大迭代次數(shù)、慣性權(quán)值w、學(xué)習(xí)因子c1、c2及控制參數(shù)μ等。
(2)混沌初始化：
①隨機(jī)產(chǎn)生一個(gè)n維每個(gè)分量數(shù)值在[0，1]上的向量，z1=(z11，z12，…，z1n)，n為種群的大小，根據(jù)式(8)，得n個(gè)混沌序列z1，z2，…，zn。
②利用式(9)將zi，1≤i≤n分量載波到相應(yīng)的變量取值區(qū)間，選出較優(yōu)的POPSIZE個(gè)粒子作為初始種群。
(3)隨機(jī)初始化各個(gè)粒子的初始速度并計(jì)算其適應(yīng)值，設(shè)置各個(gè)粒子的初始極值并計(jì)算種群極值。
(4)根據(jù)式(6)、式(7)更新粒子位置和速度。
(5)啟動(dòng)混沌搜索。隨機(jī)產(chǎn)生d個(gè)[0，1]上的隨機(jī)數(shù)，根據(jù)式(8)得到d個(gè)混沌序列，并把產(chǎn)生的混沌序列依次載波放大到對(duì)應(yīng)變量的取值范圍上，從中選出最優(yōu)位置xi*。
(6)比較當(dāng)前粒子的個(gè)體極值和xi*的適應(yīng)值，如果xi*較優(yōu)則用xi*更新當(dāng)前粒子的最優(yōu)位置。
(7)更新個(gè)體極值和群體極值。
(8)跳至步驟(4)直到算法到達(dá)最大迭代次數(shù)。
(9)輸出全局最優(yōu)值和全局最優(yōu)粒子、最優(yōu)跨度ω、負(fù)載平衡度β。
2.4 問題編碼
對(duì)于n個(gè)任務(wù)m個(gè)資源的調(diào)度，粒子的位置和速度均用n維向量表示，維數(shù)和任務(wù)數(shù)一致。如位置向量(x1，x2，…，xm)中第i維分量xi表示任務(wù)ti的權(quán)值，是[0，m)之間的一個(gè)隨機(jī)數(shù)。當(dāng)n=10，m=5時(shí)，各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的權(quán)值范圍如表1。
若某粒子的位置矢量表示如下：
Particle：(2.5, 1. 8,0.6,2.4,4.8,3.2,0.7,1.9,2.5,4.0)
上述粒子即為任務(wù)的一個(gè)調(diào)度方案，由表1可得任務(wù)與節(jié)點(diǎn)的映射關(guān)系如表2所示。
3 實(shí)驗(yàn)與性能分析
以GridSim工具包為基礎(chǔ)構(gòu)建網(wǎng)格仿真環(huán)境，將本文提出的MCPSO算法與基于獨(dú)立任務(wù)的基本粒子群優(yōu)化算法MPSO算法進(jìn)行對(duì)比分析。
PSO算法參數(shù)設(shè)置如下：種群大小POPSIZE=10，學(xué)習(xí)因子c1=c2=2.05，慣性因子ω=0.729，算法最大迭代次數(shù)為1 000，混沌控制參數(shù)?滋=4。測(cè)試運(yùn)行50次，取50次實(shí)驗(yàn)的平均結(jié)果作為實(shí)驗(yàn)結(jié)果。
實(shí)驗(yàn)中有5個(gè)節(jié)點(diǎn)，10個(gè)任務(wù)，各個(gè)任務(wù)的預(yù)計(jì)完成時(shí)間{10, 42, 34, 27, 56, 79, 77, 62, 81, 51}，單位為s。
實(shí)驗(yàn)從調(diào)度方案的求解質(zhì)量、makespan、負(fù)載平衡度3個(gè)方面比較兩種算法的性能。
求解質(zhì)量如表3所示。
比較可知，本文提出的MCPSO算法比MPSO有更好的性能，平均跨度值與最好解的偏差小，最好解的次數(shù)明顯多于MPSO算法，最差解也明顯優(yōu)于MPSO，MCPSO算法的求解質(zhì)量更好。
為了觀察算法的收斂特性，給出了兩種算法1 000次迭代的makespan變化曲線，如圖2所示。從圖2可以看出，MCPSO算法收斂速度優(yōu)于MPSO算法的情況，并能得到更好的解，而且改進(jìn)的PSO算法初始解明顯更優(yōu)。
由圖3可知，兩種算法的負(fù)載均衡度隨著迭代次數(shù)的增加而減少，即負(fù)載均衡性能都有提升。而MCPSO算法的負(fù)載均衡性能大大好于MPSO算法。
通過實(shí)驗(yàn)可以看出，基本粒子群能快速地找到較優(yōu)解，但是后期逐漸收斂于該解，并處于“停滯”狀態(tài)，很難得到更優(yōu)解。引入混沌機(jī)制的MCPSO算法，擁有基本粒子群算法快速收斂的特性，同時(shí)在未得到最優(yōu)解的情況下，逐漸向最優(yōu)解靠近，不斷得到更優(yōu)解甚至最優(yōu)解。
為改善網(wǎng)格調(diào)度性能，本文提出了基于獨(dú)立任務(wù)的改進(jìn)PSO任務(wù)調(diào)度算法。該算法以時(shí)間跨度makespan為數(shù)學(xué)模型，結(jié)合粒子群算法和混沌優(yōu)化原理，首先通過混沌初始化得到較優(yōu)的初始種群，有效減少粒子飛向較優(yōu)點(diǎn)的迭代次數(shù)；在更新粒子位置和速度時(shí)，對(duì)粒子的最優(yōu)位置進(jìn)行混沌搜索，試圖找出更優(yōu)的位置，使粒子飛向更優(yōu)位置而避免陷入局部最優(yōu)位置。實(shí)驗(yàn)表明，與基本粒子群算法MPSO相比，MCPSO算法能有效提升任務(wù)調(diào)度問題的求解質(zhì)量，縮短了makespan，優(yōu)化了計(jì)算節(jié)點(diǎn)的負(fù)載均衡性能。下一步的研究工作是在關(guān)聯(lián)任務(wù)調(diào)度時(shí)，如何利用該算法有效提高任務(wù)調(diào)度的效率，以及如何讓算法在當(dāng)網(wǎng)格系統(tǒng)中用戶的實(shí)際需求多樣化時(shí)仍然有效。
參考文獻(xiàn)
[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].計(jì)算機(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].計(jì)算機(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.