遺傳算法在tsp問題中的應用

《遺傳算法在tsp問題中的應用》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、遺傳算法在TSP問題中的應用周師專（南昌大學信息工程學院軟件工程416116114082）摘要：旅行商問題是研究最為廣泛的組合優(yōu)化問題，在現(xiàn)實生活中，也有著廣泛的應用。遺傳算法是一種有效的解決優(yōu)化問題的方法。遺傳算法是求解NP完全問題的一種常用方法，它在解決排列組合問題方面占有很重要的地位。本文針對旅行商問題，分別對個體的基因編碼、適應值，以及選擇、交叉、變異算子進行了設計，將此程序應用到旅行商問題的研究中。關鍵詞：遺傳算法；旅行商問題；交叉；變異；組合優(yōu)化引言旅行商問題（TravellingSalesmanProblem）是數(shù)學領域中著名問題之一

2、，可描述為:有一個旅行商人要拜訪個城市，從〃個城市中的某一城市出發(fā)，不重復地走完其余n-1個城市并回到原山發(fā)點，在所有可能路徑中求岀路徑長度最短的一條。TSP問題是一個相當古老的優(yōu)化問題，在過去的10年中，出現(xiàn)了一些逼近最優(yōu)解的算法：最近鄰居、貪婪算法、最近插入、最遠插入、雙最小生成樹、帶解法、空間充填曲線算法等。而后來發(fā)展起來的遺傳算法，是一種求解M題的高效并行全局搜索方法，能夠解決復雜的全局優(yōu)化問題。一、遺傳算法概述遺傳算法（GeneticAlgorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自

3、然進化過程（適者生存，優(yōu)勝劣汰遺傳機制）搜索最優(yōu)解的方法，通常用來生成有用的解決方案來優(yōu)化和搜索問題。從選定的初始解山發(fā),通過不斷地迭代，逐步優(yōu)化當前解，直到最后搜索到最優(yōu)解或滿意解。其迭代過程是從一紐初始解（群體）出發(fā)，采用類似于自然選擇和有性繁殖的方法，在繼承原有優(yōu)良基因的基礎上生成具有更好性能的丁一代解的群體。遺傳算法的基本運算過程如卜‘：a）初始化：設置進化代數(shù)計數(shù)器F0,設置最大進化代數(shù)7；隨機生成個個體作力初始群體汽0）。b）個體評價：計算群體中各個個體的適應度。C)選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一

4、代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算:將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。群體經過選擇、交叉、變異運算之后得到下一代群體八01人e)變異運算:將變異算子作川于群體。即是對群體屮的個體串的某些基因座上的基因值作變動。f)終止條件判斷:若則以進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。運算停止。算法流程圖如圖1所示。圖1二、問題分析TSP問題就是尋找一條最短的遍歷n個城市的最短路徑，即搜索自然數(shù)子集W={1,2,…，n}(W的元素表示對n個城市的

5、編號)的一個排列it(W)={VI，V2,…，Vn},使len=Sd(Vi,Vi+1)+d(VI,Vn)取最小值，式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距離。遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。該操作以群體中的所有個體為對象。選擇(Selection)、交叉(Crossover)和變異(Mutation)是遺傳?算法的3個主要操作算子，它們構成了所謂的遺傳操作(geneticoperation),使遺傳算法具有了其它傳統(tǒng)方法所沒有的特性。遺傳算子包含如下6個基本因素：(1)參數(shù)編碼：由于遺傳算法不能直接處理解空間的解數(shù)

6、據(jù)，因此必須通過編碼將它們表示成遺傳空間的基因型串結構數(shù)據(jù)。巾于旅行商問題的解是一個序列，且序列的內容相同順序不同，所以二進制編碼對TSP不是最適合的。這里以城市的遍歷次序作為算法編碼，即(il,i2,…，in)是{1,2,…,n}的全排列。(1)生成初始群體：由于遺傳算法的群體型操作需要，所以必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是通過隨機方法產生。(2)適應度評估檢測：遺傳算法在搜索進化過程屮僅用適應度(ntness)值來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。巾于用個體r相對應的哈密頓圈長的倒數(shù)作力適應度

7、較大，容易早收斂而得到局部最優(yōu)解，所以川exp(-evaluate(father[i]))作為適應度函數(shù)，其中father[i]為種群中的一個個體，evaluate()是一個序列中城市之間的距離總和。(3)選擇(selection):選擇或復制操作是為了從當前群體屮選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。個體適應度越高，其被選擇的機會就越多。此處采用與適用度成比例的輪盤賭方法進行選擇。(4)交叉操作：交叉操作是遺傳算法屮最主要的遺傳操作?？煞謨刹竭M行：首先對種群屮個體進行隨機配對;其次，在配對個體屮隨機設定交叉處，配對個體彼此交換部分

8、信息。(5)變異：變異操作是按位(bit)進行的，即把某一位的內荇進行變異。由于TSP問題的解是一個序列，所以由一個解序列