基于改進天牛群算法的多目標云任務調度

任金霞 王興康 甘夏冰

（江西理工大學電氣工程與自動化學院，江西 贛州 341000）

任務調度是合理利用有限的計算資源處理用戶的各類任務請求，而服務質量參數（QoS）則是在任務調度算法中不可避免的一項評價指標，在不違反服務級別協議（SLA）的前提下，有效完成各類用戶提交的硬性指標，避免負載利用不充分等問題[1]。目前，許多云計算任務調度模型通過引入啟發式優化算法解決任務調度[2-4]。如以布谷鳥搜索算法和粒子群算法為基礎，通過將布谷鳥算法的隨機搜索方式與粒子群算法的快速收斂優點相結合，使得算法能夠較為高效地提高本身的搜索精度[2]。本文提出了以天牛群搜索算法為基礎進行改進的任務調度策略，對云任務調度分配中的任務完成時間、費用以及負載均衡度等多目標進行優化。

1 標準天牛群算法

1.1 天牛須算法

天牛須算法是在2017年由Jiang等經過研究、實驗提出的一種智能仿生優化算法[5]，其算法代碼簡潔、運算速度快，但是算法精度過低。該算法主要是通過天牛本身的兩只左右須上的觸角對周圍氣味濃度進行比較，從而判斷前行方向。

1.2 粒子群算法

粒子群算法是以研究飛鳥的捕獵行為為基礎形成的算法。當飛鳥進行捕獵時，最簡單直接的方法就是對距離食物最近的鳥類進行跟蹤。該算法將單獨的飛鳥抽象為一個獨立的粒子，將捕食范圍抽象為多維空間。用矢量X定義其在搜索空間的位置，用矢量V定義其在搜索時的速度。通過對粒子的位置信息進行比較，確定飛鳥群中個體最優位置以及目前飛鳥自身位置，以此作為粒子群體的尋優經驗，找到搜尋范圍內的最優適應度值。

1.3 天牛群算法

天牛群算法是以天牛須搜索算法和粒子群算法為基礎研究出的一種仿生智能算法。該算法源于研究天牛通過本身觸角比較周圍氣味濃度覓食的行為而產生，并以粒子群算法為模型賦予天牛種群概念，通過天牛種群以一定的行為方式在有效范圍內對目標進行搜索。

2 改進天牛群算法

在云計算調度模型的應用中，天牛群算法雖然全局搜索能力大幅度提高，但搜索時天牛不夠靈活，搜索前期易收斂過快，從而只能陷入局部最優解的困境，耽誤搜索時間。因此，本文通過引入信息反饋策略及對天牛群的速度以及步長進行自適應調整對天牛群算法進行優化。

2.1 引入自適應權重以及步長

步長是影響天牛群算法搜索能力的關鍵參數，在引入騎兵反饋策略確定大致目標區域后，需要將天牛的速度與步長進行相應改變。隨著迭代次數的增加，在鎖定大致目標區域后，天牛需要將自身的步長逐漸變小，以免步長過大導致天牛群跳出目標區域，陷入局部最優，而天牛速度則需要逐漸增加抵消天牛因步長變小帶來的影響，提高天牛在目標大致區域的搜索速度，降低天牛對食物的搜索時間，有效避免因天牛過早收斂陷入局部最優解。因此，本文引入正弦自適應和動態自適應權重機制，以改進天牛群算法的位置與速度。

2.2 加入奇兵反饋策略

在天牛進行搜索前，先隨機選出小部分天牛，其數量定位在天牛群總數量的10%。在每次迭代搜索時進行隨機搜索，即將這部分天牛隨機傳送到有效搜索區域內，得到隨機天牛位置的反饋信息，在這部分天牛中選出適應度最佳的天牛位置與大部分正常搜索的天牛群中最佳天牛位置進行比較。如果隨機天牛選出的位置適應度更好，則將正常搜索天牛向選定隨機天牛位置靠攏，反之則不影響天牛的正常搜索，最終通過不斷迭代，找到最佳適應度位置。隨著算法的迭代，外出搜索的天牛作用會越來越小，所以迭代后期使得外出天牛慢慢回歸群體，天牛群搜索數量變多，提高了算法后期搜索精度，并在對于群體最優個體與個體最優的學習因子中進行適應性改變。

2.3 改進天牛群算法的任務調度流程

文章將改進天牛群算法作為云任務調度策略時，需要將云任務調度的可行解空間與天牛群個體的位置進行映射編碼處理。運算步驟為：

（1）初始化云計算數據中心物理主機列表和每個物理主機上虛擬機列表。（2）初始化參數，將天牛群中所有天牛隨機傳送至搜索區域內，并根據天牛所在位置利用目標函數計算出其適應度值。（3）對天牛的速度、位置進行迭代更新后，確定云任務調度中適應度值，選出最優個體以及群體最優位置。（4）判斷種群最優位置，確定每次迭代的各類天牛的位置，若當次迭代的天牛位置為調度分配中歷次迭代中最優值，則用其代替個體天牛中的歷史最優值，否則對天牛群的歷史全局最優位置進行更新。（5）若提前確定全局最優解或者算法的迭代次數達到設定最大值時，則算法終止，返回當前所有天牛群最優解即云任務調度中最小適應度值。（6）任務調度結束。

3 仿真實驗對比

實驗環境：Inter Core （TM） i5-4076U CPU 4.0 GHz；系統平臺為windows 8操作系統；軟件為matlab2015。本文通過仿真平臺對改進天牛群算法（BSOS）、天牛群算法（BOS）、粒子群算法（POS）和螢火蟲算法（FA）在云計算任務調度中針對適應度、任務完成時間、費用以及負載均衡等目標方面進行仿真以及結果分析。

3.1 收斂速度、精度對比

為了測試改進算法的收斂速度以及收斂精度，將云計算任務數量設置為700，種群數量以及迭代次數均設置為100，虛擬機數量設置為6。通過算法的迭代次數與任務的完成時間、費用、均衡度以及適應度函數的關系對其算法性能進行驗證，試驗結果如圖1～圖4所示。從圖1～圖4可以看出，對于時間、費用、負載均衡度3個優化目標，BSOS算法無論是前期搜索時收斂速度、后期搜索時的收斂精度都較強于其他算法。主要原因是改進算法引入奇兵反饋策略后，迭代前期對于目標搜索的范圍變得更加廣泛，可以幫助BSOS算法更快速地鎖定有效的搜索空間，通過自適應步長與權重的相互配合，隨著算法的后續搜索，搜索精度則會逐漸提高。對于多目標函數構建的適應度數而言，BSOS算法迭代前期與3種算法收斂速度基本持平，但隨著散落奇兵天牛的陸續回歸，增加的天牛群在目標區域的搜索數量，加快天牛群對于目標的搜索效率，使得BSOS算法的收斂速度顯著提升。

圖1 適應度收斂性對比

圖2 時間收斂性對比

圖3 均衡度收斂性對比

圖4 費用收斂性對比

3.2 優化目標結果對比

將虛擬機的數量設置為6，云計算任務數量分別 設 置 為100、400、700、1 000。通 過 與BSO、POS、FA三種算法仿真結果進行比較、分析，得出試驗結果如圖5～圖8所示。從圖5～圖8可以看出，隨著任務數量的不斷增加，BSOS算法在完成云計算任務的時間、費用、均衡度以及對多目標函數所構成的適應度值的搜索上，優化效果均優于其他3種算法。當任務為100個和400個時，4種算法無論是在單目標還是多目標的搜索上均差別不大，但當任務數量增加到700個和1 000個時，對于時間、費用、均衡度3個單目標而言，BSOS算法的優化效果與其他3種算法的差異逐漸變大。這是因為BSOS算法引入奇兵反饋策略后，能夠迅速提高對有效搜索區域的搜索效率，避免算法前期無法跳出局部最優的困境問題，并因為天牛步長、權重因子以及個體、群體學習因子的自適應變化，增加了算法在目標區域的搜索效率，保證BSOS算法較其他算法在局部搜索和全局搜索方面均有很大程度地提高，在規模較大的云計算任務調度過程中優化效果更加明顯。

圖5 任務完成時間對比

圖6 任務完成費用對比

圖7 任務完成均衡度對比

圖8 適應度函數對比

4 結語

對天牛群算法改進，并以任務完成時間、費用以及均衡度構建為多目標函數，應用在云計算任務調度中。經過對改進算法的理論分析以及實驗結果仿真對比可以看出，隨著任務數量的增加，BSOS算法在收斂速度、完成任務時間、費用以及負載均衡方面表現均較為優越。