最小生成樹問題的分析與研究

引言

組合優化研究的是具有有限個可行解的優化問題。其中最具挑戰性的問題就是組合爆炸。近年來，遺傳算法在組合優化學界里日益受到重視，并在許多工業工程實驗與實際應用中取得了良好的成果，特別是在解決組合優化領域中的最小生成樹問題MST中，顯示了它的巨大潛力。

一、問題的描述

考慮一個連通的無向圖G=(V，E)，其中，V={ν1，ν2，…，νn}是代表終端或通信站的有線的端點集。 E={eij|eij=(νi，νj)，νi，νj∈V}是代表終端或站間連線的有限邊集。每條邊由一個記為W={wij|wij=w(νi，νj)，wij＞0，νi，νj∈V}的正實數的權重，代表距離、價格等。生成樹是連接V中所有端點的來自E的最小邊集，因此對于圖G至少可找到一棵生成樹。最小生成樹記為T*，是邊的權重和最小的生成樹。其描述如下:，其中，T為圖G的生成樹的集合。

在一些實際問題中，端點的度不是可任意選取的。通信網絡中為防止節點故障帶來的脆弱性，對節點的度也有限制。即確定極小化總的邊權的生成樹時，往往要求端點νi的度di不大于一個給定值bi。令T*dc是圖G的所有樹中滿足度約束的最小生成樹，則問題可描述為:。為方便起見，這里僅討論完全圖上的對稱問題，即，wij=wji，且bi=b對所有νi∈V。

二、染色體表達

dc-MST問題是MST問題加上度約束的擴展，所以染色體表達中應含有顯式的或隱式的各個端點的度信息。在幾種樹的編碼中，只有Prufer數編碼含有顯式端點的度的信息，在Prufer數編碼中度為d的端點正好出現d-1次。因此，通常采用Prufer數編碼。

三、交叉和變異

Prufer數編碼任意交叉和變異后仍代表一棵樹。簡單的采用單點交叉，變異則可隨機的變為1和n中的一個整數。由于存在度約束，無論是出始終群眾隨機產生的染色體，還是交叉或變異產生的后代都可能不滿足度約束，即為非法的。因此需要改進染色體中的非法端點，采用Prufer數編碼則容易做到。令是染色體中未做度檢查的端點集。如一個端點違反度約束，即編碼中該端點出現的次數大于d-1，那么將多出的端點隨機的替換為的其他端點就可減少該端點的度。

四、評估與選擇

評估過程由兩步組成:轉換染色體為樹;計算樹的總權。

令P為染色體是合格端點集。適值可以按權系數矩陣W=[wij]計算。

五、dc-MST算法

和傳統的遺傳算法相比，該算法的主要特點是為滿足度約束在簡單遺傳算法中嵌入了度改進步驟。整個dc-MST計算步驟如下:

begin

t←0; 初始化P(t); 改進P(t)的度; 評估P(t);

while不滿足終止條件 do

重組P(t)獲得C(t); 改進C(t)的度; 評估C(t)； 從P(t)和C(t)中選擇P(t+1);

t←t+1;

end

end

六、數值例子

以下例子是Savelsbergh和Volgenant給出的，它們用分支定界法求得的最優解的值為225。這是一個9節點的完全圖，下為9節點dc-MST問題的邊權重。

遺傳算法的參數設定如下:種群大小pop=size=50，交叉率pc=0.5，變異率pm=0.01，最大代數max_gen=500，所有端點的限定度b=3，運行30次。

用該GA算法，多數運行都能達到最優值2256。這表明，GA法不用啟發式或問題的專門性質，就能通過表達解的染色體的繁殖過程以高的概率達到最優解。

七、結論

比較兩種選擇策略。具體數據為:

說明了兩種方法都能獲得最優解，但采用混合選擇策略的GA比轉輪法的平均目標值和相對誤差都要好一些。

組合優化研究的是具有有限個可行解的優化問題。在日常生活中，特別是在工程設計中，有許多這樣的問題。其中一個重要而廣闊的應用領域就是如何有效的利用不充足的資源以提高生產效益。

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