模擬退火算法介紹(摘自08集訓(xùn)隊(duì) 顧研《淺談隨機(jī)化思想在幾何問(wèn)題中的應(yīng)用》)


    一.模擬退火算法的原理

模擬退火算法是一種元啟發(fā)式（Meta-Heuristics）算法，來(lái)源于固體退火原理，將固體加熱至充分高的溫度，再讓其徐徐冷卻。加熱時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/kt，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。

    二.模擬退火算法的模型

① 初始化：初始溫度T(充分大)，初始解狀態(tài)S(算法迭代的起點(diǎn))， 每次迭代次數(shù)L

② for k=1 to L 做③至⑥

③ 產(chǎn)生新解S’

④ 計(jì)算增量Δt′=C(S′)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)

⑤ 若Δt′<0則接受S’作為新的當(dāng)前解，否則以概率e-Δt/k接受S’作為新的當(dāng)前解

⑥ 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序

⑦ T逐漸減少，然后轉(zhuǎn)②

    回到此題，題意為：平面上有一個(gè)矩形，在矩形內(nèi)有一些陷阱。求得矩形內(nèi)一個(gè)點(diǎn)，該點(diǎn)離與它最近的已知陷阱最遠(yuǎn)（點(diǎn)的個(gè)數(shù)≤1000）。精度要求：1/10。

這題的精度要求不高，一個(gè)很樸素的想法是枚舉平面中的一些網(wǎng)格點(diǎn)并進(jìn)行判斷。當(dāng)然這樣的點(diǎn)太多了，我們必須選一些比較有“希望”的點(diǎn)，同時(shí)還不能忽略任何平面上的任何一點(diǎn)。

我們使用類比的方法引入模擬退火算法，初始解狀態(tài)S可以在矩形內(nèi)隨便選取，初始溫度T對(duì)應(yīng)于每次調(diào)整的距離D，產(chǎn)生新解的方式是在目前解為圓心、半徑為D的圓周上任取一點(diǎn)，評(píng)價(jià)函數(shù)取距離最近的陷阱的距離，終止條件為D足夠小。

由此可得本問(wèn)題的模擬退火算法：由初始解S和控制參數(shù)初值D開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減D值，算法終止時(shí)可以得到一組解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表（Cooling Schedule）控制，包括控制參數(shù)的初值D及其衰減因子D’、每個(gè)值D時(shí)的迭代次數(shù)L。

模擬退火算法還有一個(gè)特點(diǎn)：具有并行性。因此我們可以將初始解S改成初始解集，對(duì)于每個(gè)候選解都進(jìn)行迭代，答案取最終解集的最優(yōu)解。

由于我們必須保證能覆蓋矩形上的每個(gè)位置，因此在①中確定p后（我們按網(wǎng)格狀放置），②中的delta可取max{矩形邊長(zhǎng)}/sqrt(n)。設(shè)算法的迭代次數(shù)為t，則算法的復(fù)雜度O（P*L*t*n）。
   

POJ 1379