模擬退火算法課件

SimulatedAnnealing

（模擬退火算法）模擬退火算法的思想最早是由Metropo比等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于MenteCalro迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解．即在局部?jī)?yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，目前己在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、圖像處理等領(lǐng)域。

退火工藝:退火是將金屬和合金加熱到適當(dāng)溫度，保持一定時(shí)間，然后緩慢冷卻的熱處理工藝。退火后組織亞共析鋼是鐵素體加片狀珠光體；共析鋼或過(guò)共析鋼則是粒狀珠光體。總之退火組織是接近平衡狀態(tài)的組織。退火的目的:①降低鋼的硬度，提高塑性，以利于切削加工及冷變形加工。②細(xì)化晶粒，消除因鑄、鍛、焊引起的組織缺陷，均勻鋼的組織和成分，改善鋼的性能或?yàn)橐院蟮臒崽幚碜鹘M織準(zhǔn)備。③消除鋼中的內(nèi)應(yīng)力，以防止變形和開(kāi)裂SimulatedAnnealing相似性：金屬問(wèn)題能量狀態(tài)成本函數(shù)溫度控制參數(shù)完整排列的晶體結(jié)構(gòu)問(wèn)題的最優(yōu)解Globaloptimalsolutioncanbeachievedaslongasthecoolingprocessisslowenough.Optimization,steepestdescentandlocalminimaf(x)GlobalminimumLocalminimumLocalminimumLocalminimum要從局部最優(yōu)逃出，必須上行（up-step）SA的上行機(jī)制：△＝（當(dāng)前解）—（下一個(gè)解）T為溫度，即SA的控制參數(shù)SA接受相鄰解的標(biāo)準(zhǔn)令X為當(dāng)前解X’新的解（相鄰解）C(x)(C(x’))betheenergystate(cost)ofx(x’)概率Paccept=exp[(C(x)-C(x’))/T]N=Random(0,1)無(wú)條件接受相鄰解，如果：C(x’)<C(x),即相鄰解比當(dāng)前解好以一定的概率接受相鄰解，如果C(x’)>=C(x),即相鄰解比當(dāng)前解差當(dāng)N<Paccept時(shí)，接受相鄰解參數(shù)設(shè)置T初始溫度t冷卻溫度冷卻過(guò)程的設(shè)定（Thecoolingschedule）L每一特定溫度下的搜索次數(shù)：退火過(guò)程設(shè)定CoolingSchedule:N溫度T的主要作用：決定接受差的解的概率初始溫度的設(shè)定：由可忍受的解差的程度和接受的概率決定，比如以0.8的概率接受比當(dāng)前解值大100，初始溫度應(yīng)為多少？一般溫度設(shè)定為500——1000較為合適。需要運(yùn)行程序多試。退火過(guò)程設(shè)定N溫度T的降低過(guò)程： 每次減少固定的值：T’=T-Td

每次按固定比例減少：T’=T*r，此方法比較常用每個(gè)特定溫度下的搜索次數(shù)L：根據(jù)計(jì)算耗時(shí)來(lái)確定。搜索的收斂：溫度降低到設(shè)定的最低溫度，如0.5度。AlgorithmInitializeinitialsolutionx,highesttemperatureTh,andcoolesttemperaturetT=ThWhenthetemperatureishigherthant

Whilenotinequilibrium SearchforthenewsolutionX’AcceptorrejectX’accordingtoMetropolisCriterionEndDecreasethetemperatureTEndT=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否ExampleTravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity12345611247910211201383617134695156SAparametersettingTh=2000t=10r=0.6N=2生成新的解：隨機(jī)選擇兩個(gè)位置，交換其表示的城市T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解溫度T＝2000n=0SequenceThelengthoftheroute12345630新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute13245628當(dāng)前解SequenceThelengthoftheroute12345630新的解Exp((新的解－當(dāng)前解)/T)=exp(-2/2000)Random[0,1]=0.7T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628當(dāng)前解溫度T＝2000n=1T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute12345630當(dāng)前解SequenceThelengthoftheroute12354636新的解Exp((新的解－當(dāng)前解)/T)=exp(-5/2000)Random[0,1]=0.99，拒絕新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute12345630當(dāng)前解SequenceThelengthoftheroute12346531新的解Exp((新的解－當(dāng)前解)/T)=exp(-1/2000)Random[0,1]=0.6T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628當(dāng)前解溫度T＝1200n=2T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute12345630當(dāng)前解SequenceThelengthoftheroute21345627新的解接受新的解溫度T＝1200n=0T=Th求得初始解BS=初始解n=0求得新的解新的解比當(dāng)前解好？接受新的解用新的解替換當(dāng)前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:溫度Th:最高溫度t:最低溫度BS：已經(jīng)找到的最好解N:某一溫度下達(dá)到平衡的搜索次數(shù)是否是否是否是否是否SequenceThelengthoftheroute21345627BSSequenceThelengthoftheroute21345627當(dāng)前解溫度T＝1200n=1ExampleSolutionrepresentationAnintegerlist,i.e.,(1,4,2,3,6,5)SearchmechanismSwapanytwointegers(exceptforthefirstone)(1,4,2,3,6,5)(1,4,3,2,6,5)CostfunctionExampleStepn:visitingsequence(1,4,2,3,6,5)->cost=189Generateneighbor:obtainsequence(1,2,4,3,6,5)->cost=180Replacecurrentsequenceby(1,2,4,3,6,5)Stepn+1:visitingsequence(1,2,4,3,6,5)->cost=180Generateneighbor:obtainsequence(1,2,4,3,5,6)->cost=190Temperature=99Probability:exp((180-181)/99)=0.904Random()=0.6->acceptneighborReplacecurrentsequenceby(1,2,4,3,5,6)…Stepn+F:Temperature=Temperature*0.9ControlParametersDefinitionofequilibriumCannotyieldanysignificantimprovementaftercertainnumberofloopsAconstantnumberofloopsAnnealingschedule(i.e.Howtoreducethetemperature)Aconstantvalue,T’=T-TdAconstantscalefactor,T’=T*RdAscalefactorusuallycanachiev