【正文】 傳算法的觀點(diǎn)來(lái)看 ， 解的進(jìn)化主要靠選擇機(jī)制和交叉策略來(lái)完成 ， 變異只是為選擇、交叉過(guò)程中可能丟失的某 些遺傳基因進(jìn)行修復(fù)和補(bǔ)充 ， 變異在遺傳算法的全局意義上只是一個(gè)背景操作 。 } } } for(i=p1+1。 } for(i=p1+1。 /*srand( (unsigned)time( NULL ) )。 } } 部分映射交叉 部分映射交叉（ Partially Mapped Crossover 簡(jiǎn)稱(chēng) PMX）稱(chēng)為部分匹配交叉。j++) printf(%d,population[i].Path[j])。 int t。 for(x=0。j++) { for(i=j+1。 } rate(int m) { population[m].fitness=(double)population[m].value/(double)rightvalue_sum。i++) { length=0。 else { if(code[n][i]+k==j+1) { population[n].Path[i]=j+1。iMaxPathlength。 rightvalue(POPSIZE)。我們希望適應(yīng)度最好的個(gè)體要盡可 能的保存到下一代群體中，為達(dá)到這個(gè)目的我們使用最優(yōu)保存策略進(jìn)化模型。 為了保證遺傳算法的全局收斂性 ， 就要維持群體中個(gè)體的多樣性 ， 避免有效基因的丟失 。 for(j=1。 path_code(int n) /*path change into code */ { int b[MaxPathlength]。 在遺傳算法中有兩種基于串的基因編碼形式 ， 一種是基于二進(jìn)制的遺傳算法 (binary coded GA)， 一種是基于順序的遺傳算法 (the orderbased GA)。xPOPSIZE。x++) { for(y=0。一種是完全隨機(jī)的方法產(chǎn)生，它適合與對(duì)問(wèn)題的解無(wú)任何先驗(yàn)知識(shí)的情況 。一般為 100～ 1000。 (3) 交叉概率 pc。 較常用的基本位變異、均勻變異、邊界變異、非均勻變異和高斯變異等。交叉對(duì)象一般是符號(hào)編 碼表示的個(gè)體。它是在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體 。 (5) 確定式采樣選擇（ Determinstic Sampling selection） 基本思想是按照一種確定的方式進(jìn)行選擇操作。有以下幾種常用的選擇算子的操作方法：比例選擇 、最優(yōu)保存策略、確定式采樣選擇、無(wú)放回隨機(jī)選擇、無(wú)放回余數(shù)隨機(jī)選擇、排序選擇和隨機(jī)聯(lián)賽選擇等。 適應(yīng)度尺度變換 (Fitness Scaling):對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小變換。個(gè)體適應(yīng)度大小決定該個(gè)體被遺傳到下一代群體中的概率。 最后，簡(jiǎn)要介紹一下參數(shù)編碼方法。 (4)改善了遺傳算法的復(fù)雜性，提高了運(yùn)算效率。 (3)符合最小字符集編碼原則。 (4)便于利用模式定理對(duì)算法進(jìn)行理論分析。目前還沒(méi)有一套既嚴(yán)密有完整的指導(dǎo)理論及評(píng)價(jià)準(zhǔn)則能夠指導(dǎo)我們?cè)O(shè)計(jì)編碼方案。 第四步：確定解碼方法，即確定出個(gè)體基因型 X到個(gè)體表現(xiàn)型 X的對(duì)應(yīng)關(guān)系轉(zhuǎn)換方法。但這些遺傳算法都有共同的特點(diǎn)，即通過(guò)對(duì)生物遺傳和進(jìn)化過(guò)程中選擇、交叉、變異機(jī)理的模仿，來(lái)完成對(duì)問(wèn)題最優(yōu)解的自適應(yīng)搜索過(guò)程。 5 1991年 編輯出版了《遺傳算法手冊(cè) (Handbook of Geic Algorithms)》書(shū)中包括遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。 因此遺傳算法在 TSP問(wèn)題求解方面的應(yīng)用研究 ， 對(duì)于構(gòu) 造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決 TSP問(wèn)題等有著多方面的重要意義 。盡管在遺傳算法的研究和應(yīng)用過(guò)程中出現(xiàn)許多難題 ，同時(shí)也會(huì)產(chǎn)生許多不同的算法設(shè)計(jì)觀點(diǎn)，然而，目前遺傳算法的各種應(yīng)用實(shí)踐已經(jīng)展現(xiàn)出了其優(yōu)異的性能和巨大的發(fā)展?jié)摿?，它的發(fā)展前景激勵(lì)著各類(lèi)專(zhuān)業(yè)技術(shù)人員把遺傳算法的理論和方法運(yùn)用于自己的工作實(shí)踐中。然而，自然界中的生物卻在這方面表現(xiàn)出了其優(yōu)異的能力，它們能夠以?xún)?yōu)勝劣汰、適者生存的自然進(jìn)化規(guī)則生存和繁衍，并逐步產(chǎn)生出對(duì)其生存環(huán)境適應(yīng)性很高的優(yōu)良物種。 關(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 the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of geic algorithm in solving TSP is made. Keywords: TSP geic algorithm geic operators encoding 引 言 現(xiàn)代科學(xué)理論研究與實(shí)踐中存在著大量與優(yōu)化、自適應(yīng)相關(guān)的問(wèn)題，但除了一些簡(jiǎn)單 的情況之外，人們對(duì)于大型復(fù)雜系統(tǒng)的優(yōu)化和自適應(yīng)問(wèn)題仍然無(wú)能為力。 遺傳算法是新發(fā)展起來(lái)的一門(mén)學(xué)科，各種理論、方法尚未成熟，有待于進(jìn)一步地發(fā)展和完善，但它卻為我們解決許多復(fù)雜問(wèn)題提供了希望。遺傳算法就其本質(zhì)來(lái)說(shuō) ， 主要是解決復(fù)雜問(wèn)題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法 。 4 1989年出版了專(zhuān)著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search， Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。這樣，由不同的編碼 方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。 第三步：確定表示可行解的染色體編碼方法，也即確定出個(gè)體的基因型 X及遺傳算法的搜索空間。 針對(duì)一個(gè)具體問(wèn)題，如何設(shè)計(jì)一個(gè)完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一，也是遺傳算法的一個(gè)重要研究方向。 (3)符合最小字符集編碼原則 。 (2)交叉，變異等遺傳操作易于實(shí)現(xiàn)。 (3)便于較大空間的遺傳搜索。 但對(duì)于使用符號(hào)編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計(jì)交叉、變異等遺傳運(yùn)算的操作方法，以滿(mǎn)足問(wèn)題的各種約束要求，這樣才能提高算法的搜索性能。 根據(jù)個(gè)體的適應(yīng)值，就可決定在此環(huán)境下的生存能力。 但是，在僅用適應(yīng)度函數(shù)來(lái)計(jì)算個(gè)體適應(yīng)度時(shí) ,有些遺傳算法收斂很快 ,有些遺傳算法收斂很慢，因此在運(yùn)行到不同的階段時(shí)須對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。選擇的主要目的為了避免基因缺失、提高全局收斂性和計(jì)算效率。由于隨機(jī)操作的原因，這種選擇方法的選擇誤差較大，有時(shí)連適應(yīng)度高的個(gè)體也選不上。 單點(diǎn)交叉算子 最常用的交叉算子是單點(diǎn)交叉算子。然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來(lái)修改交叉區(qū)域之外的各個(gè)基因座的基因值。 (2) 維持群體多樣性，防止早熟現(xiàn)象。一般的建議范圍是 20～ 100。表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。 產(chǎn)生初始種群的方法通常有兩種。xPOPSIZE。 for(x=0。 對(duì)遺傳基因進(jìn)行編碼時(shí) ， 要考慮到是否適合或有利于交叉和變異操作 。 但是這種表 示方法 ， 在進(jìn)行單點(diǎn)交叉的時(shí)候 ， 交叉點(diǎn)右側(cè)部分的旅程發(fā)生了隨機(jī)變化 ， 但是交叉點(diǎn)左側(cè)部分的旅程未發(fā)生改變 ， 由于存在這樣的缺點(diǎn) ， 所以順序表示的方法的適用性存在一定的問(wèn)題。i++) { k=0。 遺傳算法中一個(gè)要求解決的問(wèn)題是如何防止“早熟”收斂現(xiàn)象 。 最優(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è)體。x++) code_path(x)。 for(i=0。j++) { if((b[j]==1)) k++。in。i++) rightvalue_sum=population[i].value+rightvalue_sum。jPOPSIZE。 population[i].fitness=temp_fitness。單點(diǎn)交叉運(yùn)算的示意圖如下： Ａ：０１１００１１ Ａ １ ：０１１０００１ Ｂ：１００１１０１ Ｂ １ ：１００１１１１ 交叉點(diǎn) one_point_crossover(int a,int b) { int i,j。jPathlength。 code[b][i]=t。 int c[MaxPathlength]。 p2=temp。 break。 } } } } 變異算子 遺傳算法強(qiáng)調(diào)的是交叉的功能 。 code[i][j]=p。 x=rand()%(POPSIZE)。 } for(i=p1+1。 int x,temp,p1,p2。 p2=temp。 x=rand()%(POPSIZE)。 for(i=p2。 這種方法與貪心對(duì)換變異有相同的思想 ， 但是更易擴(kuò)張更有效率 。 選擇 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)題取得了滿(mǎn)意的結(jié)果 ， 把局部?jī)?yōu)化的高效性與遺傳算法的魯棒性很好的結(jié)合起了 。 } 此外 ， 對(duì)于變異操作還有一些變體形式 ， 如 Sushil Jouis[19]提出的貪心對(duì)換變異 (greedyswap mutation)， 其基本思想是從一個(gè)染色體中隨機(jī)的選擇兩個(gè)城市 (即兩個(gè)碼值 )， 然后交換它們 ， 得到新的染色體 ， 以旅程長(zhǎng)度為依據(jù)比較交換后的染色體與原來(lái)的染色體的大小 ， 保留旅程長(zhǎng)度值小的染色體 。