1、現代優化技術現代優化技術第第8 8講：現代啟發式算法之模擬退火算法講：現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 別名別名 Meta-solutionMeta-solution Modern heuristicsModern heuristics 含義其一）含義其一） 啟發式方法的有機結合啟發式方法的有機結合現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 含義其二）含義其二） 模擬某些現象模擬某些現象 Simulated AnnealingSimulated Annealing法法 ( (退火退火現現象象) ) Tabu Search Tab

2、u Search （大腦的思考過程）（大腦的思考過程） Genetic Algorithm Genetic Algorithm （遺伝遺伝現象）現象） 含義其三）含義其三） 通過改變參數可以得到的各種通過改變參數可以得到的各種“無限運無限運行時間行時間近似算法近似算法any time any time algorithmsalgorithms）現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法現代啟發式算法探索機制：現代啟發式算法探索機制： 集中化與多樣化的對立與統一集中化與多樣化的對立與統一 集中化集中化(intensification)：在良解的附近存在良解：在良解的附近存在良解 (

3、proximate optimality property)。基于這一性質，。基于這一性質， 在較好解的周圍集中探在較好解的周圍集中探索索 多様化多様化(diversification) 避免在悪解的周圍滯留及長時間無為探索，強制到迄今為止尚未避免在悪解的周圍滯留及長時間無為探索，強制到迄今為止尚未探索的領域進行探索探索的領域進行探索現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法集中化集中化 intensification intensification因為這附近良解比較多因為這附近良解比較多再花點功夫找找看再花點功夫找找看現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法多樣

4、化多樣化 diversification diversification這附近已經探索得差不多了這附近已經探索得差不多了再到別的地方找找看再到別的地方找找看現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 集中化與多樣化的有機結合集中化與多樣化的有機結合多多様様化化集中化集中化現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 Simulated Annealing Simulated Annealing 法法 （模擬退火法）（模擬退火法） 隨機局部探索法隨機局部探索法 + + 系統地改變系統溫度參數系統地改變系統溫度參數 集中化與多樣化探索結合的一種模式集中化與多樣化探索結合的

5、一種模式現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 Simulated AnnealingAlgorithm現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法溫度高溫度高溫度溫度 T T0 0Simulated Annealing AlgorithmSimulated Annealing Algorithm 模擬金屬退火模擬金屬退火(annealing)(annealing)現象的邏輯現象的邏輯逐漸冷卻逐漸冷卻現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法Simulated Annealing AlgorithmSimulated Annealing Algori

6、thm高溫期高溫期逐漸冷卻逐漸冷卻低溫期低溫期現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 Simulated Simulated AnnealingAnnealingAlgorithmAlgorithm現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法溫度與接受概率的關系溫度與接受概率的關系0 0=f(y)-f(x)=f(y)-f(x)低溫低溫高溫高溫接受概率接受概率1 1現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 Simulated Annealing Simulated Annealing # # 模擬退火法的參數模擬退火法的參數初始溫度初始溫度 ：適當的

7、高溫區域：適當的高溫區域冷卻率冷卻率 ：冷卻溫度下降的程序：冷卻溫度下降的程序終止條件終止條件 ：同一溫度下探索的次數等：同一溫度下探索的次數等停機規則停機規則 ：停止探索的標準，如最低溫度標準、最大：停止探索的標準，如最低溫度標準、最大無更新迭代次數等無更新迭代次數等0TtTg,maxtminT現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法 對數冷卻對數冷卻 (logarithmic cooling) (logarithmic cooling) 幾何冷卻幾何冷卻 (geometric cooling) (geometric cooling) 冷卻程序冷卻程序現代啟發式算法之模擬退火算法現代啟發式算法之模擬退火算法Simulated AnnealingSimulated Annealing弱點弱點 沒有記憶探索后的解的集合的信息沒有記憶探索后的解的集合的信息 存在相同解反復探索的可能性存在相同解反復探索的可能性 又被稱為又被稱為blind searchblind sear