【導(dǎo)讀】學(xué)院信息工程學(xué)院。專業(yè)計(jì)算機(jī)科學(xué)技術(shù)與應(yīng)用。第一章基本遺傳算法2. 第二章遺傳算法的實(shí)現(xiàn)技術(shù)6. 第三章遺傳算法在TSP上的應(yīng)用15. 傳算法是解決NP問題的一種較理想的方法。文章首先介紹了基本遺傳算法的基。本原理、特點(diǎn)及其基本實(shí)現(xiàn)技術(shù)；接著針對(duì)TSP問題，論述了遺傳算法在編碼表。示和遺傳算子等方面的應(yīng)用情。況，分別指出幾種常用的編碼方法的優(yōu)點(diǎn)和缺點(diǎn)，并且結(jié)合TSP的運(yùn)行實(shí)例詳細(xì)。分析了基本遺傳算法的4個(gè)運(yùn)行參數(shù)群體大小、遺傳算法的終止進(jìn)化代數(shù)、交叉。概率、變異概率，對(duì)遺傳算法的求解結(jié)果和求解效率的影響，經(jīng)過多次的

　　

【正文】 (Pathlength2)+2。 while(abs(p2p1)2) { p2=rand()%Pathlength。 } if(p1p2) { temp=p1。 p1=p2。 p2=temp。 } temp=population[x].Path[p2]。 for(i=p2。ip1。i) population[x].Path[i]=population[x].Path[i1]。 population[x].Path[p1+1]=temp。 } 此外 ， 對(duì)于變異操作還有一些變體形式 ， 如 Sushil Jouis[19]提出的貪心對(duì)換變異 (greedyswap mutation)， 其基本思想是從一個(gè)染色體中隨機(jī)的選擇兩個(gè)城市 (即兩個(gè)碼值 )， 然后交換它們 ， 得到新的染色體 ， 以旅程長(zhǎng)度為依據(jù)比較交換后的染色體與原來的染色體的大小 ， 保留旅程長(zhǎng)度值小的染色體 。 謝勝利 [7]等提出倒位變異算子 ， 該算子是指在個(gè)體編碼串中隨機(jī)選擇兩個(gè)城市 ， 是第一個(gè)城市的右邊城市與第二個(gè)城市之間的編碼倒序排列 ， 從而產(chǎn)生一個(gè)新個(gè)體 。 例如，若有父?jìng)€(gè)體 P( 1 4 5 2 3 6 )， 假設(shè)隨機(jī) 選擇的城市是 4， 3， 那么產(chǎn)生的新個(gè)體為Offspring(1 4 3 2 5 6)。 Hiroaki SENGOKU[14]等采用 Grefenstette J J［ 15]方法的思想 ，提出了 Greedy Subtour Crossover(GSC)變異算子 。 這種方法與貪心對(duì)換變異有相同的思想 ， 但是更易擴(kuò)張更有效率 。 Konstantin Boukreev[12]實(shí)驗(yàn)發(fā)現(xiàn) :當(dāng)城市大小在 200之內(nèi)時(shí) ， 該變異算子可以大大改善程序的運(yùn)行速度 ， 隨著城市數(shù)目的增加 ， 尤其是當(dāng)城市數(shù)目達(dá)到 1000以上時(shí) ， 程序運(yùn)行速度非常慢 。 TSP的混和遺傳算法 隨著遺傳算法的發(fā)展 ,遺傳算法廣泛的與其它算法相結(jié)合 ， 產(chǎn)生許多混合遺傳算法 (Hybrid geic algorithm)。 王俊海 [8]將 Memetic算法與遺傳算法結(jié)合起來 ， 給出了一種基于 Memetic算法的高效遺傳算法 。 將這種算法應(yīng)用于 TSP問題取得了滿意的結(jié)果 ， 把局部?jī)?yōu)化的高效性與遺傳算法的魯棒性很好的結(jié)合起了 。Ranieri Baraglia[22]等提出一種解決 TSP問題的并行混合啟發(fā)式 (Parallel Hybrid Heuristic)算法 。 Jog等 [18]提出啟 發(fā)式算法 (Heuristic Algorithm)也取得了很好的效果。 第四章 實(shí)例分析 測(cè)試數(shù)據(jù) 10 個(gè)點(diǎn)的 TSP 問題的測(cè)試數(shù)據(jù)如下： 0 ,23 ,93 ,18 ,40 ,34 ,13 ,75 ,50 ,35 , 23 ,0 ,75 ,4,72 ,74 ,36 ,57 ,36 ,22 , 93 ,75 ,0 ,64 ,21 ,73 ,51 ,25 ,74 ,89 , 18 ,4 ,64 ,0 ,55 ,52 ,8 ,10 ,67 ,1, 40 ,72 ,21 ,55 ,0 ,43 ,64 ,6,99 ,74 , 34 ,74 ,73 ,52 ,43 ,0,43 ,66 ,52 ,39 , 13 ,36 ,51 ,8 ,64 ,43 ,0 ,16 ,57 ,94 , 75 ,57 ,25 ,10 ,6 ,66 ,16 ,0 ,23 ,11 , 50 ,36 ,74 ,67 ,99 ,52 ,57 ,23 ,0 ,42 , 35 ,22 ,89 ,1 ,74 ,39 ,94 ,11 ,42 ,0 , 測(cè)試結(jié)果 （ 1）利用回溯算法對(duì)上述數(shù)據(jù)測(cè)試，求出 510 個(gè)點(diǎn)的 TSP問題的最短路徑的路徑長(zhǎng)度及路徑如下： 表 41 用回溯算法求出的路徑長(zhǎng)度及路徑 點(diǎn)數(shù) 路徑長(zhǎng)度 路徑 5 152 1， 2， 4， 3， 5 6 189 1， 2， 4， 3， 5， 6 7 184 1， 2， 4， 7， 3， 5， 6 8 174 1， 2， 4， 7， 8， 3， 5， 6 10 226 1， 6， 5， 3， 8， 9， 2， 10， 4， 7 12 251 1， 2， 11， 6， 5， 3， 8， 9， 10， 4， 12， 7 13 230 1， 2， 11， 6， 13， 5， 3， 8， 9， 10， 4， 12， 7 15 230 1， 7， 12， 9， 8， 3， 5， 15， 14， 10， 4， 2， 11， 6， 13 17 222 1， 2， 16， 14， 15， 5， 3， 8， 9， 17， 11， 6， 13， 10， 4， 12， 7 19 203 17,12,4， 10， 19， 3， 5， 15， 14， 16， 2， 11， 17， 9， 8， 18， 6， 13 20 212 1,2,16,20,11,17， 9， 8， 14， 18， 6， 13， 15， 5， 3， 19， 10， 4， 12， 7 采用遺傳算法求解 TSP 的結(jié)果如下： 表 42遺傳算法求解 TSP問題 10個(gè)點(diǎn)的測(cè)試結(jié)果一 Pc= Pm= 運(yùn)行最大代數(shù) 50 代 100 代 所用方法 代數(shù) 權(quán)值 路徑 代數(shù) 權(quán)值 111 1 184 1653742 30 184 6 212 1536742 112 1 207 1246537 69 184 2 184 1653742 113 7 198 1653742 61 251 10 212 1536442 3 198 114 8 198 1653247 46 207 9 224 1426537 27 184 121 2 184 1653742 67 184 7 217 1423567 122 6 207 1426537 74 184 8 224 1735624 123 2 224 1426537 14 184 5 198 1653247 124 6 211 1243567 90 184 1 212 1536742 211 1 211 1765342 1 255 1 211 1765342 2 217 212 1 211 1243567 24 198 1 207 1246537 213 3 231 1235674 1 184 2 217 1765342 52 207 214 1 225 1635247 19 198 1 198 1742356 221 2 258 1253674 21 207 1 184 1653742 222 2 235 1427635 2 184 1 184 1653742 223 1 242 1672435 1 184 2 184 1653742 224 1 227 1635742 1 184 1 215 1724356 1 207 表 43 遺傳算法求解 TSP問題 10個(gè)點(diǎn)的測(cè)試結(jié)果二 條件 Pc= Pm= Pc= Pm= 種群 100 個(gè)種群 50 個(gè)種群 100 個(gè)種群 運(yùn)行最大代數(shù) 100 代 200 代 200 代 所用方法 代數(shù) 權(quán)值 代數(shù) 權(quán)值 代數(shù) 權(quán)值 代數(shù) 權(quán)值 111 67 252 196 252 14 251 30 233 41 237 112 43 233 18 232 127 257 4 237 71 242 113 63 229 81 229 52 259 76 251 40 245 114 79 253 118 265 73 253 36 237 1 246 121 79 338 142 235 199 242 25 245 1 256 122 29 256 32 256 124 241 6 245 1 237 123 64 248 179 245 101 256 75 247 5 248 124 66 251 113 226 125 304 98 233 48 258 211 2 275 136 259 1 277 2 285 1 245 212 2 233 25 288 1 262 1 259 1 282 213 19 249 1 277 15 254 1 283 31 266 214 1 277 39 261 126 308 1 280 1 272 221 81 266 1 268 143 237 1 276 37 274 222 1 248 5 229 134 266 1 262 3 256 223 1 299 1 258 3 268 1 314 3 241 224 1 287 149 294 2 3 264 1 232 注：所用方法按選擇，交叉，遺傳順序排列。 選擇 1： Optimization selection（ one best selected and others mate each other）；選擇 2： Optimization selection (one best selected mate with others) ；交叉 1 ： one_point_crossover ；交叉 2 ：partially_mapped_crossover；遺傳 1： simple_mutation；遺傳 2： inversion_mutation；遺傳 3:insert_mutation； 4： change_mutation。 遺傳算法求解TSP問題20點(diǎn)測(cè)試數(shù)據(jù)曲線圖200220240260280300320340360380400420440460480500520540560580600620640111 112 113 114 121 122 123 124 211 212 213 214 221 222 223 224選擇方法最優(yōu)值100250 100500 200250 200500 圖 41 遺傳算求解 TSP 問題 20 點(diǎn)的測(cè)試結(jié)果 結(jié)果分析 從上表可以看出，用方法 112， 113， 124， 222的效果較好。針對(duì)上述 10點(diǎn)的測(cè)試數(shù)據(jù)，在 Pc=,PM=,100個(gè)種群，運(yùn)行最大代數(shù)為 200的條件下，利用 ，用方法 112進(jìn)行測(cè)試，出現(xiàn)最好解的代數(shù)、權(quán)值如下 表 43 112方法的測(cè)試結(jié)果 0501001502002503001 2 3 4 5 6 7 8 9 10產(chǎn)生最優(yōu)解的代數(shù)最優(yōu)值代數(shù) 權(quán)值1101001000代數(shù)權(quán)值代數(shù) 23 66 18 19 49 21 51 83 24 5權(quán)值 24 24 23 22 22 22 24 25 23 231 2 3 4 5 6 7 8 910 圖 42 方法 112的測(cè)試結(jié)果 圖 43 方法 112的測(cè)試結(jié)果 產(chǎn)生最優(yōu)解的平均代數(shù)：（ 23+66+18+191+49+21=51+83+24+5） /10= 路徑的平均權(quán)值：（ 246+246+232+229+228+228+242+252+237+237） /10= 相對(duì)誤差：（ ） /226*100%=% 在 Pc=,PM=， 100個(gè)種群，運(yùn)行最大代數(shù)為 200的條件下，利用 的測(cè)試數(shù)據(jù)，用方法 113進(jìn)行測(cè)試，出現(xiàn)最好解的代數(shù)、權(quán)值如下： 0501001502002503001 2 3 4 5 6 7 8 9 10代數(shù)權(quán)值 圖 44 方法 113的測(cè)試結(jié)果 圖 45 方法 113的測(cè)試結(jié)果 產(chǎn)生最優(yōu)解的平均代數(shù)：（ 127+57+183+117+70+52+121+132+2+59） /10= 路徑的平均權(quán)值：（ 246+233+232+244+237+233+258+257+244+257） /10= 相對(duì)誤差：（ ） /226*100%=8% 在 Pc=， PM=， 100個(gè)種群，運(yùn)行最大代數(shù)為 200的條件下，利用 的測(cè)試數(shù)據(jù)，用方法 124進(jìn)行測(cè)試，出現(xiàn)最好 解的代數(shù)、權(quán)值如下： 050100150200215220225230235240245250255260代數(shù) 權(quán)值代數(shù) 12 57 18 11 70 52 12 13 2 59權(quán)值 24 23 23 24 23 23 25 25