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