【路徑規劃】模擬退火演算法之求解火災巡邏最短路徑【Matlab 193期】

一、簡介

1 模擬退火演算法的應用背景
模擬退火演算法提出于1982年，Kirkpatrick等人首先意識到固體退火程序與優化問題之間存在著類似性；Metropolis等人對固體在恒定溫度下達到熱平衡程序的模擬也給他們以啟迪，通過把Metropolis 演算法引入到優化程序中，最終得到一種對 Metropolis 演算法進行迭代的優化演算法，這種演算法類似固體退火程序，稱之為“模擬退火演算法”，
模擬退火演算法是一種適合求解大規模組合優化問題的隨機搜索演算法，目前，模擬退火演算法在求解 TSP，VLSI 電路設計等組合優化問題上取得了令人滿意的結果，將模擬退火演算法同其它的計算智能方法相結合，應用到各類復雜系統的建模和優化問題中也得到了越來越多的重視，已經逐漸成為一種重要的發展方向，
2 模擬退火演算法介紹




3 模擬退火演算法的引數
模擬退火是一種優化演算法，它本身是不能獨立存在的，需要有一個應用場合，其中溫度就是模擬退火需要優化的引數，如果它應用到了聚類分析中，那么就是說聚類分析中有某個或者某幾個引數需要優化，而這個引數，或者引數集就是溫度所代表的，它可以是某項指標，某項關聯度，某個距離等等，

二、源代碼

clear;
% 程 序 參 數 設 定
Coord = ... % 城 市 的 坐 標 Coordinates
[ 5.2 16.4 28.4 40.4 74.7 86.7 5.2 16.4 28.4 40.4 55.6 66.7 74.7 86.7 100.5; ...
  10.2 10.2 10.2 10.2 10.2 10.2 0 0 0 0 -11 0 0 -2.5 -2.5 ] ;
t0 = 1 ; % 初 溫 t0
iLk = 20 ; % 內 循 環 最 大 迭 代 次 數 iLk
oLk = 50 ; % 外 循 環 最 大 迭 代 次 數 oLk
lam = 0.95 ; % λ lambda
istd = 0.001 ; % 若 內 循 環 函 數 值 方 差 小 于 istd 則 停 止
ostd = 0.001 ; % 若 外 循 環 函 數 值 方 差 小 于 ostd 則 停 止
ilen = 5 ; % 內 循 環 保 存 的 目 標 函 數 值 個 數
olen = 5 ; % 外 循 環 保 存 的 目 標 函 數 值 個 數
% 程 序 主 體
p=inf;
for i=1:1:500
m = length( Coord ) ; % 城 市 的 個 數 m
fare = distance( Coord ) ; % 路 徑 費 用 fare
path = 1 : m ; % 初 始 路 徑 path
pathfar = pathfare( fare , path ) ; % 路 徑 費 用 path fare
ores = zeros( 1 , olen ) ; % 外 循 環 保 存 的 目 標 函 數 值
e0 = pathfar ; % 能 量 初 值 e0
t = t0 ; % 溫 度 t
for out = 1 : oLk % 外 循 環 模 擬 退 火 過 程
ires = zeros( 1 , ilen ) ; % 內 循 環 保 存 的 目 標 函 數 值
for in = 1 : iLk % 內 循 環 模 擬 熱 平 衡 過 程
[ newpath , v ] = swap( path , 1 ) ; % 產 生 新 狀 態
e1 = pathfare( fare , newpath ) ; % 新 狀 態 能 量
% Metropolis 抽 樣 穩 定 準 則
r = min( 1 , exp( - ( e1 - e0 ) / t ) ) ;
if rand < r
path = newpath ; % 更 新 最 佳 狀 態
e0 = e1 ;
end
ires = [ ires( 2 : end ) e0 ] ; % 保 存 新 狀 態 能 量
% 內 循 環 終 止 準 則 ：連 續 ilen 個 狀 態 能 量 波 動 小 于 istd
if std( ires , 1 ) < istd
break ;
end

三、運行結果

四、備注

完整代碼或者代寫添加QQ912100926，
往期回顧>>>>>>
【路徑規劃】粒子群優化演算法之三維無人機路徑規劃【Matlab 012期】
【路徑規劃】遺傳演算法之多物流中心的開放式車輛路徑規劃【Matlab 013期】
【路徑規劃】粒子群演算法之機器人柵格路徑規劃【Matlab 014期】
【路徑規劃】蟻群演算法之求解最短路徑【Matlab 015期】
【路徑規劃】免疫演算法之物流中心選址【Matlab 016期】
【路徑規劃】人工蜂群之無人機三維路徑規劃【Matlab 017期】
【路徑規劃】遺傳演算法之基于柵格地圖機器人路徑規劃【Matlab 018期】
【路徑規劃】蟻群演算法之多無人機攻擊調度【Matlab 019期】
【路徑規劃】遺傳演算法之基于柵格地圖的機器人最優路徑規劃【Matlab 020期】
【路徑規劃】遺傳演算法之考慮分配次序的多無人機協同目標分配建模【Matlab 021期】
【路徑規劃】蟻群演算法之多中心vrp問題【Matlab 022期】
【路徑規劃】蟻群演算法之求解帶時間窗的多中心VRP【Matlab 023期】
【路徑規劃】遺傳演算法之多中心VRP求解【Matlab 024期】
【路徑規劃】模擬退火之求解VRP問題【Matlab 025期】
【路徑規劃】A星之柵格路徑規劃【Matlab 026期】
【路徑規劃】基于一種帶交叉因子的雙向尋優粒子群柵格地圖路徑規劃【Matlab 027期】
【路徑規劃】【TSP】蟻群演算法之求解TSP問題含GUI【Matlab 028期】
【路徑規劃】蟻群演算法之柵格地圖路徑規劃【Matlab 029期】
【路徑規劃】遺傳演算法之旅行商 TSP 【Matlab 030期】
【路徑規劃】模擬退火演算法之旅行商 TSP 問題【Matlab 031期】
【路徑規劃】蟻群演算法之智能車路徑規劃【Matlab 032期】
【路徑規劃】華為杯：基于matlab 無人機優化運用于搶險救災【Matlab 033期】
【路徑規劃】matlab之最小費用最大流算問題【Matlab 034期】
【路徑規劃】A*演算法之解決三維路徑規劃問題【Matlab 035期】
【路徑規劃】人工蜂群演算法之路徑規劃【Matlab036期】
【路徑規劃】人工蜂群演算法之路徑規劃【Matlab 037期】
【路徑規劃】蟻群演算法之求解多旅行商MTSP問題【Matlab 038期】
【路徑規劃】蟻群演算法之無人機路徑規劃【Matlab 039期】

【路徑規劃】遺傳演算法之求解多VRP問題【Matlab 040期】
【VRP】遺傳演算法之帶時間窗的車輛路徑問題【Matlab 041期】
【路徑規劃】蟻群演算法之三維路徑規劃【Matlab 042期】
【路徑規劃】粒子群優化蟻群之求解最短路徑【Matlab 043期】
【TSP問題】差分進化之求解TSP問題【Matlab 044期】
【路徑規劃】RRT之三維路徑規劃【Matlab 144期】
【路徑規劃】人工勢場演算法之無人機編隊路徑規劃【 Matlab 145期】
【VRP問題】節約演算法之求解TWVRP問題【Matlab 146期】
【VRP問題】節約演算法之求解CVRP問題【Matalb 147期】
【VRP問題】禁忌搜索演算法之求解VRP問題【Matalb 148期】
【VRP問題】模擬退火演算法之求解CVRP問題【Matlab 149期】
【VRP問題】模擬退火求解帶時間窗之TWVRP問題【Matlab 150期】
【VRP問題】人工魚群演算法之求解帶時間窗VRP問題【Matlab 151期】
【VRP問題】遺傳演算法之求解帶容量VRP問題【Matlab 152期】
【路徑規劃】狼群演算法演算法之三維路徑規劃【Matlab 153期】
【路徑規劃】人工勢場演算法之無人機三維路徑規劃【Matlab 154期】
【路徑規劃】改進差分演算法之三維多無人機協同航跡規劃【Matlab 155期】
【路徑規劃】人工蜂群演算法之多無人機三維路徑規劃【Matlab 156期】
【路徑規劃】麻雀搜索演算法之無人機三維路徑規劃【Matlab 157期】
【路徑規劃】蟻群演算法之三維路徑規劃【Matlab 158期】
【路徑規劃】免疫演算法之最短路徑規劃【Matlab 159期】
【旅行商問題】免疫演算法之求解旅行商問題【Matlab 160期】
【路徑規劃】遺傳演算法的公交排班系統分析【Matlab 161期】
【TSP】粒子群演算法Hopfield之TSP求解【Matlab 162期】
【路徑規劃】A和改進A的路徑規劃【Matlab 163期】
【TSP】改進的禁忌搜索演算法之求解旅行商問題【Matlab 170期】
【TSP】改進的蟻群演算法之求解旅行商問題【Matlab 171期】