應(yīng)用數(shù)學(xué)報告

1、深圳大學(xué)課程論文題目 多旅行商問題的遺傳算法研究 成績 專業(yè) 機械工程 課程名稱、代碼 應(yīng)用數(shù)學(xué)152016040006 年級 姓名 學(xué) 號 時間 任課教師 1. 摘要 旅行商問題（Traveling Salesman Problem，簡稱TSP）是一個著名的組合優(yōu)化問題：給定n個城市，有一個旅行商從某一城市出發(fā)，訪問每個城市各一次后再回到原出發(fā)城市，要求找出的巡回路徑最短。多旅行商回路（MTSP）是旅行商問題（TSP）擴展。MTSP是指給出N個城市的集合，M個推銷商從目標城市出發(fā)，分別走一條旅行路線，使得每個城市有且僅有一個推銷商走過，最后回到原來的出發(fā)城市，且總路程最短。相對于傳統(tǒng)的變異方

2、法，此次我們通過增加種群中個體的變異數(shù)量，來提高變異程度，從而實現(xiàn)了在更少的迭代次數(shù)中使最優(yōu)解趨于穩(wěn)定。2. 引言 遺傳算法是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進化過程中適者生存規(guī)則與同一群染色體的隨機信息變換機制相結(jié)合的搜索算法。它通過給解向量編碼、形成初始種群，然后用變異、交叉重組、自然選擇等算子，進行并行迭代，求的優(yōu)化解。由于它采用隨機運算，對搜索空間無特殊要求，無需求導(dǎo)，具有運算簡單、收斂速度快等優(yōu)點。3. 論文內(nèi)容多旅行商問題根據(jù)起點和終點城市的不同，又可以分為四種不同情況，而此次論文中主要研究的是所有旅行商起點和終點城市都相同的這種情況。此次，論文中提出了一種新的GA染色體編碼

3、方式及相關(guān)的變異操作方法(Two-part chromosome technique)，并且將此方法與以前的方法在理論性能和計算性能上做比較，通過計算測試發(fā)現(xiàn)該方法具有更小的搜索空間，同時具有更好的適值解，相對于另外兩種傳統(tǒng)編碼方式。3.1 編碼方式論文主要提出了3種了編碼方法，可以通過下面3個圖形來表示它們各自不同的編碼方式。第一種編碼方式：One chromosome12-1578-2364（上圖中正數(shù)代表城市排列，負數(shù)代表分隔符，將城市劃分M塊）第二種編碼方式：Two chromosome1257836422313321 （上圖中第一個排列代表城市排列，第二個代表每個城市所對應(yīng)的旅行商）

4、第三中編碼方式：Two-part chromosome1265784343 （圖中上面的代表城市排列，下面的代表城市分割位置） 3.2、從兩個方面論證該種編碼方式具有更好的求解優(yōu)勢A. 從搜索空間上看優(yōu)勢體現(xiàn) 三種編碼方式下的解空間大小如下表所示： 以上是在三種不同的編碼方式下解空間大小通過圖形表示如下： 可見Two-part chromosome technique方式具有更小的解空間。B. 從最終的適值解上分析論文中通過給定不同的城市數(shù)，分別在三種不同編碼方式下，進行多旅行商最優(yōu)值的求解，并在圖形上顯示出來，具體結(jié)果如下圖：1、城市數(shù)固定為51 最小的總旅程 距離最長的那個旅行商的最小距離

5、 2、城市數(shù)固定為100 3、城市數(shù)固定為150 上圖中綠線是本論文所提出的一種方法，另外兩條線是傳統(tǒng)方法，從圖中可以看出，綠線在不同的情況下都表現(xiàn)出了良好適值解。同時，由于在現(xiàn)實世界中的問題可能會更感興趣的減少最長的單個旅行商的旅行距離，所以右側(cè)的三個圖分別分析了單個旅行商的旅行距離，通過觀察發(fā)現(xiàn)，其同樣具有很好的適值解。 4. 實現(xiàn)過程 由于前面論文中已經(jīng)給出了一種最優(yōu)的編碼方式，所以此次我們采用的也是前面論文中所提出的一種編碼方式來實現(xiàn)程序的編寫。4.1 實現(xiàn)流程大致過程可以分為以下幾步： 1、初始化種群：通過randperm(n)+1產(chǎn)生隨機2-n的隨機序列號，根據(jù)min_tour求插

6、入點位置位置序列，用二者來充當初始化的個體，以此組成種群。 2、根據(jù)n個城市的位置信息，求一個n*n的距離矩陣，用來充當后續(xù)的個體序列求距離時的元素間距離索引。 3、通過雙重循環(huán)來求出種群序列所對應(yīng)的旅行長度，并將索引值，序列號，旅行長度三者關(guān)聯(lián)起來，用于后續(xù)的變異操作時的索引。同時求出本次種群中的最優(yōu)個體（旅行長度最?。⑼ㄟ^序列號畫出線路圖。 4、通過一個循環(huán)，以步長為10，每次進入循環(huán)之后從種群中選取10個個體，然后找到10個個體中的最優(yōu)個體，并內(nèi)嵌一個循環(huán)次數(shù)為10的循環(huán)結(jié)構(gòu)，用來對每次的最優(yōu)個體進行9次變異，和1次不變異，因而用新的10個個體代替以前的10個個體，來形成下一個種群。

7、其中，由于形成的10個變異個體中都會有1個個體不變異，也就是說下一代種群中都會存在一部分上一代種群中的最優(yōu)的部分個體，所以最優(yōu)解永遠會趨于收斂。 5、通過迭代次數(shù)來控制變異是否結(jié)束。流程圖如下：4.2 變異方法 從種群中每10個個體中取出一個最優(yōu)個體，進行遺傳變異操作，從前面我們知道我們實質(zhì)上是從一個最優(yōu)個體變異產(chǎn)生9個不同的變異個體，以下是最優(yōu)個體對應(yīng)的9中不同變異方法。A、元素序列變異1、元素互換 x、y元素互換2、 元素倒置 m、n、k倒序排列3、 元素插入 X元素插入到y(tǒng)后4、 整體互換 將abefg排列改為efgabB、插入點變異 根據(jù)最小旅行要求隨機產(chǎn)生插入點序列。C、插入點和序列

8、號同時變異（4種） 插入點重復(fù)前面的序列變異方法，但同時加入插入點變異。 所有加一起總共可以產(chǎn)生9種不同的變異，還有一個最優(yōu)個體不變異，因此，通過一個個體產(chǎn)生了10個不同的下一代個體，用于形成下一代種群。5. 結(jié)果分析 此次程序設(shè)計中還是延續(xù)了前人的一些設(shè)計經(jīng)驗，但在變異部分增加了變異的程度，對應(yīng)增加了兩種變異方式，以前通常會選擇7種變異，此次我們增加到9種。也就是以前是從1個個體中產(chǎn)生8個變異個體，而我們是從1個個體產(chǎn)生10個變異個體，通過仿真發(fā)現(xiàn)增大變異程度，最優(yōu)解會在較少的迭代次數(shù)中趨于穩(wěn)定?，F(xiàn)分別做了一個仿真比較，如下圖： 此次采用30個城市，5個旅行商，最少旅行5個城市來做比較。前人

9、的結(jié)果：改變之后的結(jié)果： 可以發(fā)現(xiàn)，在增大變異程度之后，種群最優(yōu)路徑值會在短時間內(nèi)將路徑值降低到很小然后再慢慢平穩(wěn)降低，最后趨于穩(wěn)定。因此，如果想要在短時間內(nèi)找近似最優(yōu)值，可以采用增大變異程度來實現(xiàn)；如果想要不計較迭代時間，只是想要實現(xiàn)平穩(wěn)趨近最優(yōu)值，可以采用減小變異程度，來實現(xiàn)最優(yōu)路徑求解。6. 參考文獻1、 Arthur E.Carter,Cliff T.Ragsdale. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research 175(2006)246-257 2、 陶然，呂紅霞，陳廣秀基于MTSP的機車周轉(zhuǎn)圖編制模型與算法J西南交通大學(xué)學(xué)報，2006，41(5)：653-6573、 王海龍.周輝仁.鄭丕諤.唐萬生.WANG Hai-long.ZHOU Hui-ren.ZHENG Pie.