基于改進蟻群算法的集群負載均衡研究

摘 要：在集群負載均衡技術(shù)中，負載均衡算法的好壞直接影響負載均衡系統(tǒng)的性能。蟻群算法是一種很有效的組合優(yōu)化算法。在蟻群算法的基礎(chǔ)上，文章提出了一種與遺傳算法相融合的基于基本蟻群算法的混合智能負載平衡算法。算法中遺傳特征的引入，有效地改善了傳統(tǒng)蟻群算法容易陷入局部最優(yōu)解的缺陷，極大地提高了算法的收斂速度，有效地實現(xiàn)了集群的動態(tài)負載均衡。

關(guān)鍵詞：集群；負載均衡；蟻群算法；遺傳算法；混合智能

0 引言

集群技術(shù)以其高可用性等特性，近年內(nèi)得到了快速發(fā)展。但現(xiàn)行的集群系統(tǒng)，大多采用靜態(tài)負載均衡機制，由于影響客戶訪問頻率的因素很多，且難以預(yù)測，靜態(tài)調(diào)度往往不能令人滿意，因此設(shè)計出一種高效、適用面廣、穩(wěn)定可靠的負載均衡算法，在計算機集群系統(tǒng)中就顯得非常重要。此時，可以考慮根據(jù)各服務(wù)器運行時的負載情況及其它信息進行動態(tài)的負載均衡，最直觀的辦法是將客戶請求分配給當前負載最低的成員服務(wù)器。

目前，各種負載平衡算法層出不窮，但由于這些算法往往基于特定的集群結(jié)構(gòu)，因此非但不具備通用性，而且對于異構(gòu)集群，造成了軟件資源的極大浪費。為了解決以上問題，本文在基本蟻群算法的基礎(chǔ)上，提出了一種比較理想的負載均衡解決方案——一種蟻群算法和遺傳算法相融合的混合智能負載均衡算法。此算法以當前集群中可用節(jié)點機CPU的占用率作為系統(tǒng)實時負載對請求進行動態(tài)分配的依據(jù)，在蟻群算法的基礎(chǔ)上，融入遺傳算法，利用蟻群算法和遺傳算法良好的全局搜索能力，將其運用到網(wǎng)絡(luò)請求分配中，實現(xiàn)了一個性能優(yōu)良的負載均衡系統(tǒng)。

1 基于基本蟻群模型的集群負載均衡算法及其實現(xiàn)

1．1蟻群算法

蟻群優(yōu)化算法是由意大利學者M.Don20等人受到螞蟻覓食行為的啟發(fā)提出來的一種可以用來解決NP-hard問題中的離散組合優(yōu)化問題的優(yōu)化算法。蟻群算法以其并行性、協(xié)同工作機制、全局優(yōu)化、魯棒性和易于與其它啟發(fā)式算法結(jié)合等特點，應(yīng)用范圍遍及到許多科學技術(shù)及工程領(lǐng)域。

1．2集群負載均衡

在集群負載均衡技術(shù)中，負載均衡算法是核心，它的好壞直接影響均衡系統(tǒng)的性能，客戶端請求的分配與作業(yè)調(diào)度原理一致，所以可將多個請求分配到后臺若干個服務(wù)器上處理，以使總的請求響應(yīng)時間“最小化”，進而“最優(yōu)化”服務(wù)器端CPU的利用率。

集群服務(wù)器動態(tài)負載均衡可以描述成：在N個新到的任務(wù)、M個節(jié)點機、各個節(jié)點機的負載狀況各不相同的情況下，找到一個最優(yōu)的調(diào)度方法，使得整個任務(wù)處理的時間最短，從而提高整個集群服務(wù)器系統(tǒng)的響應(yīng)速度。由于在一次分配方案中，負載偏差率反映的是各CPU負載的總體分布規(guī)律，所以本文的目標函數(shù)就采用這個負載偏差率。目標函數(shù)可以表示如下：

e_i=f_i-F(X) (2)

上式中的f_i(n_i，s_i表示在本次分配方案下，第i個節(jié)點機上分配代價的一個預(yù)測函數(shù)，其定義如下：

f_i=(n_i+1)×S_i (3)

式(3)中的S_i為第i個節(jié)點機的CPU占用率。

式(2)中的F(X)表示系統(tǒng)的CPU平均分配代價的預(yù)算值，其定義如下：

負載偏差率總是在0～1之間取值，值越小，表明CPU的負載分布越均勻，系統(tǒng)整體的性能越高。

1．3基本蟻群算法實現(xiàn)

在每個任務(wù)處分別設(shè)置1個螞蟻，如果任務(wù)分配給節(jié)點機j，j＝1，2……N，螞蟻就在節(jié)點j上留下信息素(也就是一定的信息)，信息素的濃度越高表明該計算機完成作業(yè)的數(shù)量多，速度快，該計算機被選擇的概率越大。

當有一個節(jié)點機i加入時，先初始化該資源的信息素：

令T^shart_j=L，其中：^shart_j為初始時刻個節(jié)點機上的信息素強度，L為常數(shù)。

將任務(wù)分配給某個節(jié)點機后，如果任務(wù)完成，則該節(jié)點上的信息素信息調(diào)整公式如下：

式(5)中，^new_j表示信息素修改后節(jié)點機j上的信息素強度，^old_j表示信息素修改前節(jié)點機j上的信息素強度，p表示信息素揮發(fā)系數(shù)(取0.2)，1-p則表示信息素殘留因子，△T_j表示在本次任務(wù)分配中節(jié)點機j上的信息素的增量。初始時刻，^shart_j=L，△T=0。式(6)中，△T^K_j：表示第k只螞蟻在本次循環(huán)中在節(jié)點j上釋放的信息素強度，其中k=1，2……N。

式中，Q表示螞蟻循環(huán)一周后釋放在所經(jīng)過節(jié)點上的信息素總量。

根據(jù)任務(wù)的完成情況，相應(yīng)節(jié)點機的信息素信息也在跟著發(fā)生變化，則在資源列表中，節(jié)點機j被選中的概率p_i為

式中，n為資源快表中的資源數(shù)；T_j節(jié)點機j的信息素濃度；η_j為啟發(fā)函數(shù)，每個節(jié)點機的啟發(fā)值取該節(jié)點機當前CPU占用率的倒數(shù)；α表示信息素的重要性；β為啟發(fā)信息在螞蟻選擇路徑中的相對重要性。

2 經(jīng)遺傳算法改進的算法

蟻群算法雖然是一種很有效的組合優(yōu)化算法，但也有其不足，收斂速度不夠快就是一個主要方面。導(dǎo)致收斂速度慢的一個主要原因是：在蟻群搜索初期，由于信息素之間的差異不明顯，信息素對蟻群搜索方向的指導(dǎo)作用不強，因此蟻群搜索呈現(xiàn)出較大的盲目性。

本文在基本蟻群算法的基礎(chǔ)上結(jié)合遺傳算法，利用他們各自的優(yōu)點，提出了一種經(jīng)遺傳算法改進的混合智能算法。該算法引入了簡單遺傳算法中的選擇、交叉、變異三種基本的操作，以充分利用現(xiàn)有的信息，進行螞蟻之間關(guān)于路徑的信息交換，擴大搜索范圍，加大信息素對螞蟻搜索方向的指導(dǎo)作用，加快搜索速度、減少陷入局部最優(yōu)的可能性；還增加了一種替代操作，用通過蟻群搜索得到的解替代種群中的若干較劣個體，這種替代操作不僅會減少搜索進入停滯階段的可能性，而且能夠整合共享各種群的優(yōu)良基因，改良種群，加快種群的進化速度，

改進算法的實現(xiàn)流程描述如下：

a．設(shè)定遺傳參數(shù)和蟻群搜索參數(shù)，產(chǎn)生初始種群；

b．置每只螞蟻到初始節(jié)點；

c．對所有螞蟻計算概率p，確定每只螞蟻要轉(zhuǎn)移的下一個節(jié)點；

d．按式(2)以局部更新規(guī)則對各節(jié)點的信息素進行更新；

e．循環(huán)執(zhí)行c、d步，直至所有螞蟻都走完所有節(jié)點，然后再執(zhí)行下一步：

f．比較這次循環(huán)的結(jié)果，若目標函數(shù)E(X)有所改進，則當前分配方案為最佳方案，對各個節(jié)點上的信息素按全局更新規(guī)則進行更新，否則，分配方案不改變，各節(jié)點的信息素采用上次最好分配方案時的信息素；

g．判斷算法收斂條件是否滿足，若滿足，則轉(zhuǎn)到l，否則執(zhí)行下一步；

h．進行替換操作，用通過蟻群搜索得到的解替代種群中的若干較劣個體；

i．根據(jù)適應(yīng)度大小以一定方式執(zhí)行選擇操作，按交叉概率執(zhí)行交叉操作，按變異概率執(zhí)行變異操作；

j．根據(jù)搜索結(jié)果按全局更新規(guī)則對各個節(jié)點上的信息素進行更新；

k．轉(zhuǎn)到c；

l．結(jié)束，輸出結(jié)果。

算法的結(jié)束條件為：①目標函數(shù)值小于某一給定常數(shù)A(A取0.15)；②目標函數(shù)值連續(xù)B次無明顯改進(B取5)；③整個搜索過程循環(huán)次數(shù)超過給定最大循環(huán)次數(shù)C(C取50)。以上三個條件中的任一個條件滿足時，計算結(jié)束。

改進后的算法中，遺傳算法為蟻群搜索提供最優(yōu)個體，用算法中得到的帶有先驗信息的結(jié)果修改信息素信息，能使蟻群算法更快達到最優(yōu)解；用蟻群算法的結(jié)果對種群進行優(yōu)化，也極大地增加了種群的進化速度。兩種算法結(jié)合，雖然使整個搜索過程的復(fù)雜度有所增加，但是，這兩種算法的相互融合，相互促進，不但能加快整個算法的收斂速度，而且能有效地保證算法的收斂陸。

改進算法中用到的相關(guān)函數(shù)和算子如下：

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

根據(jù)適應(yīng)度函數(shù)設(shè)計要求，本算法中的適應(yīng)度函數(shù)為：

g(X)=I-E(X) (9)

它的取值在0～1之間，值越大，表明該染色體的適應(yīng)度越好，對應(yīng)的請求分配方案被選中的概率越高。

(2)選擇操作

本算法中用到的選擇操作是典型的輪盤賭方法。每個染色體占有一個槽，第一個染色體的槽的范圍為0到它的適應(yīng)值，以后每個染色體的槽的范圍為上一個染色體的槽的上界到這個值加上自己的適應(yīng)值。

(3)雜交操作

按照一定的交換概率Pc，從群體中選出一個個體，然后隨機地選出個體上的交叉點賦給不同的字符值(基因)，交換它們的值；即對一個被選中的分配方案中的兩個服務(wù)器上分配的任務(wù)數(shù)進行交換，從而產(chǎn)生新的分配方案。本處取Pc=0.8。

(4)變異操作

變異操作不能隨便改變某個染色體的基因值，否則就會產(chǎn)生錯誤的調(diào)度方案，可以按照一定概率Pm隨機地改變?nèi)旧w的宇符值。操作時，在選中的一個個體中，任意選取個體的兩個不同的字符，對其進行交換操作，從而產(chǎn)生新的個體。本處取Pm=0.05。

變異操作只有在停滯狀態(tài)下才進行。當循環(huán)在近一段時間內(nèi)所產(chǎn)生的最優(yōu)路徑?jīng)]有變化的時候稱為停滯狀態(tài)。

3 算法分析

為了檢驗算法的有效性，我們在C枓環(huán)境下對算法進行了模擬測試。該實驗旨在測試算法的搜索能力。為了在PC機上模擬網(wǎng)絡(luò)環(huán)境，預(yù)先設(shè)置了5個可用節(jié)點機，15個待分配的任務(wù)。初始時刻，設(shè)置5個節(jié)點機的CPU占用率各為5％，20％，35％，45％，60％，分別用基本蟻群算法模型和經(jīng)遺傳算法改進的算法進行模擬。達到收斂所需的循環(huán)次數(shù)和目標函數(shù)值的比較如表1所示。

由試驗結(jié)果對比分析可知，在目標函數(shù)值相近的情況下，改進后算法的循環(huán)次數(shù)大大減少。

4 結(jié)束語

本文根據(jù)基本的蟻群算法模型提出了一種蟻群算法與遺傳算法相融合的算法模型，由于遺傳算法的引入，有效地改善了傳統(tǒng)蟻群算法容易陷入局部最優(yōu)解的缺陷，極大地提高了算法的收斂速度，使算法具有更好的全局搜索能力和更快的收斂速度。通過比較分析可以看出，改進算法可以彌補蟻群算法自身存在的不足，提高負載平衡，有效地解決集群的負載均衡問題。

本文創(chuàng)新點：

(1)把節(jié)點機負載偏差率作為目標函數(shù)，并把該目標函數(shù)小于某一給定值作為算法收斂的條件。

(2)在傳統(tǒng)蟻群算法的的基礎(chǔ)上，融入了遺傳算法，利用遺傳算法的進化結(jié)果修改各節(jié)點信息素，加大了信息素對螞蟻搜索方向的指導(dǎo)作用，加快了整個算法的收斂速度。