云計算任務調度雙精英種群文化基因改進算法?

楊春花 劉 娟

（烏魯木齊職業大學信息工程學院 烏魯木齊 832000）

1 引言

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

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

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

2 云計算任務調度問題的優化模型

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

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

最大任務的執行時間Tmax采用下述公式計算得到：

不平衡程度Bdegree的數學表達式如下所示：

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

上述優化模型求得最優需使得任務完成時間最短，即：

式中，cost為最短的任務完成時間。

3 改進的文化基因算法

3.1 文化基因算法

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

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

3.2 粒子群算法

粒子群算法是模擬鳥群捕食的仿真優化算法［13］。設種群規模為N，維數為D，第i個粒子的坐標位置向量為，速度向量為，個體極值為，粒子群全局極值記為

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

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

3.3 遺傳粒子群算法

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

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

3.4 雙精英種群進化機制

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

圖2 雙精英種群最優粒子被交換的示意圖

雙精英種群文化基因算法進化流程如下所述：

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

Step2：計算種群中全部個體的適應度函數值。

Step3：對種群中全部個體按適應度值大小進行排序，求解到局部極值點和當前全局極值點。

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

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

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

Step7：分別計算兩個精英種群的各個精英的適應度函數值。

Step8：兩個粒子群進行信息交流，也即交換其最優粒子。

Step9：判斷是否達到最大迭代次數，是則轉為Step10，否則轉為Step2。

Step10：將迭代計算的優化結果輸出。

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

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

模擬退火算法（SA）最早由Kirk-patrick等應用于組合優化領域。模擬退火算法基于金屬熱力學降溫過程，在這個降溫過程中不斷產生新解并根據Metrolips準則來判斷是否接受該解，從而最終獲得更佳的優化解。

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

4 仿真實驗

4.1 基于測試函數的仿真對比

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

1）De jong函數，極值點為0.0。De jong函數的數學表達式為

具體的De jong函數的仿真測試結果如圖3和表1所述。

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

表1 采用De jong函數的仿真測試結果

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

2）Schaffer函數，極值點為0.0。其數學表達式為

具體的Schaffer函數的仿真測試結果如圖4和表2所述。

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

表2 采用Schaffer函數的仿真測試結果

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

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

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

表3 云計算任務調度問題的估算執行時間表

具體的云計算任務調度問題的尋優收斂曲線如表4圖5和圖6所述。

表4 云計算任務調度問題優化的仿真測試結果

圖5 云計算任務調度問題最大任務完成時間的尋優收斂曲線

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

圖6 云計算任務調度問題計算節點使用的不平衡程度的尋優收斂曲線

5 結語

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