PDF《文 童辕 号：1》

2 ) 根据某 种跃迁 分布 , 随机地从 x 跳到x… (

3 ) 计算 E( +

1 ) , 如果 E( +

1 ) r , 则用 + l 取代 x , 否则保 持不变 . (

4 ) 根据降温公 式,计算下一 步的温度 T( +1 ) 、 回到(

2 ) 重复以上 过程 , 直到 E达到某个 预定 的精度范 围. 在以上 方案 实 施过程 中.在任 意 一下 温度下 , 体 系可 以重复 试探 L次,这里 L称为Ma p Ko B链长 . 根 据跃迁 分布 , 降温方式 , 接 收几率 的不 同,模拟退火 可以分 为三种形式 : 经 典模拟退 火(A),快速模 拟退 火( F S A) , 推广模 拟退火 ( G S A) . 在经典模 拟退 火()[11J,跃迁分布是高斯 形式的 : , ^

一、2g( 缸)∞ 既p ( 一)(1)这里 z是变量z的试探跃迁距离 , 丁是约化单位的退火温度.如果跳跃使新能量变低 , 则新态 接收 ;

否则就 用Bokzma n - G i b b s 形 的接收几率 来判断接 收.接收几率 用Me t r o l ~ i s 形式:r^1P=r ai n l l , e x p ( 一I(2)CSA可 以收敛 到一个 不错 的全局极小 , 但 正如我 们 以下 要指 出的 , 它 的收敛 相 当慢 . G e m a n等人指 出,如果用 以上形式 的跃迁 和 接收 几率 , 则 以几率 l 找 到全 局极 小的充要 条件 是温度 随时间对数 下降【 … , 这就 是所 谓的经典模 拟退火 , 叉称为 B o l t z ma n n机器.

1 9

8 7年,Szu和 H a r t l e y提出了所 谓 的快 速模 拟退火 ( F S A ) C ' .F S A使用半局域 的Canchy-Lorentz跃迁分 布:个石0)这里 D 是变量空间的维数.C S A 采用的高斯分布是一个局域分布,而FSA采用的Cauchy-Lorentz跃迁 分布 是一个半 局域的分 布,在同样 的 温度 下,Cauchy-Lorentz分布使 体系有更 大机会 进行长距离跃 迁.F S A 中 的温 度随时问的倒 数lit,其接收几率仍 用Me t mt ~ i s的形式 . 以上介 绍了CSA和 F S A .尽 管在 目标 函数 的变 量较少 , 局域极小 不太多时它 们 能给 3期向阳等 : 推广 模 拟退 火 方法 及 其应 用 出合 理 的结果 , 当 目标 函数 的变 量很多 局域 极 小也 很多 时,这些方 法 容易 陷入 局 部极 小 而找不 到全 局极 小[1,为此人 们 又发 展_r更有 效 的推广 模拟退 火算法 [ ~ ' .

2 推广模拟退 火 的统 计基础1 l i s 统计Tsallls将熵的表 达式 = 一∑lln(此处w是可能 态的总数,P是相 应 的几 率) 推广 为[]:l(q∈ 侬)(4]g―i丁,'口t J J 【

4 J 可看 出,当q一1时,恢复原来熵 的表达 式.利用 ∑ l P , =L , 如 也可 以写成 : 南一p~-1)(5)(5)式表 明,在所有情 况下≥0 , 当w=1 时,0.在正则 系统 中.在两个约 束∑tP.=l 和∑l户=(e是髑级)下求极值可得到::里(6)和;

∑[卜卢(1一g ) ] (

7 ) 是 推广 配分 函数 , 卢=1 ~ J E T是Lagrange参数 .在g一1极限下 , = P ― / zI (

8 ) Z t =∑ (

9 ) 又恢复了Boltzma n n统计.图1是几率 P随能量 变化 图像 .1 ) 当口1时,在￡= 处,几率 分 布发 散,当卢e 一+∞时,户―岫.以上是 关于 Ts a l l i s 统计 的一些基 本知识 , 包括 Ts a l l i s 熵,Tsallis几率 分布等等.T s a l l i s 统计,特别 是Tsallis几率分 布,是推广模 拟退火 的基础 . 图l几率P随能量的变化 物理学进展20卷

3 推广 模 拟退 火 的提 出 在模拟退 火【 " ] 中,最重 要的三个 部分就是 降温 方式,跃迁几率分 布和接收几 率分布.本 节的主要 内容 是给出它们 在推广模拟退 火【

8 _ 中的表达 式【

1 6 ] . 在Boltz~mnn机器 中,接收几率用 了Me t r o p o l i s 方案 : f