基于MATLAB的模擬退火算法解決旅行推銷員問題的研究

03MATLAB仿真實驗與算法改進01旅行推銷員問題介紹02模擬退火算法介紹03MATLAB仿真實驗與算法改進01旅行推銷員問題介紹02模擬退火算法介紹給定N個城市和每個城市之間的距離，推銷員要訪問每一個城市，并且只去一次，最終返回原城市，尋找最短路徑。旅行推銷員問題簡介旅行推銷員問題（TravellingSalesmanProblem，又稱為旅行商問題、貨郎擔問題、TSP問題）是一個多局部最優(yōu)的優(yōu)化問題：給定N個城市和每個城市之間的距離，推銷員要訪問每一個城市，并且只去一次，最終返回原城市，尋找最短路徑。旅行推銷員問題由愛爾蘭數(shù)學家SirWilliamRowanHamilton和英國數(shù)學家ThomasPenyngtonKirkman在19世紀提出的數(shù)學問題WilliamRowanHamilton旅行推銷員問題研究意義現(xiàn)實生活中經(jīng)常要同時考慮多個目標，目標之間往往存在沖突性，我們要在多個目標中尋找一個公平、合理的最優(yōu)解。如路程最短、時間最短、費用最省、風險最小等多方面的因素。該問題的實際模型在VLSI芯片設計、連鎖店的貨物配送、網(wǎng)絡路由設計、物流、生產(chǎn)調(diào)度等領域有著廣泛的應用價值，故研究TSP問題，對科學管理與經(jīng)濟決策的許多應用領域中都有重大意義。03MATLAB仿真實驗與算法改進01旅行推銷員問題介紹02模擬退火算法介紹模擬退火算法(SimulatedAnnealingAlgorithm,SAA)是一種通用概率算法，用來在固定時間內(nèi)尋求在一個大的搜尋空間內(nèi)找到的最優(yōu)解。適合解決大規(guī)模組合優(yōu)化問題，特別是NP完全類問題的通用有效近似算法。模擬退火算法最早的思想是由Metropolis在1953年提出的，由S.Kirkpatrick,C.D.Gelatt和M.P.Vecch于1983年成功地將其應用在組合最優(yōu)化問題中，目前已經(jīng)應用到各門學科中以解決非線性系統(tǒng)中的優(yōu)化問題。物理退火在冶金學或材料工程中，退火（Annealing）是一種能夠改變材料微結(jié)構(gòu)，進而改變硬度和強度的機械性質(zhì)的熱處理。過程為將金屬加溫到某個高于再結(jié)晶溫度的一點并維持此溫度一段時間，再將其緩慢冷卻。加溫維持溫度緩慢冷卻加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。物理退火模擬退火算法物理退火優(yōu)化問題物質(zhì)狀態(tài)解能量最低的物質(zhì)狀態(tài)最優(yōu)解退火過程求解過程溫度T控制參數(shù)t能量E目標函數(shù)F等溫過程Metropolis抽樣過程模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解，計算目標函數(shù)的差，接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解。Metropolis準則是SA算法收斂于全局最優(yōu)解的關(guān)鍵，是Metropolis等人在1953年提出的重要性采樣法，其基本采樣思想是著重選擇那些具有重要貢獻的狀態(tài)，則可以較快地達到較好的結(jié)果。溫度越小，則降溫概率p就越小，溫度越高，與出現(xiàn)一次能量差為dE的降溫概率p就越大。p越大則j狀態(tài)是重要狀態(tài)的概率就越大。若j是重要狀態(tài)，則取代i成為當前狀態(tài)，否則舍棄新狀態(tài)再重復以上新狀態(tài)產(chǎn)生過程。這種接受新狀態(tài)轉(zhuǎn)移的準則即為Metropolis準則。Metropolis準則

解空間：解空間X是訪遍每一個城市且只有一次的所有路經(jīng)，解可以表示為{x1,x2,……,xn}，x1,……,xn是1,2,……,n的一個排列，表明x1城市出發(fā)，依次經(jīng)過x2,……,xn城市，再返回x1城市。初始解可選為(1,……,n);目標函數(shù)：訪問所有城市的路徑總長度；其中最優(yōu)路徑為目標函數(shù)等于最小值時所對應的路徑。新路徑的產(chǎn)生：隨機產(chǎn)生1和n之間的兩相異數(shù)k和m，假設k<m，則將原路徑：(x1,x2,…,xk,xk+1,…,xm,xm+1,…,xn)變?yōu)樾侣窂剑?x1,x2,…,xm,xk+1,…,xk,xm+1,…,xn)模擬退火算法解決TSP問題模型求解旅行推銷員問題（TSP）的模擬退火算法模型可描述如下:YYYYNNNN選擇初始路徑X0確定初始溫度T0當前路徑Xi=X0當前溫度Ti=T0Exp(-△f/Ti)>random(0,1)跳出外循環(huán)結(jié)束

當前溫度Ti下降從Xi的鄰域中隨機選擇Xj，計算Xi與Xj的路程差△f=f(Xj)-f(Xi)△f<=0

當前路徑Xi=Xj跳出內(nèi)循環(huán)選一初始狀態(tài)X0,作為當前解：并且確定初始溫度T0，令當前的Xi=X0和Ti=T0。然后從Xi的鄰域中隨即選擇Xj，計算Xi與Xj的路徑差，比較差值。按一定方式將T降溫，即令T(t+1)＝k×T(t)，i=i+1，然后檢查退火過程是否結(jié)束，如果不是繼續(xù)交換，如果是的話輸出Xi作為最優(yōu)輸出。模擬退火算法的流程圖模擬退火算法在搜索策略上與傳統(tǒng)的隨機搜索方法不同，它是一種啟發(fā)式隨機搜索算法。不僅引人了物理系統(tǒng)退火過程的自然機理，而且還引入了適當?shù)碾S機因素。它在迭代過程中，不但能接受使目標函數(shù)值變“好”的點，又能夠以一定的概率接受使目標函數(shù)值變“差”的點。接受概率隨著溫度的下降逐漸減小，因為在整個解的鄰域范圍內(nèi)取值的隨機性，可使算法避免陷入局部最優(yōu)解，有利于提高求得全局最優(yōu)解的可靠性。模擬退火算法的效果示范局限性123在目標函數(shù)復雜、變量多時，執(zhí)行時間長。為了得到一個好的近似解,控制參數(shù)T需要從一個較大的值開始,并需要在每一個溫度值T下執(zhí)行多次Metropolis算法，導致減慢迭代運算的速度。溫度T的初始數(shù)據(jù)和減小步長較敏感。如果溫度T的初值選擇較大，減小步長太小，雖然最終能得到較優(yōu)的解,但算法收斂速度太慢；如果溫度T的初值選擇較小，減小步長過大，可能得不到全局最優(yōu)解。容易遺失當前遇到的最優(yōu)解。搜索過程通過執(zhí)行概率接受來判斷。模擬退火算法的局限性1)模擬退火算法自身要素改進增加升溫或重升溫過程增加補充搜索過程增加記憶功能……模擬退火算法的改進策略2)和其他算法結(jié)合遺傳算法混沌搜索禁忌算法……03MATLAB仿真實驗與算法改進01旅行推銷員問題介紹02模擬退火算法介紹TSP問題假設有40個城市，坐標矩陣如下（單位：km），第一行是各城市的橫坐標，第二行是各城市的縱坐標：zuobiao=[2.373.751.453.765.714.071.426.595.323.64.35.675.622.671.204.350.270.940.821.371.612.420.67.390.532.40.632.51.983.680.553.763.885.651.785.252.102.400.622.555.51.22.80.994.06.92.662.44.71.3;6.913.870.852.750.726.742.710.693.645.643.590.593.550.550.51.451.433.420.382.272.260.256.230.192.191.132.082.045.020.852.320.153.301.552.901.741.760.350.291.282.30.993.52.91.23.80.451.24.70.5];待尋優(yōu)城市位置分布利用基本的模擬退火算法：（1）初始解的產(chǎn)生：隨機產(chǎn)生城市序列。（2）新解的產(chǎn)生：隨機選擇兩個城市，交換在路徑上的位置。選擇不同的初溫、溫度變化率和在每個溫度下的搜索次數(shù)得到的仿真實驗結(jié)果。終止溫度為0.001。取不同參數(shù)時模擬退火算法對40城市尋優(yōu)的仿真結(jié)果實驗次數(shù)初始溫度每個溫度下的搜索次數(shù)溫度變化率最優(yōu)距離（km）運行時間（秒）11005000.9545.496862.052786210015046.832523.27674231005055.601710.629814450010047.827919.39315855005052.506514.5146916100030048.815448.4334757100010050.469022.460067810005051.092812.6625459200015045.393641.710554210200010047.289020.096185111005000.7550.854115.9211521210030056.64548.10133113500100043.931124.2264951450080045.973619.3682961550050050.381114.5637071650030047.52729.4693691750010054.05964.18842718100030050.53598.94543919100020051.75597.19137220100010052.26457.12147921200030051.75439.25097822200020053.51677.42748723200010057.12305.3151532450010000.65

45.235017.5530902550050049.411410.94340326100020054.20425.23688327200010051.26487.130828當初始溫度較大，結(jié)束溫度較低，溫度下降較慢，每個溫度的搜索次數(shù)較多時，優(yōu)化結(jié)果比較好，但是需要的計算時間很長。如果采取適當高的初溫和搜索次數(shù)，可以縮短計算時間。如果加快溫度下降速度，可以明顯縮短計算時間，但是要通過實驗選擇合適的初溫和每個溫度下的搜索次數(shù)，否則計算結(jié)果不佳。如果每個溫度下的搜索次數(shù)不夠，即使取到較高的初溫，尋優(yōu)結(jié)果也不令人滿意。如果溫度選擇不合適，容易陷入局部極值。MATLAB仿真結(jié)果分析采取不同的參數(shù)做了多組仿真實驗，將典型結(jié)果列在上表中。從表中數(shù)據(jù)可知以下結(jié)論：改進再搜索記憶新解初始解每次搜索時保存當前尋到的歷史最優(yōu)值，以保證最優(yōu)值不被丟掉。產(chǎn)生一個初始解群，從中挑選一個最優(yōu)解，作為初始解。以爭取在開始時盡量遍歷整個解空間，找到一個相對好的解，為搜索做一個較好的開始。在整體搜索結(jié)束后，在尋到的最優(yōu)解附近，利用貪婪搜索的思路，進行小范圍的搜索，只接受比當前解更好的新解。為減少冗余計算，將禁忌搜索的思路引入進來，每次記錄互換的城市序號，如果下一次迭代他們又被選中互換，則重新選擇互換的城市，以避免重復的計算。模擬退火算法的