運(yùn)用遺傳算法求解TSP問題的探討

1、第 24卷 第 5期 天 中 學(xué) 刊 V ol. 24 No. 5 2009年 10月 Journal of Tianzhong Oct. 2009收稿日期:2009-02-25作者簡介:劉會超(1982 ,男,河南駐馬店人,黃淮學(xué)院計算機(jī)科學(xué)系助教,武漢大學(xué)軟件工程國家重點(diǎn)實(shí)驗室碩士研究生.運(yùn)用遺傳算法求解 TSP 問題的探討劉會超 1, 2,劉 珂 2(1. 武漢大學(xué),湖北 武漢 430072; 2. 黃淮學(xué)院,河南 駐馬店 463000摘 要:通過對遺傳編碼方案的改進(jìn),克服了 TSP 問題中的數(shù)據(jù)冗余缺陷,使得搜索性能得到提高.將該遺傳 算法應(yīng)用于實(shí)際 TSP 問題,計算結(jié)果證明了該遺傳

2、算法的有效性. 關(guān)鍵詞:TSP ;遺傳算法;雜交;變異 1 TSP 問題及其應(yīng)用TSP 問題是組合優(yōu)化中典型的 NP-C 問題. TSP問題可以描述為:某商人要到給定 n 個城市推銷貨物, 從某城市出發(fā)遍歷其余各城市一次且僅一次,最后再 回到起點(diǎn),求其最短的行程,即尋找一條巡回路徑 12( n P p p p =L , , , , 使得1111( min( ( n i i n i f P d p p d p p +=+, , , (1其中 p i 為城市號, d (p i , p j 表示城市 i 與城市 j 之間的 連接代價.對于對稱式 TSP ,有 d (p i , p j = d (p

3、j , p i ; 對于非對稱式 TSP , d (p i , p j d (p j , p i . 本文僅討論對 稱式 TSP .TSP 問題涉及網(wǎng)絡(luò)通訊、車輛調(diào)度、管道鋪設(shè)、電路布線等優(yōu)化問題,因此快速、有效地解決 TSP 問 題有著極高的實(shí)際應(yīng)用價值.迄今為止,人們?yōu)榍蠼?TSP 問題提出了大量的搜索算法,如窮舉搜索法、貪婪法、插入算法、 r-opt 算法、神經(jīng)網(wǎng)絡(luò)算法、模擬退 火算法、動態(tài)規(guī)劃法、分支定界法、遺傳算法及蟻群 算法等 1.2 運(yùn)用遺傳算法求解 TSP 問題遺傳算法(Genetic Algorithm,簡稱 GA 的基本 思想是基于 Darwin 進(jìn)化論的 Mendel 的

4、遺傳學(xué)說,它 將問題的解集看作一個種群, 通過不斷的選擇、 交叉、 變異等遺傳操作,使解的質(zhì)量越來越好.遺傳算法最遺傳編碼方法有多種, 本文采用路徑表示法, 即:n 個城市的個體表示為 12( n p p p L , , , , 其中 p 1p n 互不相等;路徑 (5 9 1 4 7 2 3 8 6 10 可以直 接表示為 (59147238610 .實(shí)際上,由于路徑實(shí)際表達(dá)的是一個首尾相連的 回路,所以存在冗余路徑.例如,路徑 (5 9 1 4 7 2 3 8 6 10 可以寫成 (10 5 9 1 4 7 2 3 8 6 ,也可以寫成 (8 6 10 5 9 1 4 7 2 3 等. 也

5、就是說, n 個城市間的任意一條路徑就對應(yīng)有另外 n 1條冗余路徑.在本文中,消除冗余路徑的做法是:把所有個體 編碼的首位 p 1強(qiáng)制設(shè)為1號城市,這樣,參與演化操 作的所有個體所表達(dá)的路徑都是以城市1為首位的, 其他 n 1條等價路徑就不會出現(xiàn).去除冗余, 有助于 縮小搜索范圍,縮短搜索時間,提高搜索效率,最終 獲得更優(yōu)的解. 2.2 選擇機(jī)制求解 TSP 問題, 常用的選擇機(jī)制有輪盤賭選擇機(jī) 制、最佳個體選擇機(jī)制、期望值模型機(jī)制、聯(lián)賽選擇 機(jī)制等 3,本文中采用輪盤賭選擇機(jī)制.輪盤賭選擇 機(jī)制先定義種群中個體適應(yīng)度函數(shù)中圖分類號:TP18文獻(xiàn)標(biāo)識碼:B文章編號:1006-5261(2009

6、 05-0036-02劉會超,劉 珂:運(yùn)用遺傳算法求解 TSP 問題的探討·37·( i i g f P =, (2再計算個體的相對適應(yīng)值1( mi i ii i h P g f =, (3最后,根據(jù) ( i i h p 把一個圓盤分成 n 份,每份扇形的中心角為 2i g . 在 (2式和 (3式中, P i 表示某條合法的 路徑, ( i f P 表示路徑的長度, 12i m =L , , .在進(jìn)行 選擇時,可以假想轉(zhuǎn)動一下圓盤,若某參照點(diǎn)落入第i 個扇形內(nèi), 則選擇個體 i . 這樣, 小扇區(qū)的面積越大, 被選中的概率也越大,即個體適應(yīng)值越大它被選擇到 的機(jī)會也越多,

7、其基因結(jié)構(gòu)被遺傳到下一代的可能性 也越大.運(yùn)用此選擇方式隨機(jī)生成 m 個體(個體數(shù)一 般為 20200 ,最終形成演化種群. 2.3 雜交算子的設(shè)計雜交算子是模擬生物進(jìn)化中染色體的交換組合來 產(chǎn)生新的優(yōu)良品種,進(jìn)而搜索到空間中新的點(diǎn) 4.雜 交一般是以概率 0.600.98c q 進(jìn)行的.關(guān)于路徑表 示的雜交算子主要有部分匹配雜交(Partially Matched Crossover ,簡稱 PMX 、順序雜交(Order Crossover,簡稱 OX 、 循環(huán)雜交 (Cycle Crossover, 簡稱 CX 等, 本文采用的是 PMX .在 PMX 操作中,首先隨機(jī)地在父體中選取兩個

8、 雜交點(diǎn),定義這兩點(diǎn)之間的區(qū)域為匹配區(qū)域,一并交 換相應(yīng)的匹配區(qū)域;然后根據(jù)匹配區(qū)域內(nèi)的城市確定 部分映射關(guān)系;接著在父體上先填入無沖突的城市, 以保證在路徑中每個城市被且僅被訪問一次;再對有 沖突的城市分別執(zhí)行這些部分映射,直到填入無沖突 時,則獲得雜交后的兩后代.例如, 對下面的兩父體, 隨機(jī)選擇兩個雜交點(diǎn) (“ |” 表示雜交點(diǎn)1(182 | 4357 | 6109 p =, 2(174 | 6893 | 2510 p =,交換兩個雜交點(diǎn)之間的匹配區(qū)域,得到1(1* | 6893 |*q =, 2(1* | 4357 |*q =,其中 “ *” 為待定城市號. 由匹配區(qū)域確定的部分映射

9、為:4 6, 3 8, 5 9, 7 3.然后,從各自的父體 中填入無沖突的城市,得到1(1*2 | 6893 | *10*q =, 2(1* | 4357 | 2*10 q =.個體 1q 中的第一個 *處原為 8,由映射關(guān)系 3 8映射 到 3仍沖突,再由 7 3映射到 7無沖突, 則把 7填入. 類似地進(jìn)行操作,最終得到的兩個子個體為1(172 | 6893 | 4105 q =,2(186 | 4357 | 2910 q =. 2.4 變異算子的設(shè)計從遺傳算法的觀點(diǎn)來看,解的進(jìn)化主要靠選擇機(jī)制和雜交算子來完成,變異只是為選擇、雜交過程中可能丟失的某些遺傳基因進(jìn)行修復(fù)和補(bǔ)充 5.變異一

10、般是以概率 0.050.20m q 進(jìn)行的.3 實(shí)驗與結(jié)論, , 在相同的演化代數(shù)下,傳 統(tǒng)方法所求得的較優(yōu)值 ( 373.660km f P =,較優(yōu)路徑 為 32109871465P =, , , 而用本文去除冗余的 方法所求得的較優(yōu)值 ( 355.461km f P =,較優(yōu)路徑為表 1 各城市之間的距離 km3484.118471049.524實(shí)驗結(jié)果表明,采用該演化算法能夠降低種群生 成時的冗余度, 保持種群的多樣性, 提高求解的效率, 而且還能有效地避免“早熟”現(xiàn)象,因而此算法是有 效算法.參考文獻(xiàn):1 王宇平,李英華.求解 TSP 的量子遺傳算法 J.計算機(jī)學(xué)報, 2007, (5:748755.2 黃雪梅,李濤,徐春林,等.一種基于免疫遺傳的 TSP 求解方法 J.四川大學(xué)學(xué)報 (工程科學(xué)版 , 20