趙 然，郭志川,朱小勇

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學(xué)院大學(xué),北京100049)

0 引 言

蝗蟲優(yōu)化算法(Grasshopper Optimization Algorithm, GOA)是一種元啟發(fā)式優(yōu)化算法，可以用來解決任務(wù)調(diào)度問題[1]。任務(wù)調(diào)度問題是一種在邊緣計(jì)算領(lǐng)域常見的問題[2]。邊緣終端節(jié)點(diǎn)存在較強(qiáng)的異構(gòu)性，節(jié)點(diǎn)資源情況和任務(wù)處理速度不同，所以不同的任務(wù)調(diào)度方案會產(chǎn)生不同的執(zhí)行結(jié)果。一個(gè)優(yōu)秀的任務(wù)調(diào)度方案可能會對邊緣計(jì)算系統(tǒng)的服務(wù)效果產(chǎn)生很大影響。

任務(wù)調(diào)度問題是將多個(gè)任務(wù)調(diào)度到多個(gè)節(jié)點(diǎn)的優(yōu)化問題[3]。任務(wù)調(diào)度問題也是一個(gè)NP-hard問題[4]。許多元啟發(fā)式算法(Meta-Heuristic Algorithm)被用來處理邊緣計(jì)算中的任務(wù)調(diào)度問題[5]。元啟發(fā)式算法具有操作簡單和開銷較少的優(yōu)點(diǎn),能夠在最優(yōu)化問題中通過評價(jià)、迭代、演進(jìn)等方式逐步找到全局最優(yōu)解或近似全局最優(yōu)解[6]。

粒子群算法(Particle Swarm Optimization, PSO)是一種非常經(jīng)典的元啟發(fā)式算法[7-11]。該算法最初是受到鳥群活動規(guī)律的啟發(fā)，通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)解。近年來，研究人員通過模仿昆蟲、魚類和其他群體生物的自然行為提出了一些新的元啟發(fā)式算法，包括蟻獅算法[12](Ant Lion Optimizer, ALO)、鯨魚優(yōu)化算法[13-14](Whale Optimization Algorithm, WOA)、蜻蜓優(yōu)化算法[15-17](Dragonfly Algorithm, DA)、蟻群算法[18-20](Ant Colony Optimization)等。2017年，Saremi等人[1]提出了蝗蟲優(yōu)化算法。蝗蟲優(yōu)化算法通過在蝗蟲集群內(nèi)部分享經(jīng)驗(yàn)，進(jìn)行多輪迭代演進(jìn)，不斷修正搜索方向，最終找到最優(yōu)位置或者近似最優(yōu)位置。

自蝗蟲優(yōu)化算法提出以來，研究人員在此基礎(chǔ)上提出了一些改進(jìn)優(yōu)化算法，但提升效果不夠顯著。Ewees等人[21]于2018年提出了基于反向?qū)W習(xí)的改進(jìn)蝗蟲優(yōu)化算法(Improved Grasshopper Optimization Algorithm Using Opposition-Based Learning, OBLGOA)。OBLGOA引入了反向?qū)W習(xí)策略，以生成的反向解作為備選的可行解，使用這種策略可以提高算法的收斂速度，但是由于反向?qū)W習(xí)策略缺乏隨機(jī)性，對算法性能的提升效果較為有限。Arora等人[22]于2018年提出了混沌蝗蟲優(yōu)化算法(Chaotic Grasshopper Optimization Algorithm, CGOA)。CGOA引入混沌映射因子來提高算法性能，文獻(xiàn)[22]中使用了10種不同的混沌映射因子來測試混沌理論的效果，但是因?yàn)椴煌幕煦缫蜃釉谔幚聿煌臏y試函數(shù)的時(shí)候效果不同，對算法整體的效果提升也不夠理想。

研究人員對于蝗蟲優(yōu)化算法的改進(jìn)缺乏隨機(jī)性，也沒有考慮算法會陷入局部最優(yōu)的問題，改進(jìn)效果不夠顯著。本文通過引入基于Levy飛行的局部搜索機(jī)制和基于線性遞減參數(shù)的隨機(jī)跳出策略，提出一種基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法，優(yōu)化算法的搜索性能，并將所提出的改進(jìn)算法應(yīng)用于解決邊緣計(jì)算中的任務(wù)調(diào)度問題。

1 蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法模擬了自然界中蝗蟲群的遷徙和覓食行為?；认x群為了尋找一個(gè)有食物的新棲息地，不斷進(jìn)行遷徙。在這個(gè)過程中,蝗蟲群內(nèi)部蝗蟲之間的相互作用力會對每一個(gè)蝗蟲個(gè)體的位置造成影響。來自蝗蟲群外的風(fēng)的力量和重力也會影響蝗蟲集群整體的移動軌跡。另外，對于遷徙過程來說，目標(biāo)食物的位置也是一個(gè)重要的影響因素。

蝗蟲優(yōu)化算法將蝗蟲集群抽象為一群搜索單元進(jìn)行數(shù)學(xué)建模，借鑒其遷徙和覓食的移動過程的特點(diǎn)。文獻(xiàn)[1]提出了蝗蟲群體遷徙的數(shù)學(xué)模型，具體的模擬公式如式(1)所示：

Xi=Si+Gi+AI

(1)

其中，變量Xi為第i個(gè)搜索單元的位置，變量Si代表蝗蟲集群內(nèi)部搜索單元之間的相互作用力對第i個(gè)搜索單元的影響程度，變量Gi代表蝗蟲集群外部重力因素對第i個(gè)搜索單元的影響程度，變量Ai代表風(fēng)力的影響因素。在應(yīng)用于解決數(shù)學(xué)優(yōu)化問題的時(shí)候，為了優(yōu)化數(shù)學(xué)模型，公式(1)中代表集群外部影響因子的變量Gi和Ai需要被替換為目標(biāo)食物的位置Td，這樣迭代公式變成式(2)所示：

Xi=Si+Td

(2)

其中，變量Si的定義如式(3)所示：

(3)

其中，ub和lb分別表示搜索空間的上界和下界，變量c為搜索單元的搜索舒適區(qū)控制參數(shù)。其中函數(shù)s(r)為計(jì)算蝗蟲集群之間的社會關(guān)系影響因子，該函數(shù)定義如式(4)：

(4)

其中，e是自然底數(shù)，變量f表示吸引力因子，參數(shù)l表示吸引力長度。在整個(gè)搜索過程中，每個(gè)位置的評價(jià)指標(biāo)為適應(yīng)度函數(shù)。在優(yōu)化問題中，適應(yīng)度函數(shù)通常為所要求解的目標(biāo)函數(shù)，通過適應(yīng)度函數(shù)計(jì)算所得到的值為適應(yīng)度值(fitness)。在任務(wù)調(diào)度問題中，適應(yīng)度函數(shù)通常是根據(jù)具體任務(wù)調(diào)度模型所建立的評價(jià)函數(shù)。在優(yōu)化問題的求解過程中，公式(2)作為演進(jìn)公式，被不斷循環(huán)迭代來尋找最優(yōu)解，每輪迭代得到的最優(yōu)的適應(yīng)度值即被視為目前得到的最優(yōu)解的值,得到的最優(yōu)解的位置則被視為當(dāng)前的食物目標(biāo)位置Td，直到達(dá)到迭代次數(shù)為止。

2 基于Levy飛行改進(jìn)蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法具有簡單的理論基礎(chǔ)，易于實(shí)施。但是原始的蝗蟲優(yōu)化算法缺乏隨機(jī)因素，幾乎沒有變化，算法在搜索過程中很容易陷入局部最優(yōu)。為了解決這些不足，本文提出2個(gè)改進(jìn)方法：基于Levy飛行的局部搜索機(jī)制和基于線性遞減參數(shù)的隨機(jī)跳出策略。

2.1 基于Levy飛行的局部搜索機(jī)制

原始蝗蟲優(yōu)化算法中的所有參數(shù)都是確定性的，非常缺乏隨機(jī)性。這會導(dǎo)致算法在迭代演進(jìn)的過程中缺乏創(chuàng)造性，每個(gè)搜索單元只能搜索相對確定的位置。將隨機(jī)因子引入到確定性系統(tǒng)中是提高性能的常用方法。

Levy飛行是一種非常有效的提供隨機(jī)因子的數(shù)學(xué)方法。Levy飛行可以提供步長符合Levy分布的隨機(jī)游走方法，Levy分布如式(5)：

Levy～u=t-λ， 1<λ≤3

(5)

為了擴(kuò)展搜索單元的搜索半徑，增強(qiáng)算法的隨機(jī)性以及局部最優(yōu)值的搜索能力，本節(jié)提出一種基于Levy飛行的局部搜索機(jī)制。當(dāng)一次位置更新的迭代過程結(jié)束的時(shí)候，該機(jī)制可以以一定概率通過Levy飛行對每個(gè)搜索單元的位置進(jìn)行局部調(diào)整，調(diào)整公式的定義如式(6)所示。在某種程度上，Levy飛行可以在搜索單元向著最優(yōu)解位置搜索的過程中為其提供一定的“視覺”，使得搜索單元可以“看到”它們周圍的一片較小的區(qū)域內(nèi)的情況。

X=X+10×c×sts×Levy(dim)×X

(6)

其中，sts是控制飛行方向和變化概率的閾值函數(shù)，sts的計(jì)算方法如式(7)所示。其中，sign(x)是sign符號函數(shù)，xtrans是取值在[-3,3]之間的隨機(jī)數(shù)。

sts=sign(xtrans-1)+sign(xtrans+1)

(7)

2.2 基于線性遞減參數(shù)的隨機(jī)跳出策略

蝗蟲優(yōu)化算法的基礎(chǔ)理論比較簡單，該算法只關(guān)注了收斂到全局最優(yōu)的過程，而忽略了跳出局部最優(yōu)的機(jī)制。因此，蝗蟲優(yōu)化算法的搜索過程很容易陷入局部最優(yōu)，使得搜索無法更進(jìn)一步地進(jìn)行下去。

為了提高蝗蟲優(yōu)化算法的跳出局部最優(yōu)的能力，本節(jié)提出基于線性遞減參數(shù)的隨機(jī)跳出策略。當(dāng)搜索單元搜索到當(dāng)前最優(yōu)解的位置的時(shí)候，該目標(biāo)位置可以替換舊的目標(biāo)位置。如果沒有搜索到最優(yōu)解，則可以開始啟動基于線性遞減參數(shù)的隨機(jī)跳出策略。該策略的計(jì)算方式如式(8)：

Xi=(2×(0.5-rand(0,1))+1)×Xi

(8)

其中，Xi是第i個(gè)搜索單元的位置。如果新搜索到的Xi擁有更優(yōu)的適應(yīng)度值，那么它將會取代原來的Xi，可以認(rèn)為發(fā)生了一次成功的跳出行為。

原始蝗蟲優(yōu)化算法的演進(jìn)公式僅僅將當(dāng)前迭代獲得的最佳位置作為搜索方向，但是忽略了一些其他可能有用的信息。為了使新發(fā)生的成功跳出動作所提供的信息能夠持續(xù)影響接下來的搜索過程，LBGOA將搜索單元的位置迭代演進(jìn)公式變成式(9)：

Xi=m×Si+(1-p)×Td+p×Xi

(9)

其中，p是用于控制搜索單元位置影響的協(xié)調(diào)參數(shù)。p在第一次迭代的時(shí)候初始化為0。如果搜索單元沒有進(jìn)行跳出或者跳出局部最優(yōu)失敗，p仍會被設(shè)置為0，以確保只有Si和Td才能影響下一次迭代演進(jìn)。當(dāng)搜索單元完成一次成功跳出時(shí)，p被設(shè)置為在接下來的3次迭代中線性遞減為0的變量，以使成功跳出的行為對搜索過程的影響持續(xù)到接下來的3次迭代過程中。經(jīng)過一些試驗(yàn)，p的遞減間隔被設(shè)置為0.35。對p取值的進(jìn)一步研究不在本文討論范圍內(nèi)。參數(shù)p的計(jì)算方法如式(10)：

(10)

2.3 基于Levy飛行的改進(jìn)蝗蟲算法流程

基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法的搜索過程分為初始化階段、迭代演進(jìn)階段、適應(yīng)度值更新階段和跳出階段這4個(gè)階段。在初始化階段，設(shè)置參數(shù)，并隨機(jī)初始化所有搜索單元的初始位置。在這一階段中，還計(jì)算了最優(yōu)目標(biāo)的位置和相應(yīng)的最優(yōu)適應(yīng)度值。在迭代演進(jìn)階段，搜索循環(huán)開始進(jìn)行。每個(gè)搜索單元都通過公式(9)移動到新的位置。之后每個(gè)搜索單元根據(jù)公式(6)以一定的概率進(jìn)行Levy飛行調(diào)整，并生成新的搜索位置。在適應(yīng)度值更新階段，計(jì)算新位置的適應(yīng)度值。如果新的適應(yīng)度值優(yōu)于當(dāng)前的全局最優(yōu)適應(yīng)度值，則新的位置可以取代舊的全局最優(yōu)目標(biāo)的位置。如果新的適應(yīng)度值沒有比當(dāng)前全局最優(yōu)目標(biāo)的適應(yīng)度值更優(yōu)，那么該搜索單元就會進(jìn)入跳出階段。在此階段，搜索單元嘗試根據(jù)公式(8)跳出局部最優(yōu)，并計(jì)算新的適應(yīng)度值。如果新的適應(yīng)度值優(yōu)于當(dāng)前搜索單元本身的適應(yīng)度值，那么新的位置可以取代舊的搜索單元的位置，完成一次成功的跳出。此時(shí)參數(shù)p也根據(jù)公式(10)進(jìn)行更新。如果新的適應(yīng)度值沒有優(yōu)于當(dāng)前搜索單元本身的適應(yīng)度值，那么搜索單元不會跳到新的位置上，會仍然停留在舊的位置上。到目前為止，循環(huán)求解過程中的一次迭代已經(jīng)完成。在達(dá)到最大迭代次數(shù)之后，循環(huán)過程結(jié)束，此時(shí)的全局最優(yōu)適應(yīng)度值和全局最優(yōu)目標(biāo)位置就是最終的尋優(yōu)求解的結(jié)果?；贚evy飛行的改進(jìn)蝗蟲優(yōu)化算法的流程如算法1所示。

算法1基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法

1:初始化蝗蟲集群初始位置，計(jì)算目標(biāo)適應(yīng)度

2:while未達(dá)到最大迭代次數(shù)do

3:根據(jù)公式(9)更新Xi的位置

4:Xi搜索單元根據(jù)公式(6)進(jìn)行Levy飛行

5:計(jì)算適應(yīng)度值

6:if當(dāng)前適應(yīng)度值優(yōu)于目標(biāo)適應(yīng)度值then

7:更新目標(biāo)適應(yīng)度值和目標(biāo)最優(yōu)解位置

8:else

9:Xi搜索單元根據(jù)公式(9)進(jìn)行跳出

10:計(jì)算適應(yīng)度值

11:if當(dāng)前適應(yīng)度值優(yōu)于搜索單元自身適應(yīng)度值then

12:更新搜索單元的位置

13:end if

14:根據(jù)公式(10)設(shè)置參數(shù)p的值

15:end if

16:end while

17:返回得到的目標(biāo)最優(yōu)值和目標(biāo)最優(yōu)解的位置

3 實(shí)驗(yàn)結(jié)果及分析

3.1 CEC測試實(shí)驗(yàn)設(shè)置

為了評估所提出的基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法(LBGOA)的性能，本文進(jìn)行CEC測試實(shí)驗(yàn)。將LBGOA算法與6個(gè)元啟發(fā)式算法的性能進(jìn)行了比較，對比算法包括原始的蝗蟲優(yōu)化算法(GOA)，基于反向?qū)W習(xí)的蝗蟲優(yōu)化算法(OBLGOA)，最近幾年新提出的3種元啟發(fā)式算法：鯨魚優(yōu)化算法(WOA)、蜻蜓優(yōu)化算法(DA)和蟻獅優(yōu)化算法(ALO)，以及經(jīng)典的啟發(fā)式算法粒子群優(yōu)化算法(PSO)。

本文的CEC測試實(shí)驗(yàn)使用了CEC2014中的30個(gè)測試函數(shù)，來測試所提出的LBGOA算法的搜索性能。測試函數(shù)可以分為4種類型，用來評估算法的不同方面的性能。其中，測試函數(shù)F1～F3是單峰測試函數(shù)(Unimodal Functions)，只有一個(gè)局部最優(yōu)位置，可以用來評價(jià)算法的局部搜索能力和搜索的精確程度。測試函數(shù)F4～F16是具有多個(gè)局部最優(yōu)的簡單多峰測試函數(shù)(Simple Multimodal Functions)，可以用來評價(jià)算法的擺脫局部最優(yōu)能力[1]。測試函數(shù)F17～F22是混合函數(shù)(Hybrid Function)，測試函數(shù)F23～F30是復(fù)合函數(shù)(Composition Functions)，這2類測試函數(shù)比較復(fù)雜，在測試優(yōu)化算法的搜索性能方面更具有說服力。本實(shí)驗(yàn)中的F1～F30等30個(gè)測試函數(shù)的維度均調(diào)整為10維，每個(gè)維度的搜索范圍為[-100,100]。

使用Matlab代碼完成CEC測試實(shí)驗(yàn)。每個(gè)算法使用30個(gè)搜索單元進(jìn)行搜索，每次實(shí)驗(yàn)進(jìn)行500次迭代搜索。為了降低意外情況對于實(shí)驗(yàn)結(jié)果準(zhǔn)確性的影響，測試實(shí)驗(yàn)對每個(gè)算法重復(fù)30次，通過計(jì)算實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)平均值來評價(jià)算法的性能。

3.2 實(shí)驗(yàn)結(jié)果

7種算法在30個(gè)測試函數(shù)上運(yùn)行30次，得到的最優(yōu)目標(biāo)適應(yīng)度值的平均值如表1所示。

表1 7種算法測試結(jié)果適應(yīng)度值的平均值

測試函數(shù)LBGOAGOAOBLGOAWOAALODAPSOF1427870.2848045.516653321236950612297011460482140352.2F21237.4995043.48322961.86443185151412.16297420.262246.68F31155.7848527.375445.03758602.4152864.179279.4962646.196F4423.4581421.6316418.0353453.9205423.8234433.4269426.5156F5520.0003520.0093520.0897520.3077520.026520.1495520.1224F6601.9969603.8861604.399608.8616604.4631606.631603.0682F7700.2521700.2536700.3641701.7564700.1967700.4361700.5344F8823.1493824.1401832.5778843.1588824.8245832.569820.142F9918.6721923.3185926.0815952.4135926.9009936.5463921.6901F101562.3531839.0421904.6371731.4911553.9721739.9341497.235F111783.2791960.8071961.0242338.862056.1222187.4781907.531F121200.1691200.2751200.3941201.0461200.341200.4241200.198F131300.2571300.2331300.4431300.4971300.3051300.5871300.221F141400.1991400.2121400.3251400.2931400.2371400.5241400.307F151501.1211501.581501.8561510.1431501.8141503.4391501.035F161603.0941603.0931603.4091603.4251603.2671603.5021603.019F173679.0677353.2779055.856285165.2196126.517979.354249.137F189799.42711557.778471.42313886.9112038.5112294.7810691.1F191902.5621903.3031904.3571906.7691904.7461905.2151902.776F202610.4924613.9494829.71512700.3612292.3311154.325563.958F216462.12312128.6910058.55578944.911127.6811801.244738.309F222305.6562349.3652386.6332298.6632275.6432322.2892326.972F232629.4612630.2512629.9132642.6982630.3632632.6322629.733F242525.52530.1952546.0992588.8192554.0012564.0342551.431F252693.2122686.1212682.5552699.7792692.8542699.242698.162F262700.1892700.232700.2882700.4232703.6322700.4192703.526F272957.9023094.4093074.3783145.3843036.4383103.233050.753F283247.7963323.7213473.3423473.2333501.2823553.3583469.034F294086.467394935.9928366.1306480.1757693.4876842.21149437F304816.5424664.884942.4357372.3455160.0745302.0894651.662

從表1中可以看出，所提出的LBGOA在17個(gè)函數(shù)的測試中能夠得到最優(yōu)的平均適應(yīng)度值，在F1、F7、F8、F15、F18和F21等6個(gè)函數(shù)的測試中能夠得到次優(yōu)的平均適應(yīng)度值，只有在其他7個(gè)函數(shù)的測試中得到相對不夠優(yōu)秀的平均適應(yīng)度值。

F1～F3的3個(gè)單峰函數(shù)測試結(jié)果表明，在基于Levy飛行的局部搜索機(jī)制的幫助下，所提出的LBGOA算法擁有較好的局部搜索能力，能夠搜索到更精細(xì)的局部最優(yōu)解。F4～F16的13個(gè)多峰函數(shù)測試結(jié)果表明，在基于線性遞減參數(shù)的隨機(jī)跳出策略的幫助下，所提出的LBGOA算法擁有較好的跳出局部最優(yōu)困境的能力。

為了消除實(shí)驗(yàn)數(shù)據(jù)的偶然性并表明實(shí)驗(yàn)結(jié)果的顯著性，本研究引入了威爾科克森秩和檢驗(yàn)。這里計(jì)算了關(guān)于LBGOA與每個(gè)其他算法之間在測試函數(shù)F1～F30上的統(tǒng)計(jì)數(shù)據(jù)的p值。當(dāng)p小于0.05時(shí)，可以認(rèn)為2個(gè)樣本之間的差異是顯著的。LBGOA的威爾科克森秩和檢驗(yàn)結(jié)果如表2所示。

表2 LBGOA算法與其他6種算法在CEC測試集上的威爾科克森秩和檢驗(yàn)結(jié)果P值

測試函數(shù)GOAOBLGOAWOAALODAPSOF10.0050845.86E-063.02E-110.0020525.19E-073.82E-09F20.0001253.69E-113.02E-110.0579291.78E-100.297272F31.46E-104.98E-113.02E-113.02E-111.78E-100.297272F40.0446410.8883032.43E-050.0080720.0241570.033934F50.1023263.02E-113.02E-110.0099413.02E-112.03E-09F60.0001414.42E-063.02E-113.81E-078.99E-110.021506F70.0073930.0079593.02E-110.0797821.86E-060.003339F80.0099410.0003993.81E-070.0085330.0002840.018087F90.0850.002381.46E-100.0103152.32E-060.025186F100.0011748.88E-060.0198830.0088830.0467560.039526F110.022360.0144121.01E-080.0002391.02E-050.085F120.0260770.0001116.07E-110.000772.68E-060.021701F130.0080720.0002254.11E-070.0724466.53E-080.053951F140.0068431.34E-056.36E-050.18097.60E-070.001114F150.0191120.0002533.02E-110.0010582.23E-090.041191F160.0088830.0018570.0008120.0933412.28E-050.055923F170.0002842.78E-076.70E-112.37E-101.64E-050.043764F180.0233980.090490.7061710.0089990.2458140.044641F190.0042263.26E-074.50E-115.46E-091.41E-090.065204F200.0001411.19E-063.16E-101.29E-091.41E-090.000284F210.0518770.2837782.03E-090.0270860.1334540.014412F220.0112280.0008120.0064140.0555460.4289630.027061F234.80E-072.87E-103.02E-111.10E-088.15E-112.84E-10F240.0162370.0006553.69E-119.51E-066.01E-080.003339F250.0555460.0050840.0001170.0036711.34E-050.022365F260.1023260.0011746.53E-080.000626.53E-070.037282F270.0338740.0048562.37E-100.0144121.19E-060.015366F280.0241573.83E-053.26E-076.77E-058.89E-101.02E-05F290.0580180.0048560.0058270.0559236.35E-050.03255F300.0090470.0098233.57E-060.0222570.0451460.042038

從表2中可以看出，在大多數(shù)的測試結(jié)果中，LBGOA與其他幾種比較算法之間的p值小于0.05，僅有少部分測試結(jié)果的p值大于0.05，說明所進(jìn)行的CEC實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果是顯著的。

4 LBGOA應(yīng)用于任務(wù)調(diào)度問題

4.1 任務(wù)調(diào)度問題描述

在邊緣計(jì)算中，由于異構(gòu)邊緣節(jié)點(diǎn)的資源情況、工作負(fù)載、處理速度和任務(wù)類型的不同，將不同的任務(wù)調(diào)度到不同邊緣節(jié)點(diǎn)上執(zhí)行會產(chǎn)生不同的代價(jià)。邊緣計(jì)算的任務(wù)調(diào)度問題中，常見的代價(jià)包括任務(wù)執(zhí)行時(shí)間和節(jié)點(diǎn)運(yùn)行開銷費(fèi)用[23]。

本節(jié)將所提出的LBGOA算法應(yīng)用于邊緣計(jì)算中的任務(wù)調(diào)度問題。將N個(gè)任務(wù)調(diào)度到M個(gè)異構(gòu)節(jié)點(diǎn)的一種調(diào)度方案抽象為搜索空間中的一個(gè)點(diǎn)的位置，每一種調(diào)度方案都是一個(gè)N維離散向量[24]。每個(gè)調(diào)度方案可以對應(yīng)一個(gè)任務(wù)總執(zhí)行時(shí)間和節(jié)點(diǎn)運(yùn)行開銷費(fèi)用，并且以此來計(jì)算任務(wù)調(diào)度問題中的適應(yīng)度值。搜索單元集群通過LBGOA算法在整個(gè)搜索空間中搜索最佳適應(yīng)度值的位置，能夠得到最優(yōu)或近似最優(yōu)的任務(wù)調(diào)度方案。

(11)

第j個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間stj是通過將在第j個(gè)節(jié)點(diǎn)上執(zhí)行的所有任務(wù)的執(zhí)行時(shí)間相加得到的。計(jì)算方法如公式(12)所示：

(12)

總的執(zhí)行時(shí)間Makespan為所有節(jié)點(diǎn)的執(zhí)行時(shí)間取最長值。計(jì)算方法如公式(13)所示：

Makespan=max{stj|j=1,2,3,…,M}

(13)

工作節(jié)點(diǎn)在執(zhí)行任務(wù)的時(shí)候會產(chǎn)生額外的開銷費(fèi)用。費(fèi)用只與工作節(jié)點(diǎn)的工作時(shí)間有關(guān)，不論工作節(jié)點(diǎn)上執(zhí)行的是什么類型的任務(wù)。節(jié)點(diǎn)的開銷費(fèi)用價(jià)格為bpsj，表示第j個(gè)節(jié)點(diǎn)在單位時(shí)間內(nèi)產(chǎn)生的任務(wù)執(zhí)行開銷費(fèi)用?？偟馁M(fèi)用Budget是通過將所有節(jié)點(diǎn)產(chǎn)生的費(fèi)用相加得到的。Budget的計(jì)算方法如公式(14)：

(14)

Makespan和Budget是從2個(gè)方面來描述任務(wù)調(diào)度問題的開銷情況的，因此需要一個(gè)統(tǒng)一的評估適應(yīng)度。在本文中，任務(wù)調(diào)度問題的評估適應(yīng)度被定義為Makespan和Budget通過權(quán)重參數(shù)和進(jìn)行結(jié)合的結(jié)果。評估適應(yīng)度fitness的計(jì)算方法如公式(15)：

fitness=α×Makespan+β×Budget

(15)

優(yōu)化問題的搜索過程是連續(xù)的，但任務(wù)調(diào)度問題的解決方案是離散的，所以需要對LBGOA算法進(jìn)行離散化處理。當(dāng)每個(gè)循環(huán)迭代的過程結(jié)束后，所有的搜索單元都向距離其最近的整數(shù)位置進(jìn)行調(diào)整。

4.2 任務(wù)調(diào)度問題實(shí)驗(yàn)設(shè)置

在此任務(wù)調(diào)度模塊中，N個(gè)任務(wù)被分為K種類型，M個(gè)工作節(jié)點(diǎn)正在等待處理它們。在本文的工作中，不失一般性地，將K、N和M分別設(shè)置為4、10和5。為了平衡Makespan和Budget對fitness的影響，系數(shù)α和β設(shè)置為0.7和0.3。任務(wù)類型及任務(wù)消耗資源情況如表3所示。

表3 任務(wù)類型及資源消耗情況

項(xiàng)目任務(wù)12345678910資源4020304025354510510類型1112223344

每個(gè)節(jié)點(diǎn)擁有的總可用資源及節(jié)點(diǎn)開銷費(fèi)用價(jià)格bps情況如表4所示。

表4 節(jié)點(diǎn)擁有資源及開銷費(fèi)用價(jià)格bps

項(xiàng)目節(jié)點(diǎn)12345資源1005015010080bps0.50.20.80.10.5

表5 任務(wù)和節(jié)點(diǎn)的mips

jmipskjk=1k=2k=3k=4j=152108j=22421j=3810105j=42134j=55588

本文將所提出的LBGOA算法與另外6種算法進(jìn)行比較，包括GOA、OBLGOA、WOA、ALO、DA和PSO，每種算法使用30個(gè)搜索單元進(jìn)行搜索。為了減少意外因素的影響，對每種算法進(jìn)行30次獨(dú)立測試，計(jì)算并比較測試結(jié)果的平均值(avg)、標(biāo)準(zhǔn)差(std)、最優(yōu)值(min)、最差值(max)以及LBGOA相比不同算法的效果提升程度(pro)等統(tǒng)計(jì)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如表6所示。

表6 任務(wù)調(diào)度實(shí)驗(yàn)結(jié)果

算法avgstdminmaxpro/%LBGOA13.730.5612.5514.720GOA14.830.8513.1316.127.4OBLGOA14.700.7513.2815.997.5WOA14.430.8812.7716.284.8ALO18.992.2914.9223.5527.7DA19.592.7516.1926.2329.9PSO17.331.1914.4420.2920.7

任務(wù)調(diào)度實(shí)驗(yàn)結(jié)果表明，本文所提出的LBGOA在所有評價(jià)指標(biāo)方面都優(yōu)于其他算法。在平均值方面，LBGOA能夠得到最優(yōu)的解決方案。相比原始GOA算法和OBLGOA算法，LBGOA算法能夠?qū)⑵骄敌Ч謩e提升7.4%和7.5%，這說明所提出的2種針對GOA的優(yōu)化策略是有效的。相比其他4種算法，LBGOA算法能夠?qū)⑵骄敌Ч謩e提升4.8%、27.7%、29.9%和20.7%。另外LBGOA擁有最小的標(biāo)準(zhǔn)差，說明該算法相比其他算法更加穩(wěn)定。LBGOA可以找到所有算法中的最優(yōu)解，并且找到最差解的值相比其他算法找到的最差解也更優(yōu)。綜上所述，本文所提出的LBGOA算法在解決邊緣計(jì)算中的任務(wù)調(diào)度問題方面性能非常優(yōu)秀，相比其他算法效果提升非常顯著。

5 結(jié)束語

本文針對蝗蟲優(yōu)化算法隨機(jī)性差、容易陷入局部最優(yōu)的問題，提出了一種基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法(LBGOA)，并將其應(yīng)用于解決邊緣計(jì)算中的任務(wù)調(diào)度問題。一方面該算法引入了基于Levy飛行的局部搜索機(jī)制，擴(kuò)展搜索單元的搜索半徑，增強(qiáng)算法的隨機(jī)性以及局部最優(yōu)值的搜索能力。另一方面，該算法采用了基于線性遞減參數(shù)的隨機(jī)跳出策略，增強(qiáng)了算法跳出局部最優(yōu)的能力。實(shí)驗(yàn)結(jié)果表明，所提出的基于Levy飛行的改進(jìn)蝗蟲優(yōu)化算法相比原始GOA算法及其他幾種對比算法，能夠獲得更優(yōu)的搜索精度。將所提出的LBGOA算法應(yīng)用于邊緣計(jì)算中的任務(wù)調(diào)度問題，實(shí)驗(yàn)結(jié)果表明，該算法也能夠取得更優(yōu)的搜索結(jié)果，相比GOA、OBLGOA、WOA、ALO、DA和PSO算法，搜索效果分別提升7.4%、7.5%、4.8%、27.7%、29.9%和20.7%。