【正文】 Jog等 [18]提出啟 發(fā)式算法 (Heuristic Algorithm)也取得了很好的效果。 例如，若有父個體 P( 1 4 5 2 3 6 )， 假設(shè)隨機 選擇的城市是 4， 3， 那么產(chǎn)生的新個體為Offspring(1 4 3 2 5 6)。 p2=temp。 int x,temp,p1,p2。 } if(p1p2) { temp=p1。 } } (3) 對換變異 ， 隨機選擇串中的兩點 ， 交換其碼值。 p1=p2。 int x,temp,p1,p2。 p=rand()%(Pathlengthj)+1。 population[b].Path[i]=c[i]。 c[i]=population[a].Path[i]。 } if(p1p2) { temp=p1。 PMX的算法描述： partially_mapped_crossover(int a,int b) { int i,j。i++) { t=code[a][i]。iPOPSIZE。 } } } } } 交叉算子 本文用于旅行商問題求解的交叉算子用的是常規(guī)單點交叉和部分映射交叉。 temp_fitness=population[j].fitness。 int temp_Path[MaxPathlength]。 } for(i=0。 rightvalue_sum=0。 for(j=0。 } code_path(int n) /*code change into path */ { int b[MaxPathlength]。 for(x=0。 輪盤賭選擇 (roulette wheel selection) 個體適應(yīng)度按比例轉(zhuǎn)換為 選中概率，將輪盤分成 n個扇區(qū)進行 n次選擇，產(chǎn)生n個 0～ 1之間的隨機數(shù)相當于轉(zhuǎn)動 n次輪盤，可以獲得 n次轉(zhuǎn)盤停止時指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個體被選中。 } } else k++。 for(i=0。 例如 ， 順序表 C = (1， 2， 3， 4， 5， 6， 7， 8， 9)，一條旅程為 517894632。 printf(\n)。xPOPSIZE。 /* Seed the randomnumber generator with current time so that * the numbers will be different every time we run. */ srand( (unsigned)time( NULL) )。 TSP問題的描述很簡單，簡言之就是尋找一條最短的遍歷 n個城市的路徑，或者說搜索整數(shù)子集 X = { 1， 2， … ， n} ( X 的元素表示對 n個城市的編號 ) 的一個排列л ( X) = { v1， v2， … ， vn},使 T = ∑ d( vi， vi + 1) + d( vi， vn) 取最小值。一般取 ～ 。 (2) 群體大小 M表示群體中所含個體的數(shù)量。它們共同完成對搜索空間的全局搜索和局部搜索，使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。 例如 ：以下兩個個體在第二、四個基因座之間進行交叉運算，得到兩個新個體： 均勻交叉算子 均勻交叉 (Uniform Crossover)：是指兩個配對個體的每個基因 座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。交叉運算是指兩個相互配對的染色體按某種方式交換其部分基因，從而形成新個體。 (3) 排序選擇方法（ Rankbased selection） 主要思想是：對群體中的所有個體按其適應(yīng)度大小進行排序，基于這個排序來分配各個個體被選中的概率。遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。 (2)由個體的表現(xiàn)型可計算出對應(yīng)個體的目標函數(shù)值。適應(yīng)度較高的個體遺傳到下一代的概率就相對大一些；而適應(yīng)度較低的個體遺傳到下一代的概率就 相對較小一些。 (2)便于在遺傳算法中利用所求解問題的專門知識。 符點數(shù)編碼 符點數(shù)編碼方法 :指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示個體的編碼長度等于其決策變量的個數(shù)，個體變量的長度等于去決策變量的真實值，所以也叫真值編碼方法．它有以下幾個優(yōu)點： (1)適合于在遺傳算法中表示范圍較大的數(shù)。這個特點是遺傳算法中使用格雷碼進行個體編碼的主要原因。它有如下幾個優(yōu)點： (1)編碼，解碼簡單易行 。 編碼是應(yīng)用遺傳算法時要解決的主要問題，也是設(shè)計 遺傳算法的一個關(guān)鍵步驟。 遺傳算法的應(yīng)用步驟： 第一步： 確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間。遺傳算法中包含了如下 5個基本要素 : (1) 對參數(shù)進行編碼； (2) 設(shè)定初始種群大小； (3) 適應(yīng)度函數(shù)的設(shè)計； (4) 遺傳操作設(shè)計； (5) 控制參數(shù)設(shè)定 (包括種群大小、最大進化代數(shù)、交叉率、變異率等 )。 2 1967年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。目前求解 TSP問題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、 Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹描述算法。遺傳算法是一類具有較強魯棒性的優(yōu)化算法，特別是對于一些大型、復(fù)雜非線性系統(tǒng)，它更表現(xiàn)出了比其他傳統(tǒng)優(yōu)化方法更加獨特和優(yōu)越的性能。 文章首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術(shù) ；接著 針對 TSP 問題 ， 論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應(yīng)用情況 ， 分別指出幾種常用的編碼方法的優(yōu)點和缺點 ，并且結(jié)合 TSP的運行實例詳細分析了基 本遺傳算法的 4個運行參數(shù)群體大小、遺傳算法的終止進化代數(shù)、交叉概率、變異概率，對遺傳算法的求解結(jié)果和求解效率的影響，經(jīng)過多次的測試設(shè)定出了它們一組比較合理的取值。 遺傳算法使用群體搜索技術(shù)，它通過對當前群體施加選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，并逐步使群體進化到包含或接近最優(yōu)解的狀態(tài)。 貨郎擔問題 (Traveling Salesman Problem ,TSP)， 也稱為巡回旅行商問題 ，是一個較古的問題 。 70年代 De Jong基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗。 基本原理 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法 ， 由美國 ， 其主要特 點是群體搜索策略和群體中個體之間的信息交換 ， 搜索不依賴于梯度信息 ?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應(yīng)用價 值。 第六步：設(shè)計遺傳算子，即確定出選擇運算、 交叉運算、變異運算等遺傳算子的具體操作方法。 編碼原則二 (最小字符集編碼原則 ):應(yīng)使用能使問題得到自然表示或描述的具有最小字符集的編碼方案。 由于二進制不便于反映所求問題的結(jié)構(gòu)特征，對于一些連續(xù)函數(shù)的優(yōu)化問題等，也由于遺傳運算的隨機特性而使得其局部搜索能力較差，因而人們提出了用格雷碼來對個體進行編碼。 假設(shè)一個二進制編碼為 B=bnbn1? b2b1，其對應(yīng)的格雷碼為 G=gngn1?g2g1。 (6)便于設(shè)計針對問題的專門知識的知識型遺傳算子。 多參數(shù)交叉編碼方法：將各個參數(shù)中起主要作用的碼位集中在一起。目標函數(shù)值的使用是通過評價個體適應(yīng)度來體現(xiàn)的。 乘冪尺度變換公式如下： F＇ =F ? 冪指數(shù) n與所求解的問題有關(guān)。概率越大所占轉(zhuǎn)盤面積越大，被選中的機率越大。 (7) 隨機聯(lián)賽選擇 (Stuchastic Tournament Selection) 每次選取幾個適應(yīng)度最高的一個個體 遺傳到下一代群體中。 雙點交叉算子 雙點交叉 (Twopoint Crossover)：是指在個體編碼串中隨機設(shè)置了兩個交叉點，然后進行部分基因交換。 例如 :以下兩個個體選取第三、六個基因座之后進行交叉運算，得到兩個新個體： 變異算子 在生物的遺傳和自然進化中，其細胞分裂復(fù)制環(huán)節(jié)有可能會因為某些偶然因素的影響而產(chǎn)生一些復(fù)制差錯，就會導(dǎo)致生物的某些基因發(fā) 生某種變異，從而產(chǎn)生新的染色體，表現(xiàn)出新的生物性狀。 (1) 編碼串長度 L。一般取 ～ 。表示每一代群體中被替換掉的個體中所占的百分率，即每一代中有 (M G個個體被替換掉 )。這樣選擇 初始種群可使遺傳算法更快地到達最優(yōu)解。y++) { if(y==0) code[x][y]=1。 for(y=0。 在求解 TSP問題時 ， 1985年 ， Grefenstette[9]等提出了基于順序表示 (ordinal representation)的遺傳基因編碼方法 。 for(i=0。j++) { if((b[j]==0)) { if(population[n].Path[i]==j) { code[n][i]=jk。Konstantin Boukreev[5]采用聯(lián)賽選擇方法和最優(yōu)個體保存方法相結(jié)合的方法 ，通過在 VC++ TSP問題的遺傳算法 ， 取得了很好的效果 。 (2)若當前群體中最佳個體的適應(yīng)度比總的迄今為止最好的個體適應(yīng)度還要高，則以當前群體中的最佳個體作為新的迄今為止最好的個體。xPOPSIZE。 for(i=0。 break。jPathlength1。 int x。i++) { if(population[j].valuepopulation[i].value) { temp_value=population[j].value。x++) { temp_Path[x]=population[j].Path[x]。iPOPSIZE。 } */ i=rand()%(Pathlength2)+1。 算法 PMX的運算步驟如下： (1)隨機選取兩個基因座 I和 J緊后的位置為交叉點，即將第 I+1和 J個基因座之間的各個基因座定義為交叉區(qū)域。 p2=rand()%(Pathlength3)+2。i++) { for(j=0。i++) { for(j=0。 simple_mutation() { int i,j,p。i++) code_path(i)。 while(abs(p2p1)2) { srand( (unsigned)time( NULL ) )。 } for(i=p2。 p1=rand()%Pathlength。 population[x].Path[p2]=temp。 while(abs(p2p1)2) { p2=rand()%Pathlength。 population[x].Path[p1+1]=temp。 王俊海 [8]將 Memetic算法與遺傳算法結(jié)合起來 ， 給出了一種基于 Memetic算法的高效遺傳算法 。 遺傳算法求解TSP問題20點測試數(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 點的測試結(jié)果 結(jié)果分析 從上表可以看出，用方法 112， 113， 124， 222的效果較好。 Konstantin Boukreev[12]實驗發(fā)現(xiàn) :當城市大小在 200之內(nèi)時 ， 該變異算子可以大大改善程序的運行速度 ， 隨著城市數(shù)目的增加 ， 尤其是當城市數(shù)目達到 1000以上時 ， 程序運行速度非常慢 。ip1。 p1=rand()%Pathlength。 } temp=population[x].Path[p1]。 int insert[MaxPathlength]。i=p2。 p1=rand()%Pathlength。 for(i=0。 從遺