模擬退火算法原理及matlab源代碼

1、模擬退火算法模擬退火算法是一種通用的隨機(jī)搜索算法，是局部搜索算法的擴(kuò)展。它的思想是再1953年由metropolis提出來的，到1983年由kirkpatrick等人成功地應(yīng)用在組合優(yōu)化問題中。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)

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

3、olingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：第一步是由一個(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)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。第二步

4、是計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則:若Δt′0則接受S′作為新的當(dāng)前解S，否則以概率exp(Δt′T)接受S′作為新的當(dāng)前解S。errHold=InfxHold=0%x1=[7513]i=0whilei200i=i1j=0

5、T=T50%退火whilej200j=j1functionErr1=nonLinearSumErr1(x1)%計(jì)算x1的誤差x2=newSolver1(x1functionErr110110)%在x1的鄰域生成新一組解x2functionErr2=nonLinearSumErr1(x2)%計(jì)算x2的誤差%檢查方程是否得解[solution1minErr1isTrue1]=isSolution(x1functionErr1precisio