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

1、目錄1 引言 12 問題描述 23 基于遺傳算法 TSP 算法 23.1 基于遺傳算法的 TSP 算法總體框架 23.2 算法的詳細(xì)設(shè)計 33.2.1 解空間的表示方式 33.2.2 種群初始化 43.2.3適應(yīng)度函數(shù) 43.2.4選擇操作 43.2.5交叉操作 53.2.6變異操作 63.2.7 進化逆轉(zhuǎn)操作 63.3 實驗結(jié)果分析 74 基于模擬退火算法的 TSP 算法 104.1 SA 算法的實現(xiàn)過程 104.2 算法流程圖 104.3 模擬退火算法的實現(xiàn)過程 104.4 實驗結(jié)果 115 對兩種算法的評價 145.1 遺傳算法優(yōu)缺點 145.2 模擬退火算法的優(yōu)缺點 156 結(jié)語 15

2、參考文獻 17附錄： 錯 誤！未定義書簽。廊坊師范學(xué)院本科生畢業(yè)論文論文題目 ：基于遺傳算法與模擬退火算法的 TSP 算法求解 10 大城市最短旅途論文摘要：TSP問題為組合優(yōu)化中的經(jīng)典的 NP完全問題.本論文以某旅行社為中 國十大旅游城市 -珠海、西安、杭州、拉薩、北京、麗江、昆明、成 都、洛陽、威海制定最短旅途為例，分別利用基于遺傳算法的 TSP 算法與基于模擬退火算法的 TSP 算法求解 10 大城市旅游路線問題 . 本論文給出了遺傳算法與模擬退火算法中各算子的實現(xiàn)方法， 并展示 出求解系統(tǒng)的結(jié)構(gòu)和求解系統(tǒng)基于 MATLAB 的實現(xiàn)機制 利用 MATLAB 軟件編程，運行出結(jié)果，并對基于

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

4、ation This article takes a travel agency looking for the shortest trip of ten tourist cities in ChinaZhuhai， 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 algo

5、rithm 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

6、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 pathKeywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path1 引言TSP問題為組

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

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

9、算法的 Metropolis 6抽樣過程， 冷卻過程對應(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問題描述本案例為某旅行社為中國十大旅游城市，分別為珠海、西安、杭州、拉薩、 北京、麗江、昆明、成都、洛陽、威海，根據(jù)全程路徑最短為目的，制定最優(yōu)的 旅游順序依次游玩這十個城市這類問題就由TSP算法來解決，尋找出一條最短 遍歷這10個城市的路徑.利用google地圖找到城市坐標(biāo)，下表為這十個城市的位 置坐標(biāo)如表2

10、-1所示.表2-110個城市的位置坐標(biāo)城市編號X坐標(biāo)Y坐標(biāo)城市編號X坐標(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è)計、種群初始化、適應(yīng)度函數(shù)選擇、終止條 件設(shè)定、選擇操作設(shè)定、交叉操作設(shè)定以及變異操作設(shè)定和進化逆轉(zhuǎn)操作 .為簡 化TSP問題的求解，假設(shè)每個城市和其它任意一個城市之間都以歐氏距離 問直

11、 接相連.遺傳算法TSP問題的流程圖如圖2-1所示.N圖2-1算法流程框架圖3.2算法的詳細(xì)設(shè)計321解空間的表示方式遺傳算法對解空間的表示大多采用二進制編碼形式，但是二進制編碼方式不 適合TSP問題的解的表示，因為它要求特殊的修補算子9來修復(fù)變化算子所產(chǎn)生的非法路徑（即不可行路徑）.給出城市編號，用十進制數(shù)編碼來表示解更合 適，例如：近鄰表示、次序表示和路徑表示等等 .這里米用了最簡單的路徑表示 法.它是最自然、最接近人類思維的表示法.因此對十大旅游城市按照珠海、西安、 杭州、拉薩、北京、麗江、昆明、成都、洛陽、威海順序依次編號為1，2，3,4, 5, 6, 7, 8, 9，10，例如，下面

12、的路徑（閉合的）：5 1 24 36 7 9 8 10f表示從城市5出發(fā)，經(jīng)過1, 2, 4, 3, 6, 7, 9, 8, 10最后回到城市5的一條 路徑，可以自然地用一維數(shù)組來表示：（5, 1, 2, 4, 3, 6, 7, 9, 8, 10）10個旅游城市的TSP問題，如果將種群規(guī)模設(shè)為 200,則解空間就用二維數(shù)組 來表示：Path20010.322種群初始化種群的規(guī)模選擇應(yīng)適當(dāng)，盲目的增大種群規(guī)模不能使算法得到改進，反而大大增加了計算的開銷.10個城市TSP問題，可以選擇小規(guī)模的種群（例如 200）, 種群初始化時，先產(chǎn)生1, 2,，10的一條規(guī)則路徑，然后在這條路徑中隨機 選兩個數(shù)

13、，將它們交換位置，這樣做若干次（本文采用 200次），保證這條路徑 變成了一條隨機的路徑.以這條隨機路徑為基礎(chǔ)，對一些隨機的位，做兩兩交換， 這樣產(chǎn)生了一個個體；同樣地產(chǎn)生種群里其它的個體 .3.2.3 適應(yīng)度函數(shù)適應(yīng)度表明個體或解的優(yōu)劣性10，不同的問題，適應(yīng)度函數(shù)的定義方式也不同，本文設(shè)kj kzll川k6|l|k10為一個采用整數(shù)編碼的染色體，Dkkj為城市ki到城市kj的歐氏距離，貝U該個體的適應(yīng)度為11(1)fitness 二即適應(yīng)度函數(shù)為恰好走遍10個城市，在回到出發(fā)城市的總距離的倒數(shù).優(yōu)化的目 標(biāo)就是選擇適應(yīng)度函數(shù)值盡可能大的染色體，適應(yīng)度函數(shù)值越大的染色體越優(yōu) 質(zhì)，反之越劣質(zhì).

14、求得種群中所有個體的適應(yīng)值后，將適應(yīng)值最大的個體保存起 來，到演化完畢時，這個個體就是最后要求的最優(yōu)解 .3.2.4選擇操作選擇操作的目的是為了從當(dāng)前群體中以一定的概率選擇優(yōu)良個體到新群體 中，將選擇算子作用于群體，從而使優(yōu)化的個體有機會直接遺傳到下一代或通過 配對交叉產(chǎn)生新的個體再遺傳到下一代； 個體被選中的概率與適應(yīng)度值有關(guān)， 適 應(yīng)度值越大，被選中的概率也就越大12，而適應(yīng)度值越大的染色體越優(yōu)質(zhì).本案 例選擇輪盤賭法，即基于適應(yīng)度比例的選擇策略，個體 i被選中的概率為：PiFiN(2)其中，F(xiàn)為個體i的適應(yīng)度值；N為種群個體數(shù)目325交叉操作交叉操作是遺傳算法中最主要的遺傳操作， 通過交

15、叉操作可以得到新一代個 體，新個體結(jié)合了其父輩個體的特性， 交叉體現(xiàn)了信息交換的思想.利用不同映 射雜交，確定交叉操作的父代，將父代樣本兩兩分組，每組重復(fù)以下過程：(1)產(chǎn)生兩個1，10區(qū)間的隨機整數(shù)*和D，確定兩個位置，對兩個位置的中間數(shù)據(jù)進行交叉,如rr4,獷75124367981010623589417交叉為：*123589*1010*24367*1*(2)交叉后，對同一個個體中有重復(fù)的城市編號，不重復(fù)的數(shù)字保留，有沖 突的數(shù)字(帶*的位置)采用部分映射的方法消除沖突，即利用中間段的對應(yīng)關(guān) 系進行映射結(jié)果為：4 12358910 524367交叉是希望不同的個體在產(chǎn)生下一代時, 好質(zhì)量的

16、下一代6 710819能夠結(jié)合各自的優(yōu)勢基因，產(chǎn)生更326 變異操作變異可以看作是外界對種群的影響變異是為了引入新的因素，希望個體在 外界的作用下，能夠?qū)崿F(xiàn)自我優(yōu)化，生好的基因?qū)⒆儺愃阕幼饔糜谌后w即是對 群體中的個體串的某些基因位置上的基因值作變動.變異算子采用了簡單的倒序變換，以10城市為例，隨機的產(chǎn)生兩個小于10的整數(shù)，對某個個體進行分割， 假設(shè)斤=4, r2=7，將分割段倒序并放回原來的位置即可，如下數(shù)組所示：5 1 2 | 4 | 3 6 | 7 | 9 8 10得到的新解為：5 1 2 | 7 | 3 6丨4 | 9 8 10由于這種變異算子仍能保持個體中的路徑片段， 即倒序前后這個

17、切割段的路 徑是一樣的，只是兩端點與整個路徑的連接顛倒了，這使得變異不是漫無邊際， 而是有所取舍的.這種簡單反序可以保證后代仍然是一條合法途徑.3.2.7進化逆轉(zhuǎn)操作為了改善遺傳算法的局部搜索能力，在選擇、交叉、變異之后引進連續(xù)多次 的進化逆轉(zhuǎn)操作，這里的“進化”是指逆轉(zhuǎn)算子的單方向性 13，即只有經(jīng)逆轉(zhuǎn) 后，適應(yīng)度值有所提高的才接受下來，否則逆轉(zhuǎn)無效 產(chǎn)生兩個1，10區(qū)間內(nèi)的隨機整數(shù)斤和r2，確定兩個位置，將其對換位置， 例如廠4,礦刁5 1 2 | 4 | 3 6 | 7 | 9 8 10進化逆轉(zhuǎn)后為：5 1 2 | 7 | 3 6丨4 | 9 8 10對每個個體進行交叉變異，然后代入適應(yīng)

18、度函數(shù)進行評估， x選擇出適應(yīng)值 大的個體進行下一代交叉和變異以及進化逆轉(zhuǎn)操作循環(huán)操作： 判斷是否滿足設(shè)定 的最大遺傳代數(shù)MAXGEN 14，不滿足則跳入適應(yīng)度值計算；否則結(jié)束遺傳操作.3.3實驗結(jié)果分析1-10的十個數(shù)字按順序為珠海、西安、杭州、拉薩、北京、麗江、昆明、成 都、洛陽、威海的編號.利用各城市坐標(biāo)構(gòu)成的10 2的矩陣及初始化隨機值和 DrawPath函數(shù)畫出閉合路徑圖，為優(yōu)化前的隨機路線軌跡圖，如圖3-1所示：邊 Figure 1|c丨回 fl圖3-1隨機路線軌跡圖圖中三角標(biāo)注的數(shù)字6代表起點，依次按照箭頭方向遍歷，最終再次回到 起點6.初始種群中的一個隨機值：637 8 51

19、2 4 910 6總距離：165.2494對照1-10數(shù)字編號所代表的的城市，隨機路線為：麗江一 杭州一 昆明一 成都一 北京一 珠海一 西安一 拉薩一 洛陽一 威海 麗江.29優(yōu)化后的最優(yōu)路線圖如圖3-2所示:Q Figure 3File Edit View Insert Tools Desktop Window Help | n|皺鷲紗物繪銘T0|匡i|口最優(yōu)解的路徑團125120J1-363423標(biāo)坐O橫.32624圖3-2最優(yōu)路線圖最優(yōu)解:467 1 310 59 2 84總距離：77.1532即最優(yōu)路線如下所示：拉薩一 麗江一 昆明一 珠海一 杭州一 威海一 北京一 洛陽一 西安一

20、成都拉薩此遺傳算法在解決TSP問題過程中的優(yōu)化迭代過程如下圖 3-3所示:中|回圖3-3優(yōu)化過程其中橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)為優(yōu)化過程中路線長度.由該優(yōu)化過程圖可知，優(yōu)化前后路徑長度有了很大的改進，20代以后路徑長度基本上已經(jīng)保持 不變了，可以認(rèn)為是最優(yōu)解了 總距離由原來的165.2494變?yōu)?7.1532,降低為 原來的46.69%,表明利用遺傳算法解決TSP問題可以起到較好的作用.4基于模擬退火算法的TSP算法4.1 SA算法的實現(xiàn)過程4.2 算法流程圖圖4-1模擬退火算法求解流程框圖4.3模擬退火算法的實現(xiàn)過程(1) 控制參數(shù)的設(shè)置需要設(shè)置的主要控制參數(shù)有降溫速率 q、取初始溫度To足

21、夠大，令T=To，任取初始解3，確定每個T時的迭代次數(shù)，即Metropolis鏈長L,如圖表4-1所示.表4-1參數(shù)設(shè)定降溫速率q初始溫度T。結(jié)束溫度Tend鏈長L0.910000.001500(2) 初始解對于10個城市的TSP問題，得到的解為1n個排序，其中每個數(shù)字為對應(yīng)城市的編號，10個城市的TSP問題1, 2, 3, 4, 5, 6，7, 8, 9，10，則|1|2|3|4|5|6|7|8|9|1就為一個合法解，采用隨機排列的方法產(chǎn)生一個初始解S .(3) 解變換生成新解通過對當(dāng)前解進行變換，產(chǎn)生新路徑的數(shù)組即新解，這里采用的變換是產(chǎn) 生隨機數(shù)的方法來產(chǎn)生將要交換的兩個城市， 用二鄰域

22、變換法15產(chǎn)生新的路徑， 即新的可行解S2.例如n=10時，產(chǎn)生兩個1，10范圍內(nèi)的隨機整數(shù)ri和2確定 兩個位置，將其對換位置，如11=4， 2=7512 | 4 |36 | 7 | 9810得到的新解為：512 | 7 |36 | 4 | 9810(4) Metropolis 準(zhǔn)則若路徑長度函數(shù)為f(S)，則當(dāng)前解的路徑為f(SJ，新解的路徑為f(S2)，路徑差為 df = f (S,)- f (E) 16，則 Metropolis 準(zhǔn)則為17:1P 二 / df、( 3)exp(-)若df :：: 0，則接受S2作為新的當(dāng)前解，即3 =S2 ；否則計算S2的接受概率 exp(-df/T)

23、，即隨機產(chǎn)生的(0，1)區(qū)間上均勻分布的隨機數(shù)rand，若exp(-df /T rand 18,也接受S作為新的當(dāng)前解，S =S2 ；否則保留當(dāng)前解S -(5) 降溫利用降溫速率q進行降溫，即T=qT，則T小于結(jié)束溫度，則停止迭代輸出 當(dāng)前解S,為最優(yōu)解，結(jié)束程序，否則按衰減函數(shù)衰減T后逐漸降低控制溫度，重 復(fù)Metropolis過程，繼續(xù)迭代，直至滿足結(jié)束準(zhǔn)則，求出最優(yōu)解.4.4實驗結(jié)果利用各城市坐標(biāo)構(gòu)成的10 2的矩陣及初始化隨機值和DrawPath函數(shù)分別畫出優(yōu)化前的隨機路徑軌跡圖與優(yōu)化后的最優(yōu)閉合路徑圖，以及優(yōu)化過程 圖并利用計時器記錄了運行結(jié)果所花費的時間.為優(yōu)化前的隨機路線軌跡圖，

24、如圖4-2所示.Q Fig聽 1File Edit View Insert Tools Desktop Window Help0日日 b 聘搖屈 s a圖4-2隨機路線軌跡圖初始種群中的一個隨機值：81 7 4 36 10 2 9 5 8總距離：149.0742優(yōu)化后的最優(yōu)路線軌跡圖如圖4-3所示.圖4-3最優(yōu)路線軌跡圖最優(yōu)解：928 4 67 13 10 5 9總距離：77.1532即最優(yōu)路線如下所示：洛陽一 西安一 成都一 拉薩一 麗江一 昆明一 珠海一 杭州一 威海一 北京 洛陽本次運行的時間如下所示：Elapsed time is 12.232553 sec on ds.優(yōu)化過程如圖4

25、-4所示:圖4-4優(yōu)化過程由圖4-4可以看出，優(yōu)化前后的路徑長度得到很大的改進，由優(yōu)化前的149.0742變?yōu)?7.1532,變?yōu)樵瓉淼?1.75%, 50代以后路徑長度基本上已經(jīng)保持 不變了，可以認(rèn)為是最優(yōu)解了 .5對兩種算法的評價 5.1遺傳算法優(yōu)缺點遺傳算法優(yōu)點：（1）對可行解表示的廣泛性;（2）群體搜索特性；（3）不需要輔助信息；（4）內(nèi)在啟發(fā)式隨機搜索特性；（5）遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù) 是不連續(xù)的，非規(guī)則的或有噪音的情況下，也能以很大的概率找到全局最優(yōu)解；（6）遺傳算法具有固有的并行性和并行計算能力；（7）遺傳算法具有可擴展性，易于同別的技術(shù)

26、混合遺傳算法缺點：（1）編碼不規(guī)則或編碼存在表示的不規(guī)則性；（2）單一的遺傳算法編碼不能全面的將優(yōu)化問題的約束表示出來；（3）遺傳算法通常的效率比比其他傳統(tǒng)的優(yōu)化方法低；（4）遺傳算法容易出現(xiàn)過早收斂；（5）遺傳算法對算法的精度，可信度，計算復(fù)雜性等方面，還沒有有效的定量 分析方法5.2 模擬退火算法的優(yōu)缺點模擬退火法優(yōu)點：（1）它能夠處理具有任意程度的非線性、不連續(xù)性、隨機性的目標(biāo)函數(shù)；（2）目標(biāo)函數(shù)可以具有任意的邊界條件和約束；（3）比其他線性優(yōu)化方法， SA 的編程工作量小，且易于實現(xiàn)；（4）統(tǒng)計上可以保證找到全局最優(yōu)解模擬退火算法缺點：（1）找到最優(yōu)解需要耗費非常多的時間；（2）相對于

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

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

29、 報：2001，6(01)：14-19 3代桂平，王勇，侯亞榮 . 基于遺傳算法的 TSP 問題求解算法及其系統(tǒng) J. 微 計算機信息， 2010( 04)：15-16，19 4 Negnevistsky，M . 顧力栩，沈晉惠譯 . 人工智能智能系統(tǒng)指南 M. 北京 : 機械工業(yè)出版社 . 2010.5 任春玉.基于混合遺傳算法的 TSP問題優(yōu)化研究J.哈爾濱商業(yè)大學(xué)學(xué) 報.2007. 6 Michalewicz Z. Genetic Algorithms +Data Structure=Evolution Programs. Springer-Verlag， Berlin. 20117 易

30、敬， 王平， 李哲. 基于遺傳算法的 TSP 問題研究 J. 信息技術(shù)， 2006， 30(7): 110-112.8 鄧輝文.離散數(shù)學(xué)M.北京：清華大學(xué)出版社.2006. 9劉雁兵，劉付顯 . 基于遺傳算法的 TSP 問題求解與仿真 J. 電光與控 制.2007. 10 張春霞，王蕊 . 基于遺傳算法求解 TSP 問題的算法設(shè)計 J. 安陽工學(xué)院學(xué) 報.2007.11鄭阿奇.MATLAB實用教程M .北京：電子工業(yè)出版社.2004. 12李飛，白艷萍 .用遺傳算法求解旅行商問題 J. 中北大學(xué)學(xué)報 .2007.13 翟梅梅.基于交叉算子改進的遺傳算法求解TSP問題J.淮南師范學(xué)院學(xué)報.200

31、9.14 Merz P.A comparison of recombination operators forthe traveling salesman problemA.Proceedings of the Genetic and Evolutionary Conference.200715 周濤. 基于改進遺傳算法的 TSP 問題研究 J. 微電子學(xué)與計算機， 2006， 23(10)： 104-107. 16 Jung S， Moon B R. Toward Minimal Restriction of Genetic En coding and Crossovers for the

32、Two-Dimensional Euclidean TSP J.IEEE Transactions onEvolutionary Computation， 2011， 6 ( 12) :557565 17 Tsai Cheng-Fa ， Tsai Chun-Wei ， Yang Tzer . A Modified Mul tiple-Searching Method to Genetic Algorithms for Solving Travel ing Salesman ProblemJ.IEEE Transactions on Systems，Man and Cybernetics ， 2

33、011 ，3 (10) :612 18 Write A H. Genetic Algorithms for Real Parameter Optimization. FoundationofGeneticAlgorithms.Sanmateo，GA.2010:205-218附錄： 遺傳算法的TSP方法代碼：1 種群初始化函數(shù) InitPop 的代碼：% 初始化種群%輸入：% NIND ：種群大小% N ： 個體染色體長度(這里為城市的個數(shù))%輸出：%初始種群function Chrom=InitPop(NIND,N)Chrom=zeros(NIND,N);% 用于存儲種群 for i=1:NI

34、NDChrom(i,:)=randperm(N);% 隨機生成初始種群 end2 種群個體的適應(yīng)度函數(shù) Fitness 的代碼 :% 適配值函數(shù)%輸入：%個體的長度( TSP 的距離)%輸出：%個體的適應(yīng)度值function FitnV=Fitness(len)FitnV=1./len;3 選擇操作函數(shù)的 Select 的代碼：% 選擇操作%輸入%Chrom 種群%FitnV 適應(yīng)度值%GGAP代溝%輸出%SelCh 被選擇的個體function SelCh=Select(Chrom,FitnV,GGAP) NIND=size(Chrom,1);NSel=max(floor(NIND*GGAP

35、+.5),2);ChrIx=Sus(FitnV,NSel);SelCh=Chrom(ChrIx,:);其中，函數(shù) Sus 的代碼為 ：% 輸入 :%FitnV 個體的適應(yīng)度值%Nsel 被選擇個體的數(shù)目% 輸出 :%NewChrIx 被選擇個體的索引號 function NewChrIx = Sus(FitnV,Nsel) Nind,ans = size(FitnV); cumfit = cumsum(FitnV);trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1); Mf = cumfit(:, ones(1, Nsel);Mt = trial

36、s(:, ones(1, Nind);NewChrIx, ans = find(Mt Mf & zeros(1, Nsel); Mf(1:Nind-1, :) =rand % 交叉概率 Pc SelCh(i,:),SelCh(i+1,:)=intercross(SelCh(i,:),SelCh(i+1,:);endend%輸入：%a 和 b 為兩個待交叉的個體%輸出：%a 和 b 為交叉后得到的兩個個體其中 intercross 函數(shù)代碼：function a,b=intercross(a,b)L=length(a); r1=randsrc(1,1,1:L); r2=randsrc(1,1,1

37、: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(i2) b(i2)=b1(i);endendend5 變異操作函數(shù) Mutate 的代碼：% 變異操作%輸入： %SelCh 被選擇的個體 %Pm 變異概率%輸出：% SelCh 變異后的個體 function SelCh=Mutate(

38、SelCh,Pm) NSel,L=size(SelCh);for i=1:NSel if Pm=rand R=randperm(L); SelCh(i,R(1:2)=SelCh(i,R(2:-1:1);endend6 進化逆轉(zhuǎn)操作函數(shù) Reverse 代碼：% 進化逆轉(zhuǎn)函數(shù)%輸入 %SelCh 被選擇的個體 %D 個城市的距離矩陣%輸出%SelCh 進化逆轉(zhuǎn)后的個體 function SelCh=Reverse(SelCh,D) row,col=size(SelCh);ObjV=PathLength(D,SelCh); % 計算路徑長度 SelCh1=SelCh;for i=1:rowr1=r

39、andsrc(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:-1:mininverse); endObjV1=PathLength(D,SelCh1); %計算路徑長度index=ObjV1ObjV;SelCh(index,:)=SelCh1(index,:);DrawPath 的代碼：一個隨機解 （ 個體 ）7 畫出所給路線的軌跡圖函數(shù)% 畫路徑函數(shù)%輸入% Chrom 待畫路徑

40、% X 各城市坐標(biāo)位置 function DrawPath（Chrom,X） R=Chrom（1,:） Chrom（1,1）; % figure;hold on plot(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)+0.05,num2str(i),color,1,0,0); endA=X(R,:);row=size(A,1);for i=2:row坐標(biāo)轉(zhuǎn)換arrowx,arrowy

41、 = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2);% annotation（textarrow,arrowx,arrowy,HeadWidth,8,color,0,0,1）;endhold offxlabel（橫坐標(biāo) ）ylabel（縱坐標(biāo) ）title（ 軌跡圖 ）box on8 遺傳算法的主函數(shù)代碼：%遺傳算法求解 TSP 問題 （ 為選擇操作從新設(shè)計后程序 ）%輸入：%D距離矩陣%NIND 為種群個數(shù)%X參數(shù)是中國 10 個城市的坐標(biāo) （ 初始給定 ）%MAXGEN 為停止代數(shù)， 遺傳到第 MAXGEN 代時程序停止 ,MAXGEN 的具體取值視問題的規(guī)模和

42、耗費的時間而定%m 為適值淘汰加速指數(shù) , 最好取為 1,2,3,4, 不宜太大%Pc交叉概率%Pm變異概率%輸出：%R為最短路徑%Rlength為路徑長度clearclcclose allX=22.31113.5834.37108.9530.29120.1629.6691.1439.95116.4126.86100.2324.89102.8330.59104.0734.65112.4637.53122.13;D=Distanse(X); %生成距離矩陣N=size(D,1); %城市個數(shù)% 遺傳參數(shù)NIND=100; %種群大小MAXGEN=200; %最大遺傳代數(shù)Pc=0.9; %交叉概率

43、Pm=0.05; %變異概率GGAP=0.9; %代溝% 初始化種群Chrom=InitPop(NIND,N);% 畫出隨機解的路徑圖DrawPath(Chrom(1,:),X)titlepause(0.0001)% 輸出隨機解的路徑和總距離 disp( 初始種群中的一個隨機值 :) OutputPath(Chrom(1,:);Rlength=PathLength(D,Chrom(1,:); disp( 總距離： ,num2str(Rlength); disp( )% 優(yōu)化gen=0;figure;hold on;box on xlim(0,MAXGEN) title( 優(yōu)化過程 ) xlab

44、el(代數(shù) )ylabel(最優(yōu)值 )ObjV=PathLength(D,Chrom); % 計算路徑長度 preObjV=min(ObjV);while gen,num2str(R(i);enddisp(p)計算個體路線長度函數(shù) PathLength 代碼：% 計算各個體的路徑長度% 輸入：% D 兩兩城市之間的距離% Chrom 個體的軌跡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

45、(1:end-1);i2=p(2:end); len(i,1)=sum(D(i1-1)*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;模擬退火

46、算法的TS方法代碼：生成新解：function S2=NewAnswer(S1)% 輸入% S1: 當(dāng)前解% 輸出% S2 ：新解N=length(S1);S2=S1;a=round(rand(1,2)*(N-1)+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：下一個當(dāng)前解% R：下一個當(dāng)前解的路線距離%R1=PathLength(D,S1); % 計算路線

47、長度N=length(S1); %得到城市的個數(shù)R2=PathLength(D,S2); % 計算路線長度 dC=R2-R1; % 計算能力之差 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