模拟退火算法 第四节幻灯片.ppt

文档介绍：模拟退火算法的应用
应用的一般要求
模拟退火算法应用的一般形式是:从选定的初
始解开始,在借助于控制参数 t 递减时产生的一
系列马氏链中,利用一个新解产生装置和接受准
则,重复进行包括“产生新解-计算目标函数差
-判断是否接受新解-接受(或舍弃)新解”这
四个任务的试验,不断对当前解迭代,从而达到
,算法的应用需满足如下三个方面的要求:
,由解空间,目标函数和初始解三部分组成.
解空间,它为问题的所有可能解的集合,它限

的优化问题,任一可能解即为一可行解,因此解

问题中,一个解除满足目标函数最优的要求外,
还必须满足一组约束,因此在解集中可能包含一
,可以限定解空间仅为所有可
行解的集合,即在构造解时就考虑到对解的约束;也可允许解空间包含不可行解,而在目标函数中
加上所谓罚函数以“惩罚”不可行解的出现,将不
可行解可行化.
,可分为如下四个步骤:
首先,.
其次,计算与新解伴随的目标函数差.
第三,.
其中 t 为控制参数,Δf 为新解与当前解之间的目
标函数差(在最小化问题中)或当前解与新解之
间的目标函数差(在最大化问题中).此外,在
有约束但又限定解空间仅包含可行解的问题中,
上述接受准则中还必须加上对新解的可行性判定.
最后,当新解被确定接受时,,,则在原当前解的基础上继续下一轮试验.
.
组合优化问题的应用
(TSP)
一解空间
解空间 F 可表为{1,2 … n} 的所有循环排列的集合,即
其中每一循环排列表示遍访 n 个城市的一条回路,πi =j 表示在第 i 个次序访问城市 j ,并约定πn+1= (1,2 … n).
二目标函数
注意到约定πn+1= π1 .
三新解的产生
此时的目标函数即为访问所有城市的路径长度或称为代价函数,须求其最小值,选为
用2-opt u 和 v ,交换u 和 v的位置,即可产生新路径为(设 u < v )
六冷却进度表.

CHN144 实例而言,可取
t0280, tk1 tk,  , Lk 100n,
停止准则是:在 s 个相继的马氏链中解无任何变化就终止算法.(如可取s=1).
初始路径图
算法得到的优化路径图