一种改进的快速模拟退火组合优化法
王卓鹏 高国成 杨卫平
摘要
基于对求解全局优化问题的确定性方法和模拟退火算法的分析，文中提出了一种改进的快速模拟退火算法.实验结果表明，该算法可以显著地提高求解全局优化问题的计算效率.
关键词 快速模拟退火 全局优化 随机搜索
An Improved Fast Simulated Annealing Combinatorial Optimization
Wang Zhuopeng1 Gao Guocheng2 Yang Weiping1
1(Department
of Electrical Engineering, Shandong Min. Inst., Ji'nan 250031)
2(Department
of Elementary Education, Shangdong Min. Inst., Ji'nan 250031)
Abstract This paper presents an
improved fast simulated annealing algorithm based on the analysis on deterministic method
and simulated annealing algorithm for solving global optimization problems. The
experimental results indicate that the algorithm can significantly improve the
computational efficiency of solving global optimization problems.
Keywords fast simulated
annealing; global optimization; random search
1 引言
许多实际优化问题的目标函数都是非凸的，存在许多局部最优解，
特别是随着优化问题规模的增大，局部最优解的数目将会迅速增加.因此，有效地求出一般非凸目标函数的全局最优解至今仍是一个难题.
求解全局优化问题的方法可分为两类，一类是确定性方法，另一类是随机性方法.确定性算法一般适用于求解满足特定要求的一些特殊向题.而梯度法和一般的随机搜索方法则沿着目标函数下降方向搜索，因此常常陷入局部而非全局最优值.
模拟退火算法是1983年由Kirkpatrick
S.等人首次提出并已被成功地用于求解TST、VLSI电路设计和计算机设计等大规模组合优化问题的随机性方法.它在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理.它在迭代过程中不仅接受使目标函数值变“好”的点，
而且还能够以一定的概率接受使目标函数值变“差”的点，接受概率随着温度的下降逐渐减小.模拟退火算法的这种搜索策略有利于避免搜索过程陷入局部最优解，有利于提高求得全局最优解的可靠性.
本文讨论求解如下优化问题
式中，Ω={(x1, x2,…, xn)|ai＜xi＜bi, i=1,2,…,n},函数f有界，不要求连续.
本文基于对快速模拟退火算法的分析，通过大量实验测试，确定了有利于达到最优解的关键退火参数.利用确定性算法收敛快的特点研究两者的有机结合，给出了一种高效的改进快速模拟退火算法.
2 快速模拟退火算法(FSA)
步骤1 确定初始值
给定初始解X0∈Ω和初始温度T0＞0，基本步长V0，设定检验精度ε，检验Metropolis抽样稳定性的阈值NT，与结束退火有关的阈值I.计算f(X0)，令Xopt=X0, fopt=f(X0)，置i=0，k=0, m=0, ik=0.
步骤2 新态试探点生成
Yi=Xi+ηγV0s
若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)＜fopt，则令Xopt=Xi+1, fopt=f(Xi+1), m=0， 否则令m=m+1.
步骤5 Metropolis 抽样稳定性判别
若m＜NT，则令i=i+1, 转步骤2； 否则令m=0.
步骤6 退火结束判别
若fopt＞Tk，则令ik=ik+1,否则令ik=0；
若ik≥I或fopt＜ε，则算法结束.否则，即ik＜I且fopt≥s时，继续步骤7.
步骤7 退火方案
若fopt大于某一给定值fopt，则按Tk+1=T0/(1+delta*func-call)退火，否则，按Tk+1=rT.Tk退火.置k=k+1,转步骤2.
式中,func-call为模拟退火算法中目标函数调用次数，0＜rT＜1.
