多智能體遺傳算法在云計算負載均衡中的應用研究

付天馳

（遼寧工程職業學院，遼寧 鐵嶺 112008）

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

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

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

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

1 關于本研究的相關工作

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

研究人員對此主題進行了許多研究，提供了各種靜態、動態和混合資源規劃策略。靜態規劃算法包括：ISH 算法、MCP 算法和ETF 算法，即BNP（Limited Number Processing SORS），相對于具有高效網絡的分布式環境，由于虛擬云計算的應用單元，團體需求復雜多樣，必須按要求提供服務費用。此外，很多研究人員也針對這個課題研究了相應的啟發式算法，但隨著問題的不斷增多，啟發式算法的影響并不那么明顯。

2 多智能體遺傳算法

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

2.1 個體生存環境

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

2.2 遺傳操作算子

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

2.3 MAGA 與GA 的比較

表1 對GA 與MAGA 在信息交互方式、遺傳算子、自學習能力等方面進行了對比分析。以函數優化為例，對MAGA 與GA 的性能進行比較，取n=20，設優化函數為：

表1 GA 與MAGA 在遺傳操作上的對比

通過對兩種算法執行10 次后得到的最優函數值的比較，表明MAGA的執行效果明顯優于傳統的遺傳算法。

3 負載均衡模型

每個用戶請求用戶信息的主要參數（ReqPerHrPerUser，ReqSize，ReqCPU，ReqMemory，Count）。其中：ReqPerHrPeruser 表示每小時平均互聯網用戶數；ReqSize 是用戶組中每個用戶的每個請求的大小。ReqCPU 是指CPU 執行請求的使用率，以百分比表示，與2.4GHz 的CPU 內核相對應；ReqMemory 是指在M中執行請求所使用的內存量；計算每分鐘發送請求的平均數。

為了解決網格資源規模急劇增加的問題，提出了一種資源調度模型。基于用戶請求標準的分組策略，組中的每個參數都有一個最大值，每個組中所有用戶的所有參數的總和不能超過由組指定的最大值，該最大值可分為一個組，該組可根據時間序列重新設置參數。

3.1 負載均衡模型的建立

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

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

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

基于內存消耗與CPU 消耗，Vmi上的總負載：

其中，w 和v 是權重因子，且滿足w+v=1。

3.2 編碼

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

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

00001—VM_0

00010—VM_1

11110—VM_29

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

{00001,00100,10010,00110,10010,11000,11100,00010,01000,10000}

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

4 算法步驟

Step1：隨機生成LSIZE2個Agent,初始化L0,更新Best0,令t ←0。

Step2：對LI中的每個Agent 執行鄰域競爭算子得到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,并將自學習算子作用在其上。

Step6：若Energy(CBestl+1）＞Energy(Best')成立，則令Bestl+1←CBesll+1；否則Bestl+1←Bestt，CBestl+1← Bestt。

Step7：如果終止條件滿足，輸出Bestt并停機；否則，令1 ←t+1 并轉Step2。

其中，L'表示第t 代的Agent 網格，LI+1/3和LI+1/3是Li和LI+1的中間代Agent 網格；Bestt是L0，L..,Lt中最優的Agent，CBestt表示Lt中最優的Agent；Pc 和Pm為預先設定的參數，分別是鄰域正交交叉算子和變異算子的執行概率。

5 結語

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