遺傳算法畢業(yè)論文

1、 TOC o 1-5 h z 1_引言1 HYPERLINK l bookmark12 o Current Document 2問題描述23 某于遺傳算法TSP算法2基于遺傳算法的TSP算法總體框架2算法的詳細(xì)設(shè)計(jì)3解空間的表示方式3種群初始化4 HYPERLINK l bookmark23 o Current Document 適應(yīng)度函教4 HYPERLINK l bookmark32 o Current Document 選擇操作4 HYPERLINK l bookmark57 o Current Document 交叉操作 5 HYPERLINK l bookmark66 o Curre

2、nt Document 變異操作6 HYPERLINK l bookmark69 o Current Document 進(jìn)化逆轉(zhuǎn)操作63.3實(shí)驗(yàn)結(jié)果分析74基于模擬退火算法的TSP算法104.1、入算法的實(shí)現(xiàn)過程104.2算法流程圖10 HYPERLINK l bookmark75 o Current Document 4.3模擬退火算法的實(shí)現(xiàn)過程10 HYPERLINK l bookmark83 o Current Document 4.4實(shí)驗(yàn)結(jié)果115對(duì)兩種算法的評(píng)價(jià)145.1遺傳算法優(yōu)缺點(diǎn)14 HYPERLINK l bookmark108 o Current Document 5.2模

3、擬退火算法的優(yōu)缺點(diǎn)15 HYPERLINK l bookmark118 o Current Document 6結(jié)語15參考文獻(xiàn)17附錄：19師學(xué)院本科生畢業(yè)論文論文題目：基于遺傳算法與模擬退火算法的TSP算法求解10大城市最短旅途論文摘要：TSP問題為組合優(yōu)化中的經(jīng)典的NP完全問題.本論文以某旅行社為中 國(guó)十大旅游城市一威海制定最短旅途為例，分別利用基于遺傳算法的TSP算法與基于模擬退火算法的TSP算法求解10大城市 旅游路線問題.本論文給出了遺傳算法與模擬退火算法中各算子的 實(shí)現(xiàn)方法，并展示出求解系統(tǒng)的結(jié)構(gòu)和求解系統(tǒng)基于MATLAB的實(shí)現(xiàn) 機(jī)制.利用MATLAB軟件編程，運(yùn)行出結(jié)果，并對(duì)基

4、于遺傳算法的 TSP算法結(jié)果與基于模擬退火算法的TSP算法的結(jié)果進(jìn)行比較，描述 其優(yōu)缺點(diǎn)，并選擇最為恰當(dāng)?shù)腡SP算法，實(shí)現(xiàn)最短旅途的最優(yōu)解.關(guān)鍵詞：遺傳算法；模擬退火算法；TSP；最短路徑；Title： TSP Algorithm Based on Genetic Algorithm or Simulated Annealing Algorithm for Solving the Shortest Journey of 10 CitiesAbstract : TSP problem is a classic NP problem about combinatorial optimization

5、. This article takes a travel agency looking for the shortest trip of ten tourist cities in China Zhuhai, Xian, Hangzhou, Lhasa, Beijing, Lijiang, Kunming, Chengdu, Luoyang and Weihai for instance , and solves this problem by TSP algorithm based on genetic algorithm and simulated annealing algorithm

6、 . The article gives the implementations of every operator of genetic algorithm and simulated annealing algorithm and demonstrates the architecture and the implementation mechanism of the solving system based on MATLAB. I program and operate the results by MATLAB software , and compare the results b

7、ased on genetic algorithm and simulated annealing algorithm . And describe their advantages and disadvantages so that choose the most appropriate TSP algorithm to achieve the optimal solution for the shortest path.Keywords: genetic algorithm； simulated annealing algorithm ； TSP； the shortest pathTSP

8、問題為組合優(yōu)化中的經(jīng)典問題，已經(jīng)證明為一 NP完全問題1，即其 最壞情況下的時(shí)間復(fù)雜性隨著問題規(guī)模的擴(kuò)大，按指數(shù)方式增長(zhǎng)，到目前 為止不能找到一個(gè)多項(xiàng)式時(shí)間的有效算法.TSP問題可描述為：已知n個(gè)城市 相互之間的距離，某一旅行商從某個(gè)城市出發(fā)訪問每個(gè)城市一次且僅一次， 最后回到出發(fā)城市，如何安排才使其所走路線最短.TSP問題不僅僅是一個(gè)簡(jiǎn) 單的組合優(yōu)化問題，其他許多的NP完全問題可以歸結(jié)為TSP問題，如郵路問 題、裝配線上的螺帽問題和產(chǎn)品的生產(chǎn)安排問題等，使得TSP問題的有效求 解具有重要的意義.本文中的TSP算法主要采用遺傳算法與模擬退火算法.遺傳算法是一種進(jìn)化算法，其基本原理是仿效生物界中

9、的“物競(jìng)天擇， 適者生存”的演化法則.遺傳算法把問題參數(shù)編碼為染色體，再按照所選 擇的適應(yīng)度函數(shù)，利用迭代的方式進(jìn)行選擇、交叉、變異以及進(jìn)化逆轉(zhuǎn)等運(yùn) 算對(duì)個(gè)體進(jìn)行篩選和進(jìn)化，使適應(yīng)值大的個(gè)體被保留，適應(yīng)值小的個(gè)體被淘 汰4，新的群體繼承了上一代的信息，又優(yōu)于上一代，這樣反復(fù)循環(huán)，直至 滿足條件，最后留下來的個(gè)體集中分布在最優(yōu)解的周圍，篩選出最優(yōu)個(gè)體作 為問題的解.模擬退火算法的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般的組合 優(yōu)化問題之間的相似性5，該算法是一種優(yōu)化算法，其物理退火過程由三部 分組成，分別為：加溫過程、等溫過程、冷卻過程.其中，加溫過程對(duì)應(yīng)算 法設(shè)定初溫，等溫過程對(duì)應(yīng)算法的Me

10、tropolis6抽樣過程，冷卻過程對(duì)應(yīng)控 制參數(shù)的下降.這里能量的變化就是目標(biāo)函數(shù)，要得到的最優(yōu)解就是能量最 低態(tài)7 . Metropolis準(zhǔn)則是SA算法收斂于全局最優(yōu)解的關(guān)鍵所在， Metropolis準(zhǔn)則以一定的概率接受惡化解，這樣就使算法跳離局部最優(yōu)的陷 阱.2問題描述本案例為某旅行社為中國(guó)十大旅游城市，分別為威海，根據(jù)全程路徑最短為目的，制定最優(yōu)的旅游順序依次游玩這十個(gè)城市.這類問題就由TSP 算法來解決，尋找出一條最短遍歷這10個(gè)城市的路徑.利用google地圖找到城 市坐標(biāo)，下表為這十個(gè)城市的位置坐標(biāo)如表2-1所示.表2-1 10個(gè)城市的位置坐標(biāo)城市編號(hào)X坐標(biāo)Y坐標(biāo)城市編號(hào)X坐

11、標(biāo)Y坐標(biāo)122.31113.58626.86100.23234.37108.95724.89102.83330.29120.16830.59104.07429.6691.14934.65112.46539.95116.411037. 53122.133基于遺傳算法TSP算法3.1基于遺傳算法的TSP算法總體框架TSP問題的遺傳算法包括編碼設(shè)計(jì)、種群初始化、適應(yīng)度函數(shù)選擇、終止條 件設(shè)定、選擇操作設(shè)定、交叉操作設(shè)定以及變異操作設(shè)定和進(jìn)化逆轉(zhuǎn)操作.為簡(jiǎn) 化TSP問題的求解，假設(shè)每個(gè)城市和其它任意一個(gè)城市之間都以歐氏距離8直接 相連.遺傳算法TSP問題的流程圖如圖2-1所示.圖2-1算法流程框架圖3

12、.2算法的詳細(xì)設(shè)計(jì)解空間的表示方式遺傳算法對(duì)解空間的表示大多采用二進(jìn)制編碼形式，但是二進(jìn)制編碼方式不 適合TSP問題的解的表示，因?yàn)樗筇厥獾男扪a(bǔ)算子9來修復(fù)變化算子所產(chǎn)生 的非法路徑（即不可行路徑）.給出城市編號(hào)，用十進(jìn)制數(shù)編碼來表示解更合適， 例如：近鄰表示、次序表示和路徑表示等等.這里采用了最簡(jiǎn)單的路徑表示法. 它是最自然、最接近人類思維的表示法.因此對(duì)十大旅游城市按照威海順序依次編號(hào)為1，2, 3, 4，5, 6，7, 8, 9，10，例如，下面的路徑（閉合 的）： 512436798105 表示從城市5出發(fā)，經(jīng)過1, 2, 4, 3, 6, 7, 9, 8, 10最后回到城市5的一

13、條 路徑，可以自然地用一維數(shù)組來表示：（5, 1, 2, 4, 3, 6, 7, 9, 8, 10）10個(gè)旅游城市的TSP問題，如果將種群規(guī)模設(shè)為200,則解空間就用二維數(shù)組來 表示：Path20010.種群的規(guī)模選擇應(yīng)適當(dāng)，盲目的增大種群規(guī)模不能使算法得到改進(jìn)，反而大 大增加了計(jì)算的開銷.10個(gè)城市TSP問題，可以選擇小規(guī)模的種群（例如200）， 種群初始化時(shí)，先產(chǎn)生1，2,，10的一條規(guī)則路徑，然后在這條路徑中隨機(jī) 選兩個(gè)數(shù)，將它們交換位置，這樣做若干次（本文采用200次），保證這條路徑 變成了一條隨機(jī)的路徑.以這條隨機(jī)路徑為基礎(chǔ)，對(duì)一些隨機(jī)的位，做兩兩交換， 這樣產(chǎn)生了一個(gè)個(gè)體；同樣地產(chǎn)

14、生種群里其它的個(gè)體.適應(yīng)度函數(shù)適應(yīng)度表明個(gè)體或解的優(yōu)劣性10，不同的問題，適應(yīng)度函數(shù)的定義方式也不同，本文設(shè)kk2|Ik I Ik為一個(gè)采用整數(shù)編碼的染色體，D不同，本文設(shè)kk2|610k.k.i城市化城市化的歐氏距離， j則該個(gè)體的適應(yīng)度為11:（1）fitness =（1）羿 Dkk + i /n 1i=1即適應(yīng)度函數(shù)為恰好走遍10個(gè)城市，在回到出發(fā)城市的總距離的倒數(shù).優(yōu)化的目 標(biāo)就是選擇適應(yīng)度函數(shù)值盡可能大的染色體，適應(yīng)度函數(shù)值越大的染色體越優(yōu) 質(zhì)，反之越劣質(zhì).求得種群中所有個(gè)體的適應(yīng)值后，將適應(yīng)值最大的個(gè)體保存起 來，到演化完畢時(shí)，這個(gè)個(gè)體就是最后要求的最優(yōu)解.選擇操作選擇操作的目的是

15、為了從當(dāng)前群體中以一定的概率選擇優(yōu)良個(gè)體到新群體 中，將選擇算子作用于群體，從而使優(yōu)化的個(gè)體有機(jī)會(huì)直接遺傳到下一代或通過 配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代；個(gè)體被選中的概率與適應(yīng)度值有關(guān)，適 應(yīng)度值越大，被選中的概率也就越大12，而適應(yīng)度值越大的染色體越優(yōu)質(zhì).本案 例選擇輪盤賭法，即基于適應(yīng)度比例的選擇策略，個(gè)體i被選中的概率為：(2)p =(2)藝FjJ=1其中，F(xiàn)為個(gè)體，的適應(yīng)度值；N為種群個(gè)體數(shù)目.交叉操作交叉操作是遺傳算法中最主要的遺傳操作，通過交叉操作可以得到新一代個(gè)體，新個(gè)體結(jié)合了其父輩個(gè)體的特性，交叉體現(xiàn)了信息交換的思想.利用不同映射雜交，確定交叉操作的父代，將父代樣本兩兩分組

16、，每組重復(fù)以下過程:(1)產(chǎn)生兩個(gè)1，10區(qū)間的隨機(jī)整數(shù)(1)產(chǎn)生兩個(gè)1，10區(qū)間的隨機(jī)整數(shù)r1和r2，確定兩個(gè)位置，對(duì)兩個(gè)位置的中間數(shù)據(jù)進(jìn)行交叉，10交叉為:10(2)交叉后，1010的中間數(shù)據(jù)進(jìn)行交叉，10交叉為:10(2)交叉后，1010對(duì)同一個(gè)個(gè)體中有重復(fù)的城市編號(hào)，不重復(fù)的數(shù)字保留，有沖突的數(shù)字(帶*的位置)采用部分映射的方法消除沖突，即利用中間段的對(duì)應(yīng)關(guān)突的數(shù)字(帶*的位置)采用部分映射的方法消除沖突，即利用中間段的對(duì)應(yīng)關(guān)系進(jìn)行映射.結(jié)果為:6 7 1010 5交叉是希望不同的個(gè)體在產(chǎn)生下一代時(shí)，能夠結(jié)合各自的優(yōu)勢(shì)基因，產(chǎn)生更 好質(zhì)量的下一代.變異操作變異可以看作是外界對(duì)種群的影響

17、.變異是為了引入新的因素，希望個(gè)體在 外界的作用下，能夠?qū)崿F(xiàn)自我優(yōu)化，生好的基因.將變異算子作用于群體.即是對(duì) 群體中的個(gè)體串的某些基因位置上的基因值作變動(dòng).變異算子采用了簡(jiǎn)單的倒序 變換，以10城市為例，隨機(jī)的產(chǎn)生兩個(gè)小于10的整數(shù)，對(duì)某個(gè)個(gè)體進(jìn)行分割， 假設(shè),二4，匕=7，將分割段倒序并放回原來的位置即可，如下數(shù)組所示：512 | 4 | 36 |7 | 9810得到的新解為：512 | 7 36 4 9810由于這種變異算子仍能保持個(gè)體中的路徑片段，即倒序前后這個(gè)切割段的路 徑是一樣的，只是兩端點(diǎn)與整個(gè)路徑的連接顛倒了，這使得變異不是漫無邊際， 而是有所取舍的.這種簡(jiǎn)單反序可以保證后代仍

18、然是一條合法途徑.進(jìn)化逆轉(zhuǎn)操作為了改善遺傳算法的局部搜索能力，在選擇、交叉、變異之后引進(jìn)連續(xù)多次 的進(jìn)化逆轉(zhuǎn)操作，這里的“進(jìn)化”是指逆轉(zhuǎn)算子的單方向性13，即只有經(jīng)逆轉(zhuǎn) 后，適應(yīng)度值有所提高的才接受下來，否則逆轉(zhuǎn)無效.產(chǎn)生兩個(gè)1，10區(qū)間的隨機(jī)整數(shù)r1和2，確定兩個(gè)位置，將其對(duì)換位置例如,二4，r=75 1 24 3 6 7 9 8 10進(jìn)化逆轉(zhuǎn)后為：5 1 27 3 6 4 9 8 10對(duì)每個(gè)個(gè)體進(jìn)行交叉變異，然后代入適應(yīng)度函數(shù)進(jìn)行評(píng)估，X選擇出適應(yīng)值 大的個(gè)體進(jìn)行下一代交叉和變異以及進(jìn)化逆轉(zhuǎn)操作循環(huán)操作：判斷是否滿足設(shè)定 的最大遺傳代數(shù)MAXGEN14，不滿足則跳入適應(yīng)度值計(jì)算；否則結(jié)束遺

19、傳操作.1-10的十個(gè)數(shù)字按順序?yàn)橥５木幪?hào).利用各城市坐標(biāo)構(gòu)成的10 2的矩陣及初始化隨機(jī)值和DrawPath函數(shù)畫出閉合路徑圖，為優(yōu)化前的隨機(jī) 路線軌跡圖，如圖3-1所示：圖3-1隨機(jī)路線軌跡圖圖中三角標(biāo)注的數(shù)字6代表起點(diǎn)，依次按照箭頭方向遍歷，最終再次回到起 點(diǎn)6.初始種群中的一個(gè)隨機(jī)值：637851249106總距離：165.2494對(duì)照1-10數(shù)字編號(hào)所代表的的城市，隨機(jī)路線為：一一一一一一一一威海一.優(yōu)化后的最優(yōu)路線圖如圖3-2所示:圖3-2最優(yōu)路線圖最優(yōu)解：467131059284總距離：77.1532即最優(yōu)路線如下所示：一一一一一威海一一一一一此遺傳算法在解決TSP問題過程中的

20、優(yōu)化迭代過程如下圖3-3所示:圖3-3優(yōu)化過程其中橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)為優(yōu)化過程中路線長(zhǎng)度.由該優(yōu)化過程圖 可知，優(yōu)化前后路徑長(zhǎng)度有了很大的改進(jìn)，20代以后路徑長(zhǎng)度基本上已經(jīng)保持 不變了，可以認(rèn)為是最優(yōu)解了.總距離由原來的165.2494變?yōu)?7.1532，降低為 原來的46.69%，表明利用遺傳算法解決TSP問題可以起到較好的作用.4基于模擬退火算法的TSP算法4.1 SA算法的實(shí)現(xiàn)過程4.2算法流程圖4.3模擬退火算法的實(shí)現(xiàn)過程控制參數(shù)的設(shè)置需要設(shè)置的主要控制參數(shù)有降溫速率q、取初始溫度九足夠大，令T二個(gè) 任取初始解S，確定每個(gè)t時(shí)的迭代次數(shù)，即Metropolis鏈長(zhǎng)L，如圖表4-

21、1 所示.表4-1參數(shù)設(shè)定降溫速率q初始溫度T0結(jié)束溫度Tend鏈長(zhǎng)L0.910000.001500初始解對(duì)于10個(gè)城市的TSP問題，得到的解為1n 一個(gè)排序，其中每個(gè)數(shù)字為對(duì) 應(yīng)城市的編號(hào)，10個(gè)城市的TSP問題1，2，3, 4，5，6，7，8，9，10，則|1|2|3|4|5|6|7|8|9|10就為一個(gè)合法解，采用隨機(jī)排列的方法產(chǎn)生一個(gè)初始解 S1.解變換生成新解通過對(duì)當(dāng)前解S1進(jìn)行變換，產(chǎn)生新路徑的數(shù)組即新解，這里采用的變換是產(chǎn) 生隨機(jī)數(shù)的方法來產(chǎn)生將要交換的兩個(gè)城市，用二鄰域變換法15產(chǎn)生新的路徑， 即新的可行解S2.例如n=10時(shí)，產(chǎn)生兩個(gè)1，10圍的隨機(jī)整數(shù)二和Y2確定兩個(gè) 位置

22、，將其對(duì)換位置，如r =4，七二7512 | 43679810得到的新解為：512 73649810Metropolis 準(zhǔn)則若路徑長(zhǎng)度函數(shù)為f (S)，則當(dāng)前解的路徑為f (S1)，新解的路徑為f (S2)，(3)路徑差為 df - f (S ) - f (S ) 16，則 Metropolis 準(zhǔn)則為17:(3)P exp( - T)若df rand 18，也接受S作為新的當(dāng)前解，S = S ;否則保留當(dāng)前解S .2121降溫利用降溫速率q進(jìn)行降溫，即T=qT，則T小于結(jié)束溫度，則停止迭代輸出 當(dāng)前解S1為最優(yōu)解，結(jié)束程序，否則按衰減函數(shù)衰減T后逐漸降低控制溫度，重 復(fù)Metropolis

23、過程，繼續(xù)迭代，直至滿足結(jié)束準(zhǔn)則，求出最優(yōu)解.4.4實(shí)驗(yàn)結(jié)果利用各城市坐標(biāo)構(gòu)成的10 2的矩陣及初始化隨機(jī)值和DrawPath函數(shù)分別 畫出優(yōu)化前的隨機(jī)路徑軌跡圖與優(yōu)化后的最優(yōu)閉合路徑圖，以及優(yōu)化過程圖.并 利用計(jì)時(shí)器記錄了運(yùn)行結(jié)果所花費(fèi)的時(shí)間.為優(yōu)化前的隨機(jī)路線軌跡圖，如圖4-2所示.File Edit View n&ert Tools Desktop Window Helpk 冬公鴛口ns io圖4-2隨機(jī)路線軌跡圖初始種群中的一個(gè)隨機(jī)值:817436102958總距離：149.0742優(yōu)化后的最優(yōu)路線軌跡圖如圖4-3所示.圖4-3最優(yōu)路線軌跡圖最優(yōu)解：928467131059總距離：77

24、.1532即最優(yōu)路線如下所示：一一一一一一一威海一一本次運(yùn)行的時(shí)間如下所示：Elapsed time is 12.232553 seconds.優(yōu)化過程如圖4-4所示:圖4-4優(yōu)化過程由圖4-4可以看出，優(yōu)化前后的路徑長(zhǎng)度得到很大的改進(jìn)，由優(yōu)化前的 149.0742變?yōu)?7.1532，變?yōu)樵瓉淼?1.75%，50代以后路徑長(zhǎng)度基本上已經(jīng)保 持不變了，可以認(rèn)為是最優(yōu)解了.5對(duì)兩種算法的評(píng)價(jià)5.1遺傳算法優(yōu)缺點(diǎn)遺傳算法優(yōu)點(diǎn):對(duì)可行解表示的廣泛性；群體搜索特性；不需要輔助信息；在啟發(fā)式隨機(jī)搜索特性；遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)是不連續(xù)的，非規(guī)則的或有噪音的情況下，

25、也能以很大的概率找到全局最優(yōu)解；遺傳算法具有固有的并行性和并行計(jì)算能力；遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合.遺傳算法缺點(diǎn)：編碼不規(guī)則或編碼存在表示的不規(guī)則性；單一的遺傳算法編碼不能全面的將優(yōu)化問題的約束表示出來；遺傳算法通常的效率比比其他傳統(tǒng)的優(yōu)化方法低；遺傳算法容易出現(xiàn)過早收斂；遺傳算法對(duì)算法的精度，可信度，計(jì)算復(fù)雜性等方面，還沒有有效的定量 分析方法.5.2模擬退火算法的優(yōu)缺點(diǎn)模擬退火法優(yōu)點(diǎn)：它能夠處理具有任意程度的非線性、不連續(xù)性、隨機(jī)性的目標(biāo)函數(shù)；目標(biāo)函數(shù)可以具有任意的邊界條件和約束；比其他線性優(yōu)化方法，SA的編程工作量小，且易于實(shí)現(xiàn)；統(tǒng)計(jì)上可以保證找到全局最優(yōu)解.模擬退火算法缺

26、點(diǎn)：找到最優(yōu)解需要耗費(fèi)非常多的時(shí)間；相對(duì)于其他一些技術(shù)對(duì)某一個(gè)具體問題的求解需要更困難的參數(shù)調(diào)整；使用不當(dāng)致使降溫過快，導(dǎo)致模擬退火變?yōu)榱四M淬火(SQ)，而SQ是無 法從統(tǒng)計(jì)學(xué)上保證找到最優(yōu)解的.6結(jié)語遺傳算法利用自然界的“物競(jìng)天擇、適者生存”的演化法則，把問題參數(shù)編 碼為染色體，再利用迭代的方式進(jìn)行選擇、交叉以及變異等運(yùn)算來交換種群中染 色體的信息，最終生成符合優(yōu)化目標(biāo)的染色體.實(shí)踐證明，遺傳算法在搜索優(yōu)秀 解的過程中模擬生物遺傳，實(shí)現(xiàn)優(yōu)中選優(yōu)的過程，在解空間中快速收斂到優(yōu)秀解. 遺傳算法對(duì)于解決TSP問題等組合優(yōu)化問題具有較好的尋優(yōu)性能.模擬退火算法 是利用自適應(yīng)啟發(fā)式概率性搜索的算法，

27、可以用以求解不同的非線性問題，對(duì)不 可微甚至不連續(xù)的函數(shù)優(yōu)化，能以較大的概率求得全局最優(yōu)解，并且能處理不同 類型的優(yōu)化設(shè)計(jì)變量（離散的，連續(xù)的，混合型的），不需要任何的輔助信息， 對(duì)目標(biāo)函數(shù)和約束函數(shù)沒有任何要求.利用Metropolis算法適當(dāng)?shù)乜刂茰囟鹊?下降過程，在優(yōu)化問題中具有很強(qiáng)的競(jìng)爭(zhēng)力，但是其優(yōu)化過程效率略低于遺傳算 法.因此，解空間較小的情況下，遺傳算法與模擬退火算法均可采用，但是解空 間較大時(shí)，考慮結(jié)果運(yùn)行時(shí)間，應(yīng)采用遺傳算法.參考文獻(xiàn)畢曉君.信息智能處理技術(shù)M.：電子工業(yè).2010.儲(chǔ)理才.基于MATLAB的遺傳算法程序設(shè)計(jì)及TSP問題求解J.集美大學(xué)學(xué)報(bào)：2001， 6 （

28、01）： 14-19代桂平，王勇，侯亞榮.基于遺傳算法的TSP問題求解算法及其系統(tǒng)J.微計(jì)算機(jī)信息，2010（04）： 15-16，19Negnevistsky，M.顧力栩，晉惠譯.人工智能智能系統(tǒng)指南M.:機(jī)械工業(yè).2010.任春玉.基于混合遺傳算法的TSP問題優(yōu)化研究J.商業(yè)大學(xué)學(xué)報(bào).2007.Michalewicz Z. Genetic Algorithms +Data Structure=Evolution Programs. Springer-Verlag， Berlin. 2011易敬，王平，哲.基于遺傳算法的TSP問題研究J.信息技術(shù)，2006, 30（7）： 110-112.鄧

29、輝文.離散數(shù)學(xué)M.：清華大學(xué).2006.雁兵，付顯.基于遺傳算法的TSP問題求解與仿真J.電光與控制.2007.春霞，王蕊.基于遺傳算法求解TSP問題的算法設(shè)計(jì)汀.工學(xué)院學(xué)報(bào).2007.阿奇.MATLAB實(shí)用教程M.：電子工業(yè).2004.飛，白艷萍.用遺傳算法求解旅行商問題J.中北大學(xué)學(xué)報(bào).2007.翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解TSP問題J.師學(xué)院學(xué) 報(bào).2009.Merz P.A comparison of recombination operators forthe traveling salesman problemA.Proceedings of the Genetic an

30、d Evolutionary Conference.2007周濤.基于改進(jìn)遺傳算法的TSP問題研究J.微電子學(xué)與計(jì)算機(jī)，2006, 23(10)： 104-107.Jung S, Moon B R. Toward Minimal Restriction of Genetic Encoding and Crossovers for the Two-Dimensional Euclidean TSP J.IEEE Transactions on Evolutionary Computation, 2011, 6 ( 12) :557565Tsai Cheng-Fa , Tsai Chun-Wei

31、, Yang Tzer . A Modified Mul tiple-Searching Method to Genetic Algorithms for Solving Travel ing Salesman ProblemJ.IEEE Transactions on Systems , Man and Cybernetics , 2011 , 3 (10) :612Write A H. Genetic Algorithms for Real Parameter Optimization. FoundationofGeneticAlgorithms.Sanmateo, GA.2010：205

32、-218附錄:遺傳算法的TSP方法代碼：1種群初始化函數(shù)InitPop的代碼：%初始化種群%輸入：% NIND :種群大小% N：個(gè)體染色體長(zhǎng)度(這里為城市的個(gè)數(shù))%輸出：%初始種群function Chrom=InitPop(NIND,N)Chrom=zeros(NIND,N);% 用于存儲(chǔ)種群for i=1:NINDChrom(i,:)=randperm(N);%隨機(jī)生成初始種群 end2種群個(gè)體的適應(yīng)度函數(shù)Fitness的代碼:%適配值函數(shù)%輸入：%個(gè)體的長(zhǎng)度(TSP的距離)%輸出：%個(gè)體的適應(yīng)度值function FitnV=Fitness(len) FitnV=1./len;3選擇操

33、作函數(shù)的Select的代碼：%選擇操作%輸入%Chrom 種群%FitnV適應(yīng)度值%GGAP :代溝%輸出%SelCh被選擇的個(gè)體function SelCh=Select(Chrom,FitnV,GGAP)NIND=size(Chrom,1);NSel=max(floor(NIND*GGAP+.5),2);ChrIx=Sus(FitnV,NSel);SelCh=Chrom(ChrIx,：)；其中，函數(shù)Sus的代碼為：%輸入：%FitnV 個(gè)體的適應(yīng)度值%Nsel 被選擇個(gè)體的數(shù)目%輸出：%NewChrIx被選擇個(gè)體的索引號(hào)function NewChrIx = Sus(FitnV,Nsel)

34、Nind,ans = size(FitnV);cumfit = cumsum(FitnV);trials = cumfit(Nind) / Nsel * (rand + (0:NselT);Mf = cumfit(:, ones(1, Nsel);Mt = trials(:, ones(1, Nind);NewChrIx, ans = find(Mt Mf & zeros(1, Nsel); Mf(1:NindT, :) =rand %交叉概率 PcSelCh(i,:),SelCh(i+1,:)=intercross(SelCh(i,:),SelCh(i+1,:);endend%輸入：%a和b

35、為兩個(gè)待交叉的個(gè)體%輸出：%a和b為交叉后得到的兩個(gè)個(gè)體其中intercross函數(shù)代碼：function a,b=intercross(a,b)L=length(a);r1=randsrc(1,1,1:L);r2=randsrc(1,1,1:L);if r1=r2a0=a;b0=b; s=min(r1,r2)；e=max(r1,r2)；for i=s：ea1=a；b1=b；a(i)=b0(i)；b(i)=a0(i)；x=find(a=a(i)；y=find(b=b(i)；i1=x(x=i)；i2=y(y=i)；if isempty(i1)a(i1)=a1(i)；endif isempty(i

36、2)b(i2)=b1(i)；endendend5變異操作函數(shù)Mutate的代碼：%變異操作%輸入：%SelCh被選擇的個(gè)體%Pm 變異概率%輸出：% SelCh變異后的個(gè)體function SelCh=Mutate(SelCh,Pm)NSel,L=size(SelCh)；for i=1:NSelif Pm=randR=randperm(L)；SelCh(i,R(1:2)=SelCh(i,R(2:-1:1)； endend6進(jìn)化逆轉(zhuǎn)操作函數(shù)Reverse代碼：%進(jìn)化逆轉(zhuǎn)函數(shù)%輸入%SelCh被選擇的個(gè)體%D 個(gè)城市的距離矩陣%輸出%SelCh 進(jìn)化逆轉(zhuǎn)后的個(gè)體function SelCh=Rev

37、erse(SelCh,D)row,col=size(SelCh)；ObjV=PathLength(D,SelCh)； %計(jì)算路徑長(zhǎng)度 SelCh1=SelCh； for i=1:rowr1=randsrc(1,1,1:col);r2=randsrc(1,1,1:col);mininverse=min(r1 r2);maxinverse=max(r1 r2);SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:T:mininverse); end ObjV1=PathLength(D,SelCh1); %計(jì)算路徑長(zhǎng)度 index=ObjV1Ob

38、jV;SelCh(index,:)=SelCh1(index,:);7畫出所給路線的軌跡圖函數(shù)DrawPath的代碼：%畫路徑函數(shù)%輸入% Chrom 待畫路徑% X 各城市坐標(biāo)位置function DrawPath(Chrom,X)R=Chrom(1,:) Chrom(1,1); % 個(gè)隨機(jī)解(個(gè)體) figure; hold onplot(X(:,1),X(:,2),o,color,0.5,0.5,0.5)plot(X(Chrom(1,1),1),X(Chrom(1,1),2),rv,MarkerSize,20)for i=1:size(X,1)text(X(i,1)+0.05,X(i,2

39、)+0.05,num2str(i),color,1,0,0);endA=X(R,:);row=size(A,1);for i=2:rowarrowx,arrowy = dsxy2figxy(gca,A(iT:i,1),A(iT:i,2);% 坐標(biāo)轉(zhuǎn)換annotation(textarrow,arrowx,arrowy,HeadWidth,8,color,0,0,1); end hold offxlabel(橫坐標(biāo))ylabel(縱坐標(biāo))title(軌跡圖)box on8遺傳算法的主函數(shù)代碼：%遺傳算法求解TSP問題(為選擇操作從新設(shè)計(jì)后程序)%輸入：%D距離矩陣%NIND為種群個(gè)數(shù)%NIND%

40、X參數(shù)是中國(guó)10個(gè)城市的坐標(biāo)（初始給定）%MAXGEN為停止代數(shù)，遺傳到第MAXGEN代時(shí)程序停止,MAXGEN的具體取值視問題的規(guī)模和耗費(fèi) 的時(shí)間而定%m為適值淘汰加速指數(shù)，最好取為1,2,3,4,不宜太大%Pc交叉概率%Pm變異概率%輸出：%R為最短路徑%Rlength為路徑長(zhǎng)度clear clcclose allX=22.31 113.5834.37 108.9530.29 120.1629.66 91.14%生成距離矩陣%城市個(gè)數(shù)%生成距離矩陣%城市個(gè)數(shù)%種群大小%最大遺傳代數(shù)%交叉概率%變異概率%代溝 TOC o 1-5 h z %遺傳參數(shù) %種群大小%最大遺傳代數(shù)%交叉概率%變異概

41、率%代溝MAXGEN=200；1Pc=0.9；1Pm=0.05；GGAP=0.9；1%初始化種群 Chrom=InitPop（NIND,N）； %畫出隨機(jī)解的路徑圖 DrawPath（Chrom（1,：）,X） title pause（0.0001） %輸出隨機(jī)解的路徑和總距離 disp（初始種群中的一個(gè)隨機(jī)值：） OutputPath（Chrom（1,：）； Rlength=PathLength（D,Chrom（1,：）； disp（總距離：，num2str（Rlength）； disp（）%優(yōu)化 gen=0；figure；hold on；box onxlim(0,MAXGEN)title(

42、優(yōu)化過程)xlabel(代數(shù))ylabel(最優(yōu)值)ObjV=PathLength(D,Chrom); %計(jì)算路徑長(zhǎng)度 preObjV=min(ObjV);while gen,num2str(R(i);enddisp(p)計(jì)算個(gè)體路線長(zhǎng)度函數(shù)PathLength代碼：%計(jì)算各個(gè)體的路徑長(zhǎng)度%輸入：% D 兩兩城市之間的距離% Chrom個(gè)體的軌跡function len=PathLength(D,Chrom)row,col=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);for i=1:NINDp=Chrom(i,:) Chrom(i,1);i1=p(

43、1:end-1);i2=p(2:end);len(i,1)=sum(D(i1T)*col+i2);end重插入子代得到新種群的函數(shù)Reins代碼：%重插入子代的新種群%輸入：%Chrom 父代的種群%SelCh 子代種群%ObjV 父代適應(yīng)度%輸出% Chrom組合父代與子代后得到的新種群 function Chrom=Reins(Chrom,SelCh,ObjV) NIND=size(Chrom,1);NSel=size(SelCh,1);TobjV,index=sort(ObjV);Chrom=Chrom(index(1:NIND-NSel),:);SelCh;模擬退火算法的TSP方法代碼

44、：生成新解：function S2=NewAnswer(S1)%輸入% S1:當(dāng)前解%輸出% S2：新解N=length(S1);S2=S1;a=round(rand(1,2)*(NT)+1);W=S2(a(1);S2(a(1)=S2(a(2);S2(a(2)=W;Metropolis準(zhǔn)則函數(shù)function S,R=Metropolis(S1,S2,D,T)%輸入% S1：當(dāng)前解% S2:新解% D:距離矩陣(兩兩城市的之間的距離)% T:當(dāng)前溫度%輸出% S：下一個(gè)當(dāng)前解% R：下一個(gè)當(dāng)前解的路線距離%R1=PathLength(D,S1); %計(jì)算路線長(zhǎng)度N=length(S1);%得到

45、城市的個(gè)數(shù)R2=PathLength(D,S2); %計(jì)算路線長(zhǎng)度dC=R2-R1;%計(jì)算能力之差if dC=rand%以 exp(-dC/T )概率接受新路線S=S2；R=R2；else%不接受新路線S=S1；R=R1；Endfunction varargout = dsxy2figxy(varargin)if length(varargin1) = 1 & ishandle(varargin1) .& strcmp(get(varargin1,type),axes)hAx = varargin1;varargin = varargin(2:end);elsehAx = gca;end；if length(varargin) = 1pos = varargin1;elsex,y = deal(varargin:);endaxun = get(hAx,Units);set(hAx,Units,normalized);axpos = get(hAx,Position);axlim = axis(hAx);axwidth = diff(axlim(1:2);axheight = diff(axlim(3:4);if exist(x,var)varargout1 = (x - axlim(1) *