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

摘要:文章首先介紹TSP問題與遺傳算法的基本特點及其基本步驟。接著討論用遺傳算法解決TSP問題的編碼、適應度函數(shù)設計方面的采用的方法，以及選擇算子，交叉算子和變異算子的應用現(xiàn)狀以及效果，最后對解決TSP問題的前景提出了展望。

關鍵詞:TSP;遺傳算法;遺傳操作;算子

中圖分類號:TP311 文獻標識碼:A文章編號:1009-3044(2010)03-672-02

Application in TSP Based on Genetic Algorithm

LI Hua-zhong， YANG Jing-hua

(Computer Science and Technology Institute of Hua Yu College from Henan Agricultural University， Shangqiu 476113， China)

Abstract: First， the passage introduced the problem of TSP， the basic feature and procedure of Genetic algorithm. Then discussed the way of coding， the function of fitness of solving TSP by Genetic algorithm. The application and effect of selection operator， crossover operator and mutation operator. At last， how to solve TSP in the future will be given.

Key words: TSP; genetic algorithm; genetic operation; operator

旅行商問題(TSP)，也稱為貨郎擔問題，是一個較古老的問題。最早可以追溯到1759年Euler提出的騎士旅行問題。1948年，由美國蘭德公司推動，TSP成為近代組合優(yōu)化領域的一個典型難題。應該說，TSP是一個具有廣泛應用背景和重要理論價值的組合優(yōu)化難題，它已經(jīng)被證明屬于NP難題。對TSP問題的大量研究使得TSP問題成為了一個著名的組合優(yōu)化問題目前，求解TSP問題的較為常用的方法有二叉樹描述法、啟發(fā)式搜索法、最近鄰法、神經(jīng)網(wǎng)絡法、模擬退火法和遺傳算法等。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局概率搜索算法，具有良好的全局尋優(yōu)能力，成為解決問題的有效方法之一。

1 TSP問題描述

TSP(旅行商問題)的簡單描述是:一名商人欲到n個城市推銷商品，每兩個城市i和j之間的距離為d，存在i，j如何使商人每個城市走一遍后回到起點，且所走的路徑最短。用數(shù)學符號表示為:設n維向量表示一條路徑X=(C₁， C₂， ……，C_n)，目標函數(shù)為

minF(x)=∑ⁿ⁺¹_i=1d(C_i，C_i+1)+d(C₁+ C_n)

用圖語言來描述TSP，給出一個圖G=(V， E)，每邊e∈E上有非負權值w(e)，尋找G的Hamilon圈C，使得C的總權W(C)=∑e∈E(C) w(e)最小。TSP搜索空間隨著城市數(shù)n的增加而增大，所有的旅程路線組合數(shù)為(n-1)!/2。5個城市的情形對應120/10=12條路線，10個城市的情形3628800/20=181440條路線，100個城市的情形則對應有4.6663×10155條路線。在次龐大的搜索空間中尋求最優(yōu)解，對于常規(guī)方法和現(xiàn)有的搜索而言，存在諸多的計算困難。借助遺傳算法的搜索能力解決TSP問題是很自然的想法。

2 遺傳算法的特點及基本步驟

2.1 遺傳算法的特點

遺傳算法是模擬達爾文的“適者生存” 的自然進化論與蒙德爾的遺傳變異理論而提出的一種求解復雜系統(tǒng)全局優(yōu)化問題的通用計算框架。它的主要特點是群體搜索策略和群體中個體之間的信息交換。它適用范圍于處理傳統(tǒng)搜索方法難于解決的復雜和非線性問題。可廣泛用于組合優(yōu)化，機器學習.自適應控制，規(guī)劃設計和人工生命等領域。遺傳算法是一種有向隨機搜索法，其遺傳算子原則上執(zhí)行盲目搜索，體現(xiàn)了隨機搜索的特點，故能廣泛搜索整個解空間而跳出局部。通過不斷計算各染色體的適應值，選擇最好的染色體，從而獲得最優(yōu)解。基于遺傳算法的本質是處理復雜問題的一種啟發(fā)性隨機搜索算法故用于TSP是有效的。

2.2 遺傳算法的基本步驟

遺傳算法是通過借鑒生物界自然選擇和自然遺傳機制而產(chǎn)生的一種計算方法，與其他的優(yōu)化算法一樣，遺傳算法也是一種迭代算法。從選定的初始解出發(fā)，通過不斷地迭代，逐步改進當前解，直到最后搜索到最優(yōu)解或滿意解。其迭代過程是從一組初始解(群體)出發(fā)，采用類似于自然選擇和有性繁殖的方法，在繼承原有優(yōu)良基因的基礎上生成具有更好性能的下一代解的群體。遺傳算法的運算過程為:對給定問題，給出變量的編碼方法，定義適應度函數(shù)。1)初始化。令t=0，給出正整數(shù)(最大迭代次數(shù))，交叉概率Pc及變異概率Pm，隨機生成M個個體作為初始群體P(0);2)個體評價。計算P(t)中各個體的適應度;3)選擇。對群體P(t)進行選擇操作，得到中間群體;4)交叉。把交叉操作作用于中間群體;5)變異。把變異操作作用于交叉之后所得到的群體，則得到第(t+1)代群體P(t+1);6)若t

3 遺傳算法用于TSP問題

3.1 編碼表示

用遺傳算法求解TSP時，算法的編碼表示是算法設計的重點，它對遺傳基因的操作有一定的限制。TSP的編碼策略主要包括二進制表示、順序表示、路徑表示、矩陣表示和邊表示等。由于二進制編碼具有如下的特點數(shù)據(jù)冗長，并且表達能力有限，計算機無法承受如此巨大的計算量甚至根據(jù)調整不同的參數(shù)時，所運行的時間，有時會達到近幾個小時，從時間效率來說，工作效率實在是低下，并達到無法忍受的程度，所以實際中很少使用。順序表示是指將所有城市依次排列構成一個順序表，對于一條旅程，可以依次旅行經(jīng)過順序處理每個城市，每個城市在順序表中的順序就是一個遺傳因子的表示。每次處理完一個城市，從順序表中去掉該城市。處理完所有城市后，將每個城市的遺傳因子連接起來，即成為一條旅程的基因表示(染色體編碼)。

路徑表示是表示旅程歲應的基因編碼的最自然，最簡潔的表示方法。

3.2 初始化群體和適應度函數(shù)及其終止條件的設定

根據(jù)編碼方法，隨機產(chǎn)生初始群體，直到達到所需規(guī)模為止。適應度函數(shù)，由于是求最短路徑，適應度函數(shù)一般采用求函數(shù)最大值，例如取路徑總長度T的倒數(shù)，即fitness=l/T。其中，

T=∑ⁿ⁺¹_i=1d(C_i，C_i+1)+d(C₁+ C_n)

適應度越小的個體，該個體的路徑越短，該個體則越好。也有采用fitness=l/T2計算適應度的算法。也有的算法采用fitness=1/(T+aN)，其中N為未遍歷的城市的個數(shù)，a為懲罰函數(shù)系數(shù)，常取城市間最長距離的兩倍多，路徑T越大，適應度函數(shù)越小。

迭代停止條件一般是:若某代群體中的最差個體與最好的個體適應度的差不大于某個數(shù)(根據(jù)問題規(guī)模變化)，則終止算法。若最佳個體連續(xù)保持一定代數(shù)，則終止算法。若算法迭代次數(shù)達到一定代數(shù)，則終止算法。

3.3 選擇算子

選擇是從一個舊種群(old population)中選擇生命力強的個體位串產(chǎn)生新種群的過程。或者說，選擇是個體根據(jù)其適值函數(shù)f拷貝自己的過程。直觀地講，可以把適值(或目標)函數(shù)f看作是我們期望的最大效益或好處的某種量度。根據(jù)個體的適值拷貝位串意味著:具有高的適值的個體更大可能在下一代中產(chǎn)生一個或多個子孫。顯然這個操作是模仿自然選擇現(xiàn)象，將達爾文的適者生存理論運用于個體的選擇。

對于求解TSP問題， 常用的選擇機制有輪盤賭選擇機制、隨機遍歷抽樣法、局部選擇法、截斷選擇法、錦標賽選擇法等。遺傳算法中一個較難解決的問題是如何較快地找到最優(yōu)解并防止“早熟”收斂問題。為了保證遺傳算法的全局收斂性，就要維持解群體的個體多樣性。這種做法會明顯改善遺傳算法的行為，因為其增加了體在種群中的分布區(qū)域，但增加了計算時間。

3.4 交叉算子

Goldberg提出基于路徑表示的部分映射交叉(partially—mapped， PMX)，首先隨機地在父個體中選取兩雜交點，并交換相應的段。再根據(jù)該段內的城市確定部分映射。在每代父個體上先填入無沖突的城市。而對有沖突的城市分別執(zhí)行這些部分映射直到填人無沖突，剛可獲得交叉后的兩后代。由Davis提出順序交叉(order， OX)，它與PMX操作非常類似。也是首先隨機地在父個體中選擇兩雜交點，再交換雜交段，其它位置根據(jù)保持父代個體中城市的相對次序來確定。由Oliver等提出的循環(huán)交叉(CX)，將另一個父個體作為參照以對當前父個體中的城市進行重組。先與另一父個體實現(xiàn)一個循環(huán)鏈.并將對應的城市填入相應的位置，循環(huán)組成后.再將另一父體的城市填入相同的位置。

上述幾種TSP操作基本上考慮的是城市的位置和順序，未考慮城市間的連接。Grefenstette認為遺傳算法應用與TSP，其遺傳操作不僅要考慮城市間的位置，而且有必要考慮城市間的關系，城市間的關系定義為邊，讓子個體繼承父個體中邊的信息設計邊的遺傳操作很有意義。1989年，Whitle等提出了一種邊重組(Edge Recombination.ER)交叉操作，使個體能夠從父個體繼承95%～99%的邊信息。ER操作是根據(jù)繼承兩個父個體定義的旅程中城市間的相鄰關系生成子個體。1991年，Stark weather等提出了一種改進的方法，在ER操作中不再保留父個體中共同部分的序列。實驗結果表明這種處理方法比隨機選擇的處理的性能有相當?shù)母纳啤?/p>

3.5 變異算子

盡管復制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異是用來防止這種不可彌補的遺漏，在簡單遺傳算法中，變異就是某個字符串某一位的值偶然的(概率很小的)隨機的改變，即在某些特定位置上簡單地把1變成0，或反之。變異是沿著個體字符空間的隨機移動，當它有節(jié)制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要概念的保險策略。

變異本身是一種局部隨機搜索，與選擇/重組算子結合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力;同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。在變異操作中，變異率不能取得太大。變異算子的設計要比交叉算子的設計靈活得多。簡單的倒位操作，即首先在父個體中隨機地選擇兩截斷點，然后將該兩點所夾的子串中的城市進行反序。也有一種貪婪倒位變異算子，它的主要思想是:首先隨機選擇一個城市C，然后在除外的其他城市中選除C、cRight、cLeft以外的距離C最近的城市C’，在對cRight到C’之間的城市進行倒位。

4 總結與展望

對于TSP，目前還不存在能找到完美解的方法，這個問題是NP難的。為了進一步提高算法的全局優(yōu)化能力，避免搜索過程陷入局部極小，現(xiàn)已提出的改進策略主要有:并行多鄰域搜索、平滑優(yōu)化曲面形狀、熵抽樣等高級技術。對于復雜優(yōu)化問題，單一機制的優(yōu)化算法很難實現(xiàn)全局優(yōu)化，且效率較低。多種優(yōu)化機制和鄰域搜索結構相混合，是能較大程度提高全局優(yōu)化度和魯棒性的有力途徑，并可一定程度上放松對單一算法參數(shù)選擇的苛刻性，所以混合優(yōu)化策略會是一種趨勢。

總之，對于TSP問題，可從問題的編碼及遺傳算子設計方面來改進發(fā)展遺傳算法。尤其包含啟發(fā)式信息，盡量讓子代繼承父代的優(yōu)良特性。通過保持邊的有用信息找到更好的算法，這是算法改進的一個趨勢，同時為了防止局部收斂必須讓算法達到收斂性與群體多樣性的平衡。

參考文獻:

[1] 王小平，曹立明.遺傳算法-理論、應用及軟件實現(xiàn)[M].西安:西安交通大學出版社，2002.

[2] 田貴超，黎明.旅行商問題(TSP)的幾種求解方法[J].計算機仿真，2006(8):153-157.

[3] 易敬，王平.基于遺傳算法的TSP問題研究[J].信息技術，2006(7):110-112.

[4] 李飛，白艷萍.用遺傳算法求解旅行商問題[J].中北大學學報，2007(1):49-52.

[5] 敖友云，遲洪軟.基于遺傳算法求解TSP問題的一種算法[J].計算機與數(shù)字工程，2006(4):52-55.