搜索
a(,100080),,,,AnEfficientSimulatedAnnealingAlgorithmforGlobalOptimizationYangRuoliGuJifa(InstituteofSystemsScience,ChineseAcademyofSciences,Beijing100080)AbstractAheuristiccriterionfordeterminingthetemperatureupdatingfunctionofsimulatedannealingalgorithmisproposedinthispaper.Anappropriateformofproba2bilitydensityfunctionforgeneratingtherandomvectorsisconstructed.Thetempera2tureupdatingfunctioncorrespondingtotheprobabilitydensityfunctionisderivedbyusingtheproposedheuristiccriterion.Thenewtemperatureupdatingfunctionderivedisinverselyproportionaltoapowerfunctionoftheannealingtimeandisindependentofthedimensionoftheoptimizationproblems.Thenumericalcomputationresultsindicatethatthesimulatedannealingalgorithmwiththenewtemperatureupdatngfunctionandthecorrespondingprobabilitydensityfunctioncanimprovesignificantlythecomputa2tionalefficiencyforsolvingtheglobaloptimizationproblems.Keywordssimulatedannealing;globaloptimization;randomsearch1,,,,,[1],,,,,,,,[2,3]80199755a19961014(N.69474033),Metropolis[4],TSPVLSINP2[5,6],[79],,,,,,,,minxRnf(x)(1)f:RnR,(1)[10,11],,[12-13],,,[14][14],1ön,1ön,n1ön,n,[15],1önqön,q1,q=n,,,1önm,mE1,,2(1):Step1x0RnT00,,B0f(x0),X0=x0,Xmin=x0,fmin=f(x0),k=0Step2Zk,XkZkYk,Yk=Xk+Zk(2)f(Yk)Step3(0,1)G,XkTkYk(Pa(YkûXk,Tk),Pa(YkûXk,Tk)=min1,expf(Xk)-f(Yk)BTk,(3)GFPa(YkûXk,Tk),Xk+1=Yk,f(Xk+1)=f(Yk);Xk+1=Xk,f(Xk+1)=f(Xk)Step4f(Xk+1)fmin,Xmin=Xk+1,fmin=f(Xk+1)0319975Step5,,Xmin,fmin;Step6Step6Tk+1,k=k+1,Step2,B,,,,,,3,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:ARnk00,kEk0A4,:g1(vûT)=T1öm2m(ûvû+T)(m+1)öm,vR(4)T0,mE1kZk,(4),,TkZkP1(ûTk):p1(zkûTk)=7ni=1g1(zkiûTk)(5)zk=(zk1,zk2,,xkn)Zk:Zki=sign(Ui)Tk1ûUiûm-1,i=1,2,,n(6)135ZkiZki,U1,U2,,Un[-1,1],sign()Zk,Zk,:g2(vûT)=T1ömm(v+T)(m+1)ömvE000(7)vR,T0,mE1Vk1,Vk2,,Vkng2(ûTk),W1,W2,,Wn[-1,1],Vk1,Vk2,,Vkn,W1,W2,,Wn,kZk:Zki=WiVki6Nj=1W2j,i=1,2,,n(8)ZkiZkii{1,2,,n},Zki0,,,ZkTkp2(ûTk)p2(zkûTk)=12n101n7ni=1g2ûzkiûsi6nj=1s2jTk1si6nj=1s2jds1dsn,zki0,i=1,2,,n(9)zk=(zk1,zk2,,zkn)g2(ûTk)Vki:Vki=Tk1Umi-1,i=1,2,,n(10)U1,U2,,Un[0,1],,(8)Zk:Zki=WiTk6Nj=1W2j1Umi-1,i=1,2,,n(11),,5(5)1(5),,,Tk=T0km,k=1,2,(12)T00,mE1(4)g1(ûTk)m,ARnk00,kEk0ZkAA0,A={zRnziûFA,i=1,2,,n}kTk,(5)ZkAP(ZkA)=A-AA-A7ni=1(Tk)1öm2m(ûzkiû+Tk)(m+1)ömdzk1dzkn=7ni=1A0(Tk)1ömm(zki+Tk)(m+1)ömdzkiFA0(Tk)1ömm(F+Tk)(m+1)ömdF2319975=1-TkA+Tk1ömF1-TkA+T01ömk00,kEk0ZkA7k=k0P(ZkA)F7k=k01-TkA+T01öm=expln7k=k01-TkA+T01öm=exp6k=k0ln1-TkA+T01ömln(1-y)F-y,0Fy1,(12),7k=k0P(ZkA)Fexp-6k=k0TkA+T01öm=exp-6k=k0T0A+T01öm1k=exp-T0A+T01öm6k=k01k=0,,(12)(9)Tk=AkTk-1,0Ak1,kE1,,,Ak,,,Ak,,Tk,Ak11T1=T0,Tk=k-1kmTk-1,kE2,A1=1,Ak=k-1km,kE2,kE2,()k,Ak,k,Ak1,m,Ak1,,1,m,16:minxf(x)s.t.aiFxiFbi,i=1,2,,n(13)x=(x1,x2,,xn),aibixi,Step2,,;,,kYdk,,Yk:335Yki=bi-(Ydk-bi)MOD(bi-ai)ifYdkibiYdki,ifaiFYdkiFbiai+(ai-Ydki)MOD(bi-ai),ifYdkiai(14)YdkiYkiYdkYki,(a)MOD(b)aöb,,,7:minxf(x)=11006100i=1(x4i-16x2i+5xi)s.t.-10FxiF10,i=1,2,,1002100,-7813323,T0=107,m=3,B=1,x0i=10,1FiF100,ûfmin-f3û10-3,f3=-78.3323,(8),(14),[14],1ön,[15]Tk=T0exp(-ck),k=1,2,(15)T00,c0,c=0.01,1[14],10,101[14]199802366427599[14]3427438197418531,[14],,,8,,m,mE1,1ön,,43199751TobrnAandZilinskasA.GlobalOptimization,Springer2Verlag,1989.2KirkpatrickSGelatt,CDJrandVecchiMP.OptimizationbySimulatedAnnealing.Science1983,(220):671-680.3CernyV.ThermodynamicalApproachtotheTravellingSalesmanProblem:AnEfficientSimulationAl2gorithm,JournalofOptimizationTheoryandApplications,1985,(45):41-45.4MetropolisN,RosenbluthAW,RosenbluthMN,TellerAHandTeller,E.EquationsofStateCal2culationbyFastComputingMachines.TheJournalofChemicalPhysics,1953,(21):1087-1092.5LaarhovenPJMvanandAartsEHL.SimulatedAnnealing:TheoryandApplications,DReidelPublishingCompany,Dordrecht,1987.6AartsEHLandKorstJHM.SimulatedAnnealingandBoltsmannMachines:AStochasticApproachtoCombinatorialOptimizationandNeuralComputing,Wiley,Chichester,1989.7VanderbiltDandLouieSG.AMonteCarloSimulatedAnnealingApproachtoOptimizationoverCon2tinuousVariables.JournalofComputationalPhysics,1984,(56):259-271.8BohachevskyIO,JohnsonMEandSteinML.GeneralizedSimulatedAnnealingforFunctionOpti2mization.Technometrics,1986,(28):209-217.9CoranaA,MarchesiMMartiniCandRidellaS.MinimizingMultimodalFunctionsforContinuousVariableswiththeSimulatedAnnealingAlgorithm.ACMTransactionsonMathematicalSoftware,1987,(13):262-280.10BlisleCJP.ConvergenceTheoremsforaClassofSimulatedAnnealingAlgorithmsonRd,JournalofAppliedProbability,1992,(29):885-895.11RomeijnHEandSmithRL.SimulatedAnnealingforConstrainedGlobalOptimization.JournalofGlobalOptimization,1994,(5):101-124.12SzuHH.Non2ConvexOptimization,Proc.SPIE,1986,(698):59-65.13Szu,HHandHartleyPL.FastSimulatedAnnealing.PhysicsLetterA,1987,(122):157-162.14Ingber,L.VeryFastSimulatedReannealing.MathematicalandComputerModelling1989,(12):967-973.15IngberL.SimulatedAnnealing:PracticeversusTheory.MathematicalandComputerModelling,1993,(18):29-57.535