歐氏Steiner最小樹的Delaunay三角網混合智能求解方法

王家楨， 馬 良， 張惠珍

（上海理工大學管理學院，上海 200093）

歐氏Steiner最小樹的Delaunay三角網混合智能求解方法

王家楨， 馬 良， 張惠珍

（上海理工大學管理學院，上海 200093）

歐氏Steiner最小樹問題是組合優化中一個經典的NP難題，在許多實際問題中有著廣泛的應用.由于使用普通智能算法求解較大規模問題時，極易陷入拓撲結構的局部最優，因此，基于Delaunay三角網技術并結合智能算法的有關思想，設計了一種改進的混合型智能求解方法，可大幅度提高算法在尋找更好拓撲結構上的有效性.算法在Matlab環境下編程實現，經大量STEINLIB中的標準數據實例測試和驗證，獲得了滿意的效果，為求解較大規模的歐氏Steiner最小樹問題提供了新的有效方法.

歐氏Steiner最小樹；Delaunay三角網；多邊形剖分；智能算法

Steiner樹問題［1-2］是指連接給定點的最小樹長問題，其最優解稱為Steiner最小樹（Steiner minimum tree，SMT）.該問題在實際中有著廣泛的應用，如通信網絡設計、印刷電路板設計、傳輸線布線等.

根據點和連線的空間屬性，Steiner樹問題可進一步細分為歐氏Steiner樹（Euclidean Steiner tree，EST）問題和絕對值距離Steiner樹（rectilinear Steiner tree，RST）問題（連線只有水平和垂直兩種形式）.雖然已有精確算法可用于求解此類問題，但由于Steiner樹問題已被證明是組合優化中的一個NP難題，現實而合理的辦法往往是設計各種啟發式算法以尋求問題的滿意解.

本文基于計算幾何中Delaunay三角網［3］的相關理論，利用智能算法，設計了一種改進型的混合智能求解方法.其特點在于從幾何的角度入手，結合了智能算法的優點，大幅度提高了算法在尋找更好拓撲結構上的有效性.

1 歐氏Steiner最小樹問題

給定原點集X（也稱正則點集），歐氏Steiner樹是指在歐氏平面上連接點集X中所有點的最短樹.由于允許增加輔助點集S（s-點集），因此，Steiner最小樹問題的本質就是尋求點集S，使得連接X∪S的生成樹最小.

下面，先列出幾條關于Steiner最小樹的基本性質［4-6］：

性質1SMT上任何兩條鄰接邊的夾角不小于120°.

性質2SMT上任何1個頂點的關聯邊不多于3條.

性質3SMT上與s-點相關聯的邊必定為3條，且這3條邊中任意兩邊夾角為120°.

性質4設SMT的原點為n個，則s-點的數目小于等于（n-2）.

性質5假設由n個原點所圍成的區域為凸包，則所有s-點都必定包含在凸包內.

性質6SMT中每個葉子都是原點，若能設法求出s-點的個數及其位置，就可用常規的最小生成樹算法求得SMT，因此，問題的關鍵是尋找s-點.

2 Delaunay三角網

Delaunay三角網是Voronoi圖（也稱為Dirichlet圖）的伴生圖形，對它的研究是從對Voronoi圖的研究開始的［7］.

Voronoi圖定義假設V=｛v1，v2，…，vn｝，n≥3是歐氏平面上的一個點集，并且這些點不共線，4點不共圓，d（vi，vj）表示點vi，vj間的歐氏距離.設x為平面上的點，則區域V（i）=｛x∈E2｜d（x，vi）≤d（x，vj），j=1，2，…，n，j≠i｝稱為Voronoi多邊形，E2表示二維歐氏空間，各點的Voronoi多邊形共同組成Voronoi圖.

平面上的Voronoi圖可以看作是點集V中的每個點作為生長核以相同的速率向外擴張，直到彼此相遇為止而在平面上形成的圖形.除最外層的點形成開放的區域外，其余每個點都形成一個凸多邊形.

Delaunay三角網定義有公共邊的Voronoi多邊形稱為相鄰的Voronoi多邊形，連接所有相鄰的Voronoi多邊形的生長中心所形成的三角網稱為Delaunay三角網.Delaunay三角網的外界是一個凸多邊形，它由連接V中的凸集形成，通常稱為凸殼.

Delaunay三角網具有兩個非常重要的性質［8］：

a.空外接圓性質.在由點集V所形成的D-三角網中，其每個三角形的外接圓均不包含點集V中的其它任意點.

b.最大的最小角性質.在由點集V所能形成的三角網中，D-三角網中三角形的最小角度是最大的.

由于這兩個性質，決定了Delaunay三角網具有極大的應用價值.同時，它也是二維平面三角網中唯一的、最好的.

3 普通智能算法求解Steiner樹時的缺陷

圖1（a）中是一株正則點個數n為5的歐氏Steiner最小樹，且為滿拓撲結構，使用的求解方法是遺傳算法.圖1（b）中是一株正則點個數n為15的歐氏Steiner最小樹，使用的求解方法也是遺傳算法.在圖1（b）中有5個正則點和圖1（a）中的5個正則點的位置完全相同.但非常遺憾的是，圖1（b）中同樣位置的5個點并沒有構成滿拓撲結構.這說明僅僅使用普通的智能算法求解歐氏Steiner最小樹，拓撲結構極易陷入局部最優，而且當正則點個數較多時，一旦拓撲結構陷入了局部最優，智能算法幾乎不可能跳出這樣的局部最優.

圖1 智能算法缺陷示意圖Fig.1 Shortcoming of basic intelligent algorithm

因此，針對上述問題，本文提出了一種與Delaunay剖分有關的混合智能方法來求解歐氏Steiner最小樹，能夠在很大程度上避免拓撲結構陷入局部最優.

4 算法描述及示例

歐氏Steiner最小樹的Delaunay三角網混合智能算法具體步驟如下：

第一步對平面上給定的正則點構建Delaunay三角網，如圖2所示.

圖2 Delaunay三角網示意圖1Fig.2 Delaunay triangulation 1

這里不贅述構建Delaunay三角網的算法，該步驟在Matlab中操作起來比較簡單，只需直接調用Delaunay函數即可.

第二步將這些三角形中3個內角均小于120°的三角形找出來，如圖3所示.

圖3 Delaunay三角網示意圖2Fig.3 Delaunay triangulation 2

第三步對3個內角均小于120°的三角形集合區域進行多邊形剖分，如圖4所示.

圖4 Delaunay三角網示意圖3Fig.4 Delaunay triangulation 3

多邊形剖分遵循如下規則：

a.剖分必須沿著Delaunay三角網中三角形的邊；

b.找出每個三角形的最長邊，如果該最長邊為某兩個三角形的公共邊，則將這兩個三角形拼接在一起.

第四步利用智能算法對每一塊區域所含的正則點逐塊進行Steiner點的求解，如圖5所示.

圖5 滿拓撲結構示意圖Fig.5 Full topology structure

本環節所使用的智能算法為遺傳算法.遺傳算法［9］是一類借鑒生物進化思想的隨機優化算法，通過選擇、交叉、變異等操作產生下一代的解，并逐步淘汰掉適應度值較低的解，獲得適應度值較高的解，經過多次這樣的操作得出適應度最高的解.

a.染色體的產生

染色體的長度為2（n-2），其中，n為正則點的個數.每一個點的坐標產生方式為，隨機選擇一個三角形［10］，在這個三角形中生成一個隨機點.用｛x1，y1，x2，y2，…，xn-2，yn-2｝這樣的形式表示n-2個點的坐標，每兩個數字表示一個點的坐標.

b.染色體的適應度

目標是生成樹的長度最小化，因此適應度為該染色體中的Steiner點和正則點求得的最小生成樹長度的倒數.

c.染色體的選擇

利用隨機遍歷抽樣法（stochastic universal sampling，簡記SUS），此方法與輪盤賭選擇法基本相似，是對輪盤賭選擇法的一種改進，特點是只要進行一次輪盤旋轉.其采用均勻分布且個數等于種群規模的旋轉指針，等距離選擇個體.其中第一個指針位置由［0，1／H］區間的均勻隨機數決定，H代表旋轉指針的個數.該方法提供了零偏差和最小個體擴展.

d.染色體的交叉

本文采用2-opt法進行交叉.需要注意的是，染色體斷開的位置必須為偶數位置，目的是不把一個點的x坐標和y坐標割裂開來.

e.染色體的變異

隨機刪除染色體中的一個點的坐標，重新隨機選擇一個三角形，在其中生成一個隨機點加入染色體中.

按上述步驟，對“第三步”剖分之后的每一個區域都使用一次遺傳算法，得到每一塊區域中的滿拓撲結構.

第五步選擇適當的滿拓撲結構，構成最終解.

第四步中求得的所有滿拓撲結構，并不能同時存在于最終的解中，例如本示例中圖6的滿拓撲結構1和滿拓撲結構2不可能同時存在于最終解.

在滿拓撲結構數量較小的情況下（如10以內的規模），可使用經典算法［11］，諸如分支定界法或回溯法等，精確地求得應選擇哪些拓撲結構.但是在滿拓撲結構數量較大的情況下，解空間的大小為2p，p為第四步中所求得的所有滿拓撲結構個數，其時間復雜度為O（2p），用經典算法將在計算時間上達到難以容忍的程度.因此，這一步驟依然采用遺傳算法進行求解.其中染色體的長度為滿拓撲結構的個數，變量均為布爾型變量，0代表不選擇該滿拓撲結構，1代表選擇該拓撲結構.

圖6 示例滿拓撲結構Fig.6 Full topology structure of the example

本示例求得的最終解如圖7所示，入選的滿拓撲結構有圖6中的滿拓撲結構1，3，5.

圖7 示例結果Fig.7 Result of the example

將圖1（b）和圖7放在一起進行比較，如圖8所示.

圖8 改進效果對比Fig.8 Comparison of improvements

圖8（a）具有3個滿拓撲結構的正則點個數均為3，而圖8（b）具有的3個滿拓撲結構的正則點個數為3，4，5.很明顯，圖8（b）的拓撲結構要優于圖8（a）的拓撲結構.

整個算法的時間復雜度主要來自有限次數的遺傳算法，因此，該算法的時間復雜度等同于遺傳算法的時間復雜度.整個算法的時間復雜度為O（MNn2）.其中，M為遺傳代數，N為群體規模，n為正則點個數.

5 實例測試

為檢驗算法的有效性，上述算法用Matlab編程實現，并在國際通用的測試數據庫STEINLIB中選取一系列的實例數據進行了測試，部分結果如下所示.

表1為一個正則點個數為16的實例，給出了16個正則點的坐標；表2是直接使用遺傳算法所求得的s-點的坐標；表3是使用本文中改進后算法所求得的s-點的坐標.

表1 正則點個數為16的實例數據Tab.1 Data for terminal vertices number of 16

表2 直接使用遺傳算法求得的結果（n=16）Tab.2 Results of Steiner points by basic genetic algorithm（n=16）

正則點的最小生成樹長度為2.400 4，直接使用遺傳算法求得Steiner樹長為2.349 0，使用本文上述算法求得Steiner樹長為2.345 9.如圖9所示，圖9（a）為直接使用遺傳算法，僅求得了3個Steiner點，且均為正則點個數為3的滿拓撲結構；圖9（b）為使用本文上述算法，求得了6個Steiner點，分別形成了正則點個數為3，4，5的3個滿拓撲結構.

下面用一個規模更大的實例來進一步證明算法的有效性，表4為一個正則點個數為50的實例，給出了50個正則點的坐標.表5（見下頁）是直接使用遺傳算法所求得的s-點的坐標；表6（見下頁）是使用本文中改進后算法所求得的s-點的坐標.

表3 使用本文算法求得的結果（n=16）Tab.3 Results of Steiner points by the modified algorithm（n=16）

圖9 改進效果對比（n=16）Fig.9 Comparison of improvements（n=16）

表4 正則點個數為50的實例數據Tab.4 Data for terminal vertices number of 50

表6 使用本文算法求得的結果（n=50）Tab.6 Results of Steiner points by the modified algorithm（n=50）

正則點的最小生成樹長度為5.143 1，直接使用遺傳算法求得Steiner樹長為5.046 3，使用本文上述算法求得Steiner樹長為4.976 3.如圖10所示，圖10（a）為直接使用遺傳算法，僅求得了5個Steiner點，且均為正則點個數為3的滿拓撲結構；圖10（b）為使用本文上述算法，求得了15個Steiner點，分別形成了5個正則點個數為3的滿拓撲結構和5個正則點個數為4的滿拓撲結構.

圖10 改進效果對比（n=50）Fig.10 Comparison of improvements（n=50）

6 結束語

經大量實例測試和結果比較表明，本文給出的混合智能算法在拓撲結構上明顯優于直接使用遺傳算法，在求解Steiner最小樹問題上，可起到很好的優化作用，且算法思路簡單直觀、易于實現，對現實中有關實際應用問題的解決提供了方便的求解手段和工具.

作為初步嘗試，本文中的智能算法環節，僅選取了遺傳算法作為基本方法，此環節可替換為其它的智能算法進行求解，亦可得到相應的改善和優化，有關工作將在后續研究中展開.

［1］ 馬良，寧愛兵.高級運籌學［M］.北京：機械工業出版社，2008.

［2］ 馬良，朱剛，寧愛兵.蟻群優化算法［M］.北京：科學出版社，2008.

［3］ Green P J，Sibson R.Computing Dirichlet tessellations in the plane［J］.The Computer Journal，1978，21（2）：168-173.

［4］ 越民義.最小網絡——斯坦納樹問題［M］.上海：上?？茖W技術出版社，2006.

［5］ 丁雪楓，馬良，丁雪松.基于模擬植物生長算法的構造通訊網絡Steiner最優樹方法［J］.上海理工大學學報，2010，32（1）：88-91.

［6］ 張瑾，單貴，馬良.基于電勢的最優加權Steiner樹螞蟻算法及其選址應用［J］.上海理工大學學報，2009，31（3）：283-285.

［7］ 武曉波，王世新，肖春生.Delaunay三角網的生成算法研究［J］.測繪學報，1999，28（1）：28-35.

［8］ 周培德.計算幾何：算法設計與分析［M］.北京：清華大學出版社，2011.

［9］ 金慧敏.歐氏Steiner最小樹問題的智能優化算法研究［D］.上海：上海理工大學，2005.

［10］ van Laarhoven J W，Ohlmann J W.A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in R-d［J］.Journal of Heuristics，2011，17（4）：353-372.

［11］ 王曉東.計算機算法設計與分析［M］.北京：電子工業出版社，2001.

（編輯：丁紅藝）

Hybrid Intelligent Algorithm Based on Delaunay Triangulation for Euclidean Steiner Minimum Tree Problem

WANGJia-zhen， MA Liang， ZHANGHui-zhen
（Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

Euclidean Steiner minimum tree problem is a classical NP-hard problem in combination optimization，with a wide range of applications in many practical problems.Because of the easiness of getting stuck into local optimal topology by using general intelligent algorithms for large scale problems，a combination of Delaunay triangulation technique and intelligent algorithm wasintroduced to design a hybrid intelligent method，which can apparently improve the effectiveness of searching for better topology structures.The proposed algorithm was coded in Matlab，and was tested through series of standard instances from STEINLIB.The algorithm can obtain satisfied results and provide a new effective way to solve the problem of large scale Euclidean Steiner minimum tree.

Euclidean Steiner minimum tree；Delaunay triangulation；polygon decomposition；intelligent algorithm

TP 301.6

A

2013-07-20

上海市一流學科建設資助項目（S1201YLXK）；滬江基金項目（A14006）；上海市教委科研創新項目（14YZ090）；高校博士點專項科研基金聯合資助項目（20123120120005）；上海高校青年教師培養資助計劃（SLG12010）；上海理工大學國家級項目培育項目（13XGQ07）

王家楨（1988-），女，碩士研究生.研究方向：智能優化、系統工程.E-mail：ggggpeushmy＠foxmail.com

馬 良（1964-），男，教授.研究方向：智能優化、系統工程.E-mail：maliang＠usst.edu.cn

1007-6735（2014）04-0351-06

10.13255／j.cnki.jusst.2014.04.009