章剛 胡鵬

摘 要：算力邊緣服務(wù)器部署問題是構(gòu)建算力網(wǎng)絡(luò)的基礎(chǔ)性問題。在實踐過程中，算力邊緣服務(wù)器靠近算力資源并為其加入算力網(wǎng)絡(luò)提供接入服務(wù)。然而，算力資源的整體結(jié)構(gòu)往往由現(xiàn)實需求所決定，并時刻隨需求的變化而變化。在算力邊緣服務(wù)器資源有限的情況下，如何合理部署算力邊緣服務(wù)器，使得其能夠保障算力網(wǎng)絡(luò)有效地建設(shè)已成為當(dāng)前各界所關(guān)注的熱點。首先，對算力邊緣服務(wù)器部署問題進行分析，并將其轉(zhuǎn)換為帶約束的多目標優(yōu)化問題。針對該問題，提出一種改進型遺傳算法予以解決。該算法優(yōu)點在于：尋找無重復(fù)可行解作為初始種群，為選擇操作提供了更多挑選的余地；選擇時，采用個體均衡選擇策略，保證了迭代群體的多樣化與分散化；交叉和變異時，分別采用不同種類的隨機兩點交叉與輪流隨機單點變異的策略，從而保障了新生種群的多元性與多樣性。實驗從算力資源總量偏差率、負載平衡誤差率、收斂率、期望最優(yōu)解誤差率四個方面驗證，該算法適合應(yīng)用于算力邊緣服務(wù)器的部署。

關(guān)鍵詞：算力邊緣服務(wù)器； 算力網(wǎng)絡(luò)； 部署問題； 遺傳算法； 帶約束的多目標優(yōu)化

中圖分類號：TP393 文獻標志碼：A?文章編號：1001-3695（2024）05-035-1527-05

doi：10.19734/j.issn.1001-3695.2023.08.0391

Computing first edge server deployment algorithm for computing first network

Abstract：The problem of computing first edge server deployment is a fundamental problem in computing first network. In the actual scenario， the computing first edge server is close to computing power resources and provides access services for them to join the computing first network. However， the structure of computing resources is often determined by the actual demand， and changes with the change of demand. Under the constraint of computing first edge server resources， how to reasonably deploy computing first edge servers to ensure the effective construction of computing networks has become a hot topic of concern for all sectors. Firstly， this paper analyzed the deployment problem of computing first edge servers and transformed it into a multi-objective optimization problem with constraints. It proposed an improved genetic algorithm to address this issue. The advantages of this algorithm were as follows. It found non repetitive feasible solutions as the initial population provided more room for selection operations. When selecting， it adopted an individual balanced selection strategy to ensure the diversity and decentra-lization of the iterative population. When crossing and mutating，it adopted different types of random two point crossing and rotating random single point mutation strategies， thereby ensuring the diversity and diversity of the newborn population. The experiments is verified by resources deviation rate， load error rate， convergence rate. And expectation solution error rate shows that the algorithm is very effective and reasonable.

Key words：computing first edge server（CFES）; computing first network（CFN）; deployment problem; genetic algorithm; multi-objective optimization with constraints

0 引言

2021年，國家發(fā)改委等四部委聯(lián)合出臺《全國一體化大數(shù)據(jù)中心協(xié)同創(chuàng)新體系算力樞紐實施方案》 ，明確指出要變革現(xiàn)有網(wǎng)絡(luò)傳輸能力，提升跨區(qū)域算力調(diào)度水平，從而構(gòu)建起滿足新一輪數(shù)字經(jīng)濟發(fā)展的國家算力網(wǎng)絡(luò)體系——算力網(wǎng)絡(luò)（CFN）。算力網(wǎng)絡(luò)的建設(shè)既是國家、社會發(fā)展的戰(zhàn)略要求，又是當(dāng)前經(jīng)濟轉(zhuǎn)型發(fā)展的新機遇［1～3］。

作為重大基礎(chǔ)設(shè)施，算力網(wǎng)絡(luò)要真正意義上實現(xiàn)依然存在一系列基礎(chǔ)性問題需要解決。其中，算力邊緣服務(wù)器部署問題（computing first edge server deployment problem，CFESDP）便是眾多基礎(chǔ)性問題之一［4，5］。

首先，算力（包括云、邊、端等算力）是一種新型生產(chǎn)資源，其能夠被放置在企業(yè)各個生產(chǎn)部門周圍，為企業(yè)實現(xiàn)智能化、數(shù)字化轉(zhuǎn)型提供重要的算力保障，因此受到企業(yè)界高度關(guān)注，從而大力推動了算力發(fā)展。但由于缺乏算力構(gòu)建的行業(yè)標準，使得當(dāng)前算力的發(fā)展過于雜亂無序化，這不僅造成算力資源重復(fù)建設(shè)，而且也使算力資源過度分散。

算力邊緣服務(wù)器（CFES）是一種部署在算力資源附近且為算力資源提供網(wǎng)絡(luò)接入服務(wù)的廉價服務(wù)器，其能夠有效組織雜亂無章的算力資源，并把這些算力資源統(tǒng)一按序接入到算力網(wǎng)絡(luò)中?？芍?，算力邊緣服務(wù)器在算力網(wǎng)絡(luò)構(gòu)建過程中發(fā)揮著極其重要的作用。

然而，在實際過程中，企業(yè)各個生產(chǎn)部門往往受到市場需求的影響而時刻發(fā)生結(jié)構(gòu)性調(diào)整，這種部門結(jié)構(gòu)性調(diào)整也直接迫使服務(wù)于各個生產(chǎn)部門的算力資源相應(yīng)地動態(tài)調(diào)整，且這種調(diào)整是被動的、難以預(yù)測的。由于算力資源的整體結(jié)構(gòu)存在動態(tài)變化的可能，作為部署在算力資源附近且資源有限的算力邊緣服務(wù)器必須具備靈活部署的能力，才能保障算力網(wǎng)絡(luò)的有效建設(shè)。由此可知，算力邊緣服務(wù)器的靈活部署能力是構(gòu)建算力網(wǎng)絡(luò)的前提和基礎(chǔ)，且依此產(chǎn)生的算力邊緣服務(wù)器部署問題（CFESDP）正逐漸成為算力網(wǎng)絡(luò)的熱點問題。

算力邊緣服務(wù)器部署問題是指在部署成本有限的情況下，如何合理部署CFES，使CFES所接入的算力資源總量最大的同時總負載最小［5］。

需要指出的是，除算力網(wǎng)絡(luò)外，CFESDP問題還常見于諸如工業(yè)邊緣智能、移動邊緣計算等領(lǐng)域。因此，研究CFESDP問題具有廣泛的理論與現(xiàn)實意義。

現(xiàn)階段，關(guān)于CFESDP問題的討論，可從以下兩個方面進行梳理：

a）算力網(wǎng)絡(luò)方面。算力網(wǎng)絡(luò)建設(shè)問題自被提出以來，便成為學(xué)術(shù)界和產(chǎn)業(yè)界所關(guān)注的重點。但由于算力網(wǎng)絡(luò)是一個全新的研究領(lǐng)域，相關(guān)技術(shù)知識儲備不足，所以基礎(chǔ)研究的進展相當(dāng)緩慢。目前，主要的研究中心在于算力網(wǎng)絡(luò)的系統(tǒng)體系結(jié)構(gòu)設(shè)計方面，而關(guān)于CFESDP問題的討論基本空白［1，4，6］。

b）其他相關(guān)應(yīng)用領(lǐng)域方面。（a）工業(yè)邊緣智能方面。文獻［7］嘗試把霧計算服務(wù)器引入到工業(yè)制造領(lǐng)域的邊緣，為后期工業(yè)生產(chǎn)提供邊緣智能服務(wù)奠定基礎(chǔ)，但其具有強烈的局部性和特殊性，并不適合解決CFESDP問題。文獻［8］探討了工業(yè)生產(chǎn)設(shè)備實時運維問題，為討論方便，該文把實時運維問題進行轉(zhuǎn)換，并提出一種啟發(fā)式部署算法來解決，但并未對問題轉(zhuǎn)換的合理性進行闡述，從而使得算法的有效性未被論證。（b）移動邊緣計算方面。文獻［9］討論移動邊緣計算以虛擬機形式在用戶近端部署服務(wù)的問題，提出一種分治式部署算法，目的是提高邊緣側(cè)的服務(wù)資源利用率以及控制系統(tǒng)流量，但這種基于差異化思想的部署算法無法推廣到算力網(wǎng)絡(luò)中。文獻［10］把分類思想應(yīng)用于具體的場景部署中，但該種做法存在必要的前提，就是移動用戶群體分布形態(tài)必須滿足分類思想，這是一種理想化的假設(shè)，不具備普遍性。文獻［11］試圖從某特定場景出發(fā)，通過預(yù)測手段畫出移動用戶的遷移軌跡，并基于遷移軌跡確定潛在的邊緣服務(wù)器部署位置，但這種部署模式無法在算力網(wǎng)絡(luò)中復(fù)制。文獻［12］分析了移動邊緣計算架構(gòu)下的虛擬網(wǎng)絡(luò)功能管理器的部署問題，提出一種分布式部署方案解決，但該方案由于需要時刻采集與分析邊緣端服務(wù)器的信息，勢必會增加邊緣端服務(wù)器的負載，這與CFESDP問題相沖突。

綜上，已有研究成果要么忽略CFESDP問題的討論，要么雖有討論但都不適合解決CFESDP問題?；诖?，本文通過分析CFESDP問題的特性并提出一種啟發(fā)式算法，即改進型遺傳算法（improved genetic algorithm for computing first network，IGACFN）予以解決。

1 問題描述

本文選用多目標優(yōu)化模型描述CFESDP問題，其理由是：a）這與問題自身性質(zhì)有關(guān)，通過分析問題，發(fā)現(xiàn)多目標優(yōu)化模型能夠更加清晰地闡述該問題的內(nèi)涵，也為該問題的求解提供了便利；b）通過對已有的研究成果梳理發(fā)現(xiàn)，目前關(guān)于該問題的求解，絕大部分都優(yōu)先采用多目標優(yōu)化模型建模，這是一種主流方法。具體建模情況如下：

根據(jù)統(tǒng)計，目前企業(yè)所使用的算力資源主要分為云算力、邊緣算力以及端算力三種資源。為方便討論，假設(shè)云、邊、端等算力都可以通過一組相同評估指標進行算力度量，那么令集合Val={Cmp，CmpE，NetP，MemP}為評估算力的指標集。其中：Cmp表示每秒浮點運算次數(shù)；CmpE表示每單位能耗所產(chǎn)生的算力；NetP表示每秒能夠傳輸?shù)谋忍匚粩?shù)；MemP表示存儲單元個數(shù)。

再假定Cloud={Cloud1，Cloud2，…，Cloud|Cloud|}表示一組云算力集合，|Cloud|表示云算力總量；EdgC={EdgC1，EdgC2，…，EdgC|EdgC|}表示一組邊緣算力集合，|EdgC|表示邊緣算力總量；End={End1，End2，…，End|End|}表示一組端算力集合，|End|表示端算力總量；CFES={CFES1，CFES2，…，CFES|CFES|}表示一組算力邊緣服務(wù)器，|CFES|表示算力邊緣服務(wù)器的總數(shù)；令對任意算力邊緣服務(wù)器CFESj而言，其可以為云算力、邊緣算力以及端算力等任意算力提供接入服務(wù)，而且對任意算力（云或邊或端）而言，其可以接入到任意CFESj中，但同一時刻只能有一個邊緣服務(wù)器為之響應(yīng)。

CFESDP問題為：給定一組云算力集合Cloud、邊緣算力集合EdgC、端算力集合End，以及算力邊緣服務(wù)器集合CFES，在部署成本CostCFES 有限的情況下，尋找一種算力邊緣服務(wù)器部署方案，使得所接入算力資源的總量CFCFES最大，并使得算力邊緣服務(wù)器的總負載LoadCFES最小。依據(jù)問題描述，可得

s.t. CostCFES （x）∈（0，COST］

其中：x表示部署候選方案；COST表示成本的閾值。

1）算力資源的總量 指所有算力邊緣服務(wù)器所接入的算力資源量總和，可按如下公式計算：

2）算力邊緣服務(wù)器的總負載 指所有算力邊緣服務(wù)器的負載總和，可按如下公式計算：

綜上分析可知，CFESDP問題屬于帶約束的多目標優(yōu)化問題。該問題是一類難問題，本文提出一種啟發(fā)式算法（即改進型遺傳算法IGACFN）予以解決。

2 算法描述

2.1 經(jīng)典遺傳算法

經(jīng)典遺傳算法（genetic algorithm，GA）［13］是一種模擬自然界生物進化過程與機制的全局概率優(yōu)化搜索算法，廣泛應(yīng)用于多目標優(yōu)化、工程制造等領(lǐng)域。

本文之所以采用經(jīng)典遺傳算法作為解決問題的基礎(chǔ)算法，理由是：a）多目標優(yōu)化問題的求解本質(zhì)上就是在解空間內(nèi)搜索最優(yōu)解的過程，相對其他啟發(fā)式算法，經(jīng)典遺傳算法不僅能夠簡便地表示解，而且能夠通過交叉與變異操作快速對解迭代，從而高效地完成最優(yōu)解的搜索，求解效率優(yōu)于其他啟發(fā)式算法；b）隨著研究的深入，未來CFESDP問題必將被高維化，但問題的內(nèi)涵不會發(fā)生改變，依然屬于多目標優(yōu)化類問題，經(jīng)典遺傳算法在求解高維問題時同樣具有不可比擬的優(yōu)勢，為保證此類問題求解方法的一致性與連貫性，降低后期研究的難度，本文優(yōu)先選擇經(jīng)典遺傳算法作為基礎(chǔ)算法。

但經(jīng)典遺傳算法在解決CFESDP問題時，容易陷入到局部最優(yōu)解當(dāng)中，因而提出IGACFN算法，在優(yōu)化相關(guān)問題的同時解決CFESDP問題。

2.2 IGACFN算法描述

IGACFN算法的主要思想為：a）為豐富選擇的多樣性，首先生成一組無重復(fù)可行根（個體）構(gòu)成初始種群，可提高最優(yōu)解命中率；b）個體選擇時，從全局和局部兩個維度依次挑選不同種類的個體組成迭代群體，保證了被選群體多元化和分散化；c）交叉操作時，通過組合不同種類的個體隨機交叉操作，維系了新生群體的多樣性；d）變異操作時，對交叉操作產(chǎn)生的不同種類的新個體，輪流實現(xiàn)隨機變異操作，不僅提升了局部深挖能力，還進一步豐富了群體的多樣性。

2.2.1 編碼方式

由于CFESDP問題的本質(zhì)就是集合中的子集劃分問題（除空集外），當(dāng)子集被選中時用二進制數(shù)“1”表示，當(dāng)子集未被選中時則用二進制數(shù)“0”表示，所以一個候選解可用一組二進制數(shù)表達。依據(jù)此思想，二進制數(shù)編碼方式為本文首選。

2.2.2 初始化種群

通常，種群由一組個體（解）構(gòu)成，本文采用多次無重復(fù)可行根策略產(chǎn)生種群，具體過程如下：

a）設(shè)置變量數(shù)組Div〈·〉用于保存可行解，確定最大循環(huán)次數(shù)，轉(zhuǎn)入步驟b）。

b）隨機產(chǎn)生一組個體，依據(jù)式（1）的約束條件0

c）依次遍歷Div〈·〉中所存入的可行解，剔除與x相同的解，轉(zhuǎn)入步驟d）。

d）判定是否滿足最大循環(huán)次數(shù)，如果不滿足，則轉(zhuǎn)入步驟b），否則退出初始化過程。

2.2.3 適應(yīng)度函數(shù)

遺傳算法中的適應(yīng)度函數(shù)用于評價每個被選個體的好壞，被選個體的評價越好（即滿足約束條件的同時使得函數(shù)值越優(yōu)）則適應(yīng)度函數(shù)值越大；反之，則適應(yīng)度函數(shù)值越小。依據(jù)式（1），適應(yīng)度函數(shù)f（x）可定義為

其中：φcost（x）表示為懲罰因子；rcost代表懲罰程度；x表示候選解（個體）。

2.2.4 選擇策略

本文采用個體均衡選擇策略：a）從全局角度，通過混合式選擇較優(yōu)個體與較差個體組成迭代群體；b）從局部角度，對同一類的被選個體而言，被選個體之間盡可能地分散，保持一定距離。該策略的目的是保證被選群體多樣化和分散化，為避免陷入局部最優(yōu)打下基礎(chǔ)。

1）全局選擇

a）較優(yōu)個體指適應(yīng)度函數(shù)f（x）值最優(yōu)的那部分個體，通過隨機機制選擇該部分個體作為迭代群體。

b）較差個體指除較優(yōu)個體之外，適應(yīng)度函數(shù)f（x）值、CFCFES（x）值以及LoadCFES（x）值較差的個體，該部分個體的選擇按以下方式操作：

（a）計算所有較差個體的f（x）值、CFCFES（x）值以及LoadCFES（x）值，計算結(jié)果分別按照從小到大排序；

（b）對任意被選個體xj而言，根據(jù)式（6）計算其各自適應(yīng)度比：

2）局部選擇。

對任意被選個體xj而言，為保證其盡可能分散，按如下方式操作：

設(shè)Dp·，xj」表示為被選個體xj在同一種類中的擁擠度，則其可表達為

其中：Dp［xi，xj］表示xj與同一類的被選個體xj之間的距離；k表示被選個體的維度；|x0|表示同一種類中被選個體的總數(shù)。當(dāng)Dp［·，xj］越小，說明被選個體xj的擁擠度越小，分散程度越高。依據(jù)分散程度的結(jié)果，被選個體xj的最終被選概率PF（xj）可按如下公式計算：

其中：Q表示擁擠度的閾值，一般為間隔距離均值的倒數(shù)。

2.2.5 交叉與變異操作

1）交叉規(guī)則

全局搜索能力與交叉操作密切相關(guān)，為提升算法的全局搜索力，本文采用不同種類隨機兩點交叉策略，具體過程如下：

a）根據(jù)選擇策略確定迭代群體后，從迭代群體集中隨機選擇一個較優(yōu)個體與一個較差個體兩兩組合，直至所有個體都完成組合。

b）隨機確定交叉操作的起點與終點，然后把較優(yōu)個體x的起點與終點之間的部分基因與較差個體y的相同部分基因?qū)崿F(xiàn)相互交換，從而完成交叉操作，如圖1所示。

c）對交叉操作所形成的新個體，根據(jù)式（1）的約束條件0

交叉操作的目的是維持種群多樣性，同時提升全局搜索能力。

2）變異規(guī)則

局部搜索能力與變異操作密切相關(guān)，為提升算法的局域性深挖能力，進一步豐富群體的多樣性，本文采用不同種類輪流隨機單點變異策略，具體過程如下：

a）基于上述交叉操作的結(jié)果，把新產(chǎn)生的群體按照較優(yōu)與較差兩種類別劃分，每類個體依據(jù)f（x）、CFCFES（x）以及LoadCFES（x）三個維度分別排序。

b）對較優(yōu)類與較差類中每個個體xj，基于式（6）分別計算Fitnessf（xj）、FitnessCF（xj）以及FitnessLoad（xj），并進一步按照式（11）計算其各自累積適應(yīng)度比：

c）依據(jù)式（12）計算每個個體xj的平均累積適應(yīng)度比：

d）依次輪流對較優(yōu)類和較差類操作。創(chuàng)建一個隨機數(shù)，如果該隨機數(shù)落在不同個體平均累積適應(yīng)度比之間，則取平均累積適應(yīng)度比高的個體作為待變異個體。

e）基于隨機單點變異思想，對待變異個體進行變異操作。

f）對變異操作所形成的新個體，根據(jù)式（1）的約束條件0

變異操作的目的是提升算法的局部深挖能力，進一步豐富群體的多樣性。

2.2.6 IGACFN算法過程

a）依據(jù)2.2.1和2.2.3節(jié)分別確定編碼方式以及適應(yīng)度函數(shù)，初始化參數(shù)rcost和σ，設(shè)定種群規(guī)模以及迭代次數(shù)，轉(zhuǎn)入步驟b）。

b）依據(jù)多次無重復(fù)可行根策略產(chǎn)生初始種群，并通過適應(yīng)度函數(shù)f（x）計算其適應(yīng)度值，轉(zhuǎn)入步驟c）。

c）根據(jù)式（6）～（10）選擇迭代群體，轉(zhuǎn)入步驟d）。

d）對迭代群體按照2.2.5節(jié)實現(xiàn)交叉與變異操作，產(chǎn)生下一代種群，并依據(jù)適應(yīng)度函數(shù)計算該種群的適應(yīng)度值，轉(zhuǎn)入步驟e）。

e）檢查當(dāng)前情況是否達到退出條件，如果達到，保存搜索到的解集并退出；否則轉(zhuǎn)入步驟c）。

2.2.7 算法有效性分析

算法初始化時期，尋找一組無重復(fù)可行解組成初始種群，不僅提供了更多種選擇，而且提升了最優(yōu)解命中率；選擇操作時期，從全局層面和局部層面有目的地混合式選擇較優(yōu)個體與較差個體，從而保證了種群多樣化和分散化；交叉操作時期，通過組合較優(yōu)個體與較差個體隨機交叉操作并對新個體檢驗其合理性，從而維系了種群的多元性；變異操作時期，對較優(yōu)新個體與較差新個體輪流實現(xiàn)隨機單點變異操作，并檢驗其合理性，從而進一步保障種群的多元性和多樣性，并有效提高了算法的局部搜索能力。綜上，算法在每次迭代過程中，不僅保證了種群的豐富性，而且保證了其有效性。

3 實驗與分析

1）軟硬件環(huán)境 5臺曙光系列服務(wù)器，CPU型號為AMD Opteron 4122，內(nèi)存8 GB，SATA硬盤300 GB，操作系統(tǒng)為RedHat Enterprise Linux 4.3。

2）關(guān)鍵參數(shù) 在綜合衡量現(xiàn)有成果對參數(shù)取值的建議以及基于多次重復(fù)實驗的結(jié)果下，按如下方式設(shè)定參數(shù)：rcost∈（0.2，0.9），σ∈（0.2，0.9），其中，rcost表示懲罰程度，σ表示概率隨機數(shù)，種群規(guī)模設(shè)定為65～85，迭代次數(shù)設(shè)定為75～105。

3）環(huán)境模擬 首先對5臺曙光服務(wù)器編號并分成兩組功能模塊，其中1#、2#及3#服務(wù)器模擬云、邊、端三種算力且模擬的算力種類總量范圍為［150，280］。每種算力資源可依據(jù)算力評估指標集Val評估并參照實際場景隨機賦值。另一方面，4#和5#服務(wù)器用于模擬10個CFES，并依據(jù)實驗情況模擬每個CFES在處理算力資源接入時其所消耗的資源（如CPU、網(wǎng)絡(luò)、內(nèi)存等）。

4）測試算法 為保證算法的合理性，本文分別選取啟發(fā)式部署算法（HGA）［8］和分治式部署算法（DCBHPA）［9］與IGACFN算法進行對比。

5）測試性能指標及實驗結(jié)果

a）算力資源總量偏差率（resources deviation rate，RDR）。

RDR=|期望最大資源總量-被測算法求得實際資源總量|/期望最大資源總量

該指標用來衡量各算法所得到的算力資源總量與期望最大資源總量之間的相差程度。

實驗1 在設(shè)定CFES的個數(shù)為10、算力種類總量的規(guī)模不斷增加的條件下，測試各類算法的RDR。如圖2所示，種類總量為150種，IGACFN的RDR接近2.1%，DCBHPA的RDR接近2.2%，HGA的RDR接近2.19%，IGACFN的RDR分別相對地降低了4.5%和4.1%。

種類總量為200種，IGACFN的RDR接近2.48%，DCBHPA的RDR接近2.9%，HGA的RDR接近2.81%，IGACFN的RDR分別相對地降低了14.5%和11.7%。

種類總量為280種，IGACFN的RDR接近3.92%，DCBHPA的RDR接近5.18%，HGA的RDR接近5.23%，IGACFN的RDR分別相對地降低了24.3%和25%。

b）負載平衡誤差率（load error rate，LER）［14，15］。

LER=|被測算法求得實際負載均衡度-期望負載均衡度|/期望負載均衡度

該指標主要用于衡量各算法實際計算的負載分布情況與期望分布情況相差的程度。

實驗2 在設(shè)定CFES的個數(shù)為10、算力種類總量的規(guī)模不斷增加的條件下，測試各類算法的LER，如圖3所示。圖3中，種類總量為150種，IGACFN的LER接近8.1%，DCBHPA的LER接近8.8%，HGA的LER接近9%，IGACFN的LER分別相對地降低了7.9%和10%。

種類總量為200種，IGACFN的LER接近12.9%，DCBHPA的LER接近15.3%，HGA的LER接近16.2%，IGACFN的LER分別相對地降低了15.6%和20.3%。

種類總量為280種，IGACFN的LER接近18.3%，DCBHPA的LER接近25.6%，HGA的LER接近25.2%，IGACFN的LER分別相對地降低了28.5%和27.3%。

c）收斂率（convergence rate，CR）。

CR=|被測算法的實際收斂平均值-期望收斂值|/期望收斂值

該指標用于衡量各測試算法的執(zhí)行效率及收斂快慢程度。

實驗3 在設(shè)定CFES的個數(shù)為10、算力種類總量的規(guī)模不斷增加的條件下，測試各類算法的CR變化情況，如圖4所示。圖4中，種類總量為150種，IGACFN的CR接近10.1%，DCBHPA的CR接近11.2%，HGA的CR接近10.8%，IGACFN的CR分別相對地降低了9.8%和6.5%。

種類總量為200種，IGACFN的CR接近12.6%，DCBHPA的CR接近15%，HGA的CR接近14.3%，IGACFN的CR分別相對地降低了16%和11.9%。

種類總量為280種，IGACFN的CR接近27.7%，DCBHPA的CR接近38.6%，HGA的CR接近38.1%，IGACFN的CR分別相對地降低了28.2%和27.3%。

d）期望最優(yōu)解誤差率（expectation solution error rate，ESER）。

ESER=|期望最優(yōu)解-被測算法求得最優(yōu)解的平均值|/期望最優(yōu)解

該指標主要用于衡量IGACFN與經(jīng)典遺傳算法GA［13］的最優(yōu)解搜索能力。

實驗4 在設(shè)定CFES的個數(shù)為10、算力種類總量的規(guī)模不斷增加的條件下，測試以上兩類算法的ESER變化情況，如圖5所示。圖5中，種類總量為150種，IGACFN的ESER接近1.7%，GA的ESER接近1.82%，IGACFN的ESER相對地降低了6.6%。

種類總量為200種，IGACFN的ESER接近1.91%，GA的ESER接近2.2%，IGACFN的ESER相對地降低了13.2%。

種類總量為280種，IGACFN的ESER接近3.6%，GA的ESER接近4.57%，IGACFN的ESER相對地降低了21.2%。

通過以上多組實驗測試說明，IGACFN算法相對于已有研究成果，在解決CFESDP問題上更加具有優(yōu)勢。原因在于：a）DCBHPA算法是基于差異化思想的部署算法，但究其本質(zhì)就是在進行分類，隨著算力種類總量不斷增加，分類策略必將導(dǎo)致算法整體性能下降；b）HGA算法是一種基于最小子集劃分的部署方法，該方法主要采用窮舉遍歷思想搜索最佳部署方案，當(dāng)算力種類總量不斷增加時，窮舉規(guī)模迅速擴大，必將影響到算法的有效性；c）經(jīng)典遺傳算法GA存在陷入到局部最優(yōu)的可能，求解問題時最優(yōu)解往往比較粗糙。而IGACFN不存在（或緩解）以上算法的弊端，因此算法更加有效。

4 結(jié)束語

算力網(wǎng)絡(luò)是加快推動經(jīng)濟轉(zhuǎn)型的重要抓手，本文以此為背景，討論了算力網(wǎng)絡(luò)建設(shè)中的基礎(chǔ)性問題——算力邊緣服務(wù)器部署問題，并從優(yōu)化論角度，提出了帶約束的多目標優(yōu)化問題。針對該問題，提出一種改進型遺傳算法予以解決，并通過實驗驗證其有效性和合理性。未來，如何支持上千個算力邊緣服務(wù)器部署將成為工作的重心。

參考文獻：

［1］中國移動研究院. 算力網(wǎng)絡(luò)技術(shù)白皮書［R］. 北京： 中國移動， 2022. （China Mobile Research Institute. Computing force network technology whitepaper［R］. Beijing： China Mobile， 2022.）

［2］中國信通院. 中國算力發(fā)展指數(shù)白皮書2022［R］. 北京： 中國信通院， 2022. （CAICT. China computational power development index white paper 2022［R］. Beijing： CAICT， 2022.）

［3］端側(cè)算力網(wǎng)絡(luò)白皮書［R］. 北京： 中國移動，北京郵電大學(xué)， 中國通信學(xué)會， 2022. （Edge computing force network whitepaper［R］. Beijing： China Mobile， BUPT， CIC， 2022.）

［4］何濤， 楊振東， 曹暢，等. 算力網(wǎng)絡(luò)發(fā)展中的若干關(guān)鍵技術(shù)問題分析［J］. 電信科學(xué)， 2022，38（6）： 62-70. （He Tao， Yang Zhendong， Cao Chang， et al. Analysis of some key technical problems in the development of computing power network［J］. Telecommunication Science， 2022，38（6）： 62-70.）

［5］Yi Meng， Chen Qingkui， Zhang Gang. Multistage dynamic packet access mechanism of Internet of Things［J］. Mobile Information Systems， 2018， 2018（6）：1-16.

［6］段曉東， 姚惠娟， 付月霞，等. 面向算網(wǎng)一體化演進的算力網(wǎng)絡(luò)技術(shù)[J]. 電信科學(xué)， 2021，37（10）：76-85. （Duan Xiaodong， Yao Huijuan， Fu Yuexia， et al. Computing force network technologies for computing and network integration evolution［J］. Telecommunications Science， 2021，37（10）： 76-85.）

［7］劉強. 工業(yè)霧節(jié)點部署問題研究［D］. 南京：南京郵電大學(xué)， 2020. （Liu Qiang. Study of fog node deployment optimization problem for industrial IoT applications［D］. Nanjing： Nanjing University of Posts and Telecommunications， 2020.）

［8］顏曉蓮. 工業(yè)物聯(lián)網(wǎng)的工業(yè)邊緣云部署算法［J］. 計算機集成制造系統(tǒng)， 2022，28（2）： 576-585. （Yan Xiaolian. Industrial edge cloud deployment algorithm for industrial Internet of Things［J］. Computer Integrated Manufacturing Systems， 2022， 28（2）： 576-585.）

［9］李光輝. 面向移動邊緣計算中多應(yīng)用服務(wù)的虛擬機部署算法［J］. 電子與信息學(xué)報， 2022， 44（7）： 2431-2439. （Li Guanghui. Virtual machine placement algorithm for supporting multiple applications to mobile edge computing［J］. Journal of Electronics & Information Technology， 2022，44（7）： 2431-2439.）

［10］Wang Shangguang， Zhao Yali， Xu Jinliang. et al. Edge server placement in mobile edge computing［J］. Journal of Parallel and Distri-buted Computing， 2019， 127： 160-168.

［11］Zeng Feng， Ren Yongzheng. Cost-effective edge server placement in wireless metropolitan area networks［J］. Sensors， 2019，19（1）： 32-52.

［12］馬悅， 張玉梅. 面向多接入邊緣計算的VNFM分布式部署方案［J］. 西安電子科技大學(xué)學(xué)報， 2021，48（4）： 20-26. （Ma Yue， Zhang Yumei. Method for distributed deployment of the virtual network function manager for MEC［J］. Journal of Xidian University， 2021，48（4）： 20-26.）

［13］Creevey F M， Hill C D， Hollenberg L C L. GASP： a genetic algorithm for state preparation on quantum computers［J］. Scientific Reports， 2023，13（1）： 11956-11963.

［14］Balevi E. Gitlin R. D. Optimizing the number of fog nodes for cloud-fog-thing networks［J］. IEEE Access， 2018，6（3）： 11173-11183.

［15］Cheng Zhipeng， Liwang Minghui， Chen Ning， et al. Deep reinforcement learning-based joint task and energy offloading in UAV-aided 6G intelligent edge networks［J］. Computer Communications， 2022，192（8）： 234-244.