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