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

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

2、參考文獻(xiàn) 17附錄： 錯(cuò) 誤！未定義書簽。廊坊師范學(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ì)基于

3、遺傳算法的 TSP 算法結(jié) 果與基于模擬退火算法的TSP算法的結(jié)果進(jìn)行比較，描述其優(yōu)缺點(diǎn)， 并選擇最為恰當(dāng)?shù)?TSP 算法，實(shí)現(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完全問題,即其 最壞情況下的時(shí)間復(fù)雜性隨著問題規(guī)模的擴(kuò)大，按指數(shù)方式增長(zhǎng) 2，到目前 為止不能找到一個(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)化算法，其基本原理是仿效生物界中

8、的“物競(jìng)天擇， 適者生存”的演化法則 3 遺傳算法把問題參數(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)

9、算法的 Metropolis 6抽樣過程， 冷卻過程對(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

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

11、 接相連.遺傳算法TSP問題的流程圖如圖2-1所示.N圖2-1算法流程框架圖3.2算法的詳細(xì)設(shè)計(jì)321解空間的表示方式遺傳算法對(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，例如，下面

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個(gè)旅游城市的TSP問題，如果將種群規(guī)模設(shè)為 200,則解空間就用二維數(shù)組 來表示：Path20010.322種群初始化種群的規(guī)模選擇應(yīng)適當(dāng)，盲目的增大種群規(guī)模不能使算法得到改進(jìn)，反而大大增加了計(jì)算的開銷.10個(gè)城市TSP問題，可以選擇小規(guī)模的種群（例如 200）, 種群初始化時(shí)，先產(chǎn)生1, 2,，10的一條規(guī)則路徑，然后在這條路徑中隨機(jī) 選兩個(gè)數(shù)

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

14、求得種群中所有個(gè)體的適應(yīng)值后，將適應(yīng)值最大的個(gè)體保存起 來，到演化完畢時(shí)，這個(gè)個(gè)體就是最后要求的最優(yōu)解 .3.2.4選擇操作選擇操作的目的是為了從當(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被選中的概率為：PiFiN(2)其中，F(xiàn)為個(gè)體i的適應(yīng)度值；N為種群個(gè)體數(shù)目325交叉操作交叉操作是遺傳算法中最主要的遺傳操作， 通過交

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

16、下一代6 710819能夠結(jié)合各自的優(yōu)勢(shì)基因，產(chǎn)生更326 變異操作變異可以看作是外界對(duì)種群的影響變異是為了引入新的因素，希望個(gè)體在 外界的作用下，能夠?qū)崿F(xiàn)自我優(yōu)化，生好的基因?qū)⒆儺愃阕幼饔糜谌后w即是對(duì) 群體中的個(gè)體串的某些基因位置上的基因值作變動(dòng).變異算子采用了簡(jiǎn)單的倒序變換，以10城市為例，隨機(jī)的產(chǎn)生兩個(gè)小于10的整數(shù)，對(duì)某個(gè)個(gè)體進(jìn)行分割， 假設(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由于這種變異算子仍能保持個(gè)體中的路徑片段， 即倒序前后這個(gè)

17、切割段的路 徑是一樣的，只是兩端點(diǎn)與整個(gè)路徑的連接顛倒了，這使得變異不是漫無邊際， 而是有所取舍的.這種簡(jiǎn)單反序可以保證后代仍然是一條合法途徑.3.2.7進(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ū)間內(nèi)的隨機(jī)整數(shù)斤和r2，確定兩個(gè)位置，將其對(duì)換位置， 例如廠4,礦刁5 1 2 | 4 | 3 6 | 7 | 9 8 10進(jìn)化逆轉(zhuǎn)后為：5 1 2 | 7 | 3 6丨4 | 9 8 10對(duì)每個(gè)個(gè)體進(jìn)行交叉變異，然后代入適應(yīng)

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

19、2 4 910 6總距離：165.2494對(duì)照1-10數(shù)字編號(hào)所代表的的城市，隨機(jī)路線為：麗江一 杭州一 昆明一 成都一 北京一 珠海一 西安一 拉薩一 洛陽一 威海 麗江.29優(yōu)化后的最優(yōu)路線圖如圖3-2所示:Q Figure 3File Edit View Insert Tools Desktop Window Help | n|皺鷲紗物繪銘T0|匡i|口最優(yōu)解的路徑團(tuán)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)化過程中路線長(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-1模擬退火算法求解流程框圖4.3模擬退火算法的實(shí)現(xiàn)過程(1) 控制參數(shù)的設(shè)置需要設(shè)置的主要控制參數(shù)有降溫速率 q、取初始溫度To足

21、夠大，令T=To，任取初始解3，確定每個(gè)T時(shí)的迭代次數(shù)，即Metropolis鏈長(zhǎng)L,如圖表4-1所示.表4-1參數(shù)設(shè)定降溫速率q初始溫度T。結(jié)束溫度Tend鏈長(zhǎng)L0.910000.001500(2) 初始解對(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|1就為一個(gè)合法解，采用隨機(jī)排列的方法產(chǎn)生一個(gè)初始解S .(3) 解變換生成新解通過對(duì)當(dāng)前解進(jìn)行變換，產(chǎn)生新路徑的數(shù)組即新解，這里采用的變換是產(chǎn) 生隨機(jī)數(shù)的方法來產(chǎn)生將要交換的兩個(gè)城市， 用二鄰域

22、變換法15產(chǎn)生新的路徑， 即新的可行解S2.例如n=10時(shí)，產(chǎn)生兩個(gè)1，10范圍內(nèi)的隨機(jī)整數(shù)ri和2確定 兩個(gè)位置，將其對(duì)換位置，如11=4， 2=7512 | 4 |36 | 7 | 9810得到的新解為：512 | 7 |36 | 4 | 9810(4) Metropolis 準(zhǔn)則若路徑長(zhǎng)度函數(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 ；否則計(jì)算S2的接受概率 exp(-df/T)

23、，即隨機(jī)產(chǎn)生的(0，1)區(qū)間上均勻分布的隨機(jī)數(shù)rand，若exp(-df /T rand 18,也接受S作為新的當(dāng)前解，S =S2 ；否則保留當(dāng)前解S -(5) 降溫利用降溫速率q進(jìn)行降溫，即T=qT，則T小于結(jié)束溫度，則停止迭代輸出 當(dāng)前解S,為最優(yōu)解，結(jié)束程序，否則按衰減函數(shù)衰減T后逐漸降低控制溫度，重 復(fù)Metropolis過程，繼續(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ī)路線軌跡圖，

24、如圖4-2所示.Q Fig聽 1File Edit View Insert Tools Desktop Window Help0日日 b 聘搖屈 s a圖4-2隨機(jī)路線軌跡圖初始種群中的一個(gè)隨機(jī)值：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)路線如下所示：洛陽一 西安一 成都一 拉薩一 麗江一 昆明一 珠海一 杭州一 威海一 北京 洛陽本次運(yùn)行的時(shí)間如下所示：Elapsed time is 12.232553 sec on ds.優(yōu)化過程如圖4

25、-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)：（1）對(duì)可行解表示的廣泛性;（2）群體搜索特性；（3）不需要輔助信息；（4）內(nèi)在啟發(fā)式隨機(jī)搜索特性；（5）遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù) 是不連續(xù)的，非規(guī)則的或有噪音的情況下，也能以很大的概率找到全局最優(yōu)解；（6）遺傳算法具有固有的并行性和并行計(jì)算能力；（7）遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)

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

27、其他一些技術(shù)對(duì)某一個(gè)具體問題的求解需要更困難的參數(shù)調(diào)整；（3）使用不當(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ā)式概率性搜索的算法， 可以用以求解不

28、同的非線性問題， 對(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) 1畢曉君. 信息智能處理技術(shù) M. 北京: 電子工業(yè)出版社 . 2010.2儲(chǔ)理才.基于MATLAB的遺傳算法程序設(shè)計(jì)及TSP問題求解J.集美大學(xué)學(xué)

29、 報(bào)：2001，6(01)：14-19 3代桂平，王勇，侯亞榮 . 基于遺傳算法的 TSP 問題求解算法及其系統(tǒng) J. 微 計(jì)算機(jī)信息， 2010( 04)：15-16，19 4 Negnevistsky，M . 顧力栩，沈晉惠譯 . 人工智能智能系統(tǒng)指南 M. 北京 : 機(jī)械工業(yè)出版社 . 2010.5 任春玉.基于混合遺傳算法的 TSP問題優(yōu)化研究J.哈爾濱商業(yè)大學(xué)學(xué) 報(bào).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ì) J. 安陽工學(xué)院學(xué) 報(bào).2007.11鄭阿奇.MATLAB實(shí)用教程M .北京：電子工業(yè)出版社.2004. 12李飛，白艷萍 .用遺傳算法求解旅行商問題 J. 中北大學(xué)學(xué)報(bào) .2007.13 翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解TSP問題J.淮南師范學(xué)院學(xué)報(bào).200

31、9.14 Merz P.A comparison of recombination operators forthe traveling salesman problemA.Proceedings of the Genetic and Evolutionary Conference.200715 周濤. 基于改進(jìn)遺傳算法的 TSP 問題研究 J. 微電子學(xué)與計(jì)算機(jī)， 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 ： 個(gè)體染色體長(zhǎng)度(這里為城市的個(gè)數(shù))%輸出：%初始種群function Chrom=InitPop(NIND,N)Chrom=zeros(NIND,N);% 用于存儲(chǔ)種群 for i=1:NI

34、NDChrom(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 選擇操作函數(shù)的 Select 的代碼：% 選擇操作%輸入%Chrom 種群%FitnV 適應(yīng)度值%GGAP代溝%輸出%SelCh 被選擇的個(gè)體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 個(gè)體的適應(yīng)度值%Nsel 被選擇個(gè)體的數(shù)目% 輸出 :%NewChrIx 被選擇個(gè)體的索引號(hào) 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 為兩個(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

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 被選擇的個(gè)體 %Pm 變異概率%輸出：% SelCh 變異后的個(gè)體 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 進(jìn)化逆轉(zhuǎn)操作函數(shù) Reverse 代碼：% 進(jìn)化逆轉(zhuǎn)函數(shù)%輸入 %SelCh 被選擇的個(gè)體 %D 個(gè)城市的距離矩陣%輸出%SelCh 進(jìn)化逆轉(zhuǎn)后的個(gè)體 function SelCh=Reverse(SelCh,D) row,col=size(SelCh);ObjV=PathLength(D,SelCh); % 計(jì)算路徑長(zhǎng)度 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); %計(jì)算路徑長(zhǎng)度index=ObjV1ObjV;SelCh(index,:)=SelCh1(index,:);DrawPath 的代碼：一個(gè)隨機(jī)解 （ 個(gè)體 ）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è)計(jì)后程序 ）%輸入：%D距離矩陣%NIND 為種群個(gè)數(shù)%X參數(shù)是中國(guó) 10 個(gè)城市的坐標(biāo) （ 初始給定 ）%MAXGEN 為停止代數(shù)， 遺傳到第 MAXGEN 代時(shí)程序停止 ,MAXGEN 的具體取值視問題的規(guī)模和

42、耗費(fèi)的時(shí)間而定%m 為適值淘汰加速指數(shù) , 最好取為 1,2,3,4, 不宜太大%Pc交叉概率%Pm變異概率%輸出：%R為最短路徑%Rlength為路徑長(zhǎng)度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); %城市個(gè)數(shù)% 遺傳參數(shù)NIND=100; %種群大小MAXGEN=200; %最大遺傳代數(shù)Pc=0.9; %交叉概率

43、Pm=0.05; %變異概率GGAP=0.9; %代溝% 初始化種群Chrom=InitPop(NIND,N);% 畫出隨機(jī)解的路徑圖DrawPath(Chrom(1,:),X)titlepause(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 on xlim(0,MAXGEN) title( 優(yōu)化過程 ) xlab

44、el(代數(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

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：下一個(gè)當(dāng)前解% R：下一個(gè)當(dāng)前解的路線距離%R1=PathLength(D,S1); % 計(jì)算路線

47、長(zhǎng)度N=length(S1); %得到城市的個(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