PDF《文 童辕 号：1》

@ l 第20卷 第 3期

2 O O O年 9月 物理学进展PRoGRESS I N PHYS I (

2 5 Vo

1 2 0, No.

3 S印t.,2000文童辕 号:1000-0542(2000}03-0319-16推广模拟退火方法及其应用向阳龚新高 . - 一l-_-一(中国科学院固体物理研究所 , 台肥

2 3

0 0

3 1 )

0 2 / 摘要:本文介绍了推广模扳退火方法的基本思想及其坑计基础.我们通过一系列标准 函数测试了推广模拟退火方法舶性 能.作为该方法 的应用 , 我们研究 了Thornso~问磨 和 团簇结 构 最后 , 探讨了推广摸拙退火 方法的教率随体系复杂性舶变化. 关毽 词:最优化;

推广模拙退火算法;

Ⅲ

3 ∞ 问题 中圄分类 号:O224;

O4

1 1 .

9 文献标 识码 : A

1 引言在自然 科学 , 社会科 学,以及人 们的 日常生 活 中广泛存 在着大量 的求 最 太或最小 的问 题,即所 谓 的最 优化 问题 , 用 数学语 言来说 , 就 是决定 一组 参量 , 使其 对应的 目标 函数 达到 最小 值 或最 大值 .例如 , 近 年来 , 由于c50的发 现,物理学 家 和化 学家 对 团簇 发生了广泛 丽浓 厚 的兴趣 【

1 -

9 ] .真实 团簇 的 结构 , 就是指其 能量 ( 自由能) 最低的结 构,所以求 团簇 结构 问题 , 也就是求 其能 量最 低 的结构 阃题 .近年 来 自旋玻 璃 的研 究 中也 涉及 到求 体系总能最低 的结构 问题 .事 实上 , 最优 化 问题遍 及理 论物 理 和实 验物理 的各个 领域_1…, 有 必要 对最优 化 问题 和最优 化方 法进行广 泛而深人 的研究 . 总体上最优 化方法可以分 为两 大类:决定 性方法(determi n d me t t x x l s )和随机方法(staticme t h o d s ) E " J . 决定性的方法可以非常快,但容易陷人局部极小(1ocalmi n i mu m) .相反,随机方法不 易 陷入局 部极小 , 但 在有 限步数 内没有 一种随机方 法可以保证 找到全 局极 小 .在所有 的优 化方法 中.模拟退 火方法被 认为是最 有效 的方 法之一 . 模 拟退火方 法 的基 本思想来 源于 固体 的退 火过程 .首先我们 回顾 一下固体遇 火过程 的物 理图象 .在加热 固体 时,固体中原子 的热运 动不 断增 强,随着 温度 的不 断升 高,固体的 长程有序被 彻底破 坏,固体熔解为 液体 ( 或 气体 ) .冷却时 , 液体中原子 的热运 动渐 渐 减弱 , 随着 温度 的徐 棘降低 , 原子运 动渐趋 有序 .当湿 度降 至结 晶温 度后,原子运 动 变为 围绕 晶体格点 的微小 振动 , 液体 凝 固成 固体 , 这种由高 温 向低 温逐 渐降温的过 程称 为退 收藕 刚胡:

2 0

0 0 ~

0 1 Ml l 基金项 目:杰出青年基金 (

1 9

9 2

5 4

1 8 ) , 大规模科学计算(

9 7

3 ) 资助项 目物理学进展20卷 火 .退火 过程 中系统 的熵 值不断 减小 , 系统 能量了随温度 降低趋于最 小值 . 对 固体退 火 过程 的研究 给 人们 以新 的启示 .1

9 8 2年,Kirkpatrick等人 _ l I | 首先意识 到固体退火 过程与优 化 问题 之 间存 在 的类 似性 , Me t r b p o l i s 等对固体在 恒定温度 下达 到 热平 衡 过程 的模拟 也给他 们 以启迪 : 应 该把 Me t r o p o l i s准则 引入 到优 化过 程 中来 .最终他们 得到 一种对 Me t r o p o l i s 算法进行 迭代 的优化算 法,这种算 法类似 固体退火 过程 , 称之为" 模拟 退火算法 .具体方 案实施 如下 : (

1 ) 初始 时刻 :l , 在一 足够高 的初始 温度 丁( ) 下,随机选取一 个初始态 . , 计算 E ( ) (