中國(guó)數(shù)學(xué)建模-編程交流-模擬退火算法

1、中國(guó)數(shù)學(xué)建模編程交流模擬退火算法.txt鮮花往往不屬于賞花的人，而屬于牛糞。。。道德常常能彌補(bǔ)智慧的缺陷，然而智慧卻永遠(yuǎn)填補(bǔ)不了道德空白人生有三樣?xùn)|西無(wú)法掩蓋：咳嗽貧窮和愛，越隱瞞，就越欲蓋彌彰。中國(guó)數(shù)學(xué)建模編程交流模擬退火算法模擬退火算法模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小

2、。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為eΔE(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種

3、啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。3.5.1模擬退火算法的模型模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火的基本思想:(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L(2)對(duì)k=1，……，L做第(3)至第6步：(3)產(chǎn)生新解S′(4)計(jì)算增量Δt′=C(S′)

4、C(S)，其中C(S)為評(píng)價(jià)函數(shù)(5)若Δt′0，然后轉(zhuǎn)第2步。算法對(duì)應(yīng)動(dòng)態(tài)演示圖：模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)

5、函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則:若Δt′Romof[01])S=S′IFthehaltconditionisTRUETHENtermination=trueEndT_lowerEndEnd模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問(wèn)題

6、(MaxCutProblem)、01背包問(wèn)題(ZeroOneKnapsackProblem)、圖著色問(wèn)題(GraphColouringProblem)、調(diào)度問(wèn)題(SchedulingProblem)等等。模擬退火算法的參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下三點(diǎn)：(1)溫度T的初始值設(shè)置問(wèn)題。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)

7、解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。(2)退火速度問(wèn)題。模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來(lái)說(shuō)，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對(duì)具體問(wèn)題的性質(zhì)和特征設(shè)置合理的退火平衡條件。(3)溫度管理問(wèn)題。溫度管理問(wèn)題也是模擬退火算法難以處理的問(wèn)題之一。實(shí)際應(yīng)用中，由