模拟退火算法机理研究

模拟退火算法机理研究

第32卷第6期2004年6月

同济大学学报(自然科学版)

JOURNALOFTONGJIUNIVERSITY(NATURALSCIENCE)Vol.32No.6

　Jun.2004

模拟退火算法机理研究

陈华根,吴健生,王家林,陈　冰

(同济大学海洋地质教育部重点实验室,上海　200092)

摘要:从机理上分析了采用Metropolis,,避免了落入局部极小点的可能,,深入分析了算法的退火计划和模型扰动,,;并提出了改进的思路,为下一关键词:模拟退火算法;效率;最优;退火计划

中图分类号:TP301.6　　　　　　文献标识码:A　　　　　　　文章编号:0253-374X(2004)06-0802-04

MechanismStudyofSimulatedAnnealingAlgorithm

CHENHua2gen,WUJian2sheng,WANGJia2lin,CHENBing

(KeyLaboratoryofMarineGeology,TongjiUniversity,Shanghai200092,China)

Abstract:AftertheimportanceofacceptanceofMetropolisruleinsimulatedannealing(SA)algorithmisanalyzed,itisconsideredthatthisrulecanmakethemodeljumpingoutoflocallowpointandthenwefindtheoptimizationwiththecontrolofannealingscheme.Sowithadeepanalysisofannealingscheme,modelvibrationandthecooperationskillsbetweenthem,theimprovementaboutthisalgorithmisconsideredpossibleandthedetailedideaisputforwardforhighefficiencyasagoodfoundationforimprovement.

Keywords:simulatedannealingalgorithm;efficiency;optimization;annealingscheme

　　模拟退火算法(simulatedannealing,SA)作为局部搜索算法的扩展,在每一次修改模型的过程中,随机产生一个新的状态模型,然后以一定的概率选择邻域中能量值大的状态.这种接受新模型的方式使其成为一种全局最优算法,并得到理论证明和实际应用的验证.

SA虽然在寻优能力上不容置疑,但它是以严密

提出了非常快速模拟退火计划及相应的算法(very

fastsimulatedannealing,VFSA)[1],使得算法效率有所提高,并且已应用在一些实际研究中.但是,在实际应用中效率还是偏低,并且与约束条件的个数和模型的扰动范围密切相关,因此仍然阻碍着算法在更多领域中的实际应用.解决这个问题的要点有3个:①尽可能多地获得与算法有关的已知信息以增加约束条件的个数;②减小模型的扰动范围;③进一步改进算法,提高效率.从这3个要点看,①和②都是客观的,均与已知条件相关,如要进一步获得更多信息需要大量的投入或者查阅多方面资料;而对

的退火计划为保证的,

具体地讲,就是足够高的初始温度、缓慢的退火速度、大量的迭代次数及同一温度下足够的扰动次数.因此,SA的效率问题一直是算法真正走向实用的主要障碍.Ingber针对这一问题,

收稿日期:2003-05-19

基金项目:中国岩石圈结构数据库资助项目(200010101-10);同济大学理科基金资助项目作者简介:陈华根(1968-),男,浙江嵊州人,讲师,工学博士.E2mail:huagen-chen@sina.com

第1页下一页