利模擬退火算法解決旅行商問題

1、利模擬退火算法解決旅行商問題武 健 同組：任旭東，劉 洋，李 丹（遼寧師范大學 物理與電子技術學院）摘要：旅行商問題（Traveling Salesman Problem，TSP），是數(shù)學領域中著名問題之一。組合優(yōu)化領域里的一個典型的、易于描述卻難以處理的NP完全難題。模擬退火（Simulatated Algorithm，SA）算法是通過控制退火參數(shù)，從而模擬退火過程進行的全局尋優(yōu)的一種算法，用來在一個大的搜尋空間內找尋命題的最優(yōu)解。通過MATLAB對優(yōu)化過程進行仿真計算，證實了SA算法可以能夠解決TSP問題。關鍵詞：旅行商 模擬退火 優(yōu)化 MATLAB1. 前言旅行商問題的簡單描述是：一名商

2、人想到n個城市推銷商品，如何選擇一條路徑使得商人每個城市走且只走一遍后回到起點，而且所走路徑最短?；赥SP問題的特性，目前解決該問題的方法主要有禁忌搜索算法、神經(jīng)網(wǎng)絡優(yōu)化算法、蟻群算法、遺傳算法和模擬退火算法等。本文介紹了利用SA算法求解TSP問題的方法。2. 基本原理2.1旅行商問題中的相關定義(1)問題定義：Dij代表從城市i到城市j的距離(i,j=1,2,3,20)，問題是要找出遍訪每個城市恰好一次的一條回路，且其路徑長度R為最小。(2)解空間：解空間P是遍訪每個城市恰好一次的所有回路，可表示為(1,2,3,20)的所有循環(huán)排列的集合。(3)新解的產(chǎn)生：在第120個訪問的城市中隨機選取

3、第i次和第j次訪問的城市，在路徑P中交換這兩個城市的訪問順序其余不變，此時的路徑為R1。(新解的產(chǎn)生方法不唯一) (4)目標函數(shù)：目標函數(shù)為訪問所有城市的回路長度，需求其最小值。2.2模擬退火算法 模擬退火算法是一種非導數(shù)優(yōu)化方法。模擬退火來源于拉絲玻璃的物理特性，原理類似于以一定的速率冷卻金屬時所發(fā)生的現(xiàn)象。緩慢下降的溫度使融化金屬中的原子排成有規(guī)則的結構，結果將產(chǎn)生具有較高能量的非晶體結構。在該算法中，溫度較高時允許對遠處的點求函數(shù)值，并且有可能接受一個具有較高能量的新點。而溫度低時，模擬退火算法只在局部處求目標函數(shù)值，它接受較高能量新點的可能性非常小。 模擬退火算法包含的基本步驟：(1)

4、 選取一個起始點z，并設一個較高的起始溫度T令迭代次數(shù)N=1；(2) 求目標函數(shù)E=f(x)的函數(shù)值；(3) 按照由生成函數(shù)g(x , T)確定的概率選擇x，令新點xn等于x+x；(4) 計算新的目標函數(shù)值En=f(xn)；(5) 按照由接受函數(shù)h(E，T)確定的概率將x設為xn，E設為En，其中E=EnE；(6) 按照退火時間表降低溫度T；(7) 增加迭代次數(shù)k，如果k達到最大迭代次數(shù)，停止迭代，否則返回步驟(3)。3. 具體工作程 序 初 始 化產(chǎn) 生 初 始 解達 到 穩(wěn) 態(tài)滿足算法終止條件最 終 解產(chǎn) 生 新 解滿足Metropolis準則圖1-1 程 序 流 程 圖3.1選取起始點并

5、初始化變量 在利用模擬退火進行優(yōu)化之前，必須首先選取一個優(yōu)化的起始點，該優(yōu)化起始點隨機選取。本實驗中設城市數(shù)目為20，Z=X,Y為城市坐標：X = 17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20Y = 1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 103.2固定溫度的模擬退火子函數(shù) 首先，在溫度為一個較高值時，利用生成函數(shù)確定新的搜索點，常用的生成函數(shù)有Boltzman機使用的高斯密度函數(shù)，Cauchy機使用的Cauchy分布函數(shù)等。為了確定新數(shù)據(jù)是否能夠被接受，必須選擇一個適當?shù)慕邮芎瘮?shù)。

6、3.3降低溫度繼續(xù)優(yōu)化過程 按照退火時間表降低溫度，s=0.98T，重新進行模擬退火推理，直到滿足停止條件。4. 結 論對程序進行多次MATLAB的優(yōu)化仿真，最終能夠找到最優(yōu)解?？梢娎媚M退火算法解決旅行商問題還是較為有效的，其初值魯棒性也較好，可以將該模型應用于解決更多優(yōu)化組合問題中。其實際模型在路徑、網(wǎng)絡、分配等優(yōu)化問題中有著廣泛的應用。模擬退火算法的試驗性能具有質量高、初值魯棒性強、通用易實現(xiàn)的優(yōu)點，最大的缺點是優(yōu)化過程較長。參考文獻：1. 曲強、陳雪波 基于MATLAB的模擬退火算法的實現(xiàn) 鞍山科技大學學報 2003年6月2. 陳磊、毛亞林 基于MATLAB的非導數(shù)優(yōu)化仿真 計算機應

7、用與IT技術 2005年1月3. 高尚 求解旅行商問題的模擬退火算法 華東船舶工業(yè)學院學報 2003年6月4. 潘昊、曲曉麗 旅行商問題的一種模擬退火算法求解 現(xiàn) 代 電 子 技 術 2007年第18期附 錄(程序代碼)：clc;N=1;Num=20;T=1000;T0=1e-3;k=150;s=0.98;x=17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20;y=1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 10;z=x;y;z(1,21)=z(1,1);z(2,21)=z(2,1);p1=1

8、,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21;while T>T0 for t=1:k R1=0; for i=1:Num R1=R1+sqrt(z(1,p1(i)-z(1,p1(i+1).2+(z(2,p1(i)-z(2,p1(i+1).2); end R1 p2=p1; a=round(rand(1,2)*19+1); W=p2(a(1); p2(a(1)=p2(a(2); p2(a(2)=W; R2=0; for i=1:Num R2=R2+sqrt(z(1,p2(i)-z(1,p2(i+1).2+(z(2,p2(i)-z(2,p2(i+1).2); end if (R2-R1)<0 p1=p2; elseif exp(R1-R2)/T)>rand p1=p2; end temp(t,1:length(p1)=p1; R1=0; for i=1:Num R1=R1+sqrt(z(1,p1(i)-z(1,p1(i)+1).2+(z(2,p1(i)-z(2,p1(i)+1).2); end temp(t,length(p1)+1)=R1; end fmin i=min(temp(:,length(p