旅行商問題畢業(yè)論文

1、<p><b>　　摘要</b></p><p>　　旅行商問題（Travelling Salesman Problem，簡稱TSP）是一個典型的組合優(yōu)化問題，并且是一個NP難題，其可能的路徑總數(shù)與城市數(shù)目n 是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，因而尋找出有效的近似求解算法就具有重要的意義。</p><p>　　遺傳算法（GA）是求解旅行商問題

2、（TSP）的常用方法之一。針對中國旅行商問題（CTSP），本文利用遺傳算法的全局搜索能力進(jìn)行組合優(yōu)化問題求解，設(shè)計一種大比例的優(yōu)秀個體保護(hù)的大變異遺傳算法，并使用MATLAB語言進(jìn)行了實際的編程求解，編程中的各個模塊分別實現(xiàn)了選擇、交叉、變異等關(guān)鍵環(huán)節(jié)。用編制的程序快速求解出了滿足的結(jié)果，用本文設(shè)計的遺傳算法的思路和編程程序是正確的。用該策略迅速找到了CTSP最優(yōu)解，該路徑長度為15378km，比目前已知CTSP解更優(yōu)。對遺傳算法迅速求

3、解TSP最優(yōu)解提供了可行解決方案。</p><p>　　關(guān)鍵詞：遺傳算法；CTSP；最短路徑；MATLAB</p><p><b>　　Abstract</b></p><p>　　The traveling salesman problem (TSP) is a well-known NP complete problem, It’s inc

4、reased by exponential n. So, it is hard to find a precision result, and it is very important to search for the near result. </p><p>　　The genetic algorithm (GA) is one of the ideal methods in solving it. For

5、 CTSP，According to genetic algorithm’s global searching proterty, a kind of big probability variation’s genetic algorithm is put forward, which copies big proportion of fittest. In MATLAB, the typical Chinese traveling s

6、alesman problem is computed and the result shows the thought and program is correct. The best path for CTSP is found quickly through the algorithm. The best path 15378km is get, the result is the best so far</p>&

7、lt;p>　　Key words: The Genetic Algorithm (GA); Chinese Traveling Salesman Problem (CTSP); The Shortest Path; MATLAB </p><p><b>　　目 錄</b></p><p><b>　　摘要I</b></p>

8、<p>　　AbstractII</p><p><b>　　緒論1</b></p><p>　　1 CTSP數(shù)學(xué)模型及常用算法2</p><p>　　1．1 TSP的數(shù)學(xué)模型2</p><p>　　1．2 TSP問題的常用求解方法2</p><p>　　1．2．1

9、 遺傳算法（GA）2</p><p>　　1．2．2 模擬退火算法（SA）3</p><p>　　1．2．3 蟻群算法（ACO）3</p><p>　　1．2．4 禁忌搜索（TS）4</p><p>　　1．2．5 粒子群優(yōu)化算法（PSO）4</p><p>　　1．3 CTSP問題的數(shù)學(xué)模型，目前

10、最優(yōu)解5</p><p>　　1．3．1 CTSP的數(shù)學(xué)建模5</p><p>　　1．3．2 CTSP目前最優(yōu)解5</p><p>　　2 用遺傳算法SGA求解CTSP問題7</p><p>　　2．1 遺傳算法求解框架7</p><p>　　2．2 種群初始化和計算適應(yīng)度8</p>

11、<p>　　2．2．1 種群初始化8</p><p>　　2．2．2 計算適應(yīng)度8</p><p>　　2．3 遺傳算子8</p><p>　　2．3．1 選擇算子8</p><p>　　2．3．2 交叉算子8</p><p>　　2．3．3 變異算子9</p><

12、;p>　　2．3．4 終止判斷9</p><p>　　3 MATLAB簡介與特點10</p><p>　　3．1 MATLAB簡介10</p><p>　　3．2 MATLAB的特點10</p><p>　　4 用MATLAB求解CSTP問題12</p><p>　　4．1 種群初始化12

13、</p><p>　　4．2 計算適應(yīng)度12</p><p>　　4．3　選擇算子12</p><p>　　4．3．1 計算選擇算子的過程12</p><p>　　4．3．2　選擇算子計算的代碼實現(xiàn)13</p><p>　　4．4 交叉算子15</p><p>　　4．4．1

14、交叉概率的選擇15</p><p>　　4．4．2 交叉算法實現(xiàn)16</p><p>　　4．5 變異算子16</p><p>　　4．5．1 變異概率的選擇16</p><p>　　4．5．2 變異算法實現(xiàn)17</p><p>　　4．6 路徑輸出17</p><p>　

15、　5 實驗結(jié)論及分析19</p><p>　　5．1 實驗結(jié)論19</p><p>　　5．2 需要進(jìn)一步解決的問題20</p><p><b>　　致 謝21</b></p><p><b>　　主要參考文獻(xiàn)22</b></p><p><b>

16、　　緒 論</b></p><p>　　旅行商問題（Travelling Salesman Problem，簡稱TSP）是一個典型的組合優(yōu)化問題，并且是一個NP難題，遺傳算法（GA）、模擬退火算法（SA）等算法是求解這類問題的常用方法。</p><p>　　首先，提出了CTSP問題，并建立CTSP問題的數(shù)學(xué)模型，列舉常用的幾種求解旅行商問題的解法，給出目前求解出這個問題的最優(yōu)

17、解。</p><p>　　其次，用遺傳算法求解CTSP問題。針對中國旅行商問題（CTSP），設(shè)計了選擇 (Selection)交叉 (Crossover)變異 (Mutation)遺傳算法的改進(jìn)策略。用該策略迅速找到了CTSP最優(yōu)解，該路徑長度為15378km，比目前已知CTSP解更優(yōu)。對遺傳算法迅速求解TSP最優(yōu)解提供了可行解決方案。</p><p>　　再次，選擇工具實現(xiàn)用遺傳算法求解

18、旅行商問題，在這次設(shè)計過程中，我們選擇了MATLAB作為我們處理這個問題的工具，因為旅行商問題是一個數(shù)學(xué)問題，MATLAB是一個專門解決數(shù)學(xué)問題的數(shù)學(xué)軟件，并且提供了遺傳算法工具箱（我們程序中用到的很多代碼都來自于遺傳算法工具箱中的函數(shù)），而且它有很強的繪圖功能，所以，我們選擇MATLAB作為我們解決旅行家問題的工具。</p><p>　　最后，對我們事先得到的結(jié)果進(jìn)行分析，最終求得最優(yōu)解，得到最優(yōu)路徑。在以下的

19、文章中，介紹這一過程的具體實現(xiàn)。</p><p>　　1 CTSP數(shù)學(xué)模型及常用算法</p><p>　　旅行商問題（Travelling Salesman Problem，簡稱TSP）可描述為某旅行商欲往n個城市推銷貨物，從某個城市出發(fā)，沿途經(jīng)過各個城市一次后返回到出發(fā)城市，要確定一條行走的路線，使得總路徑最短。</p><p>　　1．1 TSP的數(shù)學(xué)模型&

20、lt;/p><p>　　假設(shè)有一個圖G= ( V，E) ， 其中V是頂點集，E是邊集，設(shè)D=()是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短路徑的回路。若對于城市V={，，…， } 的一個訪問順序為 ,其中 ∈V(i=1，2，3…，n) ，且記 ，則旅行商問題的數(shù)學(xué)模型為：</p><p><b>　?。?）&

21、lt;/b></p><p>　　1．2 TSP問題的常用求解方法</p><p>　　TSP問題求解方法目前有好幾種，下面介紹幾種求解TSP問題比較成熟的幾種算法，遺傳算法（GA）、模擬退火算法（SA）、蟻群算法（ACO）、禁忌搜索（TS）和粒子群優(yōu)化算法（PSO）。</p><p>　　1．2．1 遺傳算法（GA）</p><p&g

22、t;　　遺傳算法是J．Holland于1975年受生物進(jìn)化論啟發(fā)而提出的源于自然界生物進(jìn)化過程，生物是通過自然選擇和有性繁殖兩個基本過程如圖1所示不斷進(jìn)化的，通過自然淘汰變異、遺傳進(jìn)化，以適應(yīng)環(huán)境的變化產(chǎn)生適合個體。人們將搜索和優(yōu)化過程模擬生物進(jìn)化過程，用搜索空間的點模擬自然界中的生物個體，將求解過程的目標(biāo)函數(shù)度量或生物體對環(huán)境的適應(yīng)能力，將生物的優(yōu)勝劣汰過程類比為搜索和優(yōu)化過程中好的可行取代交叉的可行解的迭代過程。</p>

23、<p>　　1．2．2 模擬退火算法（SA）</p><p>　　模擬退火算法最早由Metropolis等（1953）提出，Kirkpatrick于1983 年將其用于組合優(yōu)化。SA算法是基于Mente Carlo迭代求解策略的一種隨即優(yōu)化算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。算法的基本思想是從一給定解開始的，從鄰域中隨機產(chǎn)生另一個解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有

24、限范圍內(nèi)變壞。它由一控制參數(shù)t決定，其作用類似于物理過程中的溫度T，對于控制參數(shù)t的每一取值，算法持續(xù)進(jìn)行“產(chǎn)生新解-判斷-接受或舍棄”的迭代過程，對應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。經(jīng)過大量的解變換后，可以求得給定控制參數(shù)t值時優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)t的值，重復(fù)執(zhí)行上述迭代過程。當(dāng)控制參數(shù)逐漸減小并趨于零時，系統(tǒng)亦越來越趨于平衡狀態(tài)，最后系統(tǒng)狀態(tài)對應(yīng)于優(yōu)化問題的整體最優(yōu)解。該過程也稱冷卻過程。由于固體退火必須緩

25、慢降溫，才能使固體在每一溫度下都達(dá)到熱平衡，最終趨于平衡狀態(tài)，因此，控制參數(shù)的值必須緩慢衰減，才能確保模擬退火算法最終趨于優(yōu)化問題的整體最優(yōu)解。模擬退火算法要從鄰域中隨機產(chǎn)生另一個解，對于TSP問題，它的鄰域是指兩條路徑除局部</p><p>　　1．2．3 蟻群算法（ACO）</p><p>　　蟻群算法是Colorni和Dorigo等于20世紀(jì)90年代對蟻群行為的研究受啟發(fā)而提出的，

26、仿生學(xué)家發(fā)現(xiàn)螞蟻個體之間通過一種外激素（pheromone）的物質(zhì)信息傳遞。螞蟻在移動中能在所經(jīng)路徑中遺留外激素，而且螞蟻會在移動中能夠感知這種物質(zhì)，并以次指導(dǎo)自己的運動方向。因此，有大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象。某一路徑上走過的螞蟻越多，則后來選擇該路徑的概率就越大，螞蟻個體之間就是通過這種信息的交流達(dá)到搜索失誤的目的，人們通過模擬螞蟻搜索失誤的過程來求解一些組合優(yōu)化問題。</p><p&

27、gt;　　1．2．4 禁忌搜索（TS）</p><p>　　禁忌搜索思想最早由Glover于1986年提出的，它是模擬人的思維的一種只能搜索算法。即人們對已搜索的地方不會立即去搜索，而去對其他地方進(jìn)行搜索，若沒能找到可再搜索已去的地方。禁忌搜索算法從一個初始可能解出發(fā)，選擇一系列的特定搜索方向（移動）作為試探，選擇實現(xiàn)使目標(biāo)函數(shù)值減少最多的移動。為了避免陷入局部最優(yōu)解，禁忌搜索中采用了一種靈活“記憶”技術(shù)，即對

28、已經(jīng)進(jìn)行的優(yōu)化過程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，這就是tabu表的建立。tabu表中保存了最近若干次迭代過程中所實現(xiàn)的移動，凡是處于tabu表中的移動，在當(dāng)前迭代過程中是不允許實現(xiàn)的，這樣可以避免算法重新訪問在最近若干次迭代過程中已經(jīng)訪問的解群。從而防止了循環(huán)，幫助算法擺脫局部最優(yōu)解。另外，為了盡可能不錯過產(chǎn)生最優(yōu)解的“移動”，禁忌搜索孩采用“釋放準(zhǔn)則”的策略。</p><p>　　1．2．5 粒子群優(yōu)

29、化算法（PSO）</p><p>　　粒子群優(yōu)化算法一種基于群體智能方法的演化計算技術(shù)，最早有Konnedy和Eberhart于1995年提出，受到人工生命的研究結(jié)果的啟發(fā)，PSO的基本概念源于對鳥群捕食行為的研究。PSO中，每個優(yōu)化問題的潛在解都是搜索空間的一只鳥，稱之為“粒子”。所有粒子都有一個又被優(yōu)化的函數(shù)決定他們的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機粒子（隨機解

30、），然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。另一個極值。另外也可以不用整個種群而知識用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。</p><p>　　1．3 CTSP問題的數(shù)學(xué)模型，目前最優(yōu)解</p><p>　　TSP問題有兩類，即對稱與不對稱。對稱即第i個城市到第j城市的距離與第j個城市到第i城市的距離相等；不對稱即第i城市和第

31、j城市的距離與第j個城市到第i城市的距離不相等。中國旅行商問題（CTSP）是一個真實的地理問題，由勒藩教授提出，可以簡單描述為從北京出發(fā)經(jīng)過中國的31個省會、直轄市又回到北京的最短路徑。 </p><p>　　1．3．1 CTSP的數(shù)學(xué)建模</p><p>　　在中國31個城市之間尋找最優(yōu)路徑，共有(31- 1) ! /2= 1.326×條路徑。CTSP問題中31個

32、城市編號及平面圖中相對坐標(biāo)如下所示：</p><p>　　1拉薩（1304，2312）— 2北京（3639，1315）— 3上海（4177，2244）— 4天津（3712，1399）— 5石家莊（3488，1535）— 6太原（3326，1556）— 7呼和浩特（3238，1229）— 8沈陽（4196，1004）— 9長春（4312 ，790）— 10哈爾濱（4386，570）— 11西安（3007，1970）

33、— 12蘭州（2562，1756）— 13銀川（2788，1491）— 14 西寧（2381，1676）— 15烏魯木齊（1332，695）— 16濟南（3715，1678）— 17南京（3918，2179）— 18杭州（4061，2370）— 19合肥 3780，2212）— 20南昌（3676，2578）— 21福州（4029，2838）— 22臺北（4263，2931）— 23鄭州（3429，1908）— 24武漢（3507，23

34、67）— 25長沙（3394，2643）— 26廣州（3439，3201）— 27南寧（2935，3240）— 28海口（3140，3550）— 29成都（2545，2357）— 30貴陽（2778，</p><p>　　1．3．2 CTSP目前最優(yōu)解</p><p>　　CTSP問題求解；最優(yōu)路徑為：</p><p>　?。?1 福州—22 臺北—18 杭州—

35、3 上?！?7 南京—19 合肥—23 鄭州—11 西安—6 太原—5 石家莊—16 濟南—4 天津—2 北京—8 沈陽—9 長春—10哈爾濱—7 呼和浩特—13 銀川—12 蘭州—14 西寧—15 烏魯木齊—1 拉薩—29 成都—31 昆明—30 貴陽—27 南寧—28 ?？凇?6 廣州—25 長沙—24 武漢—20 南昌）獲得結(jié)果的總路程為15378km，這也是CTSP問題的最短路徑。所得路徑圖形如圖2所示：</p>

36、<p><b>　　圖2最優(yōu)路徑圖</b></p><p>　　2 用遺傳算法SGA求解CTSP問題</p><p>　　2．1 遺傳算法求解框架</p><p>　　遺傳算法根據(jù)適者生存，優(yōu)勝劣汰等自然進(jìn)化原則，從候選解中一代一代地優(yōu)選適應(yīng)性函數(shù) ( FitnessFunction) 的解，重組后構(gòu)成新的參數(shù)組合，而逐漸取得最優(yōu)解

37、 。適應(yīng)性函數(shù)與傳統(tǒng)優(yōu)化算法中的目標(biāo)函數(shù)和成本函數(shù)相對應(yīng),父輩個體 ( Individual ) 對子代的貢獻(xiàn)與適應(yīng)性函數(shù)成正比。它通常使用3種操作符 (Operator)：選擇 (Selection)交叉 (Crossover)變異 (Mutation) 。相關(guān)執(zhí)行過程如圖3所示：</p><p>　　2．2 種群初始化和計算適應(yīng)度</p><p>　　2．2．1 種群初始化<

38、/p><p>　　以遍歷城市的次序排列進(jìn)行編碼。如碼串1 2 3 4 5 6 7 8表示自城市l(wèi)開始，依次經(jīng)城市2，3，4，5，6，7，8，最后返回城市1的遍歷路徑。顯然，這是一種針對TSP問題的最自然的編碼方式。</p><p>　　2．2．2 計算適應(yīng)度</p><p>　　遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。此處適

39、應(yīng)度函數(shù)取路徑長度的倒數(shù)，即： </p><p><b>　　（2）</b></p><p><b>　　2．3 遺傳算子</b></p><p>　　遺傳算子包括：選擇算子、交叉算子、變異算子三種算子。</p><p>　　2．3．1 選擇算子</p><p>　　開始

40、，我們用隨機方法產(chǎn)生初始解群。隨著遺傳算法的執(zhí)行，我們保留M個較優(yōu)的個體作為樣本群體，采用輪盤賭選擇算法。</p><p>　　輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個體的適應(yīng)度為，則個體被選中遺傳到下一代群體的概率為：</p><p><b>　?。?）</b></p><p

41、>　　2．3．2 交叉算子</p><p>　　旅行商問題對交叉算子的設(shè)計要求是：對任意兩條巡回路線進(jìn)行交叉操作之后，都能夠得到另外兩條新的并且具有實際意義的巡回路線。</p><p>　　旅行商問題中常用的交叉算子包括：常規(guī)單點交叉或多點交叉、部分影射交叉、順序交叉、循環(huán)交叉和邊重組交叉。交叉運算是指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成

42、兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。此處采用循環(huán)交叉(Cycle Crossover，簡稱CX)，CX是由Oliver等提出的一種交叉操作方法。其基本思想是：任意兩條巡回路線都可能組成一些互不相交的循環(huán)回路，相互交換其中一個循環(huán)回路的基因就有可能產(chǎn)生新的巡回路線。</p><p>　　2．3．3 變異算子</p><

43、p>　　所謂變異運算，是指依據(jù)變異概率 Pm 將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。此處采用插入變異：若染色體1 2 3 4 5，變異點為2，插入點為4，則變異后染色體為1 3 4 2 5，新染色體繼承了舊染色體大部分基因。</p

44、><p>　　2．3．4 終止判斷</p><p>　　若終止條件（①最優(yōu)個體保持20代不變；②＝；③群體平均適應(yīng)度與最優(yōu)個體適應(yīng)度之差小于ε，ε是任意小的正實數(shù)；只要滿足其中一條就終止）滿足，則算法終止，把種群中的最好個體譯碼，然后作為最優(yōu)解輸出，結(jié)束；否則，在進(jìn)行循環(huán)選擇，交叉，變異。</p><p>　　3 MATLAB簡介與特點</p><

45、;p>　　3．1 MATLAB簡介</p><p>　　MATLAB由Math works公司開發(fā)，是一種用于工程計算的高性能語言，它主要包括兩大內(nèi)容：核心函數(shù)和工具箱。幾百個核心函數(shù)的MATLAB數(shù)學(xué)運算的基礎(chǔ)功能的基礎(chǔ)，功能愈來愈強大的工具箱是MATLAB深入應(yīng)用到各個具體工程領(lǐng)域的利器。MATLAB編程代碼很接近數(shù)學(xué)推導(dǎo)格式，簡潔直觀，更符合人們的思維習(xí)慣，所以編程及其方便，被稱為“草稿紙”式的編程

46、工具。MATLAB的典型應(yīng)用包括一下幾個方面：數(shù)學(xué)計算、算法開發(fā)、建模及仿真、數(shù)據(jù)分析及可視化、科學(xué)及工程繪圖、應(yīng)用開發(fā)（包括圖形界面）。</p><p>　　3．2 MATLAB的特點</p><p>　　MATLAB將計算、可視化和編程功能集成于非常易于使用的環(huán)境中，是一個交互式的、以矩陣計算為基礎(chǔ)的科學(xué)和工程計算軟件。MATLAB特點可以簡潔概括如下：</p><

47、;p><b>　　編程效果高</b></p><p>　　與Fortran、C語言相比，MATLAB更接近于人們通常進(jìn)行計算的思維方式，用MATLAB編程猶如書寫數(shù)學(xué)公式，編程時間和程序量會大大減少。</p><p><b>　　計算功能強</b></p><p>　　MATLAB以不必指定維數(shù)的矩陣和數(shù)組作為主要的

48、運算對象，矩陣、數(shù)組和向量的計算功能特別強，庫函數(shù)非常豐富，適用于科學(xué)和工程計算。</p><p><b>　　使用簡便</b></p><p>　　MATLAB語言靈活、方便，集成環(huán)境將編譯、鏈接、執(zhí)行融為一體，可以在統(tǒng)一窗口上排除書寫、語法錯誤，加快了用戶編寫、修改、調(diào)試程序的速度。同時計算結(jié)果也用人們十分實習(xí)的數(shù)學(xué)符號表示，即使是只具有初步計算機知識的人也可以很

49、快掌握他的基本功能。</p><p><b>　　易于擴充</b></p><p>　　用戶根據(jù)需要建立文件和庫函數(shù)一樣可以被調(diào)用，從而提高了使用效率，擴充了計算功能。MATLAB還可以與Fortran、C語言子程序混合編程。</p><p>　　MATLAB有強大的圖形繪制功能</p><p>　　MATLAB作為一個

50、強大的繪圖工具，有很強的繪圖功能，不僅可以繪制普通函數(shù)的二維、三維甚至四維圖形，而且還可以繪制專業(yè)圖像如直方圖、餅圖等等。還可以進(jìn)行適當(dāng)?shù)膱D形處理，給圖形加入聲音效果，以及創(chuàng)建圖形用戶界面等。</p><p>　　4 用MATLAB求解CSTP問題</p><p>　　4．1 種群初始化</p><p>　　城市規(guī)模為31，初始化種群即要生成一個31列N行的矩陣

51、，每一行代表一條路徑，若某一行為[2，4，16，5，6，11，23，19，17，3，18，22，21，20，24，25，26，28，27，30，31，29，1，15，14，12，13，7，10，9，8]，則代表2—4—16—5—6—11—23—19—17—3—18—22—21—20—24—25—26—28—27—30—31—29—1—15—14—12—13—7—10—9—8，代表依次經(jīng)過各個城市的巡回路線。</p><

52、;p>　　4．2 計算適應(yīng)度　</p><p>　　遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。此處適應(yīng)度函數(shù)取路徑長度Td的倒數(shù)，即：公式（2），若一條路徑的長度為15378KM，則適應(yīng)度為=1/15738。</p><p><b>　　4．3　選擇算子</b></p><p>　　4．3．1

53、 計算選擇算子的過程</p><p>　　利用上一章介紹的的輪盤賭算法計算選擇算子，其過程如下：首先，生成路徑，得到矩陣path_cord_string，計算出path_cord_string矩陣的列數(shù)parameter_number=4；pouplation=5，根據(jù)已經(jīng)給出的路徑代價計算出每一條路徑的長度，得到矩陣fitness_value，計算出所有路徑長度的和（），對fitness_value矩陣排序得到

54、矩陣maxfitness_selection，再對計算出的每一條路徑序號進(jìn)行排序，得到矩陣，根據(jù)公式計算得到矩陣selection_probability，對矩陣selection_probability累加得到矩陣added_selection_probability=，利用隨機數(shù)函數(shù)生成1以內(nèi)的一個4行1列的矩陣日rand，在計算出矩陣range，如果矩陣rand矩陣中每一行的值屬于矩陣range矩陣中每一行的兩個值之間的范圍，此條

55、路徑被保留，作為交叉算子使用的路徑。</p><p>　　4．3．2　選擇算子計算的代碼實現(xiàn)</p><p>　　選擇算子實現(xiàn)代碼如下：</p><p>　　function [ max_fitness_temp_position , path_code_string , maxfitness_selection ,istate ] = SGA__TSP_roule

56、ttewheel_selection( path_code_string , fitness_value )</p><p>　　istate = 0;</p><p>　　if( size(path_code_string,1) ~= length(fitness_value) )</p><p>　　maxfitness_selection = NaN

57、;</p><p>　　max_fitness_temp_position = NaN;</p><p>　　istate = 1;</p><p><b>　　end</b></p><p>　　[ population , parameter_numbers ] = size(

58、path_code_string );</p><p>　　fitness_value_temp = fitness_value;</p><p>　　for idx = population : -1 : 1</p><p>　　[ maxfitness_selection(idx),max_fitness_temp_position(idx) ] = max(

59、fitness_value_temp );</p><p>　　fitness_value_temp( max_fitness_temp_position( idx ) ) = 0 ;</p><p><b>　　end</b></p><p>　　selection_probability = fitness_value./sum(fitne

60、ss_value,2); %%計算每條路徑的長度占所有路徑長度和的比例</p><p>　　selection_probability_pointer = get_sorting_pointer( selection_probability , 'descend' );</p><p>　　selection_probability = sort(selection_pr

61、obability,2,'descend'); %%降序排列selection_probability矩陣。</p><p>　　added_selection_probability = incremental_add_array(selection_probability);</p><p>　　flag = rand(1,population); %%利用函數(shù)生成隨機

62、數(shù)矩陣range.</p><p>　　range = generate_probability_range( added_selection_probability );</p><p>　　temp_path = NaN*zeros( population , parameter_numbers );</p><p>　　location = NaN*zero

63、s( 1,population);</p><p>　　%%如果矩陣rand矩陣中每一行的值屬于矩陣range矩陣中每一行的兩個值之間的范圍，此條路徑被保留，作為交叉算子使用的路徑。</p><p>　　for idx = 1 : 1 : population</p><p>　　for jdx = 1 : 1 : population</p><

64、;p>　　if( flag(idx) > range(jdx,1) & flag(idx) < range(jdx,2))</p><p>　　location(idx) = selection_probability_pointer(jdx);</p><p><b>　　break;</b></p><p><

65、;b>　　end</b></p><p><b>　　end</b></p><p>　　temp_path(idx,:) = path_code_string(location(idx),:);</p><p><b>　　end</b></p><p>　　path_code_

66、string = temp_path;</p><p>　　function [ array_pointer ] = get_sorting_pointer( array , sort_type )</p><p>　　pointer(1,:) = array;</p><p>　　pointer(2,:) = 1 : 1: length(array);</p

67、><p>　　array = sort( array , 2 , sort_type );</p><p>　　for idx = 1 : 1 : length(array)</p><p>　　[location] = SGA__where_is( array(idx) , pointer(1,:) );</p><p>　　array_poi

68、nter( idx ) = location(2);</p><p><b>　　end</b></p><p>　　function [ array ] = incremental_add_array ( array )</p><p>　　for idx = 1 : 1 : (length(array)-1)</p><

69、p>　　array( idx + 1 ) = array( idx ) + array( idx + 1 );</p><p><b>　　end</b></p><p>　　function [ range ] = generate_probability_range( sorted_probability_array )</p><p&g

70、t;　　count = 0 ;</p><p>　　for idx = 1 : 1 : length(sorted_probability_array)</p><p>　　range( idx, 1 ) = count ;</p><p>　　range( idx, 2 ) = sorted_probability_array(idx) ;</p>

71、<p>　　count = sorted_probability_array(idx);</p><p><b>　　end</b></p><p>　　最終求出path_code_string矩陣，此矩陣就是選擇算子求得的路徑，作為交叉算子使用的路徑。</p><p><b>　　4．4 交叉算子</b>&l

72、t;/p><p>　　4．4．1 交叉概率的選擇</p><p>　　種群中參加交叉運算個體的比例，如果種群規(guī)模為1000，交叉概率為0.2，則參加交叉運算元素個數(shù)為200個。交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。不同交叉概

73、率環(huán)路長度的比較如圖4所示。</p><p>　　4．4．2 交叉算法實現(xiàn)</p><p>　　以一個簡單例子交實現(xiàn)交叉算法，任意選擇兩條路徑為例，這兩條路徑分別是，，從1這一點開始，在A中選擇1，找到B中1號位置對應(yīng)的值為2，找到A中2對的位置，再到B中找到3號位置的值為1，因為1已經(jīng)交叉算過了，所以將與的值交換，得到新的序列和，給下一步變異算法作為變異算法使用的路徑。整個過程如圖5所

74、示。</p><p>　　圖5交叉算法實現(xiàn)的過程</p><p><b>　　4．5 變異算子</b></p><p>　　4．5．1 變異概率的選擇</p><p>　　種群中參加變異運算個體的比例，如果種群規(guī)模為1000，交叉概率為0.04，則參加交叉運算元素個數(shù)為40個。變異操作是對種群模式的擾動，有利于增加種

75、群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。</p><p>　　4．5．2 變異算法實現(xiàn)</p><p>　　此處采用插入變異，整個過程如圖6所示：</p><p>　　圖6變異算法實現(xiàn)的過程</p><p><b>　　4．6 路徑輸出</b></p>

76、<p>　　MATLAB代碼實現(xiàn)如下：</p><p>　　fclose('all');</p><p><b>　　figure</b></p><p><b>　　hold on</b></p><p><b>　　grid off</b>&l

77、t;/p><p>　　%%從文件中讀取數(shù)據(jù)</p><p>　　fid1 = fopen('N2TSP.txt' , 'r' );</p><p>　　fid2 = fopen('OUTPUT_best_TSP_path.txt' , 'r' );</p><p>　　dot =

78、 fscanf( fid2 , '%g' );</p><p>　　TEMP = fscanf( fid1 , '%g' );</p><p>　　n=size(TEMP,1)/2;</p><p>　　C=zeros(n,2);</p><p><b>　　count=1;</b><

79、;/p><p>　　for i=1:n </p><p>　　C(i,1)=TEMP(count); C(i,2)=TEMP(count+1); count=count+2; </p><p><b>　　End</b></p><p>　　N=length(dot);</p><p>　　sca

80、tter(C(:,1),C(:,2),'filled');</p><p><b>　　hold on</b></p><p>　　plot([C(dot(1),1),C(dot(N),1)],[C(dot(1),2),C(dot(N),2)])</p><p><b>　　hold on</b></

81、p><p>　　for ii=2:N</p><p>　　plot([C(dot(ii-1),1),C(dot(ii),1)],[C(dot(ii-1),2),C(dot(ii),2)]); %%打印圖形</p><p><b>　　end</b></p><p><b>　　hold on</b>&l

82、t;/p><p><b>　　5 實驗結(jié)論及分析</b></p><p><b>　　5．1 實驗結(jié)論</b></p><p>　　進(jìn)化代數(shù)Generation=100，種群規(guī)模Population=500 交叉概率Pc=0.6 變異概率Pm=0.1。得到最大路徑，最小路徑，平均路徑如圖7所示：</p><

83、;p><b>　　圖7 進(jìn)化過程</b></p><p>　　得到較有解與最優(yōu)解路徑之間的比較如圖8所示：</p><p>　　圖8最優(yōu)解與次優(yōu)解比較</p><p>　　最終求得CTSP問題的最優(yōu)路徑為：</p><p>　?。?1 福州—22 臺北—18 杭州—3 上海—17 南京—19 合肥—23 鄭州—11

84、 西安—6 太原—5 石家莊—16 濟南—4 天津—2 北京—8 沈陽—9 長春—10哈爾濱—7 呼和浩特—13 銀川—12 蘭州—14 西寧—15 烏魯木齊—1 拉薩—29 成都—31 昆明—30 貴陽—27 南寧—28 海口—26 廣州—25 長沙—24 武漢—20 南昌）獲得結(jié)果的總路程為15378km，這也是目前求得CTSP問題的最短路徑。</p><p>　　5．2 需要進(jìn)一步解決的問題</p&

85、gt;<p>　?。?）該策略對于TSPLIB中其它問題的可行性。</p><p>　?。?）遺傳算法其它改進(jìn)策略免疫遺傳算法、并行遺傳算法、小生境遺傳算法、單親遺傳算法、混合遺傳算法等。</p><p>　?。?）與其他智能算法結(jié)合蟻群算法、模擬退火、神經(jīng)網(wǎng)絡(luò)等與遺傳算法的對比和結(jié)合。</p><p>　?。?）遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用。</

86、p><p><b>　　致 謝</b></p><p>　　首先，感謝zz老師，這篇論文的每個實現(xiàn)環(huán)節(jié)和每個數(shù)據(jù)，都離不開您的細(xì)心指導(dǎo)。而您細(xì)心的講解和對我們的指導(dǎo)，幫助我能夠很快的理解這個設(shè)計題目，在短時間內(nèi)做出這樣的結(jié)果。您嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣；你循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪。</p><p>

87、;　　其次，感謝我們同組的同學(xué)，在這次畢業(yè)設(shè)計過程中，他們給予了我很多幫助，無論在題目實現(xiàn)還是在論文寫作階段，在他們身上也學(xué)到了很多東西。</p><p>　　在論文即將完成之際，我的心情無法平靜，從開始進(jìn)入課題到論文的順利完成，老師、同學(xué)、朋友給了我無言的幫助，在這里請接受我誠摯的謝意！</p><p><b>　　主要參考文獻(xiàn)</b></p><

88、;p>　　[1] 靳蕃.神經(jīng)計算智能基礎(chǔ)[M] .成都：西南交通大學(xué)出版社.2000：300–308</p><p>　　[2] 黨建武．神經(jīng)網(wǎng)絡(luò)方法求解組合優(yōu)化問題的研究[學(xué)位論文] ．成都：西南交通大學(xué)，1996</p><p>　　[3] 周明，孫樹棟．遺傳算法原理及應(yīng)用[M] ．國防工業(yè)出版社：143–156</p><p>　　[4] 高尚等．求解旅