TSP问题的模拟退火算法ppt课件.pptx

TSP问题的模拟退火算法 1 模拟退火简介1 1问题讨论模拟退火算法步骤参数选取模拟退火算法求解TSP问题 2 1模拟退火简介 物理解释 材料中的原子原来会停留在使内能有局部最小值的位置 加热使能量变大 原子会离开原来位置 而随机在其他位置中移动 退火冷却时速度较慢 使得原子有较多可能可以找到内能比原先更低的位置 统计学解释 我们将热力学的理论套用到统计学上 将搜寻空间内每一点想像成空气内的分子 搜寻空间内的每一点 也像空气分子一样带有 动能 以表示该点对命题的合适程度 算法先以搜寻空间内一个任意点作起始 每一步先选择一个 邻居 然后再计算从现有位置到达 邻居 的概率 3 1 模拟退火简介 假设物体在加热一定温度后 它的所有分子存在D种状态空间 随着温度的下降 这些分子停留在不同的状态 最终趋于稳定状态 由统计力学研究表明 在温度T 分子停留在状态r的概率满足波兹曼 Boltzmann 概率分布其中 E r 是状态r的能量 Z T 是概率分布的标准化因子 4 1 1问题讨论 在同一个温度T下 能量高的状态概率大还是小 设E1 E2 有所以即表示 分子停留在能量小的状态概率大 当T 时 不同状态的概率分布 5 1 1问题讨论 首先 求最低能量状态概率与温度T的关系 求导当rmin是D中最低能量的状态时 得 6 1 1问题讨论 然后其中 D0是有最低能量的状态集合 因此 当T 0时 即 当温度趋于0时 分子停留在最低能量状态的概率趋于1 7 2 模拟退火算法步骤 Metropolis准则 Step1 任选一个初始解i0 k 0 初始温度t0 tmax Step2 若在该温度达到内循环条件 则到Step3 否则 从领域N i 中随机选一个j 计算 fij f j f i 若 fij 0 则i j 否则若exp fij tk random 0 1 时 则i j 重复Step2 Step3 若在该tk 1 d tk k k 1 若满足外循环停止条件 终止计算 否则 回到Step2 8 2 模拟退火算法步骤 内循环 Step2表示在同一温度tk时 在一些状态的随机搜索 当温度很低tk 0时 exp fij tk 0 停止条件 内循环次数step maxstep 若是 转到Step3 且降温tk 1 tk step 0 k k 1增加新温度tk下的maxstep maxstep a 若否 step step 1 反复Step2 外循环 停止条件是温度tk足够低 tk e 若是 算法结束 输出结果 若否 回到Step2 9 3 参数选取 t0tk 1 tkmaxstep maxstep a t0太大 计算时间增加 t0太小 会过早陷入局部最优 10 4 模拟退火算法求TSP问题 解的表示 用一个访问序列T t1 t2 t3 tn t1 来表示经过n个城市的顺序 距离矩阵 D dij 是由城市i和城市j之间的距离所组成的距离矩阵 数学模型 解的邻域 随机产生2个位置 让序列T上对应的两个位置上的城市顺序对换 11 4 模拟退火算法求TSP问题 Tips 访问序列T t1 t2 t3 tn t1 简化为T