【正文】 l path p2 D。2778 2826。3140 3550。3439 3201。3507 2376。4263 2931。3676 2578。4061 2370。3715 1678。2381 1676。2562 1756。4386 570。4196 1044。3326 1556。3712 1399。3639 1315。(7) T 逐漸減少, 且T 趨于0, 然后轉(zhuǎn)第2 步運(yùn)算.模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫(即退火)，如果急速降溫(即淬火)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，粒子在溫度T時(shí)趨于平衡的概率為exp(E/(kT))，其中E為溫度T時(shí)的內(nèi)能，E為其改變量，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)產(chǎn)生“新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子a、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件C. 模擬退火算法的基本思想模擬退火算法可以分解為解空間、：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)s(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L；(2)對(duì)k=1，……，L做第(3)至第6步；(3)產(chǎn)生新解；(4)計(jì)算增量cost=cost()cost(s)，其中cost(s)為評(píng)價(jià)函數(shù)；(5)若t0則接受作為新的當(dāng)前解，否則以概率exp(t/T)接受作為新的當(dāng)前解；(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，；(7)T逐漸減少，且T趨于0，然后轉(zhuǎn)第2步運(yùn)算. 模擬退火算法的關(guān)鍵技術(shù)（1）新解的產(chǎn)生和接受模擬退火算法新解的產(chǎn)生和接受可分為如下4個(gè)步驟：①，減少算法耗時(shí)，常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、因而對(duì)冷卻進(jìn)度表的選取有一定的影響.②，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法.③，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則：若0則接受作為新的當(dāng)前解S，否則以概率exp(/T)接受作為新的當(dāng)前解S.④當(dāng)新解被確定接受時(shí)，同時(shí)修正目標(biāo)函數(shù)值即可.模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性.（2）參數(shù)控制問題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下3點(diǎn)：①，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整.②，一個(gè)常用的函數(shù)為： (1)式中是一個(gè)非常接近于1的常數(shù)，t為降溫的次數(shù).③：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L的選取應(yīng)遵循在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡的原則. Metropolis準(zhǔn)則固體在恒定溫度下達(dá)到熱平衡的過程可以用Morte Carlo算法方法加以模擬，雖然該方法簡單但必須大量采樣得到比較精確的結(jié)果，MetropoliS等在1953年提出了重要的采樣法，作為固體的當(dāng)前狀態(tài)，該狀態(tài)的能量為E，然后用攝動(dòng)裝置使隨機(jī)選取的某個(gè)粒子的位移隨機(jī)地產(chǎn)生一微小變化，得到一個(gè)新的狀態(tài)J，新狀態(tài)的能量是E，如果E則接受新狀態(tài)j為當(dāng)前狀態(tài)：否則，考慮到熱運(yùn)動(dòng)的影響，該新狀態(tài)是否“接受”，物體退火過程的統(tǒng)計(jì)性質(zhì)服從下式所示的正則分布： P{E=E}= (2)式中，exp（）稱為Boltzmann因子，T是絕對(duì)溫度，k是Boltamann常熟，Z(T)為概率分布的標(biāo)準(zhǔn)因子 Z(T)= (3)由式()可知，物體處于狀態(tài)i和狀態(tài)j的幾率的比值等于相應(yīng)的Boltzmann因子的比值，即 r=exp() (4)[0，1]區(qū)間均勻分布的隨機(jī)數(shù)，若r，則接受新狀態(tài)J，反之，則舍棄.如果新狀態(tài)j可以接受，(固體狀態(tài)的變換稱為遷移)后，系統(tǒng)趨于能量較低的平衡狀態(tài).通過對(duì)上述物理現(xiàn)象的模擬，假定L(S，f)存在鄰域以及相應(yīng)解的產(chǎn)生機(jī)制，、分別為對(duì)應(yīng)于解i，： P(t)=P(i)= (5) 合理的停止準(zhǔn)則既要確保算法收斂于某一近似解，的CPU時(shí)間考慮，Nahar等人提出用事先確定好的控制參數(shù)的個(gè)數(shù)，～，也缺乏靈活性.控制模擬退火的漸進(jìn)收斂特性給人們以新的啟示：“充分小”時(shí)，t“充分小”在某種程度上可以替代“最終解質(zhì)量”的判據(jù)，直接構(gòu)成停止準(zhǔn)則的判斷式te：二是由算法進(jìn)程的接受概率隨控制參數(shù)值遞減的性態(tài)，確定一個(gè)終止參數(shù)，若算法進(jìn)程的當(dāng)前接受率，這種方法兼顧了最終解質(zhì)量和CPU時(shí)間兩個(gè)方面對(duì)停止準(zhǔn)則的要求，只要值選取恰當(dāng)，CPU時(shí)間可望縮減而最終解的質(zhì)量仍有保證.常用的選取停止準(zhǔn)則的另一個(gè)途徑是不改進(jìn)規(guī)則控制法，以算法進(jìn)程所得到的某些近似解為衡量標(biāo)準(zhǔn)，判斷算法當(dāng)前解的質(zhì)量是否持續(xù)得到明顯提高，從而確定是否終止算法，在^和等參數(shù)的配合下，不僅可望得到高質(zhì)量的最終解，而且對(duì)于CPU時(shí)間有相對(duì)控制作用(即CPU時(shí)間隨問題規(guī)模的增大而增大)，解質(zhì)相對(duì)穩(wěn)定. 組合優(yōu)化與物理退火的相似性引進(jìn)模擬退火算法(SA)的原動(dòng)力是基于這樣的模擬：.在對(duì)固體物質(zhì)進(jìn)行退火處理時(shí)，通常是先對(duì)它加溫，使其熔化，讓其中的粒子可以自由運(yùn)動(dòng)，然后隨著溫度緩慢下降，則不能達(dá)這個(gè)能量最低態(tài)，這個(gè)過程的本質(zhì)是慢速冷卻，讓粒子有充分的時(shí)間失去可動(dòng)性，進(jìn)行重新分布，這是退火的技術(shù)定義，也有類似的過程，把控制參數(shù)視為溫度，解空間作為狀態(tài)空間，那么模擬退火算法(SA)尋找基態(tài)的過程就是求目標(biāo)函數(shù)極小值的優(yōu)化過程，因此，. 表1 組合優(yōu)化與物理退火的相似性組合優(yōu)化物理退火組合優(yōu)化物理退火解粒子狀態(tài)Metropolis抽樣過程等溫過程最優(yōu)解能量最低態(tài)控制參數(shù)的下降冷卻設(shè)定初始溫度熔解過程目標(biāo)函