模拟退火算法中的退火策略研究
收稿日期:2002-07-10
基金项目:华东船舶工业学院青年基金资助(2002313)
作者简介:高尚(1972-),男,江苏镇江人,硕士,讲师,主要从事系统理论与优化等方面的研究。
文章编号:1671-654×(2002)04-0020-03
模拟退火算法中的退火策略研究
高 尚
(华东船舶工业学院电子与信息系,江苏镇江212003
)
摘 要:退火策略是模拟退火算法中的重要一环,本文将研究退火策略对模拟退火算法的影响问题,给出了MATLAB 语言程序,典型复杂函数优化的仿真表明退火速率应适中。
关键词:模拟退火算法;退火策略;优化;
MATLAB
中图分类号:O224文献标识码:A
引言
模拟退火算法最早思想由Metropolis 在1953年提出,1983年K irkpatrick 等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。目前已在工程中得到了广泛应用
[1～7]
,诸如生产调度、控
制工程、机器学习、神经网络、图像处理等领域。退火策略是模拟退火算法中的重要一环,有关退火策略对模拟退火算法的影响的文献并不多,本文将研究退火策略对模拟退火算法的影响问题。
1 模拟退火算法
模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。算法的基本思想是从一给定解开始的,从邻域中随机产生另一个解,接受准则允许目标函数在有限范围内变坏,它由一控制参数t 决定,其作用类似于物理过程中的温度T ,对于控制参数t 的每一取值,算法持续进行“产生新解-判断-接受或舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热
平衡的过程。经过大量的解变换后,可以求得给定
控制参数t 值时优化问题的相对最优解。然后减小控制参数t 的值,重复执行上述迭代过程。当控制参数逐渐减小并趋于零时,系统亦越来越趋于平衡状态,最后系统状态对应于优化问题的整体最优解。该过程也称冷却过程。由于固体退火必须缓慢降温,才能使固体在每一温度下都达到热平衡,最终趋于平衡状态,因此,控制参数的值须缓慢衰减,才能确保模拟退火算法最终趋于优化问题的整体最优解。
对于一般无约束优化问题:min f (X )
模拟退火算法的一般框架[1～3]:给定起、止“温度”T 、T 0,模拟参数初始化
X 0;
While (T >T 0)do
在X 0的邻域内模拟产生随机扰动△X ;
计算扰动引起的目标函数(能量)值的变化△E ;
若,△E ≤0,接受新值,否则若
exp (△E/T )>rand (0,1)(rand (0,1)表示0～1之间的随机数),也接受新值,否则就拒绝;
确定新的参数值,若扰动被接受,则X 0ωX 0+△X ,否则X 0ωX 0;
若接受新值,降温T ωupdate (T ),否则不降温;
End
其中:T ωupdate (T )就是退火策略,也就是温度下降方法。
2 常见的退火策略
第32卷 第4期 航空计算技术 Vol.32No.4 2002年12月 Aeronautical Computer T echnique Dec.2002
常见的退火策略有下面几种:设t k 为第k 迭代时温度。
对数下降[2]:t k =α/1og (k +k 0)
快速降温[2]:t k =β/(1+k )
直线下降[1]:t k =(1-K
k
)t 0指数退温[1,2]:t k =αt k -1
四种退火方法的温度下降速度是不一样的,指数退温是最常用的一种策略,其温度变化很有规律,直接与参数α相关。这里只研究指数退温策略,以此来总结规律。
由t k =at k -1可知,t k =a k t 0=t 0e ln α-k 因此称为指数退温,设起始温度为T =10000,其温度随着
参数值不同与迭代次数a 的关系如图1所示。
图1 温度随着参数α值不同与迭代次数的关系图
由图1可知:α值越小,退火速度越快,所以我们重点研究不同α值对模拟退火算法的影响。
3 程序设计与测试分析
3.1 程序设计
为了说明问题,以下面4个国内外学者经常采用的优化测试函数[2]来研究。
F 1=100(x 21-x 2)2+(1-x 1)
2
(1)F 2=max (|x 1|-|x 2|)
(2)F 3=sin 2x 21+x 2
2-0.5
[1+0.001(x 21+x 22)]
2-0.5(3)F 4=x 21+x 2
2
(4)
以解F 1为例来说明用MATLAB 语言设计的方法与步骤:
第一步:编写目标函数文件aneal-f1.m function y =aneal-f1(x )
y =1003(x (1)3x (1)-x (2)2+(1-x (1)2;第二步:编写模拟退火算法程序anneal-t1.m (假设起始温度T =10000,终止温度T 0=1,α=0.9)
x1=[11];%参数初始化T =100000;a =0.9;N =1;while T >1
f1=aneal-f1(x1);%计算原来目标函数 x2(1)=x1(1)+0.23(rand -0.5); x2(2)=x1(2)+0.23(rand -0.5); f2=aneal-f1(x2);%计算新的目标函数 if f2-f1<0 T =T 3a ; x1=x2; cc (N )=f2; N =N +1;
elseif exp ((f1-f2)/T )>rand T =T 3a ; x1=x2; cc (N )=f2; N =N +1;
end end
f1=aneal-f1(x1);%计算最终目标函数
disp (′The result are :′)disp (′x (1)X (2)′
)disp (x1)
disp (′The objective function is :′
)disp (f1)
tt =1:N -1;
plot (tt ,cc )%绘画出迭代过程
为测试需要,运行1000次的程序如下:
time1=datestr (now )%初始时间mm =1;
while mm <=1000
anneal-t1%调用程序opf (mm )=f1;
mm =mm +1;
1
22002年12月 高 尚:模拟退火算法中的退火策略研究
end
time2=datestr(now)%运行后时间
min(opf)%最好目标值
max(opf)%最差目标值
mean(opf)%最差目标值
3.2 测试分析
对每个程序运行1000次,对F1函数的模拟参数初始化X0=[0,0],结果如表1,最优解为F1min =F1(1,1)=0;对F2函数的模拟参数初始化X0 =[1,1],结果如表2,最优解为F2min=F2(0,0)= 0;对F3函数的模拟参数初始化X0=[1,1],结果如表3,最优解为F3min=F3(0,0)=-1;对F4函数的模拟参数初始化X0=[1,1],结果如表4,最优解为F4min=F4(0,0)=0。
表1 取不同值时解目标函数的结果
结果 α运行1000次
总的时间(s)
最好
目标值
最差
目标值
平均
目标值
0.95490.00899.8853 1.6919 0.9250.002635.3377 2.1987 0.8120.057257.5572 3.8577 0.780.076560.2747 4.5553 0.650.145676.4038 4.4441
表2 取不同值时解目标函数的结果
结果 α运行1000次
总的时间(s)
最好
目标值
最差
目标值
平均
目标值
0.95600.0626 3.7922 1.4744 0.9210.0931 2.8654 1.3305 0.8110.2778 2.1908 1.2162 0.770.0765 2.1093 1.1913 0.660.3973 1.8274 1.1617
表3 取不同值时解目标函数的结果
结果 α运行1000次
总的时间(s)
最好
目标值
最差
目标值
平均
目标值
0.9552-0.9903-0.0025-0.3595 0.926-0.9885-0.0025-0.2578 0.812-0.9397-0.0025-0.1621 0.78-0.9067-0.0025-0.1078 0.66-0.8782-0.0025-0.0880
表4 取不同值时解目标函数的结果
结果 α运行1000次
总的时间(s)
最好
目标值
最差
目标值
平均
目标值
0.95480.005719.7519 3.0901 0.9210.004315.1206 2.6141 0.8100.04857.0043
2.2828
0.770.1019 6.1188 2.1953
0.650.2034 4.9562 2.1665
从表1～4可知,α值越小,退火速度越快,迭代次数减少,运行时间短;对于最好目标值这一指标来说,α应取大点;对于最差目标值和平均目标值这两个指标来说,α取值不具有一致性结论,对于目标函数,α应取大点,而对于目标函数F1,α应取小点。综合几个指标,建议α取适中。对于其他退火函数,采取的策略应该使退火速率适中。图2显示了α= 0.9对F1函数,用模拟退火算法的运行的某一次的迭代过程。
图2 对函数模拟退火算法的一次的迭代过程
4 结束语
通过对测试函数的具体运行结果分析了退火策略对模拟退火的影响,其理论分析有待进一步研究。模拟退火算法是依赖邻域结构的迭代方法,模拟退火算法对选择试验解比较敏感[6,7],对如何选择初值,如何找邻解,如何设置初温等参数设计还有待研究。
参考文献:
[1] 邢文循,谢金星.现代优化计算方法[M].北京:清华大
学出版社,1999:90-129.
[2] 王凌.智能优化算法及其应用[M].北京:清华大学出
版社,2001(10):17-35.
[3] 刘宝碇,赵瑞清.随机规划与模糊规划[M].北京:清华
大学出版社,1998:45-50.
[4] 张德富,顾卫刚,沈平.一种解旅行商问题的并行模拟
退火算法[J].计算机研究与发展,1995(2).
[5] 田湃,杨自厚,张嗣瀛.一类非线性规划的模拟退火求
解[J].控制与决策,1994,9(3):173-177.
[6] K irkpatrick S,G elatt J r C D,Vecchi J r M P.Optimization
by simulated annealing[J].Science,1983.
[7] A.Bolte,U.W.Thonemann,Optimisation simulated an2
nealing schedules with genetic programming[J].Eu-ro2
pean Journal of Operational Research92(1996):402-
416. (下转第26页)
方程,其中的四面体网格生成和自适应网格的细化均用Delaunay三角剖分技术实现。计算实践表明,非结构网格的自适应技术可以用相对较少的网格计算出较精确的结果,使计算效率得到明显的提高。
参考文献:
[1] Jameson A.,Baker T.J.and Weatherhill N.P..Calcula2
tion of Inviscid Transonic Flow over a Complete Aircraft
[J].AIAA Paper86-0103,1986.
[2] Loehner R..FEM in CFD:Grid G eneration,Adaptivity
and Parallelization[J].N92-27679,1992.
[3] Owen S J.A Survey of Unstructured Mesh G eneration
Technology.steve.owen@https://www.wendangku.net/doc/9a13013478.html,.
[4] 朱培烨.空间曲面的非结构网格生成[J].航空学报,
2001,22(2):151-154.
[5] 朱培烨.三维非结构网格自动生成[J].计算物理,
2001,18(6):573-576.
Three2Dimensional Adaptive U nstructured Mesh for Euler Equ ations
ZHU Pei2ye
(A eronautical Com puti ng Technique Research Instit ute,Xi′an710068,Chi na)
Abstract:The three2dimensional Euler are solved on unstructured tetrahedral mesh2 es using an adaptive strategy.The basic algorithm for the Euler solver consists of an explicit ver2 tex2based finite volume method.The Delaunay triangulation is used both to generate the meshes and to refine the meshes.The transonic flow over the ON ERA M6wing is calculated by means of the adaptive strategy,and the results are compared with experimental data to show the accuracy and efficiency of the present method.
K ey w ords:adaptive mesh technique;Euler equations;unstructured mesh
(上接第22页)
R esearch on annealing strategy in Simulated Annealing Algorithm
G AO Shang
(East Chi na S hi pbuil di ng Instit ute,Zhenjiang212003,Chi na)
Abstract:The annealing strategy is an important step in simulated annealing algorithm.The effect of annealing strategy in simulated annealing algorithm is researched in this paper.MA TLAB programs of simulated annealing algorithm are given.Simulation results of typical complex func2 tion optimization show that the speed of annealing must be moderate.
K ey w ords:simulated annealing algorithm;annealing strategy;optimization;MA TLAB