求解tsp問題的貪婪隨機模擬退火算法

1、收稿日期：收稿日期：基金項目：基金項目：福建省自然科學基金（2008J0316），福建省青年人才科技創(chuàng)新基金（2006F3013）作者簡介：作者簡介：鐘一文（1968），男，福建上杭人，教授，從事計算智能及其應用的研究。通訊作者：通訊作者：鐘一文，男，教授，博士；電話：13328208369；Email：yiwenzhong@求解求解TSP問題的貪婪隨機模擬退火算法問題的貪婪隨機模擬退火算法鐘一文，蔡榮英福建農(nóng)林大學計算機與信息學院，福

2、建福州，350002摘要摘要：模擬退火算法是一種典型的智能優(yōu)化算法，它的一個主要缺點是收斂速度慢。針對這一問題，提出了一種基于貪婪隨機策略的求解旅行商問題的模擬退火算法，在從當前解的鄰域中選擇候選解時，根據(jù)問題領域的啟發(fā)式信息，采用貪婪策略從鄰域中生成一個候選解列表，再從候選解列表中隨機選擇一個候選解。仿真結果表明，貪婪隨機模擬退火算法明顯優(yōu)于傳統(tǒng)的模擬退火算法。關鍵詞：關鍵詞：模擬退火算法；貪婪隨機；旅行商問題中圖分類號：中圖分類號：

3、TP301文獻標識碼：文獻標識碼：A文章編號：文章編號：AGreedyRomSimulatedAnnealingAlgithmfTravelingSalesmanProblemZHONGYiwenCAIRongyingCollegeofComputerInfmationScienceFujianAgricultureFestryUniversityFuzhou350002ChinaAbstract:SimulatedAnnealinga

4、lgithmisatypicalintelligentoptimizationalgithm.Oneofitsmainshtagesisslowconvergencespeed.IndertotacklethisshtageagreedyromSimulatedAnnealingalgithmfTravelingSalesmanProblemispresented.Inthepresentedalgithmbasedonheuristi

5、cinfmationderivedfromtheproblemathacidatelistisedgreedilyfromtheneighbhoodofcurrentsolution.Thencidatesolutionisedromlyfromthecidatelist.SimulatedresultsshowthattheproposedalgithmcangetbetterresultthanclassicalSimulatedA

6、nnealingalgithm.Keywds:SimulatedAnnealingalgithmGreedyromTravelingSalesmanProblem1引言引言模擬退火（SimulatedAnnealingSA）算法是一種典型的智能優(yōu)化方法，SA算法的思想最早是由Metropolis等[1]提出的，SA算法依據(jù)Metropolis準則接受新解，因此，除接受優(yōu)質解外，還在一定范圍內(nèi)接受劣質解，SA算法在開始時溫度t值較大，可以

7、接受較差的劣質解，隨著t值的減小，只能接受較好的劣質解，最后在t值趨于零時，就不再接受任何劣質解了，這就使SA算法可以從局部最優(yōu)的“陷阱”中跳出，從而有可能求得優(yōu)化問題的全局最優(yōu)解。SA算法同時還具有簡單和通用的特點，因此SA算法在許多領域都得到了很好的應用，比如在VLSI、生產(chǎn)調度、控制工程、機器學習、神經(jīng)網(wǎng)絡、圖像處理等領域。但是，盡管從理論上證明了SA算法能收斂到全局最優(yōu)解，在使用SA算法的過程中也發(fā)現(xiàn)，其收斂速度很慢，與此相反，

8、啟發(fā)式算法通?；谀车目臻g銳化SA算法通過對原搜索空間進行某種非線性拉伸操作，強化各局部極值點的差異，使“好的更好，差的更差”，這樣，在銳化后的空間中，模擬退火跳出較好局部最小的概率相對減小，因而更易于得到好解；文獻[35]研究了不同鄰域結構的大小對SA算法性能的影響，文獻[67]研究了不同的鄰域結構（不同形式的逆轉鄰域、插入鄰域和交換鄰域及它們的混合）對SA算法性能的影響。當確定了鄰域結構后，上述文獻基本上都是采用等概率的方式從鄰域中

9、隨機產(chǎn)生下一個候選解，文獻[6]提出了一個基于領域知識的啟發(fā)式方式，其基本思想是在插入鄰域中選擇插入位置和插入城市時，根據(jù)TSP問題中邊的信息，使用比例選擇策略，優(yōu)先破壞長的邊，優(yōu)先插入短的邊：在選擇插入位置時，使路徑中相鄰城市之間的距離大的兩個城市以較大的概率被選取，在它們之間插入其他城市，即選擇位置i為插入點的概率為：（2）)(]][]][)%1[([stourLengthisNNisdpi???假設已經(jīng)選定在位置i插入，選擇插入的

10、城市時，使距離城市s[i]近的城市以較大的概率選為下一個訪問點，即選擇位置j上的城市s[j]的概率為：（3）?????Nkjksisddjsisddp1maxmax)]][]][[[()]][]][[[(式中dmax是其他城市到城市s[i]的最大距離。仿真結果表明，上述比例選擇策略的使用能有效地提高SA算法的性能[6]，但上述方式存在以下不足：（1）在選擇插入位置時，優(yōu)先破壞距離大的城市的策略在有些情況下是不合適的，因為各個城市到其他城

11、市的平均距離可能有很大的差別。（2）這種概率選擇方式比較費時，特別是選擇插入位置時，每次都得重新生成概率分布表。（3）在選擇插入城市時，公式（3）考慮了從某一城市出發(fā)所能到達的所有城市，而實際上，在最佳路徑上的邊幾乎都是較短的邊[8]，所以，如果只考慮離這個城市較近的一些城市，則算法可能具有較快的收斂速度，更好的局部求精能力。3貪婪隨機模擬退火算法貪婪隨機模擬退火算法針對比例選擇策略的上述不足，本文提出一種基于貪婪隨機思想的候選解生成策

12、略。先根據(jù)城市之間的距離生成一個二維的排名表rank，其中rank[i][j]表示城市j到城市i的距離在所有到城市i的城市的排名，排名越小，距離越短，即排名為1表示距離最短，排名為2表示距離第二短，依此類推；建立一個二維的近鄰城市排序表der，里面的每一個元素der[i][j]的值表示對城市i而言，第j近的城市是der[i][j]，即最近的城市是der[i][1]，次近的城市是der[i][2]，依此類推。在選擇插入位置時i，使用錦標賽