侯淑靜

(西藏民族學(xué)院財(cái)經(jīng)學(xué)院，陜西咸陽712082)

TSP問題［1］描述:一個(gè)商人欲到n個(gè)城市推銷商品，每兩個(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市僅走一遍后回到起點(diǎn)且所走路徑最短。TSP問題分為對(duì)稱和非對(duì)稱距離兩大類，當(dāng)對(duì)所有的城市i和j都有dij=dji時(shí)，稱為對(duì)稱TSP問題，否則稱為非對(duì)稱TSP問題。

TSP問題是一個(gè)典型的易于描述卻難以大規(guī)模處理的NP難問題。本文通過四種算法求解對(duì)稱TSP問題，并對(duì)這幾種算法作簡單分析和比較。在所測(cè)試的問題中，每個(gè)城市為平面上的一個(gè)點(diǎn)，分別用兩組數(shù)組來記錄每個(gè)城市的x，y坐標(biāo)，兩個(gè)城市之間的距離為它們的歐氏距離。本文采用了4個(gè)測(cè)試問題，城市數(shù)目分別為10，30，50和75。本文程序在matlab6.5中運(yùn)行通過。

1 貪婪算法

1.1 算法思想

貪婪算法的基本思想是找出整體當(dāng)中每個(gè)小的局部的最優(yōu)解，并且將所有的這些局部最優(yōu)解合起來形成整體上的一個(gè)最優(yōu)解［2］。因此能夠使用貪婪算法的問題必須滿足下面的兩個(gè)性質(zhì):

1.整體的最優(yōu)解可以通過局部的最優(yōu)解來求出;

2.一個(gè)整體能夠被分為多個(gè)局部，并且這些局部都能夠求出最優(yōu)解。

1.2 TSP問題的貪婪算法

從一個(gè)給定的城市出發(fā)，選擇距離該城市最近的且未曾到達(dá)過的城市作為下一個(gè)到達(dá)的城市，直到遍歷完所有的城市為止。考慮到初始城市的選取對(duì)結(jié)果的影響較大，而且該算法所需要的計(jì)算量比較小，在本文程序?qū)崿F(xiàn)中，應(yīng)用該算法求解TSP問題時(shí)，對(duì)每個(gè)城市作為初始出發(fā)的城市運(yùn)用貪婪算法，再找出最好的解。

2 禁忌搜索算法

2.1 算法思想

禁忌搜索算法的特點(diǎn)是采用了禁忌技術(shù)。所謂禁忌［3］就是禁止重復(fù)前面的工作。為了回避局部鄰域搜索陷入局部最優(yōu)的不足，禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再搜索這些點(diǎn)，以此來跳出局部最優(yōu)點(diǎn)。

2.2 TSP問題的禁忌搜索算法

禁忌搜索［4］的一般過程為:

Step1，選定初始解xnow，以及給出禁忌表 H=?;

Step2，若滿足停止規(guī)則，停止計(jì)算;否則，在xnow的鄰域中選出滿足禁忌要求的候選集中選取評(píng)價(jià)值最好的解xbest，置xbest=xnow，更新禁忌表H，重復(fù) Step2。

本文程序中，初始解xnow是在解空間S中隨機(jī)選取的。采用2-opt鄰域結(jié)構(gòu)，當(dāng)程序迭代的次數(shù)達(dá)到給定的數(shù)目時(shí)(在本文測(cè)試中取為100)，停止運(yùn)算，計(jì)算過程中記錄得到最好的解。禁忌對(duì)象選取的是對(duì)換，評(píng)價(jià)值取為路徑的長度，當(dāng)候選集中所有元素都被禁忌，按特赦規(guī)則解禁:即找出候選集中評(píng)價(jià)值最好的元素解禁。由于初始解是隨機(jī)產(chǎn)生的，每一次運(yùn)行出來的結(jié)果不一樣，在測(cè)試時(shí)運(yùn)行n(與城市數(shù)目一樣)次，在所得結(jié)果中取最小的。運(yùn)行時(shí)間為這n次運(yùn)行所需時(shí)間的平均值。

為了分析禁忌長度對(duì)結(jié)果的影響，選取50個(gè)城市的測(cè)試問題，并對(duì)不同的禁忌長度運(yùn)行test文件，(都迭代100步終止)得到結(jié)果，如表1所示:

表1 對(duì)不同禁忌長度運(yùn)行的結(jié)果

容易看出，禁忌長度對(duì)結(jié)果有很大的影響。由于迭代次數(shù)相同，在運(yùn)行時(shí)間上并沒有什么差異。

3 模擬退火算法

3.1 算法思想

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。模擬退火算法(Simulated Annealing，SA)最早的思想是由N.Metropolis［5］等人于 1953 年提出。1983 年，S.Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。

3.2 TSP問題的模擬退火算法的一般過程

模擬退火算法［6］的一般過程為:

Step1，任選一個(gè)初始解x0，xK=x0，k=0;t0=tmax(初始溫度);

Step2，若在該溫度下達(dá)到內(nèi)循環(huán)的停止條件，轉(zhuǎn)到Step3;否則在鄰域N(xi)中任選一個(gè)解xj，計(jì)算 △fij=f(xj)-f(xi)，若 △fij≤0，則xi=xj，否則若exp(-△fij)≥rand(0，1)時(shí)，則xi=xj;重復(fù)Step2;

Step3，降溫過程tk+1=d(tk)，k=k+1，若滿足停止條件，終止計(jì)算;否則返回Step2。

本文程序中，Step3中采用的降溫方法是tk+1=αtk，K≥0，0＜α＜1。其中取 α=0.8。當(dāng)退火的溫度接近0時(shí)(溫度小于10-9時(shí))，停止計(jì)算。其中內(nèi)循環(huán)停止條件為在該溫度條件下迭代100次。解采用路徑表示，鄰域采用的是2-opt結(jié)構(gòu)。跟禁忌算法類似，運(yùn)行多次取最好的結(jié)果，并計(jì)算平均運(yùn)行時(shí)間。

對(duì)四個(gè)測(cè)試問題運(yùn)用模擬退火算法的計(jì)算結(jié)果，如表2所示:

表2 四個(gè)測(cè)試問題的模擬退火算法的結(jié)果

從上面的表格中可以看出:初始溫度的選取對(duì)計(jì)算結(jié)果有一定的影響。并不是初始溫度越高得到的解就越好;當(dāng)溫度取為100左右時(shí)得到的解相對(duì)還是比較好的。但溫度越高，運(yùn)行的時(shí)間也越長，這是因?yàn)榈拇螖?shù)增大了。還可以看出在同一個(gè)初始溫度條件下，隨著城市數(shù)目的增加，運(yùn)行的時(shí)間相差并不大。

4 遺傳算法

4.1 算法思想

遺傳算法［7］(Genetic Algorithm)是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。

4.2 TSP問題的遺傳算法

遺傳算法［8-9］的一般過程如下:

Step1，選擇問題的一個(gè)編碼，給出一個(gè)有N個(gè)個(gè)體的初始群體pop(1)，t=1;

Step2，對(duì)群體pop(1)中的每一個(gè)個(gè)體popi(t)計(jì)算它的適應(yīng)函數(shù)fi=fitness(popi(t))，i=1，2，.，N;

Step4，通過雜交，雜交概率為pc，得到一個(gè)N個(gè)個(gè)體的crosspop(t+1);

Step5，以一個(gè)較小的概率p，使得一個(gè)個(gè)體的一個(gè)基因發(fā)生變異，形成mutpop(t+1);t=t+1，一個(gè)新的群體pop(t)=mutpop(t)，返回Step2。

本文應(yīng)用該算法求解TSP問題的幾點(diǎn)說明如下:

初始種群:用隨機(jī)的方式選擇若干個(gè)個(gè)體組成初始種群。

適應(yīng)度函數(shù)選取為路徑長度的倒數(shù)。

選擇算子:采用比例選擇方法為選擇算子，即在第t代運(yùn)算過程中，個(gè)體j被選中的概率與其在群體中的相對(duì)適應(yīng)度成正比，本程序以此作為相應(yīng)的選擇比例。

由于解的路徑表示在雜交操作中會(huì)產(chǎn)生不可行解，因此采用另外的編碼方式:次序表示;次序表示可以使得傳統(tǒng)的雜交算子可行。即從次序表示的任何兩條路徑，從某點(diǎn)截?cái)嗪蠼粨Q的子串所得到的兩個(gè)后代仍然是合法路徑。

次序表示的編碼算法是:

Step 1:以城市代碼做一個(gè)集合 C={1，2，…，n}。

Step 2:設(shè)路徑的第一位是城市代碼j，則取j為編碼的第一位，并在C中刪除j。

Step 3:設(shè)路徑的第(i-1)位已經(jīng)編碼，則在C中刪去該位的城市代碼。

Step 4;取路徑中的第i位的城市代碼在C中排序的位置作為其碼值，該值在1至(n-i+1)之間，并從C中刪去該城市代碼。

Step 5:重復(fù)上述過程直到C為空集。

次序表示的解碼算法與編碼算法完全類似，只是由編碼對(duì)應(yīng)城市代碼，就可以得到路徑表示。

編碼和解碼函數(shù)分別由coding和decode函數(shù)實(shí)現(xiàn)。

在程序?qū)崿F(xiàn)過程中，采用的雜交方式為隨機(jī)產(chǎn)生交配位置，并以一定概率交配，交配的方式為簡單交配;兩父本雜交后產(chǎn)生的兩個(gè)子個(gè)體，選擇適應(yīng)度大的那個(gè)個(gè)體作為子群的一個(gè)個(gè)體。變異方式采用的是隨機(jī)產(chǎn)生變異位置變異。當(dāng)?shù)竭_(dá)一定數(shù)目時(shí)停止計(jì)算。為減少初始種群對(duì)程序運(yùn)行結(jié)果的影響，多次運(yùn)行程序(n次)，在所有結(jié)果中取最好的解，并計(jì)算平均運(yùn)行時(shí)間。

對(duì)30個(gè)城市的測(cè)試問題的遺傳算法實(shí)現(xiàn)中，在種群規(guī)模為50，迭代次數(shù)為100，雜交概率為0.95的情形下，選取不同的變異概率得到結(jié)果，如表3所示:

表3 不同變異概率的遺傳算法的結(jié)果

當(dāng)種群規(guī)模為50，迭代次數(shù)為100，變異概率為0.02的情形下，選取不同的雜交概率得到結(jié)果，如表4所示:

表4 不同雜交概率的遺傳算法的結(jié)果

5 結(jié)果及比較

為方便起見，將四種算法得到的結(jié)果列在下面的表格中，如表5所示。參數(shù)設(shè)置:在模擬退火算法中初始溫度設(shè)為100;禁忌算法中禁忌長度為，迭代次數(shù)為100;遺傳算法中，種群規(guī)模為50，迭代次數(shù)為 100，雜交和變異概率分別為 0.95 和 0.02.。

表5 不同算法運(yùn)行的結(jié)果

貪婪算法是一個(gè)確定性算法，它在很短的時(shí)間內(nèi)就可以得到較好的解。不過由該算法得到的結(jié)果沒有改善的余地。模擬退火算法和禁忌搜索算法的計(jì)算結(jié)果相當(dāng)，兩者都需要調(diào)節(jié)好參數(shù)，如果參數(shù)不恰當(dāng)就得不到較好的解。對(duì)遺傳算法來說，它是一種群智能算法，計(jì)算量很大，在相同迭代次數(shù)的條件下，其結(jié)果不如模擬退火算法。而且它的參數(shù)對(duì)結(jié)果影響很大，如果想要得到較好的解需要不斷地調(diào)節(jié)參數(shù)，隨著種群規(guī)模的擴(kuò)大，計(jì)算時(shí)間也越長。

禁忌搜索算法和遺傳算法的運(yùn)行時(shí)間隨著城市數(shù)目的增加迅速增大，對(duì)模擬退火算法來說這種變化并不明顯，由于兩者結(jié)果相當(dāng)，當(dāng)城市數(shù)目較大時(shí)，模擬退火算法在時(shí)間上具有一定的優(yōu)勢(shì)。無論從結(jié)果還是計(jì)算時(shí)間上來看，遺傳算法的效果都不好。

［1］郭靖揚(yáng).旅行商問題概述［J］.大眾科技，2006(8)：229-230.

［2］邢文訓(xùn).現(xiàn)代優(yōu)化計(jì)算方法［M］.清華大學(xué)出版社，1999.

［3］李陽，李文芳，馬驪等.混合退火算法求解旅行商問題［J］.計(jì)算機(jī)應(yīng)用，2014(1)：110-113.

［4］張洪艷.改進(jìn)禁忌搜索算法在TSP問題中的應(yīng)用［J］.科技資訊，2013(32)：4-5.

［5］辛萌嬌，沈林.模擬退火算法探討［J］.旅游縱覽(下半月)，2013(9)：43-43.

［6］曲曉麗，潘昊，柳向斌.旅行商問題的一種模擬退火算法求解［J］.現(xiàn)代電子技術(shù)，2007(18)：78-80.

［7］金曉龍.蟻群和遺傳混合算法求解旅行商問題［J］.電腦開發(fā)與應(yīng)用，2014(8)：44-46.

［8］李鋒，魏瑩.基于仿真的遺傳算法求解動(dòng)態(tài)旅行商問題［J］.系統(tǒng)管理學(xué)報(bào)，2009，5(18)：591-595.

［9］單春艷，姚鵬修.遺傳算法在旅行商問題的研究與應(yīng)用［J］.工業(yè)控制計(jì)算機(jī)，2013，11(26)：107-109.