一种改进的快速模拟退火组合优化法.pdf

《一种改进的快速模拟退火组合优化法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1999年2月系统工程理论与实践第2期　a一种改进的快速模拟退火组合优化法121王卓鹏　高国成　杨卫平1(山东矿业学院电气工程系,山东济南250031)2(山东矿业学院基础部,山东济南250031)摘要　基于对求解全局优化问题的确定性方法和模拟退火算法的分析,文中提出了一种改进的快速模拟退火算法.实验结果表明,该算法可以显著地提高求解全局优化问题的计算效率.关键词　快速模拟退火　全局优化　随机搜索AnImprovedFastSimulatedAnnealingCombinatorialOptimization121WangZhuopengGaoGuochengYangWeiping

2、1(DepartmentofElectricalEngineering,ShandongMin.Inst.,Ji'nan250031)2(DepartmentofElementaryEducation,ShangdongMin.Inst.,Ji'nan250031)AbstractThispaperpresentsanimprovedfastsimulatedannealingalgorithmbasedontheanalysisondeterministicmethodandsimulatedannealingalgorithmforsolvingglobaloptimizati

3、onproblems.Theexperimentalresultsindicatethatthealgorithmcansignificantlyimprovethecomputationalefficiencyofsolvingglobaloptimizationprob2lems.Keywordsfastsimulatedannealing;globaloptimization;randomsearch1　引言许多实际优化问题的目标函数都是非凸的,存在许多局部最优解,特别是随着优化问题规模的增大,局部最优解的数目将会迅速增加.因此,有效地求出一般非凸目标函数的全局最优解至今仍是

4、一个难题.求解全局优化问题的方法可分为两类,一类是确定性方法,另一类是随机性方法.确定性算法一般适用于求解满足特定要求的一些特殊向题.而梯度法和一般的随机搜索方法则沿着目标函数下降方向搜索,因此常常陷入局部而非全局最优值.模拟退火算法是1983年由KirkpatrickS.等人首次提出并已被成功地用于求解TST、VLSI电路设计和计算机设计等大规模组合优化问题的随机性方法.它在搜索策略上与传统的随机搜索方法不同,它不仅引入了适当的随机因素,而且还引入了物理系统退火过程的自然机理.它在迭代过程中不仅接受使目标函数值变“好”的点,而且还能够以一定的概率接受使目标函数值变“差”的点,接受

5、概率随着温度的下降逐渐减小.模拟退火算法的这种搜索策略有利于避免搜索过程陷入局部最优解,有利于提高求得全局最优解的可靠性.本文讨论求解如下优化问题minf(X)nX∈8

6、定性算法收敛快的特点研究两者的有机结合,给出了一种高效的改进快速模拟退火算法.2　快速模拟退火算法(FSA)步骤1　确定初始值给定初始解X0∈8和初始温度T0>0,基本步长V0,设定检验精度E,检验Metropolis抽样稳定性的阈值NT,与结束退火有关的阈值I.计算f(X0),令Xopt=X0,fopt=f(X0),置i=0,k=0,m=0,ik=0.步骤2　新态试探点生成Yi=Xi+GCV0式中,G为控制扰动大小的比例常数,C为随机扰动,服从Cauchy分布.V0为与初值及取值范围有关的步长值.计算f(Yi).步骤3　新态生成　　若f(Yi)≤f(Xi),则令Xi+1=Yi,f

7、(Xi+1)=f(Yi)f(Xi)-f(Yi)　　若f(Yi)>f(Xi),则计算P=exp,Tk　　若PP≤P,则令Xi+1=Yi,f(Xi+1)=f(Yi),否则令Xi+1=Xi,f(Xi+1)=f(Xi).式中PP为[0,1]间的均匀分布.步骤4　最优解更新　　若f(Xi+1)