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