章剛 胡鵬

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

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

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A?文章編號(hào)：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年，國(guó)家發(fā)改委等四部委聯(lián)合出臺(tái)《全國(guó)一體化大數(shù)據(jù)中心協(xié)同創(chuàng)新體系算力樞紐實(shí)施方案》 ，明確指出要變革現(xiàn)有網(wǎng)絡(luò)傳輸能力，提升跨區(qū)域算力調(diào)度水平，從而構(gòu)建起滿足新一輪數(shù)字經(jīng)濟(jì)發(fā)展的國(guó)家算力網(wǎng)絡(luò)體系——算力網(wǎng)絡(luò)（CFN）。算力網(wǎng)絡(luò)的建設(shè)既是國(guó)家、社會(huì)發(fā)展的戰(zhàn)略要求，又是當(dāng)前經(jīng)濟(jì)轉(zhuǎn)型發(fā)展的新機(jī)遇［1～3］。

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

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

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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

根據(jù)統(tǒng)計(jì)，目前企業(yè)所使用的算力資源主要分為云算力、邊緣算力以及端算力三種資源。為方便討論，假設(shè)云、邊、端等算力都可以通過(guò)一組相同評(píng)估指標(biāo)進(jìn)行算力度量，那么令集合Val={Cmp，CmpE，NetP，MemP}為評(píng)估算力的指標(biāo)集。其中：Cmp表示每秒浮點(diǎn)運(yùn)算次數(shù)；CmpE表示每單位能耗所產(chǎn)生的算力；NetP表示每秒能夠傳輸?shù)谋忍匚粩?shù)；MemP表示存儲(chǔ)單元個(gè)數(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ù)；令對(duì)任意算力邊緣服務(wù)器CFESj而言，其可以為云算力、邊緣算力以及端算力等任意算力提供接入服務(wù)，而且對(duì)任意算力（云或邊或端）而言，其可以接入到任意CFESj中，但同一時(shí)刻只能有一個(gè)邊緣服務(wù)器為之響應(yīng)。

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

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

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

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

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

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

2 算法描述

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

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

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

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

2.2 IGACFN算法描述

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

2.2.1 編碼方式

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

2.2.2 初始化種群

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

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

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

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

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

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

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

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

2.2.4 選擇策略

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

1）全局選擇

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

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

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

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

2）局部選擇。

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

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

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

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

2.2.5 交叉與變異操作

1）交叉規(guī)則

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

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

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

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

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

2）變異規(guī)則

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

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

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

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

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

e）基于隨機(jī)單點(diǎn)變異思想，對(duì)待變異個(gè)體進(jìn)行變異操作。

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

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

2.2.6 IGACFN算法過(guò)程

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

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

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

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

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

2.2.7 算法有效性分析

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

3 實(shí)驗(yàn)與分析

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

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

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

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

5）測(cè)試性能指標(biāo)及實(shí)驗(yàn)結(jié)果

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

RDR=|期望最大資源總量-被測(cè)算法求得實(shí)際資源總量|/期望最大資源總量

該指標(biāo)用來(lái)衡量各算法所得到的算力資源總量與期望最大資源總量之間的相差程度。

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

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

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

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

LER=|被測(cè)算法求得實(shí)際負(fù)載均衡度-期望負(fù)載均衡度|/期望負(fù)載均衡度

該指標(biāo)主要用于衡量各算法實(shí)際計(jì)算的負(fù)載分布情況與期望分布情況相差的程度。

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

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

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

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

CR=|被測(cè)算法的實(shí)際收斂平均值-期望收斂值|/期望收斂值

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

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

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

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

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

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

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

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

種類(lèi)總量為200種，IGACFN的ESER接近1.91%，GA的ESER接近2.2%，IGACFN的ESER相對(duì)地降低了13.2%。

種類(lèi)總量為280種，IGACFN的ESER接近3.6%，GA的ESER接近4.57%，IGACFN的ESER相對(duì)地降低了21.2%。

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

［4］何濤， 楊振東， 曹暢，等. 算力網(wǎng)絡(luò)發(fā)展中的若干關(guān)鍵技術(shù)問(wèn)題分析［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)一體化演進(jìn)的算力網(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］劉強(qiáng). 工業(yè)霧節(jié)點(diǎn)部署問(wèn)題研究［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］. 計(jì)算機(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］李光輝. 面向移動(dòng)邊緣計(jì)算中多應(yīng)用服務(wù)的虛擬機(jī)部署算法［J］. 電子與信息學(xué)報(bào)， 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］馬悅， 張玉梅. 面向多接入邊緣計(jì)算的VNFM分布式部署方案［J］. 西安電子科技大學(xué)學(xué)報(bào)， 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.