基于改進(jìn)蟻群算法的集群負(fù)載均衡研究

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

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

0 引言

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

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

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

1．1蟻群算法

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

1．2集群負(fù)載均衡

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

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

e_i=f_i-F(X) (2)

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

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

式(3)中的S_i為第i個(gè)節(jié)點(diǎn)機(jī)的CPU占用率。

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

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

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

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

當(dāng)有一個(gè)節(jié)點(diǎn)機(jī)i加入時(shí)，先初始化該資源的信息素：

令T^shart_j=L，其中：^shart_j為初始時(shí)刻個(gè)節(jié)點(diǎn)機(jī)上的信息素強(qiáng)度，L為常數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k．轉(zhuǎn)到c；

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

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

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

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

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

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

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

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

(2)選擇操作

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

(3)雜交操作

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

(4)變異操作

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

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

3 算法分析

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

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

4 結(jié)束語

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

本文創(chuàng)新點(diǎn)：

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

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