1、會計學1用用MATLAB實現模擬退火算法實現模擬退火算法6.1 算法基本理論6.2 算法的MATLAB實現6.3 應用實例第1頁/共30頁簡單了解退火算法特點簡單了解退火算法特點 介紹模擬退火前，先介紹爬山算法。 爬山算法是一種簡單的貪心搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。第2頁/共30頁簡單了解退火算法特點簡單了解退火算法特點爬山算法 如圖所示：假設C點為當前解，爬山算法搜索到A點這個局部最優解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優的解。 模擬退火算法 在搜索到局部最優解A后，會以一定的概率一定的概率接受到E的移

2、動。也許經過幾次這樣的不是局部最優的移動后會到達D點，于是就跳出了局部最大值A。第3頁/共30頁 工程中許多實際優化問題的目標函數都是非凸的，存在許多局部最優解。 求解全局優化問題的方法可分為兩類： 確定性方法和隨機性方法。 確定性算法適用于求解具有一些特殊特征的問題，而梯度法和一般的隨機搜索方法則沿著目標函數下降方向搜索，因此常常陷入局部而非全局最優解。 第4頁/共30頁 模擬退火算法（SA）是一種通用概率算法。用來在一個大的搜索空間內尋找問題的最優解。 1953年，Metropolis等提出了模擬退火的思想。 1983年，Kirkpatrick等將SA引入組合優化領域。 第5頁/共30頁

3、退火，俗稱固體降溫 先把固體加熱至足夠高溫，使固體中所有粒子處于無序的狀態，然后將溫度緩慢下降，粒子漸漸有序，這樣只要溫度上升得足夠高，冷卻過程足夠慢，則所有粒子最終會處于最低能態。第6頁/共30頁 算法試圖隨著控制參數T的降低，使目標函數值f（內能E）也逐漸降低，直至趨于全局最小值（退火中低溫時的最低能量狀態），算法工作過程就像固體退火過程一樣。6.1 算法基本理論算法基本理論模擬退火算法的由來模擬退火退火解粒子狀態最優解能量最低的狀態目標函數f內能控制參數溫度T第7頁/共30頁以概率接受新狀態 第8頁/共30頁新狀態的內能當前狀態的內能溫度EjEi（更差的解）時，0P10000 結束，輸出

4、當前解 YNYNNYYN擾動：數隨機產生01的數二變換法三變換法NY第19頁/共30頁 第20頁/共30頁 第21頁/共30頁while t=tf for r=1:Markov_length if (rand 0.5) %隨機產生01的數，若小于，則二變換 ind1 = 0; ind2 = 0; while (ind1 = ind2) ind1 = ceil(rand.*amount); ind2 = ceil(rand.*amount); end tmp1 = sol_new(ind1); sol_new(ind1) = sol_new(ind2); sol_new(ind2) = tmp1

5、; else %否則，三變換 ind1 = 0; ind2 = 0; ind3 = 0; while (ind1 = ind2) | (ind1 = ind3) . | (ind2 = ind3) | (abs(ind1-ind2) = 1) ind1 = ceil(rand.*amount); ind2 = ceil(rand.*amount); ind3 = ceil(rand.*amount); end tmp1 = ind1;tmp2 = ind2;tmp3 = ind3; 第22頁/共30頁 if (ind1 ind2) & (ind2 ind3) elseif (ind1

6、ind3) & (ind3 ind2) ind2 = tmp3;ind3 = tmp2; elseif (ind2 ind1) & (ind1 ind3) ind1 = tmp2;ind2 = tmp1; elseif (ind2 ind3) & (ind3 ind1) ind1 = tmp2;ind2 = tmp3; ind3 = tmp1; elseif (ind3 ind1) & (ind1 ind2) ind1 = tmp3;ind2 = tmp1; ind3 = tmp2; elseif (ind3 ind2) & (ind2 ind1) in

7、d1 = tmp3;ind2 = tmp2; ind3 = tmp1; end % ind1 ind2 ind3 tmplist1 = sol_new(ind1+1):(ind2-1); %u、v之間的城市 sol_new(ind1+1):(ind1+ind3-ind2+1) = . sol_new(ind2):(ind3); %將v到w的城市移到u后面 sol_new(ind1+ind3-ind2+2):ind3) = . tmplist1; %u、v之間的城市移到w后面 end第23頁/共30頁 第24頁/共30頁 % 計算目標函數即內能 E_new = 0; for i = 1 : (a

8、mount-1) E_new = E_new + . dist_matrix(sol_new(i),sol_new(i+1); end %從第一個城市到最后一個城市的距離 E_new = E_new + . dist_matrix(sol_new(amount),sol_new(1);第25頁/共30頁 第26頁/共30頁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第27頁/共30頁