求解tsp問(wèn)題的貪婪隨機(jī)模擬退火算法

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

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

3、TP301文獻(xiàn)標(biāo)識(shí)碼：文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：文章編號(hào)：AGreedyRomSimulatedAnnealingAlgithmfTravelingSalesmanProblemZHONGYiwenCAIRongyingCollegeofComputerInfmationScienceFujianAgricultureFestryUniversityFuzhou350002ChinaAbstract:SimulatedAnnealinga

4、lgithmisatypicalintelligentoptimizationalgithm.Oneofitsmainshtagesisslowconvergencespeed.IndertotacklethisshtageagreedyromSimulatedAnnealingalgithmfTravelingSalesmanProblemispresented.Inthepresentedalgithmbasedonheuristi

5、cinfmationderivedfromtheproblemathacidatelistisedgreedilyfromtheneighbhoodofcurrentsolution.Thencidatesolutionisedromlyfromthecidatelist.SimulatedresultsshowthattheproposedalgithmcangetbetterresultthanclassicalSimulatedA

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

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

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

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

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

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

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