模拟退火算法的改进及其应用

《模拟退火算法的改进及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、应用数学八八,理模拟退火算法的改进及其应用‘王强武汉大学计算机科学系,然提要模拟退火算法是随机优化近似算法本文首先介绍其物理背景和一般形式后通过对算法增加记忆,和返回两个功能以及在算法之后链接一个局部搜索过程改,,最善了算法性能接着将改进算法应用于解旅游商问题后对该算法作简要的性能评论关键词模拟退火算法随机变量随机函数旅游商问题动态规划解法空间复杂性时间复杂性组合优化问题主题分类模拟退火算法的背景和内容仁’〕「〕〕,,模拟退火算法是一种随机优化近似算法其思想来源于热动力系统特别是液体的,,“凝固与结晶过程或者金属的冷却与退火过程对于金属冷却在物

2、理上快速冷却过程称为粹”,“”,火系统的能量绝对降低但不会达到最低能量而缓慢冷却过程称为退火由于原子失去热动力时有充裕的时间重新分布系统能够达到最低能量状态“退”,在火过程中系统的能量服从概率分布’一,了其中为能量,为温度,为常数该分布说明系统依概率尸处于任一能量为艺,,“的热平衡状态并且随着温度的降低系统处于高能量状态的概率随之减小这就是退”火规律模拟退火算法就是模拟热动力系统运用这一规律进行优化数值计算的方法运用模拟退火算法解决问题需要模拟热动力系统将问题转化为适宜算法的数学模型,于,设为实数集为正实数集无特别声明后续符号沿用前面符号说明描

3、述问题的全部可能解,记全部可能解的集合为几对应于热平衡系统的状态集‘、、,一‘,,‘任,构造出由当前解随机产生新解的随机函数宁门右任为随机变量类似于热动力系统中状态迁移的自发摄动机制口,任十确定与当前解相对应的极小化目标函数〔类似于热动力系统当前状态的能量一选择控制参数“任类似于热动力系统的温度收稿日期一一修订日期一一国家自然科学基金资助项目第期王强模拟退火算法的改进及其应用一￡‘」引入准则,,,一‘一一八,“,△一一,,,任根据上面数学模型及式,其中定义决择随机函数,,,一“右一‘,叩镇户△夕,尸△,,,宁,军任,其中佰任为随机变量为随机变量

4、任’,任,十,专算法模拟退火算法给定从口〔出发开始算法随机变量宁每次变,’一,叩宁,,一‘,甲化由决择随机函数得到新解令随机变量宁变化若干次后减小的值,在新的,任下重复上述过程直到满足某个停止准则为止对模拟退火算法的改进考,虑算法的实践运用由于决择函数的随机性终止解可能不是整个过程所遇解中,,口,最优的即使是最优的在算法无法穷尽可能解集的情况下虽然阐明了算法对整体,,最优解的渐近收敛性但的可接受性也不能不遭到怀疑另外当终止解毗邻整体最优解的时候,算法本身不能迅速进一步逼近甚至达到它鉴于,对算法进行改进,提出算以上分析法‘,算法改进模拟退火算法在

5、算法中设置一个记忆器一任刀又伙记录过程‘’,“一中决择函数确定的最优解及其目标函数值设为算法的终止解比较,,‘‘、和如果则令一最后进行下面过程由随机函数产生新解一·泞,,‘“厂,一‘宁变化若干次后终止算法仅当时接受令,可以记住并返,一定程度提高了算法算法具有记忆和返回功能回到曾经历过的最优解,“”,的稳定性而算法最后的迭代过程这里称粹火改善实际上是在算法之后链接上一个局,“”“”,“”部搜索过程这样不仅可以通过退火结果与粹火结果的比较对退火结果的可靠性进行,一定程度的评价提供直观帮助而且可以获得更好的近似解甚至整体最优解在旅游商问题上的应用·,

6、,,,,二二旅游商问题即给定两两连通的个城市⋯要从出发遍访每个城市恰好一,,,,乞」,次最后返回求最短路径这是图论中的著名问题是一个完全问题闭难度问题的完整精确解法,其复杂度会是令人难,当稍大时,以接受的川因此解此问题只能满足于求近似解本节遵循这一精神,用算法巧妙解决这一问题,同时使计算量为的一个多项式函数首先,建立如下数学模型,,⋯,,配置可能解将每个城市赋以标号则每个配置旅游顺序可以表为到,,的一个排列用数组存贮镇动镇为某一城市标号,。,重排机制按林氏的方法川采用如下两种形式随机选取一段路径代之以该路径,的逆序路径随机选取一段路径及其外一点

7、将这段路径插入到该点之后极小化目标函数给出由城市位置决定的距离矩阵对称或非对称应用数学年蜘︸甄︸仅一月”况“·必,,,,于其中簇簇为城市到的距离是,’习,占,,,,’‘’,了占,一,一”‘艺⋯闪·其中声任艺占,一,,⋯,式等价于式一艺‘,‘‘其中约定一,如果实际问题有这样的要求经过一条河流或山脉的次数尽量少或多那么可以采用所谓罚函数的方法确定目标函数如规定河流一侧的城市的参数为,·一另一侧的城市的,,于是式可写成参数为石一八,、。。一,,’艺「其中久为某个正常数或负常数,,,,一,⋯,,,⋯满足任,十一控制参数任实现算法的一般步骤为一,,。,①

8、令式中给出控制参数任初值任意取一初始排列计算相应的目标函,一。‘,,‘。‘。数值然后置一一与同大小数组‘,’,,,,②由产生重排计算一及色一一再由式计