模擬退火算法與MATLAB實(shí)現(xiàn)課件

模擬退火算法及其MATLAB實(shí)現(xiàn)模擬退火算法及其MATLAB實(shí)現(xiàn)1第6章模擬退火算法及其MATLAB實(shí)現(xiàn)6.1算法基本理論6.2算法的MATLAB實(shí)現(xiàn)6.3應(yīng)用實(shí)例第6章模擬退火算法及其MATLAB實(shí)現(xiàn)6.1算法基本理2簡(jiǎn)單了解退火算法特點(diǎn)介紹模擬退火前，先介紹爬山算法。

爬山算法是一種簡(jiǎn)單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。簡(jiǎn)單了解退火算法特點(diǎn)介紹模擬退火前，先介紹爬3簡(jiǎn)單了解退火算法特點(diǎn)爬山算法如圖所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏點(diǎn)無論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。

模擬退火算法

在搜索到局部最優(yōu)解A后，會(huì)以一定的概率接受到E的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。簡(jiǎn)單了解退火算法特點(diǎn)爬山算法模擬退火算法46.1算法基本理論一、算法概述

工程中許多實(shí)際優(yōu)化問題的目標(biāo)函數(shù)都是非凸的，存在許多局部最優(yōu)解。求解全局優(yōu)化問題的方法可分為兩類：

確定性方法和隨機(jī)性方法。確定性算法適用于求解具有一些特殊特征的問題，而梯度法和一般的隨機(jī)搜索方法則沿著目標(biāo)函數(shù)下降方向搜索，因此常常陷入局部而非全局最優(yōu)解。

6.1算法基本理論一、算法概述工程中56.1算法基本理論一、算法概述模擬退火算法（SA）是一種通用概率算法。用來在一個(gè)大的搜索空間內(nèi)尋找問題的最優(yōu)解。1953年，Metropolis等提出了模擬退火的思想。1983年，Kirkpatrick等將SA引入組合優(yōu)化領(lǐng)域。

6.1算法基本理論一、算法概述模擬退火算法66.1算法基本理論二、基本思想

退火，俗稱固體降溫先把固體加熱至足夠高溫，使固體中所有粒子處于無序的狀態(tài)，然后將溫度緩慢下降，粒子漸漸有序，這樣只要溫度上升得足夠高，冷卻過程足夠慢，則所有粒子最終會(huì)處于最低能態(tài)。6.1算法基本理論二、基本思想7算法試圖隨著控制參數(shù)T的降低，使目標(biāo)函數(shù)值f（內(nèi)能E）也逐漸降低，直至趨于全局最小值（退火中低溫時(shí)的最低能量狀態(tài)），算法工作過程就像固體退火過程一樣。6.1算法基本理論模擬退火算法的由來模擬退火退火解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)目標(biāo)函數(shù)f內(nèi)能控制參數(shù)溫度T算法試圖隨著控制參數(shù)T的降低，使目標(biāo)函6.1算86.1算法基本理論Metropolis準(zhǔn)則——–以概率接受新狀態(tài)

6.1算法基本理論Metropolis準(zhǔn)則——–以概率9新狀態(tài)的內(nèi)能當(dāng)前狀態(tài)的內(nèi)能溫度Ej>Ei（更差的解）時(shí)，0<P<1,P隨著T的減小而減?。?.1算法基本理論

新狀態(tài)的內(nèi)能當(dāng)前狀態(tài)的內(nèi)能溫度Ej>Ei（更差的解）時(shí)，6.106.1算法基本理論當(dāng)初始溫度足夠高時(shí)，概率P接近于1，所以當(dāng)前解經(jīng)過擾動(dòng)產(chǎn)生的新解，無論好壞，基本都可以被接受為當(dāng)前解。即不受制于當(dāng)前解，不會(huì)困在局部最優(yōu)解中，可以遍及解空間的各個(gè)區(qū)域，當(dāng)然也不會(huì)保持在最優(yōu)解處。隨著溫度降低，概率降低，較差解被接受的次數(shù)減少，當(dāng)前解逐漸停留到最優(yōu)解周圍。

溫度達(dá)到終止溫度前，概率足夠低，使得只有最優(yōu)解被接受，較差解都不接受。最優(yōu)解即為最后接受的當(dāng)前解。算法總結(jié)在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。6.1算法基本理論當(dāng)初始溫度足夠高時(shí)，概率116.1算法基本理論三、算法其他參數(shù)的說明

6.1算法基本理論三、算法其他參數(shù)的說明

126.1算法基本理論四、算法基本步驟

6.1算法基本理論四、算法基本步驟

13初始溫度，隨機(jī)產(chǎn)生初始解。

接受新解作為當(dāng)前解計(jì)算概率與[0,1)隨機(jī)數(shù)之間的差值差值大于0

結(jié)束，輸出當(dāng)前解

YNYNNYYN初始溫度，隨機(jī)產(chǎn)生初始解。

接受新解作為當(dāng)前解計(jì)算概率與[146.1算法基本理論四、算法基本步驟算法實(shí)質(zhì)分為兩層循環(huán)，在任一溫度下隨機(jī)擾動(dòng)產(chǎn)生新解，計(jì)算目標(biāo)函數(shù)值的變化，決定是否接受。由于算法初始溫度比較高，這樣使E增大的新解在初始時(shí)也可能被接受，因此能跳出局部極小值，然后通過緩慢地降低溫度，算法可能收斂到全局最優(yōu)解。雖然在低溫時(shí)接受函數(shù)已經(jīng)非常小了，但仍不排除有接受更差解得可能，因此一般都會(huì)把退火過程中碰到的最好的可行解（歷史最優(yōu)解）也記錄下來，與終止算法前最后被接受解一并輸出。6.1算法基本理論四、算法基本步驟算法實(shí)質(zhì)156.1算法基本理論五、幾點(diǎn)說明1、新解的產(chǎn)生

要求盡可能地遍及解空間的各個(gè)區(qū)域，這樣，在某一恒定溫度下，不斷產(chǎn)生新解時(shí)，就可能跳出局部最優(yōu)解。2、收斂的一般條件：初始溫度足夠高；熱平衡時(shí)間足夠長(zhǎng)；終止溫度足夠低；降溫過程足夠緩慢；

6.1算法基本理論五、幾點(diǎn)說明1、新解的產(chǎn)生166.1算法基本理論五、幾點(diǎn)說明

6.1算法基本理論五、幾點(diǎn)說明

176.1算法基本理論六、算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：計(jì)算過程簡(jiǎn)單，通用，魯棒性強(qiáng)，適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問題。缺點(diǎn)：收斂速度慢，執(zhí)行時(shí)間長(zhǎng)，算法性能與初始值有關(guān)及參數(shù)敏感等缺點(diǎn)。6.1算法基本理論六、算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：缺點(diǎn)：186.2算法的MATLAB實(shí)現(xiàn)旅行商問題一名商人要到n個(gè)不同的城市去推銷商品，每2個(gè)城市I和j之間的距離為d，如何選擇一條路徑使得商人每個(gè)城市走一遍后回到起點(diǎn)所走的路徑最短。例：有52座城市，已知每座城市的坐標(biāo)，求每個(gè)城市走一遍后回到起點(diǎn)，所走的路徑最短。6.2算法的MATLAB實(shí)現(xiàn)旅行商問題一19初始溫度(93)，隨機(jī)產(chǎn)生初始解(1到52的隨機(jī)排列)。

接受新解作為當(dāng)前解計(jì)算概率與[0,1)隨機(jī)數(shù)之間的差值差值大于0

擾動(dòng)次數(shù)>10000

結(jié)束，輸出當(dāng)前解

YNYNNYYN擾動(dòng)：數(shù)>0.5隨機(jī)產(chǎn)生0~1的數(shù)二變換法三變換法NY初始溫度(93)，隨機(jī)產(chǎn)生初始解(1到52的隨機(jī)排列)。

206.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

216.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

226.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟whilet>=tfforr=1:Markov_lengthif(rand<0.5)

%隨機(jī)產(chǎn)生0~1的數(shù)，若小于0.5，則二變換ind1=0;ind2=0;while(ind1==ind2)ind1=ceil(rand.*amount);ind2=ceil(rand.*amount);endtmp1=sol_new(ind1);sol_new(ind1)=sol_new(ind2);sol_new(ind2)=tmp1;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);endtmp1=ind1;tmp2=ind2;tmp3=ind3;

6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟while236.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟if(ind1<ind2)&&(ind2<ind3)elseif(ind1<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)ind1=tmp3;ind2=tmp2;ind3=tmp1;end%ind1<ind2<ind3tmplist1=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后面end6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟246.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

256.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟%計(jì)算目標(biāo)函數(shù)即內(nèi)能E_new=0;fori=1:(amount-1)E_new=E_new+...dist_matrix(sol_new(i),sol_new(i+1));end

%從第一個(gè)城市到最后一個(gè)城市的距離E_new=E_new+...dist_matrix(sol_new(amount),sol_new(1));6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟266.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

6.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟

276.2算法的MATLAB實(shí)現(xiàn)一、算法設(shè)計(jì)步驟ifE_new<E_currentE_current=E_new;sol_current=sol_new;ifE_new<E_best%冷卻過程中最好的解保存下來′E_best=E_new;sol_best=sol_new;endelse

%若新解的目標(biāo)函數(shù)大于當(dāng)前解的，%則以一定的概率接受新解