第9章旅行商問題9.1TSP的構造啟發式算法9.2線性規劃模型9.3TSP路徑構造的貪婪啟發式算法9.4TSP的改進啟發式算法9.5TSP的遺傳算法

9.1TSP的構造啟發式算法

旅行商問題(TravelingSalesmanProblem,TSP)是這樣一個問題:給定一系列城市和每對城市之間的距離,求解訪問每一座城市一次并回到起始城市的最短回路。TSP是運籌學中目前研究最為廣泛的問題之一,但對于一般情況,還沒有有效的解決方法。雖然TSP的復雜性未知,但60多年來,其求解方法在不斷改進。表9-1顯示了TSP問題的求解記錄。

9.2線性規劃模型

此模型的決策變量有n(n-1)個,式(9-2)和式(9-3)均有n個,連通性約束有2n-2n-2個,因此共有2n-2個約束條件,即使對于n=318這樣小規模的TSP問題,也有5.34e+95個約束條件,比宇宙中的原子數量還要多!

一般來講,通過算法構建一條可行的旅行商路徑并不困難,雖然一般情況下證明是最優的很困難。在這種情況下,我們不知道找到的路徑是否是最優解,但是知道這個解還不錯,因此可以稱之為優化解,它可能是最優的,也可能不是,并且很多情況下,可以通過解的下界大概估計優化解的優化程度。

9.3TSP路徑構造的貪婪啟發式算法

9.3.1最近鄰算法所謂最近鄰算法,就是從一個點開始逐步增加距離當前點最近的點構造出一個TSP路徑。

例9-1在Matlab上實現最近鄰函數,并隨機生成城市節點進行驗證。

使用Matlab編寫最近鄰函數的代碼如下:

在平面上隨機生成30個點,使用最近鄰方法構造TSP路徑的代碼如下:

進行4次實驗,算法構造生成的TSP路徑如圖9-1所示。圖9-1最近鄰算法生成的幾個TSP路徑

9.3.2插入算法

插入算法是從一個較小的圈開始,逐步將不在圈上的點插入圈上,直到擴充為一條TSP路徑為止。

例9-2在Matlab上實現插入函數,并隨機生成城市節點進行驗證。

在平面上隨機生成30個點,使用插入算法構造TSP路徑的代碼如下:

進行4次實驗,算法構造生成的TSP路徑如圖9-2所示。由圖可見,生成的不是最優解,而是優化解。圖9-2插入算法生成的幾個TSP路徑

9.3.3Merger算法

9.4TSP的改進啟發式算法

9.4.12opt操作

例9-3在如圖9-3所示的TSP路徑上,查看有沒有兩條邊能滿足交叉消除操作的條件。圖9-3TSP路徑的交叉消除操作

如圖9-3所示,當前TSP路徑上有(1,2)和(3,4)兩條邊在平面上是有交叉的,于是根據三角不等式可得

因此,在TSP路徑上去掉(1,2)和(3,4)兩條邊,并增加(1,3)和(2,4)兩條邊,TSP路徑的總長度縮短,解得到改進。

例9-4在Matlab上實現2opt函數,并隨機生成城市節點進行驗證。

進行實驗,結果如圖9-4所示,可以發現在平面上已經沒有交叉了。圖9-42opt操作通過消除平面交叉改進TSP路徑

9.4.2k－opt操作

所謂k－opt操作,就是在TSP路徑上去掉k條邊,并使用另外的k條總長度更小的邊將其代替并重新連接成一條可行TSP路徑的操作。

如果一條TSP路徑無法通過kopt操作改進,則稱其為k－optimal的。如果一條TSP路徑是koptimal的,則對于比k小的自然數k',這條路徑一定也是k'optimal的。

如果一條TSP路徑是n－optimal的,則這條TSP路徑是最優的。

雖然能夠驗證k－optimal中的k越大,解越接近最優,但是隨著k的增大,k－optimal的驗證難度呈指數級增加,因此一般情況下只利用k=2,3來改進。

9.5TSP的遺傳算法

9.5.1基本原理與步驟TSP路徑構造的貪婪啟發式算法通過貪婪規則從無到有構造一個優化解,TSP的改進啟發式算法對一個已有的解進行改進,而TSP的遺傳算法中上述兩個算法的工作都要做,因此,也稱之為元啟發式算法。遺傳算法計算的過程框架如圖9-5所示。

圖9-5遺傳算法(元啟發式算法)計算的過程框架

遺傳算法的基本步驟如下:

步驟1:將問題的解編碼為染色體,并生成初始染色體群,每個染色體代表一個解。

步驟2:進行交叉、變異、選擇等操作,計算每個染色體的適應度函數值,更新染色體群。

步驟3:直到滿足算法停止條件的時候,停止計算,最優的染色體代表的解即為所得的優化解,否則轉步驟2。

9.5.2算法設計要點

1.解的編碼

在旅行商問題中,對問題解的編碼應該采用城市編號序列的方法,這樣更加有利于交叉、變異等操作生成可行解,否則一個交叉之后,生成可行解的概率很低。

2.生成初始種群

所謂生成初始種群,就是生成一定數量的可行解,一般隨機生成,而不太采用構造啟發式算法。作為全局性算法,隨機生成初始種群的方式有可能會避免過早陷入局部最優解。

3.交叉操作

一般的交叉操作是選擇兩個染色體作為父母,從隨機的位置截斷后,重新組合到一起。但是對于旅行商問題的兩個染色體來講,如果采用一般的交叉操作,多數情況下會得到一

個不可行的解,例如:

作為父母染色體,從第一個基因與第