陳智豪,楊天明

(江蘇農(nóng)林職業(yè)技術(shù)學(xué)院基礎(chǔ)部，江蘇 句容 212400)

遺傳算法在最小Steiner樹問題中的應(yīng)用研究

陳智豪,楊天明

(江蘇農(nóng)林職業(yè)技術(shù)學(xué)院基礎(chǔ)部，江蘇 句容 212400)

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

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

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

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

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

結(jié)論1對(duì)于n個(gè)給定的點(diǎn)v1,v2,…,vn,最小Steiner生成樹T*總是存在的。

結(jié)論2對(duì)于n個(gè)給定的點(diǎn)v1,v2,…,vn,設(shè)最小Steiner生成樹T*中Steiner點(diǎn)的個(gè)數(shù)為s，則s≤n-2。

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

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

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

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

以上4個(gè)結(jié)論表明：①最小Steiner生成樹存在；②Steiner點(diǎn)的個(gè)數(shù)不超過給定點(diǎn)個(gè)數(shù)減去2；③利用最小Steiner生成樹設(shè)計(jì)出的路線和最小生成樹相比較最多能夠縮短大約13.4%；④可以確定Steiner點(diǎn)的坐標(biāo)取值范圍。

2 應(yīng) 用

2.1 有線通訊網(wǎng)絡(luò)問題

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

表1 各地點(diǎn)的坐標(biāo) (單位：m)

2.2 算法設(shè)計(jì)

遺傳算法是求解最小Steiner生成樹問題的一種近似解法，它是由染色體編碼方法、個(gè)體適應(yīng)度評(píng)價(jià)、遺傳算子、運(yùn)行參數(shù)共4個(gè)主要的要素構(gòu)成的。

1)編碼與解碼 采用二進(jìn)制編碼，也就是用由0和1這2個(gè)數(shù)字構(gòu)成的字符串表示所有的個(gè)體，一個(gè)個(gè)體對(duì)應(yīng)著一組待求的點(diǎn)。為了把搜索范圍限定在矩形框內(nèi)，就要把矩形區(qū)域放縮到[0,1]×[0,1]的單位面積正方形，相應(yīng)的每個(gè)點(diǎn)的坐標(biāo)也要進(jìn)行放縮。每個(gè)個(gè)體的二進(jìn)制編碼結(jié)構(gòu)如下：

其中，*是0或1。

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

對(duì)于一個(gè)個(gè)體的解碼，首先需要根據(jù)個(gè)體結(jié)構(gòu)將個(gè)體的編碼分段，然后把每一段編碼轉(zhuǎn)換為十進(jìn)制數(shù)字：

再把這些十進(jìn)制的數(shù)字轉(zhuǎn)換為點(diǎn)的坐標(biāo)(x1,y1),(x2,y2),…,(xds,yds)：

這樣就可以把用二進(jìn)制編碼表示的個(gè)體解碼得到所有待求點(diǎn)的坐標(biāo)了。

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

3)對(duì)種子的評(píng)價(jià) 對(duì)于某個(gè)個(gè)體所對(duì)應(yīng)的生成樹，要判斷其優(yōu)劣主要是看其目標(biāo)函數(shù)值。取以已知點(diǎn)和待求點(diǎn)作為頂點(diǎn)的圖的最小生成樹長(zhǎng)度作為目標(biāo)函數(shù)值。這個(gè)值當(dāng)然是越小越好。

接著，在[0,1]區(qū)間上隨機(jī)地產(chǎn)生M個(gè)數(shù)r。如果r落在第m個(gè)小區(qū)間內(nèi)，則選擇保留與之對(duì)應(yīng)的那個(gè)個(gè)體。這目標(biāo)函數(shù)值越小則對(duì)應(yīng)的小區(qū)間越短，在輪盤上占據(jù)的范圍就越小，那么該個(gè)體比較不容易被選中；反之，則更容易被選中。把這一步驟反復(fù)進(jìn)行多次之后，適應(yīng)度較高的個(gè)體將會(huì)有較大的可能被選中從而保留下來。

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

6)變異 筆者采用單點(diǎn)變異操作[3]，變異概率為0.03。變異的基因位是隨機(jī)生成的，把要執(zhí)行變異操作的基因位上的數(shù)0變成1或1變成0。

2.3 試驗(yàn)

圖1 最小Steiner生成樹圖形

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

[1]雷英杰.Matlab遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，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].系統(tǒng)工程學(xué)報(bào),1999,14(3):211-214 .

[編輯] 洪云飛

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

O242.2

A

1673-1409(2012)10-N013-02