基于進(jìn)化多任務(wù)多目標(biāo)優(yōu)化的邊緣計(jì)算任務(wù)卸載

摘 要：目前邊緣計(jì)算卸載的主流方案是將其建模為一個(gè)多目標(biāo)優(yōu)化問題，即最小化能耗和延時(shí)。不同于已有研究，主要考慮邊緣計(jì)算中，不同卸載區(qū)域的任務(wù)具有一定的相似性，可以利用任務(wù)的相似性加快算法的收斂速度和求解效果。以此基于進(jìn)化多任務(wù)優(yōu)化，提出一種進(jìn)化多任務(wù)多目標(biāo)優(yōu)化算法求解不同區(qū)域的任務(wù)卸載問題。該算法考慮了多個(gè)獨(dú)立的待優(yōu)化區(qū)域，將每個(gè)區(qū)域的任務(wù)卸載系統(tǒng)模型建模為一個(gè)多目標(biāo)優(yōu)化問題。通過學(xué)習(xí)不同區(qū)域的用戶分布和待處理任務(wù)的相似性來動(dòng)態(tài)調(diào)節(jié)種群的交流程度，加快了收斂速度，通過一次進(jìn)化，實(shí)現(xiàn)對兩個(gè)不同區(qū)域的優(yōu)化。實(shí)驗(yàn)結(jié)果表明，算法在收斂速度及最優(yōu)解分布的均勻性上均取得較好效果，可以獲得邊緣計(jì)算下的卸載部署優(yōu)化方案。

關(guān)鍵詞：移動(dòng)邊緣計(jì)算； 多目標(biāo)優(yōu)化； 多任務(wù)進(jìn)化優(yōu)化； 任務(wù)卸載

中圖分類號：TP18文獻(xiàn)標(biāo)志碼： A文章編號：1001－3695（2024）04－030－1164－07

doi：10.19734/j.issn.1001－3695.2023.08.0360

Task offload in edge computing based on evolutionarymulti task multi－objective optimization

Kong Shan Zheng Yuqi2

Abstract：At present， the mainstream solution of edge computing offloading is to model it as a multi－objective optimization problem to minimize energy consumption and delay. Different from the existing research， this paper mainly considered that tasks in different unloading areas had certain similarity in edge computing， which could be used to accelerate the convergence speed and solution effect of the algorithm. Based on this， this paper proposed an evolutionary multi－task multi－objective optimization algorithm to solve task offloading problems in different regions based on evolutionary multi－task optimization. This algorithm considered multiple independent regions to be optimized. It modeled the task offloading system model for each region as a multi－objective optimization problem， dynamically adjusting the communication level of the population by learning the user distribution in different regions and the similarity of the tasks to be processed， accelerating convergence speed， and achieving optimization for two different regions through one evolution. The experimental results show that the proposed algorithm has achieved good results in convergence speed and the uniformity of the optimal solution distribution， and can obtain the unloading deployment optimization scheme under edge computing.

Key words：mobile edge computing; multi－objective optimization; multi－task evolutionary optimization; task offloading

0 引言

隨著物聯(lián)網(wǎng)的發(fā)展，移動(dòng)設(shè)備不再局限于智能手機(jī)、個(gè)人電腦等小型微電子設(shè)備。增強(qiáng)虛擬現(xiàn)實(shí)、自動(dòng)駕駛、數(shù)字醫(yī)療等應(yīng)用場景對響應(yīng)延遲和計(jì)算速度提出了更高的要求。將計(jì)算資源集中在核心的中央云架構(gòu)難以滿足大量用戶的需求。基于對計(jì)算資源邊緣化的相關(guān)研究，歐洲電信標(biāo)準(zhǔn)協(xié)會提出了移動(dòng)邊緣計(jì)算的概念，旨在分配計(jì)算資源，提供低延遲、高帶寬的計(jì)算服務(wù)，創(chuàng)造一個(gè)開放、協(xié)作的網(wǎng)絡(luò)環(huán)境。

移動(dòng)邊緣網(wǎng)絡(luò)主要由移動(dòng)邊緣服務(wù)器（MES）和移動(dòng)設(shè)備（MD）組成。與終端設(shè)備相比，邊緣服務(wù)器配置了大量的計(jì)算資源，可以顯著提高處理速度。在移動(dòng)邊緣計(jì)算場景中，MD可以將待處理的應(yīng)用分解成子任務(wù)，并將其卸載到MES以充分利用計(jì)算資源。因此在智能設(shè)備終端附近部署具有堅(jiān)實(shí)計(jì)算能力的服務(wù)器，通過縮短直線距離來降低處理延遲。

由于MES環(huán)境的復(fù)雜性，許多因素會影響卸載決策。設(shè)計(jì)最優(yōu)的卸載決策策略以充分發(fā)揮MES在延時(shí)和能耗方面的性能增益是一個(gè)非常具有挑戰(zhàn)性的科學(xué)問題。作為一個(gè)NP－h(huán)ard問題，啟發(fā)式算法常被用來求解不同模式架構(gòu)下的最優(yōu)方案。用戶的使用體驗(yàn)主要受限于延時(shí)和能耗。現(xiàn)有研究成果大多將它們組合成單一的目標(biāo)函數(shù)，難以體現(xiàn)它們之間的制約關(guān)系，當(dāng)作為多目標(biāo)優(yōu)化問題求解時(shí)，計(jì)算量會大大增加。此外，由于邊緣服務(wù)器經(jīng)常需要部署在多個(gè)區(qū)域，而這些區(qū)域的部署往往存在一定的相似性，所以如果單獨(dú)優(yōu)化各個(gè)區(qū)域，無疑增加了計(jì)算的復(fù)雜性。

進(jìn)化多任務(wù)優(yōu)化是一種新的優(yōu)化模型，它利用了任務(wù)之間的相似性進(jìn)行知識遷移，加快算法的求解?；诖?，跟以往的研究不同，本文提出了一種自適應(yīng)多任務(wù)進(jìn)化優(yōu)化算法。該算法考慮多個(gè)獨(dú)立區(qū)域進(jìn)行優(yōu)化，它將每個(gè)領(lǐng)域的任務(wù)卸載系統(tǒng)模型抽象為一個(gè)多目標(biāo)優(yōu)化問題，并利用任務(wù)之間的相似性進(jìn)行知識遷移，動(dòng)態(tài)學(xué)習(xí)用戶分布和不同區(qū)域待處理任務(wù)的相似性，調(diào)整種群交流的程度。算法的最終目標(biāo)可以實(shí)現(xiàn)基于同一種群規(guī)劃和求解不同區(qū)域的任務(wù)卸載方案。

本文的主要貢獻(xiàn)概括如下：

a）設(shè)計(jì)了一種個(gè)體編解碼方案。它可以被分解成滿足區(qū)域約束的卸載策略。在迭代過程中，只有源碼被用作交配、非支配排序和其他操作的個(gè)體。最后，將最優(yōu)個(gè)體解碼成對應(yīng)不同區(qū)域的任務(wù)卸載方案。

b）采用基于分布的自適應(yīng)參數(shù)學(xué)習(xí)方法，動(dòng)態(tài)調(diào)整種群的交流程度，減少過度交流對種群收斂速度造成的負(fù)反饋。

c）基于一組預(yù)先生成的參考點(diǎn)對種群中的個(gè)體進(jìn)行非支配排序，為分散區(qū)域的個(gè)體提供額外信息作為參考，有效地提高了非支配解的均勻性，從而提高種群的多樣性。

1 相關(guān)工作

根據(jù)任務(wù)的類型和卸載的需求，卸載決策通常分為延時(shí)最小化和能耗最小化。最小化延時(shí)卸載策略就是完成任務(wù)執(zhí)行計(jì)算的時(shí)間要求最低。延時(shí)是邊緣計(jì)算資源調(diào)度優(yōu)化的重要指標(biāo)，為了滿足移動(dòng)邊緣場景下的低延時(shí)，文獻(xiàn)［1］在集中式單元－分布式單元架構(gòu)中建立基于深度學(xué)習(xí)的邊緣服務(wù)卸載框架，估計(jì)源和目標(biāo)邊緣節(jié)點(diǎn)距離，啟發(fā)式搜索目標(biāo)虛擬機(jī)，提出新的延遲最小化算法。文獻(xiàn)［2］研究了低功耗物聯(lián)網(wǎng)系統(tǒng)邊緣計(jì)算中的細(xì)粒度任務(wù)卸載問題?？紤]到物聯(lián)網(wǎng)任務(wù)調(diào)度、邊緣服務(wù)器上的異構(gòu)資源以及多接入邊緣網(wǎng)絡(luò)中的無線干擾，提出了面向多用戶邊緣系統(tǒng)的輕量級有效卸載方案，將最合適的物聯(lián)網(wǎng)任務(wù)和子任務(wù)卸載到邊緣服務(wù)器，從而最大限度地減少執(zhí)行時(shí)間。文獻(xiàn)［3］基于Lyapunov最優(yōu)進(jìn)化理論的動(dòng)態(tài)計(jì)算卸載算法提出了LODCO算法。該方法從任務(wù)運(yùn)行延時(shí)和任務(wù)運(yùn)行故障兩個(gè)方面優(yōu)化卸載決策。該方法最大限度地減少了卸載任務(wù)的處理延遲，并保證了成功的數(shù)據(jù)傳輸過程，減少了卸載失敗的機(jī)會。仿真結(jié)果表明，該算法在降低延遲方面具有很大優(yōu)勢，可以將卸載任務(wù)執(zhí)行時(shí)間減少64%。文獻(xiàn)［4］提出改進(jìn)蝙蝠群算法來解決邊緣計(jì)算中任務(wù)卸載調(diào)度優(yōu)化問題，改進(jìn)混沌蝙蝠群協(xié)同卸載方案，顯著降低了任務(wù)完成延遲，滿足實(shí)時(shí)處理任務(wù)需求。最小化能耗卸載的策略是在任務(wù)執(zhí)行過程中最小化系統(tǒng)范圍內(nèi)的能耗，同時(shí)滿足一定的延遲要求。能源消耗是數(shù)據(jù)中心的主要成本之一，文獻(xiàn)［5］討論了邊緣計(jì)算能否在云計(jì)算、數(shù)據(jù)下載、更新和預(yù)加載等應(yīng)用以及不同場景下的功耗變化等方面節(jié)省能源消耗。研究各種情況下的資源分配和任務(wù)調(diào)度以減少能源消耗是非常有意義的。文獻(xiàn)［6］提出了邊緣計(jì)算網(wǎng)絡(luò)架構(gòu)，允許邊緣節(jié)點(diǎn)共享計(jì)算和無線資源，滿足了任務(wù)延遲要求，同時(shí)最大限度地減少移動(dòng)用戶的總能耗。文獻(xiàn)［7］采用人工魚群算法設(shè)計(jì)了延遲約束下的能耗優(yōu)化卸載策略。該策略考慮了任務(wù)數(shù)據(jù)傳輸網(wǎng)絡(luò)的鏈接條件，有效降低了設(shè)備的能耗，但存在算法復(fù)雜的缺點(diǎn)。在多重資源環(huán)境下，文獻(xiàn)［8］設(shè)計(jì)了一種能量最小化的粒子群任務(wù)調(diào)度算法，用于匹配多個(gè)資源，以降低邊緣終端設(shè)備的能耗。文獻(xiàn)［9］研究了計(jì)算任務(wù)的部分卸載。為了最小化移動(dòng)設(shè)備的能耗，提出了一個(gè)任務(wù)可分離的移動(dòng)設(shè)備節(jié)能優(yōu)化問題，并使用貪心算法求解。對于某些系統(tǒng)，用戶更希望能夠最小化系統(tǒng)的總時(shí)間和能量消耗，以降低系統(tǒng)的整體消耗；或者權(quán)衡時(shí)間和能源消耗，以確保系統(tǒng)總消耗相對最優(yōu)和穩(wěn)定。因此，如何權(quán)衡延遲和能耗也是邊緣計(jì)算的一個(gè)有價(jià)值的研究方向。為了聯(lián)合權(quán)衡延時(shí)和能耗的問題，文獻(xiàn)［10］聯(lián)合確定了每個(gè)任務(wù)的卸載決策和資源分配，并聯(lián)合優(yōu)化卸載決策和本地中央處理單元的頻率，以最小化移動(dòng)設(shè)備的能源和時(shí)間成本。文獻(xiàn)［11］提出了一種動(dòng)態(tài)計(jì)算卸載算法來實(shí)現(xiàn)卸載成本和性能之間的權(quán)衡。它將優(yōu)化問題分解為一組子問題，并以并行分布式方式在線解決這些子問題，減少等待時(shí)間，提高服務(wù)質(zhì)量。文獻(xiàn)［12］建立了一種多目標(biāo)優(yōu)化策略來平衡服務(wù)器的能耗和延遲性能，并利用內(nèi)點(diǎn)法和排隊(duì)論解決了優(yōu)化問題。文獻(xiàn)［13］提出了一種基于任務(wù)卸載問題博弈論的卸載方案。這近似于理論最優(yōu)策略的最優(yōu)解，并顯著降低了系統(tǒng)開銷。

以上研究多是基于單用戶單任務(wù)場景，但在真實(shí)的任務(wù)場景中，多用戶多任務(wù)的情形更為常見，且更具有研究意義?；诖藛栴}，文獻(xiàn)［14］研究了多個(gè)任務(wù)之間具有優(yōu)先級約束的MEC架構(gòu)，優(yōu)化的目標(biāo)是最小化響應(yīng)時(shí)間，提出了一種基于貝葉斯網(wǎng)絡(luò)（Bayesian network based evolutionary algorithm，BNEA）的進(jìn)化算法來優(yōu)化任務(wù)分配策略。文獻(xiàn)［15］提出了一種深度強(qiáng)化學(xué)習(xí)（deep reinforcement learning，DRL）算法，用于解決異構(gòu)邊緣服務(wù)器中的計(jì)算卸載問題。該算法考慮了多任務(wù)、邊緣子網(wǎng)異構(gòu)性和邊緣設(shè)備移動(dòng)性，研究網(wǎng)絡(luò)環(huán)境并產(chǎn)生計(jì)算卸載決策，采用 Actor－Critic算法和深度確定性策略梯度，采用進(jìn)化計(jì)算卸載決策以最小化任務(wù)。文獻(xiàn)［16］提出了一種物聯(lián)網(wǎng)邊緣計(jì)算系統(tǒng)中的協(xié)同計(jì)算卸載和多用戶調(diào)度算法，該算法在隨機(jī)流量到達(dá)的情況下最小化延遲和功耗的長期加權(quán)和。將動(dòng)態(tài)優(yōu)化問題轉(zhuǎn)換為連續(xù)時(shí)間馬爾可夫決策過程（continuous time Markov decision process，CTMDP）模型，利用半梯度下降法和時(shí)差算法對值函數(shù)進(jìn)行線性逼近，推導(dǎo)出求解CTMDP模型的簡單算法。文獻(xiàn)［17］基于智能可穿戴設(shè)備通信網(wǎng)絡(luò)的邊緣卸載系統(tǒng)，提出了一種多用途計(jì)算排序分割算法，在卸載前劃分部分待卸載的任務(wù)。一旦作出卸載決策，就會建立以最小傳輸成本為目標(biāo)的相關(guān)模型，并提出動(dòng)態(tài)卸載策略。文獻(xiàn)［18］提出了一種高效的計(jì)算卸載方案，用于結(jié)合云計(jì)算的分布式負(fù)載平衡MEC網(wǎng)絡(luò)。通過使用隊(duì)列理論對非線性多目標(biāo)優(yōu)化問題進(jìn)行建模，從而減少邊緣和云服務(wù)的執(zhí)行延遲和成本。文獻(xiàn)［19］建立了一種多目標(biāo)優(yōu)化策略來平衡服務(wù)器的能耗和延遲 性能，并利用內(nèi)點(diǎn)法和排隊(duì)論解決優(yōu)化問題。文獻(xiàn)［20］提出了一種基于多任務(wù)任務(wù)卸載博弈論的卸載方案。這近似于理論最優(yōu)策略的最優(yōu)解，并顯著降低了系統(tǒng)開銷。文獻(xiàn)［21］將多用戶移動(dòng)邊緣計(jì)算場景中的任務(wù)卸載問題表述為一個(gè)凸優(yōu)化問題，該問題在有限資源條件下最小化延遲和能耗的加權(quán)和，使用計(jì)算卸載機(jī)制將移動(dòng)設(shè)備能耗和任務(wù)執(zhí)行延遲降至最低。

然而，以同時(shí)降低能耗、延時(shí)為目標(biāo)的已有研究，忽略了任務(wù)之間的關(guān)聯(lián)性?，F(xiàn)實(shí)生活中，很多優(yōu)化任務(wù)之間往往具有潛 在的關(guān)聯(lián)性，這說明可以將進(jìn)行一個(gè)優(yōu)化任務(wù)過程中獲得的知識用于優(yōu)化另一個(gè)任務(wù)，以實(shí)現(xiàn)進(jìn)一步提高目標(biāo)優(yōu)化任務(wù)的性能。不同于已有的多目標(biāo)優(yōu)化方案，本文提出了一種基于進(jìn)化多任務(wù)多目標(biāo)優(yōu)化方法，其核心在于利用進(jìn)化種群間的知識交流，可以實(shí)現(xiàn)不同區(qū)域內(nèi)的任務(wù)卸載方案同時(shí)求解，利用區(qū)域間的潛在相似性加快收斂速度。實(shí)驗(yàn)結(jié)果表明了算法的有效性。

2 系統(tǒng)模型

2.1 模型簡述

終端智能設(shè)備的功能雖然強(qiáng)大，但隨著待處理數(shù)據(jù)量的提升，僅依靠終端自己的計(jì)算能力仍難以滿足需求。隨著個(gè)人終端功能的提升和其他智能設(shè)備的進(jìn)一步普及，對邊緣服務(wù)器的需求愈發(fā)迫切。

基于多任務(wù)進(jìn)化的多應(yīng)用服務(wù)部署的邊緣網(wǎng)絡(luò)系統(tǒng)模型如圖1所示。整個(gè)系統(tǒng)主要分為中心云端、邊緣服務(wù)器端和移動(dòng)設(shè)備端三部分。云端上可以提供用戶所需要的所有服務(wù)，且假定云端上有近乎無限的計(jì)算資源。相較于計(jì)算資源有限的終端設(shè)備，邊緣服務(wù)器往往能夠提供更高的計(jì)算速度。在一定區(qū)域內(nèi)，移動(dòng)設(shè)備可將部分應(yīng)用數(shù)據(jù)分解，卸載至邊緣計(jì)算服務(wù)器進(jìn)行處理，以降低響應(yīng)延時(shí)［22］。

如圖1所示，移動(dòng)設(shè)備與邊緣服務(wù)器之間通過無線方式實(shí)現(xiàn)數(shù)據(jù)傳輸。邊緣服務(wù)器之間通過有線連接，傳輸速度大幅提升，丟包率降低。

假設(shè)一個(gè)特定區(qū)域R內(nèi)有n個(gè)邊緣計(jì)算服務(wù)器和m個(gè)移動(dòng)終端。用戶通過智能終端完成S種類型的任務(wù)，例如數(shù)據(jù)處理、圖像修復(fù)等?？蓪⑷蝿?wù)進(jìn)行分解為不同大小的數(shù)據(jù)包，進(jìn)行分布式處理，以加快處理速度。

考慮到任務(wù)的種類和復(fù)雜程度、任務(wù)可分解為的數(shù)據(jù)包總量，及對應(yīng)的數(shù)據(jù)量、代碼量、復(fù)雜度等特征存在一定的差異。制定合適的資源分配策略，為區(qū)域中的每個(gè)智能終端選取最為合適的處理方式，盡可能縮短任務(wù)處理過程中造成的延時(shí)和能量消耗，即為優(yōu)化目標(biāo)。

2.2 網(wǎng)絡(luò)延時(shí)定義

如表1所示，多個(gè)區(qū)域（R1，R2，…，Rk）內(nèi)的資源分配優(yōu)化問題存在一定的相似性，主要體現(xiàn)在不同的區(qū)域都需要將計(jì)算資源卸載到服務(wù)器上。對于用戶Ui的待處理任務(wù)Qi，設(shè)其可被分解為ci個(gè)子任務(wù)，每個(gè)子任務(wù)的數(shù)據(jù)量為δiw，則用戶Ui的待處理數(shù)據(jù)總量（Di）為

即同時(shí)使K個(gè)邊緣計(jì)算網(wǎng)絡(luò)中的移動(dòng)終端設(shè)備的平均延時(shí)和能耗實(shí)現(xiàn)最小化。

對于每個(gè)獨(dú)立區(qū)域Rk，移動(dòng)設(shè)備可將較為復(fù)雜的任務(wù)進(jìn)行分解，卸載至邊緣服務(wù)器進(jìn)行處理。由于邊緣服務(wù)器具備充足計(jì)算資源，運(yùn)算速度大幅加快。然而，該過程中，移動(dòng)設(shè)備自身需額外消耗能量實(shí)現(xiàn)數(shù)據(jù)上傳和下載，數(shù)據(jù)量過大時(shí)，數(shù)據(jù)傳輸產(chǎn)生的能耗可能會超過由設(shè)備自身進(jìn)行處理。移動(dòng)設(shè)備的儲電量有限，難以支撐過于頻繁的任務(wù)卸載。因此，區(qū)域中的平均能耗 和平均延時(shí)T 難以同時(shí)達(dá)到最小化，一個(gè)目標(biāo)的降低必然以另一個(gè)目標(biāo)的增加為代價(jià)。

盡管不同區(qū)域內(nèi)的移動(dòng)設(shè)備最優(yōu)卸載方案不具有相關(guān)性，不存在數(shù)值關(guān)系，但其邊緣計(jì)算網(wǎng)絡(luò)存在潛在相似性，因此可以相互提供參考，加快優(yōu)化進(jìn)程。在后文中，將進(jìn)一步討論這種相似性。

3基于進(jìn)化多任務(wù)多目標(biāo)優(yōu)化的邊緣計(jì)算任務(wù)卸載算法

3.1 算法框架

MOEA－RP算法的主要步驟如下：

a）對個(gè)體進(jìn)行編碼，得到初始種群P0，隨機(jī)分配技能因子τk（k=1，…，K）；由參考點(diǎn)生成策略，得到參考點(diǎn)集合Z。

b）對初始種群進(jìn)行解碼，由式（4）～（9）計(jì)算初始種群P0中個(gè)體的目標(biāo)函數(shù)值{ 2，…， K}和{ 2，…， K}，初始化理想點(diǎn)Z=［ min， min］。

c）開始迭代。自適應(yīng)學(xué)習(xí)參數(shù)rmp，動(dòng)態(tài)控制不同技能因子τk的個(gè)體交流程度；隨機(jī)選擇父代個(gè)體，通過交叉變異進(jìn)一步擴(kuò)大解空間，得到子代種群St，子代通過繼承策略，保留父代個(gè)體的技能因子；對子代個(gè)體進(jìn)行解碼，計(jì)算其目標(biāo)值 和 ，更新理想點(diǎn)Z；合并父代和子代種群，在參考點(diǎn)集合Z的信息輔助下進(jìn)行非支配排序，保留與初始種群數(shù)量相同的最優(yōu)個(gè)體解。

d）達(dá)到迭代次數(shù)上限，輸出各技能因子對應(yīng)的非支配解，針對不同區(qū)域進(jìn)行解碼，得到各區(qū)域的最優(yōu)任務(wù)卸載方案，以此模擬解決移動(dòng)邊緣場景下的資源分配問題。

3.2 個(gè)體編碼與種群初始化

對于K個(gè)存在邊緣計(jì)算網(wǎng)絡(luò)的區(qū)域R1，R2，…，Rk，其中邊緣計(jì)算服務(wù)器和移動(dòng)設(shè)備的數(shù)量分別為{m1，m2，…，mK}，{n1，n2，…，nK}。待處理的任務(wù)為Q1，Q2，…，Qs，其對應(yīng)的可分解子任務(wù)數(shù)為{c1，c2，…，cS}。

初始種群P0中包含的個(gè)體數(shù)量為N，每個(gè)個(gè)體可通過特殊的解碼方式，轉(zhuǎn)換為針對不同區(qū)域中移動(dòng)終端設(shè)備子任務(wù)分配方案的一個(gè)解。種群中的每個(gè)個(gè)體以大小相同的矩陣形式表示。矩陣的行數(shù)為各區(qū)域內(nèi)移動(dòng)終端設(shè)備數(shù)量的最大值，列數(shù)為待處理的任務(wù)可分解份數(shù)的最大值，即α=max{m1，m2，…，mk，β=max{c1，c2，…，ck}。

以第t代的其中一個(gè)個(gè)體Pti為例：

該最小化問題為一個(gè)凸優(yōu)化問題，可使用一般方式進(jìn)行求解。滿足目標(biāo)的rmpkj取值，即為區(qū)域k與j用戶任務(wù)卸載候選解的相似性度量。

圖2展示了父代個(gè)體pi、pj的交叉過程。隨機(jī)生成位點(diǎn)pos1，pos2∈［1，2，…，β］，其中pos1＜pos2。個(gè)體pi、pj均為矩陣形式，對兩者位于［pos1，pos2］的列進(jìn)行交換，以分別生成子代si、sj。

3.4 個(gè)體解碼與適應(yīng)度計(jì)算

在多任務(wù)算法框架下，種群中個(gè)體經(jīng)過編碼后，不再針對某一特定區(qū)域內(nèi)的任務(wù)分配方案具有實(shí)際意義。因此需通過解碼，使同一個(gè)體可同時(shí)表示多個(gè)分配方案。

令兩個(gè)區(qū)域R1、R2中的邊緣計(jì)算服務(wù)器數(shù)量分別為4、5。分別以節(jié)點(diǎn){0.25，0.5，0.75，1.0}和{0.2，0.4，0.6，0.8，1.0}對個(gè)體中的取值進(jìn)行分段取整，實(shí)現(xiàn)由浮點(diǎn)數(shù)取值到服務(wù)器編號的一一對應(yīng)。對于用戶數(shù)較少的區(qū)域和總?cè)蝿?wù)數(shù)較少的用戶，個(gè)體編碼存在冗余。此時(shí)截?cái)嗌釛壢哂嗖糠郑瑑H采用所需長度進(jìn)行計(jì)算。由此實(shí)現(xiàn)個(gè)體解碼，依據(jù)其技能因子τi，通過式（9）計(jì)算對應(yīng)的目標(biāo)函數(shù)值。

算法2 個(gè)體解碼

輸入：編碼后種群Pt、所有區(qū)域內(nèi)的移動(dòng)邊緣服務(wù)器和移動(dòng)終端設(shè)備的位置和任務(wù)。

輸出：解碼后種群 Pt。

具體計(jì)算服務(wù)器和終端設(shè)備之間的距離：D1，D2，…，Dk

根據(jù)Dk（k=1，…，K）為所有移動(dòng)終端設(shè)備分配服務(wù)器

for 每個(gè)個(gè)體pi do

if picm= =0 then

continue //由設(shè)備自身進(jìn)行處理

else

calculate pos：pcm∈［pos/Dk，（pos+1）/Dk］

picm ←pos //任務(wù)位置

end if

更新解碼的種群：pt←pt ∪ pi*

end for

3.5 非支配排序

通過定義個(gè)體間的支配關(guān)系，依據(jù)其目標(biāo)函數(shù)值對其進(jìn)行排序，以保留最優(yōu)個(gè)體。經(jīng)過交叉變異后，父代Pt和子代St合并組成大小為2N的種群。對于個(gè)體pi和pj，若obj1i＜o(jì)bj1j且obj2i＜o(jì)bj2j，則稱個(gè)體pj被個(gè)體pi支配。彼此間不存在支配關(guān)系的個(gè)體集合構(gòu)成非支配平面的同一層級。均勻生成［0，π/2］的K個(gè)參考點(diǎn)，與需要在第l層選擇的候選解數(shù)目相同。生成的參考點(diǎn)均勻分布在兩個(gè)目標(biāo)函數(shù)所成的超平面上。其中第k個(gè)參考點(diǎn)與x軸所成的角度為kπ/2K。標(biāo)準(zhǔn)化讓兩個(gè)目標(biāo)函數(shù)值處同一個(gè)量級。兩個(gè)目標(biāo)函數(shù)標(biāo)準(zhǔn)化后的值均落在［0，1］，與x軸所成的角度為θ。

保留過程，即在最后一層中選出K個(gè)個(gè)體。首先計(jì)算出每個(gè)個(gè)體兩個(gè)目標(biāo)函數(shù)標(biāo)準(zhǔn)化后所成角度的余弦函數(shù)值，將上述求得的角度的余弦函數(shù)值的絕對值之差作為個(gè)體到各參考點(diǎn)間的距離，其中距離最小的一個(gè)即為個(gè)體對應(yīng)的參考點(diǎn)。若多個(gè)個(gè)體與同一個(gè)參考點(diǎn)對應(yīng)，則僅保留其中距離最小的一個(gè)個(gè)體。參考點(diǎn)圖示如圖3所示。

結(jié)合預(yù)先生成的參考點(diǎn)角度和參考點(diǎn)集合Z確定個(gè)體所在的范圍［θα，θβ］，θα和θβ為相鄰的兩個(gè)參考點(diǎn)－理想點(diǎn)連線到坐標(biāo)軸的角度。分別計(jì)算θ與左右界限的差值，取其中較小的為其對應(yīng)的距離：

將式（16）的距離單調(diào)遞增排序，即θi＜θj，i＜j。將距離個(gè)體最近的參考點(diǎn)與之關(guān)聯(lián)。最后，根據(jù)K個(gè)參考點(diǎn)保留相應(yīng)的K個(gè)最優(yōu)個(gè)體。優(yōu)先保留最近的個(gè)體，若多個(gè)個(gè)體與同一個(gè)參考點(diǎn)對應(yīng)，則僅保留其中距離最小的一個(gè)個(gè)體。若一次排序沒有保留K個(gè)，則二次順延保留，直到保留K個(gè)個(gè)體，得到K個(gè)最均勻最優(yōu)個(gè)體。

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

3.6.1 參數(shù)設(shè)置及對比算法

將區(qū)域R1和R2內(nèi)的用戶任務(wù)分配為同時(shí)處理的兩個(gè)優(yōu)化問題。區(qū)域大小均為 200×200。其中區(qū)域R1中的邊緣服務(wù)器數(shù)量為4，坐標(biāo)分別為［50，50］、［50，150］、［150，50］、［150，150］。區(qū)域R2中的邊緣服務(wù)器數(shù)量為5，在上述位置基礎(chǔ)上，增設(shè)服務(wù)器［100，100］。區(qū)域內(nèi)用戶數(shù)為200～1 200，用戶位置隨機(jī)生成。

設(shè)置種群大小為100，參考點(diǎn)數(shù)量與種群大小相同。交叉因子μc=0.9，變異因子μm=0.1。每種參與對比的算法獨(dú)立運(yùn)行次數(shù)為20。服務(wù)器與用戶設(shè)備的相關(guān)參數(shù)如表2所示。仿真實(shí)驗(yàn)的運(yùn)行環(huán)境如表3所示。

3.6.2 評價(jià)指標(biāo)

本文選擇反轉(zhuǎn)世代距離IGD作為量化指標(biāo)[23]，以對算法的收斂效果進(jìn)行評價(jià)。

其中：PF為算法在最后一次迭代中得到的非支配解集；|PF|為非支配解的總數(shù)；PF為所有參與計(jì)算的算法在多次獨(dú)立運(yùn)行過程中得到的非支配解集，統(tǒng)一進(jìn)行非支配排序后的最優(yōu)解集合，采用該集合作為測試場景的最優(yōu)解集。該集合中的解對應(yīng)的平均延時(shí) 和平均功耗 均小于其他解。

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

本文選取經(jīng)典的多任務(wù)進(jìn)化算法MOMFEA ［24］、MOMFEA－Ⅱ［2５］和基于參考點(diǎn)的NSGA－Ⅲ［26］作為對比算法。其中 NSGA－Ⅲ作為每次處理一個(gè)優(yōu)化問題的單任務(wù)優(yōu)化算法，分別在用于測試的兩個(gè)區(qū)域上進(jìn)行計(jì)算，比較結(jié)果如下。

圖4、5展示了區(qū)域內(nèi)用戶數(shù)量階梯式遞增時(shí)，平均等待延時(shí)和平均設(shè)備能耗的最小值。由圖可知，能耗和延時(shí)均隨用戶數(shù)量遞增而有所增加，主要原因?yàn)橛脩裘芏仍鲩L帶來的局部傳輸速度下降。MOEA－RP算法在區(qū)域R1和R2內(nèi)均使兩個(gè)目標(biāo)實(shí)現(xiàn)最小，且相較其他對比算法具有明顯優(yōu)勢。

表4列出了算法在不同仿真示例中的IGD值，由于IGD能在一定程度上反映最優(yōu)解的收斂性和均勻性，數(shù)值越小，與真實(shí)非支配平面越接近。相較于對比算法，MOEA－RP在多個(gè)示例中均得到最小IGD值，說明算法收斂性較好，且性能較為穩(wěn)定。

圖6、7分別展示了獨(dú)立運(yùn)行過程中，區(qū)域R1和R2中MOEA－RP與對比算法同平均IGD值最接近的非支配平面。算法 MOEA－RP同時(shí)使兩個(gè)區(qū)域內(nèi)的平均延時(shí)和能耗降低到更優(yōu)值，且相較其他算法具有明顯優(yōu)勢。

相較于單任務(wù)算法NSGA－Ⅲ，算法MOEA－RP借助多任務(wù)思想，自適應(yīng)學(xué)習(xí)參數(shù)，充分利用不同子任務(wù)的種群相似性，使具有不同技能因子的個(gè)體相互促進(jìn)收斂，從而有效擴(kuò)大搜索解空間，加快收斂速度。相較于多任務(wù)算法MOMFEA和MOMFEA－Ⅱ，MOEA－RP在進(jìn)行非支配排序時(shí)，使用預(yù)先生成的參考點(diǎn)提供額外信息，與不斷更新的理想點(diǎn)共同為種群中的個(gè)體提供方向指引，從而在保證解的收斂性的前提下，兼顧均勻性，得到更具有代表性的非支配解。

4 結(jié)束語

針對區(qū)域內(nèi)用戶的任務(wù)卸載方案部署優(yōu)化問題，本文建立服務(wù)器－用戶設(shè)備的系統(tǒng)模型，并提出一種基于多任務(wù)多目標(biāo)進(jìn)化的算法MOEA－RP算法，以設(shè)備平均延時(shí)和能耗為目標(biāo)，構(gòu)建了一個(gè)多目標(biāo)問題，通過求解該多目標(biāo)問題，可以獲得一組邊緣計(jì)算下的服務(wù)部署方案。并且利用任務(wù)之間的相似性，在任務(wù)之間進(jìn)行高效的知識遷移。設(shè)計(jì)相應(yīng)編解碼策略，實(shí)現(xiàn)對目標(biāo)函數(shù)的求解。同時(shí)在多個(gè)測試實(shí)例上進(jìn)行算法性能的驗(yàn)證相較于對比算法，在收斂速度和收斂效果及最優(yōu)解分布的均勻性上均取得較好效果。下一步將尋求與相關(guān)企業(yè)的合作，驗(yàn)證算法在具體應(yīng)用場景的效果。

參考文獻(xiàn)：

［1］徐佳， 李學(xué)俊， 丁瑞苗， 等. 移動(dòng)邊緣計(jì)算中能耗優(yōu)化的多重資源計(jì)算卸載策略［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2019，25 （4）： 954－961. （Xu Ji Li Xuejun， Ding Ruimiao， et al. Energy efficient multi－resource computation offloading strategy in mobile edge computing［J］.Computer Integrated Manufacturing Systems ， 2019，25 （4）： 954－961.）

［2］Shu Chang， Zhao Zhiwei， Han Yunpeng， et al. Multi－user offloading for edge computing networks： a dependency－aware and latency－optimal approach［J］.IEEE Internet of Things Journal ， 2019， 7 （3）： 1678－1689.

［3］簡琤峰， 陳家煒， 張美玉. 面向邊緣計(jì)算的改進(jìn)混沌蝙蝠群協(xié)同調(diào)度算法［J］. 小型微型計(jì)算機(jī)系統(tǒng)， 2019，40 （11）： 2424－2430. （Jian Chengfeng， Chen Jiawei， Zhang Meiyu. Improved chao－tic bat swarm cooperative scheduling algorithm for edge computing［J］.Journal of Chinese Computer Systems ， 2019， 40 （11）： 2424－2430.）

［4］Ali Z， Jiao L， Baker T，et al.A deep learning approach for energy efficient computational offloading in mobile edge computing［J］.IEEE Access ， 2019， 7 ： 149623－149633.

［5］Vu T T， Huynh N V， Hoang D T， et al. Offloading energy efficiency with delay constraint for cooperative mobile edge computing networks［C］//Proc of IEEE Global Communications Conference. Piscataway， NJ： IEEE Press， 2018： 1－6.

［6］Vu T T， Huynh N V， Hoang D T， et al. Offloading energy efficiency with delay constraint for cooperative mobile edge computing networks［C］//Proc of IEEE Global Communications Conference. Piscataway， NJ： IEEE Press， 2018： 1－6.

［7］Mao Yuyi， Zhang Jun， Letaief K B. Dynamic computation offloading for mobile－edge computing with energy harvesting devices［J］.IEEE Journal on Selected Areas in Communications，2016， 34 （12）： 3590－3605.

［8］Wei Feng， Chen Sixuan， Zou Weixia. A greedy algorithm for task offloading in mobile edge computing system［J］.China Communications ， 2018， 15 （11）： 149－157.

［9］Li Guangshun， Yao Yonghui， Wu Junhua，et al.A new load balancing strategy by task allocation in edge computing based on interme－diary nodes［J］.EURASIP Journal on Wireless Communications and Networking ， 2020，2020 （1）： article No.3.

［10］Yan Ji Bi Suzhi， Huang Liang， et al. Deep reinforcement learning based offloading for mobile edge computing with general task graph［C］//Proc of IEEE International Conference on Communications. Piscataway， NJ： IEEE Press， 2020： 1－7.

［11］張艮山， 劉旭寧. 資源受限移動(dòng)邊緣計(jì)算任務(wù)拆分卸載調(diào)度決策［J］. 計(jì)算機(jī)應(yīng)用與軟件， 2019， 36 （10）： 268－273，278. （Zhang Genshan， Liu Xuning. Tasks split and offloading scheduling decision in mobile edge computing with limited resources［J］.Computer Applications and Software，2019， 36 （10）： 268－273，278.）

［12］Sun Lu， Wang Jie， Lin Bin. Task allocation strategy for MEC－ enabled IIoTs via Bayesian network based evolutionary computation［J］.IEEE Trans on Industrial Informatics ， 2020， 17 （5）： 3441－3449.

［13］代美玲， 劉周斌， 郭少勇， 等. 基于終端能耗和系統(tǒng)時(shí)延最小化的邊緣計(jì)算卸載及資源分配機(jī)制［J］. 電子與信息學(xué)報(bào)， 2019，41 （11）： 2684－2690. （Dai Meiling， Liu Zhoubin， Guo Shaoyong， et al. A computation offloading and resource allocation mechanism based on minimizing devices energy consumption and system delay［J］.Journal of Electronics amp; Information Technology ， 2019，41 （11）： 2684－2690.）

［14］Li Yunzhao， Qi Feng， Wang Zhili，et al.Distributed edge computing offloading algorithm based on deep reinforcement learning［J］.IEEE Access，2020， 8 ： 85204－85215.

［15］Lei Lei， Xu Huijuan， Xiong Xiong， et al. Joint computation offloa－ding and multiuser scheduling using approximate dynamic programming in NB－IoT edge computing system［J］.IEEE Internet of Things Journal ， 2019， 6 （3）： 5345－5362.

［16］Rui Lanlan， Yang Yingtai， Gao Zhipeng， et al. Computation offloa－ding in a mobile edge communication network： a joint transmission delay and energy consumption dynamic awareness mechanism［J］.IEEE Internet of Things Journal，2019，6 （6）： 10546－10559.

［17］Sufyan F， Banerjee A. Computation offloading for distributed mobile edge computing network： a multiobjective approach［J］.IEEE Access ， 2020，8 ： 149915－149930.

［18］Yang Song， Li Fan， Shen Meng，et al.Cloudlet placement and task allocation in mobile edge computing［J］.IEEE Internet of Things Journal，2019， 6 （3）： 5853－5863.

［19］Ning Zhaolong， Dong Peiran， Wang Xiaojie，et al.Deep reinforcement learning for vehicular edge computing： an intelligent offloading system［J］.ACM Trans on Intelligent Systems and Technology ， 2019， 10 （6）： 1－24.

［20］Wang Weixu， Ge Shuxin， Zhou Xiaobo. Location－privacy－aware ser－vice migration in mobile edge computing［C］//Proc of IEEE Wireless Communications and Networking Conference. Piscataway， NJ： IEEE Press， 2020： 1－6.

［21］Chen Yishan， Deng Shuiguang， Ma Hongtao，et al.Deploying data－intensive applications with multiple services components on edge［J］.Mobile Networks and Applications ， 2020， 25 （2）： 426－441.

［22］Song Fuhong， Xing Huanlai， Luo Shouxi，et al.A multiobjective computation offloading algorithm for mobile－edge computing［J］.IEEE Internet of Things Journal ， 2020， 7 （9）： 8780－8799.

［23］Deb K， Pratap Agarwal S，et al.A fast and elitist multiobjective genetic algorithm： NSGA－Ⅱ［J］.IEEE Trans on Evolutionary Computation ， 2002， 6 （2）： 182－197.

［24］Gupta Ong Y S， Feng Liang，et al.Multiobjective multifactorial optimization in evolutionary multitasking［J］. IEEE Trans on Cybernetics，2016，47 （7）： 1652－1665.

［25］Bali K K， Gupta Ong Y S，et al.Cognizant multitasking in multiobjective multifactorial evolution： MOMFEA－Ⅱ［J］.IEEE Trans on Cybernetics，2020，51 （4）： 1784－1796.

［26］Deb K， Jain H. An evolutionary many－objective optimization algorithm using reference－point－based nondominated sorting approach， part I： solving problems with box constraints［J］. IEEE Trans on Evolutionary Computation ， 2013， 18 （4）： 577－601.

［27］唐楓， 馮翔， 虞慧群. 基于自適應(yīng)知識遷移與資源分配的多任務(wù)協(xié)同優(yōu)化算法［J］. 計(jì)算機(jī)科學(xué)， 2022， 49 （7）： 254－262. （Tang Feng， Feng Xiang， Yu Huiqun. Multi－task cooperative optimization algorithm based on adaptive knowledge transfer and resource allocation［J］.Computer Science，2022， 49 （7）： 254－262.）

［28］Zhang Xingyi， Tian Ye， Cheng Ran，et al.An efficient approach to nondominated sorting for evolutionary multiobjective optimization［J］.IEEE Trans on Evolutionary Computation ， 2014， 19 （2）： 201－213.

收稿日期：2023－08－20；修回日期：2023－09－26基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61972456）

作者簡介：孔珊（1988—），女，河南開封人，講師，主要研究方向?yàn)槎嗄繕?biāo)優(yōu)化、邊緣計(jì)算（kongshan@zznu.edu.cn）；鄭玉琦（1996—），女，碩士研究生，主要研究方向?yàn)檫M(jìn)化計(jì)算及其在邊緣計(jì)算中的應(yīng)用．