運(yùn)籌學(xué)基礎(chǔ) 課件 第9章

第9章旅行商問題9.1TSP的構(gòu)造啟發(fā)式算法9.2線性規(guī)劃模型9.3TSP路徑構(gòu)造的貪婪啟發(fā)式算法9.4TSP的改進(jìn)啟發(fā)式算法9.5TSP的遺傳算法

9.1TSP的構(gòu)造啟發(fā)式算法

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

9.2線性規(guī)劃模型

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

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

9.3TSP路徑構(gòu)造的貪婪啟發(fā)式算法

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

例9-1在Matlab上實現(xiàn)最近鄰函數(shù),并隨機(jī)生成城市節(jié)點進(jìn)行驗證。

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

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

進(jìn)行4次實驗,算法構(gòu)造生成的TSP路徑如圖9-1所示。圖9-1最近鄰算法生成的幾個TSP路徑

9.3.2插入算法

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

例9-2在Matlab上實現(xiàn)插入函數(shù),并隨機(jī)生成城市節(jié)點進(jìn)行驗證。

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

進(jìn)行4次實驗,算法構(gòu)造生成的TSP路徑如圖9-2所示。由圖可見,生成的不是最優(yōu)解,而是優(yōu)化解。圖9-2插入算法生成的幾個TSP路徑

9.3.3Merger算法

9.4TSP的改進(jìn)啟發(fā)式算法

9.4.12opt操作

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

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

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

例9-4在Matlab上實現(xiàn)2opt函數(shù),并隨機(jī)生成城市節(jié)點進(jìn)行驗證。

進(jìn)行實驗,結(jié)果如圖9-4所示,可以發(fā)現(xiàn)在平面上已經(jīng)沒有交叉了。圖9-42opt操作通過消除平面交叉改進(jìn)TSP路徑

9.4.2k－opt操作

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

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

如果一條TSP路徑是n－optimal的,則這條TSP路徑是最優(yōu)的。

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

9.5TSP的遺傳算法

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

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

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

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

步驟2:進(jìn)行交叉、變異、選擇等操作,計算每個染色體的適應(yīng)度函數(shù)值,更新染色體群。

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

9.5.2算法設(shè)計要點

1.解的編碼

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

2.生成初始種群

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

3.交叉操作

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

個不可行的解,例如:

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