用遺傳算法求最小生成樹

朱彥廷

(廣西現代職業技術學院計算機系，廣西河池547000)

0 引言

生成樹是圖論的一個重要概念，許多工程問題，如通訊、交通、供電和給排水等網絡設計，通常都可以轉化為求最小生成樹問題.不同的最小生成樹代表不同的方案，因為權值有時與幾個因素(如路途遠近、路況好壞，拆遷難易等)都有關，很難定得十分合理，幾棵最小生成樹，往往有一棵是最好的方案，有時某棵次小生成樹甚至是一個更好的方案.因此，最好能找出幾棵最小或次小生成樹，然后再加斟酌，決策將更為科學.

使用經典算法，如Kruskal、Prim、Sollin算法，一般只能找出一棵最小生成樹.遺傳算法是一種模擬生物進化過程的算法，對求解組合優化問題很是有效，尋找最小生成樹其實也是組合優化問題，可以考慮使用.

設一無向圖共有n個頂點，m條邊.用遺傳算法求最小樹，編碼方法幾乎都是邊編碼，對邊進行編號，一個個體是一個二進制代碼，長為m，代表圖的一個子圖，若某位為1，表示它所對應的邊是子圖的邊;若為0，表示它所對應的邊不是子圖的邊，因為一棵過n個項點的樹有n－1條邊，且是連通的，因而應使個體只有n－1位為1(否則肯定不代表生成樹)，然后對它代表的子圖進行遍歷，若能訪問到n個頂點，則子圖是連通的，是一棵生成樹.交叉、變異算子極可能破壞個體的可行性，即產生的新個體不是只有n－1位為1，不能直接使用，要進行變通，如文獻［4］改成換位算子、逆轉算子，相當于舍棄了交叉算子，修改了變異算子.在此，采用節點編碼，對節點進行編號.

1 基本原理

根據圖論中的Cayley定理，一個有n個頂點的完全圖有nn－2棵不同的生成樹，而由乘法原理，n－2個1～n之間的數有nn－2個不同的排列，兩者可以是一一對應關系.這個排列通常稱為Prufer數.例如，圖1(a)是一個完全圖，(b)是該圖的一棵生成樹，對應的排列是22.

圖1 無向圖和生成樹

一棵生成樹對應的排列可以這樣構造:規定編號為n的節點為根節點，找到樹上標號最小的葉子節點i，則它的雙親節點j是排列的第一個數，刪除節點i及邊(i，j).重復上述過程，直到只剩下一條邊，得到一個n－2個數字的排列.

反過來，一個排列對應的生成樹可以這樣構造:找到最小的不在排列中而且未使用的節點i，設排列的第一個數是j，則(i，j)是樹的一條邊，從排列中刪去j，并把i標記為已使用.重復上述過程，直到排列為空，這時還未使用的2個節點一個是n，另一個設為k，再加上邊(k，n)，得到生成樹的n－1條邊.

2 算法設計

2.1 編碼采用十進制編碼，一個個體有n－2位，每位取值范圍是1～n，代表完全圖的一棵生成樹.

2.2 適應度函數生成樹各邊的權值的和越小，適應度應該越大.設圖的各邊的權值分別為W1，W2，…，Wm.由個體得到完全圖的生成樹，如果它的各邊在圖中都存在，是圖的生成樹，適應度為

其中，F0=(n－1)max(W1，W2，…，Wm)，是完全圖的生成樹的邊的集合，x是大于0的常數;如果有一條邊不存在，不是圖的生成樹，適應度最小，為x.

2.3 遺傳算子

2.3.1 選擇算子采用賭輪選擇(依據如表1，注意個體適應度的最小值是100(不是生成樹)，最大值是139(最小生成樹)，范圍很小)，用個體的適應度與群體中個體的適應度的總和之比作為其被選擇的概率，個體的適應度越高，被選擇的概率將越大.因為選擇是基于概率做出的，適應度低的個體也可能被選擇，這有助于維持群體多樣性.如果適應度函數中x等于0，最初很可能各個個體的適應度都為0(對于本問題，找到一棵生成樹很不容易)，從而適應度的總和為0，無法計算個體被選擇的概率，因此x應大于0，還應使適應度最大值、最小值的比值不致太大，以免出現早熟現象(在算法運行的初期，如果產生個別適應度非常高的個體，它們將很快充斥群體，使進化難以繼續，陷于局部最優).

表1 是否采用賭輪選擇性能對比

2.3.2 交叉算子采用單點交叉，從群體中隨機選擇2個個體，隨機產生交叉位，交換它們該位后面的串，得到2個新個體.例如對于個體111111和222222，設產生的交叉位為3，則交換后產生的新個體分別為111222、222111.

2.3.3 變異算子先采用基本位變異，對交叉后的個體，隨機產生變異位，變換該位，得到新個體.例如對于個體111111，設產生的變異位為3，隨機產生的變換位為5，則變異后產生的新個體為115111.然后進行比較(依據如表2)，如果新個體不如原個體，放棄變異，即保留好的變異，舍棄壞的變異，這樣如果變異產生的新個體不如原個體，不會有什么不利影響.生物進化到現在這個程度，用了幾十億年，因而恐怕不能說是十分完美的，遺傳算法不應單純的模仿進化，也應有所選擇.

表2 是否進行比較性能對比

2.3.4 整理算子這是本算法特有的算子.算法追求的是找出盡可能多的最小、次小生成樹.本問題比較特殊，好的父代個體產生好的子代個體的可能性小些，如果沒有本算子，最后得到的個體適應度幾乎都很低，沒有什么價值.為了保存較好的個體(如果是最小、次小生成樹，非常珍貴)，將新群體、原群體混合，選出最好的且不重復(對于本問題，較好的個體較少，如果不加這個限制，個別較好的個體可能充斥群體)的個體(約占群體中個體數目的80%)，這將最大限度地保存較好的個體，再隨機產生少量個體(約占群體中個體數目的20%，這將增大搜索空間.依據如表3)，合起來組成下代群體.

表3 是否隨機產生少量個體性能對比

這樣如果交叉產生的新個體不及原個體，也沒有什么不利影響.因此使用本算法，可以放心交叉、變異，無須擔心交叉、變異概率設置得是否合適(這2個參數設置得過大、過小都將影響算法的性能［4］，最好不固定，隨著算法的運行而變化［5］(但實現將更復雜)).

2.4 算法流程

(1)設置群體大小M、最大進化代數T，適應度函數中的常數x;

(2)隨機生成M個個體作初始群體，計算各個個體的適應度;

(3)如果進化代數t=T，轉到(9);(4)選擇;

(5)交叉; (6)變異;

(7)整理，得到下代群體; (8)t=t+1，轉到(3); (9)輸出最終群體.

3 實例

要建立一給水網絡，有10個節點，23條可能的線路，如圖1所示(括號中為線路長度)，求一組線路總長度最短或次短的方案.采用經典算法，一般只能得到一棵權為60的最小生成樹.應用本算法，取M=10，T=1000，x=100，運行20次，最終群體中個體的平均適應度為136.6，最高為138.4，最低為133.3，可見算法雖然帶有隨機性，結果不確定，但還是很有效的，其中第19次結果如表1所示(用c語言實現時，為了方便，將節點編號1～10依次改為0～9)，獲得8棵最小、次小生成樹(最后2個個體是隨機產生的，不代表生成樹)，其中1 號個體對應的邊是:(1，5)，(0，1)，(2，0)，(4，7)，(3，4)，(2，3)，(6，2)，(8，6) ，(9，8)，即第 5、1、2、15、11、7、10、19、23條邊，可以結合其它因素確定具體選擇哪種方案.

表4 最終群體

圖2 建立給水網絡資料

為了取得更好的效果，可以先用經典算法求出一棵最小生成樹，從而得到個體適應度的最大值，如果群體中有一個個體的適應度達到(或接近)這個值，標志著進化已經達到較高的階段，可以考慮停止進化.

4 結束語

和邊編碼比較起來，節點編碼編碼較短(如果邊數很多，應采用這種方式，以免編碼過長)，產生的個體代表完全圖的生成樹，只要各邊在(實際的)圖中都存在就肯定是生成樹，無須另行檢驗(過程比較繁瑣)，交叉、變異算子基本都可以直接使用，但把個體轉換成完全圖的生成樹(實際是找出它的各條邊)實現不太容易.

［1］孫小軍，劉三陽，王志強.一種求解最小生成樹問題的算法［J］.計算機工程，2011，37(23):241－243.

［2］朱曉虹.量子遺傳算法求解度約束最小生成樹［J］.巢湖學院學報，2010，42(6):38－42.

［3］何忠華，孟祥瑞.基于節點編碼的最小生成樹算法［J］.黑龍江科技信息，2008(34):90.

［4］劉志成，錢建剛.基于改進遺傳算法的最小生成樹算法［J］.計算機工程與設計，2004，25(9):1620－1622.

［5］陳曦，林濤，唐賢瑛.遺傳算法的參數設計與性能研究［J］.計算機工程與設計，2004，25(8):1309－1310.