（概率论与数理统计专业论文）非时齐markov链的收敛性.pdf

中文摘要 捅要 求目标函数的最小值点的问题是计算数学中的一个重要问题 用确定算法 计算往往只能求出局部极小值点 而用近来迅速发展起来的随机算法 则往往 能求出最小值点 模拟退火算法是 种随机算法 这种算法在本质上是构造一个收敛的非时 齐马氏链 因此判别一个非时齐m a r k o v 链是否收敛是模拟退火算法的基本理论 问题 当前最常用的判别定理是d o b r u s h i n i s a a c s o n m a d s e n 定理 它给出了有限 状态空间上非时齐m a r k o v 链收敛的判准 本文的主要结果 定理3 3 用耦合的方法 给出了一个一般状态空间非 时齐马氏链收敛的判准 特别是所给条件只依赖于每步的转移概率 而不依赖 于该转移概率所确定的平稳分布 因此更便于在实际中的应用 关键词 耦合 模拟退火 非时齐m a r k o v 链 目标函数 湖北大学硕士学位论文 a bs t r a c t s e a r c h i n gf o rt l l em i n i m u mo ft h eo b j e c t i v ef u n c t i o ni sa ni m p o r t a n tp r o b l e mi n c o m p u t a t i o n a lm a t h e m a t i c s w eu s u a l l yg e tal o c a lm i n i m u mb yd e t e r m i n a t ea l g o r i t h m b u tw ec a l lo b t a i nt h eg l o b a lm i n i m u mb y u s i n gr e c e n t l yd e v e l o p i n gr a n d o ma l g o r i t h m t h es i m u l a t e da n n e a l i n ga l g o r i t h m s a ar a n d o ma l g o r i t h m c o n s t r u c t san o n h o m o g e n e o u sm a r k o vc h a i nw h i c hi sc o n v e r g e n c e s ot h eb a s i ct h e o r yp r o b l e mo f s ai st oj u d g et h ec o n v e r g e n c eo fn o n h o m o g e n e o u sm a r k o vc h a i n c u r r e n t l y t h e d o b r u s h i n i s a a c s o n m a d s e nt h e o r e mi sm o s t l yu s e da st h ec r i t e r i af o rt h ec o n v e r g e n c e o fn o n h o m o g e n e o u sm a r k o vc h a i ni nf i n i t es t a t es p a c e t h em a i nr e s u l to ft h i sp a p e r n a m e l yt h e o r e m3 3 s h o w sac r i t e r i af o rt h ec o n v e r g e n c eo fn o n h o m o g e n e o u sm a r k o vc h a i ni ng e n e r a ls t a t es p a c e i np a r t i c u l a r w h e nt h e g i v e nc o n d i t i o n so n l yd e p e n do nt h eo n es t e pt r a n s i t i o np r o b a b i l i t y n o tt h es t a t i o n a r y d i s t r i b u t i o no ft h et r a d i t i o n a la l g o r i t h m s oi ti sm o r ec o n v e n i e n ti np r a c t i c e k e yw o r d s c o u p l i n g s i m u l a t e da n n e a l i n g n o n h o m o g e n e o u sm a r k o vc h a i n p i r r e d u c i b i l i t y o b j e c t i v ef u n c t i o n i i 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任何其他个 人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡献的个人和集 体 均已在文中以明确方式标明 本人完全意识到本声明的法律后果由本人承 担 作者签名 卿嘉多 签名日期 勿占年占月弓日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留 使用学位论文的规定 即 按照学校要求提交学位论文的印刷本和电子版本 学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版 并提供目录检索与阅览服务 学 校可以允许采用影印 缩印 数字化或其它复制手段保存学位论文 在不以赢 利为目的的前提下 学校可以公开学位论文的部分或全部内容 保密论文在 解密后遵守此规定 作者签名 研参多 导师签名 丧劬乙义 日期 劲德年6 月弓日 日期 加 箨 月乒日 1引言 从上世纪八十年代以来 基于非时齐m a r k o v 链的全局最优解的随机搜索算 法已经引起了众多学者的极大关注 最初的一个例子是基于m e t r o p o l i s 采样的 模拟退火算法 阵1 k i r k p a t r i c k 等人为最优化问题提出的 1 1 2 随后由g e m a n 等人 引入到图像处理等应用领域中 3 4 模拟退火算法的基本步骤是依据非时齐m a r k o v 链在搜索空间上构造一 个图 并且从图中的一个点跳到另一个点 以此来探测搜索空间 非时 齐m a r k o v 链是在搜索过程中由一个点跳到一个 恶化 点 但这并不排除在这 个跳的过程中 可以从局部最优的 陷阱 中跳出来 的渐小概率生成 即模 拟退火算法的迭代过程就是m a r k o v 链的生成过程 这个m a r k o v 链通常是非时齐 的 5 研 当温度固定时 m a r k o v 链是时齐的 模拟退火算法的收敛性包含两个方面的内容 即算法能否在一个设定好的 有限时间内终止以及能否达到实际应用的需求 得到所需要的解 由于模拟退 火算法的随机性 进而转化为讨论其渐近收敛性 按渐近的概率原则收敛 模拟退火算法根据m e t r o p o l i s 准则接受新解 以一种概率的方式来进行搜索 从 而能够从局部最优的 陷阱 中跳出来 最后得到全局的最优解 并由此形成 一定长度的随机m a r k o v 链 5 8 因为m a r k o v 链的初始分布和每步的转移概率决 定了非时齐m a r k o v 链的分布 而初始分布不可控制 转移概率依赖于冷却进度 表f 9 以某一个速度收敛 所以我们的目标是寻找一个收敛的判断准则 使得对 任意初始分布 非时齐m a r k o v 链都收敛 以往关于这方面的结果大多是在有限状态或可数状态空间上的 1 0 1 1 但 是在实际应用中 经常碰到 般状态空间 例如礼维欧氏空间 p 上的非时 齐m a r k o v 链的收敛性问题 本文主要研究一般状态空间非时齐m a r k o v 链的收敛 性 并在第三章 定理3 3 给出了一般状态空间上的非时齐m a r k o v 链收敛的一 个判断准则 湖北大学硕士学位论文 2预备知识 为更好地说明在一般状态空间上 非时齐m a r k o v 链的收敛性问题 本章将 介绍m a r k o v 链的相关性质和耦合方法 2 1m a r k o v 链的概念 设 q 厂 p 是概率空间 x 留 x 是可测空间 其中留 x 是由x 中的可 数个子集生成的盯代数 记4 o 1 2 对任意死 4 k q x 是可 测映射 圣 九 铊 4 是一个定义于q 取值于状态空间x 上的随机序列 记碍 盯 如 i 0 1 2 礼 如果对v n 4 a 绍 x 都有 e 毋 a l 霹 e 毋 i 2 1 1 则随机序列圣 九 扎 2 是m a r k o v 链 1 2 13 若记r x a e 曲 a i 九 z z x a 留 x 则r r x a z x a 留 x 是概率核 即 1 对每个a 留 x p a 是x 上的非负可测函数 2 对每个z x p z 是留 x 的概率 概率测度r 称为m a r k o v 链圣的第n 步转移概率 如果p 1 恳 p 3 r 则称m a r k o v 链圣 九 n 4 是时齐m a r k o v 链 否则称为非时 齐m a r k o v 矧1 2 1 3 本文主要讨论非时齐m a r k o v 链 若用留 x 上的概率测度 记为奴的分布 即 则 p n a 尸 九 a a 三移 x p n a p o p l p 2 r a 户0 d 埘卢 州州产 州动 卢 卅 2 2 预备知识 又设 是匆 x 上的符号测度 p 的全变差范数 1 1 1 1 s u p if r 渺i i 1 1 2 1 2 如果存在勿 x 上的概率测度7 r 使得对留 x 上的任意概率测度p o 都有 p o 只 r 一7 r l 一0 n 0 0 2 1 3 则称非时齐m a r k o v 链是遍历的 7 r 称为极限分布 特别地 当只 恳 r o o m a r k o v 链西是时齐m a r k o v 链 则极限分布就是平稳分布 即对任意的a 留 x 有7 r a 7 r p a n q m a r k o v 过程存在定理知 由概率核序列 r n 1 可以决定一个非时 齐m a r k o v 链 1 2 1 3 后面我们总称 r 竹 1 是一个非时齐m a r k o v 链 2 2 耦合与全变差距离 设p l 芦2 是留 x 上的两个概率测度 豇是留 x 留 x 上的概率测度 如果满足边缘性 口 a lxx p 1 a 1 a 1 留 x 豇 x a 2 比2 a 2 a 2 留 x 则称豇是p 1 与p 2 的耦合 1 4 1 8 1 记k p 1 p 2 为肛1 与p 2 的全体耦合 引理2 1 令 1 弘2 记 d p l d 弘2 夕1 2 面 9 22 面 g m i n 9 1 9 2 y 夕d 肛7 v a a 9 1 一夕 d p a 劈 x 屹 a 9 2 一g d 上 a 绍 x q n 夕 z p d z b 留 x 穷 x 3 湖北大学硕士学位论文 易知 0 y 1 z l 地分别是历 x 上的测度 q 是劈 x 留 x 上的测度 令乒2t 警心引 则嘶 铴的耦厶 撇帕瑚基本 耦合 证明 若1 l 则有 g 9 1 9 2 p 7 一a 8 皿 a x q a x 夕 z p 7 d z j a x x n x 譬 2 耖 z 咖 z 州俄a 留 n 同理可证口 a x p 2 a a 留 x 即皿是芦1 与p 2 的耦合 若0 y s u pi f z p d z 一f f 妙 p d 矽 i l l p 一p z i i 再在上面不等式中对面 k p 1 j u 2 求下确界得到 风艇脚 d z 剪 豇 血 d 可 尹1 一跳 由上面不等式 并注意条件皿 k p 1 z 2 只需证 去1 1 1 圳 咖 虹 当1 1 时 上式显然成立 t l p o 0 当7 1 时 d z 可 2 d x d y d z 型掣 d z 可 q d x d y 譬掣 i i o 1 叶 一 i i 一1 1 一一y r 于是 只需证 丢i t 1 2 1 1 1 叶 湖北大学硕士学位论文 往证之 扣 咄i l 互1 s u s p 引理获证 i d p 一 d p l 趣s u p f f g d p f 州 l 三 厶 驰 c g g d p 7 一厶 o 使得 那么对任意的 l t 2 t 都有 蕃肌 肛t 一p i i 1 一 x 2 2 4 证明 令p 7 p t u 妒g l 蛆d p 仍 垃d p 由题设知 p 7 可令卯 啬 由于m 和肌 则有 从而有 夕l 夕3 纯 船 p 7 一n 8 一a 8 m i n g l 夕2 g g a p 7 一n 8 6 一 2 预备知识 所以j r 夕d p 7 f 9 3 d x 由引理2 2 的证明过程知 咱 l i 1 咖7 冬l 一 n 即式 2 2 4 获证 一 引理2 4 设p 1 岛是 x 留 x 上的两个概率核 对任意给定的z 和y 构造概 率p 1 z 和b y 的基本耦合j p z 则户 p x 秒 a z y x x x a 勿 x 留 x 是乘积空1 7 x x 留 x 留 x 上的概率核 证明 要证明 i v z y x x p x 可 是留 x 历 x 上的概率测度 i i v b 留 x 纺 x 户 斟是留 x 劈 x 可测的 由户的构造知 i 是显然成立的 往证 i i 为此记 q z 可 a p 1 z a 4 b 可 a z 秽 x x a 纺 x 夕 z z 亏p i 丽1 x d z 9 2 z 可 2 揣 g x 可 z min g x y z 92 x yg xm i n g l y 9 2 x z 可 2 z j z j j 先证夕1 夕2 g 是留 x x 历 x 留 x 可测的 三元可测 a 只证9 1 三元可测 即可 因为同理可证夕2 是三元可测的 而当夕l 9 2 元可测时 则夕显然是三元 可测的 注意到 历 x 是可数生成的 可找到 x 留 x 上的一个有限可测 划分序列 级 札 l 2 使得玩 1 是级的加细 即级中的元素是级 l 中 的若干个元素的并集 记级 b i 川 砂 酸 令 毋k m 归缸 徊蚋刈 咖 删畿蓦 注意到 q 础 b 船 z 可 b 等 z 眚笔熬是留 x 留 x 匆 x 可测的 从一 而夕i n z y z 也是留 x 留 x 留 x 可测的 7 湖北大学硕士学位论文 又由 级 扎 1 的构造易证 e b i n 1 z y y l 盯 丘 夕 n z y 从而对任意给定的z y x 夕i n z y 盯 吸 礼 1 是上鞅 而 o e 9 i z j 夕i n z 箩 z q z 可 d z 1 于是由上鞅收敛定理知 三元可测序列 夕 z y z n 1 是收敛的 易见 g l x y 名 j 婴9 i 哪 z y 名 q z 可 一口 s t l 一 因此夕1 作为三元可测函数序列 夕p 扎 1 的极限是三元可测的 对任意z y x a 劈 x 记r z 秒 a 厶夕 z y z q z y d z 魄 z 耖 a 仇 z 可 z 夕 z y z q y d z i 1 2 由于夕l 9 2 夕都是三元可测的 而任意的b 历 x q x y b 关 于 z y 是历 x 留 x 可测的 从而对任意给定的a 历 x v l x y a 屹 z 箩 a r x 掣 a 关于 z 是留 x 留 x 可测的 任意给定a 1 a 2 留 x 则 户 z 可 a a2 p仕 萝 x z 可 竺丛兰 三 砉毛掣 7 舢 z x 叩 a 1 a 2 r 任 x 1 z y r x 秒 z x z z a 1 a 2 由上面的讨论知 p x a 1 a 2 关 t x 可 是留 x 留 x 可测的 由此及单调类定理知 对任意的b 留 x 历 x p z 可 b 关于 z 耖 是勿 x 留 x 可测的 至此 i i 获证 2 预备知识 引理2 5 设 是纺 x 上的符号测度 p 是 x 历 x 上的概率核 则有 p i i 证明 因为当l f 1 时 p f l l 所以 p f i 1 lc t l 1 则 i i p i l s u pi u p f i s u pi v p f i s u pi 夕 l i li f l s lg e p f l f l l s u p l l j i i i g e f l f l 1 其中l f f d 引理得证 设沪 x 表示留 x 上的全体概率测度 在沪 x 上定义概率距离 p m p 2 0 p l r o l l 引理2 6 设 x 留 x 是波兰空间 则 夕 x p 是完各的度量空间 证明见文献 1 3 第1 6 9 页定理5 4 引理2 7 设 脚 n 1 c 汐 当 p p n p n 1 0 因为 p 肛 1 n 时 n i 有 j d 肌 肛 1 e 于是对任意的正整数m 由三角不等式知 故 p 几 竹 1 是c a u c h y 序列 一 引理2 8 设 x 留 x 是波兰空间 尸是时齐m a r k o v 链的每一步转移概率 若 存在非平凡测度儿f f 得 i n fp z 则p 存在平稳分布7 r 即7 r p 7 r 证明见文献1 1 2 1 第3 8 4 页定理1 6 0 2 9 肛pp 胁 一 ppp 胁 一 m npn p 湖北大学硕士学位论文 3非时齐m a r k o v 链的收敛性 3 1 有限状态空间的情形 当状态空间是有限集时 要判别一个非时齐m a r k o v 链的收敛性有下面的著 名结果 定理3 1 d o b r u s h i n i s a a c s o n m a d s e n 定 里1 1 9 2 0 设 是有限状态空间s 上的 非时齐m a r k o v 链 其第死步转移矩阵为r 如果他们满足 a 1 r 作为时齐的转移矩阵时有不变分布 a 2 i i 一7 r n li i o o a 3 或者满足l s a a c s o n m a d s e n 条件 对于任意概率分布向量p l 及正整 蜘 恒有 i i p 一 弓 r 0 0 n 或者满足d o b m s h i n 条件 对于任意j 收缩系数满足 c b r 0 佗一 2 0 其中c p j r i 1s u px l 一 f 1 1 只一r i 只是尸的第l 行组成的行向 量 那么存在s 上的概率测度丌 使得 1 1 1 一7 r i i 一0 n 0 0 2 无论什么初始分布 o 下 此非时齐的m a r k o v 链k 在时刻礼的分布弘a 恒有极限 0 p n 一7 r 0 0 n o o 定理3 2 模拟退火的收敛性定理1 1 9 数 k 是取值于s 上的非时齐m a r k o v 链 在s 上的概率7 r 使得 s 是有限集 i i s 是s 上的函 记肛竹 t p k t i s 如果存 i 如一7 r i 一0 n o o 1 0 3非时齐m a r k o v 链的收敛性 则百的支撑是 i s l i 5 曾 是 工 从而有 p 1 i m 1 n 3 1 2 这是模拟退火中非常适用的定理 由定理3 2 知 只要 3 1 1 式成立 则 3 1 2 式也成立 再有定理3 1 的条件成立 则 3 1 1 式成立 由此可知定 理3 1 的条件能推出 3 1 2 式成立 故定理3 1 不但有重要的理论价值 而且具 有重要的实用价值 3 2 一般状态空间的情形 上一节里我们介绍了有限状态空间上的非时齐m a r k o v 链的模拟退火理论 只讨论有限状态空间非时齐m a r k o v 链在实际应用中是不够的 下面我们将研究 在一般状态空间上模拟退火非时齐m a r k o v 链的收敛性问题 本小节的主要结果 是定理3 3 类似于有限状态空间上的d o b r u s h i n i s a a c s o n m a d s e n 定理 定理3 3 设 x 留 x 是波兰空间 给定历 x 上的非时齐m a r k o v 链 r 7 1 2 如果它满足 i n fp n z 珏 l 2 3 2 3 其中 是留 x 上的非平凡测度 i i 其中风 1 一 x 靠 1 一m i n g n x 1 x n 1 2 那么 存 在留 x 上的概率测度7 r 使得对任意留 x 上的概率测度肋 当n o o 时有 p o p l 易 r 一丌i i 0 证明 对每一个概率核只 耗 l 2 作为一个时齐i 约m a r k o v 链 由引 理2 8 知 存在唯一平稳分布7 1 n 即 r 下面分四步证明定理3 3 n 伊 l o 1 c 唧 湖北大学硕士学位论文 a i i 一7 r n 1 i i o o n b 对任意的概率测度p 1 与p 2 和任意的正整数歹有 i 卢l p 2 弓弓 1 r i i 0 扎一 c 存在概率测度7 r 使得i i 一7 r i 一0 佗 0 0 d 对任意的初始分布肋 有 p o p l 马 r 一丌l l 0 礼 o 证明 a 设r z y d u d v 是p n x 和r 1 可 的基本耦合 则由引 理2 2 和引理2 3 知 丢i i p 一只 1 1 m 口 赢 x y d u 删 氏 刎 x 由平稳分布的定义和引理2 4 及上式知 割 一 1 i i 扣丌n r 一 r o 磊 如 如 1 1 只 z 一r 磐 i i 引出 磊 u v d x d y s 死 她 以 靠 其中亓n 是 和 1 的基本耦合 于是由条件 i i 得到 i i 一 lo 2 靠 0 0 结论 a 得证 证明 b 设国n z 翟 g p n z 和r 可 的基本耦合 由引 1 2 3 非时齐m a r k o v 链的收敛性 理2 4 5 n 0 z 芗 是 xxx 纺 x x 勿 x 上的概率核 于是有 主i i m m g 一驯 扣p 弓弓 r p z 弓弓 r i l f z o a j 国n d u d v d 缸 u 3 2 4 往证之 为了证明 3 2 4 式成立 由引理2 2 知 我们只需证 明豇包岛 1 国扎为p 弓弓 r 与p 2 弓弓 l r 的耦合 为简单见 我们 只证佗 2 的情形 一般情形可类似地证明 即证口国1 国2 是p 1 只b 与p 2 p 1 p 2 的 耦合 由耦合的边缘性知 o i x 可 a x 且 z a 国1 z 可 x a p 1 可 a z x a 勿 x q 2 x 秒 a x p 2 z a q 2 z 可 xxa p 2 a z x a 勿 x 下面验证边缘性条件 皿囝l q 一2 axx p l p l p 2 a z x a 留 x p q q 2 x a p 2 只b a z x a 留 x 注意到p 1p 1 恳 a l d x p l x d y p 2 y a 而 硒讼a x 砌圳棚 x y d u d v 国2 u v a xx 砌州拥 刎 毗m 岛 u 卅 矾圳 p 1 叫u 恳 u a p d z b z d u p d 让 a 弘lp 1 p 2 a 即 3 2 5 式获证 类似地 可证 3 2 6 式成立 3 2 4 式获证 1 3 3 2 5 3 2 6 湖北大学硕士学位论文 由引理2 3 知 f d u 口 q n i z y d u d v 加 z 可 x 佗 1 2 糊j fd u v q z x d u d v 0 由此结合上式得 m 啪n 舢 毗删 m 可 如 佗 1 2 3 2 7 反复利用 3 2 7 式归纳得 硒岛 国n 札叫嘶 口 s 叠包岛 玩 1 u 秽 d 却 d z 们鳓 1 im 一0 竹 o o k j 由此结合 3 2 4 式知结论 b 得证 证明 c 由 a 知 i 一f i n 1 i 0 3n s t 当n n 时有 肋只 r 一7 r 0 1 4 3 2 8 p n 嘶 i 可 zd 可 dzd 一肛 一 n 一 一 3 非时齐m a r k o v 链的收敛性 对任意的正整数歹 7 7 利用三角不等式有 i i o 只 r 一7 r 0 l l p o p l r 一7 r 弓 r 7 r 弓 r 一丌 尬时 1 7 r 一乃0 n 1 时 一丌i l m 2 时 n 3 o 聃 一乃 七 i k l 恢一 10 n 2 时 l 弘 只 如一1 7 r 只i i n 时 3 2 1 3 3 2 1 4 3 2 1 5 3 2 1 6 都成立 把 3 2 1 3 3 2 1 5 代入 3 2 1 1 和 3 2 1 2 得到两个新的不等式 同 3 2 1 4 式一起代入到 3 2 1 0 式得 r 一7 r t l 0 铮j i 且对所有的i 有 1 则函 数g sxs f 0 1 1 称为s 和 的生成概率函数 其中鲂 玄乡主篇 i 断嘶顺素能 定义4 3 若数列 死 k 0 1 死为第k 次迭代的温度 满足 对任意 七有t k 0 t k 1 0 s t e p2 当停止条件s 不真对 执行以 f 步骤 2 j 给定x 七 i 选定玩 i 其概率分布为 p 磊 j l x k i 9 i j j u i 2 2 给定玩 歹 生成巩一 0 1 并且令 硒 卜z k u k 0 口 口 否则矿 0 2 3 令k 七 1 s t e p3 更瓤k 转到s t e p2o 此算法产生的随机过程 托 是一个定义在 s 上的离散时间的非时齐m a r k o v 链 且它的状态转移概率由下式给出 1 7 湖北大学硕士学位论文 p c 扎 引 t r c 七 g o m i n 1 e x p 一笔产 ic j l 一 疋 i j j s j l 其中 是生成概率 死表示温度控制参数 e x p 一掣1 表示接受概率 即 第一章中的入 意思是一旦由状态i 生成 它接受状态j 的概率 如果我们把 温度瓦固定在r 则算法4 1 生成的m a r k o v 链就是时齐的 且有转移矩阵p 尸c 虬 引 t g o m i n1 e x p 一笔攀 歹 1 一 r t i j e s j i 文献 6 2 1 的m a r k o v 链具有平稳分布7 r t 它的分量由下式给出 孵h 删唧 粥h 半 小 川 若t 0 则7 r t 收敛到丌 其分量仉 为 一 磅i i 其它 其中c 为常数 a a r t s 和k o r t s 1 1 1 讨论了在以上这些条件下 该算法渐进收敛到全 局最优解丌 l l p 定理4 1 当l 充分大时 目标函数 经过至多l 次迭代可达到全局最优解 进 一步 令序列 k 歹 时筏的值才会变化 设序列 凤 k 0 1 和 s k 七 0 1 满足 对任意k 0 5 凤 1 凤 1 凤 1 i r a 风 1 露 0 0 如 0 5 k 1 垓 雄一1 i n x 一1 i 则钵 氟 否则今 雄一l 更新 反 蠢 转到s t e p 2 这里我们采用m e t r o p o l i s 准则接受新解 先给定粒子的初始状态i 作为固 体的当前状态 该状态的能量是最 然后使随机选取的某个粒子的位移随机地 产生一个微小的变化 得到一个新状态歹 新状态的能量为b 如果e f 蜀 则要考虑到热 运动的影响 该新状态是否为 重要 状态 要依据固体处于该状态的几率来 判断 圆体处于状态i 和状态j 的几率为接受概率a 这样通过用随机发生器产生 o 1 区间的随机数7 若p r 则新状态为 重要 状态 否则新状态舍去 如果新状态j 为 重要 状态 就以j 取 代i 成为当前状态 否则仍以i 为当前状态 再重复以上新状态的产生过程 直 至系统趋于能晕最低的平衡状态 当温度趋于零时 p 为无穷小 在 0 1 区间随机产生一个小于p 的7 非常 2 0 4 非时齐m a r k o v 链的模拟退火算法 难 所以相当于不能接受任一个如果易 晟的新状态j 了 根据以上分析 基 于m e t r o p o l i s 采样准则的非时齐m a r k o v 链的模拟退火算法 的流程图如下 图4 1 非时齐m a r k o v 链的模拟退火算法的流程图 2 1 湖北大学硕士学位论文 结果及展望 模拟退火算法在本质上是构造一个收敛的非时齐马氏链的随机算法 因此 判别一个非时齐马氏链是否收敛是模拟退火算法的基本理论问题 d o b m s h i n i s a a c s o n m a d s e n 定理是当前最常用的判准 它给出了有限状态空问上非时齐马 氏链收敛的判准 本文的主要结果 定理3 3 用耦合的方法 给出了 个一般状态空间非 时齐马氏链收敛的判准 特别是所给条件只依赖于每步的转移概率 而不依赖 于该转移概率所确定的平稳分布 因此更便于在实际中的应用 当然 由于我们的知识有限 所以我们的工作中不可避免地存在着瑕疵和 有待进一步研究的地方 比如 1 一般状态空间的情形还有待进一步的研究 目前还没有证明定 理3 4 和d o b r u s h i n i s a a c s o n m a d s e n 定理相互等价 2 是否可以找到适当的漂移条件来判别非时齐m a r k o v 链的收敛性 3 m a r k o v 链的长度表示m e t r o p o l i s 算法第惫次迭代时产生的变换数 我 们是否可以构造好的m a r k o v 链 能够以较少的迭代次数达到较好的收敛结果 在对这些问题进行研究的过程中 我们坚信能够更加了解数学的博大精 深 也相信通过我们的努力 在不久的将来一定能使这些问题得到解决 2 2 参考文献 参考文献 1 h a n n i gj c h o n ge k p k u l k a m is r r e l a t i v ef r e q u e n c i e so fn o n h o m o g e n e o u sm a r k o vc h a i n si ns i m u l a t e da n n e a l i n ga n dr e l a t e da l g o r i t h m s a i e e e i c d c e c c 0 5 1 c s e v i l l e s p a i n 2 0 0 5 1 5 6 6 2 6 6 6 3 1 2 k i r k p a t r i c ks g e l a t tc d j r v e c c h im p o p t i m i z a t i o nb ys i m u l a t e da n n e a l i n g j s c i e n c e 1 9 8 3 4 5 9 8 2 2 0 6 7 1 6 8 0 3 m e t r o p o l i sn r o s e n b l u t ha w r o s e n b l u t hm n e ta 1 e q u a t i o no fs t a t ec a l c u l a t i o n sb yf a s tc o m p u t i n gm a c h i n e s j j o u r n a lo fc h e m i c a lp h y s i c s 1 9 5 3 6 2 1 1 0 8 7 1 0 9 2 4 g e m a ns g e m a nd s t o c h a s t i cr e l a x a t i o n g i b b sd i s t r i b u t i o n a n dt h eb a y e s i a n r e s t o r a t i o no fi m a g e s j i e e et r a n s p a t t e r na n a l y s i sm a c h i n ei n m l l i g e n c e 1 9 8 4 6 7 2 1 7 4 1 5 d e a nl i s a a c s o na n dr i c h a r dw m a d s e n m a r k o vc h a i n st h e o r ya n da p p l i c a t i o n m n e w y o r k w i l e y 1 9 7 6 6 g i d a sb n o n s t a t i o n a r ym a r k o vc h a i n sa n dc o n v e r g e n c eo ft h ea n n e a l i n ga l g o r i t h m j j s t a t i s t p h y s 19 8 5 3 9 7 3 13 1 7 l a wa m k e l t o nw d s i m u l a t i o nm o d e l i n g a n a l y s i s m 2 n de d i t i o n n e w y o r k m c g r a w h i l l i n c 1 9 9 l 8 h a d d o c kj m i t t e n t h a lj s i m u l a t i o no p t i m i z a t i o nu s i n gs i m u l a t e da n n e a l i n g j c o m p u t e r sa n di n d u s t r i a le n g i n e e r i n g19 9 2 2 0 4 8 7 3 9 5 9 h a j e kb c o o l i n gs c h e d u l e sf o ro p t i m a la n n e a l i n g j m a t h e m a t i c so fo p e r a t i o n s r e s e a r c h 1 9 9 8 2 1 3 3 11 3 2 9 10 d u d e w i c ze j d a l a is r a l l o c a t i o no fo b s e r v a t i o n si nr a n k i n ga n ds e l e c t i o n w i t hu n e q u a lv a r i a n c e s j s a n k h y a 1 9 7 5 b 3 7 2 8 7 8 11 a a r t se h l a n dk o r s tj s i m u l a t e da n n e a l i n ga n db o l t z m a n nm a c h i n e s m w i l e y n e wy o r k 1 9 8 9 2 3 湖北大学硕士学位论文 12 m e y ns e a ne t w e e d i er i c h a r dl m a r k o vc h a i n sa n ds t o c h a s t i cs t a b i l i t y m n e w y o r k s p r i n g e r v e r l a g 19 9 3 1 3 c h e nm e f r o mm a r k o vc h a i n st on o n e q u i l i b r i u mp a r t i c l es y s t e m s m s i n