模擬退火算法(編輯修改稿)
2024-08-31 16:36 本頁面
【文章內(nèi)容簡介】 分布等）產(chǎn)生 狀態(tài)產(chǎn)生函數(shù) 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減小； (3)當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。 ? 方法 具體形式對算法影響不大 一般采用 min[1,exp(?C/t)] 狀態(tài)接受函數(shù) 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 收斂性分析 通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時難以得到精確的參數(shù)； 初溫應(yīng)充分大； ? 實(shí)驗表明 初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計算時間； 初溫 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 方法 （ 1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； （ 2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫； （ 3）利用經(jīng)驗公式。 初溫 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 數(shù)值計算估計方法示例 智能優(yōu)化計算 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 時齊算法的溫度下降函數(shù) （ 1） ， α越接近 1溫度下降越慢，且其大小可以不斷變化； （ 2） ，其中 t0為起始溫度， K為算法溫度下降的總次數(shù)。 溫度更新函數(shù) 10 ,0 ,1 ????? ?? ktt kk0tKkKtk??山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 非時齊模擬退火算法 每個溫度下只產(chǎn)生一個或少量候選解 ? 時齊算法 —— 常用的 Metropolis抽樣穩(wěn)定準(zhǔn)則 （ 1）檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （ 2）連續(xù)若干步的目標(biāo)值變化較?。? （ 3）按一定的步數(shù)抽樣（固定長度）。 （ 4）有接受和拒絕的比率控制跌代步數(shù)（比如給定一個跌代步長上限 U和接受比率指標(biāo) R） 內(nèi)循環(huán)終止準(zhǔn)則 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計 智能優(yōu)化計算 ? 常用方法 （ 1）設(shè)置終止溫度的閾值； （ 2）設(shè)置外循環(huán)迭代次數(shù)； （ 3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （ 4）概率分析方法 (接受概率控制法）。 外循環(huán)終止準(zhǔn)則 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高； 初值魯棒性強(qiáng)； 簡單、通用、易實(shí)現(xiàn)。 ? 模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。 模擬退火算法的優(yōu)缺點(diǎn) 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的可行方案 （ 1）設(shè)計合適的狀態(tài)產(chǎn)生函數(shù)； （ 2）設(shè)計高效的退火歷程； （ 3）避免狀態(tài)的迂回搜索； （ 4）采用并行搜索結(jié)構(gòu)； （ 5）避免陷入局部極小，改進(jìn)對溫度的控制方式； （ 6）選擇合適的初始狀態(tài)； （ 7）設(shè)計合適的算法終止準(zhǔn)則。 改進(jìn)內(nèi)容 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的方式 （ 1）增加升溫或重升溫過程，避免陷入局部極?。? （ 2）增加記憶功能（記憶“ Best so far”狀態(tài)）； （ 3）增加補(bǔ)充搜索過程（以最優(yōu)結(jié)果為初始解）； （ 4）對每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （ 5）結(jié)合其它搜索機(jī)制的算法； （ 6）上述各方法的綜合。 改進(jìn)內(nèi)容 山東大學(xué)威海分校信息工程學(xué)院 2022年 模擬退火算法的改進(jìn) 智能優(yōu)化計算 ? 改進(jìn)的思路
法律信息相關(guān)推薦
鄂ICP備17016276號-1