計算機中遺傳算法中樹構造的分析

中國醫科大學附屬盛京醫院醫務部 高 興

計算機中遺傳算法中樹構造的分析

中國醫科大學附屬盛京醫院醫務部 高 興

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

通訊網絡 Steiner最小樹 最小生成樹 遺傳算法

一、網絡有線通訊問題

兩個通訊站間通訊線路的費用與線路的長度成正比，通過引入若干個“虛設站”并構造一個新的Steiner樹就可以降低由一組原始站點生成的傳統的極小生成樹的線路長度。用這種方法可以降低線路長度多達13。4%。假定對一包含9個通訊站點的局部網絡進行布線，目的是使其網絡連通且總線路最短。這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︱，且一切新增虛設點必須位于格子節點上（即坐標為整數）。通過構造這個網絡的Steiner最小樹，使網絡布線達到全局最優化。

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

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

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

三、模型建立與求解

1. 遺傳算法求解

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

（1）編碼

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

（2）初始種群的選取

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

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

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

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

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

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

（3）選擇操作

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

（4）變異操作

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

2. 結果

對于原始給定的9個通訊站，經過多次試驗，遺傳算法迭代不到第10次就可以收斂到最優解，并且有良好的穩定性，當然不同的運算，就有不同的隨機數字產生，這里給出5種不同的總長都為94的最優解，這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）。

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

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

本文采用的是自適應遺傳算法，在數據規模較小的情況下，尚體現不出其優越性。現隨機產生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]，運行遺傳算法主程序，適應函數值上升得較快，這說明遺傳算法收斂得較快；當平均適應度函數值接近最大適應度函數值時，適應函數值也呈上升趨勢，說明當種群單一，遺傳算法陷入局部最優解時，遺傳算法就會加快新個體的產生，避免算法的早熟收斂。

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

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

book=92,ebook=215