模擬退火演算法工具箱應用實例

Ⅲ 求助：一個簡單的模擬退火演算法的例子，規模要小一點的。

《＊高性能計算機》，用模擬退火演算法比用dp要快一些，准確性也要高。
＊注 高性能計算機是一道題。

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

作為模擬退火演算法應用，討論旅行商問題(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的單次比較方式。
⑸ 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。
⑹上述各方法的綜合應用。

Ⅳ 實際問題中可以用到模擬退火演算法的有哪些

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

Ⅵ 誰能給我舉一個模擬退火演算法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)

Ⅶ matlab 有模擬退火演算法的工具包嗎

其實原理很簡單，就是一種概率性的搜索演算法，只是一個小程序，所以可以自己編寫，我目前就是用自己編寫的。
幾個關鍵點就是退火溫降一定要緩慢，也就是迭代次數盡量多，所以在溫度變化函數裡面的參數要設置可能。

Ⅷ 怎樣將模擬退火演算法工具箱添加到matlab中

其實原理很簡單，就是一種概率性的搜索演算法，只是一個小程序回，所以可以自己編答寫，我目前就是用自己編寫的。目前我認為幾個關鍵點就是退火溫降一定要緩慢，也就是迭代次數盡量多，所以在溫度變化函數裡面的參數要設置可能。另外，同溫條件下可以多尋找一些新生個體。最後，發揮matlab的並行運算功能，也就是對退火演算法進行群體優化，這樣，相對於單一個體來講，具有更強大的全局搜索能力。你可以看下陳華根發表的《模擬退火演算法機理研究》，希望對你有所幫助。純屬個人經驗，不足之處歡迎指正

Ⅸ matlab優化工具箱模擬退火法怎麼用

從提示看，目標函數寫法不正確，一、變數x1,x2,等等，要寫成：x(1),x(2),....
二、初始值個數，要與變數數相同，有幾個x(1),x(2),...,x(5),就要有幾個，如5個初始值，而你只寫2個，就不對了。

Ⅹ 誰有完整模擬退火演算法的Delphi或VB例子

有計算方法才知道