【正文】 選擇 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。 將這種算法應(yīng)用于 TSP問(wèn)題取得了滿意的結(jié)果 ， 把局部?jī)?yōu)化的高效性與遺傳算法的魯棒性很好的結(jié)合起了 。 這種方法與貪心對(duì)換變異有相同的思想 ， 但是更易擴(kuò)張更有效率 。 } 此外 ， 對(duì)于變異操作還有一些變體形式 ， 如 Sushil Jouis[19]提出的貪心對(duì)換變異 (greedyswap mutation)， 其基本思想是從一個(gè)染色體中隨機(jī)的選擇兩個(gè)城市 (即兩個(gè)碼值 )， 然后交換它們 ， 得到新的染色體 ， 以旅程長(zhǎng)度為依據(jù)比較交換后的染色體與原來(lái)的染色體的大小 ， 保留旅程長(zhǎng)度值小的染色體 。 for(i=p2。 } if(p1p2) { temp=p1。 x=rand()%(POPSIZE)。 } (4) 插入變異 ， 從串中隨機(jī)選擇 1個(gè)碼 ， 將此碼插入隨機(jī)選擇的插入點(diǎn)之后 。 p2=temp。 p2=rand()%(Pathlength1)+1。 int x,temp,p1,p2。i=p1+1。 } for(i=p1+1。 p2=rand()%Pathlength。 x=rand()%(POPSIZE)。 } (2) 逆轉(zhuǎn)變異 ， 在編碼串中 ， 隨機(jī)選擇兩點(diǎn) ， 再將這兩點(diǎn)內(nèi)的子串按反序插入到原來(lái)的位置中。 code[i][j]=p。 i=rand()%(POPSIZE)。 } } } } 變異算子 遺傳算法強(qiáng)調(diào)的是交叉的功能 。jPathlength。 break。jPathlength。 p2=temp。 while(abs(p2p1)2) { /*srand( (unsigned)time( NULL ) )。 int c[MaxPathlength]。 (2)對(duì)交叉區(qū)域中的每個(gè)基因座Ｐ（Ｐ＝Ｉ＋１， I＋２ … ，Ｊ） ,體Ｔ Ｘ 中去求出 tＱ Ｘ =tＰ Ｙ 的基因座Ｑ，在個(gè)體Ｔ Ｙ 中求出 tＲ Ｙ ＝ tＰ y的基因座Ｒ，然后相互交換基因值 tＱ Ｘ 和 tＰ Ｙ ， tＲＹ 和 tＰ y所得的結(jié)果即為Ｔ Ｘ １ ，Ｔ Ｙ １ 。 code[b][i]=t。 for(i。jPathlength。i++) path_code(i)。單點(diǎn)交叉運(yùn)算的示意圖如下： Ａ：０１１００１１ Ａ １ ：０１１０００１ Ｂ：１００１１０１ Ｂ １ ：１００１１１１ 交叉點(diǎn) one_point_crossover(int a,int b) { int i,j。 population[j].Path[x]=population[i].Path[x] 。 population[i].fitness=temp_fitness。 population[j].value=population[i].value 。jPOPSIZE。 int temp_value。i++) rightvalue_sum=population[i].value+rightvalue_sum。j++) length=l[population[i].Path[j]1][population[i].Path[j+1]1]+length。in。 } } } } } rightvalue(int n) { int i,j。j++) { if((b[j]==1)) k++。iPathlength。 for(i=0。x++) rate(x)。x++) code_path(x)。 (3)用迄今為止最好的個(gè)體替換掉當(dāng)前群體中最差的個(gè)體。 最優(yōu)保存策略選擇 (Ｅ litist selection) 在遺傳算法的運(yùn)行過(guò)程中，通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺 傳操作而不斷產(chǎn)生新的個(gè)體，雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)生出越來(lái)越多的優(yōu)良個(gè)體，但由于遺傳操作的隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個(gè)體。謝勝利等提出濃度控制策略 ， 當(dāng)某種個(gè)體的濃度超過(guò)給定的濃度閥值時(shí)減少該種個(gè)體的數(shù)量 ， 使之控制在給定的濃度閥值之內(nèi) ， 并隨機(jī)產(chǎn)生新的個(gè)體以補(bǔ)足種群的規(guī)模 ， 他們通過(guò)實(shí)驗(yàn)證明該策略很好的解決了遺傳算法中群體的多樣性問(wèn)題 。 遺傳算法中一個(gè)要求解決的問(wèn)題是如何防止“早熟”收斂現(xiàn)象 。 b[j]=1。i++) { k=0。iMaxPathlength。 但是這種表 示方法 ， 在進(jìn)行單點(diǎn)交叉的時(shí)候 ， 交叉點(diǎn)右側(cè)部分的旅程發(fā)生了隨機(jī)變化 ， 但是交叉點(diǎn)左側(cè)部分的旅程未發(fā)生改變 ， 由于存在這樣的缺點(diǎn) ， 所以順序表示的方法的適用性存在一定的問(wèn)題。 順序表示是指所有城市依次排列構(gòu)成一個(gè)順序表 (order list)， 對(duì)于一條旅程 ， 可以依旅行經(jīng)過(guò)順序處理每個(gè)城市 ， 每個(gè)城市在順序表中的順序就是一個(gè)遺傳因子的表示 ， 每處理完一個(gè)城市 ， 從順序表中去掉該城市。 對(duì)遺傳基因進(jìn)行編碼時(shí) ， 要考慮到是否適合或有利于交叉和變異操作 。yPathlength。 for(x=0。 else code[x][y]=rand()%(Pathlengthy)+1。xPOPSIZE。下面給出了 C語(yǔ)言描述的完全隨機(jī)產(chǎn)生新種群的函數(shù)。 產(chǎn)生初始種群的方法通常有兩種。 約束條件的處理方法 主要有搜索空間限定法、可行解變換法、罰函數(shù)法。表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。 (4) 變異概率 pm。一般的建議范圍是 20～ 100。使用二進(jìn)制編碼時(shí)，編碼串長(zhǎng)度 l的選取與問(wèn)題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí)，編碼串長(zhǎng)度 l與決策變量的個(gè)數(shù) n相等；使用符號(hào)變量來(lái)表示個(gè)體時(shí)。 (2) 維持群體多樣性，防止早熟現(xiàn)象。在遺傳算法中的變異運(yùn)算，是指將基因座上的基因值用該基因座的等位基因來(lái)替換，從而產(chǎn)生新個(gè)體。然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來(lái)修改交叉區(qū)域之外的各個(gè)基因座的基因值。 雙點(diǎn)交叉的具體操作過(guò)程是： (1) 在相互配對(duì)的兩個(gè)個(gè)體編碼中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。 單點(diǎn)交叉算子 最常用的交叉算子是單點(diǎn)交叉算子。 交叉算子 在生物的自然進(jìn)化中，兩個(gè)同源染色體通過(guò)交配而重組，形成新的染色體，從而產(chǎn)生新的個(gè)體或物種。由于隨機(jī)操作的原因，這種選擇方法的選擇誤差較大，有時(shí)連適應(yīng)度高的個(gè)體也選不上。 (2) 最優(yōu)保存策略選擇 (Elitist selection) 在遺傳算法的運(yùn) 行過(guò)程中，通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷產(chǎn)生新的個(gè)體，雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)生出越來(lái)越多的優(yōu)良個(gè)體，但由于遺傳操作的隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個(gè)體。選擇的主要目的為了避免基因缺失、提高全局收斂性和計(jì)算效率。 指數(shù)尺度變換公式如下： F＇ =exp(β F) 系數(shù)β決定了選擇的強(qiáng)制性。 但是，在僅用適應(yīng)度函數(shù)來(lái)計(jì)算個(gè)體適應(yīng)度時(shí) ,有些遺傳算法收斂很快 ,有些遺傳算法收斂很慢，因此在運(yùn)行到不同的階段時(shí)須對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。 由于個(gè)體適應(yīng)度大小決定該個(gè)體被遺傳到下一代群體中的概率。 根據(jù)個(gè)體的適應(yīng)值，就可決定在此環(huán)境下的生存能力。 適應(yīng)度函數(shù) 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)其生存環(huán)境的適應(yīng)程度。 但對(duì)于使用符號(hào)編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計(jì)交叉、變異等遺傳運(yùn)算的操作方法，以滿足問(wèn)題的各種約束要求，這樣才能提高算法的搜索性能。 (7)便于處理復(fù)雜的決策變量約束條件。 (3)便于較大空間的遺傳搜索。格雷碼到二進(jìn)制碼的轉(zhuǎn)換公式： 格雷碼編碼方法是二進(jìn)制編碼方法的一種變形，其編碼精度與相同長(zhǎng)度二進(jìn)制編碼方法的精度相同。 (2)交叉，變異等遺傳操作易于實(shí)現(xiàn)。 格雷碼編碼 格雷碼，連續(xù)的兩個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間只有一個(gè)碼位不相同。 (3)符合最小字符集編碼原則 。 迄今為止人們已經(jīng)提出了許多的編碼方法，總的來(lái)說(shuō)，可以分為三類：二進(jìn)制編碼方法，浮點(diǎn)數(shù)編碼方法，符號(hào)編碼方法。 針對(duì)一個(gè)具體問(wèn)題，如何設(shè)計(jì)一個(gè)完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一，也是遺傳算法的一個(gè)重要研究方向。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M、 T、 Pc、 Pm等參數(shù)。 第三步：確定表示可行解的染色體編碼方法，也即確定出個(gè)體的基因型 X及遺傳算法的搜索空間。 基本遺傳算法描述： 基本遺傳算法只使用選擇算子 ( Selection Operator)、交叉算子(Crossover Operator)、變異算子 (Mutation Operator)這三種算子。這樣，由不同的編碼 方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。 它是一種全局化搜索算法 ， 尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問(wèn)題 。 4 1989年出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search， Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。在一系列研究工作的基礎(chǔ)上 80年代 Goldberg進(jìn)行總結(jié)歸納，形成了遺傳算的基本框架。遺傳算法就其本質(zhì)來(lái)說(shuō) ， 主要是解決復(fù)雜問(wèn)題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法 。 最早可以追溯到 1759年 Euler提出的騎士旅行問(wèn)題 。 遺傳算法是新發(fā)展起來(lái)的一門學(xué)科，各種理論、方法尚未成熟，有待于進(jìn)一步地發(fā)展和完善，但它卻為我們解決許多復(fù)雜問(wèn)題提供了希望。由于其具有思想簡(jiǎn)單、易于實(shí)現(xiàn)、應(yīng)用效果明顯等優(yōu)點(diǎn)而被眾多應(yīng)用領(lǐng) 域所接受，并在自適應(yīng)控制、組合優(yōu)化、模式識(shí)別、機(jī)器學(xué)習(xí)、人工生命、管理策略等領(lǐng)域得到了廣泛應(yīng)用。 關(guān)鍵詞 ： TSP 遺傳算法 遺傳算子 編碼 Abstract TSP (Traveling Salesman Problem) is a typical NP plete problem and geic algorithm (GA) is the perfect method for solving NP plete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and geic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic geic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic geic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid geic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains