模拟退火算法在连续变量全局优化问题中应用.pdf

《模拟退火算法在连续变量全局优化问题中应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2001年10月北京航空航天大学学报0ctober2001第27卷第5期JournaiofBeijingUniversityofAeronauticsandAstronauticsVoi.27No.5模拟退火算法在连续变量全局优化问题中应用江加和宋子善沈为群邱力为（北京航空航天大学自动控制系）摘要：研究了基于模拟退火算法应用于连续变量全局优化问题，并给出了实现步骤.介绍了控制参数实用选择方法.针对连续变量的特殊性，给出了新解产生的实用方法.最后以计算机视觉领域中的基本矩阵的求解作为一个实例，来说明它在连续变量中的应用.大量数字仿真结果表明该算法能有效地

2、解决连续变量全局优化问题.关键词：退火；最优化算法；随机搜索；基本矩阵中图分类号：0242.1文献标识码：A文章编号：1001-596（52001）05-0556-04I模拟退火（simuiatedanneaiing）算法是一类被对偶（s，f），解空间sC#，目标函数是f一个映称为蒙特卡罗（MonteCario）法的随机张驰法.模射，f：s、#的I维实数函数，现在问题是寻找最拟退火不像确定的基于梯度的迭代算法，后者总小值点!min6s，使得（f!min）＄（f!），V!Cs.是在目标函数下降的方向上运动；前者允许目标!"$模拟退火算法简介函数在增加的方

3、向上作随机的变化.因此，模拟退模拟退火算法采用Metropoiis准则，在算法的火算法能跳出局部极小值，该算法早在1953年由每一步，随机产生一个新的候选解.如果这个新解［1］［2］Metropoiis提出来，在1983年Kirkpatrick成功地使目标函数减小，那么它是可以接受的；否则要以将其应用于求解组合优化问题.指数概率的形式来决定它是否接受.接受新解的模拟退火方法是一种模拟金属退火过程随机概率P由下式给出：搜索方法.模拟退火过程从第一个“熔解”开始，系ex（p-!f/T）!f>0统处在一个足够高的温度下，在此温度下几乎所P={（1）1!f＄0

4、有的随机运动都是可接受的，接着温度依据“冷式中，!f是由随机扰动引起的目标函数的变化；凝”规则慢慢下降.在每一个温度点必须经过足够T是温度.从（1）式不难看出，对于一个给定的长的时间系统才能达到稳定状态，最终处在能量!f，当T相对较大时，接受正能量的概率大于T最低状态.相对较小时的概率.整个过程归结如下：模拟退火算法在离散变量全局优化问题上获得了广泛应用［2］，如货郎担问题、0-1背包问题以1）令i=0，T=T0，T0为初始温度，随机选择（0）及调度问题等等.近年来，用模拟退火算法求解初值!.［3］2）由!（i）随机扰动产生一个新的候选解连续变量全局优

5、化问题引起了人们的重视.连（i+1）续变量全局优化问题最大的不同点在于其解并非!.（i+1）（i）有限状态的组合，这给搜索增加困难.因此用模拟3）计算!f=（f!）-（f!）.退火算法求解连续变量全局优化问题相对复杂.4）如果!f＄0，接受新解；否则给出一个服从本文介绍了用模拟退火算法求解连续变量全局优均匀分布0到1之间的随机数r，如果化问题的实用方法.ex（p-!f）>r，则接受新解.5）i=i+1，如果i＄L，返回到第2）步.!模拟退火算法6）令i=0，根据温度方案减小T.!"!连续变量全局优化问题描述7）如果不满足终止条件，返回到第2）步，否连续

6、变量全局优化问题可描述为：给定一个则终止.收稿日期：2000-03-14作者简介：江加和（1965-），男，江西波阳人，博士生，100083，北京.第5期江加和等：模拟退火算法在连续变量全局优化问题中应用557从上述步骤可以看出模拟退火算法包括两个函数变化都很小，就可以认为系统趋于热平衡，循环，一个内循环和一个外循环.在内循环中，对MetropoiiS抽样达到稳定.也可以选择一个固定数应某个温度下，要求MetropoiiS抽样达到稳定，对作为MetropoiiS抽样稳定的条件.对于连续变量而于连续变量，理论上需经过无穷次迭代才能达到言，内循环次数L选取

7、对算法是否收敛起着至关稳定，实际上L选择一个有限值.外循环要求T重要的作用，如果L选取不当，有可能搜索不到趋于0时终止，实际上T选择一个接近于0的值，最优解.随着连续变量个数的增多，内循环次数L或者当计算值接近最优值，停止迭代.应随着增大.对于连续变量优化问题，其解并非是有限状态的组合，这给候选解的产生提出更高的要求，给3候选解产生方法搜索增加了困难.候选解由随机扰动产生，需经过连续变量候选解的产生与组合优化问题不大量的随机搜索得到最优解，特别是随着连续变同，后者的候选解的产生比较简单，只要调换两个量个数的增加，计算量也随着增加.序号，就可以产生邻域状

8、态，不管问题多复杂，它的状态是有限的；而前者，其邻域状态有无穷多，2控制参数的确定这给产生邻域