基于自適應交叉變異的飛蛾算法云計算任務調度策略

李宏偉

摘 要：針對云計算資源調度效率低的問題，提出一種基于自適應交叉變異的飛蛾優化算法云資源調度策略.首先引入綜合學習策略，對飛蛾種群進行初始化，提高全局搜索能力.其次在迭代過程中加入自適應交叉變異策略，加強粒子跳出局部最優的概率.最后建立云計算任務調度問題的數學模型，將改進后的飛蛾算法對模型進行求解，并將實驗結果與其他優化策略的實驗結果在時間花費和能源花費中進行對比，取得了較優的結果.

關鍵詞：飛蛾優化算法;云計算;資源調度;自適應交叉變異;綜合學習

中圖分類號：TP18? 文獻標識碼：A? 文章編號：1673-260X（2020）01-0026-06

云計算是一類集成網絡計算與虛擬技術的新型計算模式，可以針對具有大數據量的計算問題進行處理[1].由于云計算模型復雜度較高且具有較強的非線性，因此可歸為NP-Hard問題[2].在云計算的計算過程中，云計算中的資源調度通常呈動態特性，調度難以合理化[3]，并且云計算在運算過程中，每個節點的工作方式互異，處理的數據量大小也各不相同，導致云計算經常出現資源利用率不平衡的問題，很大程度影響了云服務的質量[4].因此，提高云計算效率的關鍵問題是如何合理對云資源進行調度.為了提高云計算的資源利用率，國內外許多學者展開了深入研究.

趙宏偉等提出一種改進細菌覓食的云計算資源調度策略，通過細菌算法對資源調度節點進行復制和消亡，調高資源利用率[5].羅云等提出一種改進粒子群算法的云資源調度策略[6]，通過混沌隨機數擾動策略加強了粒子群算法的全局收斂能力，減少任務完成時間，提高了云計算效率.任神河等將直覺模糊時間序列預測用于平衡云計算網絡動態負載[7]，很大程度提升了云計算的運算效率.李佳等提出一種基于布谷鳥算法的云資源調度策略[8]，降低了時間消耗成本和能源消耗成本，提高云計算資源的利用率.王欣欣等提出一種基于雙適應度動態遺傳算法的優化策略[9]，提出代價函數用于輔助權值的分配，提高了算法的尋優精度.在尋優策略中將能源消耗和時間消耗歸為一個目標函數，并將改進后的算法對其求解，很大程度地提高了云計算效率.Yuan H等提出一種基于改進粒子群算法的云計算資源優化調度策略[10].Liu J等提出一種基于博弈優化模型的資源優化調度策略[11].以上策略在一定程度上提高了云資源的利用率，但單一機制的優化算法在處理維數較高的問題上，卻存在一定缺陷，使得云計算在處理大規模任務量時，利用率仍不高，因此本文提出一種基于自適應交叉變異的飛蛾優化算法，求解云計算資源調度問題.

飛蛾優化算法的優點在于，算法尋優機制簡單，易于實現，相對其他優化算法而言，算法控制參數較少，易于調節.但缺點在于算法全局搜索能力較差，易早熟收斂，陷入局部最優.因此本文針對以上缺陷通過引入綜合學習策略和自適應交叉變異策略對算法進行改進，提高算法的全局收斂能力和求解高維問題的能力.并將改進后的飛蛾算法用于求解云計算資源調度問題.

1 云計算資源調度模型

云計算任務調度模型是一類具有多約束條件的非線性數學模型，目的是將m個獨立任務合理分配給服務器n個可利用資源，降低云服務器執行任務的時間和能源消耗.因此在建立云計算任務調度模型時，主要考慮時間消耗和能源消耗最小化的問題.

1.1 時間消耗

時間消耗是指任務提交到任務完成，并將調度完成后的結果反饋給用戶的時間間隔.在計算過程中，各獨立任務均為并行執行，因此，假設在m個獨立任務中，第k個任務完成時間最長，則將第k個任務的完成時間定義為云計算任務調度的時間消耗.其數學表達式如下所示：

式中，Timer為云計算任務調度的時間消耗，timei，j=TLi/Cpuj，表示第i個任務在第rj個資源節點的運算時間，j=[1，2，K，n]，n為服務器的資源數量.i=[1，2，L，m]，m為任務總數，Cpuj為虛擬機處理能力，TLi為第i個任務的長度.pi，j為任務執行判定條件，若pi，j=1則表示計算任務i在第rj個資源節點上執行，否則該任務不執行.

1.2 執行能耗

在n個務器資源中，每一個虛擬資源在完成任務后均會因處理數據而產生能量的消耗，這種消耗定義為執行能耗.因此可通過式（2）計算執行完m個獨立任務后計算機產生的總執行能耗.其數學表達式如下所示：

式中，ei，j為第i個任務在第j個資源節點上產生的執行能耗.

因此，考慮時間消耗和能源消耗最小化的云計算任務調度模型的目標函數為：

minf（x）=？姿1*Timer（x）+？姿2*JC（x）? （3）

式中，？姿1和？姿2為時間消耗和執行能耗的慣性權重，且？姿1+？姿2=1，？姿1>0，？姿2>0.

2 飛蛾優化算法的改進策略

2.1 基本飛蛾火焰優化算法

飛蛾火焰優化算法[12]（Moth-flame Optimization Algorithm， MFO）是Mirjalili S.于2015年提出的一種以飛蛾撲焰行為為基礎的智能優化算法.設MFO算法的種群為M：

M=[m1，m2，L，mn]T? （4）

式中，mi=[mi，1，mi，2，L，mi，d]T;n為飛蛾數量;d為維數.由于飛蛾個體適應度值均儲存于矩陣OM中，因此定義：

OM=[OM1，OM2，L，OMn]T? （5）

在飛蛾火焰優化算法中，火焰被描述為算法當前迭代所得最佳位置，因此設最優位置矩陣為F，其適應度值存放于矩陣OF之中.

F=[f1，f2，L，fn]T? （6）

OF=[OF1，OF2，L，OFn]T? （7）

式中fi=[fi，1，fi，2，L，fi，n]T.在飛蛾優化算法中，飛蛾通過一種類似橫向定位機制進行導航.因此飛蛾會在火焰附近進行更新，直到搜索到最佳方案，這種行為可以被描述為捕焰行為和棄焰行為.首先飛蛾Mi會以一種對數螺線的方式朝向距自身最近的火焰Fj移動：

S（Mi，Fj）=Di*ebt*cos（2？仔t）+Fj? （8）

式中，S（Mi，Fj）為更新后的飛蛾位置;b為參數，決定螺旋形狀;t為[-1，1]之間的隨機數;通常當t→1時，表示飛蛾離火焰距離最遠，當t→-1時，表示飛蛾距火焰距離最近;Di=|Fj-Mi|為飛蛾距火焰之間的距離;其次，在MFO算法中，火焰數量會自適應減少，直到找到一個最優的火焰位置，這個減少過程被描述為棄焰行為：

flame=round（N-t*（N-1）/Tmax）? （9）

式中，t為算法當前迭代次數;Tmax為最大迭代次數;N為最大火焰數量.

2.2 自適應交叉變異的飛蛾火焰優化算法（Adaptive Cross-mutation Moth Optimization Algorithm， ACMOA）

首先，飛蛾優化算法在種群初始化階段，搜索范圍完全依賴隨機性，難以保證全局最優解一定在搜索范圍內，以致算法最終找到的全局最優解的精度不高，甚至導致算法早熟收斂陷入局部最優.根據研究表明，初始種群的位置在很大程度會影響算法的尋優精度，因此針對上述問題，本文利用綜合學習策略對飛蛾優化算法進行種群初始化.ACMOA的種群位置初始化過程表述如下：

1）首先對飛蛾種群進行隨機初始化操作：M（t=0）={mij}，i=1，2，…，NP，j=1，2，…，ND;

2）計算反向飛蛾種群M′（t=0）={m′ij};其中：mmax，j表示種群mi第j維元素最大值，mmin，j表示種群mi第j維元素最小值.

3）從種群{M（t=0）∪M′（t=0）}中選擇NP個適應度值較小的蜂群位置作為ACMOA算法的最終初始種群.

通過綜合學習策略對飛蛾粒子的初始位置進行初始化，有效地保證了解的質量，豐富了種群多樣性，提高了算法搜索到全局最優解的概率，提高了算法的收斂精度.

其次，算法在迭代過程中，會出現陷入局部最優早熟收斂的情況，這是由于在算法迭代后期，粒子始終會圍繞當前適應度較高的粒子進行局部搜索，導致算法難以跳出最優解的吸引，早熟收斂.傳統的交叉變異策略使得種群中全部粒子獲得的變異概率相同，但根據實驗表明，適應度值較高的粒子因變異產生的新的粒子，新粒子的適應度值并不一定優于變異前的粒子.因此本文引用一種自適應的概念，根據粒子當前適應度值的大小自適應獲得交叉變異概率.該策略以反正切函數y=arctan（x）為基礎，使得適應度值較低的粒子過得較大的交叉變異概率，適應度值較高的粒子，獲得較小的交叉變異概率.ACMOA算法的自適應交叉變異公式如下所示.其中交叉概率記為pc，變異概率記為pm.

式中，pcmax為交叉概率上限，pcmin為交叉概率的下限，根據大量實驗表明，pcmax=0.75，pcmin=0.36時算法的收斂最優.pmmax為變異概率的上限，pmmin為變異概率的下限，pmmax=0.85，pmmin=0.26時算法的收斂最優.favg為種群中全部粒子的平均適應度值.fmax為種群中全部粒子的最大適應度值.f為變異個體的適應度值.f′表示兩個進行交叉操作的個體中適應度值較大解.

ACMOA算法的尋優步驟如下所述：

Step1：初始化參數：即飛蛾種群規模大小NP，最大迭代次數tmax.交叉概率的最大值pcmax=0.75和最小值pcmin=0.36，變異概率的最大值pmmax=0.85和最小值pmmin=0.26.

Step2：在解空間內初始化飛蛾種群的位置，再利用反向學習算法產生反向種群.計算兩個種群中全部個體的適應度值，并進行排序，選擇NP個最優個體作為最終的初始化種群.

Step3：計算出NP個個體適應度值的大小，找出適應度值最小的個體位置作為最優位置.

Step4：依照式（8）和式（9）對飛蛾個體的位置進行更新計算.

Step5：依照式（10）和式（11）對粒子進行自適應交叉變異操作.

Step6：對更新后的粒子進行辯解處理.

Step7：判斷算法是否達到終止條件，既是否達到最大迭代次數.是，則輸出全局最優解.否，則返回返回Step3.

2.3 基于測試函數的性能測試

為驗證本文所提ACMOA算法的整體性能，首先選取12個基準測試函數做為評價函數，對ACMOA進行求解，記錄算法求解的平均值和標準差.12個基準測試函數如表1所示.

其次為了驗證ACMOA算法相較其他用于云計算資源調度的優化算法具有更高的搜索精度，本文將ACMOA算法的實驗結果分別與改進的雞群算法（ICSO）[13]、改進的蝙蝠算法（HS-BA）[14]和改進的蟻群算法（TCLB-EACO）[14]的實驗結果進行對比.其中f1至f4為單峰函數，f5至f8為多峰函數，維數分別設置為10、30和50，f9至f12為固定維函數.為了保證實驗的公平性，四種算法迭代次數均為100，種群規模均為50，四種算法對12個測試函數個獨立運行30次并記錄最佳結果.具體測試結果如表2所示，最優解加粗表示.

從表2中可得，對于單峰測試函數而言，首先，四種算法均可以收斂到全局最優解，但本文所提ACMOA算法所求解的平均值最小，說明ACMOA算法相較其他三種算法具有更高的收斂精度.其次，隨維度的增加，算法求解的復雜度增加，除ACMOA算法外，其他三種算法的收斂精度均大幅下降，且ACMOA算法求解的標準差更小，說明ACMOA算法的魯棒性要優于其他三種算法，算法的整體性能更優.

其次，對于多峰測試函數而言，ACMOA算法同樣可以取得更小的平均值和標準差.說明DPSSO算法相較其他四種算法而言，具有更高的全局搜索能力，搜索成功率也更高，算法穩定性更強.同樣，ACMOA算法在求解過程中，隨維度增加，雖然求解精度會適當降低，但依然遠優于其他三種算法.說明ACMOA算法適用于求解具有復雜非線性的問題.

最后，對于固定維函數而言，由于目標函數求解維數較少，使得四種算法的求解精度和算法穩定性均有所提高.但ACMOA算法的標準差較其他三種算法相比，可以求解到更小的值，說明ACMOA算法魯棒性更高.總體而言ACMOA算法克服了早熟收斂，陷入局部最優的問題，很大程度提高了算法整體性能和收斂精度.

3 仿真實驗及分析

本文將改進后的飛蛾優化算法優化云計算資源調度模型，其中仿真平臺為MATLAB 2014a，CPU為Inter Core i5-5200U，主頻為2.20 GHz.為了驗證ACMOA算法的實際調度能力，將本文所得實驗結果與ICSO算法、HS-BA算法和TCLB-EACO的實驗結果從時間花費和能耗花費兩個指標進行對比.

3.1 小規模任務性能對比

首先，本文在任務量較小的情況下，對四種算法進行對比驗證，具體實驗結果如圖1～圖2所示.

從圖1中可得，相較其他三種算法而言，ACMOA算法所用時間最短，說明ACMOA算法的收斂精度更高且收斂速度更快，算法在迭代后期，收斂速度不會出現減緩甚至停滯的現象.因此很大程度的縮短了云計算的計算時間，節約了時間成本.其次，在云計算過程中，隨任務量增加ACMOA算法求解時間沒有出現較大波動，說明ACMOA算法的全局收斂能力更強，搜索范圍更廣.

從圖2中可得，其他三種算法隨任務量的增加，能耗花費曲線波動較大，說明其他三種算法在能量消耗上的穩定性不高，但ACMOA算法在迭代過程中，曲線波動較為平緩，說明ACMOA算法在能量消耗穩定性上遠優于其他三種算法.此外，ACMOA算法的最大能耗僅為其他算法的50%～75%，說明ACMOA算法的能量消耗遠低于其他三種算法.因此，ACMOA算法較大程度地降低了計算資源調度的能耗花費，合理分配了任務資源.ACMOA算法在能耗花費方面要遠優于其他三種算法.

3.2 大規模任務性能對比

其次，本文在任務量較大的情況下，對四種算法進行對比驗證，具體實驗結果如圖3～圖4所示.

從圖3中可得，本文所提ACMOA算法的花費時間遠遠低于其他三種算法的花費時間，雖然隨任務量的增加，四種算法的花費時間均有明顯增加，但ACMOA算法受影響更小，曲線上升趨勢更加平穩.因此ACMOA算法在處理時間花費的問題上，優化結果遠優于其他三種算法，魯棒性更強.

圖4為四種算法的能量消耗對比圖，從圖中可得，本文所提ACMOA算法的能量消耗最低，并且隨任務量的增加，變化趨勢不大，穩定性遠優于其他三種算法，因此在求解大規模任務問題上，ACMOA算法的整體性能仍然更優.

4 結論

本文針對云計算資源調度不合理導致云計算效率低的問題，提出一種基于自適應交叉變異的飛蛾優化算法對其進行優化.首先針對傳統飛蛾優化算法收斂精度低，收斂速度慢，在迭代過程中易早熟收斂陷入局部最優的問題，通過綜合學習策略和自適應交叉變異策略對算法進行改進，豐富了算法的種群多樣性，提高了算法的全局搜索能力和算法跳出局部最優的能力，很大程度高了算法的整體優化性能.其次通過數值仿真實驗，驗證了所提算法具有較強的收斂能力.最優將改進后的算法用于云計算資源調度優化，實驗結果表明ACMOA算法在優化過程中取得了較好的結果，很大程度降低了云計算的時間成本和能耗成本，提高了云資源的調度效率.

參考文獻：

〔1〕林偉偉，齊德昱.云計算資源調度研究綜述[J].計算機科學，2012，39（10）：1-6.

〔2〕胡艷娟，朱非凡，王藝霖，石超，武理哲.云制造環境下的資源調度研究綜述[J].制造技術與機床，2018（03）：33-39.

〔3〕賈嘉，慕德俊.基于粒子群優化的云計算低能耗資源調度算法[J].西北工業大學學報，2018，36（02）：339-344.

〔4〕林偉偉，劉波，朱良昌，齊德昱.基于CSP的能耗高效云計算資源調度模型與算法[J].通信學報，2013，34（12）：33-41.

〔5〕趙宏偉，田力威.基于改進細菌覓食算法的云計算資源調度策略[J].計算機科學：1-10[2019-10-06].

〔6〕羅云，唐麗晴.云計算調度粒子群改進算法[J].計算機系統應用，2019，28（07）：151-156.

〔7〕任神河，鄭寇全，關冬冬，惠軍華.基于IFTS的云計算網絡動態負載均衡方法[J].系統工程理論與實踐，2019，39（05）：1298-1307.

〔8〕李佳，夏云霓.云計算資源調度問題求解的布谷鳥搜索算法[J].控制工程，2019，26（01）：170-174.

〔9〕王欣欣，劉曉彥.基于雙適應度動態遺傳算法的云計算資源調度[J].計算機工程與設計，2018，39（05）：1372-1376+1421.

〔10〕Yuan H ， Li C ， Du M . Optimal Virtual Machine Resources Scheduling Based on Improved Particle Swarm Optimization in Cloud Computing[J]. Journal of Software， 2014.

〔11〕Liu J， Guo Z. Scheduling Algorithm of Cloud Computing Based on DAG Diagram and Game Optimal Model[J]. International Journal of Grid and Distributed Computing， 2015， 8.

〔12〕Seyedali Mirjalili. Moth-flame optimization algorithm： A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems，2015，89.

〔13〕陳暄，龍丹.基于改進的雞群算法在云計算資源調度中的研究[J].計算機應用研究，2019，36（09）：2584-2587.

〔14〕李天朝，李蜀瑜.基于改進的蝙蝠算法在云計算資源調度中的研究[J].電子設計工程，2017，25（01）：43-46.

〔15〕聶清彬，蔡婷，王寧.改進的蟻群算法在云計算資源調度中的應用[J].計算機工程與設計，2016，37（08）：2016-2020.