（分析化学专业论文）团簇结构优化新算法与应用研究.pdf

、。h ：、i ， d i s s e r w 汀i o ns u b m i 丌e dt o t h eg f 之a d u a t es c h o o lo fn a n k a iu n i v e r s i t y f o rt h ed e g r e eo fd o c t o ro fs c i e n c e d e v e l o p m e n t o fn e wg l o b a lo p t i m i z a t i o na l g o r i t h m sf o r s t r u c t u r a lo p t i m i z a t i o no f c l u s t e r s c a n d i d a t e ：x i a o l i y a n g s u p e r v i s o r ：p r o f x u e g u a n gs h a o s p e c i a l i t y ：a n a l y t i c a lc h e m i s t r y c o l l e g eo fc h e m i s t r y n a n k a iu n i v e r s i t y t i a n j i n3 0 0 0 7 1 ，er c h i n a a p r i l2 0 0 8 惴5 6肿2烘 脚1胛y 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：桶略确 2 o a 年皇月沙日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名： 卸矽 学位论文作者签名： 粕断 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：牺耐嘲 锄蟛年岁月2 0 日 摘要 摘要 团簇结构优化是计算化学领域中非常重要的研究课题之一。然而团簇结构 优化属于非常困难的全局优化问题，因为团簇势能曲面上存在着大量的局部极 值，且局部极值的个数随团簇的原子个数呈指数关系增长。因此，发展快速、 高效的优化算法成为解决团簇结构优化问题的关键。本论文针对大尺寸团簇结 构优化问题发展了两种全局优化算法，并成功用于l e n n e r d j o n e s ( l j ) 和银团 簇的结构优化。本论文的主要内容包括： 1 总结了团簇研究的意义、内容、手段及最新进展，重点总结了团簇结构 优化算法的研究进展，并综述了全局优化算法在团簇结构优化研究中的应用。 2 针对u 团簇的结构优化提出了一种动态格点搜索( d y n a m i cl a t t i c e s e a r c h i n g ，d l s ) 算法的变体，称为基于内核构建的动态格点搜索( d l sw i t h c o n s t r u c t e dc o r e ，d l s c ) 算法。该方法采用二十面体或十面体内核构建初始结构， 然后采用d l s 算法进行结构优化。将d l s c 方法用于u l o 睨o o 和l j 6 6 0 - 6 7 0 的结构 优化，结果表明d l s c 算法可以成功得到全局最稳定结构。由于内核的使用大大 减小了搜索空间，d l s c 比d l s 更加快速和高效。该算法对于小尺寸团簇结构优 化仍具有无偏性质，优化结果不受内核初始构型的影响，但随着团簇尺寸的增 大该算法逐渐从无偏转为有偏。 3 为了进一步提高d l s 算法的优化效率且不改变其无偏性，建立了一种内 部操作( i n t e r i o ro p e r a t i o n ，i o ) 与d l s 的联合算法，称为d l s i o 。i o 将势能 较高的外部原子沿径向移动到对应的团簇中心位置附近，使内部原子的排列更 加紧凑、外部原子的排列更加规整，且具有更低的能量。由于i o 优化得到的结 构比随机生成的结构更接近最稳定结构，降低了d l s 操作的搜索难度。将 d l s i o 方法用于l j 5 0 0 、u 5 6 l 、u 6 价u 6 6 5 、u 6 7 0 的结构优化，结果表明该方法 是一种无偏、高效的大尺寸团簇优化方法，为团簇结构的理论研究建立了有效 方法。 4 用d l s c 方法优化了a g l 2 1 - a g l 6 0 之间银团簇最优结构并考察了a g l 3 - a g l 6 0 的构型转化规律。a g l 3 a g a 8 为一系列无定型结构，其中仅有少数几个规则构型， a 9 4 9 一a 9 6 1 的最稳定构型为二十面体，a 9 6 2 一a g l 6 0 的最稳定构型转化为十面体，但 摘要 由m a r k s 十面体( ，z - d h ) 的不同子类构成，a g l 3 a 9 1 6 0 之间只在某些特定的尺 出现面心立方( f a c e c e n t e r e dc u b i c ，f c c ) 的最稳定构型。该结果为银团簇的 论研究提供了基础数据。 5 为了进一步考察银团簇的构型转化规律，采用d l s c 方法优化了2 1 a g l 7 0 - a g a l o 之间的银团簇结构。结果表明，在2 1 最优结构中包括9 个f c c 构 和1 2 个m d h 构型。因此，在此范围内银团簇的主要构型仍然是十面体，但 f c c 构型明显增多，可以推断更大尺寸的银团簇可能以f c c 构型为主。此结果 研究银团簇结构随尺寸大小的变化规律具有重要的参考价值。 关键词全局优化，优化算法，l e n n a r d j o n e s 团簇，银团簇 a b s t r a c t a b s t r a c t s t m c t u r a lo p t i m i z a t i o no fa t o m i co rm o l e c u l a rc l u s t e r si sa ni m p o r t a n tp r o b l e m i nc o m p u t a t i o n a lc h e m i s t r yf i e l d h o w e v e r , i ti s n o t o r i o u s l yd i f f i c u l tb e c a u s et h e n u m b e ro fl o c a lm i n i m at e n d st og r o we x p o n e n t i a l l yw i t hc l u s t e rs i z e p r o p o s i n g f a s t e ra n dm o r ee f f i c i e n to p t i m i z a t i o nm e t h o d si sak e ys t e pt oc l u s t e rs 缸u c n l r a l o p t i m i z a t i o n i nt h i sd i s s e r t a t i o n ，t w og l o b a lo p t i m i z a t i o nm e t h o d sw e r ed e v e l o p t e d a n da p p l i e dt ot h es t r u c t u r a lo p t i m i z a t i o no fl a r g es i z el e n n a r d j o n e sa n ds i l v e r c l u s t e r s 1 i m p o r t a n c e ，m e t h o d s ，a n da d v a n c e si nc l u s t e rs t u d i e sw e r ei n t r o d u c e d ， f o c u s i n go nt h ed e v e l o p m e n t so fg l o b a lo p t i m i z a t i o nm e t h o d s a p p l i c a t i o n so ft h e g l o b a lo p t i m i z a t i o nm e t h o d si ns 仃u d u r a l o p t i m i z a t i o no fa t o m i c m o l e c u l a rc l u s t e r s w e r er e v i e w e d 2 av a r i a t i o no ft h ep r e v i o u sd y n a m i cl a t t i c es e a r c h i n g ( d l s ) m e t h o d ，n a m e da s d l sw i t hc o n s t r u c t e dc o r e ( d l s c ) ，w a sp r o p o s e df o rs t m c t u r a lo p t i m i z a t i o no f l e n n a r d j o n e s ( l j ) c l u s t e r s i nd l s c ，t h es t a r t i n gr a n d o ms t r u c t u r ei sg e n e r a t e dw i t h a n i c o s a h e d r o no rad e c a h e d r o na sac o r e w i t ha n a p p l i c a t i o no fd l s ct o o p t i m i z a t i o no fl j l 0 0 _ 2 0 0a n dl j 6 6 0 - 6 7 0 ，i tw a sf o u n dt h a ta l lt h ep u t a t i v eg l o b a lm i n i m a c a nb eo b t a i n e db yu s i n gt h ed l s cm e t h o d ，a n dt h em e t h o dw a sp r o v e dt ob eh i g h e f f i c i e n tc o m p a r e dw i t ht h ep r e v i o u sd l s ，b e c a u s et h es e a r c h i n gs p a c ei sr e d u c e db y t h eu s eo ft h ef i x e dc o r e h o w e v e r , a l t h o u g hd l s ci ss t i l la nu n b i a s e da p p r o a c hf o r s m a l l e rl jc l u s t e r s ，i tt u m e do u tt ob eb i a s e df o rl a r g eo n e s 3 f o ri m p r o v i n gt h ee f f i c i e n c yo fd l sm e t h o df o ru n b i a s e do p t i m i z a t i o n ，ak i n d o ft h ei n t e r i o ro p e r a t i o n ( 1 0 ) w a sc o m b i n e dw i t hd l s t h em e t h o di sn a m e da s d l s - i o i om o v e so u t e ra t o m sw i t hh i g h e re n e r g yt o w a r dt h ec o o r d i n a t ec e n t e r , w h i c hm a k e st h ei n t e r i o ra t o m sm o r ec o m p a c ta n dt h eo u t e ra t o m sm o r eu n i f o r m l y d i s t r i b u t e dw i t hl o w e rp o t e n t i a le n e r g y t h e r e f o r e ，t h es t a r t i n gs t r u c t u r ef o rd l s o p e r a t i o n si sc l o s e rt ot h eg l o b a lo p t i m u mc o m p a r e dw i t ht h er a n d o m l yg e n e r a t e d s t r u c t u r e s o p t i m i z a t i o n so fl j s o o ，u 5 6 l ，u 6 6 0 ，u 6 6 5a n dl j 6 7 0w e r ei n v e s t i g a t e dw i t h t h ed l s i oa n dt h es t r u c t u r a lt r a n s i t i o nd u r i n gt h eo p t i m i z a t i o nw a sa n a l y z e d i tw a s i i i a b s t r a c t f o u n dt h a tt h em e t h o di se 伍c i e n ta n du n b i a s e df o ro p t i m i z a t i o no fl a r g el jc l u s t e r s t h e r e f o r e ，i tm a yb eap r o m i s i n ga p p r o a c ht ob eu n i v e r s a l l yu s e df o rs t r u c t u r a l o p t i m i z a t i o n s 4 t h es t r u c t u r e so fs i l v e rc l u s t e r sf i o ma g l 2 1t o a g l 6 0w e r eo p t i m i z e dw i t h d l s cm e t h o d ，s t r u c t u r a lc h a r a c t e r i s t i co fs i l v e rc l u s t e r sw i t ht h eg r o w t ho fc l u s t e r s i z ei si n v e s t i g a t e df r o ma g l 3t oa g l 2 0 as e to fa m o r p h o u ss t r u c t u r e sw a so b t a i n e di n t h es i z er a n g eo f13 - 4 8 ，t o g e t h e rw i t hs e v e r a lo r d e r e ds t r u c t u r e s t h ep u t a t i v es t a b l e m o t i fi si c o s a h e d r o ni nt h es i z er a n g eo f4 9 61 ，a n dt h e n ，c h a n g e st od e c a h e d r o ni n t h es i z er a n g eo f6 2 - 1 6 0 f u r t h e r m o r e ，i tw a sa l s of o u n dt h a t ，f o rc l u s t e r sw i t h d e c a h e d r a lm o t i f , t h es t a b l es t r u c t u r ei sar e s u l to ft h e c o m p e t i t i o na m o n gt h e d i f f e r e n tm a r k sd e c a h e d r a lm o t i f s o nt h eo t h e rh a n d ，f a c ec e n t e r e dc u b i c ( f e c ) m o t i f c a no n l yb eo b t a i n e df o rs o m es p e c i f i cs i z e si nt h i ss i z er a n g e 5 f o rf u r t h e rs t u d y i n gt h es t r u c t u r a lt r a n s i t i o no fs i l v e rc l u s t e r s ，2 1s i l v e r c l u s t e r si nt h es i z er a n g eo f17 0 - 310w e r eo p t i m i z e dw i t hd l s c r e s u l t ss h o wt h a t ， a m o n gt h e2 1c l u s t e r s ，n i n ef e ca n dt w l e v em - d hs t r u c t u r e sa r eo b t a i n e d t m ss h o w s t h a tt h em a i nm o t i fi ss t i l lm d hf r o ma g l 7 0t oa 9 3 1 0 ，b u tt h ep r o p o r t i o no ff e e s t r u c t u r e so b v i o u s l yi n c r e a s e d s o ，i tc a nb ed e d u c e dt h a tf e em o t i fm a yb em o r e s t a b l ef o rs i l v e rc l u s t e r sw i t hl a r g es i z e k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，o p t i m i z a t i o nm e t h o d ，l e n n a r d - j o n e sc l u s t e r , s i l v e r c l u s t e r i v 目录 目录 摘要i a b s t r a c t i i i 第一章综述1 第一节团簇研究概述1 第二节全局优化算法3 1 2 1 无偏全局优化方法。4 1 2 2 有偏全局优化算法1 2 第三节全局优化算法在团簇结构优化研究中的应用进展1 3 1 3 1 金属团簇1 3 1 3 2c 原子团簇1 5 1 3 3c 6 0 分子团簇1 6 1 3 4 水分子团簇1 7 第四节本论文的选题18 参考文献2 0 第二章基于内核构建的动态格点搜索算法3 2 第一节引言3 2 第二节算法3 3 2 2 1 动态格点搜索算法3 3 2 2 2 内核构建3 5 2 2 3 基于内核构建的动态格点搜索算法3 6 第三节结果与讨论3 6 2 3 1 成功率3 6 2 3 2 计算速度4 0 v 目录 2 3 3 搜索能力4 1 2 3 4 大尺寸团簇的结构优化4 3 第四节结论4 4 参考文献4 6 第三章基于内部操作的动态格点搜索算法4 9 第一节引言4 9 第二节算法。5 l 3 2 1 内部操作5 l 3 2 2 基于内部操作的动态格点搜索算法5 3 第三节结果讨论5 4 3 3 1 内部操作过程中的构型转化5 5 3 3 2 表面构型的转变5 7 3 3 3 动态格点搜索过程中的构型转化6 0 3 3 4 大尺寸团簇的结构优化6 2 第四节结论6 3 参考文献6 4 第四章a 9 1 3 一a 9 1 6 0 团簇的结构优化与构型转化6 7 第一节引言6 7 第二节算法6 9 第三节结果与讨论。7 1 4 3 1 优化结果7 l 4 3 2 构型与能量随着团簇大小的变化7 7 4 3 3 最稳定构型分布8 l 第四节结论8 3 参考文献8 5 v i 第五章a 9 1 7 0 a 9 3 l o 的结构优 第一节引言 第二节算法 第三节结果与讨论 第四节结论 参考文献一 致谢 个人简历、在学期间发表的学 定 和 例 态 且 里 特 计 信 体 不 或 构 的 主 演 究 这 较 粒 粒 种 第一章综述 研究团簇在不同条件下从原子分子长成固体的结构演变成为团簇研究的重要问 题之一。 团簇的研究可追溯n - 十世纪五十年代后期，1 9 5 6 年b e c k e r 用超声喷注加 冷凝法制得团簇【4 j 。但是直到七十年代团簇研究仍处于零星分散的研究状态，八 十年代后期随着实验条件的改善，团簇研究得到了快速的发展，一些发达国家 的著名大学和研究所都在积极开展团簇研究。其中最为突出的是美国加州大学 伯克利分校的k n i g h t 教授通过超声波膨胀发现钠团簇具有幻数结构，相对应的 价电子结构为满壳层【5 】。之后c 6 0 团簇的发现及其简单的制备方法引起了学术界 的轰动，越来越多的学者致力于团簇方面的研究。在美国物理学会一年一度的 年会( m a r c hm e e t i n g ) 上团簇方面的论文逐年增加，9 8 、9 9 年发表的论文比9 0 年代初增加了1 0 倍。从此，团簇作为崭新的研究领域正式进入科学家的视野。 近年来获取尺寸可选择的团簇以及逐一尺寸研究团簇的各种性质，受到广泛的 重视并取得了一系列重要进展，标志着团簇研究已由初创期考察简单体系和单 一特性转向探索复杂体系，由基础研究逐渐走向应用和开发。 团簇的性质与结构之间存在着非常密切的联系，团簇结构是理解团簇独特 性质的关键之一【6 】。团簇稳定结构的确定一直都是团簇科学界关注的重要问题 _ 刀。但是只有惰性元素等少数几种团簇的结构得到了实验和理论两方面的确定 8 - 1 0 ，其余的团簇结构一般通过理论研究来确定。用于团簇理论研究的方法很多， 从相互作用原理方面分为基于经验势的方法、基于半经验势的方法和从头计算 法( 不带任何经验参数) 。其中最精确的是从头计算澍1 1 l2 1 ，该方法直接由基本 物理量( 如普朗克常数、电子电荷和质量等) 和基本原理出发，通过自洽计算 来确定体系的基态和激发态性质，但是它的计算量过大，对于电子数目较多的 体系无法应用。同样局域密度泛函方法( 1 0 c a ld e n s i t yf u n c t i o n a la l g o r i t h m ，l d f a ) 【1 3 ，1 4 】虽然在计算小团簇方面取得了巨大的成功，但当团簇尺寸增大到2 0 个原子 以上时同样受到了计算量的限制。因此各种有效的势模型常常被用来更有效地 描述中等尺寸以上团簇的键合。近年来己发展了一系列精确度不同的相互作用 势，如第一原理多体势 15 1 、m o r s e 势【1 6 】、t e r s o f f 势【1 7 18 1 、e a m ( e m b e d d e da t o m m e t h o d ) 势 1 9 】、r g l ( r o s a t o g u i l l o p e l e g r a n d ) 势【2 们、g u p t a 势和u ( l e n n a r d j o n e s ) 1 2 6 对势【2 2 】等。基于各种势模型的蒙特卡洛( m o n t ec a r o ) 模 拟和分子动力学( m o l e c u l a rd y n a m i c s ) 模拟都已广泛用于研究团簇的热力学性 质和基态性质【2 3 | 。但是团簇的势能曲面( p o t e n t i a le n e r g ys u r f a c e ，p e s ) 在相空间 2 第一章综述 中是一个高维曲面 2 4 且存在大量局部极值( 1 0 c a lm i n i m a ) ，团簇结构的优化问题 实质是全局最低能量的搜索问题【2 5 1 。随着团簇尺寸增大局部极值数目按指数关 系增长，因此团簇优化问题属于n p ( n o n d e t e r m i n i s t i cp o l y n a m i a l ) 困难问题【2 6 1 。 即使仅包含1 0 个原子的团簇计算工作量也相当大，因此发展高效优化算法仍然 是团簇科学工作者所面临的一项重要任务。 本章主要总结了优化算法的发展以及在团簇研究中应用。 第二节全局优化算法 由于团簇势能曲面上局部极值的数目随着团簇尺寸呈指数关系增长，团簇 优化属于n p 难题，这使得寻找势能曲面上的全局最低能量非常困难，需要发展 高效、快速的全局优化方法才能使搜索变得可行、可信。 l e n n a r d j o n e s ( u ) 势能函数只考虑原子间的范德华力，函数形式非常简单， 为原子间距离的1 2 6 对势，具体的函数表达式为： e = 4 s 。磊 ( 号 1 2 一( 号 6 式中是原子数目，惭表示第f 个原子与第，个原子间的距离，可以直接通过原 子间坐标计算。s 和盯分别是二聚体势饼深( p a i rw e l ld e p t h ) 和平衡距离 ( e q u i l i b r i u mp a i rs e p a r a t i o n ) ，通常取s = 睐简化u 势能表达式。l j 势能可以 精确描述某些粒子间的势能关系，如低温下的稀有气体团簇。 由于u 势能函数形式简单，常用来考察团簇的构型随原子数增长的变化趋 势 2 m 1 1 。但是由于u 势能曲面非常粗糙而且具有大量的局部极值，u 团簇的结 构优化对于算法来讲仍然是一个巨大的挑战。u 团簇的部分最低能量结构可以 通过实验方法和大量的模拟方法得到，因此常用来评价算法的优化能力及效率。 剑桥大学的w a l e s 课题组建立的剑桥团簇数据库【3 2 1 收录了目前优化到的u 团簇 最稳定结构及对应能量。 根据是否利用了待优化问题的已有知识可将优化方法分为有偏( b i a s e d ) 优 化算法和无偏( u n b i a s e d ) 优化算法两种。其中有偏优化算法从构建好的格点开 始搜索或者基于格点搜索来进行优化，所以有偏优化算法的特点是快速，但是 此类算法只能够优化到格点对应的构型。而无偏优化算法从随机产生的结构开 3 函数值最小。利用m e t r o p o l i s 准则并适当地控制温度的下降过程实现模拟退火， 从而达到在多项式时间内求解全局优化问题的目标。 s a 算法的优化过程包括初始解的产生、解空间搜索和目标函数评价三部分。 计算过程如下： ( 1 ) 随机产生初始解s o ( 算法迭代的起点) ，设定初始温度t ( 充分大) 以及每个温度对应的迭代次数l 。 ( 2 ) 根据当前温度，采用微扰方法产生一个新解。根据m e t r o p o l i s 准则判 断是否接受此新解。如果新解满足终止条件则作为最优解，结束程序，否则对 当前温度迭代l 次。 ( 3 ) 降低温度，根据迭代次数计算当前温度，重复步骤( 2 ) ，直到温度降 低到终止温度再停止算法，选择模拟过程中得到的最优解作为近似解。 4 第一章综述 s a 算法作为随机全局优化算法将大范围的粗略搜索与局部的精细搜索相结 合。当温度较高时随机产生初始解的分布范围较大，并以较大概率接受使目标 函数变差的解，从而实现大范围搜索。随着温度的下降，解产生的分布范围逐 渐减小，接受使目标值变差解的概率也逐渐变小，从而使搜索过程从全局逐步 变为局部搜索。s a 求得的最终解和初始解无关，从理论上已经证明可以收敛于 全局最优解。 s a 对于团簇优化问题有着天然的优势，在不使用局部优化方法的情况下， s a 是局部优化能力最强的全局优化算法，能够搜索到能量比较低的结构。但是 s a 有着明显的缺点，即在温度较低时算法容易陷入局部极值无法跳出。由于在 团簇优化问题中势能益面过于复杂，跳出局部极值需要越过很高的能垒，而s a 陷入局部极优时，退火温度往往不足以提供越出能量陷阱体系所需的自由能， 因此s a 及其变体通常只用来优化较小尺寸的团簇结构 3 6 。3 8 1 。针对这种情况 x u e ”】提出了一种改进的并行s a 算法，并用该算法首次优化得到了u 6 5 与u 6 6 的全局最稳定结构。该算法将局部优化算法与s a 结合在一起，使s a 可以使用 较高的退火温度，更注重全局信息。基于特快速退火算法和群体进化策略的快 速退火演化算法( f a s ta n n e a l i n ge v o l u t i o n a r ya l g o r i t h m ，f a e a ) 【37 】结合了局部优 化算法后也成功得到了u 2 7 5 团簇的所有最稳定结构【4 0 1 。并行化的f a e a 优化能 力进一步得到提高，可以优化得到1 1 6 个原子内所有u 团簇的最稳定结构 4 1 1 。 2 0 0 3 年，l e e 提出了一种基于构象空间的退火算法，成功优化到了2 0 1 个原子 范围内的u 团簇最稳定结构畔j 。s a 及其变体除了用于团簇结构优化外还用于 分析团簇势能曲面 4 2 , 4 3 】。 1 2 1 2 b a s i n h o p p i n g 算法 剑桥大学的w a l e s 教授在1 9 9 7 年提出了b a s i n h o p p i n g ( b h ) 算法，该算法 是目前应用比较广泛的一种无偏结构优化方法，其实质是m o n t ec a r l o 方法和能 量极小化方法的联合使用。在b h 算法中每一次结构改变之后都调用局部优化方 法对能量进行局部优化，算法操作的对象为这些局部极值。因此对于b h 算法的 搜索过程而言势能曲面变成了一系列能量平台，每一个平台对应于势能曲面上 的一个势阱。这种变化不但消除了势能面上的过渡态，而且由于没有了能垒算 法可以在平台边界自由通过、加速动态越迁。 w a l e s 用b h 方法成功优化得到了1 1 0 个原子以内所有u 团簇的最稳定结 5 1 2 1 3 遗传算法 二十世纪六十年代h o l l a n d 5 0 】提出了遗传算法( g e n e t i ca l g o r i t h m ，g a ) ，这 是一类借鉴生物自然选择和遗传机制的随机优化算法。遗传算法的特点是以群 体方式进行搜索，群体中个体间信息相互交流，搜索不依赖于梯度，适合处理 传统搜索方法难于解决的复杂非线性问题。遗传算法以达尔文由低级到高级的 进化论( 适者生存) 为基础模拟进化过程，评价值或适应值高的个体有较大的 遗传机率。而且遗传算法的操作沿用了自然界的遗传策略，新个体由父代个体 遗传信息的交叉和变异生成。与自然界相似，遗传算法本身对问题一无所知， 它所需要的仅仅是算法对产生的个体进行评价并基于适应值来选择个体，使适 应值较高的个体有更多的繁殖机会。遗传算法的基本过程是一个迭代过程，包 括群体的初始化、个体的评价、个体的选择以及杂交、变异开发下一代群体。 遗传算法对整个参数空间进行全局搜索。群体在遗传算子作用下对解空间 的不同区域同时进行搜索，构成一个不断进化的群体序列。通过杂交操作把群 体集中到搜索空间期望值最高的部分。因此杂交操作是遗传算法的核心，也是 与其他算法的区别所在。为了避免陷入局部最小值，遗传算法引入了变异操作， 一方面可以在当前位置附近找到更好的解，另一方面可以保持群体的多样性， 确保继续优化。 用遗传算法优化团簇的基本思想是：对于一个给定尺寸的团簇，用原子坐 标来表示团簇，每个个体代表一个团簇结构，随机产生一定数目的结构构成整 个群体，然后对团簇结构进行遗传操作得到更低能量结构。h a r t k e 在九十年代早 期首次用g a 优化了小尺寸硅团簇结构【5 1 | ，结果证实了遗传算法可用于团簇结 构优化。1 9 9 9 年，b a r r o n 等用g a 优化了1 3 到1 4 7 个原子范围内的u 团簇结 6 第一章综述 构，得到了所有构型种类的稳定结构【5 2 1 。但在团簇优化中g a 的基因串为原子 坐标的编码，因而基于基因串的杂交操作相当于对两个父代团簇进行一种混乱 的混合，得到的子代与其父代在结构上基本上毫无相似性与继承性可言。从实 际效果讲这种杂交更像混乱的变异。因此传统的g a 优化能力有限，只能用于优 化较小尺寸的团簇结构【5 3 ”】。 d e a v e n 和h o 【5 纠对传统g a 的杂交操作进行了改进，提出了针对分子结构优 化的显性杂交策略，称为d e a v e n h o 遗传算法( d e a v e n h og e n e t i ca l g o r i t h m ， d h g a ) 或显性遗传算法( p h e n o t y p eg a ) 。j o l l l l s t o n 【5 6 】在关于遗传算法的综述 中讲解了d h g a 的显性杂交策略，在该方法中杂交操作并不直接用基因串来操 作，而是将两个团簇的部分结构进行交换。此外，在d h g a 优化过程中结合了 局部优化方法，从而克服了g a 局部优化能力弱的缺点。1 9 9 6 年，d e a v e n 等用 d h g a 优化得到了原子数1 0 0 内的u 团簇的大部分最低能量结构，其中有些是 首次发现【57 | 。1 9 9 7 年，p u l l a n 将d h g a 用于u 单原子团簇、混合原子团簇及 小尺寸分子团簇结构优化，得到了1 0 0 个原子范围内所有u 团簇的最稳定结构、 2 0 个原子范围内的混合原子团簇最稳定结构、3 2 个原子范围内的分子团簇最稳 定结构【5 引。1 9 9 8 年，w o l f 和l a n d m a n 又用d h g a 方法优化得到了1 0 0 个原子 范围内u 团簇的所有最稳定结构【5 9 1 。 为了进一步提高d h g a 的优化性能，h a r t k e 6 0 】在原有算法的基础上对优化 过程中得到的团簇结构作平面投影，根据投影图来区别团簇结构，而且还引入 了生物学中小生境( n i c h e ) 的概念，即在群体中还有具有相似结构的小生境。 该算法通过限定处于同一小生境中相似个体的数量，使得群体的多样性得到保 证。h a r t k e 应用该算法优化得到了1 5 0 个原子范围内u 团簇的全部最稳定结构 ( i - j 9 8 新结构除外) ，结果表明该算法对那些非二十面体构型的优化效率也比较 古 同o m i c h a e l i a n t 6 1 】提出了基于g a 的新型算法一共生算法( s y m b i o t i ca l g o r i t h m ) 。 该算法利用最近邻原子的强耦合作用来指导遗传算法的选择过程，而且进化过 程针对结构单元进行，这大大提高了g a 的搜索效率。该算法可用于大尺寸团簇 的最低能量异构体的优化。y u a n 等在2 0 0 8 年又提出了一种杂合型遗传算法并用 于解决全局优化问题【6 2 】。除此之外g a 在近年来也广泛用于多种类型团簇的结 构优化，在下面章节中将详细总结。 7 第一章综述 1 2 1 4 势能曲面变形方法 势能曲面变形( h y p e r s u r f a c ed e f o r m a t i o n ) 方法的优化原理是对势能函 一步处理，使粗糙的势能曲面变得平滑，减少局部极值的数目，从而使优 得简单。此类方法的关键是平滑后曲面上搜索到的最低能量是否能够回复 初势能曲面上的最低能量，是否是全局最低能量。平滑处理后的势能曲面 对全局最低能量的位置产生巨大影响 6 3 硎。势能曲面变形算法必须与一种 的局部搜索方法联合使用以确保将搜索到的极值映射回原势能曲面，而且 同时取多个局部极值【6 3 ，65 1 。以下介绍几种常见的势能曲面变形方法： d e m 方法( d i f f u s i o ne q u a t i o nm e t h o d ) 是一种平滑势能曲面的优化算 6 7 】。图1 1 给出了d e m 方法的示意图。 图1 1d e m 方法对势能面的变形与优化原理示意图 从图1 1 中可见，势能面的变化由下而上随着优化过程势能面上的盆地 ( b a s i n ) 变得越来越浅，某些本来较小的盆地逐渐消失，最后只剩下一个大盆 地，此时用梯度优化方法由任意起点可以优化得到一个局部极值。由该局部极 值出发逐步逆推曲面势能平滑过程，最后得到全局最低能量。d e m 方法被用于 优化l j 5 5 以内的几个团簇结构【鲫，结果表明该算法可以成功优化得到团簇的最 稳定结构。 距离调整算法( d i s t a n c es c a l i n gm e t h o d ，d s m ) 通过改变粒子间距离来对势 能曲面做平滑处理，适用于优化对势( p a i r w i s ep o t e n t i a l ) 。p i l l a r d y 等【6 8 】联合d s m 与分子动力学( m o l e c u l a rd y n a m i c s ，m d ) 方法优化了较小尺寸的氩原子团簇结 8 第一章综述 构( - 5 3 1 ) 。其中m d 用于在变形后的曲面上寻找全局最低能量。由于能量曲 面的变形降低了局部极值之间的能垒，使m d 能够有效地搜索构象空间。p i l l a r d y 等【6 9 】单独使用d s m 优化小尺寸u 团簇结构，发现了l j 3 8 非二十面体的最低能 量。他们还提出了自适应d s m 算法( s e l f - c o n s i s t e n tb a s i n t o d e f o r m e dm a p p i n g ， s c d b m ) 并用该方法优化了1 0 0 个原子范围内的u 团簇结构，得到了除去u 7 5 - 7 7 十面体构型外的其他全局最低能量 7 0 】。 其它的势能曲面变形方法还有l o c a t e l l i 提出的快速全局优化算法【7 l 】。该算 法通过修改势函数扩大最稳定构型在势能面上所处的范围，然后恢复原来的势 函数，对优化得到的团簇结构作局部优化。该算法成功优化得到了较难优化的 l j 3 8 、l j 7 5 、t j 9 s 和u 1 0 2 的团簇最低能量。 1 2 1 5 自适应免疫算法 自适应免疫算法( a d a p t i