資源描述：
《求解TSP問(wèn)題的貪婪隨機(jī)模擬退火算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、求解TSP問(wèn)題的貪婪隨機(jī)模擬退火算法鐘一文，蔡榮英福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院，福建福州，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)鍵詞：模擬退火算法；貪婪隨機(jī)；旅行商問(wèn)題中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：AGreedyRan
2、domSimulatedAnnealingAlgorithmforTravelingSalesmanProblemZHONGYi-wen,CAIRong-yingCollegeofComputerandInformationScience,FujianAgricultureandForestryUniversity,Fuzhou350002,ChinaAbstract:SimulatedAnnealingalgorithmisatypicalintelligentoptimizationalgorithm.Oneofitsmainshortage
3、sisslowconvergencespeed.Inordertotacklethisshortage,agreedyrandomSimulatedAnnealingalgorithmforTravelingSalesmanProblemispresented.Inthepresentedalgorithm,basedonheuristicinformationderivedfromtheproblemathand,acandidatelistisselectedgreedilyfromtheneighborhoodofcurrentsoluti
4、on.Thencandidatesolutionisselectedrandomlyfromthecandidatelist.SimulatedresultsshowthattheproposedalgorithmcangetbetterresultthanclassicalSimulatedAnnealingalgorithm.Keywords:SimulatedAnnealingalgorithm;Greedyrandom;TravelingSalesmanProblem1引言模擬退火（SimulatedAnnealing,SA）算法是一種典
5、型的智能優(yōu)化方法，SA算法的思想最早是由Metropolis等[1]提出的，SA算法依據(jù)Metropolis準(zhǔn)則接受新解，因此，除接受優(yōu)質(zhì)解外，還在一定范圍內(nèi)接受劣質(zhì)解，SA算法在開始時(shí)溫度t值較大，可以接受較差的劣質(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)域。但是，盡管從理論
6、上證明了SA算法能收斂到全局最優(yōu)解，在使用SA算法的過(guò)程中也發(fā)現(xiàn)，其收斂速度很慢，與此相反，啟發(fā)式算法通?；谀撤N貪婪策略，有較快的收斂速度，但易于陷入局部最優(yōu)解，那么，能否在SA算法中嵌入一定的貪婪策略，在保持其全局尋優(yōu)的前提下，加快SA算法的收斂速度呢？基于這個(gè)思想，針對(duì)旅行商問(wèn)題（TravelingSalesmanProblem，TSP），本文研究了在產(chǎn)生下一個(gè)解時(shí)，根據(jù)領(lǐng)域的啟發(fā)式信息，采用貪婪策略從鄰域中生成一個(gè)候選解列表，再?gòu)暮蜻x解列表中隨機(jī)選擇一個(gè)候選解，以平衡算法的隨機(jī)性和貪婪性，提高獲取優(yōu)質(zhì)解的概率，從而提高SA算法的總體性能，
7、仿真表明，這種策略能明顯提高SA算法的性能。2求解TSP問(wèn)題的模擬退火算法TSP問(wèn)題是一個(gè)典型的NP-困難的組合優(yōu)化問(wèn)題。假設(shè)有一個(gè)推銷員必須遍歷N個(gè)城市，每個(gè)城市必須且只能訪問(wèn)一次，最后返回到出發(fā)城市，TSP問(wèn)題就是要找到訪問(wèn)這些城市的順序，使旅行線路的總長(zhǎng)度最短。對(duì)一個(gè)包含N個(gè)城市的TSP問(wèn)題，可以用一個(gè)N×N的二維數(shù)組d來(lái)存儲(chǔ)城市間的距離，其中每個(gè)元素d[i][j]表示城市i和j之間的距離，用一個(gè)包含N個(gè)元素的一維數(shù)組s來(lái)存儲(chǔ)推銷員訪問(wèn)城市的順序，其中每個(gè)元素s[i]的值表示第i個(gè)訪問(wèn)的城市，求解TSP問(wèn)題的目標(biāo)就是要找到某個(gè)城市訪問(wèn)順序s
8、，使其路徑長(zhǎng)度最小，即最小化路徑長(zhǎng)度：（1）圖1是求解TSP問(wèn)題的基本SA算法，其中函數(shù)generate(s)表示從當(dāng)前解s產(chǎn)生一個(gè)候選
