【正文】 遺傳算法求解TSP問題20點(diǎn)測試數(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)的測試結(jié)果 結(jié)果分析 從上表可以看出，用方法 112， 113， 124， 222的效果較好。 第四章 實(shí)例分析 測試數(shù)據(jù) 10 個(gè)點(diǎn)的 TSP 問題的測試數(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 , 測試結(jié)果 （ 1）利用回溯算法對(duì)上述數(shù)據(jù)測試，求出 510 個(gè)點(diǎn)的 TSP問題的最短路徑的路徑長度及路徑如下： 表 41 用回溯算法求出的路徑長度及路徑 采用遺傳算法求解 TSP 的結(jié)果如下： 點(diǎn)數(shù) 路徑長度 路徑 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 表 42 遺傳算法求解 TSP問題 10 個(gè)點(diǎn)的測試結(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)的測試結(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 注：所用方法按選擇，交叉，遺傳順序排列。Ranieri Baraglia[22]等提出一種解決 TSP問題的并行混合啟發(fā)式 (Parallel Hybrid Heuristic)算法 。 王俊海 [8]將 Memetic算法與遺傳算法結(jié)合起來 ， 給出了一種基于 Memetic算法的高效遺傳算法 。 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)行速度非常慢 。 Hiroaki SENGOKU[14]等采用 Grefenstette J J［ 15]方法的思想 ，提出了 Greedy Subtour Crossover(GSC)變異算子 。 謝勝利 [7]等提出倒位變異算子 ， 該算子是指在個(gè)體編碼串中隨機(jī)選擇兩個(gè)城市 ， 是第一個(gè)城市的右邊城市與第二個(gè)城市之間的編碼倒序排列 ， 從而產(chǎn)生一個(gè)新個(gè)體 。 population[x].Path[p1+1]=temp。ip1。 } temp=population[x].Path[p2]。 p1=p2。 while(abs(p2p1)2) { p2=rand()%Pathlength。 p1=rand()%Pathlength。 int insert[MaxPathlength]。 insert_mutation() { int i。 population[x].Path[p2]=temp。 } temp=population[x].Path[p1]。 p1=p2。 while(abs(p2p1)1) { p2=rand()%Pathlength。 p1=rand()%Pathlength。 int insert[MaxPathlength]。 change_mutation() { int i。i) { population[x].Path[i]=insert[p2i]。 } for(i=p2。i=p2。 p2=temp。 } if(p1p2) { temp=p1。 while(abs(p2p1)2) { srand( (unsigned)time( NULL ) )。 p1=rand()%Pathlength。 int insert[MaxPathlength]。 inversion_mutation() { int i。i++) code_path(i)。 for(i=0。 while(j==Pathlength1) j=rand()%(Pathlength1)。 j=rand()%(Pathlength)。 simple_mutation() { int i,j,p。 從遺傳算法的觀點(diǎn)來看 ， 解的進(jìn)化主要靠選擇機(jī)制和交叉策略來完成 ， 變異只是為選擇、交叉過程中可能丟失的某 些遺傳基因進(jìn)行修復(fù)和補(bǔ)充 ， 變異在遺傳算法的全局意義上只是一個(gè)背景操作 。 break。j++) { if(population[b].Path[j]==c[i]) { population[b].Path[j]=population[b].Path[i]。i++) { for(j=0。 } } } for(i=p1+1。 population[a].Path[i]=population[b].Path[i]。j++) { if(population[a].Path[j]==population[b].Path[i]) { population[a].Path[j]=population[a].Path[i]。i++) { for(j=0。 } for(i=p1+1。 p1=p2。*/ p2=rand()%Pathlength。 p2=rand()%(Pathlength3)+2。 /*srand( (unsigned)time( NULL ) )。 int p1,p2,temp。 ＰＭＸ 操作保留了部分城市的絕對(duì)訪問順序，但是它更多地產(chǎn)生了 父代巡回路線中所沒有的部分新路線，所以這種操作方法的性狀遺傳特性不太好。 算法 PMX的運(yùn)算步驟如下： (1)隨機(jī)選取兩個(gè)基因座 I和 J緊后的位置為交叉點(diǎn)，即將第 I+1和 J個(gè)基因座之間的各個(gè)基因座定義為交叉區(qū)域。 } } 部分映射交叉 部分映射交叉（ Partially Mapped Crossover 簡稱 PMX）稱為部分匹配交叉。 code[a][i]=code[b][i]。iPathlength。 } */ i=rand()%(Pathlength2)+1。j++) printf(%d,population[i].Path[j])。i++) { for(j=0。 /* for(i=0。iPOPSIZE。 int t。 單點(diǎn)交叉 單點(diǎn)交叉又稱為簡單交叉，是指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。 population[i].Path[x]=temp_Path[x]。x++) { temp_Pa