基于差分進化人工蜂群算法的云計算資源調度

李志敏，張 偉

(1.無錫工藝職業技術學院 電子信息系，江蘇 無錫 214000；2.江南大學 物聯網學院，江蘇 無錫 214000)

0 引 言

云計算資源調度策略[1]包括先進先出調度算法、計算能力調度算法、公平調度算法、智能調度算法等[2]。先進先出就是簡單的排隊策略，計算能力調度策略是在先進先出基礎上，參考隊列資源饑餓程度再次分配，公平調度算法以用戶為單位進行資源分配，以用戶提交的任務量為權重分配計算資源，有效避免了不必要等待時間；智能調度算法是使用智能控制算法對云計算資源的調度，通過算法尋求計算資源的最優配置，達到某一最優目標，比如能耗最優、總體時間最優、等待時間最優、負載平衡等。

本文引入高斯變異和自適應因子對人工蜂群算法進行改進，引入自適應交叉概率對差分進化算法進行改進，而后將兩改進算法進行結合提出了差分進化人工蜂群算法，使兩改進算法并行尋優，并及時交流最優解及位置信息，最終提高了最優解精度、減少了算法迭代次數和收斂時間。

1 改進人工蜂群算法

人工蜂群算法是模擬蜂群采蜜行為的群體智能算法，每個蜜源位置代表一個可行解，蜂群找到最優蜜源的速度代表算法的收斂速度，蜂群尋找最優蜜源的過程就是算法尋優的過程[3]。

1.1 人工蜂群算法原理

在人工蜂群算法中使用到的參數包括種群數量N、算法最大迭代次數maxCycle、蜜源停留最大次數Limit。

初始化蜜源，此時所有蜜蜂都是偵查蜂，尋找到N個蜜源，也就是隨機產生N個蜜源[4]

Xi(n)=Xmin+rand(0,1)(Xmax-Xmin)

(1)

式中：i=1,2,…,N，Xmax、Xmin分別為可行域的最大值和最小值，rand(0,1)為(0,1)間的隨機數。

對蜜源收益度進行評價。收益靠前的偵查蜂轉化為雇傭蜂，收益靠后的偵查蜂轉化為觀察蜂，評價函數為

(2)

觀察蜂根據雇傭蜂的搖擺舞得知各蜜源花粉濃度，根據蜜源花粉濃度進行選擇，蜜源花粉濃度越高則招募的觀察蜂越多，即

(3)

式中:pi為觀察蜂選擇某一蜜源的概率，SN為雇傭蜂數量。

雇傭蜂進行局部搜索。每只雇傭蜂在原蜜源附近搜索新蜜源，根據貪婪規則若搜尋的新蜜源適應度高于原蜜源，則原蜜源取代原蜜源[5]。位置更新方式為

new_xij=xij+φij(xij-xkj)

(4)

式中:new_xij為雇傭蜂搜尋到的新食物源，xij為當前食物源，xkj為隨機選取的異于當前食物源的另一食物源，φij為[-1,1]的隨機數。

觀察蜂按照花粉濃度成比例選擇蜜源后，在此蜜源附近搜索新蜜源，若新蜜源濃度大于原蜜源，則此觀察蜂轉化為雇傭蜂，開始招募觀察蜂，其位置更新方式與雇傭蜂一致。若觀察蜂和雇傭蜂在花源附近搜索Limit次以上時，仍未能找到更優蜜源，則放棄此蜜源而隨機產生一新蜜源，防止算法陷入局部最優[6]。

記錄當前蜂群找到的所有最優蜜源，再次進行蜜源收益度評價，直至算法循環次數大于maxCycle或者符合誤差要求，算法結束。

1.2 改進人工蜂群算法

1.2.1 引進高斯變異思想

引入高斯變異就是在算法完成一次迭代之后，對剩余的蜜源進行高斯變異，若變異后的蜜源適應度值高于原蜜源，則保留新蜜源，否則保留原蜜源。引入高斯變異，是為了使算法有更好的局部搜索能力，尤其是對于有大量局部極小值的問題，可以使算法快速收斂到全局最小值點。高斯變異方法為

mutation(x)=x×(1+N(0,1))

(5)

式中：mutation(x)為高斯變異后蜜源位置，x為現在位置，N(0,1)為均值為0、方差為1的高斯分布隨機數。

1.2.2 引進自適應因子

由人工蜂群算法原理可以看出，φij對算法收斂速度和精度影響很大，算法前期較大的φij可以擴大算法搜索范圍進行全域搜素，避免陷入局部最優；算法后期較小的φij可以加強局部搜索能力進行局部細致搜索，提高搜索精度和收斂速度。

皮埃爾在研究人口增長時定義了Logistic曲線，此曲線包含兩個參數a、b，參數的變化可以調整算法平滑度，本文以此曲線定義自適應因子θk，使用此因子調節φij大小，即

(6)

式中：θk為自適應調節因子，且0<θk

2 改進差分進化算法

差分進化算法[7,8]是一種特殊的遺傳算法，使用差分方法進行變異和一對一的競爭生成策略，大大降低了遺傳算法復雜度。

2.1 差分進化算法

差分進化算法包括變異、交叉和選擇等操作[9]。變異操作為

vi,j=xbest,j+F*(xr1,j-xr2,j)

(7)

式中：xbest,j為當前種群中的最優個體，xr1,j、xr2,j為種群中的任意兩個個體，且i≠r1≠r2，F∈(0,1)控制個體變異程度。

將變異得到的個體與父代進行交叉操作，為

(8)

式中：CR是交叉概率，為(0,1)間的一個定值。

選擇操作就是優勝劣汰的過程，將變異交叉后的個體與父代進行比較，保留適應度強的個體，即

(9)

式中：xi+1為下一代選擇的個體，xi為父代個體，vi為變異交叉得到的個體，f()為適應度函數。

2.2 改進差分進化算法

在差分進化算法中，交叉概率CR對基因多樣性、算法搜索能力、算法收斂速度影響很大，因此本文引入了自適應交叉概率，使CR隨著算法的搜素不斷減小，既保證前期基因的多樣性，也保證后期搜索的細致性和速度。經研究，交叉概率CR在0.4到0.9之間[10]，因此本文提出的自適應交叉概率為

(10)

式中：k為算法迭代次數，K為算法最大循環次數。

3 差分進化人工蜂群算法

當對算法的優化和改進遇到瓶頸時，可以考慮將兩者智能算法進行結合，使兩者智能算法優勢互補，基于這一思想本文提出了差分進化人工蜂群算法，將改進的人工蜂群算法和改進差分進化算法進行結合?？紤]到兩算法解的編碼方式可以進行統一，因此采用雙種群并行尋優，尋優過程中兩算法進行最優解和位置共享，從而提高算法收斂速度和精度。

引入參數D，當兩算法均尋優D次后，兩算法交換最優解和最優解位置，各自以自身算法的適應度值對兩個最優解進行評價，保留最優解進行尋優。參數D的選擇對算法性能影響很大，若D較小時兩算法會區域一致，失去了并行尋優的意義，若D較大則兩算法交流較少，所有D的選取要根據實驗確定。

經過以上分析，給出差分進化人工蜂群算法的流程如圖1所示。

圖1 差分進化人工蜂群算法流程

4 實驗驗證

4.1 實驗設計

本文的實驗環境使用虛擬化軟件VMware Workstation建立11個節點，選擇其中某一節點作為主節點用于計算資源調度，其余10個節點用于數據的處理和存儲。本文共設計了4組實驗：

實驗一：比較人工蜂群算法與改進人工蜂群算法的云計算時間。任務個數分別為10、30、50、70、100、150，任務大小均為512 MB，分別使用傳統人工蜂群算法和改進算法進行計算資源調度，比較云計算時間。

實驗二：比較差分進化算法與改進差分進化算法的云計算時間。任務個數分別為10、30、50、70、100、150，任務大小均為512 MB，分別使用傳統差分進化算法和改進算法進行計算資源調度，比較云計算時間。

實驗三：D值的選取。將任務數分別設置為30、70、150，任務大小均為512 MB，設定D值變化范圍為[5,50]，通過觀察云計算時間隨D值的變化趨勢來確定D值。

實驗四：比較改進差分進化算法、改進人工蜂群算法、差分進化人工蜂群算法的云計算時間。任務個數分別為10、30、50、70、100、150，每個任務大小均為512 MB，分別使用3種算法進行計算資源調度，比較云計算時間。

4.2 數據處理及結論分析

實驗一：人工蜂群算法和改進人工蜂群算法的調度運算時間如圖2所示。

圖2 人工蜂群算法和改進算法調度時間比較

從圖2中可以看出，當任務數量較少時，傳統算法與改進算法調度的云計算時間相差不大，但是當任務數量增大后，兩算法的云計算時間相差較大，這是因為改進算法通過引進高斯變異和自適應因子使算法具有全局尋優能力和局部細致搜索能力，使主節點能夠找到更優的計算資源分配方式，減少云計算時間。

實驗二：差分進化算法和改進差分進化算法的調度運算時間如圖3所示。

圖3 差分進化算法和改進算法調度時間比較

從圖3中可以看出，任務數量在10到30之間時，由于任務數量少使得計算資源壓力小，所以改進算法與傳統算法調度的云計算時間大體一致，但是當任務數量超過30，也就是任務數量較大時，改進算法調度的云計算時間明顯少于傳統算法，這是因為自適應交叉概率在算法前期保留了基因多樣性，使得算法更能夠找到最優解。

實驗三：任務數分別設置為30、70、150，則差分進化人工蜂群算法調度的云計算時間隨D值變化的曲線如圖4所示。

圖4 云計算時間隨D值變化曲線

從圖4中可以看出，當任務數量少時，D值大小對云計算時間影響不大，這是因為任務數量少，計算資源壓力小。當任務數量大時，云計算時間隨著D值變化先減少后增多，因為D值較小會使兩算法尋優過程趨于一致，失去并行尋優意義，D值較大又會使并行尋優缺少交流而各行其是，所以適當的D值使兩算法尋優時能夠及時交流最優解和位置，實現信息共享和交互學習提高。從圖中可以看出D取為15時云計算時間最少。

實驗四：改進人工蜂群算法、改進差分進化算法和差分進化人工蜂群算法的調度運算時間如圖5所示。

圖5 3種算法調度時間比較

從圖5中可以看出，隨著任務量的增加，3種算法調度的云計算時間相差越來越大，這是因為兩種智能算法并行尋優過程中能夠及時交換最優解及位置信息，使兩算法能夠快速靠近最優位置，達到了強強聯合的效果，有效提升了算法性能。最優解及位置的共享使得算法迭代次數和收斂速度大大加快。

5 結束語

本文以云計算時間最少為優化目標，在對人工蜂群算法和差分進化算法改進的基礎上，提出了差分進化人工蜂群算法的云計算資源調度方法。得到了以下結論：

(1)通過引入高斯變異和自適應因子，使得人工蜂群算法能夠兼顧前期全局搜索、后期局部細致搜索和算法收斂速度，提高了解的搜索精度；

(2)通過引入自適應交叉概率，保持了算法前期的基因多樣性，使算法在更多可行解中選擇最優解，使算法找到的最優解明顯優于傳統算法；

(3)在差分進化人工蜂群算法中，D值的選取對算法性能影響很大，D值過小會使并行優化趨于一致，失去并行優化意義，D值過大則兩算法無法及時進行信息共享；

(4)差分進化人工蜂群算法使改進差分進化算法和改進人工蜂群算法并行尋優，并及時交流最優解和位置信息，使兩算法能快速靠近最優解，減少了算法循環次數和收斂時間，同時最優解精度也明顯優于其它算法。