多智能體遺傳算法在云計算負(fù)載均衡中的應(yīng)用研究

付天馳

摘 要 由于云計算系統(tǒng)具有諸多特點，因此使得云計算機(jī)系統(tǒng)的裝載平衡更復(fù)雜，難以有效地實現(xiàn)。本文采用多智能體內(nèi)遺傳算法（MAGA）來解決負(fù)載平衡，以通過參數(shù)平衡云計算中的問題。測試結(jié)果表明，云計算系統(tǒng)加載MAGA構(gòu)建的平衡模型可以有效地避免由過度依賴性參數(shù)指標(biāo)引起的單點故障問題，并且在系統(tǒng)執(zhí)行效率和系統(tǒng)平衡方面取得了良好的效果。

關(guān)鍵詞 多智能體遺傳算法 云計算負(fù)載均衡 虛擬仿真技術(shù) 靜態(tài)規(guī)劃算法

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-0745（2022）03-0016-03

云計算是基于大量計算機(jī)計算出的資源。不同的應(yīng)用系統(tǒng)可以獲得計算能力、存儲能力和各種軟件服務(wù)。云計算系統(tǒng)作為一種具有競爭性和不確定性的任務(wù)處理方式，具有高度的動態(tài)性。因此，資源規(guī)劃和任務(wù)管理是云計算中的關(guān)鍵問題[1]。現(xiàn)有算法，如靜態(tài)投票方法和隨機(jī)方法，顯然不適合這種大規(guī)模的負(fù)載平衡，因為它易于導(dǎo)致一個點故障。動態(tài)算法包括UT策略和來自負(fù)載平衡策略的彈簧策略，僅考慮單個參數(shù)的影響，并且當(dāng)影響增長時，其執(zhí)行效率將下降。此外，雖然人們設(shè)法解決了加載余額的問題，但隨著數(shù)據(jù)和尺寸的增加，它們的收斂速度將受到影響。遺傳算法在較長的搜索時間內(nèi)比較緩慢，MAGA可以在解決較大的尺寸功能時快速找到高質(zhì)量的解決方案[2-3]。本文的目的是使用MAGA來解決負(fù)載平衡并平衡云計算中的問題。插入各種不同的模擬環(huán)境，參數(shù)選擇的培訓(xùn)是在各種測試環(huán)境中進(jìn)行的，從而獲得相對最佳、更通用的校正參數(shù)，以及獲得平衡策略的負(fù)載。在整個測試中，MAGA生成的充電策略、UT策略和彈簧策略應(yīng)用于相同的模擬環(huán)境，比較最大CPU使用率、平均CPU使用率、最大內(nèi)存率和平均內(nèi)存使用，分析他們的優(yōu)點和缺點。測試表明，對于大型動態(tài)云系統(tǒng)，MAGA產(chǎn)生的負(fù)載策略，CPU的最大使用和最大內(nèi)存使用率較低，并且可以保證整個系統(tǒng)的穩(wěn)定性和強(qiáng)度。

目前，云計算已經(jīng)成為一種非常流行的計算機(jī)商業(yè)模式，它是并行計算、分布式計算和網(wǎng)絡(luò)計算的發(fā)展。云計算是一種可以獨立管理的虛擬計算資源，因此，繪制適當(dāng)?shù)年P(guān)系和資源圖，即Rational Task Plan，以動態(tài)有效地管理資源。根據(jù)服務(wù)水平協(xié)議，它是云計算機(jī)器的重要組成部分。理論上，每個用戶都有一臺虛擬裁縫機(jī)，互不接觸。每個物理主機(jī)將加載一個或多個虛擬機(jī)，以確保用戶應(yīng)用程序的獨立性。因此，云計算的任務(wù)就是規(guī)劃。在虛擬機(jī)中，保持虛擬集群的負(fù)載平衡是一種有效的算法。

云計算虛擬集群負(fù)載均衡的研究剛剛起步。本文基于對偶遺傳算法規(guī)劃，但優(yōu)化的目標(biāo)只是考慮負(fù)責(zé)任務(wù)的時間。使用算法完成整個任務(wù)只是最短的時間，因為云計算的中心思想是實現(xiàn)廉價高效的計算，除了與任務(wù)相關(guān)的時間，整個計算過程都會消耗資源和能源，系統(tǒng)中還存在需要進(jìn)一步研究的問題。智能算法是通過模擬或揭示某些自然現(xiàn)象過程和思想而發(fā)展起來的，不僅內(nèi)容涉及數(shù)學(xué)，還以物理學(xué)、生物學(xué)、人工智能、神經(jīng)科學(xué)和統(tǒng)計力學(xué)為基礎(chǔ)，為解決復(fù)雜問題提供了新的思路和手段，將動態(tài)聯(lián)盟的思想引入到文獻(xiàn)中，提出了一種基于粒子群優(yōu)化的任務(wù)分配算法，該算法在網(wǎng)絡(luò)環(huán)境中實現(xiàn)了多種均衡。

本文提出了一種自適應(yīng)變量遺傳算法（GA）來解決虛擬人群的負(fù)載問題，使虛擬累計使用值最高。仿真結(jié)果表明，該算法快速高效，具有實際應(yīng)用價值。

1 關(guān)于本研究的相關(guān)工作

虛擬仿真技術(shù)充分利用了用戶的基礎(chǔ)設(shè)施，實現(xiàn)了整個應(yīng)用系統(tǒng)。因此，越來越多的人開始關(guān)注虛擬存儲服務(wù)器的使用。為了實現(xiàn)各種信息、服務(wù)和資源的高可用性，必須使用負(fù)載平衡設(shè)備來協(xié)調(diào)和管理大量的虛擬機(jī)。最終目的是研究云計算中虛擬終端的負(fù)載平衡問題。本實用新型非常有效地提高了計算機(jī)資源的利用率，有效的負(fù)載均衡算法要求系統(tǒng)在高效的響應(yīng)時間內(nèi)智能地在不同虛擬機(jī)之間分配負(fù)載。云環(huán)境的計劃與傳統(tǒng)的資源規(guī)劃有許多不同的情況。首先，規(guī)劃目標(biāo)不同于傳統(tǒng)手段的規(guī)劃目標(biāo)。傳統(tǒng)規(guī)劃是通過物理方式來工作，屬于精細(xì)規(guī)劃;云計算環(huán)境中的規(guī)劃對象是屬于原糧規(guī)劃的虛擬機(jī)資源，傳輸?shù)臄?shù)據(jù)量也很大。

研究人員對此主題進(jìn)行了許多研究，提供了各種靜態(tài)、動態(tài)和混合資源規(guī)劃策略。靜態(tài)規(guī)劃算法包括：ISH算法、MCP算法和ETF算法，即BNP（limited number processing SORS），相對于具有高效網(wǎng)絡(luò)的分布式環(huán)境，由于虛擬云計算的應(yīng)用單元，團(tuán)體需求復(fù)雜多樣，必須按要求提供服務(wù)費用。此外，很多研究人員也針對這個課題研究了相應(yīng)的啟發(fā)式算法，但隨著問題的不斷增多，啟發(fā)式算法的影響并不那么明顯。

2 多智能體遺傳算法

從代理商的角度來看，遺傳算法中的個體被認(rèn)為是部分認(rèn)知、競爭、合作和自學(xué)能力，通過代理人、環(huán)境和每個經(jīng)紀(jì)人之間實現(xiàn)全球最佳目標(biāo)之間的互動。多智能體遺傳算法的實施機(jī)制與遺傳算法截然不同，主要納入個人之間的互動、合作和自我研究，有學(xué)者證明，多智能遺傳算法具有更快的收斂速度，對于求解高維函數(shù)的優(yōu)化問題非常有用[4-5]。

2.1 個體生存環(huán)境

與GA類似，MAGA繼續(xù)在個體上工作。在MAGA中，每個個體都被視為一個代理，每個代理都有自己的特點，可以感知周圍環(huán)境，自主運作，還可以影響和改變環(huán)境，所有代理都位于代理網(wǎng)格中。

2.2 遺傳操作算子

MAGA中的遺傳算子主要包括鄰域競爭算子、變異算子、正交內(nèi)插交叉算子，鄰域正交交叉算子實現(xiàn)了Agent之間的協(xié)作。自變異算子和自變異算子利用Agent的知識來實現(xiàn)Agent的行為。

2.3 MAGA與GA的比較

表1對GA與MAGA在信息交互方式、遺傳算子、自學(xué)習(xí)能力等方面進(jìn)行了對比分析。以函數(shù)優(yōu)化為例，對MAGA與GA的性能進(jìn)行比較，取n=20，設(shè)優(yōu)化函數(shù)為：

通過對兩種算法執(zhí)行10次后得到的最優(yōu)函數(shù)值的比較，表明MAGA的執(zhí)行效果明顯優(yōu)于傳統(tǒng)的遺傳算法。

3 負(fù)載均衡模型

每個用戶請求用戶信息的主要參數(shù)（ReqPerHrPe-rUser，ReqSize，ReqCPU，ReqMemory，Count）。其中：ReqPerHrPeruser表示每小時平均互聯(lián)網(wǎng)用戶數(shù);ReqSize是用戶組中每個用戶的每個請求的大小。ReqCPU是指CPU執(zhí)行請求的使用率，以百分比表示，與2.4GHz的CPU內(nèi)核相對應(yīng);ReqMemory是指在M中執(zhí)行請求所使用的內(nèi)存量;計算每分鐘發(fā)送請求的平均數(shù)。

為了解決網(wǎng)格資源規(guī)模急劇增加的問題，提出了一種資源調(diào)度模型。基于用戶請求標(biāo)準(zhǔn)的分組策略，組中的每個參數(shù)都有一個最大值，每個組中所有用戶的所有參數(shù)的總和不能超過由組指定的最大值，該最大值可分為一個組，該組可根據(jù)時間序列重新設(shè)置參數(shù)。

3.1 負(fù)載均衡模型的建立

負(fù)載均衡模型主要涉及適應(yīng)度函數(shù)的設(shè)計。根據(jù)組策略，主機(jī)上的每個虛擬機(jī)（VM）資源對應(yīng)于用戶組策略請求。主機(jī)包含多個虛擬機(jī)，每個虛擬機(jī)可以被分配給多個組。每個數(shù)組可以被描述為一個數(shù)組（ReqPerHrPerUser，ReqSize，ReqCPU，ReqMemory，Count）。數(shù)組中的第四個參數(shù)是數(shù)組中每個請求所消耗的內(nèi)存。因此，在執(zhí)行一組任務(wù)后，虛擬機(jī)首先加載uji內(nèi)存。

Mli=Mi+Vmpi /Vmi×100%

如果Vmpi和Vmi是固定的，那么第三個參數(shù)是集群中每個請求的平均CPU消耗量，即使在集群任務(wù)完成后，虛擬機(jī)也會加載CPU。

Cli=Ci+Vmci /Vci×100%

其中：Vmci和Vci是常數(shù)，Ci為Vmi在執(zhí)行任務(wù)之前剩余的CPU百分比。

基于內(nèi)存消耗與CPU消耗，Vmi上的總負(fù)載：

Vli=w×Mli+v×Cli

其中，w和v是權(quán)重因子，且滿足w+v=1。

3.2 編碼

假設(shè)有10個用戶組{Group0，Group9，……Group9} 和30個虛擬機(jī){VMU}，每個用戶組被視為一維。

讓另一個10維數(shù)據(jù)（x0 x1.x9），其中xi對應(yīng)一個面板，然后xi，可以選擇30和30的虛擬25，然后采取每一xi長度編碼5，其中：

00001—VM_0

00010—VM_1

11110—VM_29

若采用二進(jìn)制多維編碼方式，那么對整個系統(tǒng)的編碼即是{00000，0000，0000}，則對擁有10個用戶組、30臺VM資源的系統(tǒng)的一個可行解如下：

{00001，00100，10010，00110，10010，

11000，11100，00010，01000，10000}

故對于一個含有n個用戶組、M個VM虛擬資源的系統(tǒng)，問題的求解維數(shù)即是n，每維個體的編碼長度為log2M。

4 算法步驟

Step1：隨機(jī)生成LSIZE2個Agent，初始化L0，更新Best0，令t←0。

Step2：對LI中的每個Agent執(zhí)行鄰域競爭算子得到LI+1/3。

Step3：對LI+1/3中的每個Agent，若U（0，1）<Pe，則將鄰域正交交叉算子作用在其上，得到LI+1/3。

Step4：對LI+1/3中的每個Agent，若U（0，1）<Pe，則將變異算子作用在其上，得到LI+1。

Step5：從LI+1中找出CBest5+1，并將自學(xué)習(xí)算子作用在其上。

Step6：若Energy（CBestl+1）>Energy（Best'）成立，則令Bestl+1←CBesll+1;否則Bestl+1←Bestt，CBestl+1← Bestt。

Step7：如果終止條件滿足，輸出Bestt并停機(jī);否則，令1←t+1并轉(zhuǎn)Step2。

其中，L'表示第t代的Agent網(wǎng)格，LI+1/3和LI+1/3是Li和LI+1的中間代Agent網(wǎng)格;Bestt是L0，L..，Lt中最優(yōu)的Agent，CBestt表示Lt中最優(yōu)的Agent;Pc和Pm為預(yù)先設(shè)定的參數(shù)，分別是鄰域正交交叉算子和變異算子的執(zhí)行概率。

5 結(jié)語

本文提供了一種在云計算中使用魔法算法構(gòu)建裝載平衡模型的方法。當(dāng)解決功能最佳問題時，MAGA具有更快的收斂速度。特別是在大數(shù)據(jù)集上，魔法算法保持不錯。比較UT策略生成的加載模型，彈簧策略和魔法算法策略，可以發(fā)現(xiàn)MAGA生成的加載平衡模型更能加載以平衡UT策略和彈簧策略生成的加載平衡模型，特別是在任務(wù)數(shù)量很大的情況下，MAGA生成的云計算加載平衡模型明顯優(yōu)于其他兩個算法，并且該模型不易引起系統(tǒng)的“單次故障”，這表明該方法是可行且有效的構(gòu)建云計算負(fù)載平衡策略。

參考文獻(xiàn)：

[1] 盧虎，蔣小強(qiáng)，閔歡.具有通信約束的分布式SOR多智能體軌跡估計算法[J].航空學(xué)報，2019，40（10）：166-178.

[2] 徐向藝，陳東方.淺析信息受限下分布式多智能體優(yōu)化算法設(shè)計與分析[J].信息技術(shù)與信息化，2019（12）： 118-120.

[3] 金凱琪.多智能體系統(tǒng)的一致性研究及其在電力系統(tǒng)中的應(yīng)用[D].華北電力大學(xué)，2019.

[4] 盛喆.基于多智能體的泵站多機(jī)組優(yōu)化調(diào)度系統(tǒng)研究[J].水資源開發(fā)與管理，2019，45（10）：67-73.

[5] 田承東，楊璧竹.基于事件觸發(fā)的聚類分析方法在多智能體任務(wù)協(xié)同中的研究[J].新電腦，2019，51（02）：9-14，26.