陳智豪，侯為根，楊天明

(1.江蘇農(nóng)林職業(yè)技術(shù)學(xué)院，江蘇 句容 212400； 2.安徽工業(yè)大學(xué)，安徽 馬鞍山 243002)

?

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

陳智豪1，侯為根2，楊天明1

(1.江蘇農(nóng)林職業(yè)技術(shù)學(xué)院，江蘇 句容 212400； 2.安徽工業(yè)大學(xué)，安徽 馬鞍山 243002)

摘要：在對遺傳算法、最小生成樹和最小steiner生成樹的概念作簡單介紹之后，給出了一種改進(jìn)后的求解最小steiner生成樹問題的遺傳算法。通過實(shí)例通信網(wǎng)絡(luò)構(gòu)建的仿真實(shí)驗(yàn)，說明改進(jìn)后的算法能夠更好地收斂到局部近似最優(yōu)解，并分析了算法的優(yōu)缺點(diǎn)。

關(guān)鍵詞：遺傳算法；最小生成樹；最小steiner生成樹；通信網(wǎng)絡(luò)

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.009

進(jìn)化計算是人工智能(AI) 中的一種方法，被稱為世界三大尖端技術(shù)之一。進(jìn)化計算包括遺傳算法(GA)、遺傳規(guī)劃、進(jìn)化策略和進(jìn)化規(guī)劃等4種典型的計算方法，其中GA算法相對比較成熟，也是目前應(yīng)用廣泛的方法。GA算法是一種模擬達(dá)爾文的自然選擇、自然淘汰、適者生存的生物進(jìn)化過程[1]的計算模型，它通常是通過計算機(jī)來模擬遺傳過程的方式來實(shí)現(xiàn)，常用于計算數(shù)學(xué)中最優(yōu)化問題的搜索。

1最小生成樹和最小steiner生成樹

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

結(jié)論1[3]對于n個給定的點(diǎn)v1,v2,…,vn，最小steiner生成樹T*總是存在的。

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

結(jié)論4設(shè)由n個已知點(diǎn)所圍成的區(qū)域?yàn)橥拱?，則所有steiner點(diǎn)都必定包含在凸包內(nèi)。

2遺傳算法在最小steiner樹問題中的應(yīng)用

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

設(shè)給定位于同一水平面上的16個通訊站，要在這些站點(diǎn)之間鋪設(shè)光纜，使得費(fèi)用最少。每個站點(diǎn)作為圖G=(V,E)的一個頂點(diǎn)，頂點(diǎn)集V={P1,P2,…,P16}，站點(diǎn)的坐標(biāo)見表1。邊集E={PiPj,i=1,2,…,16,j=1,2,…,16,i≠j}，各個地點(diǎn)之間的直線距離作為邊的權(quán)，由于數(shù)據(jù)較多就不再一一羅列。

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

2.2算法設(shè)計

遺傳算法是求解最小steiner生成樹問題的一種近似解法，它由染色體編碼與解碼方法、個體適應(yīng)度評價、遺傳算子、運(yùn)行參數(shù)等4個主要要素構(gòu)成。本文采用遺傳算法求解最小steiner生成樹問題，由結(jié)論4可知所有點(diǎn)均位于已知點(diǎn)生成的凸包內(nèi)，所以首先求出凸包(ConvexHull，CH)，具體如下[4]。

在已知點(diǎn)集V={P1,P2,…,Pn}中找到縱、橫坐標(biāo)最小的點(diǎn)作為凸包的第1個頂點(diǎn)Pi1。以Pi1為起點(diǎn)做單位向量i=(1,0)，然后做出以Pi1為起點(diǎn)以V-{Pi1}中所有點(diǎn)為終點(diǎn)的(n-1)個向量Pi1Pj(j=2,3,…,n)，并把它們單位化得到ePi1Pj(j=2,3,…,n)。與單位向量i的點(diǎn)積中最小的必定是和i夾角最大，把與max{i·Pi1Pj},j=2,3,…,n相對應(yīng)的那個向量Pi1Pi2的終點(diǎn)Pi2作為凸包的第2個頂點(diǎn)。接著，以Pi2為起點(diǎn)重復(fù)前面的步驟，直至找到第k+1個凸包頂點(diǎn)和第1個頂點(diǎn)重合為止。這樣就可以得到根據(jù)已知點(diǎn)構(gòu)造出的凸包和凸包的k個頂點(diǎn)Pi1,Pi2,Pi3,…,Pik。

(1)編碼

因?yàn)橥拱械娜魏吸c(diǎn)都可以用凸包頂點(diǎn)的線性組合表示，即若有一點(diǎn)M(x0,y0)∈CH，那么

M=α1Pi1+α2Pi2+α3Pi3+…+αkPik

(1)

每個個體最初都是隨機(jī)生成的一個十進(jìn)制字符串，它代表著一組待求的點(diǎn)，其中十進(jìn)制數(shù)的個數(shù)ws=ds×k，由待求steiner點(diǎn)的個數(shù)ds和凸包頂點(diǎn)的個數(shù)k共同決定的，ds可以自己設(shè)定。

(2)解碼

首先，根據(jù)輸入的待求steiner點(diǎn)個數(shù)和兩個坐標(biāo)分量的編碼長度把個體的編碼分段，個體的二進(jìn)制編碼構(gòu)成如下：

其中*是十進(jìn)制數(shù)。

(2)

Mi=αi1Pi1+αi2Pi2+…+αikPik,i=1,2,…,ds

(3)

(3)初始群體的選取

設(shè)種群規(guī)模為M，那么根據(jù)要求的計算精度，隨機(jī)產(chǎn)生M個用十進(jìn)制碼表示的字符串，構(gòu)造出初始種群[6]。

(4)對種子的評價

對于某個個體所對應(yīng)的生成樹，要判斷其優(yōu)劣主要是看其目標(biāo)函數(shù)值。取以已知點(diǎn)和待求點(diǎn)作為頂點(diǎn)的圖的最小生成樹長度作為目標(biāo)函數(shù)值，該數(shù)值越小越好。

(5)選擇

本文把輪盤選擇與最優(yōu)保存策略兩種方法結(jié)合在一起，對個體進(jìn)行選擇操作。根據(jù)個體的目標(biāo)函數(shù)值設(shè)計輪盤。目標(biāo)函數(shù)值越小則在輪盤上占據(jù)的范圍就越小，那么該個體比較不容易被選中；反之，則更容易被選中。把這一步驟反復(fù)進(jìn)行多次之后，適應(yīng)度較高的個體將會有較大的可能被選中從而保留下來。

(6)交叉

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

(7)變異

采用單點(diǎn)變異操作，變異的基因位隨機(jī)生成，交叉產(chǎn)生的子代按照一定的變異概率pm發(fā)生變異。設(shè)要執(zhí)行變異操作的那個基因位上的數(shù)是q，如果在變異概率的范圍內(nèi)，則根據(jù)計算精度的要求把q換成即可10k-q；如果超出變異概率，則不執(zhí)行變異操作。

3實(shí)驗(yàn)分析與結(jié)論

上述解法在windows7系統(tǒng)中，通過mathematics7.0編程運(yùn)行。對于給出的上述16個站點(diǎn)，經(jīng)過多次試驗(yàn)發(fā)現(xiàn)，當(dāng)steiner點(diǎn)的個數(shù)ds=3個時效果最好，如圖1所示。

圖1最小steiner生成樹

利用本文的解法隨機(jī)求解10次，算法迭代平均12次左右就收斂到近似最優(yōu)解。本解法得到的最小steiner生成樹的近似最優(yōu)解是1 674.02，和最小生成樹的結(jié)果1 704.7相比較而言，總路徑長度縮短了1.8%，steiner點(diǎn)是(510.106,184.507),(247.08,303.723),(310.13,201.056)。

雖然本文使用凸包縮小了搜索范圍，能夠加快搜索速度，但是仍然無法達(dá)到全局最優(yōu)。嘗試通過多點(diǎn)變異或是多次實(shí)行單點(diǎn)變異操作是否能夠?qū)⒈疚闹械慕夥ǜ觾?yōu)化，則有待進(jìn)一步討論。

參考文獻(xiàn):

[1] 查理·達(dá)爾文．物種起源[M] .南京: 江蘇人民出版社，2011: 1-50.

[2] 雷英杰，張善文，李續(xù)武, 等．MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社，2014：1-10，45-61.

[3] (德)梅霍內(nèi), (德)桑德斯．算法與數(shù)據(jù)結(jié)構(gòu)[M]. 北京: 清華大學(xué)出版社, 2013: 178.

[4] 吳永輝，王建德．算法設(shè)計編程實(shí)驗(yàn)[M]. 北京: 機(jī)械工業(yè)出版社, 2013: 399.

[5] 王謙. 遺傳算法在期刊數(shù)字化任務(wù)分配中的應(yīng)用[J]. 安慶師范學(xué)院學(xué)報(自然科學(xué)版), 2013, 19(4): 66-68.

[6] 樓濤, 杜文才, 鐘杰卓. 基于混合蟻群遺傳算法的Hadoop集群作業(yè)調(diào)度[J]. 海南大學(xué)學(xué)報(自然科學(xué)版)，2015(4): 340-346.

Application of Genetic Algorithm in the Problem of Minimum Steiner Tree

CHEN Zhi-hao1，HOU Wei-gen2，YANG Tian-ming1

(1. Jiangsu Polytechnic College of Agriculture and Forestry, Jurong, Jiangsu 212400, China;2. Anhui University of Technology, Ma’anshan, Anhui 243032, China)

Abstract:After introducing the concept of genetic algorithm, minimum spanning tree and minimum Steiner spanning tree briefly, we describe the application of genetic algorithm in the problem of minimum Steiner spanning tree and give one improved method. And then, improved method can attain the better local approximate root through solving an emulated experimentation on a communication network.

Key words:genetic algorithm; minimum spanning tree; minimum Steiner spanning tree; communication network

* 收稿日期：2015-07-21

作者簡介：陳智豪，女，江蘇句容人，碩士，江蘇農(nóng)林職業(yè)技術(shù)學(xué)院講師，研究方向?yàn)閼?yīng)用數(shù)學(xué)。 E-mail: sweet215@sina.com

中圖分類號：O242.2

文獻(xiàn)標(biāo)識碼：A

文章編號：1007-4260(2016)02-0030-03

網(wǎng)絡(luò)出版時間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.009.html