文档介绍：收稿日期:2002-07-10基金项目:华东船舶工业学院青年基金资助(2002313)作者简介:高尚(1972-),男,江苏镇江人,硕士,讲师,主要从事系统理论与优化等方面的研究。文章编号:1671-654@(2002)04-0020-03模拟退火算法中的退火策略研究高尚(华东船舶工业学院电子与信息系,江苏镇江212003)摘要:退火策略是模拟退火算法中的重要一环,本文将研究退火策略对模拟退火算法的影响问题,给出了MATLAB语言程序,典型复杂函数优化的仿真表明退火速率应适中。关键词:模拟退火算法;退火策略;优化;MATLAB中图分类号:O224文献标识码:A引言模拟退火算法最早思想由Metropolis在1953年提出,1983年Kirkpatrick等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。目前已在工程中得到了广泛应用[1~7],诸如生产调度、控制工程、机器学****神经网络、图像处理等领域。退火策略是模拟退火算法中的重要一环,有关退火策略对模拟退火算法的影响的文献并不多,本文将研究退火策略对模拟退火算法的影响问题。1模拟退火算法模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。算法的基本思想是从一给定解开始的,从邻域中随机产生另一个解,接受准则允许目标函数在有限范围内变坏,它由一控制参数t决定,其作用类似于物理过程中的温度T,对于控制参数t的每一取值,算法持续进行/产生新解-判断-接受或舍弃0的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后,可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值,重复执行上述迭代过程。当控制参数逐渐减小并趋于零时,系统亦越来越趋于平衡状态,最后系统状态对应于优化问题的整体最优解。该过程也称冷却过程。由于固体退火必须缓慢降温,才能使固体在每一温度下都达到热平衡,最终趋于平衡状态,因此,控制参数的值须缓慢衰减,才能确保模拟退火算法最终趋于优化问题的整体最优解。对于一般无约束优化问题:minf(X)模拟退火算法的一般框架[1~3]:给定起、止/温度0T、T0,模拟参数初始化X0;While(T>T0)do在X0的邻域内模拟产生随机扰动vX;计算扰动引起的目标函数(能量)值的变化vE;若,vE[0,接受新值,否则若exp(vE/T)>rand(0,1)(rand(0,1)表示0~1之间的随机数),也接受新值,否则就拒绝;确定新的参数值,若扰动被接受,则X0wX0+vX,否则X0wX0;若接受新值,降温Twupdate(T),否则不降温;End其中:Twupdate(T)就是退火策略,也就是温度下降方法。:设tk为第k迭代时温度。对数下降[2]:tk=A/1og(k+k0)快速降温[2]:tk=B/(1+k)直线下降[1]:tk=(1-Kk)t0指数退温[1,2]:tk=Atk-1四种退火方法的温度下降速度是不一样的,指数退温是最常用的一种策略,其温度变化很有规律,直接与参数A相关。这里只研究指数退温策略,以此来总结规律。由tk=atk-1可知,tk=akt0=t0elnA-k因此称为指数退温,设起始温度为T=10000,其温度随着参数值不同与迭代次数a的关系如图1所示。图1温度随着参数A值不同与迭代次数的关系图由图1可知:A值越小,退火速度越快,所以我们重点研究不同A值对模拟退火算法的影响。,以下面4个国内外学者经常采用的优化测试函数[2]来研究。F1=100(x21-x2)2+(1-x1)2(1)F2=max(|x1|-|x2|)(2)F3=sin2x21+x22-[1+(x21+x22)]2-(3)F4=x21+x22(4)以解F1为例来说明用MATLAB语言设计的方法与步骤:第一步:=aneal_f1(x)y=100*(x(1)*x(1)-x(2)2+(1-x(1)2;第二步:(假设起始温度T=10000,终止温度T0=1,A=)x1=[11];%参数初始化T=100000;a=;N=1;whileT>1f1=aneal_f1(x1);%计算原来目标函数x2(1)=x1(1)+*(rand-);x2(2)=x1(2)+*(rand-);f2=aneal_f1(x2);%计算新的目标函数iff2-f1<0T=T*a;x1=(N)=f2;