确定性退火技术

*******TP301DeterministicAnnealingYangGuangwen*LiXiaoming**WangYihe***ZhengWeiminWangDingxing*(*DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)**DepartmentofComputerScience,PekingUniversity,Beijing100871(***DepartmentofComputerScience,HarbinInstituteofTechnology,Harbin150006)AbstractAccordingtoannealingprocessinstatisticalphysics,theauthorgoesafurtherstepanddiscussesthedeterministicannealing.Adetaileddescriptionisgivenofthebackgroundofdeterministicannealingforthefirsttime.Deterministicannealingsimulatestheequilibriumstatebyuseoftraditionaloptimizationmethodstofindtheminimumvalueoffreeenergyfunctionbyselectingaspecialinitialpoint.Intheory,itprovessuccessfulthatwhenfreeenergyfunctionsatisfiescertainappropriateconditions,theglobaloptimalsolutionisacontinuousmaptotemperaturewhichprovidesreliablescientificbasisfordeterministicannealing.KeyWord:DeterministicAnnealing,EquilibriumState,FreeEnergy[1]K.RoseminE=E(x)(2.1)E(x)(2.1)F(x,T)F(x,T):T=∞F(x,T)xT=0,F(x,T)=E(x)TTT=+ΔxTTmin()+ΔminF(x,T)lim()minTxT→0minE(x):2.1F(x,T),(1)T0F(x,T0)k=0,:minF(x,Tk)xTkmin()(2)Tk+1=cTk(0c1),xTkmin(),min(F(x,Tk+1))xTkmin()+1(3).,,xTkmin()+1;,(4)(4)k=k+1,(2)2.13min(,)..FxTstxD∈,DEn⊂,,j:[,)01+∞→E,j()min{(.),}TFxTxD=∈y[,)02+∞→X,yj(){|,(,)()}TxxDFxTT=∈=j()T,y()Ty:EX12→.yT0ΩΩ⊂≠∅XT,()Iy0,dd=(),Ω0yd()(()TTNTIΩ≠∅∀∈0DF(x,T)DT×{}0yT0y()T0≠∅jT0{}TkTk∈+∞[,)0TTk→0xT00∈y()yT0Ω,y()T0IΩ≠∅,dd=()Ω0,y()TIΩ≠∅(())∀∈TNTd0MmM≥xTTmm()()∈ylim()mmxTx→∞=0lim()lim((),)(,)()mmmmmTFxTTFxTT→∞→∞===jj000jT0y()TTminF(x,T)Tx(T)minF(x,T)F(x,T)D×+∞[,)0DEnT∈+∞[,)0,F(x,T)y(){()}TxT=x(T)j()T[,)0+∞x(T)[,)0+∞x(TTTTm000∈+∞→[,),xTm()xT()0TmT0minF(x,T)xTxTm()()→0TmxTxxTm()()→≠0Dx.Dj110:[,]TTD→,j1()Tj100()()TxT=,j111()()TxT=,lim()()kkTxT→∞=j10.D,j1010100()(()())()TTTTTxTxTxT=---+,((),),((),)xTTxTT1100lim()()kkTxT→∞=j10.DxD∈xxT≠()0F(x,T)FxTTFxT((),)(,)000(3.1)j1(),()TDxTkk∈FxTk(,)FxTTFTTkkkk((),)((),)≤j1k→∞j1F(x,T)FxTFxTT(,)((),)000≤,3.1xxT=()0lim()()mmxTxT→∞→0,xT()Tj()T[,)0+∞y()T[,)0+∞T00∈+∞[,)y(){()}TxT00=ΩΩIy()T0≠∅ΩxT()0e0||()||xxT-0ex∈ΩxNxT∈e(())0),x(T)d0,||TT-0d||()()||xTxT-0exT()∈ΩΩΩIy()T0≠∅dd=(),Ω0yd()(()TTNTIΩ≠∅∀∈0y()T[,)0+∞T00∈+∞[,)j()TT0j()T[,)0+∞Mitroplis[1].G.C.Fox,Physicalcomputation,Concurrency:PracticeandExperince,Vol3(6),p.627-653(1991).[2].K.Rose,E.Gurewitz,G.C,Fox,Statisticalmechanicsandphasetransitionsinclustering,PhysicalReviewLetters,65:945-948,(1990).