論文模擬退火算法(編輯修改稿)
2025-07-10 23:44 本頁面
【文章內(nèi)容簡介】 olis 鏈長 L (2)對當(dāng)前溫度 T 和 1,2, ,kL? ，重復(fù)步驟 (3)～ (6). (3)對當(dāng)前解 1S 隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解 2S 。 (4)計(jì)算 2S 的增量 39。 21( ) ( )t df f S f S? ? ? ?,其中 1()fS 是 1S 代價(jià)函數(shù)。 (5)若 0df? ，則接受 2S 作為當(dāng)前的解，即 12SS? ；否則計(jì)算 2S 的接受概率exp( / )df T? ，即隨機(jī)產(chǎn)生 (0,1)區(qū)間上均勻分布 rand ,若 exp ( / )df T ra nd??，也接受 2S 作為新的當(dāng)前解， 12SS? ；否則保留當(dāng)前解 1S (6)如果滿足終止條件則輸出當(dāng)前作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有接受時(shí)終止算法 。 (7) T 逐漸減少，且 0T? ，然后轉(zhuǎn)第 2 步。 模擬退火算法的步驟 第一部是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于 解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法好時(shí)，通常選擇有當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的領(lǐng)域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。 第二步是計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對大多數(shù)而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。 第三步是判斷新解是否被接受，判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是 Metropolis 準(zhǔn)則：若 39。0t??則接受 39。S 作為新的當(dāng)前解 S ，否則以概率exp( 39。/ )tT?? 接受 39。S 作為新的當(dāng)前解 S 。 第四步是當(dāng)新解被確定接受時(shí)，用心接代替當(dāng)前解，這只需將當(dāng)前解中 對應(yīng)于產(chǎn)生新解時(shí)的變換部分得以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭 代?？稍诖嘶A(chǔ)上開始下一輪實(shí)驗(yàn)。而當(dāng)前解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪實(shí)驗(yàn)。 模擬圖火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S (是算法迭代的起點(diǎn) )無關(guān)；模擬退火算法具有漸進(jìn)收斂性，已在理論上被證明是一種以概率 1收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 背包問題的描述 背包問題 (Knapsack Problem)是經(jīng)典 的 NP 完全問題，即假設(shè)有 m種物品，每種物品都有一個(gè)重量用 iw ( 0? )表示，一個(gè)價(jià)值用 ic ( 0? ) ( 1,2, ,im? ),同時(shí)有一個(gè)背包，其容量為 M 。先從 m 種物品中選取若干件，使其重量之和小于等于背包的容量，且價(jià)值和為最大，其中要求 iw 和 M 都是整數(shù)，定義 ix 為變量 ： 0 ( 1 , 2 , , )1ix i m????? 不 選 擇 物 品 i選 擇 物 品 i
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1