遺傳算法在最小Steiner樹問題中的應用研究

陳智豪,楊天明

(江蘇農林職業技術學院基礎部，江蘇 句容 212400)

遺傳算法在最小Steiner樹問題中的應用研究

陳智豪,楊天明

(江蘇農林職業技術學院基礎部，江蘇 句容 212400)

簡單介紹了最小生成樹和最小Steiner生成樹的概念，通過實例(有線通訊網絡問題)提出了一種求解最小Steiner生成樹問題的遺傳算法。試驗結果表明，該算法能夠收斂到全局近似最優解。

遺傳算法；最小生成樹；最小Steiner生成樹

進化計算是人工智能(AI)領域的一種方法，它包括4種典型的計算方法。其中，遺傳算法(GA)相對來說比較成熟，是目前得到廣泛應用的方法。遺傳算法是一種模擬達爾文的自然選擇、自然淘汰、適者生存的生物進化過程的計算模型，通常實現方式是通過計算機來模擬遺傳的過程，常常用于在計算數學學科中解決最優化問題的搜索[1]。下面，筆者利用遺傳算法求解最小Steiner生成樹問題，從而利用該解法解決有線通訊網絡的布線問題。

1 最小生成樹和最小Steiner生成樹

在一個賦權連通圖G=(V,E)中，如果存在子圖G′包含G中所有頂點和一部分邊，且不形成回路，則稱G′為圖G的生成樹。其中，權值最小的生成樹則稱為最小生成樹。用于求解最小生成樹的算法之中最著名的也是最經典的就是Prim算法和Kruskal算法。如果除了已知的頂點之外還能夠添加一些點，那么就能得到多個最小生成樹了。而在所有最小生成樹中總權值最小的樹就是最小Steiner生成樹。增加的點則稱為Steiner點[1]。

結論1對于n個給定的點v1,v2,…,vn,最小Steiner生成樹T*總是存在的。

結論2對于n個給定的點v1,v2,…,vn,設最小Steiner生成樹T*中Steiner點的個數為s，則s≤n-2。

結論4已知平面上n個點為P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)，設：

xu=max{x1,x2,…,xn)xd=min{x1,x2,…,xn}

yu=max{y1,y2,…,yn}yd=min{y1,y2,…,yn}

那么所有Steiner點都必定包含在點集{(x,y)|xd≤x≤xu,yd≤y≤yu}之內。

以上4個結論表明：①最小Steiner生成樹存在；②Steiner點的個數不超過給定點個數減去2；③利用最小Steiner生成樹設計出的路線和最小生成樹相比較最多能夠縮短大約13.4%；④可以確定Steiner點的坐標取值范圍。

2 應 用

2.1 有線通訊網絡問題

設給定位于同一水平面上的16個通訊站，要在這些地點之間鋪設光纜，使得費用最少。每個地點作為圖G=(V,E)的一個頂點，頂點集V={P1,P2,…,P16}，地點的坐標見表1。

表1 各地點的坐標 (單位：m)

2.2 算法設計

遺傳算法是求解最小Steiner生成樹問題的一種近似解法，它是由染色體編碼方法、個體適應度評價、遺傳算子、運行參數共4個主要的要素構成的。

1)編碼與解碼 采用二進制編碼，也就是用由0和1這2個數字構成的字符串表示所有的個體，一個個體對應著一組待求的點。為了把搜索范圍限定在矩形框內，就要把矩形區域放縮到[0,1]×[0,1]的單位面積正方形，相應的每個點的坐標也要進行放縮。每個個體的二進制編碼結構如下：

其中，*是0或1。

一個個體是隨機生成的一個二進制字符串，長度是ws=ds×p。其中,ds是待求的Steiner點的個數，在運行程序時自己設定。p是一個待求點對應的二進制編碼長度，如果要求精確到小數點后第k位，則p=dx+dy，其中dx=[log2(10k×cx)]，dy=[log2(10k×cy)]。

對于一個個體的解碼，首先需要根據個體結構將個體的編碼分段，然后把每一段編碼轉換為十進制數字：

再把這些十進制的數字轉換為點的坐標(x1,y1),(x2,y2),…,(xds,yds)：

這樣就可以把用二進制編碼表示的個體解碼得到所有待求點的坐標了。

2)初始群體的選取 設種群規模為M，那么就根據要求的計算精度，隨機產生M個介于0和1之間用二進制碼表示的字符串，構造出初始種群。這M個互不重復的二進制字符串就形成了一個一個的個體。每個個體可以根據編碼與解碼中的辦法解碼得到待求點的坐標。

3)對種子的評價 對于某個個體所對應的生成樹，要判斷其優劣主要是看其目標函數值。取以已知點和待求點作為頂點的圖的最小生成樹長度作為目標函數值。這個值當然是越小越好。

接著，在[0,1]區間上隨機地產生M個數r。如果r落在第m個小區間內，則選擇保留與之對應的那個個體。這目標函數值越小則對應的小區間越短，在輪盤上占據的范圍就越小，那么該個體比較不容易被選中；反之，則更容易被選中。把這一步驟反復進行多次之后，適應度較高的個體將會有較大的可能被選中從而保留下來。

5)交叉 筆者采用是單點交叉操作，交叉點是隨機生成的，交叉概率pc=0.03。在執行交叉操作時，2個父代個體通過在隨機產生的交叉位處互換字符串的方式進行交叉。再把交叉產生的子代個體全部放入群體中，而執行過交叉操作的父代則舍棄。

6)變異 筆者采用單點變異操作[3]，變異概率為0.03。變異的基因位是隨機生成的，把要執行變異操作的基因位上的數0變成1或1變成0。

2.3 試驗

圖1 最小Steiner生成樹圖形

上述算法通過Mathematics7.0編程，在Windows7系統中運行通過。對于給出的上述16個站點，筆者經過多次試驗發現，當Steiner點的個數取為ds=3個時效果最好。利用筆者提出的解法隨機求解10次，算法迭代平均10次左右即可收斂到近似最優解，得到的最小Steiner生成樹的最優近似解為1651.854，和最小生成樹的結果1704.7相比較而言，總路徑長度縮短了3.1%。Steiner點的坐標分別是(217.961,289.078),(289.577,206.626),(579.942,100.617)。最小Steiner生成樹的圖形如圖1所示。

[1]雷英杰.Matlab遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.

[2]Du D Z，Hwang F K.A Proof of the Gilbert-Pollak conjecture on Steiner ratio[J].Algorithmica，1992(7):121-135.

[3]馬良，蔣馥.度限制最小樹的螞蟻算法[J].系統工程學報,1999,14(3):211-214 .

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.10.005

O242.2

A

1673-1409(2012)10-N013-02