模擬退火算法(MATLAB實現(xiàn))

1、實驗用例:用模擬退火算法解決如下10個城市的TSP 問題,該問題最優(yōu)解為691.2 opt f 。表1 10個城市的坐標城市 X 坐標 Y 坐標 城市 X 坐標 Y 坐標 3 0.4000 0.4439 8 0.8732 0.6536 編程實現(xiàn)用MATLAB 實現(xiàn)模擬退火算法時,共編制了5個m 文件,分別如下 1、swap.mfunction newpath , position = swap( oldpath , number % 對 oldpath 進 行 互 換 操 作% number 為 產(chǎn) 生 的 新 路 徑 的 個 數(shù) % position 為 對 應(yīng) newpath 互 換 的

2、位 置 m = length( oldpath ; % 城 市 的 個 數(shù) newpath = zeros( number , m ;position = sort( randi( m , number , 2 , 2 ; % 隨 機 產(chǎn) 生 交 換 的 位 置 for i = 1 : numbernewpath( i , : = oldpath ;% 交 換 路 徑 中 選 中 的 城 市newpath( i , position( i , 1 = oldpath( position( i , 2 ;newpath( i , position( i , 2 = oldpath( positi

3、on( i , 1 ; end2、pathfare.mfunction objval = pathfare( fare , path % 計 算 路 徑 path 的 代 價 objval% path 為 1 到 n 的 排 列 ,代 表 城 市 的 訪 問 順 序 ; % fare 為 代 價 矩 陣 , 且 為 方 陣 。 m , n = size( path ; objval = zeros( 1 , m ; for i = 1 : mfor j = 2 : nobjval( i = objval( i + fare( path( i , j - 1 , path( i , j ; en

4、dobjval( i = objval( i + fare( path( i , n , path( i , 1 ; end3、distance.mfunction fare = distance( coord % 根據(jù)各城市的距離坐標求相互之間的距離% fare 為各城市的距離,coord 為各城市的坐標 , m = size( coord ; % m 為城市的個數(shù)fare = zeros( m ;for i = 1 : m % 外層為行for j = i : m % 內(nèi)層為列fare( i , j = .( sum( ( coord( : , i - coord( : , j . 2 0.

5、5 ;fare( j , i = fare( i , j ; % 距離矩陣對稱endend4、myplot.mfunction = myplot( path , coord , pathfar % 做出路徑的圖形% path 為要做圖的路徑,coord 為各個城市的坐標% pathfar 為路徑path 對應(yīng)的費用len = length( path ;clf ;hold on ;title( '近似最短路徑如下,費用為' , num2str( pathfar ;plot( coord( 1 , : , coord( 2 , : , 'ok'pause( 0.4

6、 ;for ii = 2 : lenplot( coord( 1 , path( ii - 1 , ii , coord( 2 , path( ii - 1 , ii , '-b'x = sum( coord( 1 , path( ii - 1 , ii / 2 ;y = sum( coord( 2 , path( ii - 1 , ii / 2 ;text( x , y , '(' , num2str( ii - 1 , '' ;pause( 0.4 ;endplot( coord( 1 , path( 1 , len , coord( 2 ,

7、 path( 1 , len , '-b' ;x = sum( coord( 1 , path( 1 , len / 2 ;y = sum( coord( 2 , path( 1 , len / 2 ;text( x , y , '(' , num2str( len , '' ;pause( 0.4 ;hold off ;5、mySAA.m% 模擬退火算法( Simulated Annealing Algorithm MATLAB 程序% 程序參數(shù)設(shè)定Coord = . % 城市的坐標Coordinates 0.6683 0.6195 0.4 0

8、.2439 0.1707 0.2293 0.5171 0.8732 0.6878 0.8488 ; .0.2536 0.2634 0.4439 0.1463 0.2293 0.761 0.9414 0.6536 0.5219 0.3609 ;t0 = 1 ; % 初溫t0iLk = 20 ; % 內(nèi)循環(huán)最大迭代次數(shù)iLkoLk = 50 ; % 外循環(huán)最大迭代次數(shù)oLklam = 0.95 ; % lambdaistd = 0.001 ; % 若內(nèi)循環(huán)函數(shù)值方差小于istd 則停止ostd = 0.001 ; % 若外循環(huán)函數(shù)值方差小于ostd 則停止ilen = 5 ; % 內(nèi)循環(huán)保存的目標

9、函數(shù)值個數(shù)olen = 5 ; % 外循環(huán)保存的目標函數(shù)值個數(shù)% 程序主體m = length( Coord ; % 城市的個數(shù)mfare = distance( Coord ; % 路徑費用farepath = 1 : m ; % 初始路徑pathpathfar = pathfare( fare , path ; % 路徑費用path fareores = zeros( 1 , olen ; % 外循環(huán)保存的目標函數(shù)值e0 = pathfar ; % 能量初值e0t = t0 ; % 溫度tfor out = 1 : oLk % 外循環(huán)模擬退火過程ires = zeros( 1 , ilen

10、 ; % 內(nèi)循環(huán)保存的目標函數(shù)值for in = 1 : iLk % 內(nèi)循環(huán)模擬熱平衡過程 newpath , = swap( path , 1 ; % 產(chǎn)生新狀態(tài)e1 = pathfare( fare , newpath ; % 新狀態(tài)能量% Metropolis 抽樣穩(wěn)定準則r = min( 1 , exp( - ( e1 - e0 / t ;if rand < rpath = newpath ; % 更新最佳狀態(tài)e0 = e1 ;endires = ires( 2 : end e0 ; % 保存新狀態(tài)能量% 內(nèi)循環(huán)終止準則:連續(xù)ilen 個狀態(tài)能量波動小于istd if std( ires , 1 < istdbreak ;endendores = ores( 2 : end e0 ; % 保存新狀態(tài)能量% 外循環(huán)終止準則:連續(xù)olen 個狀態(tài)能量波動小于ostd if std( ores , 1 < ostdbreak ;endt = lam * t ;pathfar = e0 ;% 輸 入 結(jié) 果fprintf( '近似最優(yōu)路徑為:n ' %disp( char( path , path(1 + 64 ; disp(pathfprintf( '近似最優(yōu)路徑費用tpathfare=&