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

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

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

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

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

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

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

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

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