改進人工蜂群算法及其在邊緣計算卸載的應用

章呈瑞，柯 鵬，尹 梅

1.武漢科技大學 計算機科學與技術學院，武漢 430065

2.智能信息處理與實時工業系統湖北省重點實驗室，武漢 430065

隨著5G通訊技術與物聯網技術的發展，用戶對AR、VR等計算密集型、時延敏感型應用的需求越來越高。根據思科2020年度互聯網報告統計，預計到2023年全球移動設備將從2018年的88億增長到2023年的131億，連接到IP網絡的設備數量將達到293億高于2018年的184億[1]。傳統的云計算作為一種集中式計算，已難以在短時間內處理需要大量資源的應用程序。此外，由于云計算中心往往距離用戶較遠，也帶來了數據傳輸時延高、能耗高等一系列問題。

為了應對這些問題，移動邊緣計算（mobile edge computing，MEC）應用而生[2]，該模式通過云計算下沉，端計算上移來將移動智能終端及物聯網設備的計算任務卸載至邊緣云中，解決了傳統云計算模式算力有限、時延較高的不足。

MEC計算卸載作為一個重要的研究方向，受到了國內外學者的廣泛研究。目前對于計算卸載策略的研究主要包括三個方向，最小化時延、最小化能耗以及時延和能耗加權后最小化該代價函數[3]。

文獻[4-7]側重于對最小化時延的研究。文獻[4]研究了多用戶計算的劃分以及云資源上卸載計算，設計了一個離線啟發式算法，來解決計算卸載所面臨的時延問題。文獻[5]采用馬爾可夫決策方法，根據任務緩沖區的排隊狀態、本地處理單元的執行狀態以及傳輸單元的狀態來動態卸載計算任務。文獻[6]構建了一個帶有能量收集設備的MEC系統，并提出了一種基于李雅普諾夫優化的動態計算卸載算法用以最小化時延。文獻[7]提出了一種在MEC中使用排隊網絡和遺傳算法的有效卸載策略，并與粒子群算法對比在最小化任務響應時延上取得了較好的效果。

文獻[8-10]側重于對最小化能耗的研究。文獻[8]考慮了前向鏈路和反向鏈路的鏈路狀況，運用離散的人工魚群算法，在時延約束下，最小化能耗。文獻[9]提出了一種車聯網中的霧云計算卸載算法以最小化車輛和計算設施的能耗。文獻[10]設計了一個考慮任務延遲的MEC系統，提出了一種聯合優化資源分配和任務卸載分配的策略，用于最小化能耗。

文獻[11-14]側重于對時延和能耗進行聯合優化。文獻[11]通過為用戶任務設置優先級，采用均衡傳輸性能的信道分配算法為卸載任務分配信道資源，實現計算資源最優配置，優化系統總增益。文獻[12]研究了超密集邊緣網絡中的依賴關系任務卸載問題，提出一種啟發式算法，在保證子任務之間依賴關系的同時，共同優化時延和能耗。文獻[13]通過拉格朗日對偶分解將原問題分解成若干個子問題，在通信和計算資源約束下最小化執行時延和能耗的加權和。文獻[14]考慮工業環境下的應用，采用離散的粒子群算法，使用懲罰函數來平衡時延與能耗。

通過分析以上研究，不難發現，文獻[4-7]雖能夠獲得一個較好的時延，但并未充分考慮移動終端的能耗情況，這就會導致低電量設備仍可能會為滿足最小時延要求，選擇在本地計算，導致電量消耗更快。文獻[8-10]能夠對能耗進行較好的優化，延長終端設備的使用時間，但可能會導致某些對時延敏感的應用得不到及時的處理。文獻[11]聯合考慮了計算時延和能耗，側重于對單一邊緣服務器的優化，未能充分考慮系統整體的全局優化。文獻[12-13]則難以解決多MEC多終端設備的卸載問題。文獻[14]選用離散的粒子群算法求解時延與能耗的代價函數，取得了較好的效果，但由于粒子群算法的限制，在迭代后期仍然采用全維度更新策略，在高維問題上難以取得更好的收斂精度，且較容易陷入局部最優。

本文則在以上研究的基礎上，考慮到真實環境中多移動設備多MEC服務器的情況，引入云服務器，從整體角度考慮，將能耗作為懲罰項構造代價函數，使用人工蜂群算法（artificial bee colony algorithm，ABC）[15]聯合優化時延與能耗。

啟發式算法在MEC卸載領域得到了很好的應用[7-8，14]，ABC作為經典啟發式算法，被證明具有良好的全局收斂性[16]，具有收斂精度高，易于跳出局部最優等良好性質，近年來也在云計算卸載、霧計算卸載等領域獲得較好表現。文獻[17]提出一種混合隊列蟻群和人工蜂群算法以解決移動云計算環境的任務分配及卸載，文獻[18]針對智能電網的云霧計算場景，提出了一種混合人工蜂群優化算法（HABACO）進行仿真實驗，獲得較好的負載平衡效果。文獻[19]在霧計算場景下利用ABC優化適應度函數來優化能耗、調度運行時間等，提升網絡服務質量。以上研究均取得了較好的表現，但并不適用于MEC環境下高維、高并發的計算卸載。

由于蜂群的單維更新策略，導致算法前期在高維問題上收斂速度較慢，后期難以依靠個體本身的位置更新跳出局部最優，僅能依靠向偵察蜂轉化來增強探索能力，對個體的開發能力有一定的損失[20]。故本文引入多維更新種群解決此問題，并通過種群間的轉化平衡算法的探索和開發能力，使得算法能夠在任意最大容忍時間限度內，獲得較好的卸載方案。

1 系統模型

本文構建了一個云服務器輔助的多設備移動邊緣計算卸載系統，移動終端設備或者物聯網設備可以通過無線網絡與MEC服務器或云服務器的基站進行通信。假定有M個移動設備。N個MEC服務器，1個云服務器，每一個移動終端產生任務后，可以在本地進行計算，也可以選擇將任務卸載至邊緣服務器或云服務器，即每一個任務會有N+2種可能的卸載結果，其卸載模型如圖1所示。

圖1 卸載系統模型Fig.1 Offloading system model

1.1 本地計算模型

當移動設備或者物聯網設備在本地計算時，其任務執行時間為：

其中Wi表示第i個設備產生任務的數據量，Flocal表示該設備本地計算的能力（每秒CPU周期數，單位為GHz），Tlocal表示在本地完成任務所需花費的時間。

本地計算的能耗為：

其中，Tlocal為本地計算的時間，Plocal為本地計算的功率，Elocal為本地計算的能耗。

1.2 卸載計算模型

每一個邊緣移動設備產生的任務除了在本地計算外，還可以選擇在邊緣服務器或者云服務器進行計算。

當其卸載至邊緣服務器時，其時延為：

卸載至邊緣服務器的能耗為：

當其卸載至云服務器時，其時延為：

卸載至云服務器的能耗為：

假設，最終卸載結果為有a個任務在本地計算。則在本地計算的最大時延為：

在邊緣端服務器計算的最大時延為：

則該系統最終時延為：

能耗為：

1.3 代價函數

將該問題轉化為在能耗約束下最小化時延的問題，其總代價計算公式為：

其中g為懲罰系數，將當前系統總能耗作為一個懲罰項，以避免系統為最小化時延全部采用本地卸載，從而導致移動設備電量消耗增多。

2 基于ABC的優化

2.1 基本的人工蜂群算法

人工蜂群算法（ABC）是由Karaboga[15]于2005年根據蜜蜂的采蜜行為提出的一種群智能優化算法，ABC算法分為四個階段：初始化階段、雇傭蜂階段、觀察蜂階段、偵察蜂階段。

（1）初始化階段：設定蜜源數量SN，問題維度D，最大迭代次數Gmax，允許最大失敗嘗試次數limit，然后根據如下公式隨機初始化一組蜜源位置：

（2）雇傭蜂階段：每只雇傭蜂占據一個蜜源Xi，并根據下式進行一維鄰域搜索產生新的位置（候選蜜源）：

其中k∈{1,2,…,SN} ，j為隨機選擇的一個維度，φij是[-1,1]均勻分布的隨機數[21-22]。所有雇傭蜂完成搜索后，通過搖擺舞[15]的方式向觀察蜂傳遞蜜源位置及蜜源質量（適應度值）。

（3）觀察蜂階段：觀察蜂根據雇傭蜂傳遞的信息按下式計算跟隨每一個雇傭蜂的概率，隨后采用輪盤賭來選擇跟隨對象，其概率計算公式如下：

其中fitness i表示第i個蜜源的適應度值，適應度值越大，表明該蜜源的質量越高，其被選擇的概率也越大。而對于最小化問題，其函數值越小，蜜源越優秀，其適應度應越大，故須按下式轉化：

其中f(X i)即表示最小化問題的函數值，當其為非負數時應取其倒數，而為避免函數值趨于0適應度趨于無窮的情況發生，在其前加1后取倒；當其為負數時應取其絕對值，而對于最小化問題，負數顯然比非負數更好，非負數最好的適應度為1，則負數的適應度應大于1，故在其絕對值前加1。

（4）偵察蜂階段：若蜜源位置超過lim it次循環都沒有更新，則雇傭蜂會放棄該蜜源轉化為偵察蜂，按照公式（12）重新初始化。

2.2 基于邊緣計算模型的編碼調整

為使人工蜂群算法能夠應用于邊緣計算卸載問題，需要建立以下映射關系，以蜜源位置代表卸載決策，將尋找卸載決策的過程轉化為人工蜂群算法尋找蜜源的過程，故需對人工蜂群算法進行離散處理。

假設移動終端數量為M，MEC服務器數量為N，云服務器數量為1，以0號位表示本地計算，1號位，2號位，…，N號位表示在對應編號的MEC服務器中卸載計算，N+1號位表示在云服務器中卸載計算。對初始化公式（12）進行離散處理得到：

其中randi(N+2)表示隨機產生[1,N+2]上的整數，此時X ij即為在[0,N+1]的整數。每一個蜜源X i表示一個1行M列的卸載決策向量，向量中元素的數值即表示該設備需要將任務卸載的位置。

對位置更新公式（13）進行離散處理得到：

其中Y ij表示位移的增量，即位置更新公式中除Xij之外的其他項，[Y ij]表示對Y ij進行四舍五入取整，%為取余，對于公式（13）：

由于X ij和X kj均為[0,N+1]的整數，且φij在[-1,1]之間，故Y i j在[-N-1,N+1]之間。若[Y ij]=0，則表示仍然在原位置卸載，若[Y ij]＞0，則表示需要將該設備的計算位置向后移動[Y ij]位，然后對N+2取余，構造循環結構以保證更新后仍然為[0,N+1]的整數。若[Y ij]＜0則相應前移[Y i j]位，最終如公式（17）所示。

例如某一時刻有5個設備的任務需要卸載，有3臺邊緣服務器及一臺云服務器。則以0表示本地計算，1、2、3分別表示在對應編號的邊緣服務器計算，4表示在云服務器計算。

首先按式（16）初始化卸載決策向量（蜜源），假設其中一組卸載決策向量如圖2的A圖，即第一臺設備將任務放在本地計算，第二臺設備將任務卸載至云服務器計算，第三臺設備將任務卸載至3號邊緣服務器計算，第四臺設備將任務卸載至2號邊緣服務器計算，第五臺設備將任務卸載至1號邊緣服務器計算。假設在迭代過程中隨機到第3維（第三臺設備）進行更新，且[Y ij]=3，代入式（17），則更新后的卸載決策向量如圖2的B圖，第三臺設備將會在1號邊緣服務器計算。此時代入代價函數計算代價，擇優選擇，如果更新后的卸載決策更優則會替代原卸載決策。

圖2 位置更新演示Fig.2 Location update demo

假設在下一次迭代時，隨機到第5維（第五臺設備）更新，且[Y ij]=-3，代入式（17），則更新后的卸載決策向量如圖2的C圖，第五臺設備將會把任務卸載至3號邊緣服務器計算，后續的過程以此類推。

這樣就完成了對人工蜂群算法的編碼調整，使得其能夠適用于本系統。

2.3 改進的人工蜂群算法

在MEC系統中，某一時刻需要卸載的任務數一般較多，對應的問題維度較高，針對高維復雜問題中人工蜂群算法收斂速度慢，開發能力弱的缺點，引入多維更新種群，利用種群優秀程度差異實現種群的轉化，以此動態調整兩種群規模。

2.3.1 單多維更新策略

為了平衡人工蜂群算法的探索與開發能力，并加快算法前期的收斂速度，在原有單維更新種群的基礎上引入多維更新種群。

對于種群1在雇傭蜂和觀察蜂階段，采用一種精英引導的單維更新策略，文獻[21]將全局最優解融入到搜索方程中提出了一種GABC算法，其位置更新公式如下：

其中，Gbest j是全局最優個體的第j個元素，ψij是在[0,1.5]上均勻分布的隨機數。

該算法取得了良好的收斂速度和收斂精度，但在復雜多模態問題上易陷入局部最優，本文將公式中的最優個體更改為精英個體，改進后的公式如下：

其中，Ebest j是從精英個體從隨機選擇的，定義種群中適應度前5的個體（最好的5個卸載決策向量）為精英個體。通過向精英個體的學習，在迭代前期，精英個體分布較為分散，有利于全局搜索，在迭代后期，精英個體較為集中，有利于局部搜索，提高收斂精度。

基本的人工蜂群算法迭代過程中都基于單一維度進行更新，而單維搜索策略也是限制ABC收斂速度以及后期收斂精度的主要原因，為了解決這一問題，對種群2在雇傭蜂階段引入多維更新策略，觀察蜂階段仍使用式（13），更新的維度數設置為D up，按下式進行更新：

其中，φ是一個1行D列的矩陣，其中每一個元素都在[-1,1]之間，根據更新維度隨機設置φ中D-Dup個元素為0，此時即表示更新Dup個維度，其余維度不更新，其中Dup會在執行動態種群策略時遞減，·表示矩陣的點乘運算，Y ij的計算與公式（18）相同。

設定boundary為種群1和種群2的分界，兩種群雇傭蜂總規模為SN，則編號1到boundary為種群1，boundary+1到SN為種群2，為保證在種群轉化后，較差種群仍有一定的搜索能力，設定一個最小的種群規模Poplimit，在執行動態種群策略時兩種群的規模都不得小于這一限制，在每一次迭代過程中其位置更新偽碼如下：

1.fori=1∶boundary

2. 根據公式（17）和（21），生成新蜜源V i

3. iff(V i)＜f(X i)

4.Xi=V i；count(i)=0

5. else

6.count(i)=count(i)+1

7. end if

8. end for

9.根據公式（15）計算每一個個體的適應度值，并根據公式（14）計算每一個個體被選中的概率

10.form=1∶boundary

11.輪盤賭選擇跟隨對象，根據公式（17）和（21），更新位置并重復步驟3到7

12.end for

13.fori=boundary+1∶SN

14.隨機選擇D up個維度根據公式（17）和（18），生成新蜜源V i，并重復步驟3到7

15.end for

16.重復步驟9

17.form=bound ary+1∶SN

18.輪盤賭選擇跟隨對象，根據公式（17）和（18），更新位置信息并重復步驟3到7

19.end for

2.3.2 動態種群策略

設定種群優秀程度因子（degree of excellence，DOE）用于判斷當前種群的好壞，DOE1和DOE2分別表示種群1和種群2的優秀程度。

在算法每一次迭代結束前進行評估，記錄當前代最優個體的索引值index。

若index≤boundary，表明當前代最優個體在種群1中，種群1優秀程度增加，種群2優秀程度減小，即：

若ind ex＞boundary，則當前代最優個體在種群2中，種群2優秀程度增加，種群1優秀程度減小，即：

記錄兩種群優秀程度差異difference：

當 |difference|＞d limit時，認為兩種群差異較大，此時執行種群轉化，此處d lim it取1/4×Gmax。

對于最小化問題，不失一般性，若difference＞0，則表明單維更新種群1更優秀，此時將種群2的一部分轉化為種群1。為最大化種群轉化的收益，對種群2按目標函數值降序排序，此時種群2排在前面的個體即為較差個體，可以直接進行種群轉化，即：

同理，若difference＜0，則表明多維更新種群2更優秀，此時將種群1的一部分轉化為種群2，對種群1按目標函數值升序排序，此時種群1排在后面的個體即為較差個體，可以直接進行種群轉化，即：

同時在每次轉化過程中較差的種群需要向較好的種群進行學習，以保證較差種群在后續迭代過程的尋優能力。其學習策略如下：

根據公式（17），則卸載模型中：

rand i為從較差種群中隨機選擇的一個個體，m、n為較好種群中隨機的兩個個體。偽代碼如下：

1.ifind ex≤boundary

2.DOE1=DOE1+1；DOE2=DOE2-1；

3.else

4.DOE1=DOE1-1；DOE2=DOE2+1；

5.end if

6.diff er ence=DOE1-DOE2

7.if |difference|＞dlimit

8.DOE1=0；DOE2=0；

9. ifdifference＞0

10.Dup=round(0.8×Dup)

11. 對種群2按目標函數值降序排列，并根據公式（26）更新boundary

12. 從種群2中隨機選擇一個個體根據公式（17）、（29）、（30）向種群1學習

12.else

13. 對種群1按目標函數值升序排列，并根據公式（27）更新boundary

14. 從種群1中隨機選擇一個個體根據公式（17）、（29）、（30）向種群2學習

15.end if

16.end if

2.4 算法復雜度分析

文獻[24]給出ABC算法一次迭代的時間復雜度為O(SN·D)，其中SN為蜜源數量，D為問題維度。與ABC算法相比，基于單多維動態種群策略的人工蜂群算法（artificial bee colony algorithm based on onedimensional and multi-dimensional dynamic population strategy，OMABC）在選擇精英個體、多維更新以及動態種群轉化時引入了額外的計算，為此給出本文算法的時間復雜度分析。OMABC在一次迭代過程中，選擇精英解（對蜜源質量進行排序）的時間復雜度為O(SN·log(SN))，多維更新的時間復雜度為O(SN·D)，動態種群轉化（對較差種群的蜜源質量進行排序）的時間復雜度為O(S N·log(SN))，則本文算法的時間度為O(SN·D+SN·log(SN))，而針對高維復雜問題，D通常遠大于log(SN)，故改進算法的時間復雜度可簡化為O(SN·D)與ABC算法時間復雜度相同。

2.5 有效性驗證

為驗證該算法在高維問題上的有效性，使用IEEE CEC 2017中29個測試函數分別在50維、100維進行實驗，其中F1、F3為單峰函數，F2因不穩定已被CEC官方刪除，F4～F10為簡單多峰函數，F11～F20為混合函數，F21～F30為復合函數。算法尋優結果越接近各測試函數最優值，表明算法尋優能力越強。

將OMABC與經典最優引導改進算法GABC[21]、ABC/best/1[22]和近些年提出多策略混合算法Modified-ABC[23]、MHABC[24]，進行對比實驗。實驗環境：處理器AMD Ryzen 7-4700U CPU@2.0 GHz，RAM 16 GB，Windows10 64位操作系統，MATLAB R2018b。設置50維時Gmax=5 000次，100維時Gmax=8 000次，為保證公平，采用統一方式初始化，每個算法獨立求解29個測試函數，并記錄最終尋優結果。重復上述過程30次，計算各算法在29個測試函數上最終尋優結果的平均值及標準差。OMABC的具體實現步驟如下：

1.初始化算法參數，包括SN、D、Gmax、limit、boundary等；

2.根據公式（12）初始化蜜源；

3.按單多維更新策略偽代碼部分，使用式（20）和（22）完成雇傭蜂階段及觀察蜂階段；

4.若蜜源連續limit次都沒有得到更新，則雇傭蜂放棄該蜜源轉化為偵察蜂按式（12）重新初始化；

5.按動態種群策略部分偽代碼實現種群轉化，較差種群通過式（28）向較好種群學習；

6.記錄全局最優值，判斷是否滿足算法終止條件（是否達到最大迭代次數），若滿足，則返回最優結果，否則返回步驟3繼續迭代。

得到的結果如表1、2所示，加粗部分為最優值，表中存在數值相同但未被加粗的情況，這是因為數據采用科學計數法統計時存在四舍五入的情況，其真實值會略大于加粗值。實驗結果表明，在50維時OMACB在15個測試函數取得最好的收斂的精度。除在F26、F30兩個測試函數外，OMABC的表現均比原始的ABC效果優異，在F4、F5、F7、F8、F16、F20、F21、F22、F25、F28、F30上與對比算法相差不大。

表1 50維ABC及其變種算法結果比較（平均值±標準差）Table 1 Comparison of 50-dimensional ABC and its variant algorithm results（mean±std.）

而在100維時，29個測試函數的收斂精度均超過基本的ABC。這是因為，基本ABC的單維更新方式難以在高維問題上發揮作用，而OMABC的單維與多維更新相互配合的方式，更能適應高維復雜問題，最終在16個測試函數上取得最優，在F4、F8、F16、F20、F23、F24、F27、F28上與對比算法差距不大。這說明單多維動態種群策略的確能夠提高的算法的尋優能力，且在高維問題上更有優勢。

圖3為在100維的測試函數F1中OMABC單維更新種群的種群規模變化曲線及ABC與OMABC的收斂曲線，其中虛線boundary表示種群1的種群規模，可以看到在迭代前期，單維更新種群表現更為優異，OMABC會相應的擴大單維更新種群的規模，同時由于采用了精英引導策略，在迭代速度方面有更多的優勢，而在迭代后期，單一維度的更新已經無法滿足算法跳出局部最優的需要，此時多維更新種群的表現更好，更多的個體將執行多維更新策略，幫助算法跳出局部最優，并提高收斂精度。

圖3 收斂曲線及種群1規模變化曲線Fig.3 Convergence curve and populationa 1 boundary change curve

表2 100維ABC及其變種算法結果比較（平均值±標準差）Table 2 Comparison of 100-dimensional ABC and its variant algorithm results（mean±std.）

3 仿真實驗

3.1 參數設置及算法流程

在驗證改進策略有效性后，將OMABC算法應用于第1節的MEC系統模型上仿真。

同樣選擇在處理器AMD Ryzen 7-4700U CPU@2.0 GHz RAM 16 GB，Windows 10 64位操作系統下使用MATLAB R2018b進行實驗。

MEC系統各項參數設置為：移動設備個數M={50,100,150,200,250,300}，MEC服務器個數N=10，云服務器個數為1，算法最大迭代次數設置Gmax=100，其他參數設置如表3。

表3 MEC系統參數設置Table 3 MEC system parameters setting

PSO算法參數：nPop=50，c1=c2=1.5，ω=0.5；ABC算法參數設置為：SN=50，limit=100；OMABC算法參數設置為：SN=50，limi t=100，D up=0.8×M，boundary=4/5×SN。

在設置好系統各項參數后，還需要確定代價函數中懲罰系數g的取值。由于T與E的量綱、數量級存在差異，故需根據實驗條件設置合適的g以平衡代價函數中時延與能耗的關系。當任務全部在本地卸載時，會對移動設備的性能有較高的要求且會帶來相當高的能耗，減少移動設備使用時間，此時代價函數應該有一個相當高的代價。

當任務全部在服務器上卸載時，將會獲得一個較低的能耗和較高的時延，也應有一個較高的代價。這兩個代價應盡可能的接近，以使得卸載算法能夠得到合理的卸載決策。此處采用二分法確定g的取值范圍，起始時設置g分別為0和1，隨機設置30組全部在本地卸載與30組全部不在本地卸載的決策向量，代入代價函數后獲取其平均值。隨后逐步縮小g的范圍至[0，0.5]、[0，0.25]、[0，0.125]一直到[0.046 875，0.050 781 25]附近時兩代價曲線已幾乎重合，限于篇幅僅展示部分曲線如圖4所示，故確定g的范圍應在0.050 781 25附近，此值可根據實際情況自行調整其大小，當希望能耗影響更大時適當取較大值，當希望時延影響更大時則取較小的值，此處取g=0.05以使得時延與能耗具有相近的影響。確定好懲罰系數g的取值后即可開始仿真實驗，OMABC的具體卸載流程如圖5所示。

圖4 不同g時的代價曲線Fig.4 Cost curve at different g

圖5 算法流程圖Fig.5 Algorithm flow chart

3.2 結果分析

在上述參數設置下，獨立重復實驗30次，選擇隨機卸載算法（Random）、粒子群算法（PSO）、基本的人工蜂群算法（ABC）與本文的改進算法（OMABC）進行對比。

圖6為在迭代次數均為100次時，不同卸載算法的收斂曲線，為保證實驗公平，所有算法統一初始化位置。

圖6 不同卸載算法的收斂曲線圖Fig.6 Convergence curves of different offloading algorithms

可以觀察到，各種卸載算法在前20次迭代中都有較快的收斂速度；Random算法，由于采用隨機卸載策略，具有盲目性，在M為50時尚能依賴隨機性尋優，但在更高維度（150維度及以上）時，已幾乎趨于直線，喪失尋優能力。這是由于高維問題更為復雜，隨機尋找缺乏目標，有利維度的信息無法保留導致的。

PSO算法通過向個體最優以及全局最優學習，在前10次迭代中取得了更好的表現，在M為50、100、150、250、300時具有較快的收斂速度，超過了基于的ABC的卸載算法；觀察PSO的迭代曲線不難發現，粒子群算法由于每次位置更新均為全維度更新，迭代曲線呈現階梯狀，這就對算法的迭代次數有很高的要求，需要設置合適的迭代次數以最大化收益，且由于其沒有跳出局部最優的操作，算法后期也很難跳出局部最優位置。

ABC算法則有較為平滑的迭代曲線，沒有明顯的階梯狀，這是由算法的單維更新策略以及偵察蜂階段所保證的，算法一維一維的緩慢向最優位置附近挪動，有效利用了優秀位置的維度信息，且不易陷入局部最優，能夠較為平穩的尋優。同時單維更新策略也是制約算法在高維問題上收斂速度的主要因素，如在M為250、300時，算法在第30次迭代后尋優精度才高過PSO算法。

而OMABC除擁有較強跳出局部最優的能力外，還具有較快的收斂速度，在迭代后期仍具備較強的尋優能力，這是由于OMABC采用了動態種群策略以及精英引導學習，能夠自適應判斷種群的好壞從而實現單維更新種群以及多維更新種群之間的相互轉換，平衡算法的探索和開發能力，提高收斂速度和收斂精度。在迭代前期，兩種群經歷一定時間的獨立尋優后，能夠自適應的擴大優秀種群的規模，從而加快算法前期收斂速度。在迭代后期，OMABC又具有人工蜂群算法不易陷入局部最優的良好性質，同時又可以自適應的判斷當前尋優的狀態，若距離最優位置較近，則擴大單維更新種群，提高收斂精度；若所處位置為局部最優位置，則擴大多維更新種群，進一步提高算法跳出局部最優的能力。

從圖6中可以看出M=50時，Random算法優化后系統總代價降低了7.43%，PSO算法優化后系統總代價降低了12.37%，ABC算法優化后系統總代價降低了18.76%，OMABC算法優化后系統總代價降低了21.60%。

在M=100時，Random算法優化后系統總代價降低了1.85%，PSO算法優化后系統總代價降低了9.61%，ABC算法優化后系統總代價降低了15.80%，OMABC算法優化后系統總代價降低了18.28%。

在M=150時，Random算法優化后系統總代價降低了0.21%，PSO算法優化后系統總代價降低了5.81%，ABC算法優化后系統總代價降低了10.79%，OMABC算法優化后系統總代價降低了11.29%。

在M=200時，Random算法優化后系統總代價降低了1.86%，PSO算法優化后系統總代價降低了8.66%，ABC算法優化后系統總代價降低了10.98%，OMABC算法優化后系統總代價降低了12.53%。

在M=250時，Random算法優化后系統總代價降低了2.25%，PSO算法優化后系統總代價降低了9.20%，ABC算法優化后系統總代價降低了11.71%，OMABC算法優化后系統總代價降低了14.29%。

在M=300時，Random算法優化后系統總代價降低了1.13%，PSO算法優化后系統總代價降低了7.55%，ABC算法優化后系統總代價降低了9.45%，OMABC算法優化后系統總代價降低了11.16%。

除M=50外，其他情況下各算法降低的代價都相對穩定，這是由于50維的問題較為簡單，各算法均能獲得更好的解，而其他情況下問題維度更高，尋優難度提升導致的。同時，不難看出OMABC在各情況均取得了最好的效果。

如圖7為在相同的迭代次數下獨立運行30次得到的箱線圖，箱體中位線表示算法30次運行的中位數，反應了數據的一般水平，箱體的上下邊界稱為內限，分別表示數據的上四分位和下四分位，因此箱體的寬度可以在一定程度上反應算法的穩定性。超出箱體上方和下方的之外的界限稱為外限，分別表示樣本數據剔除異常值后的最大值和最小值（1.5 IQR內的范圍）。

圖7 不同卸載算法的箱線圖Fig.7 Box plots of different offloading algorithms

可以看出OMABC算法，在設備數為50、100、150、200、300時箱體寬度均比對比算法小，具有較好的穩定性，在設備數為250時，OMABC的箱體寬度與ABC近似，表明穩定性與ABC算法近似。綜上可以證明OMABC在解決此類問題上具有較好的穩定性。從整體上看，OMABC箱體所處位置較其他算法更低具有較好的收斂精度。

如圖8為在不同設備個數的情況下，30次獨立運行后不同卸載策略的平均代價柱狀圖，其中Local表示在本地計算。實驗中設備個數M分別為50、100、150、200、250、300，可以觀察到隨著設備數量的增加本地卸載策略的系統總代價增加較為明顯，這是任務數量增多而又沒有得到有效卸載導致的。采用Random、PSO、ABC、OMABC算法卸載后的系統總代價較本地計算更低，減少了系統的時延與能耗。

圖8 不同設備數下各算法代價Fig.8 Cost of each algorithm under different M

OMABC與本地計算的差異也隨著設備數的增加在逐漸增大，在M為50時，系統代價平均降低了113.87；M為100時，系統代價平均降低了134.02；M為150時，系統代價平均降低了153.95；M為200時，系統代價平均降低了170.49；M為250時，系統代價平均降低了199.39；M為300時，系統代價平均降低了218.86；在不同設備數M下均能取得更為優秀的效果，驗證了OMABC算法在解決此類問題上的優越性。

4 結束語

本文針對多設備MEC系統中計算任務的執行時間以及終端設備的能耗最小化問題，構建了一個云服務器輔助的多MEC服務器計算卸載模型，并提出了一種改進的人工蜂群算法（OMABC），通過單維更新種群和多維更新種群的相互轉化與配合，提高算法的收斂精度，并在CEC 2017進行測試，驗證了算法的有效性。通過添加懲罰因子，設計代價函數，將OMABC運用在移動邊緣計算卸載問題上，實現了在能耗約束下最小化時延的目標。仿真結果表明，與Random、PSO、ABC相比，本文的OMABC算法具有更好的卸載性能。未來的研究將進一步優化人工蜂群算法，考慮任務的前驅和后繼結點，將其運用在MEC中基于工作流的任務卸載問題上。