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