模擬退火演算法經典實例

Ⅰ matlab用模擬退火法求函數f(x,y)=sin(xy)+x^2+y^2的最小值。

能解釋一下為什麼要用模擬退火法嗎？

這個函數的最小值直接觀察就能看出來在x=y=0處，或者用fminunc也可以求解：
x=fminunc(@(x)sin(x(1)*x(2))+x(1)^2+x(2)^2,[0 0])

當然，用模擬退火演算法也很簡單，換一下函數即可：
x=simulannealbnd(@(x)sin(x(1)*x(2))+x(1)^2+x(2)^2,[0 0])

Ⅱ 退火演算法的應用領域及示例

作為模擬退火演算法應用，討論旅行商問題(Travelling Salesman Problem,簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i,j) i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。
求解TSP的模擬退火演算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1,……,n}的所有循環排列的集合,S中的成員記為(w1,w2,……,wn)，並記wn+1= w1。初始解可選為(1,……,n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的產生 隨機產生1和n之間的兩相異數k和m,
若k<m,則將
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變為：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變為：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。
也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(w1,w2,……,wn)變換為(u1,u2,……,un)，則代價函數差為：
根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序：
Procere TSPSA:
begin
init-of-T; { T為初始溫度}
S={1,……,n}; {S為初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 從當前迴路S產生新迴路S′}
Δt:=f(S′））-f(S);{f(S)為路徑總長}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：
⑴ 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。
⑵ 退火速度問題。
模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
⑶ 溫度管理問題。
溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式：
T(t+1)=k×T(t)
式中k為正的略小於1.00的常數,t為降溫的次數 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。
缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。
經典模擬退火演算法的缺點：
⑴如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；
⑵如果降溫過程過快，很可能得不到全局最優解。
􀂄 模擬退火演算法的改進
⑴ 設計合適的狀態產生函數，使其根據搜索進程的需要
表現出狀態的全空間分散性或局部區域性。
⑵ 設計高效的退火策略。
⑶ 避免狀態的迂迴搜索。
⑷ 採用並行搜索結構。
⑸ 為避免陷入局部極小，改進對溫度的控制方式
⑹ 選擇合適的初始狀態。
⑺ 設計合適的演算法終止准則。
也可通過增加某些環節而實現對模擬退火演算法的改進。
主要的改進方式包括：
⑴ 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。
⑵ 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。
⑶ 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。
⑷ 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。
⑸ 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。
⑹上述各方法的綜合應用。

Ⅲ 模擬退火演算法優化BP神經網路

bp神經元網路的學習過程真正求解的其實就是權值的最優解，因為有可能會得出局部最優解，所以你才會用模擬退火來跳出局部最優解，也就是引入了逃逸概率。在這里你可以把bp的學習過程理解成關於 誤差=f（w1,w2...） 的函數，讓這個函數在模擬退火中作為目標函數，再加上模擬退火的一些初始參數（初始溫度啊，退火速度啊等等），就能找到權值解空間的一個不錯的最優解，就是一組權向量。把權向量帶入到bp當中去，輸入新的對象，自然就能算出新的輸出了。
演算法學習要腳踏實地，你要先學會神經元，在學會退火，兩個的結合你才能理解。

Ⅳ 誰能給我舉一個模擬退火演算法MATLAB源代碼的簡單例子

clear
clc
a = 0.95
k = [5;10;13;4;3;11;13;10;8;16;7;4];
k = -k; % 模擬退火演算法是求解最小值，故取負數
d = [2;5;18;3;2;5;10;4;11;7;14;6];
restriction = 46;
num = 12;
sol_new = ones(1,num); % 生成初始解
E_current = inf;E_best = inf;
% E_current是當前解對應的目標函數值（即背包中物品總價值）；
% E_new是新解的目標函數值；
% E_best是最優解的
sol_current = sol_new; sol_best = sol_new;
t0=97; tf=3; t=t0;
p=1;

while t>=tf
for r=1:100
%產生隨機擾動
tmp=ceil(rand.*num);
sol_new(1,tmp)=~sol_new(1,tmp);

%檢查是否滿足約束
while 1
q=(sol_new*d <= restriction);
if ~q
p=~p; %實現交錯著逆轉頭尾的第一個1
tmp=find(sol_new==1);
if p
sol_new(1,tmp)=0;
else
sol_new(1,tmp(end))=0;
end
else
break
end
end

% 計算背包中的物品價值
E_new=sol_new*k;
if E_new<E_current
E_current=E_new;
sol_current=sol_new;
if E_new<E_best
% 把冷卻過程中最好的解保存下來
E_best=E_new;
sol_best=sol_new;
end
else
if rand<exp(-(E_new-E_current)./t)
E_current=E_new;
sol_current=sol_new;
else
sol_new=sol_current;
end
end
end
t=t.*a;
end

disp('最優解為：')
sol_best
disp('物品總價值等於：')
val=-E_best;
disp(val)
disp('背包中物品重量是：')
disp(sol_best * d)

Ⅳ 模擬退火法的介紹

模擬退火演算法（Simulate Anneal Arithmetic，SAA）是一種通用概率演演算法，用來在一個大的搜尋空間內找尋命題的最優解。模擬退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發明。而V.Čern&amp;yacute;在1985年也獨立發明此演演算法。模擬退火演算法是解決TSP問題的有效方法之一。

Ⅵ 模擬退火原理介紹

在優化問題中，我們希望找到一個最優解，但實際上這是難以達到的。尤其是當問題較為復雜，求解空間維度較高時，我們需要在巨大的求解空間中搜索所有的可行解，並確定最優解。這樣做計算量十分巨大，幾乎無法在有限的計算時間和計算資源下完成。在實際問題中，我們並不需要精確的最優解，只需要一個近似最優解即可，這個近似最優解與完美的最優解應該足夠接近。

模擬退火（Simulated Annealing, SA）演算法是對熱力學中退火過程的模仿。將金屬加熱到高溫，此時金屬內部分子熱運動非常劇烈，內部的分子結構會出現很大變化；之後讓它緩慢降低溫度，隨著溫度的降低，分子熱運動的劇烈程度逐漸減弱，內部分子結構變化較小，逐漸趨於穩定。在尋找問題的最優解時，我們可以先給定一個初始解。此時溫度較高，初始解有很大的概率發生變化，產生一個新的解；隨著溫度的降低，解發生變化的概率逐漸減小。假定我們需要求解一個函數f(x)的最小值，那麼模擬退火演算法的過程描述如下：

產生新解的方式很多，以二進制編碼為例，假如一個解為01001101，可以隨機選取一位進行取反。假如選中了第3位，則第3位按位取反，新解為01101101。這個過程有點類似於遺傳演算法中的基因突變。上述演算法描述中每個溫度值只產生了一次新解，實際問題中可以產生多次。

演算法的關鍵在於Metropolis准則。如果新解的函數值較小，自然要把新解作為當前解；如果新解函數值較大，則它仍有一定概率被選作當前解。這個概率與df有關，df越大，說明新解越差，它被選作當前解的概率也越小；此外，這個概率還和當前溫度有關，當前溫度越高，概率越大（類似於分子熱運動越劇烈）。

參考資料
[1] Lee Jacobson, Simulated Annealing for beginners, http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6

Ⅶ C語言中退火模擬

模擬退火法 模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis准則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制參數初值t開始，對當前解重復「產生新解→計算目標函數差→ 接受或舍棄」的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schele)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

退火演算法
Simulate Anneal Arithmetic (SAA,模擬退火演算法) 模擬退火演算法 模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis准則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制參數初值t開始，對當前解重復「產生新解→計算目標函數差→接受或舍棄」的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schele)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。 模擬退火演算法起源於物理退火。 􀂄物理退火過程： （1） 加溫過程 （2） 等溫過程 （3） 冷卻過程 1 . 模擬退火演算法的模型 模擬退火演算法可以分解為解空間、目標函數和初始解三部分。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態S(是演算法迭代的起點)， 每個T值的迭代次數L (2) 對k=1，……，L做第(3)至第6步： (3) 產生新解S′ (4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數 (5) 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解. (6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。 終止條件通常取為連續若干個新解都沒有被接受時終止演算法。 (7) T逐漸減少，且T->0，然後轉第2步。 演算法對應動態演示圖： 模擬退火演算法新解的產生和接受可分為如下四個步驟： 第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。 第三步是判斷新解是否被接受,判斷的依據是一個接受准則，最常用的接受准則是Metropo1is准則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。 模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S(是演算法迭代的起點)無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂於全局最優解的全局優化演算法；模擬退火演算法具有並行性。 2 模擬退火演算法的簡單應用 作為模擬退火演算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。 求解TSP的模擬退火演算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1，……，n}的所有循環排列的集合，S中的成員記為(w1,w2 ,……，wn)，並記wn+1= w1。初始解可選為(1，……，n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數： 我們要求此代價函數的最小值。 新解的產生 隨機產生1和n之間的兩相異數k和m，若k (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變為： (w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn). 如果是k>m，則將 (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變為： (wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk). 上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。 也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。 代價函數差 設將(w1, w2 ,……，wn)變換為(u1, u2 ,……，un), 則代價函數差為： 根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序： Procere TSPSA: begin init-of-T; { T為初始溫度} S={1，……，n}; {S為初始值} termination=false; while termination=false begin for i=1 to L do begin generate(S′form S); { 從當前迴路S產生新迴路S′} Δt:=f(S′))-f(S);{f(S)為路徑總長} IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) S=S′; IF the-halt-condition-is-TRUE THEN termination=true; End; T_lower; End; End 模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 3 模擬退火演算法的參數控制問題 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點： (1) 溫度T的初始值設置問題。 溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。 (2) 退火速度問題。 模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。 (3) 溫度管理問題。 溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式： T(t+1)＝k×T(t) 式中k為正的略小於1.00的常數，t為降溫的次數 4、模擬退火演算法的優缺點 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。 缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。 經典模擬退火演算法的缺點： (1)如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢; (2)如果降溫過程過快，很可能得不到全局最優解。 􀂄 模擬退火演算法的改進 (1) 設計合適的狀態產生函數，使其根據搜索進程的需要 表現出狀態的全空間分散性或局部區域性。 (2) 設計高效的退火策略。 (3) 避免狀態的迂迴搜索。 (4) 採用並行搜索結構。 (5) 為避免陷入局部極小，改進對溫度的控制方式 (6) 選擇合適的初始狀態。 (7) 設計合適的演算法終止准則。 也可通過增加某些環節而實現對模擬退火演算法的改進。 主要的改進方式包括： (1) 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。 (2) 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。 (3) 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。 (4) 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。 (5) 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。 (6)上述各方法的綜合應用。

Ⅷ 求一個模擬退火演算法優化BP神經網路的一個程序（MATLAB）

「模擬退火」演算法是源於對熱力學中退火過程的模擬，在某一給定初溫下，通過緩慢下降溫度參數，使演算法能夠在多項式時間內給出一個近似最優解。退火與冶金學上的『退火』相似，而與冶金學的淬火有很大區別，前者是溫度緩慢下降，後者是溫度迅速下降。

「模擬退火」的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有「能量」，以表示該點對命題的合適程度。演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個「鄰居」，然後再計算從現有位置到達「鄰居」的概率。

這個演算法已經很多人做過，可以優化BP神經網路初始權值。附件是解決TSP問題的matlab代碼，可供參考。看懂了就可以自己編程與bp代碼結合。