用遺傳算法求解最短路徑問題

《用遺傳算法求解最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第19卷第3期合肥工業(yè)大學學報泊然科學版)Vbl.19附31996.9J()URNAIJOF卜IErEIUN’l、下RSllY()F刃嘆俐叫()1滅)子YSePt.1996用遺傳算法求解最短路徑問題曹魯寅羅斌欽明浩(安徽大學)(合肥工業(yè)大學),摘要文章應用遺傳算法求解圖論中的最短路徑問題并提出了該算法在解決這一問題中的一些處理方法·使用該算法可以很快地求出一批最短路徑集。文中最后給出了算法運行結果及總結。;;關鍵詞最短路徑遺傳算法鄰接矩陣0.5中圖分類號1571最短路徑問題和遺傳算法所謂最短路徑問題就是在給定的起始點,,S到終止點的通路集合中尋求長度最小的,。通路這樣的通路稱為S

2、點到t點的最短路徑,,在尋找最短路徑問題上有時人們不僅要知道兩個指定的頂點間的最短路徑還需要知道某個頂點到其它任意頂點間的最短路徑。用遺傳算法解這類問題,沒有太多的約束條,。件和有關解的限制因而可以很快地求出任意兩點間的最短路徑以及一批次短路徑,.GerithjmGA)是新近遺傳算法(netic燦go簡寫發(fā)展起來的一種模擬生命進化機制的,。.搜索和優(yōu)化方法是把自然遺傳學和計算機科學結合起來的優(yōu)化方程1975年land在Ho其專著中指出了GA的概念和方法,因其有很強的解決問題的能力和廣泛的適應性,因而近年來滲透到研究與工程的各個領域.取得了良好的效果。下面:介紹遺傳算法的幾個基本概

3、念.。(1)染色(o:體Chrmosome)在使用遺傳算法時需要把問題的解編成一個適合的碼子這種具有固定結構的符號串即是染色體.符號串的每一位代表一個基因。符號串的總位數(shù)稱為染色體的長度。一個染色體就代表問題的一個解,每個染色體也被稱為一個個體。a:,(2)群體(P叩ultion)每代所產(chǎn)生的染色體總數(shù)稱為群體一個群體包含了該問題在這一代的一些解的集合。:,(3)適應度(Fitnes)對群體中每個染色體進行編碼后每個個體對應一個具體問題,。,的解而每個解對應于一個函數(shù)值該函數(shù)值即適應函數(shù)就是衡量染色體對環(huán)境適應度,。的指標也是反映實際問題的目標函數(shù):一一1收稿日期一9960505

4、:第3期曹魯寅等用遺傳算法求解最短路徑問題113,:在前代群體的基礎上產(chǎn)生新一代群體的工作稱為遺傳操作基本的遺傳操作有·:(1)選擇(段lect)按一定的概率從上代群體中選擇M對個體作為雙親直接拷貝到下,。一代染色體不發(fā)生變化。r:,,、(2)交叉(Cr二ve)對于選中進行繁殖的兩個染色體XY以XY為雙親作交叉操作·從而產(chǎn)生兩個后代X‘、丫。o:,(3)變異(Mutatin)對于選中的群體中的個體‘染色體)隨機選取某一位進行取反運算.即將該染色體碼反轉。用遺傳算法求解的過程是根據(jù)待解問題的參數(shù)集進行編碼,隨機產(chǎn)生一個種群·計算適應函數(shù)和選擇率,進行選擇、交叉、變異操作·如果滿足迭

5、代收斂條件,此種群為最好個體·否則,對產(chǎn)生的新一代群體重新進行選擇,交叉、變異、操作,循環(huán)往復直到滿足條件。2求最短路徑問題的遺傳算法的表示與實現(xiàn)用遺傳算法求解一個優(yōu)化問題.就是對該優(yōu)化問題存在許多解二.計算每個二對應的.,。。適應函數(shù)關優(yōu)化的過程就是要尋找這樣的端使得與之對應的f(二)最大或最小2.1最短路徑問題的圖論描述,....:VVv一v,求最短路徑問題用圖論術語描述如下在圖僅由中表示頂點集合(跳,?,。)對.馬).二.馬).G·vj).G中的某一條邊(v,相應地有一個數(shù)d(如果中不存在邊氣,,,,.則令d(vivj)一的如把d(vivj)認為是邊(認馬)的長度(也可認為

6、是邊(:、:必的費用或。),則路的長度權定義為組成路的各條邊的長度的總和,,。頂點vivj之間是否有邊相連由鄰接矩陣來決定:,尸vv鄰接矩陣A對一個具有V個頂點條邊的圖G的鄰接矩陣A~〔aij〕是一個又階,,,,。方陣其中aij一1表示勸和vj鄰接a,j一。表示勸和vj不相鄰接(或i一j)2.2染色體編碼,,對于一個給定的圖模型將圖中各頂點按頂點號自然排序然后按此順序將每個待選,,,頂點作為染色體的一個基因當基因值為1時表示相應的頂點被選人該條路徑中否則反之。此染色體中的基因排列順序即為各頂點在此條通路中出現(xiàn)的先后順序,染色體的長度應等于該圖中的頂點個數(shù)。2.3適應函數(shù)f(i)二

7、,,,,,對具有個頂點的圖已知各頂點(v.vj)的邊長度d(勸vj)把vi到vjn間的一條通路勸;,:,,:針?vin的路徑長度定義為適應函數(shù),f(*)一貳、vir十1)藝,,對該優(yōu)化問題就是要尋找解壽使f(壽)值最小2.4選擇操作,,,選擇作為交叉的雙親是根據(jù)前代染色體的適應函數(shù)值所確定的質(zhì)量好的個體即從起點到終點路徑長度短的個體被選中的概率較大。2.5交叉與變異操作114合肥工業(yè)大學學報(自然科學版)1996年第19卷(3),,將被選中的兩個染色體進行交叉操作的過程是先產(chǎn)生一