數(shù)值分析方法主編

李冬果李林高磊首都醫(yī)科大學(xué)生物醫(yī)學(xué)工程學(xué)院智能醫(yī)學(xué)工程學(xué)學(xué)系面向“四新”人才培養(yǎng)普通高等教育系列教材第八章智能優(yōu)化算法基礎(chǔ)第一節(jié)最優(yōu)化問題和隨機(jī)算法第二節(jié)禁忌搜索算法第三節(jié)模擬退火方法第四節(jié)遺傳算法第五節(jié)粒子群算法

目錄/Contents

8.3模擬退火方法模擬退火算法（simulatedannealing,SA）是一種全局優(yōu)化算法，它模仿了熱力學(xué)中的物理退火過程。主要特點是設(shè)置了逐漸降低的“退火溫度”，基于此允許在搜索過程中以一定概率獲得較差的結(jié)果，從而使算法擁有了跳出局部最優(yōu)解的能力。該算法最早于1953年由Metropolis提出，并在1983年由Kirkpatrick等人應(yīng)用于組合優(yōu)化問題。8.3.1算法原理物理退火(annealing)過程是冶金和材料科學(xué)當(dāng)中采用的一種技術(shù)，它通過將物體加熱到較高水平，在保持一段合適的高溫后，再逐漸冷卻的過程。整個退火過程可以分為三個部分：（1）升溫部分，隨著溫度的不斷提升，物體被溶解為液態(tài)，組成物體的粒子自由運動，從而使整個系統(tǒng)處于一個比較均勻無序的狀態(tài)；（2）等溫過程，而當(dāng)物體保持某個溫度時，將達(dá)到一個平衡狀態(tài)，也就是在此溫度下自由能最小的狀態(tài)；（3）降溫過程，當(dāng)溫度改變時，物體的平衡狀態(tài)將隨之發(fā)生改變，當(dāng)溫度降低時，物體粒子運動范圍逐漸減小，整個系統(tǒng)逐漸由無序變?yōu)橛行颉ＤM退火過程就是優(yōu)化算法比作物體的退火過程。將優(yōu)化問題的可能解比作退火過程中的系統(tǒng)狀態(tài)，將最小化優(yōu)化的目標(biāo)函數(shù)比作退火過程中的系統(tǒng)能量，令系統(tǒng)接受較差狀態(tài)（也就是反而增大了優(yōu)化目標(biāo)函數(shù)的解）的概率依照“溫度”下降，從而既可以在高溫狀態(tài)下通過隨機(jī)的方式脫離局部最優(yōu)解，又可以使溫度下降時，能夠穩(wěn)定獲得一個最優(yōu)解。8.3.2算法設(shè)計

8.3.3算法實現(xiàn)

（5）算法終止條件。常用的算法終止條件，包括溫度值低于給定閾值，降溫次數(shù)大于給定閾值，或者能量（優(yōu)化目標(biāo)函數(shù)）改變值小于給定閾值等。（6）算法的收斂性。經(jīng)過研究，理論上已經(jīng)證明模擬退火算法具有漸進(jìn)收斂性，是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法。但在實際應(yīng)用中