基于改進型混洗蛙跳算法的網(wǎng)格DAG任務調(diào)度①

戴 扶，黃文明，鄧珍榮

（桂林電子科技大學 計算機科學與工程學院，廣西 桂林 541004）

網(wǎng)格［1］將互聯(lián)網(wǎng)上的各種資源集中在一個統(tǒng)一的框架內(nèi)，為上層應用提供高效的資源服務。網(wǎng)格環(huán)境中的調(diào)度問題研究由來已久，調(diào)度問題可看作一個組合問題，將N個任務分配到M個資源上。這種優(yōu)化組合問題非常適合用群體啟發(fā)式算法來解決。目前，研究較多的是遺傳算法（GA）、粒子群算法（PSO）、蟻群算法（ACA）、人工魚群算法（AFSA）等［2－5］?；煜赐芴惴ǎ╯huffled frog leaping algorithm，簡稱SFLA）是2003年由Eusuff等［6］提出的一種啟發(fā)式算法，用于優(yōu)化組合問題。此算法具有易理解、參數(shù)少、速度快、尋優(yōu)能力強、實現(xiàn)簡單等優(yōu)點，已被廣泛應用于水利管網(wǎng)、電力網(wǎng)絡［7］中。具有依賴關(guān)系的任務可被抽象為一個有向無環(huán)圖（directed acyclic graph，簡稱DAG）模型，DAG任務自身的結(jié)構(gòu)和實際應用程序內(nèi)的結(jié)構(gòu)特征非常相似，因此，研究DAG任務調(diào)度問題更具有現(xiàn)實意義，但也使得任務調(diào)度問題更加復雜。

針對DAG任務的編碼方式可分為2類：

1）間接編碼方式。將資源先隨機分配給任務，再利用其他手段剔除不符合DAG任務約束條件的解。如文獻［8］中，任務的執(zhí)行序不變，隨機分配一個資源，然后通過計算節(jié)點的最長前驅(qū)路徑和最短后繼路徑判斷任務之間的關(guān)聯(lián)度，剔除不符合約束條件的問題解。

2）直接利用DAG任務的約束條件進行編碼。陳晶等［9］將DAG任務的高度值作為執(zhí)行的優(yōu)先級別，再根據(jù)級別隨機分配優(yōu)先權(quán)值，這些權(quán)值組合起來就是任務解的編碼。

但這些方式都存在解碼方式比較復雜或未考慮網(wǎng)格的動態(tài)性的缺陷。如果網(wǎng)絡資源在編碼階段離開了網(wǎng)絡環(huán)境，那么就會造成最后的分配方案失效。鑒于此，提出一種改進型混洗蛙跳算法解決網(wǎng)格DAG任務調(diào)度問題：將編碼階段和資源分配階段分開，先依照DAG的依賴條件進行編碼，再在任務派發(fā)階段分配資源計算適應值；重新定義解空間度量規(guī)則，精簡算法空間，減少算法的計算量；改進SFLA算法的搜索策略，使得解集能夠迅速向最優(yōu)解聚攏。

1 編碼及適應函數(shù)

1.1 編碼

問題解的組合方式能夠反映出一個解的解決問題的效率。這種思想來源于管理領(lǐng)域內(nèi)的崗位輪換制度，通過比較人員在不同崗位上的工作狀況，進行統(tǒng)計分析，幫助優(yōu)化整個組織的人力資源配置。同樣地，DAG任務可看作一個組織機構(gòu)，各個節(jié)點就是“輪崗人員”。一個完整的“人員職位安排”就是DAG任務調(diào)度問題的一個解，如圖1所示。

圖1 DAG任務編碼示例Fig.1 Example of DAG task coding

受文獻［10］分代（GS）算法的啟發(fā)，將DAG任務按照高度值分配優(yōu)先級，同一層的節(jié)點可視為元任務，執(zhí)行序可任意排列；不同層的節(jié)點，優(yōu)先級高的先執(zhí)行。其實質(zhì)就是將解的執(zhí)行序列按約束條件分段，段內(nèi)編號是確定的，但段內(nèi)編號順序是隨意的。

1.2 適應度函數(shù)

適應值反映了解的優(yōu)秀程度，在本研究中體現(xiàn)為總?cè)蝿盏膱?zhí)行時間。執(zhí)行時間與資源分配方案息息相關(guān)，良好的分配方案可有效地提高解的質(zhì)量，提升算法的搜索性能和收斂速度。采用動態(tài)最早完成優(yōu)先（DEFF）算法［11］的思想對問題解進行資源分配，以保證每個節(jié)點的開始時間最早、執(zhí)行時間最短。

設(shè)系統(tǒng)有m個資源，P＝｛P1，P2，…，Pm｝，DAG任務分為n個節(jié)點，T＝｛T1，T2，…，Tn｝，fat（Pi）為某個資源的可利用時間，Eij為資源Pi、Pj間的通信開銷執(zhí)行時間，p（Ti）為Ti的前驅(qū)節(jié)點集合，則Ti在Pj上的最早啟動時間為：

fet，Ti（Pj）為任務Ti在Pj上的執(zhí)行時間，則任務Ti在Pj上的完成時間為

因此，任務Ti的最早結(jié)束時間F（Ti）和最早開始時間S（Ti）滿足：

最終適應度函數(shù)為

1.3 解空間的度量

由于編碼方式改變，需重新定義解空間的度量方式。受DAG任務約束條件的約束，高度值相同的節(jié)點只能在同一層中移動，可視這些節(jié)點在某個范圍內(nèi)是封閉的。因此，將DAG的層次視為解空間的維度，某個層次中的不同排序視為分布在這條基軸上的離散點，如圖2所示。如此定義可有效地反映DAG的特點，并簡化計算量。

圖2 基軸示意圖Fig.2 Example of basic shaft

定義1 基軸度量規(guī)則。在某個基軸上2個不同編碼的α和β，α的編碼通過K次交換可轉(zhuǎn)換成β，則稱α到β的距離為K，用K＝β－α表示。交換規(guī)則如下：

1）假設(shè)i為α中的第i個編碼，若該元素與β中的第i個編碼相同，則比較第i＋1個元素，直到比較α中所有元素；若不同，則跳到2）。

2）查找該編碼在β中所處的位置j，然后將α中該編碼所處位置和j位置的元素交換，再回到1）。

對于解空間中的任意解V，設(shè)其DAG模型分為U層，則解為U個基構(gòu)成的向量。

定義2 解之間的歐式距離。對于解空間內(nèi)任意2個解向量V1、V2，設(shè)解分為U層，ci為V2中第i個基到V1中第i個基的距離，則V2到V1的距離為：

2 網(wǎng)格任務調(diào)度模型

用戶將應用程序提交到任務池內(nèi)，網(wǎng)格資源向網(wǎng)格資源管理器進行登記注冊。調(diào)度器從任務池內(nèi)順序取出調(diào)度任務，同時從算法庫中選擇調(diào)度算法，利用資源管理器的資源列表和工具庫內(nèi)的一些必要工具，進行調(diào)度決策。調(diào)度決策完畢后，按照決策結(jié)果將任務發(fā)送到相應的網(wǎng)格資源，模型如圖3所示。

圖3 網(wǎng)格任務調(diào)度模型Fig.3 Grid task scheduling model

考慮資源間的通信開銷，每個資源都有一份通信表，記錄與相鄰資源間的通信時間。調(diào)度方式采用非搶占式調(diào)度方式。

3 改進型混洗蛙跳算法（ISFLA）

3.1 SFLA

SFLA是為解決全局最優(yōu)解而提出的一種變異模因進化算法［12］，它并不強調(diào)個體，而是強調(diào)個體所持有的思想變化［6］。通過向優(yōu)秀個體學習，從而改進自己的思想，進而推動整個種群的進化。算法過程如下：

1）隨機產(chǎn)生N只青蛙作為初始種群，然后計算每只青蛙的適應值，并按照適應值的優(yōu)劣排序。2）根據(jù)式（5）將N只青蛙劃分成M個模因族群。

其中：Yk為第k個模因族群；D（j）k為第k個族群中的第j只青蛙；j∈［1，N］，k∈［1，M］。

3）局部搜索。記錄種群最優(yōu)解Dg、族群內(nèi)部的最優(yōu)解Db和最差解Dw，根據(jù)式（6）進行進化。Dw先向Db進化，若進化失敗，則向Dg進化，若仍失敗，則Dw隨機變化一下替換原來的Dw。

其中：rand（）為隨機函數(shù)，取值（0，1）；dmax為允許移動的最大步長；Dx為Db或Dg。

4）全局搜索。將所有族群打散并重新按照適應度升序排序，若達到算法結(jié)束條件，則轉(zhuǎn)到5），否則回到2）。

5）輸出最優(yōu)級。

3.2 改進策略

SFLA作為一種群體啟發(fā)式算法雖然有參數(shù)少、全局尋優(yōu)能力強的特點，但也存在容易陷入局部最優(yōu)和收斂速度慢的缺點。在局部搜索策略中，Dw向Db和Dg學習為種群提供進化動力，并通過自我突變增加種群多樣性，進化點單一、動力不足導致種群長期徘徊在舊的狀態(tài)中。為此，將Db也作為進化點，向Dg學習，增加種群的進化動力，同時加入鄰域搜索作為擴展搜索解空間的手段，增加種群多樣性。

3.2.1 鄰域搜索

設(shè)置一個鄰域半徑l，當解空間中一個解向目標解逼近時，若兩解間的距離小于l，則開始探索周邊空間的優(yōu)秀解。

在算法的初期階段，l的取值應大一些，使種群在初期能夠盡可能地在整個解空間中移動，收集更多潛在的優(yōu)秀解；在算法的后期，l值應該減小，使算法有較強的局部挖掘能力。因此，l的取值為

其中：i＝1，2，…，np；np為種群迭代次數(shù)。實驗結(jié)果表明，Dmax＝9，Dmin＝1較為合適。

3.2.2Db向Dg進化策略

計算種群最優(yōu)解的適應值A(chǔ)（Dg）、族群最優(yōu)解的適應值A(chǔ)（Db）、族群最差解的適應值A(chǔ)（Dw）以及Dg與Db之間的距離D。若A（Db）＜A（Dg），直接用Db替換Dg；若A（Db）＜A（Dg），D＞l，按式（8）進化。

當A（Db′）＜A（Dg）時，用Db′替換Dg；A（Db′）＜A（Db）時，Db′替換Db；否則視為進化失敗，進行鄰域搜索。若A（Db）＝A（Dg）‖D＜l‖Db向Dg進化失敗，也進行鄰域搜索。由于鄰域搜索可能對Db所持有的信息造成較大的破壞，設(shè)定一個突變因子τ，τ∈（0，1）。隨機抽取U×τ個基，U為DAG任務的層數(shù)，根據(jù)式（9）進化。

這樣既能保持解的部分優(yōu)良信息，又能對Db周圍的空間進行探索。

當A（Db′）＜A（Dg）時，Db′替換Dg；A（Db′）≤A（Db）時，Db′替換Db；否則視為搜索失敗。

3.2.3Dw向Db進化策略

若A（Dw）＞A（Db），則根據(jù)式（10）進化。

當A（Dw′）＜A（Db）時，Dw′替換Db；A（Dw′）＜A（Dw）時，Dw′替換Dw；否則視為進化失敗，進行鄰域搜索。

若A（Dw）＝A（Db）‖Dw向Db進化失敗，進行鄰域搜索，根據(jù)式（9）進行突變，Db換成Dw。

當A（Dw′）＜A（Db）時，Dw′替換Db，否則Dw′替換Dw，增加種群多樣性。

4 系數(shù)確定和仿真及實驗分析

為驗證ISFLA的有效性，根據(jù)圖3所示的網(wǎng)格任務調(diào)度模型，在Windows環(huán)境下用Java開發(fā)了一個網(wǎng)格環(huán)境任務調(diào)度仿真平臺。在此平臺上，分別對GA、PSO、SFLA和ISFLA的搜索性能及收斂速度進行實驗。實驗數(shù)據(jù)通過Matlab進行比較分析。

GA采用標準遺傳算法，以輪盤賭法作為選擇策略，單點交叉，一點變異，突變因子為0.05，交叉系數(shù)為0.6；PSO采用標準粒子群算法，慣性系數(shù)為0.8，c1、c2為學習因子，均取值2，進化步長在［1，8］；SFLA最大進化步長為3。

4.1 確定ISFLA的最大進化步長和突變因子

最大進化步長dmax如果設(shè)置較大，青蛙有可能越過最優(yōu)值，而設(shè)置過小，移動速度會變慢，導致搜索效率太低。而設(shè)置突變因子τ的目的是為了在鄰域搜索時，只讓部分解的基進行突變，使得解的部分優(yōu)秀信息有可能保存下來，同時也使得進化路徑更加復雜，增加了計算負擔，因此有必要對其進行討論。

實驗中，可用網(wǎng)格資源數(shù)量為4，任務量為50個節(jié)點的DAG任務，初始種群為200，族群數(shù)為10，族群循環(huán)次數(shù)10次，種群循環(huán)300次，測試步長時，τ＝0.25；測突變因子時，dmax＝3，結(jié)束條件為種群循環(huán)200次。每種步長各運行10次，然后求均值。結(jié)果如圖4和表1、2所示。

從表1可看出，dmax＝9、7、3時，算法的時間開銷都集中在45s左右，但當dmax＝2時，算法的時間開銷提高到了67.10s，顯然進化步長縮短導致解的進化速度放慢。表2為突變因子對跨度和算法時間開銷的影響。從表2可看出，τ值的變化對算法的時間開銷和調(diào)度跨度影響很小。從圖4（a）可看出，dmax為7、9，算法的搜索性能明顯差于dmax為2、3，這是由于進化步長過大導致解在進化時錯失了許多潛在的優(yōu)秀解。從圖4（b）可看出，τ＝0.25時，算法的收斂速度比其他值要好些；τ＝0.80時，解的大部分基都參與了突變計算，使解本身的一些優(yōu)良基因丟失，圖4（b）中表現(xiàn)為收斂速度最差；τ＝0.10時，解中只有很少的基參與了突變計算，雖然保留了自身的優(yōu)秀基因，但對自身的改良較少。因此，dmax＝3，τ＝0.25時，ISFLA的效果較好。

圖4 ISFLA算法參數(shù)與調(diào)度跨度的關(guān)系Fig.4 The relation between SFLA parameters and span

表1 最大進化步長與調(diào)度跨度的關(guān)系Tab.1 The relation between max step size and span

表2 突變因子與調(diào)度跨度和ISFLA時間開銷的關(guān)系Tab.2 The mutation factor，span and ISFLA time cost

4.2 驗證算法的搜索性能和收斂速度試驗

選取網(wǎng)格資源數(shù)量為4，任務量為30、50個節(jié)點的DAG任務。初始種群為200，族群數(shù)為10，族群循環(huán)次數(shù)10次，種群循環(huán)200次，結(jié)束條件為種群循環(huán)200次。GA、PSO、SFLA和ISFLA各 運 行10組，求每一代的均值。實驗結(jié)果如圖5所示。從圖5（a）可看出，任務數(shù)為30時，在200次迭代過程中，各算法都能收斂到最優(yōu)解附近，GA和ISFLA搜索性能稍好。當任務規(guī)模增加到50，ISFLA和GA的搜索性能明顯好于SFLA和PSO，如圖5（b）所示。這是由于ISFLA在進化策略中增加了鄰域搜索策略，擴大了算法的探索空間，保證了種群的多樣性，從而有效避免了局部收斂。從圖5（c）可看出，PSO、GA分別經(jīng)150、40次迭代才收斂到最優(yōu)解附近，而SFLA、ISFLA分別在24、15次迭代就收斂到了最優(yōu)解附近，收斂速度較快?？捎嬎愠鯥SFLA的收斂速度較GA、PSO、SFLA分 別 提 高了75%、94%和27%。從圖5（d）可看出，ISFLA的收斂速度明顯高于GA。因此，在有時間條件約束的情況下，ISFLA能更快找到全局最優(yōu)解。

圖5 2種任務規(guī)模下GA、PSO、SFLA和ISFLA的調(diào)度跨度Fig.5 The span of GA，PSO，SFLA and ISFLA under two scales

4.3 驗證算法時間開銷實驗

實驗設(shè)計：選用網(wǎng)格資源數(shù)量為4，任務量為10、20、30、40、50個節(jié)點的DAG任務。初始種群為200，族群數(shù)為10，族群循環(huán)次數(shù)10次，種群循環(huán)500次，結(jié)束條件為種群循環(huán)500次。4種算法各運行10組，分別對算法的時間開銷求均值并進行比較。實驗結(jié)果如表3所示。

表3 不同規(guī)模下算法時間跨度Tab.3 The solutions obtained by different algorithms under the different task scales s

圖6為不同規(guī)模下4種算法的時間開銷。從圖6可看出，SFLA和ISFLA的時間開銷比GA和PSO要小。而從表3中反映的數(shù)據(jù)來看，GA和ISFLA的結(jié)果更好。因此，在網(wǎng)格資源有限的情況下，ISFLA能夠在較少的時間內(nèi)給出最好的全局最優(yōu)解。

圖6 不同規(guī)模下4種算法的時間開銷Fig.6 The time cost of four algorithms under the different task scales

5 結(jié)束語

通過綜合分析網(wǎng)格動態(tài)環(huán)境中的DAG任務調(diào)度的特點，建立了一個網(wǎng)格任務調(diào)度模型。結(jié)合DAG任務和啟發(fā)式群體智能算法的特點，設(shè)計了任務的編碼方式和度量方式?；卩徲蛩阉鞑呗院驮黾幼迦哼M化點，改進了SFLA的局部搜索策略，進而提出一種改進型混洗蛙跳算法。實驗表明，該算法能夠有效地提高搜索性能和收斂速度。下一步計劃在多目標網(wǎng)格環(huán)境下的DAG任務調(diào)度算法中，把網(wǎng)格資源負載性能指標融入到優(yōu)化策略。

［1］Foster I，Kesselman C，Tuecke S.The anatomy of the grid：enabling scalable virtual organizations［J］.International Journal of High Performance Computing Applications，2001，15（3）：200－222.

［2］蘭舟.分布式系統(tǒng)中的調(diào)度算法研究［D］.成都：電子科技大學，2009：17－54.

［3］胡成玉.面向動態(tài)環(huán)境的粒子群算法研究［D］.武漢：華中科技大學，2010：19－67.

［4］馮春時.群智能優(yōu)化算法及其應用［D］.合肥：中國科學技術(shù)大學，2009：23－55.

［5］劉波.蟻群算法改進及應用研究［D］.秦皇島：燕山大學，2010：12－45.

［6］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.Journal of Water Resources Planning and Management，2003，129（3）：210－225.

［7］Niknam T，Azad Farsani E.A hybrid self－adaptive particle swarm optimization and modified shuffled frog leaping algorithm for distribution feeder reconfiguration［J］.Engineering Applications of Artificial Intelligence，2010，23（8）：1340－1349.

［8］朱海，王宇平.融合安全的網(wǎng)格依賴任務調(diào)度雙目標優(yōu)化模型及算法［J］.軟件學報，2011，22（11）：2729－2748.

［9］陳晶，潘全科.同構(gòu)計算環(huán)境中DAG任務圖的調(diào)度算法［J］.計算機工程與設(shè)計，2009，（3）：668－670.

［10］Carter B R，Watson D W，F(xiàn)reund R F，et al.Generational scheduling for dynamic task management in heterogeneous computing systems［J］.Information Sciences，1998，106（3）：219－236.

［11］馬丹.任務間相互依賴的并行作業(yè)調(diào)度算法研究［D］.武漢：華中科技大學，2007：65－69.

［12］Eusuff M，Lansey K，Pasha F.Shuffled frog－leaping algorithm：a memetic meta－h(huán)euristic for discrete optimization［J］.Engineering Optimization，2006，38（2）：129－154.