基于遺傳模擬退火算法的網絡負載平衡研究

摘要：介紹了網絡負載平衡的基本算法，建立了負載平衡的數學模型，重點闡述了遺傳算法和模擬退火算法相結合的重要意義。并提出將遺傳模擬退火算法應用于解決網絡負載平衡問題的算法，通過實例證明了其有效性。

關鍵詞：網絡負載平衡；遺傳模擬退火

中圖分類號：TP311 文獻標識碼：A文章編號：1009-3044(2008)17-21415-03

網絡負載平衡是分布式作業調度系統的一種實現。在并行分布計算中，負載平衡牽涉到把一個問題分成一系列能夠并行處理的小任務，并且把每一個任務分配到合適的計算資源上，這樣的計算資源有可能是一個處理機，也有可能是一臺計算機。當作業量不斷增加的時候，就有可能出現有的處理器或計算機因系統負擔過重而導致性能下降或者死機，而有的處理器則因空閑而浪費資源。網絡負載平衡研究的目標就是如何研究一些可以將負載平衡地分配給網絡內的各個處理器（計算機）的策略方法，使得整個問題的處理時間減短，而計算資源的利用率得到最大化的利用。

1 負載平衡問題的數學模型[1]

負載平衡問題的數學模型可以描述為：假設系統由M臺處理計算機組成，依次標記為p0，p1，…，pM-1，處理機之間通過線路進行連接，為了便于評測系統的平衡性，用每臺處理機所擁有的數據數來表示其負載，記為w[i]，整個系統的總負載可表示為w=∑w(i)，其中0≤N-1，系統的平均負載為w*=W/N。

2 遺傳模擬退火算法

遺傳算法和模擬退火算法是較為常用的兩種智能優化算法，而且各有優缺點，將這兩種算法有機地結合在一起，應用于網絡負載平衡問題的解決，會取得更好的結果。

2.1 遺傳算法

遺傳算法使用群體搜索技術，它通過對當前群體施加選擇、交叉、變異等一系列遺傳操作，從而產生出新一代的群體，并逐步使群體進化到包含或接近最優解的狀態。由于其具有思想簡單、易于實現、應用效果明顯等優點而被眾多應用領域所接收，并在自適應控制、組合優化、模式識別、機器學習、人工生命、管理決策等領域得到了廣泛的應用。遺傳算法給我們呈現出的是一種通用的算法框架，該框架不依賴于問題的種類。遺傳算法是一類具有較強魯棒性的優化算法，特別是對于一些大型、復雜非線性系統，它更表現出了比其他傳統優化方法更加獨特和優越的性能。隱含并行性和全局搜索特性是遺傳算法的兩大顯著特征。

2.2 模擬退火算法

模擬算法是基于Mente Carlo迭代求解策略的一種隨機尋優算法，其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。

在金屬熱加工工藝中，退火是指將金屬材料加熱到某一高溫狀態，然后讓其慢慢冷卻下來這樣一個金屬熱處理過程。從統計熱力學的觀點來說，隨著溫度的降低，物質的能量將逐漸走近于一個較低的狀態，并最終達到某種平衡。

模擬退火算法就是基于金屬退火的機理而建立起的一種全局最優化方法，它能夠以隨機搜索技術從概率的意義上找出目標函數的全局最小點。

2.3 遺傳算法與模擬退火算法的結合

遺傳算法由于其運算簡單和解決問題的有效能力而被廣泛應用到眾多的領域。理論上已經證明，遺傳算法能從概率的意義上以隨機的方式尋求到問題的最優解。但另一方面，應用實踐表明，在遺傳算法的應用中也會出現一些不盡人意的問題，比如收斂較慢且易陷入局部極值點。另外，遺傳算法也無法避免多次搜索同一個可行解，這也是影響遺傳算法運行效率的一個因素。

另一方面，梯度法、爬山法、模擬退火算法、列表尋優法等一些優化算法卻具有很強的局部搜索能力，而另一些含有問題與相關知識的啟發式算法的運行效率也比較高。比如模擬退火算法對具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優解?？梢灶A計，在遺傳算法的搜索過程中整合這些優化方法的思想、構成一種混合遺傳算法(Hybrid Genetic Algorithm)是提高遺傳算法運行效率和求解質量的一個有效手段。

遺傳模擬退火算法的結構如圖1所示：

遺傳模擬退火算法可以理解為在遺傳算法中引入模擬退火算法的思想，這有效地緩解了遺傳算法的選擇壓力，并對基因操作產生的新個體實施概率接受版圖，不但增強了算法的全局收斂性，而且使算法在優化后期有較強的爬山能力，加快了進化后期的收斂速度。另一方面，遺傳模擬退火算法以遺傳算法控制尋優的方向，發揮搜索速度快的特點；而用模擬退火算法解決局部收斂的問題，以提高搜索精度。充分發揮了遺傳算法的快速全局搜索性能和模擬退火算法的局部搜索能力，因此具有較高的效率和廣泛的適用性。

2.4 遺傳模擬退火算法的基本步驟

簡單地說，遺傳模擬退火算法的特點在于利用模擬退火算法克服遺傳算法的早熟問題，利用遺傳算法克服模擬退火算法對初值的依賴性。以下是該算法的一種基本結：

(1)給定群體規模n，k:=0；初始溫度tk:=t0，群體pop(k)；

(2)若滿足停止規則，則停止計算；否則，在群體pop(k)中每一個染色體i∈pop(k)的領域中隨機選一狀態j∈N(i)，按模擬退火中的接受概率Aij(tk)： (1)

接受或拒絕j，其中f(i)為狀態i的目標值，其中f(j)為狀態j的目標值，這一階段n次迭代選出新群體newpop1(k+1)。

(3)在群體newpop1(k+1)中計算適應函數fi(tk)：

(2)

其中fmax是newpop1(k+1)中的最大適應值；按由適應函數決定的概率分布從newpop1(k+1)中隨機選n個染色體形成種群newpop1(k+1)。

(4)按遺傳算法的常規方法進行交叉得到crosspop1(k+1)；再變異得到mutpop1(k+1)。

(5)Tk+1=d(tk)，k=K+1， pop(k)=mutpop1(k+1)，返回第二步。

在遺傳模擬退火算法中，在第二步的群體選擇時隨機搜索了每一個體的領域，選擇的范圍比單純的遺傳算法要大，實際上是用所有個體的領域取代遺傳算法中的 ，而且采用Metropolis準則由式(1)所確定的概率選取，這是模擬退火的一個顯著特征。式(2)是一個加速適應值尺度變換函數，在溫度較高時加速性不明顯，當溫度較低時加速性非常顯著，是根據退火的第二個特征。第四步中的交叉和變異操作與一般遺傳算法中的處理方法一致。

3 應用實例

在這一小節中，我們將用一個實際的例子來說明遺傳模擬退火算法在網絡負載平衡中的應用。

假定我們在一個擁有4臺服務器的網絡中對16個任務進行網絡負載平衡的規劃，并且這16個任務各自獨立，相互之間沒有依存關系，同時這16個任務完成所需要的時間各不相同。

設定實例的任務編號，所需時間如表1所示。

3.1 編碼

利用遺傳算法求解優化問題時，先要將實際問題轉換成由基因按一定結構組成的染色體或個體，這一轉換操作我們稱之為編碼。編碼的方式比較靈活，在這里，我們設定一個三元組為個體的基因：(I，m，n)，其中，i為任務的編號，m為完成任務所需的時間，n為網絡中該任務被分配到的服務器(處理機)編號。例如(1，2，3)表示編號為1的任務所需的完成時間是2個單位時間長度，它被分配到了3號服務器(處理機)上。于是，仿真實驗中，一個染色體就可以表示為｛(i，m，n)1≤i≤16，0

3.2 初始群體的產生

為了滿足遺傳算法的群體型操作的需要，必須為遺傳操作準備一個若干初始解組成的初始群體。我們設定初始群體規模為20，給定的16個任務編號為1至16，任務完成所需要的時間已知，即三元組(i，m，n)中i和m已經確定。在1至4中隨機選擇一個數字分配給16個三元組，組成一個染色體，即：｛(1，5，1)，(2，6， 2)(3，8，2)…｝，共隨機產生出20條染色體，生成群體。

3.3 適應度函數

遺傳算法使用目標函數即適應度函數來評估個體或解的優劣，并作為以后遺傳操作的依據。對適應度函數的唯一要求是，針對輸入可計算出能加以比較的非負結果。由于是研究負載平衡問題，故利用方差和作為適應度函數。具體如下：

設所有任務完成的時間和為T，服務器的個數為 ，則理想狀態下每臺服務器的平均負載為w*=T/n。對于每一個染色體來說，每一個處理器上的任務總完成時間w與w*的差越小越好，故適應度函數為 ，F的值越小，則染色體的適應度越好。

3.4 模擬退火操作

遺傳模擬退火算法中的模擬退火操作主要是在個體選擇階段，在這一階段中，由于遺傳算法只選擇適應度最好的，而對適應度較低的染色體選擇的機率很小，所以容易出現過早收斂的問題，故引入模擬退火算法，使適應度較小的染色體同樣有機會被選中，從而跳出局部最優，有利于尋找到全局最優解。我們取初始溫度t0為50度，降溫系數為0.95。

3.5 實例結果及對比

以假定任務為基礎，利用VC++編寫仿真程序，分析利用普通遺傳算法和模擬退火算法進行運算，在初始群體規模、交叉概率、變異概率及遺傳代數相同的情況下，得到如下運算結果，

由實驗結果可以得出，遺傳模擬退火算法比普通的優化算法具有更好的尋求最優解的性能，在相同的條件下，尋找到最優解的概率更大。

4 結論

遺傳模擬退火算法是遺傳算法和模擬退火算法相結合的一種優化算法。遺傳算法的并行處理和快速收斂的特點和模擬退火跳出局部最優的能力得以保存，兩種不同的領域結構有機結合，搜索效率更高。

本文首次將遺傳模擬退火算法應用于網絡負載平衡，給出了該算法的結構與運算過程，并通過一個實例證明了其在網絡負載平衡方面的有效性，為進一步利用智能化算法解決網絡負載平衡問題打下了基礎。

參考文獻：

[1] 彭國震，邱毓蘭，彭德純.若干隨機型負載平衡算法[J].計算機工程，27(2):22-23.

[2] 林凡，楊晨暉.一種動態網絡負載平衡集群的實踐方法[J].廈門大學學報(自然科學版).42(4):534-535.

[3] 邢文訓，謝金星.現代優化計算方法，北京:清華大學出版社，1999.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文