模拟退火算法 第四节教程教案.ppt

2.4　模拟退火算法的应用 2.4.1　应用的一般要求 　模拟退火算法应用的一般形式是：从选定的初 始解开始，在借助于控制参数 t 递减时产生的一 系列马氏链中，利用一个新解产生装置和接受准 则，重复进行包括“产生新解－计算目标函数差 －判断是否接受新解－接受（或舍弃）新解” 这 四个任务的试验，不断对当前解迭代，从而达到 使目标函数最优的执行过程．因此，算法的应用需满足如下三个方面的要求： 一．数学模型，由解空间，目标函数和初始解三部分组成． 　解空间，它为问题的所有可能解的集合，它限 定了初始解选取和新解产生时的范围．对无约束 的优化问题，任一可能解即为一可行解，因此解 空间就是所有可行解的集合．而在许多组合优化 问题中，一个解除满足目标函数最优的要求外， 还必须满足一组约束，因此在解集中可能包含一 些不可行解．为此，可以限定解空间仅为所有可 行解的集合，即在构造解时就考虑到对解的约束；也可允许解空间包含不可行解，而在目标函数中 加上所谓罚函数以“惩罚”不可行解的出现，将不 可行解可行化． 二．新解的产生和接受机制，可分为如下四个步骤： 　首先，由一个产生装置从当前解在解空间中产生一个新解．通常选择由当前解经过简单地变换即可产生新解的方法． 其次，计算与新解伴随的目标函数差． 　第三，判断新解是否被接受．最常用的接受准则是Metropolis准则． 其中 t 为控制参数,Δf 为新解与当前解之间的目 标函数差（在最小化问题中）或当前解与新解之 间的目标函数差（在最大化问题中）．此外，在 有约束但又限定解空间仅包含可行解的问题中， 上述接受准则中还必须加上对新解的可行性判定． 　最后，当新解被确定接受时，用新解代替当前解．此时，当前解实现了一次迭代．可在此基础上开始下一轮试验．而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验． 三．冷却进度表． 2.4.2　组合优化问题的应用 １．旅行商问题（TSP） 一　解空间 　解空间 F 可表为{1,2 … n} 的所有循环排列的集合，即 其中每一循环排列表示遍访 n 个城市的一条回路，πi =j 表示在第 i 个次序访问城市 j ，并约定πn+1= π1．初始解可选为(1,2 … n)．　　 二　目标函数　 注意到约定πn+1= π1 ． 三　新解的产生 　此时的目标函数即为访问所有城市的路径长度或称为代价函数，须求其最小值，选为 　用2-opt 法．任选访问的序号 u 和 v ，交换u 和 v的位置，即可产生新路径为（设 u v ） 四　代价（目标）函数差 五　接受准则 伴随新解的代价函数差为 六　冷却进度表．　 　需由具体问题规模而定．例如康立山等对 CHN144 实例而言，可取 t0?280, tk?1? ? tk, ? ? 0.92, Lk? 100n， 停止准则是：在 s 个相继的马氏链中解无任何变化就终止算法．（如可取s=1）． 算法得到的优化路径图 2．0-1背包问题（ZKP） 一　解空间 　ZKP是一个有约束的优化问题，对此，我们限定解空间为所有可行解的集合，即 其中xi =1表示物品 i 被选择装入背包．初始解 选为(0,0 … 0)． 二　目标函数 为一需求最大值的价值函数 但必须满足约束 三　新解的产生 　随机选取物品 i ，若 i 不在背包中，则将其直接装入背包，或同时从背包中随机取出另一物品 j ；若 i 已在背包中，则将其取出，并同时随机装入另一物 品 j ．即 xi =1?xi ，且（或） xj =1? xj ，i ≠ j 四　背包价值差及体积差 根据产生新解的三种可能，伴随的背包价值差为 为判定解的可行性，还需求出对应的背包体积差为 其中ΔB为当前背包体积 B 的增量． 五　接受准则　 是扩充了可行性测定的Metropolis准则 六　冷却进度表 　例如对 n=20 的实例，可取 t0 =100，tk+1 =αtk ， α= 0.90 ，L= 50n．终止准则： s=1 ． 2.4.3　在连续和非线性优化中的应用 　从模拟退火算法的一般形式可以看出，该算法的应用并不局限于离散的和线性的优化问题．事实上，只要问题能满足2.4.1中提出的一般要求，就可以用模拟退火算法解．下面通过例子简要说明模拟退火算法在连续和非线性优化中的应用方法 . 例１求满足约束 的函数 的最大值． 　这是一个非线性量的非线性目标函数且带有非线性约束的优化问题，用理论方法求解有一定的困难，用模拟退火算法则容易得多． 　实际求解时，最简单的方法是每次随机产生变量 x、y、z 的一组值，当满足约束时再求目标函数的值，并按算法重复迭代，直至算法终止．但对本例这种带有等式约束的问题，在相当多的重复试验中也很难产生出满足约束的变量值组．为此可先将约束中的等式处理为 (?)式求出的