基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度模型構(gòu)建

潘利強(qiáng)+張燕琴

摘要摘要：網(wǎng)格任務(wù)調(diào)度屬于一個(gè)NP完全問題，傳統(tǒng)遺傳算法很難將這一多對(duì)象問題求得最優(yōu)解。通過生成節(jié)點(diǎn)性能評(píng)估函數(shù)及構(gòu)建任務(wù)動(dòng)態(tài)調(diào)度模型，經(jīng)由函數(shù)參數(shù)權(quán)重值調(diào)節(jié)，可實(shí)現(xiàn)將多對(duì)象問題轉(zhuǎn)化為單一對(duì)象問題，并對(duì)遺傳算法的雜交算子和變異算子進(jìn)行優(yōu)化，以實(shí)現(xiàn)全局最優(yōu)解的求解。

關(guān)鍵詞關(guān)鍵詞：網(wǎng)絡(luò)技術(shù)；任務(wù)調(diào)度；遺傳算法；調(diào)度模型

DOIDOI：10.11907/rjdk.162355

中圖分類號(hào)：TP302文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）001001803

引言

網(wǎng)格技術(shù)以分布式計(jì)算為算法基礎(chǔ)，解決了跨終端的任務(wù)分配與調(diào)度及資源共享問題[1]。目前的網(wǎng)格任務(wù)調(diào)度主要是利用遺傳算法的動(dòng)態(tài)迭代機(jī)制以及并行搜索的特點(diǎn)進(jìn)行的，但存在著諸多問題。本文提出構(gòu)建一個(gè)動(dòng)態(tài)的任務(wù)調(diào)度模型，根據(jù)具體調(diào)度任務(wù)調(diào)整節(jié)點(diǎn)的性能參數(shù)及其權(quán)重值，以實(shí)現(xiàn)將多對(duì)象約束問題轉(zhuǎn)化為單一對(duì)象問題，并將傳統(tǒng)遺傳算法的雜交算子及變異算子進(jìn)行優(yōu)化，實(shí)現(xiàn)全局最優(yōu)解的求解。

1問題描述

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

2動(dòng)態(tài)調(diào)度模型構(gòu)建

2.1節(jié)點(diǎn)性能評(píng)估函數(shù)ENPF生成

若要使一個(gè)屬于NP完全問題的多目標(biāo)異構(gòu)問題能夠保證得到全局最優(yōu)解，需要引入一個(gè)網(wǎng)格系統(tǒng)中資源節(jié)點(diǎn)的性能函數(shù)。該函數(shù)既能夠深刻刻畫各節(jié)點(diǎn)性能，又能夠根據(jù)用戶的不同偏好和具體任務(wù)的不同需求進(jìn)行用戶定制[3]。要評(píng)估某個(gè)節(jié)點(diǎn)的性能，除了一些已知的性能參數(shù)外，還要考慮以下3個(gè)關(guān)鍵因素：

（1）與時(shí)間有關(guān)，稱為活躍度，或者疲勞度，記為TINj。當(dāng)此時(shí)間函數(shù)值越高，也即是說，就此網(wǎng)格節(jié)點(diǎn)而言，自上次完成任務(wù)到當(dāng)前的時(shí)間間隔越長(zhǎng)，此網(wǎng)格節(jié)點(diǎn)的動(dòng)態(tài)性能評(píng)價(jià)越低。

（2）與節(jié)點(diǎn)使用頻度有關(guān)，稱為歷史記錄，記為CINj。此指標(biāo)衡量源于對(duì)網(wǎng)格計(jì)算中針對(duì)任務(wù)貢獻(xiàn)資源的節(jié)點(diǎn)所創(chuàng)立的激勵(lì)機(jī)制，也即是說，對(duì)于向任務(wù)處理提供資源的節(jié)點(diǎn)，給予一定程度的激勵(lì)回報(bào)或費(fèi)用獎(jiǎng)勵(lì)，其具體方程式為：CINj=1-∑iCi∑iC0（1）其中，∑iCi為網(wǎng)格節(jié)點(diǎn)Pj以往所有成功完成任務(wù)中的執(zhí)行時(shí)間總和；∑iC0為網(wǎng)格節(jié)點(diǎn)Pj以往所有成功完成任務(wù)中預(yù)計(jì)所需的執(zhí)行時(shí)間總和。

（3）網(wǎng)格節(jié)點(diǎn)的動(dòng)態(tài)累計(jì)可用性Uj，參數(shù)定義為：當(dāng)節(jié)點(diǎn)在網(wǎng)格系統(tǒng)中處于可用狀態(tài)時(shí)，此網(wǎng)格節(jié)點(diǎn)具體執(zhí)行任務(wù)的時(shí)間比例。當(dāng)網(wǎng)格系統(tǒng)中的某資源節(jié)點(diǎn)在某網(wǎng)格任務(wù)的接受和處理過程中處于可用狀態(tài)時(shí)，此網(wǎng)格資源節(jié)點(diǎn)的可用時(shí)長(zhǎng)累計(jì)為TA （Time of Available），相應(yīng)的此網(wǎng)格節(jié)點(diǎn)的任務(wù)執(zhí)行時(shí)長(zhǎng)可累積計(jì)為TE（Time of Execution）。因此，網(wǎng)格節(jié)點(diǎn)的可用性定義如下：Uj=TEpj/TApj（2）其中，Uj為節(jié)點(diǎn)Pj的可用性，TEpj、TApj為網(wǎng)格資源節(jié)點(diǎn)Pj的執(zhí)行時(shí)間與可用時(shí)間。

以上3個(gè)要素可以基本控制和調(diào)節(jié)不同用戶、不同具體任務(wù)的不同需求，在節(jié)點(diǎn)性能評(píng)估函數(shù)ENPF（Estimate of Node Properties Function）Ej中，節(jié)點(diǎn)以上3項(xiàng)要素具體參數(shù)值的考量比例由其3個(gè)參數(shù)值前賦予的權(quán)重值決定，3個(gè)權(quán)重的取值不同，可以影響模型得到不同的最優(yōu)解，更加能夠滿足用戶和具體任務(wù)的需求。根據(jù)以上分析，網(wǎng)格中動(dòng)態(tài)節(jié)點(diǎn)性能評(píng)估函數(shù)ENPF（Estimate of Node Properties Function）Ej為：Ej=α×e-TINj+β×CINj+γ×Uj（3）其中，α、β、γ為3個(gè)參數(shù)的權(quán)重值，它們滿足下式：α+β+γ=1

0<α，β，γ<1（4）2.2動(dòng)態(tài)調(diào)度模型構(gòu)建

一個(gè)網(wǎng)格系統(tǒng)中要進(jìn)行動(dòng)態(tài)的任務(wù)調(diào)度，首先要設(shè)計(jì)一個(gè)任務(wù)調(diào)度池，記為S。接著，要明確模型所解決的問題，即：一個(gè)網(wǎng)格系統(tǒng)G擁有多個(gè)網(wǎng)格資源節(jié)點(diǎn)，以及多個(gè)需要其解決和處理的任務(wù)?，F(xiàn)在需要將這多個(gè)任務(wù)分配到多個(gè)網(wǎng)格內(nèi)的資源節(jié)點(diǎn)上，每個(gè)任務(wù)可以分配給多個(gè)節(jié)點(diǎn)協(xié)同處理。期望完成的效果是：將任務(wù)分配給多個(gè)節(jié)點(diǎn)，盡可能提高每個(gè)節(jié)點(diǎn)的處理效率，使任務(wù)的調(diào)度和完成效率能夠達(dá)到令人滿意的效果[4]。

對(duì)此多對(duì)象的異構(gòu)問題進(jìn)行分析并用數(shù)學(xué)語言進(jìn)行描述，即為：已知網(wǎng)格G中擁有任務(wù)數(shù)n個(gè)，計(jì)為ai；此網(wǎng)格資源節(jié)點(diǎn)集計(jì)為A；網(wǎng)格G中擁有網(wǎng)格資源節(jié)點(diǎn)m個(gè)，計(jì)為pj?，F(xiàn)將網(wǎng)格系統(tǒng)中有關(guān)任務(wù)調(diào)度效率的幾個(gè)關(guān)鍵因素分別進(jìn)行設(shè)置。

在網(wǎng)格系統(tǒng)上的任務(wù)調(diào)度過程中，任務(wù)ai在節(jié)點(diǎn)pj上的各項(xiàng)指標(biāo)為：①網(wǎng)格任務(wù)調(diào)度長(zhǎng)度L；②網(wǎng)格任務(wù)調(diào)度所得的網(wǎng)格節(jié)點(diǎn)性能值E；③節(jié)點(diǎn)調(diào)度代價(jià)C。 此外，對(duì)于文中涉及的各個(gè)變量腳標(biāo)max與min，分別代表其相應(yīng)的最大、最小值。這幾個(gè)關(guān)鍵因素對(duì)應(yīng)的多對(duì)象約束函數(shù)如下：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的取值為：當(dāng)任務(wù)ai在節(jié)點(diǎn)pj上的運(yùn)行時(shí)間tij>0時(shí)，λij=1； 否則，λij=0。Lij=fj+gij+tij（8）其中，fj為網(wǎng)格系統(tǒng)節(jié)點(diǎn)pj的可用時(shí)長(zhǎng)，gij為節(jié)點(diǎn)間的通信耗時(shí)，tij為節(jié)點(diǎn)的任務(wù)執(zhí)行時(shí)長(zhǎng)。因此，求解目標(biāo)問題的多對(duì)象約束，即可歸納成上述約束方程組。

該多對(duì)象問題在求解時(shí)難以達(dá)到全局最優(yōu)，為保證得出全局最優(yōu)解，要將問題改進(jìn)成一個(gè)單一對(duì)象問題，即要引入上文生成的網(wǎng)格節(jié)點(diǎn)性能評(píng)估函數(shù)Ej。

在遺傳算法的種群調(diào)度過程中，根據(jù)網(wǎng)格節(jié)點(diǎn)性能評(píng)估函數(shù)，將以上3項(xiàng)性能指標(biāo)參數(shù)進(jìn)行改進(jìn)。任務(wù)ai在節(jié)點(diǎn)pj上的各項(xiàng)指標(biāo)為：①網(wǎng)格任務(wù)調(diào)度長(zhǎng)度LM；②網(wǎng)格任務(wù)調(diào)度所得的網(wǎng)格節(jié)點(diǎn)性能值Ej；③節(jié)點(diǎn)調(diào)度代價(jià)CM。

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

CMij=λij-Cminλij（10）于是最初確定的需解決的目標(biāo)問題，多對(duì)象網(wǎng)格任務(wù)調(diào)度模型即可轉(zhuǎn)化為一個(gè)單一對(duì)象問題，得到目標(biāo)方程為：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）。此時(shí)，當(dāng)用戶具有特殊節(jié)點(diǎn)性能偏好或具體任務(wù)在某些性能上有特殊要求時(shí)，只需通過調(diào)整權(quán)值ω1、ω2、ω3，即可滿足用戶的定制需求。

3算法改進(jìn)

3.1算法原型

目標(biāo)問題為異構(gòu)網(wǎng)絡(luò)環(huán)境下的任務(wù)調(diào)度，因此需要考慮網(wǎng)格環(huán)境中每一個(gè)節(jié)點(diǎn)的性能和鏈路狀態(tài)，以及它的歷史供求關(guān)系，以此判斷節(jié)點(diǎn)的目前狀況。這些可以用節(jié)點(diǎn)的各項(xiàng)性能參數(shù)來表示[5]。

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

3.2雜交算子優(yōu)化

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

在改進(jìn)遺傳算法中，筆者對(duì)作為最主要搜索算子的雜交算子進(jìn)行改進(jìn)，改進(jìn)后的雜交算子意在增加算法的搜索廣度，具體實(shí)現(xiàn)方法為：在雜交過程中，對(duì)父代中兩個(gè)個(gè)體對(duì)應(yīng)位上的值相加后采用模運(yùn)算求余，從而得到子代個(gè)體[8]。

3.3變異算子優(yōu)化

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

此改進(jìn)變異算子不僅簡(jiǎn)單易行，又可對(duì)個(gè)體生成產(chǎn)生擾動(dòng)，增加了種群多樣性，有助于避免改進(jìn)遺傳算法所得解陷入局部最優(yōu)，這一點(diǎn)可以通過改進(jìn)遺傳算法的收斂性來證明。

4結(jié)語

在網(wǎng)格的異構(gòu)環(huán)境中，任務(wù)調(diào)度是一個(gè)受多方因素影響、多對(duì)象約束的NP完全問題。本文為實(shí)現(xiàn)求得全局最優(yōu)解的目標(biāo)，提出了一個(gè)用來調(diào)節(jié)網(wǎng)絡(luò)節(jié)點(diǎn)性能的評(píng)估函數(shù)，并構(gòu)建了一個(gè)任務(wù)動(dòng)態(tài)調(diào)度模型，將多對(duì)象約束問題轉(zhuǎn)化為單一對(duì)象問題。同時(shí)，對(duì)傳統(tǒng)遺傳算法的雜交算子和變異算子進(jìn)行改進(jìn)，從而擴(kuò)充了算法的搜索廣度，實(shí)現(xiàn)了網(wǎng)格任務(wù)的動(dòng)態(tài)調(diào)度，并且求得全局最優(yōu)解，提高了任務(wù)執(zhí)行效率和資源利用率。

參考文獻(xiàn)參考文獻(xiàn)：

[1]桂小林.網(wǎng)格技術(shù)導(dǎo)論[M].北京：北京郵電大學(xué)出版社，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]劉麗，楊揚(yáng).基于QoS的社區(qū)公共服務(wù)網(wǎng)格資源調(diào)度[J].北京科技大學(xué)學(xué)報(bào)，2004，26（5）：560563.

[7]方勇，劉嘉勇.信息系統(tǒng)安全導(dǎo)論[M].北京：電子工業(yè)出版社，2003：7895.

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

[9]陳琛，洪流，陳學(xué)廣，等.基于網(wǎng)格的遺傳算法及其在公交運(yùn)行計(jì)劃編制中的應(yīng)用研究[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（12）： 23822388.

責(zé)任編輯（責(zé)任編輯：黃健）