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

楊春花 劉 娟

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3.1 文化基因算法

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

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

3.2 粒子群算法

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

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

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

3.3 遺傳粒子群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

表1 采用De jong函數(shù)的仿真測(cè)試結(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ù)，極值點(diǎn)為0.0。其數(shù)學(xué)表達(dá)式為

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

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

表2 采用Schaffer函數(shù)的仿真測(cè)試結(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 基于實(shí)際算例的仿真對(duì)比

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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