云計算任務(wù)調(diào)度雙精英種群文化基因改進(jìn)算法?

楊春花 劉 娟

（烏魯木齊職業(yè)大學(xué)信息工程學(xué)院 烏魯木齊 832000）

1 引言

云計算是一種通過虛擬化技術(shù)將所需要的各種資源以任務(wù)的形式整合在虛擬資源池上，以便于使用者能夠根據(jù)自身需求來獲取相應(yīng)的服務(wù)［1］。云計算環(huán)境中存在著諸多不同類型的計算任務(wù)，基于某種需求，若任務(wù)調(diào)度不夠優(yōu)化，會浪費整體的計算時間并且降低資源利用率。云計算資源調(diào)度問題的核心內(nèi)容在于如何有效運用資源，提高云計算的計算效率，縮短計算時間。云計算任務(wù)調(diào)度需要同時兼顧計算效率和資源利用率。顯然，這兩個優(yōu)化目標(biāo)之間存在著一定的矛盾性，會增加問題優(yōu)化的難度。此外，云計算在實際的計算過程中，不僅能處理計算任務(wù)規(guī)模較小的優(yōu)化任務(wù)，同時，也應(yīng)針對任務(wù)量較大的優(yōu)化任務(wù)，具有較高的運算能力和求解效率。但云計算通常隨任務(wù)量的增加，難度成幾何倍增長。由此可知，現(xiàn)實中的云計算任務(wù)調(diào)度問題極難求得令人滿意的解。

針對上述問題，國內(nèi)外的研究學(xué)者提出了不同方式的云計算資源調(diào)度算法，其中占主流的方式為通過智能優(yōu)化算法對云計算資源調(diào)度模型進(jìn)行優(yōu)化，在提高計算速度的同時，更加有效地節(jié)約計算所需資源。文獻(xiàn)［2］提出一種基于改進(jìn)粒子群算法的云計算資源調(diào)度策略，提高了云計算的計算速度。針對云計算中的任務(wù)調(diào)度問題，查英華［3］等提出了一種任務(wù)調(diào)度的增強蟻群算法。針對云計算環(huán)境下內(nèi)置任務(wù)調(diào)度方法的低效問題，申麗君［4］等提出一種基于改進(jìn)免疫進(jìn)化算法的任務(wù)調(diào)度算法。為提高基于人工智能算法在優(yōu)化云計算資源調(diào)度模式時，出現(xiàn)資源利用率低的問題，卓濤［5］等通過將隨機向量策略引入到人工蜂群算法中，提高算法的收斂精度。此外的求解方法還有布谷鳥搜索算法［6］、基于改進(jìn)慣性權(quán)重的粒子群算法［7］、模糊聚類算法［8］、蟻群優(yōu)化-蛙跳算法［9］和改進(jìn)貪婪算法［10］。上述優(yōu)化策略均是通過單一策略對人工智能算法進(jìn)行改進(jìn)，在優(yōu)化具有任務(wù)量較大的云計算任務(wù)時，算法的優(yōu)化精度并不高，難以平衡資源利用率和計算時間。

針對上述問題以及云計算資源調(diào)度模型的特點可知，采用傳統(tǒng)的人工智能算法難以求得最優(yōu)解。同時，針對具有單一改進(jìn)策略的人工智能算法而言，改進(jìn)后的算法往往難以平衡算法的全局搜索能力和局部勘探能力，導(dǎo)致算法在迭代后期早熟收斂。針對此問題，本文基于兼顧考慮計算時間成本和資源花費成本的云資源任務(wù)調(diào)度優(yōu)化模型，提出了一種云計算任務(wù)調(diào)度雙精英種群文化基因算法。為了驗證本文所提改進(jìn)算法的有效性和高效性，本文針對改進(jìn)算法進(jìn)行了測試函數(shù)對比試驗和實際算例的仿真對比實驗，試驗結(jié)果表明，本文提出的文化基因改進(jìn)算法具有更佳的算法性能。

2 云計算任務(wù)調(diào)度問題的優(yōu)化模型

云計算任務(wù)調(diào)度問題是一個多目標(biāo)的優(yōu)化調(diào)度問題。其中兩個優(yōu)化目標(biāo)分別為計算時間成本最小和資源花費成本最低［11］。云計算的計算過程中，需考慮在最短時間得到最優(yōu)結(jié)果，同時云計算任務(wù)調(diào)度需要兼顧考慮計算資源的合理配置，計算節(jié)點使用的不平衡程度能夠反映計算資源的配置情況。因此，將計算時間成本最小記為Tmax，資源花費成本最低記為Bdegree。具體的云計算資源調(diào)度優(yōu)化模型為

式（2）中，M={1 ，2，3…m}為任務(wù)集合，含m個不同的任務(wù)；N={1 ，2，3…n}為計算所需全部節(jié)點，其中節(jié)點個數(shù)為n；tij表示第i個任務(wù)在第j個計算節(jié)點上執(zhí)行所花費的時間成本；eij是決策變量，為第j個計算節(jié)點上執(zhí)行第i個任務(wù)，若是，則eij=1，否則，eij=0。

最大任務(wù)的執(zhí)行時間Tmax采用下述公式計算得到：

不平衡程度Bdegree的數(shù)學(xué)表達(dá)式如下所示：

式（3）中，enum={e1，num，e2，num，…，en，num}為節(jié)點幾何中n個不同節(jié)點執(zhí)行次數(shù)的集合，E(X)為集合X的方差。

上述優(yōu)化模型求得最優(yōu)需使得任務(wù)完成時間最短，即：

式中，cost為最短的任務(wù)完成時間。

3 改進(jìn)的文化基因算法

3.1 文化基因算法

文化基因算法是Pablo Moscat于1989年首次提出的一種模擬文化進(jìn)化的群智能算法［12］。它是一種基于種群的全局搜索與基于個體的局部啟發(fā)式搜索相結(jié)合的混合優(yōu)化算法，其與遺傳算法有著較大的類似。

為提升文化基因算法的優(yōu)化性能，本文提出了一種文化基因改進(jìn)算法，記為IMA（Improved Me?metic Algorithm）。通過混合全局搜索策略提高算法的全局搜索能力。通過引入模擬退火策略和爬山算法提高算法的局部開發(fā)能力。

3.2 粒子群算法

粒子群算法是模擬鳥群捕食的仿真優(yōu)化算法［13］。設(shè)種群規(guī)模為N，維數(shù)為D，第i個粒子的坐標(biāo)位置向量為，速度向量為，個體極值為，粒子群全局極值記為

基本粒子群群算法更新迭代計算公式如式（5）所述。

式中i=1，2，…，N，t為維度，d表示迭代次數(shù)，c1，c2為隨機權(quán)重，rand為0～1之間的實數(shù)。

3.3 遺傳粒子群算法

粒子群算法因其具有強大的全局搜索能力，故而適合于作為文化基因全局搜索的搜索算法。由粒子群算法的迭代計算公式可知，粒子群算法在求解過程中，全部的個體均受局部極值點的吸引，朝局部極值點的方向進(jìn)行移動，不利于其保持種群多樣性。相比于粒子群算法，遺傳算法在保持種群多樣性上有明顯的優(yōu)勢，遺傳算法在迭代過程中，通過交叉變異的方式，不斷生產(chǎn)新的個體，并不斷對種群中的全部個體進(jìn)行貪婪選擇，使得算法的迭代過程中，不會喪失種群多樣性。因此本文將遺傳進(jìn)化機制引入粒子群算法中。具體的遺傳粒子群算法的計算步驟如圖1所示。

圖1 遺傳粒子群全局搜索算法

3.4 雙精英種群進(jìn)化機制

由于進(jìn)化環(huán)境和初始種群都有一定的局限性，經(jīng)過相當(dāng)長時間以后，精英群體因其長期進(jìn)化而積累一定的自身優(yōu)勢，從而對整個種群形成了一定程度的“統(tǒng)治”。此時，整個種群就會顯現(xiàn)出進(jìn)化緩慢或停滯的不利狀態(tài)，這種狀態(tài)也被稱之為平衡狀態(tài)。為此，本文通過雙精英種群策略對其進(jìn)行改進(jìn)。雙精英種群進(jìn)化機制是一種并行機制，它使兩個精英種群同時進(jìn)化，并在迭代過程中不斷進(jìn)行信息交互，將每次迭代所產(chǎn)生的最優(yōu)個體保存在其中一個種群中，將適應(yīng)度值較差的個體保存在另外一個種群中，從而跳出局部最優(yōu)［14］。具體的雙精英種群最優(yōu)粒子被交換的示意圖如圖2所示。

圖2 雙精英種群最優(yōu)粒子被交換的示意圖

雙精英種群文化基因算法進(jìn)化流程如下所述：

Step1：初始化文化基因種群，規(guī)模為m。

Step2：計算種群中全部個體的適應(yīng)度函數(shù)值。

Step3：對種群中全部個體按適應(yīng)度值大小進(jìn)行排序，求解到局部極值點和當(dāng)前全局極值點。

Step4：采用遺傳粒子群算法對整個種群進(jìn)行全局搜索。先將遺傳算法中的選擇、交叉、變異算子作用于整個種群的全部個體，然后將粒子群更新規(guī)則作用于整個種群的全部個體。

Step5：選擇種群中m個個體中的2N個精英個體以構(gòu)成兩個精英種群，分別記為精英種群1和精英種群2。

Step6：采用爬山算法和模擬退火算法對兩個精英種群進(jìn)行局部搜索。精英種群1采用爬山算法進(jìn)行進(jìn)化，精英種群2采用模擬退火算法進(jìn)行進(jìn)化。

Step7：分別計算兩個精英種群的各個精英的適應(yīng)度函數(shù)值。

Step8：兩個粒子群進(jìn)行信息交流，也即交換其最優(yōu)粒子。

Step9：判斷是否達(dá)到最大迭代次數(shù)，是則轉(zhuǎn)為Step10，否則轉(zhuǎn)為Step2。

Step10：將迭代計算的優(yōu)化結(jié)果輸出。

3.5 爬山算法和模擬退火算法

爬山算法是一類具有較強局部開發(fā)能力的人工智能優(yōu)化算法，算法在求解過程中，通常從當(dāng)前最優(yōu)解出發(fā)，通過嘗試改變當(dāng)前最優(yōu)解的位置尋求適應(yīng)度值更高的最優(yōu)解，并在迭代過程中不斷進(jìn)行貪婪選擇，直到達(dá)到最大迭代次數(shù)，輸出當(dāng)前求解的最優(yōu)解［15］。

模擬退火算法（SA）最早由Kirk-patrick等應(yīng)用于組合優(yōu)化領(lǐng)域。模擬退火算法基于金屬熱力學(xué)降溫過程，在這個降溫過程中不斷產(chǎn)生新解并根據(jù)Metrolips準(zhǔn)則來判斷是否接受該解，從而最終獲得更佳的優(yōu)化解。

爬山算法和模擬退火算法都是一種局部搜索能力很強的優(yōu)化算法，因而適合作為文化基因算法的局部搜索算法。

4 仿真實驗

4.1 基于測試函數(shù)的仿真對比

本文采用兩種不同的測試函數(shù)對本文提出的改進(jìn)的文化基因算法（IMA）、全局搜索采用粒子群算法且局部搜索采用模擬退火算法的普通文化基因算法（MA）和粒子群算法這三種不同的智能優(yōu)化算法進(jìn)行對比測試。以下是具體的測試結(jié)果。

1）De jong函數(shù)，極值點為0.0。De jong函數(shù)的數(shù)學(xué)表達(dá)式為

具體的De jong函數(shù)的仿真測試結(jié)果如圖3和表1所述。

圖3 采用De jong函數(shù)的仿真測試收斂曲線

表1 采用De jong函數(shù)的仿真測試結(jié)果

由圖3和表1可知，相比其他兩種算法而言，本文所提改進(jìn)文化基因算法（IMA）求解的結(jié)果最優(yōu)，尋優(yōu)得到的最優(yōu)解為(x1，x2)=（0.9961，0.9979）；最優(yōu)解函數(shù)值為F(x1，x2)=0.00034。

2）Schaffer函數(shù)，極值點為0.0。其數(shù)學(xué)表達(dá)式為

具體的Schaffer函數(shù)的仿真測試結(jié)果如圖4和表2所述。

圖4 采用Schaffer函數(shù)的仿真測試收斂曲線

表2 采用Schaffer函數(shù)的仿真測試結(jié)果

由圖4和表2可知，本文所提改進(jìn)文化基因算法（IMA）的求解結(jié)果同樣最優(yōu)，尋優(yōu)得到的最優(yōu)解為(x1，x2)=（3.7×10-4，5.9×10-4）；最優(yōu)解函數(shù)值為F(x1，x2)=7.0×10-4。

4.2 基于實際算例的仿真對比

本文采用云計算任務(wù)調(diào)度問題的實際算例對本文提出的改進(jìn)的文化基因算法（IMA）和普通文化基因算法（MA）這三種不同的粒子群算法進(jìn)行對比測試。本文選用的云計算任務(wù)調(diào)度問題的實際算例有4個計算節(jié)點和10個任務(wù)。以下是具體的測試結(jié)果。

表3 云計算任務(wù)調(diào)度問題的估算執(zhí)行時間表

具體的云計算任務(wù)調(diào)度問題的尋優(yōu)收斂曲線如表4圖5和圖6所述。

表4 云計算任務(wù)調(diào)度問題優(yōu)化的仿真測試結(jié)果

圖5 云計算任務(wù)調(diào)度問題最大任務(wù)完成時間的尋優(yōu)收斂曲線

由圖5和圖6可知，相比于其他算法，文化基因改進(jìn)算法（IMA）最優(yōu)，求解得到的任務(wù)執(zhí)行節(jié)點序列為e=[7 6 8 7...9，]估算的最大任務(wù)完成時間為174.7872。與此同時，粒子群改進(jìn)算法（IPSO）尋到的計算節(jié)點使用的不平衡程度最小，為0.4444，其任務(wù)執(zhí)行節(jié)點序列各個節(jié)點執(zhí)行次數(shù)的集合為

圖6 云計算任務(wù)調(diào)度問題計算節(jié)點使用的不平衡程度的尋優(yōu)收斂曲線

5 結(jié)語

本文基于云計算任務(wù)調(diào)度問題的優(yōu)化模型，提出了一種基于雙精英種群文化基因改進(jìn)算法。首先，在粒子群算法的基礎(chǔ)上，引入了遺傳進(jìn)化機制，以便于更好地維持種群多樣性，從而提升其全局搜索算法全局收斂的性能；其次，為一定程度地抑制文化基因算法陷入平衡狀態(tài)不易優(yōu)化的缺陷，本文通過雙種群精英策略對其進(jìn)行改進(jìn)，提高算法的局部開發(fā)能力，防止算法在迭代后期陷入局部最優(yōu)，早熟收斂。最優(yōu)，本文通過測試函數(shù)對比試驗和實際算例仿真實驗，以時間花費和資源花費為目標(biāo)函數(shù)，對本文所提改進(jìn)文化基因算法分別進(jìn)行驗證。從實驗結(jié)果可知，本文提出的文化基因改進(jìn)算法的尋優(yōu)性能更佳，能夠更有效地解決云計算任務(wù)調(diào)度問題。