優(yōu)化算法講ppt課件(2)-資料下載頁(yè)
2025-05-06 00:31本頁(yè)面
【正文】 xold時(shí)，系統(tǒng)受到某種擾動(dòng)而可能會(huì)使其狀態(tài)變?yōu)?xnew。 與此相對(duì)應(yīng)，系統(tǒng)的能量也可能會(huì)從 E(xold)變成 E(xnew)，系統(tǒng)由狀態(tài) xold變?yōu)闋顟B(tài) xnew的 接受概率 可由下面的 Metropolis規(guī)則來(lái)確定： ? if E(xnew) E(xold) if E(xnew) ≥E(xold) 當(dāng)新?tīng)顟B(tài)使系統(tǒng)的能量函數(shù)值減少時(shí)，系統(tǒng)一定接受這個(gè)新的狀態(tài)；而當(dāng)新?tīng)顟B(tài)使系統(tǒng)的能量函數(shù)值增加時(shí)，系統(tǒng)也以某一概率接受這個(gè)新的狀態(tài)。 1( ) ( )e x p n e w o l dp E x E xT??? ?? ?????????2022/6/3 37 模擬退火算法 ? 算法 Simulated Annealing ? ① 隨機(jī)產(chǎn)生一個(gè)初始解，以它作為當(dāng)前最優(yōu)解，并計(jì)算目標(biāo)函數(shù)值。 ? ② 設(shè)置初始溫度： θ← To 。 ? ③ 設(shè)置循環(huán)計(jì)數(shù)器初值： t=1。 ? ④ 對(duì)當(dāng)前最優(yōu)解作一隨機(jī)變動(dòng) ,產(chǎn)生一新的解。計(jì)算新的目標(biāo)函數(shù)值，并計(jì)算目標(biāo)函數(shù)值的增量 Δ。 ? ⑤ 如果 Δ ＜ 0，則接受該新產(chǎn)生的解為當(dāng)前最優(yōu)解； 如果 Δ ≥0，則以概率 p = exp( Δ / θ)接受該新產(chǎn)生的解為當(dāng)前最優(yōu)解。 ? ⑥ 如果 t＜終止步效，則： t=t+1，轉(zhuǎn)向第④步。 ? ⑦ 如果未到達(dá)冷卻狀態(tài)，則： θ← T(t)轉(zhuǎn)向第③步； 如果已到達(dá)冷卻狀態(tài)，則：輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束。 2022/6/3 38 遺傳模擬退火算法 ? 遺傳模擬退火算法 是將 遺傳算法 與 模擬退火算法 相結(jié)合而構(gòu)成的一種優(yōu)化算法 。 ? 遺傳算法 的局部搜索能力較差 、 但把握搜索過(guò)程總體的能力較強(qiáng)； ? 而 模擬退火算法 具有較強(qiáng)的局部搜索能力 ， 并能使搜索過(guò)程避免陷入局部最優(yōu)解 ， 但模擬退火算法卻對(duì)整個(gè)搜索空間的狀況了解不多 ， 不便于使搜索過(guò)程進(jìn)入最有希望的搜索區(qū)域 。 2022/6/3 39 遺傳模擬退火算法 ? 算法 Geic Simulated Annealing ? ① 進(jìn)化代數(shù)計(jì)數(shù)器初始化： t← 0。 ? ② 隨機(jī)產(chǎn)生初始群體 P(t)。 ? ③ 評(píng)價(jià)群體 P(t)的適應(yīng)度。 ? ④ 個(gè)體交叉操作： P?(t) ← Crossover[P(t)] ? ⑤ 個(gè)體變異操作： P??(t) ← Mutation[P?(t)] ? ⑥ 個(gè)體模擬退火操作： P???(t) ← SimulatedAnnealing[P??(t)] ? ⑦ 評(píng)價(jià)群體 P???(t)的適應(yīng)度。 ? ⑧ 個(gè)體選擇、復(fù)制操作： P(t+1) ← Reproduction[P(t)∪ P???(t)] ? ⑨ 終止條件判斷。若不滿足終止條件，則 : t ← t+1，轉(zhuǎn)到第④步，繼續(xù)進(jìn)化過(guò)程；若滿足終止條件．則 : 輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束。 2022/6/3 40 遺傳模擬退火算法 ? 在模擬退火算法算法中溶入遺傳算法： 如并行組合模擬退火算法 PRSA（ Parallel Rebination Simulated Annealing） ? ① 隨機(jī)生成含有 M個(gè)個(gè)體的初始群體 P(0)。 ? ② 設(shè)置初始溫度參數(shù)： T ← Tmax ? ③ 對(duì) P(t)中的各個(gè)個(gè)體進(jìn)行隨機(jī)配對(duì)，對(duì)其中的每一對(duì)個(gè)體做下述處理： (a) 進(jìn)行交叉和變異運(yùn)算，由兩個(gè)父代個(gè)體 P P2生成兩個(gè)子代個(gè)體 c1和c2。 (b)對(duì)由父代個(gè)體和子代個(gè)體所組成的兩個(gè)個(gè)體組 P1和 c1， P2和 c2，以概率 p接受父代個(gè)體為下一代群體中的個(gè)體，以概率 (1p)接受子代個(gè)體為下一代群體中的個(gè)體。 其中， 式中， fp和 fc分別為父代個(gè)體和子代個(gè)體所對(duì)應(yīng)的目標(biāo)函數(shù)值。 ? ④ 終止條件判斷。若不滿足終止條件，則：按降溫表更新溫度參效 T，t=t+1，轉(zhuǎn)向第③步；若滿足終止條件，則：輸出當(dāng)前最優(yōu)點(diǎn)，算法結(jié)束。 11 e x p pcp ffT? ???? ????2022/6/3 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1