模擬退火算法課件

1、模擬退火算法模擬退火算法模擬退火算法1、模擬退火算法概述1.1 基本思想1.2 固體退火過程1.3 Metropolis準(zhǔn)則1.4 模擬退火算法與物理退火的相似性2、模擬退火算法的實(shí)現(xiàn)和應(yīng)用2.1 模擬退火算法的步驟2.2 模擬退火算法的優(yōu)缺點(diǎn)2.3 模擬退火算法應(yīng)用舉例模擬退火算法1、模擬退火算法概述1、模擬退火算法概述1.1基本思想模擬退火算法(Simulated Annealing Algorithm，SAA)是一種基于迭代求解策略的隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性

2、在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號處理等領(lǐng)域。模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。1、模擬退火算法概述1.1基本思想模擬退火算法(Simu1、模擬退火算法概述1.1基本思想 用一種形象的比喻來描述模擬退火：兔子喝醉了。它隨機(jī)地跳了很長時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒

3、了并朝最高方向跳去。這就是模擬退火。 模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會以一定的概率接受到E的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。 圖11、模擬退火算法概述1.1基本思想 用一種形起源：物理退火過程 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而冷卻時(shí)粒子漸趨有序，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。加溫過程等溫過程冷卻過程1、模擬退火算法概述1.2

4、固體退火過程 模擬退火算法來源于固體退火原理，將固體加溫至模擬退火算法采用Metropolis接受準(zhǔn)則以概率接受新狀態(tài) 若在溫度T，當(dāng)前狀態(tài)i 新狀態(tài)j 若EjEi，則接受j為當(dāng)前狀態(tài)； 否則，若概率 p=exp-(Ej-Ei)/kT大于0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)。 1、模擬退火算法概述1.3 Metropolis準(zhǔn)則模擬退火算法采用Metropolis接受準(zhǔn)則以概率接受新1、模擬退火算法概述1.4 模擬退火算法與物理退火的相似性1、模擬退火算法概述1.4 模擬退火算法與物理退火的相似1、模擬退火算法概述1.4 模擬退火算法與物理退火的相似性

5、物理退火過程物體內(nèi)部的狀態(tài)狀態(tài)的能量溫度熔解過程退火冷卻過程狀態(tài)的轉(zhuǎn)移能量最低狀態(tài)模擬退火算法問題的解空間解的質(zhì)量控制參數(shù)設(shè)定初始溫度控制參數(shù)的修改解在鄰域中的變化最優(yōu)解物理退火過程模擬退火算法類比關(guān)系1、模擬退火算法概述1.4 模擬退火算法與物理退火的相似根據(jù)熱力學(xué)的原理，在溫度為T時(shí)，出現(xiàn)能量差為dE的降溫的概率為P(dE)，表示為：P(dE) = exp( dE/(kT) )其中k是一個(gè)常數(shù)，exp表示自然指數(shù)，且dE0。這條公式說白了就是：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0（否則就不叫退火了），因此dE/kT= J(

6、Y(i) (即移動后得到更優(yōu)解)，則總是接受該移動若J(Y(i+1) Tmin，滿足則對當(dāng)前最優(yōu)解S,按照某一鄰域函數(shù)， 產(chǎn)生一新的解j。計(jì)算新的目標(biāo)函數(shù)值J(j) ， 并計(jì)算目標(biāo)函數(shù)值的增量E= J(j) - J(i) 。4) 如果E0，則接受新解，令S= j； 如果E0，則p = exp(- E /TK); 并判斷 p random0,1 ，成立則接受新解S = j; 否則S=i。5) 降溫T=T*r,0r1，回到步驟3)6) 若T T_min ) dE = J( Y(i+1) ) - J( Y(i) ) ; if ( dE =0 ) %表達(dá)移動后得到更優(yōu)解，則總是接受移動 Y(i+1)

7、= Y(i) ; %接受從Y(i)到Y(jié)(i+1)的移動else if ( exp( dE/T ) random( 0 , 1 ) ) Y(i+1) = Y(i) ; %接受從Y(i)到Y(jié)(i+1)的移動 T = r * T ; %降溫退火 ，0r1 。i + ; 偽代碼如下：2、模擬退火算法的實(shí)現(xiàn)和應(yīng)2.1 模擬退火算法的優(yōu)缺點(diǎn)1）優(yōu)點(diǎn)：可以保證全局最優(yōu)特別適合組合優(yōu)化問題可以隨機(jī)選擇初始解對問題本身沒有特別要求，不會因?yàn)閱栴}實(shí)例的改變影響性能簡單易行，通用性好2）缺點(diǎn)： 模擬退火算法在求解規(guī)模較大的實(shí)際問題時(shí)，往往存在以下缺點(diǎn)： （1）收斂速度比較慢。 （2）盡管理論上只要計(jì)算時(shí)間足夠長，模

8、擬退火法就可以保證以概率1收斂于全局最優(yōu)點(diǎn)。但是在實(shí)際算法的實(shí)現(xiàn)過程中，由于計(jì)算速度和時(shí)間的限制，在優(yōu)化效果和計(jì)算時(shí)間二者之間存在矛盾，因而難以保證計(jì)算結(jié)果為全局最優(yōu)點(diǎn)，優(yōu)化效果不甚理想。 （3）在每一溫度下很難判定是否達(dá)到了平衡狀態(tài)2、模擬退火算法的實(shí)現(xiàn)和應(yīng)2.1 模擬退火算法的優(yōu)缺點(diǎn)12、模擬退火算法的實(shí)現(xiàn)和應(yīng)用2.3 模擬退火算法應(yīng)用舉例TSP問題： 一個(gè)商人欲到n個(gè)城市推銷商品，每兩個(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路經(jīng)最短。解空間目標(biāo)函數(shù)初始解選為2、模擬退火算法的實(shí)現(xiàn)和應(yīng)用2.3 模擬退火算法應(yīng)用舉例新解的產(chǎn)生(3種方法)1、互換操作(SWAP)隨機(jī)交換兩個(gè)不同城市的位置。2、逆序操作(INV)兩個(gè)不同隨機(jī)位置的城市逆序。3、插入操作(INS)隨機(jī)選擇某個(gè)城市插入到不同隨機(jī)位置。新解的產(chǎn)生(3種方法)1、互換操作(SWAP)隨機(jī)交換兩個(gè)不TSP 30個(gè)城市坐標(biāo)如下：41 94; 37 84; 54 67; 25 62; 7 64; 2 99;68 58; 71 44; 54 62; 83 69; 64 60; 18 54;22 60; 83 46; 91 38; 25