大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講現(xiàn)代啟發(fā)式算法之模擬退火算法

1、大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法1現(xiàn)代優(yōu)化技術(shù)現(xiàn)代優(yōu)化技術(shù)第第8 8講：現(xiàn)代啟發(fā)式算法之模擬退火算法講：現(xiàn)代啟發(fā)式算法之模擬退火算法大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法2現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 別名別名meta-solutionmeta-solutionmodern heuristicsmodern heuristics 含義含義（其一其一） 啟發(fā)式方法的有機(jī)結(jié)合啟發(fā)式方法的有機(jī)結(jié)合大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法3現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 含義含義

2、（其二其二）模擬某些現(xiàn)象模擬某些現(xiàn)象 simulated annealingsimulated annealing法法 ( (退火退火現(xiàn)象現(xiàn)象) ) tabu search tabu search （大腦的大腦的思考思考過程過程） genetic algorithm genetic algorithm （遺伝（遺伝現(xiàn)象現(xiàn)象） 含義含義（其三其三）通過改變參數(shù)可以得到的各種通過改變參數(shù)可以得到的各種“無限運(yùn)行無限運(yùn)行時(shí)間時(shí)間”近似算法近似算法（any time algorithmsany time algorithms）大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法4現(xiàn)代啟發(fā)式算法

3、之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法探索機(jī)制：現(xiàn)代啟發(fā)式算法探索機(jī)制： 集中化集中化與與多多樣樣化化的對(duì)立與統(tǒng)一的對(duì)立與統(tǒng)一 集中化集中化(intensification)(intensification)：在良解的附近存在良解在良解的附近存在良解 (proximate (proximate optimality property)optimality property)?；谶@一性質(zhì)，基于這一性質(zhì)， 在較好解的周圍集中在較好解的周圍集中探索探索 多様化多様化(diversification)(diversification) 避免在避免在悪解悪解的周圍滯留及長(zhǎng)時(shí)間無為探索

4、，強(qiáng)制到迄今為止的周圍滯留及長(zhǎng)時(shí)間無為探索，強(qiáng)制到迄今為止尚未探索的領(lǐng)域進(jìn)行探索尚未探索的領(lǐng)域進(jìn)行探索大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法5現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法集中化集中化 intensificationintensification因?yàn)檫@附近因?yàn)檫@附近良解良解比較多比較多再花點(diǎn)功夫找找看再花點(diǎn)功夫找找看大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法6現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法多多樣樣化化 diversificationdiversification這附近已經(jīng)探索得差不多了這附近已經(jīng)探索得差

5、不多了再到別的地方找找看再到別的地方找找看大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法7現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 集中化與多樣化的有機(jī)結(jié)合集中化與多樣化的有機(jī)結(jié)合多様化多様化集中化集中化大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法8現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 simulated annealing simulated annealing 法法 （模擬退火法模擬退火法） 隨機(jī)局部探索法隨機(jī)局部探索法 + + 系統(tǒng)地改變系統(tǒng)溫度參數(shù)系統(tǒng)地改變系統(tǒng)溫度參數(shù) 集中化與多樣化探索結(jié)合的一種模式集中化與多樣化探索

6、結(jié)合的一種模式大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法9現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 simulated simulated annealingannealingalgorithmalgorithm大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法10現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法溫度高溫度高溫度溫度 t t0 0simulated annealing algorithmsimulated annealing algorithm 模擬金屬退火模擬金屬退火( (annealingannealing) )現(xiàn)象的邏輯

7、現(xiàn)象的邏輯逐漸逐漸冷卻冷卻大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法11現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法simulated annealing algorithmsimulated annealing algorithm高溫期高溫期逐漸逐漸冷卻冷卻低溫期低溫期大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法12現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 simulated simulated annealingannealingalgorithmalgorithm大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法13

8、現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法溫度溫度與接受概率的關(guān)系與接受概率的關(guān)系0 0=f(y)-f(x)=f(y)-f(x)低溫低溫高溫高溫接受概率接受概率1 1大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法14現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 simulated annealing simulated annealing # # 模擬退火法的參數(shù)模擬退火法的參數(shù) 初始溫度初始溫度 ：適當(dāng)?shù)母邷貐^(qū)域：適當(dāng)?shù)母邷貐^(qū)域 冷卻率冷卻率 ：冷卻（溫度下降）的程序：冷卻（溫度下降）的程序 終止條件終止條件 ：同一溫度下探索的次數(shù)等：同一溫度下探索的

9、次數(shù)等 停機(jī)規(guī)則停機(jī)規(guī)則 ：停止探索的標(biāo)準(zhǔn)，如最低溫度標(biāo)準(zhǔn)、最：停止探索的標(biāo)準(zhǔn)，如最低溫度標(biāo)準(zhǔn)、最大無更新迭代次數(shù)等大無更新迭代次數(shù)等0tttg,maxtmint大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法15現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法 對(duì)數(shù)對(duì)數(shù)冷卻冷卻 (logarithmic cooling)(logarithmic cooling) 幾何幾何冷卻冷卻 (geometric cooling)(geometric cooling) 冷卻冷卻程序程序大連海事大學(xué)現(xiàn)代優(yōu)化技術(shù)第8講：現(xiàn)代啟發(fā)式算法之模擬退火算法16現(xiàn)代啟發(fā)式算法之模擬退火算法現(xiàn)代啟發(fā)式算法之模擬退火算法simulated annealingsimulated annealing弱點(diǎn)弱點(diǎn) 沒有記憶沒有記憶探索探索后的解的集合的信息后的解的集合的信息 存在相同解反復(fù)探索的可能性存在相同解反復(fù)探索的可能性 又被稱為又被稱為blind searchblind sea