基于改進遺傳算法的網格任務調度模型構建

潘利強+張燕琴

摘要摘要：網格任務調度屬于一個NP完全問題，傳統遺傳算法很難將這一多對象問題求得最優解。通過生成節點性能評估函數及構建任務動態調度模型，經由函數參數權重值調節，可實現將多對象問題轉化為單一對象問題，并對遺傳算法的雜交算子和變異算子進行優化，以實現全局最優解的求解。

關鍵詞關鍵詞：網絡技術；任務調度；遺傳算法；調度模型

DOIDOI：10.11907/rjdk.162355

中圖分類號：TP302文獻標識碼：A文章編號文章編號：16727800（2017）001001803

引言

網格技術以分布式計算為算法基礎，解決了跨終端的任務分配與調度及資源共享問題[1]。目前的網格任務調度主要是利用遺傳算法的動態迭代機制以及并行搜索的特點進行的，但存在著諸多問題。本文提出構建一個動態的任務調度模型，根據具體調度任務調整節點的性能參數及其權重值，以實現將多對象約束問題轉化為單一對象問題，并將傳統遺傳算法的雜交算子及變異算子進行優化，實現全局最優解的求解。

1問題描述

在網格任務調度模型中，遺傳算法容易陷入兩大問題，其一便是容易陷入局部最優問題。眾所周知，網格中的任務調度問題是一個多對象約束問題，也即是說，是一個NP完全問題[2]。因此，想要在一個NP完全問題中取得全局最優解，通常比較困難。既然如此，想要控制模型求解不陷入局部最優，而總是能夠使其取得全局最優的結果，則需要對模型針對的問題進行一定程度上的優化。將這一多對象問題，轉化為單一對象問題，問題則迎刃而解。然而，單對象約束問題很難達到網格調度模型期望的動態性。因此，必須引入一個動態調度函數，用以評估每個目標的不同需求，從而根據每個節點的性能參數得出期望中的調度模型，并對原有算法進行優化，以達到最終目標。

2動態調度模型構建

2.1節點性能評估函數ENPF生成

若要使一個屬于NP完全問題的多目標異構問題能夠保證得到全局最優解，需要引入一個網格系統中資源節點的性能函數。該函數既能夠深刻刻畫各節點性能，又能夠根據用戶的不同偏好和具體任務的不同需求進行用戶定制[3]。要評估某個節點的性能，除了一些已知的性能參數外，還要考慮以下3個關鍵因素：

（1）與時間有關，稱為活躍度，或者疲勞度，記為TINj。當此時間函數值越高，也即是說，就此網格節點而言，自上次完成任務到當前的時間間隔越長，此網格節點的動態性能評價越低。

（2）與節點使用頻度有關，稱為歷史記錄，記為CINj。此指標衡量源于對網格計算中針對任務貢獻資源的節點所創立的激勵機制，也即是說，對于向任務處理提供資源的節點，給予一定程度的激勵回報或費用獎勵，其具體方程式為：CINj=1-∑iCi∑iC0（1）其中，∑iCi為網格節點Pj以往所有成功完成任務中的執行時間總和；∑iC0為網格節點Pj以往所有成功完成任務中預計所需的執行時間總和。

（3）網格節點的動態累計可用性Uj，參數定義為：當節點在網格系統中處于可用狀態時，此網格節點具體執行任務的時間比例。當網格系統中的某資源節點在某網格任務的接受和處理過程中處于可用狀態時，此網格資源節點的可用時長累計為TA （Time of Available），相應的此網格節點的任務執行時長可累積計為TE（Time of Execution）。因此，網格節點的可用性定義如下：Uj=TEpj/TApj（2）其中，Uj為節點Pj的可用性，TEpj、TApj為網格資源節點Pj的執行時間與可用時間。

以上3個要素可以基本控制和調節不同用戶、不同具體任務的不同需求，在節點性能評估函數ENPF（Estimate of Node Properties Function）Ej中，節點以上3項要素具體參數值的考量比例由其3個參數值前賦予的權重值決定，3個權重的取值不同，可以影響模型得到不同的最優解，更加能夠滿足用戶和具體任務的需求。根據以上分析，網格中動態節點性能評估函數ENPF（Estimate of Node Properties Function）Ej為：Ej=α×e-TINj+β×CINj+γ×Uj（3）其中，α、β、γ為3個參數的權重值，它們滿足下式：α+β+γ=1

0<α，β，γ<1（4）2.2動態調度模型構建

一個網格系統中要進行動態的任務調度，首先要設計一個任務調度池，記為S。接著，要明確模型所解決的問題，即：一個網格系統G擁有多個網格資源節點，以及多個需要其解決和處理的任務。現在需要將這多個任務分配到多個網格內的資源節點上，每個任務可以分配給多個節點協同處理。期望完成的效果是：將任務分配給多個節點，盡可能提高每個節點的處理效率，使任務的調度和完成效率能夠達到令人滿意的效果[4]。

對此多對象的異構問題進行分析并用數學語言進行描述，即為：已知網格G中擁有任務數n個，計為ai；此網格資源節點集計為A；網格G中擁有網格資源節點m個，計為pj。現將網格系統中有關任務調度效率的幾個關鍵因素分別進行設置。

在網格系統上的任務調度過程中，任務ai在節點pj上的各項指標為：①網格任務調度長度L；②網格任務調度所得的網格節點性能值E；③節點調度代價C。 此外，對于文中涉及的各個變量腳標max與min，分別代表其相應的最大、最小值。這幾個關鍵因素對應的多對象約束函數如下：min（L）=∑ni=1∑mj=1λijLij（5）

max（E）=∑ni=1∑mj=1λijEij（6）

min（C）=∑ni=1∑mj=1λijCij（7）其中，λij的取值為：當任務ai在節點pj上的運行時間tij>0時，λij=1； 否則，λij=0。Lij=fj+gij+tij（8）其中，fj為網格系統節點pj的可用時長，gij為節點間的通信耗時，tij為節點的任務執行時長。因此，求解目標問題的多對象約束，即可歸納成上述約束方程組。

該多對象問題在求解時難以達到全局最優，為保證得出全局最優解，要將問題改進成一個單一對象問題，即要引入上文生成的網格節點性能評估函數Ej。

在遺傳算法的種群調度過程中，根據網格節點性能評估函數，將以上3項性能指標參數進行改進。任務ai在節點pj上的各項指標為：①網格任務調度長度LM；②網格任務調度所得的網格節點性能值Ej；③節點調度代價CM。

在IMPGA的種群調度過程中，其中：LMij=Lij-LMminLMmax-LMmin（9）

CMij=λij-Cminλij（10）于是最初確定的需解決的目標問題，多對象網格任務調度模型即可轉化為一個單一對象問題，得到目標方程為：min（x）=∑ni=1∑mj=1[ω1Lij+ω2（1-Eij）+ω3Cij]

=∑ni=1∑mj=1[ω1LMij+ω2（1-Eij）+ω3CMij（11）其中，ω1+ω2+ω3=1，0<ωθ<1，（θ=1，2，3）。此時，當用戶具有特殊節點性能偏好或具體任務在某些性能上有特殊要求時，只需通過調整權值ω1、ω2、ω3，即可滿足用戶的定制需求。

3算法改進

3.1算法原型

目標問題為異構網絡環境下的任務調度，因此需要考慮網格環境中每一個節點的性能和鏈路狀態，以及它的歷史供求關系，以此判斷節點的目前狀況。這些可以用節點的各項性能參數來表示[5]。

遺傳算法構造網格控制中任務動態調度的生成模型，以生成適用于具體任務的任務動態調度，以期在滿足任務安全性要求的基礎上，達到滿意的任務完成效率和資源利用率。針對目標問題的實時性等，以及網格計算的多對象特點，利用遺傳算法動態迭代的種群進化機制和搜索特點，構造具有動態特點的任務動態調度生成模型。針對具體任務，通過區間劃分、構造遺傳算法的適應度函數，確定編碼方式以及邊界條件；初始化網格平臺上的算法種群，在操作過程中，模型還可將可用的優秀染色體在不同的子種群間交換和共享；將各子種群分配至網格的各個集群、節點上，進行選擇、交叉和進化操作[6]；確定策略組合，生成合適的任務動態調度。因此，遺傳算法是動態調度模型的算法實現原型。

3.2雜交算子優化

不同于傳統遺傳算法GA中的雜交算子，本文中利用新型的交換策略將其進行模交換。由于此時的代碼段不屬于任何一個父代個體，而取模行為也不會出現異于種群遺傳因子的子代個體，因此可以達到增加搜索廣度的目的[7]。

在改進遺傳算法中，筆者對作為最主要搜索算子的雜交算子進行改進，改進后的雜交算子意在增加算法的搜索廣度，具體實現方法為：在雜交過程中，對父代中兩個個體對應位上的值相加后采用模運算求余，從而得到子代個體[8]。

3.3變異算子優化

傳統遺傳算法的任務調度易陷入局部最優解，在改進的遺傳算法中引入起輔助作用的變異算子并對其進行改進，以期增加種群多樣性，從而實現改進算法所得解達到全局最優[9]。考慮該變異算子作為輔助算子應具有簡單易行的特點，本算法將傳統變異算子作以下簡單優化，改進為一個均勻變異算子，即可滿足要求。設k=（k1，k2，...，kn）為參加變異操作的父代個體。具體實現方法如下：①以均勻概率選取隨機數xi∈[1，q]，（i∈N，i∈[1，n]），i從1至n依次取值；②以xi替換ki；③返回步驟①直至i=n結束。從而得到新個體x=（x1，x2，...，xn）為變異后的子代個體。

此改進變異算子不僅簡單易行，又可對個體生成產生擾動，增加了種群多樣性，有助于避免改進遺傳算法所得解陷入局部最優，這一點可以通過改進遺傳算法的收斂性來證明。

4結語

在網格的異構環境中，任務調度是一個受多方因素影響、多對象約束的NP完全問題。本文為實現求得全局最優解的目標，提出了一個用來調節網絡節點性能的評估函數，并構建了一個任務動態調度模型，將多對象約束問題轉化為單一對象問題。同時，對傳統遺傳算法的雜交算子和變異算子進行改進，從而擴充了算法的搜索廣度，實現了網格任務的動態調度，并且求得全局最優解，提高了任務執行效率和資源利用率。

參考文獻參考文獻：

[1]桂小林.網格技術導論[M].北京：北京郵電大學出版社，2005：115127.

[2]J HERRERA，E HUEDO，R MONTERO，et al.A gridoriented genetic algorithm[C].In Advances in Grid ComputingEGC，2005： 315322.

[3]D LIM，Y ONG，Y JIN，et al.Efficient hierarchical parallel genetic algorithms using grid computing[J].Future Gener.Comput.Syst.，2007，23（4）：658670.

[4]JUDITH MYERSON.Grid computing and cloud computing[Z].IBM Web Development，2008：13.

[5]CHALES J MALMBORG.A genetic algorithm for service level based vehicle scheduling[J].European Journal of Operational Research，1996（93）：121134.

[6]劉麗，楊揚.基于QoS的社區公共服務網格資源調度[J].北京科技大學學報，2004，26（5）：560563.

[7]方勇，劉嘉勇.信息系統安全導論[M].北京：電子工業出版社，2003：7895.

[8]顧愷愷，姚黎，袁家斌.基于安全控制策略的網格安全技術研究[J].中國制造業信息化，2006，35（15）：3387.

[9]陳琛，洪流，陳學廣，等.基于網格的遺傳算法及其在公交運行計劃編制中的應用研究[J].計算機學報，2009，32（12）： 23822388.

責任編輯（責任編輯：黃健）