任金霞 王興康 甘夏冰

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000）

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

1 標(biāo)準(zhǔn)天牛群算法

1.1 天牛須算法

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

1.2 粒子群算法

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

1.3 天牛群算法

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

2 改進(jìn)天牛群算法

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

2.1 引入自適應(yīng)權(quán)重以及步長(zhǎng)

步長(zhǎng)是影響天牛群算法搜索能力的關(guān)鍵參數(shù)，在引入騎兵反饋策略確定大致目標(biāo)區(qū)域后，需要將天牛的速度與步長(zhǎng)進(jìn)行相應(yīng)改變。隨著迭代次數(shù)的增加，在鎖定大致目標(biāo)區(qū)域后，天牛需要將自身的步長(zhǎng)逐漸變小，以免步長(zhǎng)過大導(dǎo)致天牛群跳出目標(biāo)區(qū)域，陷入局部最優(yōu)，而天牛速度則需要逐漸增加抵消天牛因步長(zhǎng)變小帶來的影響，提高天牛在目標(biāo)大致區(qū)域的搜索速度，降低天牛對(duì)食物的搜索時(shí)間，有效避免因天牛過早收斂陷入局部最優(yōu)解。因此，本文引入正弦自適應(yīng)和動(dòng)態(tài)自適應(yīng)權(quán)重機(jī)制，以改進(jìn)天牛群算法的位置與速度。

2.2 加入奇兵反饋策略

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

2.3 改進(jìn)天牛群算法的任務(wù)調(diào)度流程

文章將改進(jìn)天牛群算法作為云任務(wù)調(diào)度策略時(shí)，需要將云任務(wù)調(diào)度的可行解空間與天牛群個(gè)體的位置進(jìn)行映射編碼處理。運(yùn)算步驟為：

（1）初始化云計(jì)算數(shù)據(jù)中心物理主機(jī)列表和每個(gè)物理主機(jī)上虛擬機(jī)列表。（2）初始化參數(shù)，將天牛群中所有天牛隨機(jī)傳送至搜索區(qū)域內(nèi)，并根據(jù)天牛所在位置利用目標(biāo)函數(shù)計(jì)算出其適應(yīng)度值。（3）對(duì)天牛的速度、位置進(jìn)行迭代更新后，確定云任務(wù)調(diào)度中適應(yīng)度值，選出最優(yōu)個(gè)體以及群體最優(yōu)位置。（4）判斷種群最優(yōu)位置，確定每次迭代的各類天牛的位置，若當(dāng)次迭代的天牛位置為調(diào)度分配中歷次迭代中最優(yōu)值，則用其代替?zhèn)€體天牛中的歷史最優(yōu)值，否則對(duì)天牛群的歷史全局最優(yōu)位置進(jìn)行更新。（5）若提前確定全局最優(yōu)解或者算法的迭代次數(shù)達(dá)到設(shè)定最大值時(shí)，則算法終止，返回當(dāng)前所有天牛群最優(yōu)解即云任務(wù)調(diào)度中最小適應(yīng)度值。（6）任務(wù)調(diào)度結(jié)束。

3 仿真實(shí)驗(yàn)對(duì)比

實(shí)驗(yàn)環(huán)境：Inter Core （TM） i5-4076U CPU 4.0 GHz；系統(tǒng)平臺(tái)為windows 8操作系統(tǒng)；軟件為matlab2015。本文通過仿真平臺(tái)對(duì)改進(jìn)天牛群算法（BSOS）、天牛群算法（BOS）、粒子群算法（POS）和螢火蟲算法（FA）在云計(jì)算任務(wù)調(diào)度中針對(duì)適應(yīng)度、任務(wù)完成時(shí)間、費(fèi)用以及負(fù)載均衡等目標(biāo)方面進(jìn)行仿真以及結(jié)果分析。

3.1 收斂速度、精度對(duì)比

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

圖1 適應(yīng)度收斂性對(duì)比

圖2 時(shí)間收斂性對(duì)比

圖3 均衡度收斂性對(duì)比

圖4 費(fèi)用收斂性對(duì)比

3.2 優(yōu)化目標(biāo)結(jié)果對(duì)比

將虛擬機(jī)的數(shù)量設(shè)置為6，云計(jì)算任務(wù)數(shù)量分別 設(shè) 置 為100、400、700、1 000。通 過 與BSO、POS、FA三種算法仿真結(jié)果進(jìn)行比較、分析，得出試驗(yàn)結(jié)果如圖5～圖8所示。從圖5～圖8可以看出，隨著任務(wù)數(shù)量的不斷增加，BSOS算法在完成云計(jì)算任務(wù)的時(shí)間、費(fèi)用、均衡度以及對(duì)多目標(biāo)函數(shù)所構(gòu)成的適應(yīng)度值的搜索上，優(yōu)化效果均優(yōu)于其他3種算法。當(dāng)任務(wù)為100個(gè)和400個(gè)時(shí)，4種算法無論是在單目標(biāo)還是多目標(biāo)的搜索上均差別不大，但當(dāng)任務(wù)數(shù)量增加到700個(gè)和1 000個(gè)時(shí)，對(duì)于時(shí)間、費(fèi)用、均衡度3個(gè)單目標(biāo)而言，BSOS算法的優(yōu)化效果與其他3種算法的差異逐漸變大。這是因?yàn)锽SOS算法引入奇兵反饋策略后，能夠迅速提高對(duì)有效搜索區(qū)域的搜索效率，避免算法前期無法跳出局部最優(yōu)的困境問題，并因?yàn)樘炫２介L(zhǎng)、權(quán)重因子以及個(gè)體、群體學(xué)習(xí)因子的自適應(yīng)變化，增加了算法在目標(biāo)區(qū)域的搜索效率，保證BSOS算法較其他算法在局部搜索和全局搜索方面均有很大程度地提高，在規(guī)模較大的云計(jì)算任務(wù)調(diào)度過程中優(yōu)化效果更加明顯。

圖5 任務(wù)完成時(shí)間對(duì)比

圖6 任務(wù)完成費(fèi)用對(duì)比

圖7 任務(wù)完成均衡度對(duì)比

圖8 適應(yīng)度函數(shù)對(duì)比

4 結(jié)語

對(duì)天牛群算法改進(jìn)，并以任務(wù)完成時(shí)間、費(fèi)用以及均衡度構(gòu)建為多目標(biāo)函數(shù)，應(yīng)用在云計(jì)算任務(wù)調(diào)度中。經(jīng)過對(duì)改進(jìn)算法的理論分析以及實(shí)驗(yàn)結(jié)果仿真對(duì)比可以看出，隨著任務(wù)數(shù)量的增加，BSOS算法在收斂速度、完成任務(wù)時(shí)間、費(fèi)用以及負(fù)載均衡方面表現(xiàn)均較為優(yōu)越。