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

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

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

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

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

5、初始化變量 在利用模擬退火進(jìn)行優(yōu)化之前，必須首先選取一個(gè)優(yōu)化的起始點(diǎn)，該優(yōu)化起始點(diǎn)隨機(jī)選取。本實(shí)驗(yàn)中設(shè)城市數(shù)目為20，Z=X,Y為城市坐標(biāo)：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ù) 首先，在溫度為一個(gè)較高值時(shí)，利用生成函數(shù)確定新的搜索點(diǎn)，常用的生成函數(shù)有Boltzman機(jī)使用的高斯密度函數(shù)，Cauchy機(jī)使用的Cauchy分布函數(shù)等。為了確定新數(shù)據(jù)是否能夠被接受，必須選擇一個(gè)適當(dāng)?shù)慕邮芎瘮?shù)。

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

7、用與IT技術(shù) 2005年1月3. 高尚 求解旅行商問題的模擬退火算法 華東船舶工業(yè)學(xué)院學(xué)報(bào) 2003年6月4. 潘昊、曲曉麗 旅行商問題的一種模擬退火算法求解 現(xiàn) 代 電 子 技 術(shù) 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