遺傳算法在云計算任務調(diào)度算法中的應用研究

鄭愛媛

(福建商業(yè)高等?？茖W校 信息管理工程系，福州 350012)

?

遺傳算法在云計算任務調(diào)度算法中的應用研究

鄭愛媛

(福建商業(yè)高等?？茖W校 信息管理工程系，福州 350012)

摘要：介紹云計算技術，分析了云計算環(huán)境下任務調(diào)度情況，給出了云計算任務調(diào)度中基于用戶滿意度的遺傳算法詳細設計，該詳細設計中重點敘述了編碼、適應度函數(shù)設計、交叉等遺傳算法實現(xiàn)的主要過程.

關鍵詞：遺傳算法；云計算；任務調(diào)度

隨著人們對仿生技術研究的深入，仿生技術的應用也越來越廣泛.遺傳算法的提出和應用就是仿生技術最經(jīng)典的應用之一，該算法強大的并行計算能力和智能優(yōu)勢深受人們的重視，很快被應用到極其復雜的系統(tǒng)任務調(diào)度配置中.由于云計算技術的技術特點，它的應用使人們處理系統(tǒng)資源調(diào)度的規(guī)模更加龐大.面對如此海量的資源調(diào)度任務信息，如何更好應用遺傳算法解決這一難題成了業(yè)界研究的一大熱點[1].本文重點研究了云計算環(huán)境下基于用戶滿意度約束的遺傳算法應用，并給出了詳細的算法實現(xiàn)過程.

1云計算技術

云計算技術可以定義為一種通過互聯(lián)網(wǎng)技術快捷地訪問共享資源的計算技術.利用云計算技術，人們可以根據(jù)業(yè)務量快速地申請和釋放共享資源，并對使用的共享資源支付費用，由此在提高資源服務質量的同時減低了成本.[2]

根據(jù)云計算技術的定義，將云計算技術特點歸納如下：

(1)租用資源：云計算為用戶提供網(wǎng)絡、存儲以及計算等基礎資源的租用服務，而且用戶不需維護這些網(wǎng)絡資源.

(2)資源共享技術：以資源共享的方式進行管理資源，通過虛擬化技術為不同的用戶分享資源，而且用戶可以自由管理和分配網(wǎng)絡資源.

(3)按需分配服務：為用戶提供資源存儲、計算以及應用程序等服務，并根據(jù)用戶的需求自動分配服務，不需要另外的管理進行干預.

(4)計費式服務：系統(tǒng)會監(jiān)控用戶的資源和服務使用量，然后進行量化收費.

(5)可變更服務：提供的服務會根據(jù)用戶的需要進行可變更處理，為用戶節(jié)約使用成本.

(6)接口通用化：用戶可以利用電腦、手機等終端設備方便地向云計算尋求服務.

2云計算環(huán)境下基于用戶滿意度約束的遺傳算法設計

在云計算環(huán)境下，任務調(diào)度情況通常這樣表示：資源總共為p，它所對應的集合R={r1,r2,…,rp}；而M表示用戶所上交的作業(yè)總數(shù)，與之對應的集合是J={J1,J2,…,JM}；一共被分成N個任務的M個作業(yè)所對應的集合為T={T1,T2,…,TN},可以把第Jm個作業(yè)分成為TNum(Jm)個任務,那么M個作業(yè)的任務總共為:

(1)

處理利用有限定的p個資源高效率的去實行N個相互之間依托并存的任務是目前云計算條件下任務調(diào)度的最大問題，并且要讓使用者在完成任務所用的時間、花費、占用的貸款以及可靠性等方面得到滿足.

2.1編碼

在討論任務調(diào)度這個問題上，現(xiàn)階段存在著非常多的編碼方式，間接和直接編碼是最為常用的兩種方式.染色體通常由兩部分組成，即調(diào)度子串和分配子串.分配子串就是指左半部分的子串，其主要是顯示分配任務的整個的資源狀況；調(diào)度子串是指右半部分的子串，其主要顯示的是任務調(diào)度的整體順序，色體的長度全部假設是總體任務數(shù)的兩倍，即2L.調(diào)度子串所照應的染色體的后L個基因，通過利用分配子串中的案例，進一步處置所獲得的染色體.把資源總數(shù)設為P，然后依據(jù)分配子串的編碼，讓分配給每一個資源的節(jié)點所照應的任務數(shù)量和任務ID順序信息，如表1所示.

表1　已經(jīng)處理過2次的染色體信息

由表1得出，它所對應的相對完善的染色體編碼：

(a)0 0 0 1 1 1 2 3 4 5,R1:1→2→3,R2:4→5

(b)0 0 0 1 1 3 1 2 4 5,R1:3→1→2,R2:4→5

(c)0 1 0 0 1 1 3 4 2 5,R1:1→3→4,R2:2→5

其中,(a)表示第3個、第1個任務以及第2個分配在了0編號的資源上，而它所實行的整體順序是1→2→3，第5個任務以及第4個任務被分配在了1號資源中，其執(zhí)行的順序是4→5.同理可得，(b)以及(c)染色體自身所攜帶的遺傳信息定義.

2.2初始種群生成

本文主要是運用隨機方式來形成初始種群.在這個初始種群生成的整個過程中，還要通過約束關系針對方案進行檢測，從而找到并且舍棄這些無效的方案[3].假設已經(jīng)完成了的任務是集合Sf，按照次序檢測每個資源上目前計劃實行的任務Ti，當Ti任務沒有依賴關系，或是依賴任務全部都在集合Sf中，Ti則是可以用的，執(zhí)行并且將Ti存放于集合Sf中.循環(huán)此過程，最后當全部的任務都能被執(zhí)行，那么這個方案就是有效的，反之就是無效的.

2.3適應度函數(shù)設計

遺傳算法進化的整體方向是由適應度函數(shù)所決定的，其還決定了群體中任一個體的優(yōu)勢和劣勢的程度.它的選擇對于遺傳算法的整體效率還是非常有用的.本文中用可靠性、貸款、完成時間、費用等四個目標，并與云計算的商業(yè)模型特征相結合，從而來衡量每一個用戶的滿意程度[4].另外，還運用了權重向量來針對用戶不同偏好程度進行衡量：

(2)

設Ai為完成任務Ti所用的的實際資源量,資源消耗量Ei是用戶所需要的，由此可得任務Ti用戶的滿意度函數(shù)是：

Wi=θln(Ai/Ei)，(0<θ≤1)

(3)

在用戶的希望資源消耗量Ei和其現(xiàn)實的消耗資源量越接近，用戶的滿意程度就越高，函數(shù)值就越趨近于0.當Wi>0，就表示用戶的期待資源的消耗量小于現(xiàn)實的消耗資源量；相反，當Wi<0，就表示用戶的期待資源的消耗量大于現(xiàn)實的消耗資源量.

(1)工作完成的時間

開始、工作總完成以及最遲完成的時間是用戶QoS時間的需求.時間需求評判的標準在本文是以工作所用的總的完成時間來衡量的.

假設N*P維ETC矩陣,在列表之中第j個資源上第i個任務的希望執(zhí)行的時間，那么Jm個工作的執(zhí)行的時間是：

(4)

那么M個工作所要的總時間是：

(5)

(2)帶寬

測量網(wǎng)絡使用狀況的重要指標就是網(wǎng)絡帶寬.網(wǎng)絡所具有的傳輸能力情況取決于帶寬大小，從而影響了在云環(huán)境下通訊的效率.帶寬的需求與頻率、通訊信息量成正比.

假設處于云計算環(huán)境的資源寬帶是Bwm,Buser代表用戶所指定作業(yè)Jm的需要帶寬，而作業(yè)Jm劃分的Ti任務的需要帶寬可以用Bi來代表，那么：

(6)

(3)可靠性

任務完成率代表了完成任務的可靠性.在云計算環(huán)境下，假設P是資源故障率(能從資源監(jiān)控系統(tǒng)來得到)，Psuc是用戶所需要的任務完成率.那么用戶對作業(yè)完成率的滿意度函數(shù)是：

Wsucc(Jm)=θln[(1-p)/psucc]

(7)

(4)費用約束

現(xiàn)階段最為盛行的QoS約束就包括費用約束，在云計算環(huán)境里，用戶QoS最為主要的組成因子之一就是費用，用戶們付費主要是根據(jù)自己需要的服務來付的.

若資源是按照單位來收費的，各資源數(shù)量設成Pi，Cmem、CBW、CCPU、Cstor分別代表內(nèi)存、帶寬資源的價格、CPU、存儲器，那么Ti任務的所有費用都可以這樣表示：

Ci=P1CCPU+P2Cmem+P3Cstor+P4CBW

(8)

(5)適應度函數(shù)

在云環(huán)境下，作業(yè)調(diào)度要顧及到上述的四個目標.針對用戶來講，其一，系統(tǒng)給作業(yè)的帶寬數(shù)值分配的越多越好，作業(yè)在運行的時候的完成率以及系統(tǒng)的穩(wěn)定性越高就越好.所以，作業(yè)調(diào)度的適用函數(shù)是：

f=-ω1WTime+ω2WBW-ω3Wcost+ω4Wsucc,(0≤ωi≤1)

(9)

其中，ωi(i=1,2,3,4)就是(2)式中所設置的權重系數(shù).

2.4選擇

提高比較好的染色體遺傳下一代的概率是當前選擇操作的真正目的.本文中，主要運用輪盤賭法來選取，把S設成種群規(guī)模，適應度fi的個體染色體選擇的Qi概率是：

(10)

2.5交叉

2.6變異

變異操作能夠保障在種群里的個體多樣性，文中對調(diào)度和分配子串運用了不相同的變異方式.

調(diào)度子串，文中主要運用的則是變異方式，即把產(chǎn)生變異的基因位數(shù)設置成整數(shù)值d來表示，而后任意抽取一變異點，針對以這個變異點為起點，緊跟著連續(xù)的d個基因位的基因值，可以運用排列組合方式生成一個新的個體,而在變異中生成的一些不符合任務之間相互約束的關系的新個體則會排除掉.

在變異后，如果把調(diào)度及分配子串歸并起來，便可以生成一個新個體.而后通過對變異后的新個體進行檢測，目的是檢測其是不是符合各任務之間相互約束的關系，如果檢測結果沒有滿足，便直接排除掉，隨后針對原來的個體需要再次變異操作，直到生成滿足約束關系的個體.[6]而針對變異概率Pm的選擇，文中主要運用了自適應方式.變異概率自適應調(diào)整公式是：

(11)

上式中，favg、fmax及f′分別代表種群平均適應度值、最大適應度值及要變異的個體適應度值，0

3結語

本文采用向量權重配置的方法把云計算調(diào)度任務中基于用戶滿意度考核指標：任務完成時間、占用帶寬、可靠性和費用應用到遺傳算法的適應度函數(shù)中,給出了云計算任務調(diào)度中基于用戶滿意度約束遺傳算法的詳細設計.利用云計算技術的優(yōu)勢,很大程度上提高了用戶對云服務的滿意度.

[參考文獻]

[1]蘇淑霞.面向云計算的任務調(diào)度算法研究[J].安徽大學學報(自然科學版),2014(9):24-27.

[2]蘇淑霞.粒子群算法在云計算任務調(diào)度中的應用[J].南京師范大學學報(自然科學版),2014(12):50-53.

[3]屈遲文.基于改進遺傳算法的云計算任務調(diào)度研究[J].世界科技研究與發(fā)展,2013(10):9-12.

[4]李英,黃國范.遺傳算法在云任務調(diào)度中的應用[J].洛陽師范學院學報,2013,25(5):14-18.

[5]李建鋒,彭艦.云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法[J].計算機應用,2011(6):81-84.

[6]鐘瀟柔,翟健宏.基于動態(tài)遺傳算法的云計算任務節(jié)能調(diào)度策略研究[J].智能計算機與應用,2014(1):58-67,112.

[責任編輯王新奇]

Application of the Genetic Algorithm in theCloud Computing Task Scheduling Algorithm

ZHENG Ai-yuan

( Department of information management, Fujian Commercial College, Fuzhou 350012, China )

Abstract：In this paper, the cloud computing technology is introduced, and the task scheduling in cloud computing environment is analyzed. A detailed design of the genetic algorithm based on user satisfaction in the cloud computing task scheduling is presented. In this design, the main process of the realization of the genetic algorithm, such as encoding, fitness function design, crossover, etc. are described in detail.

Key words：genetic algorithm; cloud computing; task scheduling

中圖分類號：TP393

文獻標志碼：A

作者簡介：鄭愛媛(1977—)，女，福建福州人，福建商業(yè)高等專科學校信息管理工程系講師，碩士，主要從事計算機軟件研究.

收稿日期：2015-10-08

文章編號：1008-5564(2016)01-0023-04 1008-5564(2016)01-0027-04