基于混沌变量的模拟退火优化方法.pdf

第14卷第4期控制与决策1999年7月
Vol.14No.4CONTROLANDDECISIONJuly1999

基于混沌变量的模拟退火优化方法X

王子才张彤王宏伟
(哈尔滨工业大学控制工程系,150001)

摘要基于混沌变量,提出一种混沌模拟退火优化方法,给出了初始温度的确定方法。利用混
沌变量对当前点进行扰动,随着搜索的深入逐渐减小扰动的幅度。数值计算结果表明,该方法可
以显著提高求解全局优化问题的计算效率。
关键词混沌变量,模拟退火,优化
分类号TP273.1

1引言

模拟退火(SA)[1]是80年代初发展起来的一种随机性组合优化方法。它模拟高温金属降
温的热力学过程,并广泛应用于组合优化问题。SA在进行优化时先确定初始温度,随机选择
一个初始状态并考察该状态的目标函数值;对当前状态附加一小扰动,并计算新状态的目标函
数值;以概念1接受较好点,以某种概率Pr接受较差点作为当前点,直到系统冷却。SA适用范
围广,算法简单,便于实现,是一种有效的全局优化方法。模拟退火区别于单纯随机搜索主要在
于它以某种概率接受较差点,从而使跳出局部最优解成为可能。模拟退火寻优效率的关键在于
随机搜索变量产生方式和温度下降策略的确定。
混沌(Chaos)是自然界中一种常见的非线性现象。混沌变量看似杂乱的变化过程其实含
有内在的规律性,利用混沌变量的随机性、遍历性及规律性可以进行优化搜索[2]。混沌优化方
法分两个阶段进行:首先,在整个空间内按混沌变量的变化规律依次考察经过的各点,接受较
好点作为当前最优点;其次,一定步数后认为当前最优点已在最优点附近,然后以当前最优点
为中心,附加一混沌小扰动,进行细搜索寻找最优点。混沌优化方法思路直观,编程实现简单方
便,经仿真验证是一种良好的优化方法。
模拟退火方法在初始温度足够高、温度下降足够慢的条件下,能以概率1收敛到全局最优
值。对随机向量概率密度函数(生成函数)及系统冷却方法的优良设计将提高其寻优效率。文
献[3]采用Cauchy分布生成函数及相应冷却方式形成快速模拟退火。文献[4,5]分别按某种
生成函数及相应的温度更新函数得到了更好的模拟退火全局优化方法。本文考虑把混沌变量
引入模拟退火,这相当于给混沌优化方法增加一个启发式规则。基于混沌变量的模拟退火方法
——混沌模拟退火方法(CSA)将集结混沌优化方法与模拟退火优化方法的优点。这也是本文
的出发点。

2混沌模拟退火方法

本文的目的是综合混沌优化和模拟退火优化的优点,从而设计出一种较好的模拟退火策

X国家高等学校博士点基金(9521320)资助课题

1997-12-29收稿,1998-02-12修回
©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net
382控制与决策1999年

略。这一是利用混沌变量自身的变化规律,二是利用模拟退火中的启发式规则。我们从初始温
度的确定、随机扰动的确定及温度下降策略三方面讨论所提出的混沌模拟退火方法。
2.1初始温度及温度下降策略的确定
应用模拟退火时,通常给出一个足够高的初始温度,以便让最初的随机搜索很充分,这实

际上进行了许多冗余的迭代。Lin等人把遗传算法与模拟退火相结合,导出了一种获得T0的
[6]
方法。本文模仿Lin的思路来确定初始温度。假定取开始时接受较差点的概率为Pr0,则Pr0

=exp(-$CöT0),其中$C为新点的函数值减去老点的函数值。于是有T0=-$CölnPr0。先
按混沌寻优方法的第一个阶段搜索N个可能解,并记录这N个点所对应的目标函数值的最大

最小值。$C=fmax-fmin为其中最大最小值之差。可看作是对随机两个点对应函数值之差最

大值的近似估计。于是按下式确定初始温度T0

fmin-fmax
T0=(1)
lnPr0

本文采用指数下降的降温方法:Tk+1=CTk,其中C<1。对不同的优化问题需要选择不同
的C,问题复杂时C应选得较大。一般C∈[0.95,0.999]。
2.2随机扰动的确定
混沌优化方法中的细搜索方式为
3
X′=X+ACk(2)
3
其中X为当前最优解,Ck为当前混沌向量。这种方式需要对X′进行越界处理,并且A的取值
不易确定。基于此,本文将(2)式改为如下的混沌扰动方法
3
C′k=(1-A)C+ACk,A<1(3)
其中C3为当前最优解映射到[0,1]区间后形成的向量,我们称为最优混沌向量。(3)式方式可

以保证C′k取值在[0,1]区间,免去了原先算法中对X′越界的处理。经多次仿真计算表明,(3)

式效果明显好于(2)式。另外,(3)式中的A采用了自适应选取,这是因为搜索初期