遺傳算法求解tsp問題的計算機仿真畢業(yè)論文

1、<p>　　題目：遺傳算法求解旅行商問題的計算機仿真</p><p>　　遺傳算法求解TSP問題的計算機仿真</p><p><b>　　摘要</b></p><p>　　由于遺傳算法在整體搜索策略和優(yōu)化搜索方法上不依賴梯度信息或其他輔助知識，只需要影響搜索方向的目標函數和相應的適應度函數，所以提供了一種求解復雜系統問題的通用框架，因

2、此遺傳算法廣泛應用于數學問題、組合優(yōu)化、機械設計、人工智能等領域。</p><p>　　遺傳算法（Genetic Algorithms,簡稱GA）是模擬自然界生物自然選擇和進化的機制而發(fā)展起來的一種高度并行、自適應的隨機搜索算法。特別適合于求解傳統的搜索算法不好處理的復雜的最優(yōu)解問題。旅行商問題（Traveling Salesman Problem）就是要決定一條經過路線中所有城市當且僅當一次且距離最短的路線，即

3、距離最短的Hamilton回路。旅行商問題是一個具有十分廣泛的實用背景和重要理論價值的組合優(yōu)化問題。目前求解TSP問題的主要方法有模擬退火算法、遺傳算法、Hopfield神經網絡算法、啟發(fā)式搜索法、二叉樹描述算法。本文選用遺傳算法求解45個城市的TSP問題，基于Microsoft Visual C++環(huán)境,采用Grefenstette等提出的一種新的巡回路線編碼方法，變異算子采用了常規(guī)的基本位變異法，通過多組實驗和數據近似的求解出了45

4、個城市的最優(yōu)解，實現了計算機仿真求解TSP問題。</p><p>　　關鍵字：旅行商問題；遺傳算法；變異算法；編碼方式</p><p>　　The computer simulation of genetic algorithm to solve </p><p>　　TSP problem</p><p><b>　　Abstra

5、ct</b></p><p>　　Due to genetic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence t

6、he search direction of the objective function and the corresponding fitness function, and so provides a generic framework for solving complicated system problem, so the genetic algorithm is widely used in mathematical pr

7、oblem, combinatorial optimization, mechanical design, artificial intelligence, etc </p><p>　　Genetic algorithm (based Algorithms, the GA) is mimic natural biological natural selection and evolution mechanism

8、 and developed a kind of highly parallel, adaptive random search algorithm. Particularly suitable for solving the traditional search algorithm is not good to deal with complex optimal solution of problem. Traveling Sales

9、man Problem ('ll Salesman Problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of Hami</p><p>　　Key words: Traveling salesm

10、an problem. Genetic algorithm; Mutation algorithm; </p><p><b>　　1緒論</b></p><p>　　自20世紀60年代以來,一種模擬生物自然遺傳與進化過程并將生物進化原理、最優(yōu)化技術和計算機技術結合起來的優(yōu)化方法—遺傳算法（Genetic Algorithm,簡稱GA）被提出并得到廣泛研究，該算法特別

11、適用于處理傳統搜索方法難以解決的復雜和非線性問題，可以廣泛應用于人工智能、機械設計、自適應控制等領域。遺傳算法固有的并行性和并行計算的能力，使在搜索過程中不容易陷入局部最優(yōu)。即使在所定義的適應度函數中是不連續(xù)的、不規(guī)則的情況下，也可以很大概率找到全局最優(yōu)解。采用自然進化機制來表現復雜的現象，能夠快速可靠地解決求解非常困難的問題，非常適用于本課題涉及的TSP問題的求解與研究。</p><p>　　旅行商問題（Tra

12、veling Salesman Problem ,TSP）是一個非常經典的組合優(yōu)化問題的NP難題，長期以來都沒有一個十分有效的算法來解決它，但TSP本身在許多領域有著重要的應用，如連鎖店的貨物配送路線、計算機網絡路由器遍歷、印刷電路板的鉆孔路線等問題都可以建模為旅行商問題。TSP問題其實是“哈密頓回路問題”中的“哈密頓最短回路問題”。在本系統就是要應用遺傳算法求解45個城市的TSP問題。因為遺傳算法本身是模擬生物自然選擇和遺傳的過程的，

13、所以用遺傳算法求解TSP最先要確定的是問題的建模，即如何用遺傳學的算子來表示旅行商問題中的變量。必需要非常的了解，并熟悉每一個遺傳學中的術語在遺傳學中的具體作用，然后應用到求解具體問題當中來。應用遺傳算法求解旅行商問題最關鍵的是編碼方式、交叉、選擇、變異算子的設計，直接關系到算法能否求出最優(yōu)解或近似最優(yōu)解。所以要在編碼方式的確定上做好足夠的功夫，以確定程序求解的精確度。</p><p>　　本章主要論述本文所研究

14、的主要內容，并對論文的章節(jié)結構進行規(guī)劃。</p><p><b>　　1.1 研究背景</b></p><p>　　旅行商問題（Traveling Salesman Problem, TSP）,也稱旅行推銷員問題，具體的數學模型可以這樣理解：現在給定以下幾個城市的位置，旅行商從其中的某一個城市出發(fā)，不重復地訪問其余的每一個城市，最后又返回到原出發(fā)點城市，要求找出這樣一

15、條路線，使旅行所付出的代價最小。雖然它是一個比較古老的問題，最早可以追溯到Euler提出的騎士旅行問題，但同時它也是一個新的問題，因為它的計算復雜度較高，雖然人們一直在嘗試用新的方法來改進求解該問題的復雜度，但是這一類問題距今都沒有能找到一個有效的算法來解決。</p><p>　　TSP問題可以形式化描述為：設G=（V,A,D）是一個圖，其中V是n個頂點的集合，A是弧線或邊集,D=（）是與A關聯的距離或費用矩陣。

16、旅行商問題就是要解決一個最小回路問題，回路中所有頂點有且僅經過一次。對于具有一個城市的旅行商問題，其可能的路徑數目為（n-1）！/2，5個城市的問題模型就對應120/10=12條路線，10個城市的問題模型對應3628800/20=181440條路線。所以當輸入越大，則耗費的時間就是個天文數字了，因此旅行商問題至今都沒有能找到一種有效的求解方法。尋求一種能短時間求解出高精度解的算法，已成為此問題研究的熱門。盡管旅行商問題至今仍然沒有找到最

17、優(yōu)解，但求解它的算法已經在不斷的改進。目前，求解TSP問題常用的算法主要有遺傳算法和蟻群算法，另外還有爬山法、模擬退火算法、神經網絡方法、貪婪算法、禁忌搜索算法等。1980Crowder和Padberg求解了318個城市的TSP問題；1987年Padberg和Rinaldi成功將城市數量增加到了2392個；最大的成功求解的旅行商問題已經增加到24798個城市。</p><p><b>　　1.2研究意義

18、</b></p><p>　　首先旅行商問題是用于求解N個城市存在（N-1）條閉合路徑的排列方案，對于這一類問題很難用全局搜索法精確地求出最優(yōu)解，這一問題已經困擾眾多學者許多年，因此研究相應的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。</p><p>　　其次，隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費了不必要的時間和金錢，而這些不必要的浪費完全可以通過對旅行路線的合理規(guī)劃來避

19、免。而在互聯網繼續(xù)擴大普及的時代，電子商務也迎來了期待已久的春天，同時物流產業(yè)也隨之水漲船高。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標，更加合理的配送路線能明顯地為物流公司增大利潤。再比如在裝配線的流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產量的相應增加。由于旅行商問題在計算機網絡、物流、旅游業(yè)、交通運輸等許多領域都有著十分廣泛的應用，因此尋找一個求解這類問題的求解方法有很高的應用價值</p>

20、<p>　　因此，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應用價值。</p><p><b>　　1.3研究內容</b></p><p>　　本文采用遺傳算法求解45個城市的旅行商問題，并對其實現計算機仿真。遺傳算法（Genetic Algorithms,GA）又叫基因進化算法或進化算法，是一種通過模擬自然界生物適者生存、優(yōu)勝

21、劣汰的進化過程而形成的一種自適應、具有全局優(yōu)化能力的隨機搜索算法。應用遺傳算法求解旅行商問題，最難得地方在于問題建模，如城市編碼方式以及交叉、變異、選擇算子的確定等。</p><p>　　本文采用的是Grefenstette等提出的一種新的巡回路線編碼方法，其可以在一定程度上克服常規(guī)巡回路線編碼方法在交異操作時易產生不滿足問題約束條件或無實際意義的巡回路線的缺點。交叉算法采用的是常規(guī)的單點交叉，之所以可以用這一常

22、規(guī)的交叉法，是因為在編碼方式上使用的是Grefenstette等提出的一種新的巡回路線編碼方法，它可以最大化交叉后后代與其父代的性狀差異，有利于算法的全局性。變異算法采用的是基本位變異法，即只是根據變異概率隨機改變染色體中的某一段染色體，具體會在后文中做詳細說明。在遺傳算法中，以個體適應度的大小來確定該個體被遺傳到下一代群體中的概率。本課題中以每條路徑長度的倒數作為適應度函數值。在求出之后將其按照從大到小的順序排列，以便于后面找出路徑之

23、和最小的城市序列。</p><p><b>　　1.4 本文的結構</b></p><p>　　本文一共分為5章，結構如下：</p><p>　　第一章緒論。這一章主要論述旅行商問題的基本概念，以及本課題主要的研究方法及其研究意義，并對論文的章節(jié)結構加以論述。</p><p>　　第二章遺傳算法理論概述。這一章主要論述遺

24、傳算法的起源發(fā)展及其實際應用，重點介紹了遺傳算法的算法原理及步驟。</p><p>　　第三章基于遺傳算法求解TSP問題。本章主要介紹了本系統具體使用什么方式實現求解過程，包括編碼方式、選擇、交叉、變異算子的具體選取。</p><p>　　第四章45個城市旅行商問題的仿真軟件的設計。本章主要對系統模塊進行了介紹，而且對應用系統進行了多組試算，最后得出結論。</p><p

25、>　　第五章結論。對本文的內容進行總結。</p><p>　　2 遺傳算法理論概述</p><p>　　2.1 遺傳算法的產生及發(fā)展</p><p>　　最早由美國Michigan(密執(zhí)安大學)的Hollang教授提出，起源于60年代對自然和人工自適應系統的研究。1967年，他的學生Bagley J.D.首次提出“遺傳算法”一詞，并發(fā)展了復制、交叉、變異、顯性

26、、倒位等遺傳算子。70年代De Jong基于遺傳算法的思想在計算機上進行了大量純數值函數優(yōu)化計算實驗，建立了著名的De.Jong五函數測試平臺。在一系列研究工作的基礎上80年代Goldberg進行總結歸納，形成了遺傳算法的基本框架；Smith將遺傳算法應用于機械學習領域；Bethke對函數優(yōu)化的遺傳算法進行了系統的研究。進入90年代，遺傳算法進入了興盛期，無論是理論研究還是實際應用都成了十分熱門的課題。如今遺傳算法已經被廣泛的應用于計算

27、機科學、人工智能、機械設計、圖像處理等各個領域，不僅如此，利用遺傳算法進行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。</p><p>　　下面是一些在遺傳算法發(fā)展進程中做出杰出貢獻的人物：</p><p>　　1 J.H.Holland</p><p>　　60年代提出在研究和設計人工自適應系統時,可以借鑒生物遺傳的機制；</p><p&

28、gt;　　70年代初提出了遺傳算法的基本定理－模式定理(Schema Theorem)，從而奠定了遺傳算法的理論基礎；　</p><p>　　80年代實現了第一個基于遺傳算法的機器學系統－分類器系統(Classifier Systems),開創(chuàng)了基于遺傳算法的機器學習的新概念。</p><p>　　2 J.D.Bagley</p><p>　　1967年在其博士論

29、文中首次提出了：“遺傳算法”一詞，發(fā)展了復制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應遺傳算法的概念。</p><p>　　3 K.A.De Jong</p><p>　　1975年在其博士論文中結合模式定理進行了大量的純數值函數優(yōu)化計算實驗，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標和離線指標。</p><p>　　4 D.J.Golgb

30、erg</p><p>　　1989年出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法(Genetic Algorithms in Search，Optimization and Machine Learning)》，系統總結了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應用。</p><p>　　5 L.Davis</p><p>　　1991年

31、編輯出版了《遺傳算法手冊 (Handbook of Genetic Algorithms)》書中包括遺傳算法在科學計算、工程技術和社會經濟中的大量應用實例。</p><p><b>　　6J.R.Koza</b></p><p>　　1992年將遺傳算法應用于計算機程序的優(yōu)化設計及自動生成，提出了遺傳編程 (Genetic Programming) 的概念，并成功的將

32、其提出的遺傳編程應用于人工智能、機器學習符號處理等方面。</p><p>　　2.2 遺傳算法基本原理</p><p>　　遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應、具有全局優(yōu)化能力的隨機搜索算法。</p><p>　　遺傳算法的思路是通過從給定一個初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進化的三種原則，逐步

33、改進種群，越來越逼近最優(yōu)解，以達到求解最優(yōu)化問題的目的。在遺傳算法中，種群中的每一個個體是問題的一個解，稱為“染色體”，染色體是一串符號，比如二進制的01串。這些染色體在后續(xù)的迭代中不斷的進化，稱為遺傳。在每一代中應用適應度（fitness）來測量染色體的優(yōu)越性，適應度高的更容易在自然的選擇中存活下來。生存下來的染色體被稱為后代（offspring）。后代通常是前一代染色體通過交叉（crossover）或者變異（mutation ）形成

34、。新的下一代再重復根據適應度選擇部分后代，淘汰一部分后代，這樣即可以保證種群染色體的優(yōu)越性，也保持了種群大小的穩(wěn)點性。遺傳算法中每一條染色體，對應著遺傳算法的一個解決方案，一般我們用適應性函數（fitness function）來衡量這個解決方案的優(yōu)劣。所以也可以把遺傳算法的過程看作是一個在多元函數里面求最優(yōu)解的過程。在這個多維曲面里面也有數不清的“山峰”，而這些最優(yōu)解所對應的就是這些山峰，這些山峰就是局部最優(yōu)解。而其中也會有一個“山峰

35、”的海拔最高</p><p>　　下面給出生物學的幾個基本概念知識，這對于理解遺傳算法很重要：</p><p>　　1）遺傳因子（gene）:DNA長鏈結構中占有一定位置的基本遺傳單位，也稱基因。生物的基因根據物種的不同而多少不一。</p><p>　　2）個體（individual）:指染色體帶有特征的實體。</p><p>　　3）種群（

36、population）:染色體帶有特征的個體的集合。</p><p>　　4）進化（evolution）;生物在其延續(xù)生命的過程中，逐漸適應其生存環(huán)境使得其品質不斷得到改良，這種生命現象稱為進化。生物的進化是以種群的形式進行的。</p><p>　　5）適應度（fitness）:度量某個物種對于生存環(huán)境的適應程度。</p><p>　　6）選擇（selection）

37、:指以一定的概率從種群中選擇若干個體的操作。</p><p>　　7）變異（musation）：復制時很小的概率產生的某些復制差錯。</p><p>　　8）編碼（coding）:DNA中遺傳信息在一個長鏈上按一定的模式排列，也即進行了遺傳編碼。遺傳編碼可以看成是從表現型到遺傳子型的映射。</p><p>　　9）串（String）:它是個體的形式，在算法中為二進制

38、串，并且對應于遺傳學中的染色體。</p><p>　　10）串結構空間（ss）：在串中，基因任意組合所構成的串集合?；虿僮魇窃诮Y構空間中進行的。串結構空間對應用于遺傳學中的基因型的集合。</p><p>　　11）染色體：是生物細胞中含有的一種微小的絲狀化合物，是遺傳物質的主要載體，由多個遺傳因子—基因組成。</p><p>　　2.3 遺傳算法基本步驟</

39、p><p>　　步驟一：編碼：把所需要選擇的群體進行編號，每一個個體就是一條染色體，一個解就是一串基因的組合。</p><p>　　步驟二：初始化：隨機生成有N個個體的初始群體，這些個體一起組成了一個種群。遺傳算法就是以這個初始群體為起點開始迭代。參數N可以根據具體的情況而定。</p><p>　　步驟三：交叉算子：這是遺傳算法最重要的操作。所謂交叉是指把兩個父代個體的

40、部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。</p><p>　　步驟四：適應度：確定個體適應度的量化評價方法，適應度用于衡量種群中個體的優(yōu)劣性，是確定種群中個體留存的關鍵。</p><p>　　步驟五：選擇算子：選擇的目的是為了從交換后的群體中選出優(yōu)良的染色體攜帶者，使它們有機會作為父代繁殖出下一代群體。選擇操作是建立在適應度之上的，適應度高的被選中的幾率

41、就大，選擇操作體現出了生物適者生存的原則。</p><p>　　步驟六：變異算子：變異是根據生物遺傳中基因突變的原理，以變異概率對群體中的某一些個體的某些“位”執(zhí)行變異。變異操作可以保證算法過程中不會產生無法進化的單一群體，避免算法早熟出現局部最優(yōu)。</p><p>　　步驟七：終止。給定最大的遺傳代數，算法在計算到最大的遺傳代數時，終止計算。</p><p>　　

42、2.4 遺傳算法算法流程圖</p><p>　　圖2-4遺傳算法算法流程圖</p><p>　　2.5 遺傳算法的特點</p><p>　　遺傳算法屬于進化算法（Evolutionary Algorithms）的一種，它通過模仿自然界的選擇與遺傳的原理來求出最優(yōu)解，遺傳算法有三個最基本的算子：選擇、交叉、變異。數值方法求解這一問題的主要手段是迭代運算。一般的迭代方法

43、容易陷入局部極小的陷阱而出現“死循環(huán)”現象，使迭代無法進行。遺傳算法很好地克服了這個缺點，是一種全局優(yōu)化算法。</p><p>　　遺傳算法與傳統的優(yōu)化方法（枚舉，啟發(fā)式等）相比較，以生物進化為原型，具有很多的優(yōu)點。主要有以下幾點：</p><p>　?。?）遺傳算法的本質并行性。首先，遺傳算法并行的方式是從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統優(yōu)化算法的最大區(qū)別。傳

44、統優(yōu)化算法從單個初始值迭代求最優(yōu)解，容易早熟陷入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，有利于全局最優(yōu)。其次，算法內含并行性，遺傳算法采用種群方式組織搜索，因而可同時搜索解空間的多個區(qū)域，并相互交流信息，能以較小的計算獲得較大收益。</p><p>　?。?）遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序.僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續(xù)可微的約束，而且

45、其定義域可以任意的設定，故幾乎可處理任何問題。</p><p>　?。?）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導它的搜索方向，具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得信息自行組織搜索時，適應度高的個體具有較高的生存率，并獲得更加適應環(huán)境的染色體。這種通過自然選擇與進化的機制消除了算法設計過程中的一個最大障礙，即需要事先描述問題的全部特點，并要說明針對所求問題的不同特點，我們設計的算

46、法應該采用的具體措施。所以，遺傳算法有很高的容錯能力，我們可以利用遺傳算法解決復雜的非結構化問題。</p><p>　?。?）遺傳算法可以直接用于實際應用當中，對于給定的問題，可以產生許多解，最終選擇是根據用戶自己的需求來選取，通用性高，實際應用性強，應用范圍廣。</p><p>　　2.6 遺傳算法的應用</p><p>　　遺傳算法為求解復雜系統問題提供了一種通

47、用的算法框架，它不取決于問題的具體領域，有很強的魯棒性，因而被廣泛的使用于組合優(yōu)化、機械設計、人工智能、數學建模、軟件工程等領域。</p><p><b>　?。?）函數優(yōu)化</b></p><p>　　函數優(yōu)化是遺傳算法經典的應用領域，也是使用最頻繁的領域。尤其是在數學領域，科學家構造出了許許多多復雜的測試函數：連續(xù)函數、離散函數、凸函數、凹函數、單峰函數、多峰函數

48、等等。對于這些非線性、求極值、多模型或多目標的函數優(yōu)化問題，用傳統的優(yōu)化方法很難解決，而用遺傳算法可以方便地得到較好的結果。</p><p><b>　?。?）組合優(yōu)化</b></p><p>　　隨著變量n的不斷增大，問題的規(guī)模增大，組合優(yōu)化問題的求解空間也急劇增大，應用傳統的枚舉法等就很難求出最優(yōu)解。對于這一類復雜的問題，遺傳算法已經被證實是十分有效的求解方式。遺

49、傳算法已經在求解TSP問題、01背包問題、圖形劃分問題等方面得到了成功的應用。</p><p><b>　　(3)生產調度問題</b></p><p>　　生產調度問題在很多情況下建立起來的傳統數學模難以精確求解，雖然經過一些簡化之后可以進行求解.也會因簡化得太多而使得求解結果與實際相差太大。目前在現實生產中主要是靠一些經驗來進行調度?，F在遺傳算法已成為解決復雜調度問

50、題的有效措施。在單件生產車間調度、流水線生產間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用。</p><p><b>　　（4）機器人學</b></p><p>　　機器人是一類復雜的難以精確建模的人工系統，而遺傳算法的起源就來自于人工自適應系統的研究。所以，機器人學理所當然地成為遺傳算法的一個重要應用領域。例如，遺傳算法已經在移動機器人路徑規(guī)劃、關節(jié)機器

51、人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行為協調等方而得到研究和應用。</p><p><b>　?。?）數據挖掘</b></p><p>　　數據挖掘是近幾年出現的數據庫技術，它能夠從大型數據庫中提取隱含的、先前未知的、有潛在應用價值的知識和規(guī)則。許多數據挖掘問題可看成是搜索問題，數據庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應用遺傳算法在數

52、據庫中進行搜索，對隨機產生的一組規(guī)則進行進化.直到數據庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數據庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數據挖掘下具。利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。</p><p><b>　　（6）人工生命</b></p><p>　　人工生命是用計算機、機械等人工媒

53、體模擬或構造出的具有自然生物系統特有行為的人造系統。自組織能力和自學習能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關系?；谶z傳算法的進化模型是研究人工生命現象的重要基礎理論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個有效的工具，人工生命的研究也必將促進

54、遺傳算法的進一步發(fā)展。</p><p>　　3 基于遺傳算法求解TSP問題</p><p>　　3.1旅行商問題的描述與建模</p><p>　　旅行商問題，即TSP問題又譯為旅行推銷員問題，屬于NP完全問題，是數學領域中著名的問題之一。它可以大致描述為這樣：有一個旅行商人要拜訪n個城市，他必須要經過所有的城市，而且每個城市只能拜訪一次，最后要回到原來出發(fā)的城市。要

55、求得的路徑路程為所有可能路徑之中的最小值，即最優(yōu)值問題。</p><p>　　可以用如下公式表達:</p><p><b>　　n-1</b></p><p>　　f(T)= ∑d(ti,ti+1)+d(nt,t1)</p><p><b>　　i=1</b></p><p>

56、;　　本系統是用遺傳算法求解45個城市的旅行商問題，并對其進行計算機仿真，做出一個能在計算機上運行的軟件。</p><p><b>　　3.2編碼方式</b></p><p>　　編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法時的一個關鍵步驟。因為編碼方法將會影響到交叉算子、變異算子等遺傳算子的運算方法，很大的程度上決定了遺傳進化的效率。迄今為止人們已經提出了

57、許多種不同的編碼方法。總的來說，這些編碼方法可以分為三大類：二進制編碼法、浮點編碼法、符號編碼法。下面我們從具體實現角度出發(fā)介紹其中的幾種主要編碼方法。</p><p>　　1.二進制編碼方法：</p><p>　　它由二進制符號0和1所組成的二值符號集。它有以下一些優(yōu)點：</p><p>　　(1）編碼、解碼操作簡單易行</p><p>　

58、　(2)交叉、變異等遺傳操作便于實現</p><p>　　(3)符合最小字符集編碼原則</p><p>　　(4)利用模式定理對算法進行理論分析。</p><p>　　二進制編碼的缺點是：對于一些連續(xù)函數的優(yōu)化問題，由于其隨機性使得其局部搜索能力較差，如對于一些高精度的問題（如上題），當解迫近于最優(yōu)解后，由于其變異后表現型變化很大，不連續(xù)，所以會遠離最優(yōu)解，達不到穩(wěn)

59、定。而格雷碼能有效地防止這類現象。</p><p><b>　　2.浮點編碼法：</b></p><p>　　對于一些多維、高精度要求的連續(xù)函數優(yōu)化問題，使用二進制編碼來表示個體時將會有一些不利之處。</p><p>　　二進制編碼存在著連續(xù)函數離散化時的映射誤差。個體長度較知時，可能達不到精度要求，而個體編碼長度較長時，雖然能提高精度，但卻使

60、遺傳算法的搜索空間急劇擴大。</p><p>　　所謂浮點法，是指個體的每個基因值用某一范圍內的一個浮點數來表示。在浮點數編碼方法中，必須保證基因值在給定的區(qū)間限制范圍內，遺傳算法中所使用的交叉、變異等</p><p>　　遺傳算子也必須保證其運算結果所產生的新個體的基因值也在這個區(qū)間限制范圍內。</p><p>　　浮點數編碼方法有下面幾個優(yōu)點：</p>

61、;<p>　?。?)適用于在遺傳算法中表示范圍較大的數</p><p>　?。?)適用于精度要求較高的遺傳算法</p><p>　?。?)便于較大空間的遺傳搜索</p><p>　?。?)改善了遺傳算法的計算復雜性，提高了運算交率</p><p>　?。?)便于遺傳算法與經典優(yōu)化方法的混合使用</p><p&

62、gt;　?。?)便于設計針對問題的專門知識的知識型遺傳算子</p><p>　?。?)便于處理復雜的決策變量約束條件</p><p><b>　　3.符號編碼法：</b></p><p>　　符號編碼法是指個體染色體編碼串中的基因值取自一個無數值含義、而只有代碼含義的符號集如｛A,B,C…｝。</p><p>　　符號編

63、碼的主要優(yōu)點是：</p><p>　　（1)符合有意義積術塊編碼原則</p><p>　?。?)便于在遺傳算法中利用所求解問題的專門知識</p><p>　　（3)便于遺傳算法與相關近似算法之間的混合使用。</p><p>　　但對于使用符號編碼方法的遺傳算法，一般需要認真設計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束需求，這樣才能

64、提高算法的搜索性能。</p><p>　　使用遺傳算法第一件事情就是確定染色編碼方式，它根據不同的問題模型使用不同的編碼方式，本系統使用的是Grefenstette等提出的一種新的巡回路線編碼方法，是一種整數編碼的方式。對于每個城市用一個整數來編號，例如有45個城市，就用0到45來標識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為45，如：0,1,2,3,4...44就是一個染色體，它表達的意思就是旅行

65、者從0號城市出發(fā)，依次訪問1,2,...44號城市再回到0號城市；下面具體具體介紹一下這一種編碼方法。</p><p>　　對于給定的旅行商問題，設其城市列表W，假定對各個城市的訪問順序為T：</p><p>　　T=（T1，T2，T3，…..，Tn）</p><p>　　規(guī)定每訪問完一個城市，就從城市列表W中將該城市除去，則用第i（i=1,2,3……n）個所訪問的

66、城市Ti在所有未訪問城市列表W={T1，T2，T3，…..，Ti-1}中的對應位置序號Gi（1≤Gi≤n-i+1）就可表示具體訪問哪個城市，如此這樣直到處理完W中所有的城市。將全部Gi順序排列在一起所得到的一個列表：</p><p>　　G=（G1，G2，G3，……，Gn）</p><p>　　這樣就可以表示一條巡回路線，它就是遺傳算法中的一個個體基因。例如，假設現在有這樣一個城市序列：&

67、lt;/p><p>　　W=(A,B,C,D,E,F,G,H,I,J)</p><p>　　有如下兩條巡回路線：</p><p>　　T1=(A,D,B,H,F,I,J,G,E,C)</p><p>　　T2=(B,C,A,D,E,J,H,I,F,G)</p><p>　　則按本系統所用的編碼方法，這兩條巡回路線可以編碼為

68、：</p><p>　　G1 =(1,3,1,5,3,4,4,3,2,1)</p><p>　　G2 =(2,2,1,1,1,5,3,3,1,1)</p><p>　　這種編碼方式的優(yōu)點在于任意的染色體都對應一條有實際意義的巡回路線，因此可以使用常規(guī)的交叉算子對它進行計算，有利于算法的實現。</p><p>　　3.3遺傳算子的設計（交叉、選

69、擇、變異）</p><p>　　3.3.1 交叉算子</p><p>　　交叉運算，一般指對兩個相互配對的染色體依據交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。求解旅行商問題的遺傳算法的交叉算法主要有：部分匹配交叉（PMX）、循環(huán)交叉（CX）、次序交叉（OX）、線性次序

70、交叉（LOX）、邊重組交叉（EX）等。本系統使用的是常規(guī)的單點交叉算子。</p><p>　　由于在確定算法的編碼方式的過程中使用的是Grefenstette等提出的編碼方式，用這種編碼方式表示個體時，個體的基因型和表現型之間是一一對應的，它使經過運算之后得到的每一個基因型都是一條有實際意義的巡回路線。因此，就可以使用常規(guī)的單點交叉算子。使用單點交叉，即在個體的編碼串上隨機設置一個交叉點，然后在該點相互交換兩個配

71、對個體的部分染色體。產生下一代個體在使用Grefenstette等提出的編碼方式時，染色體編碼串前面的一些基因發(fā)生變化時，會對后面的基因值產生巨大的影響，產生的新的個體與上一代的性狀變化就會十分明顯，有利于整個算法跳出局部最優(yōu)解。如下是具體代碼：</p><p>　　for(i=0;i<m_CrossNum;i++)</p><p><b>　　{ </b>&

72、lt;/p><p>　　int nPos, temp=0;</p><p>　　int parent1=0; //父代基因1</p><p>　　int parent2=0; //父代基因2</p><p>　　parent1=RandomInt(0,m_nGroupSize-1); </p><p>

73、　　temp=RandomInt(0,m_nGroupSize-1);</p><p>　　if(parent1>temp) parent1=temp;</p><p>　　parent2=RandomInt(0,m_nGroupSize-1);</p><p>　　temp=RandomInt(0,m_nGroupSize-1);</p>&l

74、t;p>　　if(parent2>temp) parent2=temp; </p><p>　　//復制用于交叉的基因對</p><p>　　PopNode pop1;</p><p>　　PopNode pop2;</p><p>　　pop1.CopyNode(&oldpop[parent1]);</p>

75、<p>　　pop2.CopyNode(&oldpop[parent2]);</p><p>　　// 基因序列中用于交叉的基因位</p><p>　　nPos=RandomInt(3,MAXCHROM-3); </p><p>　　pop1.CrossTwo(&pop2, nPos); </p><p>　　/

76、/交叉完成,保存結果</p><p>　　newpop[m_nGroupSize+2*i].CopyNode(&pop1);</p><p>　　newpop[m_nGroupSize+2*i+1].CopyNode(&pop2);</p><p>　　3.3.2 選擇算子</p><p>　　選擇操作是建立在對個體適應度進行

77、評價的基礎之上的。選擇操作的目的是為了避免基因缺失、提高全局收斂性和計算效率。本課題采用最常用的選擇算子——比例選擇算子（又稱輪盤賭選擇）。其基本思想是：各個個體被選中的概率與其適應度大小成正比。適應度越高的個體被選中的概率也越大；反之，適應度越低的個體被選中的概率也越小。具體操作如下：</p><p>　　計算出群體中每個個體的適應度f(i=1，2，…，M)，M為群體大?。?lt;/p><p&g

78、t;<b>　　歸一化適應度f的值</b></p><p>　　將適應度f的值從大到小排列，查找其中最小費用的個體然后將其作為下一代選擇出來。</p><p><b>　　具體代碼如下：</b></p><p>　　for(int gen=0;gen<m_GANum;gen++)</p><p&g

79、t;<b>　　{ </b></p><p>　　// 計算當前一代群體中個體的適應度數值F</p><p>　　for(int i=0;i<m_nGroupSize;i++)</p><p>　　TotalF+=1/oldpop[i].CalcCost(m_distance);</p><p><b&g

80、t;　　// 歸一化F值</b></p><p>　　for(i=0;i<m_nGroupSize;i++) </p><p>　　oldpop[i].fit=1/oldpop[i].cost/TotalF*100;</p><p>　　// 將當前一代群體中的個體按F值從大到小排序</p><p>　　for(i=0;i&

81、lt;m_nGroupSize-1;i++) </p><p><b>　　{</b></p><p>　　double max=0.0;</p><p>　　int maxpos;</p><p>　　for(int j=i;j<m_nGroupSize;j++) if(oldpop[j].fit>max)

82、</p><p><b>　　{</b></p><p>　　max=oldpop[j].fit; maxpos=j;</p><p><b>　　}</b></p><p>　　if(i!=maxpos) oldpop[i].SwapNode(&oldpop[maxpos]);</p

83、><p><b>　　}</b></p><p>　　m_CurGANum=gen;</p><p>　　// 查找當前一代中的最小費用個體</p><p>　　m_MiniCost=oldpop[0].cost;</p><p>　　m_pop.CopyNode(&oldpop[0]);&l

84、t;/p><p>　　m_GAFitness=m_pop.fit;</p><p>　　//AfxMessageBox("顯示數據");</p><p>　　UpdateData(false);</p><p>　　UpdateWindow();</p><p>　　if (m_CurGANum ==

85、m_GANum - 1)</p><p><b>　　{</b></p><p><b>　　// 繪制圖形</b></p><p>　　DrawNetwork();</p><p><b>　　}</b></p><p>　　//繼承所有父代基因<

86、;/p><p>　　for(i=0;i<m_nGroupSize;i++) newpop[i].CopyNode(&oldpop[i]);</p><p>　　3.3.3 變異算子</p><p>　　變異運算，是指改變個體編碼串中的某些基因值，從而形成新的個體。變異運算是產生新個體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。交叉運算可以和

87、變異運算相互配合，共同完成對搜索空間的全局搜索和局部搜索。本系統中變異算子采用基本位變異算子?；疚蛔儺愃阕邮侵笇€體編碼串隨機指定的某一位或某幾位基因作變異運算。因為使用由Grefenstette等所提出的編譯方法來表示個體，一個個體經過遺傳運算后所得到的任意一個基因型個體與交叉后的情況相同，都能夠對應于一條具有實際意義的巡回路線。對于二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，

88、若原有基因值為1，則將其變?yōu)? ?；疚蛔儺愃阕拥膱?zhí)行過程如下：</p><p>　?。?）對個體的每一個基因座，依變異概率Pm指定其為變異點。</p><p>　?。?）對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產生出一個新個體。</p><p>　　針對旅行商問題對變異算子的設計要求，基本位變異即交換變異。變異是單個個體內部發(fā)生變化

89、，導致產生新個體，從而產生出一條新的巡回路線。例如：</p><p>　　Tx=（B C A D E J H I F G）</p><p>　?。˙ C A I E J H D F G）=Tx′</p><p><b>　　具體代碼如下：</b></p><p>　　for(i=0;i&

90、lt;m_VariNum;i++)</p><p><b>　　{</b></p><p>　　int nPos1,nPos2,parent=0; //變異父代基因</p><p>　　parent=RandomInt(0,m_nGroupSize-1) （定義變異范圍）</p><p>　　nPos1=Rand

91、omInt(3,MAXCHROM-3); （取其中第三位與倒數第三位做</p><p>　　nPos2=RandomInt(3,MAXCHROM-3); 為變異結點）</p><p>　　PopNode pop;</p><p>　　pop.CopyNode(&oldpop[0]);</p><p>　　pop.Varite(nPo

92、s1,nPos2);（執(zhí)行結點操作）</p><p>　　newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(&pop);（保存變異結果）</p><p><b>　　}</b></p><p><b>　　3.4 適應度函數</b></p><p>　

93、　在遺傳算法中，以個體適應度的大小來確定該個體被遺傳到下一代群體中的概率。個體的適應度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應度越小，該個體被遺傳到下一代的概率也越小。因此適應度函數的選擇至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。本系統中以每條路徑長度的倒數作為適應度函數值，并對其進行統一化的操作，即按從大到小進行排序，為下一步選擇操作做準備。為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應度必

94、須為正數或零，不能是負數。具體代碼如下所示：</p><p>　　for(int i=0;i<m_nGroupSize;i++) （nGroupSize是城市之間的距離）</p><p>　　TotalF+=1/oldpop[i].CalcCost(m_distance);（父代結點的城市距離的倒數作為它的適應度）</p><p>　　3.5 遺傳算法求解TS

95、P問題的具體流程圖</p><p>　　圖3-5 遺傳算法求解旅行商問題的具體流程圖</p><p>　　4 45個城市旅行商問題的仿真軟件的設計</p><p>　　4.1 系統設計模塊</p><p>　　本系統在Microsoft Visual C++環(huán)境下完成，根據需求設計了三大模塊：算法設計模塊、演示模塊、幫助模塊。算法設計模塊完

96、成群體規(guī)模M、交叉概率Pc、變異概率Pm和進化代數T的設置；具體的參數已經設置在了演示平臺上，可以根據需要更改參數大小，但是盡量在設定的范圍之內，這樣可以保證算法的精確性；幫助模塊則設置了關于軟件和制作作者等查看項目。下圖是系統的功能模塊圖。</p><p>　　圖4-1系統功能模塊圖</p><p>　　4.2 系統詳細設計</p><p>　　由前文中介紹的個體

97、編碼方法及各種遺傳算子可以構成許多種不同的求解旅行商問題的遺傳算法，本系統主要利用這些遺傳算子對含有45座城市的旅行商問題進行了試算。</p><p>　　本系統中所使用的遺傳算法是由以下要素所構成的：</p><p><b>　　●編碼方法</b></p><p>　　基本遺傳算法使用由Grefenstette所提出的編碼方法，詳細設計見第四

98、章編碼方式一節(jié)。</p><p><b>　　●適應度函數</b></p><p>　　系統中以每條路徑長度的倒數作為適應度函數值。</p><p><b>　　●選擇算子</b></p><p><b>　　采用適應度比例法</b></p><p>&

99、lt;b>　　●交叉算子</b></p><p>　　采用常規(guī)單點交叉操作算子。</p><p><b>　　●變異算子</b></p><p>　　使用基本位交換變異操作算子</p><p><b>　　●運行參數</b></p><p>　　{M，T，P

100、c，Pm}={0~500，0~300，0.2~0.4，0.01~0.08}，式中M為群體大小，T為終止代數，Pc為交叉概率，Pm為變異概率。本系統給出各個參數的參考范圍，在此范圍內執(zhí)行搜索最佳，超出范圍也可演示，但這會影響搜索效果，可能得不到最優(yōu)解或近似最優(yōu)解。極端情況不可執(zhí)行。這些在上文中已作過詳細介紹,這里就不再重復。</p><p>　　4.2.1演示模塊設計</p><p>　?。?/p>

101、1）主窗口設計：在VC工具欄insent中插入窗口IDD_CHINA45_DIALOG，再在上面設置變量，并進行初始化。具體變量及其窗口對話框設置如下表。</p><p>　　表4.2.1為工程添加IDD_CHINA45_DIALOG的菜單選項</p><p>　　表4.2.2通過類查看（ClassView）選項卡，向主對話框添加成員變量</p><p>　　初始化

102、參數設置代碼如下：</p><p>　　m_GALen = 45; </p><p>　　m_nGroupSize = 100; </p><p>　　m_GACrossProb = 0.6;</p><p>　　m_GAVariProb = 0.

103、03;</p><p>　　m_GANum = 100;</p><p>　　m_CurGANum = 0;</p><p>　　m_MiniCost = 0.0;</p><p>　　m_CrossNum = 0;</p><p>　　m_VariNum = 0;</p><p>　　m_GA

104、Fitness = 0.0;</p><p>　　變量與對話框進行綁定：</p><p>　　DDX_Text(pDX, IDC_EDIT1, m_GALen);</p><p>　　DDX_Text(pDX, IDC_EDIT2, m_nGroupSize);</p><p>　　DDX_Text(pDX, IDC_EDIT3, m_GAC

105、rossProb);</p><p>　　DDX_Text(pDX, IDC_EDIT4, m_GAVariProb);</p><p>　　DDX_Text(pDX, IDC_EDIT5, m_GANum);</p><p>　　DDX_Text(pDX, IDC_EDIT6, m_CurGANum);</p><p>　　DDX_Text

106、(pDX, IDC_EDIT7, m_MiniCost);</p><p>　　DDX_Text(pDX, IDC_EDIT8, m_CrossNum);</p><p>　　DDX_Text(pDX, IDC_EDIT9, m_VariNum);</p><p>　　DDX_Text(pDX, IDC_EDIT10, m_GAFitness);</p>

107、<p>　　打開類向導（Class Wizard）對話框向主對話框類添加響應函數，用于顯示新生成的群體規(guī)模、交叉變異數目等。具體代碼如下：</p><p>　　void CChina45Dlg::OnMenuGaset() </p><p><b>　　{</b></p><p>　　// TODO: Add your comma

108、nd handler code here</p><p>　　CGASetDlg dlg;</p><p>　　if(dlg.DoModal()==IDOK)</p><p><b>　　{</b></p><p>　　m_nGroupSize=dlg.m_nGroupSize; （將新的群體規(guī)模賦值給對話框）<

109、/p><p>　　m_GACrossProb=dlg.m_GACrossProb; （將新的交叉概率賦值給對話框）</p><p>　　m_GAVariProb=dlg.m_GAVariProb; （將新的變異概率賦值給對話框）</p><p>　　m_GANum=dlg.m_GANum; （將新的遺傳代數賦值給對話框）</p>&l

110、t;p>　　UpdateData(false);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　在主窗口上拖一個按鈕進去，按鈕名為OnButtonGa(遺傳算法演示按鈕)并對其添加響應函數聲明,該函數執(zhí)行最短路徑更新的操作,即執(zhí)行一次算法,顯示一次運算結果：<

111、;/p><p>　　void CChina45Dlg::OnButtonGa() </p><p><b>　　{</b></p><p>　　PopNode *oldpop;</p><p>　　oldpop=new PopNode[m_nGroupSize];</p><p>　　for(int

112、k=0;k<1;k++)</p><p><b>　　{</b></p><p>　　ExecGA(k, oldpop);</p><p><b>　　}</b></p><p>　?。?）主窗口菜單設置：在菜單欄中需要做三個選項：文件、設置和幫助。在文件下面繼續(xù)添加菜單退出，并設置ID為ID

113、_MENU_EXIT；文件下邊添加菜單遺傳算法設置，設置ID為ID_MENU_GASET；幫助下邊添加菜單關于軟件和關于作者，設置ID分別為ID_MENU_SOFT、ID_MENU_WRITE。</p><p>　?。?）遺傳算法參數設置窗口的設計：在菜單遺傳算法設置下插入一個窗口IDD_DIALOG_SET,具體設置如下表所示：</p><p>　　表4.2.3 為工程添加IDD_DIA