文档介绍：分类号学号 D200877531
学校代码 10487 密级
博士学位论文
原子团簇结构预测的现实途径—高性能启发式算法
学位申请人: 赖向京
学科专业: 计算机软件与理论
指导教师: 黄文奇教授
答辩日期: 2012年 5月29日
A Dissertation Submitted in Partial Fulfillment of the Requirements for
the Degree of Doctor of Philosophy puter Science and Technology
Practical Approach to Structure Prediction of Atomic
Clusters — High-Performance Heuristic Algorithms
:Xiangjing Lai
Major :Computer Software and Theory
Supervisor :Prof. Wenqi Huang
Huazhong University of Science and Technology
Wuhan,Hubei 430074,P. R. China
May,2012.
独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研
究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他个人或
集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在
文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名:
日期: 年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权
保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。
本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检
索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本论文属于保密□,在_____年解密后适用本授权书。
不保密□。
学位论文作者签名: 指导教师签名:
日期: 年月日日期: 年月日
华中科技大学博士学位论文
摘要
原子(或分子) 团簇的几何结构是其最基本的特征之一,直接影响着团簇的其它
物理化学性质。因此,预测团簇的基态结构常常是团簇研究的第一步。然而,由于
团簇构型空间随团簇大小呈指数型增长,该问题在理论上被证明是 NP-hard 问题。
对于 NP-hard 问题,目前计算机科学界普遍认为不存在多项式时间复杂度的精
确算法。在这种背景下,国内外学者提出了大量的启发式算法。启发式算法虽然不
能保证获得问题的最优解,但它能在合理的计算时间内给出满足一定要求的次优解,
从而成为求解 NP-hard 问题的现实途径。
本文针对以下三种团簇设计了四个启发式算法,即 Lennard-Jones 团簇,多体势
能建模的金属团簇及二元合金团簇。Lennard-Jones 团簇由对势能(pair potential)建
模;由于在表述及计算上的简单性,它已成为团簇优化算法的试金石;另一方面,
由于在势能形式上过于简单,它只能用于建模少数惰性气体团簇。对于更复杂的团
簇,如金属团簇及合金团簇,多体势能可以更精确地描述原子间的相互作用,从而
被物理化学家广泛采用。在目前的研究中,我们采用了 Gupta 多体势能给金属团簇
与合金团簇建模。
对于 Lennard-Jones 团簇的优化,我们提出了一个混合的启发式算法,即含内部
算子及两阶段局部下降的动态格子搜索算法。在该算法的前一阶段,内部算子将若
干能量较高的表面原子移入团簇的内部,从而逐渐地降低团簇的势能并使其构型有
序;并且,两阶段局部下降算法通过利用一个修改的势能模型把搜索过程引入有前
途的构型区域,极大地提高了算法的成功率。在算法的后一阶段,一个动态格子搜
索算法对团簇表面的原子进行优化,进一步降低了团簇的势能。算法在 N<680 范围
内的团簇上进行了测试。计算结果表明,当前算法在计算效率上明显优于文献中已
有的算法;而且,对于 LJ533、LJ536 这两个算例,当前算法改进了先前的最好结果。
此外,为了强调搜索的无偏性,提出了该算法的一个变种;计算结果表明了它的有
效性。
I
华中科