1、2.2 模拟退火算法收敛性一 马尔可夫链定义 2.1：设 X(k)k 0,1,2, 为随机变量序列， X(k) i 称在时刻 k 处于状态 i， i， 称为 状态空间 当 中的状态数有限时，称为有限状态空间若对任意的正整数 n， X(k)k 0,1,2, 满足 则称 X(k)k 0,1,2, 为 马尔可夫链 ，简称 马氏链 马氏链具有一种 记忆遗忘功能 ，它只记忆前一时刻的状态 (2.8)可以简单地记成称为 一步转移概率 当状态空间有限时，称为 有限马氏链 定义 2.2：马氏链 X(k)k 0,1,2, 称为 齐次的 ，如果对任意 m 和 n 及任意状态 i 和 j ，只要即要求 转移概率与
2、n 无关 ，也即无论质点在何时处于状态 i ，只要由 i 出发经一单位时间转移到 j ，其概率都相同反之，若一个马氏链的相伴转移概率依赖于 n，就称该马尔可夫链为 非齐次的 P(X(n) i) 0， P(X(m) i) 0 就有用表示马氏链的 n步转移概率 ，它表示自 i出发，经 n步到达 j 的概率例 当温度 t 给定时，由 (2.5)， (2.6)， (2.7)确定的马氏链是齐次的由马氏链的性质，模拟退火算法 收敛性证明 沿用下面过程齐次算法 ：(1)在每一个给定的温度 t，给出 (2.5)的一步转移概率 pij (t) 的一些限定条件得到 平稳分布概率其中， X(n,t)表示在温度 t 时，马氏链第 n 步运动的随机变量(2)给出平稳分布应该满足的条件，使得当温度渐近达到零度时，平稳分布的极限存在，即要求(3)进一步要求平稳分布的极限具有全局最优性条件其中 Dopt为 最优状态集 综合上面 3条，得到 全局性收敛 的表达式
