計算機中遺傳算法中樹構(gòu)造的分析

中國醫(yī)科大學附屬盛京醫(yī)院醫(yī)務(wù)部 高 興

計算機中遺傳算法中樹構(gòu)造的分析

中國醫(yī)科大學附屬盛京醫(yī)院醫(yī)務(wù)部 高 興

提出了一種解決Steiner最小樹問題的自適應(yīng)遺傳算法，將Steiner最小樹問題轉(zhuǎn)化成一個組合優(yōu)化問題，并對部分初始種群的構(gòu)造給出了一種試探選擇方法。通過對通訊網(wǎng)絡(luò)Steiner最小樹問題的實例仿真分析，表明算法能有效地跳出局部極小值并快速地收斂于全局最優(yōu)值。將其推廣到考慮建站費用的極小樹問題上，取得了很好的近似解。

通訊網(wǎng)絡(luò) Steiner最小樹 最小生成樹 遺傳算法

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

兩個通訊站間通訊線路的費用與線路的長度成正比，通過引入若干個“虛設(shè)站”并構(gòu)造一個新的Steiner樹就可以降低由一組原始站點生成的傳統(tǒng)的極小生成樹的線路長度。用這種方法可以降低線路長度多達13。4%。假定對一包含9個通訊站點的局部網(wǎng)絡(luò)進行布線，目的是使其網(wǎng)絡(luò)連通且總線路最短。這9個站點的直角坐標分別為：

a（0，15），b（5，20），c（16，24），d（20，20），e（33，25），f（23，11），g（35，7），h（25，0），i（10，3）。限定兩通訊站間的線路長度必須為兩點間的直角折線距離，即d=︱x2-x1︱+︱y2-y1︱，且一切新增虛設(shè)點必須位于格子節(jié)點上（即坐標為整數(shù)）。通過構(gòu)造這個網(wǎng)絡(luò)的Steiner最小樹，使網(wǎng)絡(luò)布線達到全局最優(yōu)化。

二、問題的分析與解決步驟

上述問題允許通訊線在非站點處連接，因而不同于最小生成樹問題。最小生成樹不允許非站點處連接，而此處取消了限制，允許在站點以外的點（即“虛設(shè)站”或Steiner點）連接，可使線路變短，但卻增加了問題的復雜度。

本文將這個問題分3步解決：①確定Steiner點的個數(shù)；②確定Steiner點的位置；③建立使線路最短的生成樹。

三、模型建立與求解

1. 遺傳算法求解

前文已將Steiner最小樹問題轉(zhuǎn)化為一個組合優(yōu)化問題，即在已知所有可能的Steiner點中，確定出最優(yōu)的組合，使其與原始站點構(gòu)成Steiner最小樹。因搜索空間的不規(guī)則性，無法確定Steiner點的數(shù)目和位置，我們將使用遺傳算法來解決這個問題。詳細步驟如下：

（1）編碼

采用自然數(shù)編碼。對一有n個通訊站的通訊網(wǎng)絡(luò)，將所有可能的Steiner點進行編號。通過上述分析我們已經(jīng)解出所有可能的Steiner點（共m個）的位置，讓每一個Steiner點都唯一對應(yīng)一個1～m之間的自然數(shù)；用矩陣pop來表示所有的染色體，popsize表示矩陣pop的行數(shù)，n表示矩陣pop的列數(shù)，矩陣的每一行代表一個染色體。而每一染色體所示信息如下：設(shè)p=[p（1），p（2），…，p（n）]為矩陣pop的任一行。p（i）（i=1，2，…，n-2）：x（i）為0～m之間的自然數(shù)，如果p（i）=0則表示不加Steiner點，如果p（i）≠0則表示加入Steiner點。p n-1：表示由[p（1），p（2），…，p（n-2）]所確定的一組Steiner點與原來的n個通訊站點所確定的最小生成樹線路長度。p n：表示適應(yīng)度函數(shù)值。

（2）初始種群的選取

本文采用一種簡單有效的快速算法來產(chǎn)生部分的初始解，這些值能夠很好的逼近最優(yōu)解。算法的中心思想是：每次迭代都隨機加入一個點，并使得到的最小生成樹費用有所減少，直到已加入n-2個點或加入任何一個剩余的可能的點都不可能有所減少為止，謂之試探選擇方法。其步驟描述如下：

①求給定的n個通訊站點的最小生成樹T，記錄其線路長度為C；

②對可能的Steiner點集V p，分別計算每個候選點作為Steiner點加入之后所減少的費用，記為vf；

③隨機取一個vf>0的候選點，把它加入到樹T中，更新此樹及線路長度；同時從點集V p中去掉該點；

④重復（ii）和（iii）直到已有n-2個點或所有的vf都小于等于零（即任何剩余的候選點加入都不能減少線路長度）。

將所得解作為部分初始種群，同時隨機產(chǎn)生另外一部分初始種群，這樣既保證了初始種群的質(zhì)量，又保證了其多樣性。

（3）選擇操作

本文結(jié)合輪盤選賭和保留最優(yōu)種群的方法，采用賭輪法進行選擇，將最優(yōu)保存策略嵌入其中，以加強對下一代中最好個體的保護并克服樣本的隨機誤差。同時結(jié)合最優(yōu)保存策略選擇，取選擇率pr，將種群中的比較好的一些個體加入到下一代。

（4）變異操作

本文采用單點變異操作。定義參數(shù)pm作為遺傳系統(tǒng)中的變異概率，這個概率表明，總體中有期望值為（pm×popsize）個染色體用來進行變異操作。因此，如果pm過小，就不易產(chǎn)生新的個體結(jié)構(gòu)；如果pm取值過大，那么遺傳算法就變成了純粹的隨機搜索算法。

2. 結(jié)果

對于原始給定的9個通訊站，經(jīng)過多次試驗，遺傳算法迭代不到第10次就可以收斂到最優(yōu)解，并且有良好的穩(wěn)定性，當然不同的運算，就有不同的隨機數(shù)字產(chǎn)生，這里給出5種不同的總長都為94的最優(yōu)解，這5組解分別為：（16，20）、（23，3）、（33，11）；（16，20）、（23，3）、（23，7）、（23，20）；（16，20）、（23，20）、（25，3）、（25，7）；（5，15）、（10，15）、（20，15）、（20，24）、（25，7）；（16，20）、（25，3）、（25，7）、（25，11）、（25，20）。所要添加的虛擬點為4個，分別為（16，20）、（23，3）、（23，7）及（23，20）。

算法評價遺傳算法從多點開始并行操作，在解空間進行高效啟發(fā)式搜索，克服了從單點出發(fā)的弊端及搜索的盲目性，從而使尋優(yōu)速度更快，避免了過早陷入局部最優(yōu)解。而同類方法中，單純形法受初值和計算步長的影響較大，易收斂于局部最優(yōu)解；傳統(tǒng)的隨機尋優(yōu)技術(shù)效率較低。

應(yīng)用模擬退火法得到的最優(yōu)解一樣，將遺傳算法應(yīng)用于本文所述的通訊網(wǎng)絡(luò)優(yōu)化布線問題可以較快的求得最優(yōu)解，迭代不到10次就達到最優(yōu)解，計算機運算時間僅需幾秒；而且算法穩(wěn)定性高，連續(xù)運行此程序50次，皆收斂到相同的最優(yōu)解，收斂率達到100%。

本文采用的是自適應(yīng)遺傳算法，在數(shù)據(jù)規(guī)模較小的情況下，尚體現(xiàn)不出其優(yōu)越性。現(xiàn)隨機產(chǎn)生20個初始站點=[96 6；24 36；61 82；49 1；90 14；77 21；46 20；2 61；83 28；45 20；62 2；80 75；93 45；74 94；18 47；4142；94 85；92 53；42 21；90 68]，運行遺傳算法主程序，適應(yīng)函數(shù)值上升得較快，這說明遺傳算法收斂得較快；當平均適應(yīng)度函數(shù)值接近最大適應(yīng)度函數(shù)值時，適應(yīng)函數(shù)值也呈上升趨勢，說明當種群單一，遺傳算法陷入局部最優(yōu)解時，遺傳算法就會加快新個體的產(chǎn)生，避免算法的早熟收斂。

[1] 蒲俊，吉家鋒，伊良忠.MA TL AB[6]0數(shù)學手冊[M].上海：浦東電子出版社，2002. 6

[2] 許桂水，曾山.基于非線性規(guī)劃問題GA的Matlab程序[J].武漢工業(yè)學院學報，2002，2(3)：35-37

book=92,ebook=215