歐氏Steiner最小樹的Delaunay三角網(wǎng)混合智能求解方法

王家楨， 馬 良， 張惠珍

（上海理工大學(xué)管理學(xué)院，上海 200093）

歐氏Steiner最小樹的Delaunay三角網(wǎng)混合智能求解方法

王家楨， 馬 良， 張惠珍

（上海理工大學(xué)管理學(xué)院，上海 200093）

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

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

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

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

本文基于計算幾何中Delaunay三角網(wǎng)［3］的相關(guān)理論，利用智能算法，設(shè)計了一種改進型的混合智能求解方法.其特點在于從幾何的角度入手，結(jié)合了智能算法的優(yōu)點，大幅度提高了算法在尋找更好拓撲結(jié)構(gòu)上的有效性.

1 歐氏Steiner最小樹問題

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

下面，先列出幾條關(guān)于Steiner最小樹的基本性質(zhì)［4-6］：

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

性質(zhì)2SMT上任何1個頂點的關(guān)聯(lián)邊不多于3條.

性質(zhì)3SMT上與s-點相關(guān)聯(lián)的邊必定為3條，且這3條邊中任意兩邊夾角為120°.

性質(zhì)4設(shè)SMT的原點為n個，則s-點的數(shù)目小于等于（n-2）.

性質(zhì)5假設(shè)由n個原點所圍成的區(qū)域為凸包，則所有s-點都必定包含在凸包內(nèi).

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

2 Delaunay三角網(wǎng)

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

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

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

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

Delaunay三角網(wǎng)具有兩個非常重要的性質(zhì)［8］：

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

b.最大的最小角性質(zhì).在由點集V所能形成的三角網(wǎng)中，D-三角網(wǎng)中三角形的最小角度是最大的.

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

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

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

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

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

4 算法描述及示例

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

第一步對平面上給定的正則點構(gòu)建Delaunay三角網(wǎng)，如圖2所示.

圖2 Delaunay三角網(wǎng)示意圖1Fig.2 Delaunay triangulation 1

這里不贅述構(gòu)建Delaunay三角網(wǎng)的算法，該步驟在Matlab中操作起來比較簡單，只需直接調(diào)用Delaunay函數(shù)即可.

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

圖3 Delaunay三角網(wǎng)示意圖2Fig.3 Delaunay triangulation 2

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

圖4 Delaunay三角網(wǎng)示意圖3Fig.4 Delaunay triangulation 3

多邊形剖分遵循如下規(guī)則：

a.剖分必須沿著Delaunay三角網(wǎng)中三角形的邊；

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

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

圖5 滿拓撲結(jié)構(gòu)示意圖Fig.5 Full topology structure

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

a.染色體的產(chǎn)生

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

b.染色體的適應(yīng)度

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

c.染色體的選擇

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

d.染色體的交叉

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

e.染色體的變異

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

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

第五步選擇適當?shù)臐M拓撲結(jié)構(gòu)，構(gòu)成最終解.

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

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

圖6 示例滿拓撲結(jié)構(gòu)Fig.6 Full topology structure of the example

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

圖7 示例結(jié)果Fig.7 Result of the example

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

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

圖8（a）具有3個滿拓撲結(jié)構(gòu)的正則點個數(shù)均為3，而圖8（b）具有的3個滿拓撲結(jié)構(gòu)的正則點個數(shù)為3，4，5.很明顯，圖8（b）的拓撲結(jié)構(gòu)要優(yōu)于圖8（a）的拓撲結(jié)構(gòu).

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

5 實例測試

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

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

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

表2 直接使用遺傳算法求得的結(jié)果（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點，且均為正則點個數(shù)為3的滿拓撲結(jié)構(gòu)；圖9（b）為使用本文上述算法，求得了6個Steiner點，分別形成了正則點個數(shù)為3，4，5的3個滿拓撲結(jié)構(gòu).

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

表3 使用本文算法求得的結(jié)果（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 正則點個數(shù)為50的實例數(shù)據(jù)Tab.4 Data for terminal vertices number of 50

表6 使用本文算法求得的結(jié)果（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點，且均為正則點個數(shù)為3的滿拓撲結(jié)構(gòu)；圖10（b）為使用本文上述算法，求得了15個Steiner點，分別形成了5個正則點個數(shù)為3的滿拓撲結(jié)構(gòu)和5個正則點個數(shù)為4的滿拓撲結(jié)構(gòu).

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

6 結(jié)束語

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

作為初步嘗試，本文中的智能算法環(huán)節(jié)，僅選取了遺傳算法作為基本方法，此環(huán)節(jié)可替換為其它的智能算法進行求解，亦可得到相應(yīng)的改善和優(yōu)化，有關(guān)工作將在后續(xù)研究中展開.

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

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

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

［4］ 越民義.最小網(wǎng)絡(luò)——斯坦納樹問題［M］.上海：上海科學(xué)技術(shù)出版社，2006.

［5］ 丁雪楓，馬良，丁雪松.基于模擬植物生長算法的構(gòu)造通訊網(wǎng)絡(luò)Steiner最優(yōu)樹方法［J］.上海理工大學(xué)學(xué)報，2010，32（1）：88-91.

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

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

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

［9］ 金慧敏.歐氏Steiner最小樹問題的智能優(yōu)化算法研究［D］.上海：上海理工大學(xué)，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］ 王曉東.計算機算法設(shè)計與分析［M］.北京：電子工業(yè)出版社，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

上海市一流學(xué)科建設(shè)資助項目（S1201YLXK）；滬江基金項目（A14006）；上海市教委科研創(chuàng)新項目（14YZ090）；高校博士點專項科研基金聯(lián)合資助項目（20123120120005）；上海高校青年教師培養(yǎng)資助計劃（SLG12010）；上海理工大學(xué)國家級項目培育項目（13XGQ07）

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

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

1007-6735（2014）04-0351-06

10.13255／j.cnki.jusst.2014.04.009