模擬退火算法 第四節(jié)

2.4模擬退火算法的應(yīng)用2.4.1應(yīng)用的一般要求模擬退火算法應(yīng)用的一般形式是：從選定的初始解開始，在借助于控制參數(shù)t遞減時(shí)產(chǎn)生的一系列馬氏鏈中，利用一個(gè)新解產(chǎn)生裝置和接受準(zhǔn)則，重復(fù)進(jìn)行包括“產(chǎn)生新解－計(jì)算目標(biāo)函數(shù)差－判斷是否接受新解－接受（或舍棄）新解”這四個(gè)任務(wù)的試驗(yàn)，不斷對當(dāng)前解迭代，從而達(dá)到使目標(biāo)函數(shù)最優(yōu)的執(zhí)行過程．因此，算法的應(yīng)用需滿足如下三個(gè)方面的要求：一．?dāng)?shù)學(xué)模型，由解空間，目標(biāo)函數(shù)和初始解三部分組成．解空間，它為問題的所有可能解的集合，它限定了初始解選取和新解產(chǎn)生時(shí)的范圍．對無約束的優(yōu)化問題，任一可能解即為一可行解，因此解空間就是所有可行解的集合．而在許多組合優(yōu)化問題中，一個(gè)解除滿足目標(biāo)函數(shù)最優(yōu)的要求外，還必須滿足一組約束，因此在解集中可能包含一些不可行解．為此，可以限定解空間僅為所有可行解的集合，即在構(gòu)造解時(shí)就考慮到對解的約束；也可允許解空間包含不可行解，而在目標(biāo)函數(shù)中加上所謂罰函數(shù)以“懲罰”不可行解的出現(xiàn)，將不可行解可行化．二．新解的產(chǎn)生和接受機(jī)制，可分為如下四個(gè)步驟：首先，由一個(gè)產(chǎn)生裝置從當(dāng)前解在解空間中產(chǎn)生一個(gè)新解．通常選擇由當(dāng)前解經(jīng)過簡單地變換即可產(chǎn)生新解的方法．其次，計(jì)算與新解伴隨的目標(biāo)函數(shù)差．第三，判斷新解是否被接受．最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則．其中t為控制參數(shù),Δf為新解與當(dāng)前解之間的目標(biāo)函數(shù)差（在最小化問題中）或當(dāng)前解與新解之間的目標(biāo)函數(shù)差（在最大化問題中）．此外，在有約束但又限定解空間僅包含可行解的問題中，上述接受準(zhǔn)則中還必須加上對新解的可行性判定．最后，當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解．此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代．可在此基礎(chǔ)上開始下一輪試驗(yàn)．而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)．三．冷卻進(jìn)度表．2.4.2組合優(yōu)化問題的應(yīng)用１．旅行商問題（TSP）一解空間解空間F可表為{1,2…n}的所有循環(huán)排列的集合，即其中每一循環(huán)排列表示遍訪n個(gè)城市的一條回路，πi=j表示在第i個(gè)次序訪問城市j，并約定πn+1=π1．初始解可選為(1,2…

n)．

二目標(biāo)函數(shù)注意到約定πn+1=π1

．三新解的產(chǎn)生此時(shí)的目標(biāo)函數(shù)即為訪問所有城市的路徑長度或稱為代價(jià)函數(shù)，須求其最小值，選為用2-opt法．任選訪問的序號u和v，交換u和v的位置，即可產(chǎn)生新路徑為（設(shè)u<v）四代價(jià)（目標(biāo)）函數(shù)差五接受準(zhǔn)則伴隨新解的代價(jià)函數(shù)差為六冷卻進(jìn)度表．

需由具體問題規(guī)模而定．例如康立山等對CHN144實(shí)例而言，可取t0280,tk1

tk,

0.92,Lk

100n，停止準(zhǔn)則是：在s個(gè)相繼的馬氏鏈中解無任何變化就終止算法．（如可取s=1）．初始路徑圖算法得到的優(yōu)化路徑圖2．0-1背包問題（ZKP）一解空間ZKP是一個(gè)有約束的優(yōu)化問題，對此，我們限定解空間為所有可行解的集合，即其中xi

=1表示物品i被選擇裝入背包．初始解選為(0,0…0)．二目標(biāo)函數(shù)為一需求最大值的價(jià)值函數(shù)但必須滿足約束三新解的產(chǎn)生隨機(jī)選取物品i，若i不在背包中，則將其直接裝入背包，或同時(shí)從背包中隨機(jī)取出另一物品j；若i已在背包中，則將其取出，并同時(shí)隨機(jī)裝入另一物品j．即x