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

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

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

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問(wèn)題的常用求解方法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問(wèn)題的數(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問(wèn)題7</p><p>　　2．1 遺傳算法求解框架7</p><p>　　2．2 種群初始化和計(jì)算適應(yīng)度8</p>

11、<p>　　2．2．1 種群初始化8</p><p>　　2．2．2 計(jì)算適應(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簡(jiǎn)介與特點(diǎn)10</p><p>　　3．1 MATLAB簡(jiǎn)介10</p><p>　　3．2 MATLAB的特點(diǎn)10</p><p>　　4 用MATLAB求解CSTP問(wèn)題12</p><p>　　4．1 種群初始化12

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

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

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

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

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

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

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

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

21、lt;/b></p><p>　　1．2 TSP問(wèn)題的常用求解方法</p><p>　　TSP問(wèn)題求解方法目前有好幾種，下面介紹幾種求解TSP問(wèn)題比較成熟的幾種算法，遺傳算法（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)化過(guò)程，生物是通過(guò)自然選擇和有性繁殖兩個(gè)基本過(guò)程如圖1所示不斷進(jìn)化的，通過(guò)自然淘汰變異、遺傳進(jìn)化，以適應(yīng)環(huán)境的變化產(chǎn)生適合個(gè)體。人們將搜索和優(yōu)化過(guò)程模擬生物進(jìn)化過(guò)程，用搜索空間的點(diǎn)模擬自然界中的生物個(gè)體，將求解過(guò)程的目標(biāo)函數(shù)度量或生物體對(duì)環(huán)境的適應(yīng)能力，將生物的優(yōu)勝劣汰過(guò)程類比為搜索和優(yōu)化過(guò)程中好的可行取代交叉的可行解的迭代過(guò)程。</p>

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

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

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

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

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

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

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

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

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

32、城市編號(hào)及平面圖中相對(duì)坐標(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沈陽(yáng)（4196，1004）— 9長(zhǎng)春（4312 ，790）— 10哈爾濱（4386，570）— 11西安（3007，1970）

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

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

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

36、<p><b>　　圖2最優(yōu)路徑圖</b></p><p>　　2 用遺傳算法SGA求解CTSP問(wèn)題</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ù)相對(duì)應(yīng),父輩個(gè)體 ( Individual ) 對(duì)子代的貢獻(xiàn)與適應(yīng)性函數(shù)成正比。它通常使用3種操作符 (Operator)：選擇 (Selection)交叉 (Crossover)變異 (Mutation) 。相關(guān)執(zhí)行過(guò)程如圖3所示：</p><p>　　2．2 種群初始化和計(jì)算適應(yīng)度</p><p>　　2．2．1 種群初始化<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、路徑被保留，作為交叉算子使用的路徑。</p><p>　　4．3．2　選擇算子計(jì)算的代碼實(shí)現(xiàn)</p><p>　　選擇算子實(shí)現(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); %%計(jì)算每條路徑的長(zhǎng)度占所有路徑長(zhǎng)度和的比例</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ù)生成隨機(jī)

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矩陣中每一行的兩個(gè)值之間的范圍，此條路徑被保留，作為交叉算子使用的路徑。</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>　　種群中參加交叉運(yùn)算個(gè)體的比例，如果種群規(guī)模為1000，交叉概率為0.2，則參加交叉運(yùn)算元素個(gè)數(shù)為200個(gè)。交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。不同交叉概

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

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

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

76、<p>　　MATLAB代碼實(shí)現(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 實(shí)驗(yàn)結(jié)論及分析</b></p><p><b>　　5．1 實(shí)驗(yàn)結(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)化過(guò)程</b></p><p>　　得到較有解與最優(yōu)解路徑之間的比較如圖8所示：</p><p>　　圖8最優(yōu)解與次優(yōu)解比較</p><p>　　最終求得CTSP問(wèn)題的最優(yōu)路徑為：</p><p>　?。?1 福州—22 臺(tái)北—18 杭州—3 上?！?7 南京—19 合肥—23 鄭州—11

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

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

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

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

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