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

中国科学技术大学博士论文 摘要 摘要 全局优化问题是各学科普遍关注的课题。在化学领域，寻找化学结构的最低 能量构象具有重要意义。然而，结构优化问题相当困难，因为其势能曲面上局部 极值的数量非常多而且随着体系尺寸呈指数增长。在本论文中，发展了几种新颖 高效的全局优化算法并应用于团簇结构优化问题，采用优化算法作为构象分析方 法，研究了团簇势能 ( p o t e n t i a le n e r g yl a n d s c a p e ，p e l ) 的性质。 本论文总结了团簇研究的内容、手段和意义，综述了用于团簇结构优化研究 的全局优化算法、近期进展以及在团簇结构研究中的进展。本论文的主要研究内 容包括： 1 基于生物体系免疫机制的模拟，提出并建立了一种新颖的演化优化算法 一自适应免疫优化算法( a d a p t i v ei m m u n eo p t i m i z a t i o na l g o r i t h m ，a i o a ) 。a i o a 使 用浓度凋节机制和免疫选择机制自适应地控制群体的多样性和收敛速度。将 a i o a 应用于函数极小值问题，结果表明该算法与文献报导的随机优化方法相比 有着较好的优化效率。a i o a 还被成功应用于l e n n a r d j o n e s ( l j ) 团簇的结构优 化，优化得到了l j 8 0 以下的最优结构。 2 提出了一种用于描述团簇拓扑结构的连接表( c o n n e c t i v i t yt a b l e ，c t ) 并应 用于团簇结构的相似性检测。由于c t 包含了团簇的拓扑结构信息，它可以有效 地区分位于p e l 上不同构型的团簇。团簇相似性检测对于保证演化算法中的群 体多样性非常重要。将基于c t 的团簇相似性检测方法应用于a i o a ，成功地优 化得到了l j l l 0 以内的最优结构，并且优化效率很高。同时，对于更大尺寸的团 簇，该方法也表现出了很好的优化性能。 3 提出了一种基于能量的微扰策略和一种新的禁忌搜索方法，并与简单贪 婪方法( s i m p t eg r e e d ym e t h o d ) 相结合建立了一种新的团簇结构优化方法。与传统 的随机微扰策略相比较，基于能量的微扰策略在收敛速度和搜索能力上都有很大 提高。通过禁忌策略对势能曲面上不同面积低谷( f u n n e l ) 的搜索机会( 访问几率) 进行调控，均衡了不同低谷局部极值的访问率，使优化效率得到大大提高。利用 该方法优化得到了l j 2 0 0 以内的最优结构，并与文献报导的方法相比具有较高的 优化效率。 v 中国科学技术大学博士论文摘要 4 提出了一种高效的无偏全局优化方法一动态建模方法( 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 s 起始于一个随机产生的局部极4 、化的结构，并且通过迭代 进行动态格点( d y n a m i cl a t t i c e ，d l ) 的构建和搜索寻找更好的解。由于d l 能够极 大地减少搜索空间和非常耗时的局部能量极小化的次数，极大地提高了算法的运 行效率。首次使用无偏方法优化得到了l j 3 0 9 以下的所有最优结构，并且预测了 l j 5 0 0 的最优结构。d l s 算法为分子或原子团簇的结构优化提供了高效的优化方 法，使大尺寸团簇的无偏优化成为可能。 5 使用d l s 方法，预测了1 5 0 以内的c 6 0 分子团簇最优结构，其中8 0 以上 的c 6 0 团簇结构为首次报导。由于d l s 方法收敛速度很快且可以得到各种能量 较低的构型，通过记录不同构型的命中次数，对c 6 0 分子团簇进行了构象分析。 结果表明l e a r y 四面体序列尽管在能量上没有优势，但在一定尺寸范围内它在构 象上具有优势。同时，计算结果与高温下退火实验的结果在幻数峰的位置和峰高 上都比较吻合。 6 对实验学家和理论学家来说，p e l 理论已经成为一种统一的语言用来描述 各种反应体系。基于d l s 方法建立了一种团簇构象分析方法，由于d l s 具有很 高的优化效率，此方法可用于大尺寸( = 4 0 0 ) 团簇的构象分析和势能图分析。同 时。通过“构象熵”的定义讨论了构象熵与构象稳定性的关系；通过对温度的模 拟讨论了温度对构象稳定性的影响，结果与c 6 0 分子团簇的退火实验结果大致吻 合：此外，通过构象分析对p e l 与势函数的关系也进行了研究。 v i 中国科学技术太学博士论文摘要 a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e mi sas u b j e c to fi n t e n s ec u r r e n ti n t e r e s t i nc h e m i c a l f i e l d ，f i n d i n go u tt h ee n e r g y l o w e s tc o n f o r m a t i o no f as t r u c t u r ei so f g r e a ti m p o r t a n c e h o w e v e r ，t h es t r u c t u r a lo p t i m i z a t i o np r o b l e mi sn o t o r i o u s l yd i f f i c u l t b 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 hs y s t e ms i z e i nt h i s d i s s e r t a t i o n ，s e v e r a ln o v e la n de f f i c i e n tg l o b a lo p t i m i z a t i o nm e t h o d sw e r ep r o p o s e d a n da p p l i e dt oc l u s t e rs t r u c t u r a lo p t i m i z a t i o np r o b l e m t h ee n e r g yl a n d s c a p eo f c l u s t e r sw a sa l s os t u d i e dw i t hac o n f o r m a t i o n a la n a l y s i sm e t h o d i nt h i sd i s s e r t a t i o n ，b a s i ck n o w l e d g e s ，m e t h o d sa n ds i g n i f i c a n c eo f c l u s t e rs t u d i e s w e r ei n t r o d u c e d ，a n dt h e g l o b a lo p t i m i z a t i o nm e t h o d se m p l o y e d i ns t r u c t u r a l o p t i m i z a t i o no fa t o m i c o rm o l e c u l a rc l u s t e r sw e r er e v i e w e d t h em a i nw o r k s c o n t a i n e di nt h ed i s s e r t a t i o ni n c l u d e ： 1 b a s e do nt h ei m m u n et h e o r yo fb i o l o g y ，an o v e le v o l u t i o n a r ya l g o r i t h m ， a d a p t i v ei m m u n eo p t i m i z a t i o na l g o r i t h m ( a i o a ) ，w a sp r o p o s e d i na i o a ，d e n s i t y r e g u l a t i o na n di m m u n es e l e c t i o ni sa d o p t e dt oc o n t r o lt h ei n d i v i d u a ld i v e r s i t ya n dt h e c o n v e r g e n c ea d a p t i v e l y b ya p p l y i n gt h ea l g o r i t h mt o t h e o p t i m i z a t i o no ft e s t f u n c t i o n s ，i tw a ss h o w nt h a tt h ea l g o r i t h mi sah i g h l ye f f i c i e n to p t i m i z a t i o nm e t h o d c o m p a r e dw i t ho t h e rs t o c h a s t i co p t i m i z a t i o nm e t h o d s t h ea l g o r i t h mw a sa l s oa p p l i e d t ol e n n a r d j o n e s ( l j ) c l u s t e r s ，a n do p t i m a ls t r u c t u r eu pt ol j 8 0w a sr e p r o d u c e d 2 an o v e la n de f f e c t i v ec l u s t e r s i m i l a r i t yc h e c k i n g m e t h o du s i n gt h e c o n n e c t i v i t yt a b l e ( c t ) w a sp r o p o s e d b e c a u s ec tc o n t a i n s t h e t o p o l o g i c a l i n f o r m a t i o no fac l u s t e r ，c o n f i g u r a t i o n sa td i f f e r e n tf u n n e l so nt h ep o t e n t i a le n e r g y s u r f a c e ( p e s ) s h o wg r e a td i f f e r e n c ei nt h e i rc t s an e wv e r s i o no fa i o aw a s u t i l i z e df o ro p t i m i z a t i o no fl jc l u s t e r su pt ol j i1 0u s i n gt h ec tf o rs i m i l a r i t y c h e c k i n g i tw a sp r o v e dt h a tt h em e t h o di sv e r ye f f i c i e n t ，a n dt h em e t h o di s a l s 0 c a p a b l ef o ro p t i m i z a t i o n so fl a r g e rc l u s t e r s ，e g ，l j 2 0 0 3 a ne n e r g y b a s e dp e r t u r b a t i o na n dan e wi d e ao ft a b o os t r a t e g yw e r ep r o p o s e d f o rs t r u c t u r a lo p t i m i z a t i o na n da p p l i e di nab e n c h m a r kp r o b l e m ，i e ，t h eo p t i m i z a t i o n 中国科学技术大学博士论文 摘要 o f l jc l u s t e r s i tw a sp r o v e dt h a tt h ee n e r g y b a s e dp e r t u r b a t i o ni sm u c hb e t t e rt h a nt h e t r a d i t i o n a lr a n d o mp e r t u r b a t i o nb o t hi nc o n v e r g e n c es p e e da n ds e a r c h i n ga b i l i t yw h e n i ti sc o m b i n e dw i t has i m p l eg r e e d ym e t h o d b yt a b o o i n gt h em o s tw i d e s p r e a df u n n e l i n s t e a do ft h ev i s i t e ds o l u t i o n s ，t h eh i tr a t eo fo t h e rf u n n e l si ss i g n i f i c a n t l yi m p r o v e d g l o b a lm i n i m ao fl jc l u s t e r su pt o2 0 0a t o m sw e r ef o u n dw i t hh i g he f f i c i e n c y 4 ah i g he f f i c i e n tu n b i a s e dg l o b a lo p t i m i z a t i o nm e t h o dc a l l e dd y n a m i cl a t t i c e s e a r c h i n g ( d l s ) w a sp r o p o s e d t h em e t h o ds t a r t sw i t har a n d o m l yg e n e r a t e dl o c a l m i n i m u m ，a n df i n d sb e r e rs o l u t i o nb yac i r c u l a t i o no fc o n s t r u c t i o na n ds e a r c h i n go f t h ed y n a m i cl a t t i c e ( d l ) u n t i lt h eb e t c e r s o l u t i o na p p r o a c h e st h eb e s ts o l u t i o n b e c a u s et h ed lc a ng r e a t l yr e d u c et h es e a r c h i n gs p a c ea n dt h en u m b e ro ft h e t i m e c o n s u m i n gl o c a lm i n i m i z a t i o np r o c e d u r e s ，t h ep r o p o s e dd l sm e t h o dr u n sa t a v e r yh i g he f f i c i e n c y t h ep e r f o r m a n c eo ft h ed l s i si n v e s t i g a t e di nt h eo p t i m i z a t i o n o fl jc l u s t e r su pt o3 0 9a t o m s ，a n dt h es t r u c t u r eo ft h el j 5 0 0i sa l s op r e d i c t e d f u r t h e r m o r e ，t h ei d e ao fd y n a m i cl a t t i c ec a l lb ee a s i l ya d o p t e di nt h eo p t i m i z a t i o no f o t h e rm o l e c u l a ro ra t o m i cc l u s t e r s 5 w i t ht h en e w l yd e v e l o p e dd l sm e t h o d ，p u t a t i v eg l o b a lm i n i m af o ra l l ( c 6 0 ) n c l u s t e r sw i t hu pt on = i 5 0a r el o c a t e d b e c a u s eas i m p l eg r e e d ys t r a t e g yi sa d o p t e d f o rt h eb a s i cf r a m e ，d l sh a sav e r yh i g hc o n v e r g e n c es p e e da n dm a yc o n v e r g ea t v a r i o u sc o n f i g u r a t i o n s s o m en e ws e q u e n c e sa r ed e f i n e db yb o t hc o n f i g u r a t i o n sa n d t h es i z eo ft h eb a s i ct e t r a h e d r o n ac o n f o r m a t i o n a la n a l y s i si sc a r r i e do u tb yc o u n t i n g t h eh i tn u m b e ro fv a r i o u sm o t i f s l e a r yt e t r a h e d r a ls e q u e n c ew a sp r o v e dt ob e d o m i n a n ti nac e r t a i nr a n g eo fc l u s t e rs i z e s ，a l t h o u g ht h es e q u e n c eh a sn op o t e n t i a l e n e r g ya d v a n t a g e t h ec a l c u l a t i o nr e s u l t sa r ea l s oc o n s i s t e n tw i t ht h o s eo fa n n e a l i n g e x p e r i m e n t sa th i g ht e m p e r a t u r e ，b o t hi nm a g i cn u m b e r s a n dh e i g h to f t h ep e a k si nt h e m a s ss p e c t r u m 6 b yu s i n gd l sm e t h o d ，ab e t t e rc o m p r e h e n s i o nt ot h ee n e r g yl a n d s c a p eo f a t o m i co rm o l e c u l a rc l u s t e r sw e r eo b t a i n e df o rm u c hl a r g e rc l u s t e rs i z er = 4 0 0 ) a n e wd e f i n i t i o no fc o n f o r m a t i o n a le n t r o p yw a sp r o p o s e d ，w h i c ha g r e e sw e l lw i t ht h e c o n f o r m a t i o n a l a n a l y s i s r e s u l t so fd l s b yl i m i t i n gt h em a x i m a ln u m b e ro f c h a n g e a b l ea t o m sp e rs t r u c t u r a lt r a n s i t i o n ，t h ec o n c e p to ft e m p e r a t u r ew a ss i m u l a t e d v n l 中国科学技术大学博士论文摘要 t h ec o n f o r m a t i o n a la n a l y s i sr e s u l t sw i t ht e m p e r a t u r er o u g h l ya g r e ew i t ht h er e s u l t so f a n n e a l i n ge x p e r i m e n t sf o r ( c 6 0 ) um o l e c u l a rc l u s t e r s f u r t h e r m o r e ，t h ec a l c u l a t i o n r e s u l t sw i t hc o n s i d e r a t i o no ft e m p e r a t u r ec a ne x p l a i nw h yt h eo p t i m i z a t i o na b i l i t yo f d l si sm u c hb e t t e rt h a nm o s ts t o c h a s t i co p t i m i z a t i o nm e t h o d st h er e l a t i o n s h i po f t h ee n e r g yl a n d s c a p ea n dt h ep o t e n t i a lr a n g ew a sa l s os t u d i e d 中国科学技术大学博士论文 第一章 1 1 引言 第一章综述 在过去的十几年中，纳米科学得到了非常迅猛的发展 1 。目前该领域已经延 伸到物理、化学以及工程领域，并且在基础科学和工程技术领域都得到了非常多 的应用。纳米科学和纳米技术就是把材料的尺寸控制在几个纳米范围内f 比如， 1 - l o o n m ) 。纳米材料是连接单个原子分子与宏观物质之间的桥梁。由于尺寸效应， 跟宏观物质相比，纳米材料有着非常奇异的性质。在纳米材料中，原子或分子团 簇( c l u s t e r ) 占有非常重要的位置，它是纳米科学的基础。团簇是由几个到几十万 个原子或分子通过化学键结合在一起的聚集体。与分子不同，团簇没有固定的尺 寸与成分比例。比如，水分子由一个氧原子及两个氢原子组成，它们之间的键角 是固定的。但在金团簇、银团簇以及水分子团簇中，粒子的数目是任意的，并且 粒子排列方式也是任意的。 团簇的空间大小一般在几到几百a 之间，它具有很大的表体比，正是因为 团簇的尺寸效应使得它具有许多特殊的性质，例如，电子壳层和能带结构并存， 气、液、固的并存和转化，幻数的稳定性和几何非周期性，异常的化学活泼性使 团簇在力学、电学、光电子学、电子学、磁学、化学、催化和生物学方面出现了 许多新的现象。团簇是介于原子与固体材料之间的一种全新的状态，其性质既不 同于单个的原子分子，又不同于体相材料，也不能用二者性质的简单外推或内插 得到。人们把团簇看成介于气态和凝固态之间的“第五态”，可以认为团簇是 物质由原子分子向大块物质转变的特殊相，因此团簇还被形象地比喻为连接微观 与宏观物质的桥梁。团簇的微观结构特点和奇异的物理化学性质可用于制造和发 展具有特殊性能的新材料。这些性质包括团簇的电导、红外吸收系数和磁化率的 异常变化，超导临界温度的提高，可用于研制新材料如敏感元件、磁性液体、高 密度磁存储介质、微波及光吸收材料、半导体材料、超导材料等。 团簇研究的基本问题是弄清团簇如何由原子、分子逐步发展而成，咀及随着 这种发展，团簇的结构和性质如何变化。团簇的研究兴起于2 0 世纪7 0 年代。 2 0 世纪8 0 年代，随着实验条件的改善，团簇研究得到了迅速发展，其中最为 中国科学技术大学博士论文 第一章 突出的是，1 9 8 4 年美国加州大学伯克利分校的k n i g h t 教授使用超声膨胀方法得 到了n a 金属团簇。有趣的是，他发现n a 金属团簇具有显著的幻数结构，而且 这些幻数结构与其价电子结构的满壳分布相对应。之后，c 6 0 笼形团簇以及碳纳 米管团簇的发现更是引起了科学界的轰动。同时各种不同团簇体系奇异的电、磁、 光及化学反应特性相继发现，引起了凝聚态物理、原子分子物理、材料科学、化 学乃至核物理学界的共同关注。这种飞速发展的态势一方面得益于实验技术的不 断提高，使得产生不同尺寸的团簇并研究其物理化学性质变得方便，另一方面， 计算机和计算技术的迅速发展，对团簇结构和性质从第一性原理出发进行从头计 算( a bi n i t i o ) ，分子动力学( m o l e c u l a rd y n a m i c s ) 和分子力学( m o l e c u l a rm e c h a n i c s ) 模拟成为可能。 团簇的稳定结构是化学家们关注的一个重要课题，因为团簇的性质与它的结 构之间存在着非常密切的联系。具有特殊稳定性的团簇在结构上也表现出了完美 的对称性，如l e n n a r d j o n e s ( l j ) 原子团簇的幻数结构是具有五重对称性的闭壳 二十面体。在以前的研究中，一般根据人工制备团簇的电子衍射数据来预测它的 结构，但用它来确定团簇的最优结构仍具有一定的困难，因为实验制备的团簇一 般为各种尺寸下许多种构型的混合体。因此确定团簇的结构通常需要采用实验结 果和理论模型预测相结合的方法。 要从理论计算上决定一个团簇结构的稳定性，首先要引用一种可靠的势函数 来描述团簇原子问的相互作用。近年来，己发展了一系列精确度不同的相互作用 势，如第一原理多体势 2 1 应用广泛的m o r s e 势【3 】，t e r s o f f 势 4 , 5 1 ，e a m 势nr g l 势【7 】，g u p t a 势t 8 1 ，l j l 2 6 对势9 1 等。 有了团簇中各原子之间相互作用势以后，确定该团簇的最稳定结构的能量实 质上就成为一个多变量函数求极值的优化问题。全局优化算法是研究分子结构的 常用方法，由于分子的天然结构通常与该分子势能曲面( p o t e n t i a le n e r g ys u r f a c e ， p e s ) 上的最低能量结构相关，因此分子结构优化问题的实质是选择一种势能函数 作为全局优化算法的评价函数，利用全局优化算法在分子体系的势能曲而上搜索 全局最低能量。由于分子的p e s 上存在大量的局部极值( 1 0 c a lm i n i m a ) ，分子结构 优化是一类非常困难的全局优化问题。用于描述实际分子体系( 如纳米团簇、 蛋白质等) 的参数很多，即使是采用最简单的两体势描述原子间相互作用的团簇， 中国科学技术大学博士论文第一章 它的全局优化问题也属于n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 困难问题。n p i h 7 题是 指找不到多项式时间算法的问题，即问题的时间复杂度与参数个数呈指数增长关 系】。因此在团簇结构优化的研究中必需发展高效的全局优化算法。 本综述主要总结了应用于团簇结构优化的全局优化算法以及它的进展，并对 几种感兴趣的团簇的研究现状进行了介绍。 1 2 团簇的构型优化方法 近年来，l j 原子团簇的优化问题受到团簇理论研究及计算科学界的普遍关 注。l j 势函数只考虑原子间的范德华力，其势函数形式非常简单，为仅与原子 间距离有关的1 2 6 对势： v ( r )。s 窆窆( ( 吖。) ”一( 叫。) 6 1 1 ) l 、 7 式中表示各对原子( f ，) 间的距离，可以通过原子坐标直接得到。s 和2 1 6 口分别 是二聚体势阱深( 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 ) ，此取= 口 = 1 的简化形式。l j 势可以用于精确描述一些真实的物理体系，如低温下的稀有 气体团簇。但我们更感兴趣的是l j 势函数一般用来测试算法的优化性能。l j 原 子团簇结构优化问题的模型虽然简单，但其对于优化算法而言仍是个巨大的挑 战，因为其p e s 极其粗糙且具有大量的局部极值。实验方法和大量的模拟方法已 给出t l j 原于团簇的部分最低能量结构，可以用于评价算法的优化能力。剑桥 大学的w a l e s 课题组建立的剑桥团簇数据库 1 2 】，收录了目前已知的l j 团簇最优结 构的能量。 对于团簇尺寸较小的l j 团簇，全局最优结构大部分是二十面体( i c o s a h e d r a l 、 构型。非二十面体最优结构包括：l j 3 8 的截角八面体( t r u n c a t e do c t a h e d r o n ) 构型、 l j 7 5 7 7 ，1 0 2 1 0 4 的十面体( m a r k sd e c a h e d r o n ) 构型以及l j 9 8 的四面体f l e a r y t e t r a h e d r o n ) 1 1 3 1 构型( 如图l - l 所示) 。在这些非二十面体最优结构中，团簇的势 能曲面上有范围很宽的二十面体构型的能量陷阱，并且与最优结构所在位置的距 离很远，所以优化很容易陷入二十面体的局部极优，使得它们的最优结构很难找 到。因此在评价全局优化算法时，一般认为只有能成功优化得到非二十而体结构 中国科学技术大学博士论文第一章 的优化算法才具有实际的应用价值。 l j 3 8 t r u n c a t e do c t a h e d r o n l j 7 5l j 9 8l 儿4 7 m a r k sd e c a h e d r o n l e a r 3 , t e t r a h e d r o n i c o s a h e d r o n f i g1 - 1m o t i f so f t h eg l o b a lm i n i m ao f l jc l u s t e r sw i t ht y p i c a lp a c k i n g 根据优化算法是否利用了待优化问题的已有知识可将优化方法分为有偏 ( b i a s e d ) 方法和无偏( u n b i a s e d ) 优化算法。无偏优化算法在优化过程中不需要利用 待优化团簇体系的结构知识，这类方法能够用于不同团簇的结构优化或者其它类 型分子的结构优化问题。而有偏方法则能针对特定的构型减小优化难度。 1 2 1 无偏全局优化方法 团簇优化问题属于n p 困难问题，团簇势能曲面上的局部极值与团簇的尺寸 呈指数增长，因此找到势能曲面上的全局最优结构非常困难，需要发展高效的全 局优化方法。此外，由于团簇优化问题的搜索空间是连续的，而且该类问题待优 化的参数特别多，一般需要结合一个高效的局部最小化方法以得到精确的能量 值。团簇优化问题中使用比较多的是有限记忆共轭梯度f l1 3 f g s ) i t 4 方法。比较 成功的全局优化算法都结合了局部最小化方法，从而能更多地关注全局信息。下 面将要介绍的无偏全局优化方法都结合了局部最小化方法。 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) ：模拟退火算法起源于对固体退火 过程的模拟【l j ，加温时，国体内部粒子随温度升高变为无序状，内能增大，而 徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态， 内能减为最小。在模拟退火算法中，采用模拟的退火进度表玎提供退火过程的 温度，女为迭代次数，随着k 的增加退火温度磁渐降低。s a 包括如下过程：( 1 ) 初 始化，随机产生初始结构s o ，并且初始体系温度为t = t o ：( 2 ) 根据当前温度对当 中国科学技术大学博士论文第一章 前结构进行微扰产生一个新的结构，并根据m e t r o p o l i s 准则判断是否接受此新结 构；( 3 ) 降低温度，根据迭代次数k 重新计算当前温度r = 玎，然后重复步骤( 2 ) ； 重复循环直到温度降到终止温度，模拟退火算法停止，选择模拟过程得到的最优 的解作为近似解。 作为求解全局优化问题的随机搜索算法，s a 采用了大范围的粗略搜索与局 部的精细搜索相结合的搜索策略。当温度较高时，随机产生的试探点的散布范围 较大，并以较大的概率接受使目标函数变差的试探点，从而实现大范围搜索。随 着温度逐渐下降，随机产生的试探点的散布范围逐渐减小，接受目标函数值变差 的试探点的概率也逐渐减小，从而使搜索过程逐步变为局部探索。s a 求得的解 与初始解的状态无关，具有渐近收敛性，己在理论上被证明是一种以概率收敛于 全局最优解的全局优化算法。 由于s a 来源于固体退火原理，其对于团簇构型优化问题有着天然的优势。 在不使用局部极小化方法的情况下，s a 在全局优化算法中的局部优化能力最强， 能够得到能量比较低的结构。但s a 的缺点同样源于其优点，即在温度较低时算 法过分注重于局部最优能力而容易陷入局部极值无法跳出。对于团簇优化问题， 团簇的势能面过于复杂，当优化陷入局部极优时，要跳出局部极值需要越过很高 的能垒，而此时的退火温度往往不足以提供跃出能量陷阱体系所需的自由能。因 此常规的模拟退火算法及其变体一般只能用于优化较小的团簇 17 - 9 】。x u e l 2 0 1 发展 了一种改进的并行s a 算法，并首次发现t l j 6 5 与l j 6 6 的全局最优结构。该算法 结合了局部极小化方法，从而s a 可以使用较高的退火温度以更注重于全局信息。 基于特快速退火和群体进化策略的快速退火演化算法( f a e a ) 在结合了局部极 小化方法后也成功优化得到t l j 2 7 5 的所有己知最优结构叫。5 ( 寸f a e a 进行并行 化以后优化能力进一步得到提高，优化得到了l j l l 6 以下的所有已知最优结构 f 2 2 】。 b a s i n h o p p i n g 算法：b a s i n h o p p i n g 算法本质上是m o n f ec a r l o 方法加上能量 极小化。该方法由w a l e s 等在1 9 9 7 年提出，是目前应用最广泛的结构优化方法。 在该方法中，每一次结构改变以后都进行局部能量极小化以得到相应的局部极 值，算法操作的对象为这些局部极值。因此势能曲面变成了一系列能量平台，每 一个平台对应于势能曲面上的一个势阱( 图1 2 ) 。这种变换不但消除了势能面 中国科学技术大学博士论文第一章 上的所有过渡态，而且由于没有了能垒，体系可以在平台边界自由通过，因此加 速了动态跃迁，使优化变得容易。 f i gl 2i l l u s t r a t i o no f t h ee f f e c t so f t h eb a s i n - h o p p i n gp o t e n t i a le n e r g yt r a n s f o r m a t i o n b a s i n h o p p i n g 方法成功优化得到了l j l l 0 以下的所有已知最优结构，其中 l j 6 9 ，l j 7 5 7 8 ，l j l 0 3 1 0 4 和l j l 0 7 为首次发现。值得一提的是，1 9 9 9 年l e a r y 2 4 , 2 5 】 用b a s i n h o p p i n g 算法的变体首次优化得到了l j 9 8 的具体特殊四面体构型的全局 最优结构( 见图1 1 ) 。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) ：g a 是一种基于对生物界自然选择和自 然遗传机制的模拟来解决实际问题的高度并行、随机、自适应搜索方法。它使用 群体搜索策略，群体中的个体之间具有信息交流，搜索不依赖于梯度，适用于处 理传统搜索方法难于解决的复杂非线性问题。这些特点使得g a 可以用于大参数 空间的优化问题，同时可以避免陷入局部极优，因此它广泛应用于结构优化问题。 遗传算法的基本过程为一个循环迭代，包括群体的初始化，群体的评价，基于评 价值的选择利用，以及杂交、变异开发下代。 在团簇的结构优化中，h a r t k e 2 6 1 在九十年代早期首次用g a 优化了小尺寸硅 团簇。但在g a 中，基因串为团簇中原子坐标的编码，因而基于基因串的杂交操 作相当于对两个父代团簇进行非常混乱的混合，所得到的子代与其父代在构型上 基本上无相似性与继承性可言。从实际效果上讲，这种杂交操作蜕化为相当混乱 的变异。因此传统的遗传算法优化能力有限，只能用于优化较小的团簇 2 7 , 2 8 。 d e a v e n , n h o l 2 9 1 对传统g a 的杂交操作做了改进，首次提出了针对分子结构优 化的显型杂交策略。j o h n s t o n f ”1 在其遗传算法综述中给出t d e a v e n h o 显型杂交 中国科学技术大学博士论文第一章 策略的示意图( 如图1 3 所示) 。在该方法中，不是在基因层面进行杂交，而是 直接对两个团簇的部分结构进行交换。此外，他们还在改进的g a 结合了局部 优化方法，从而克服了g a 局部优化能力弱的缺点。使用这种基于显型杂交的g a d e a v e n 等叫优化得到了原子数小于1 0 0 的l j 原子团簇的大部分最低能量结构，其 中有些最优结构是首次报导。 f i gi 一3s c h e m a t i cr e p r e s e n t a t i o no f t h ed e a v e n h oc u ta n ds p l i c e c r o s s o v e ro p e r a t i o n h a r t k e 【”1 在d e a v e n h o 的显型g a 的基础上，对优化中得到的团簇结构作平面 投影，根据投影图来区别团簇中的构型。他还引入了生物学中小生境( n i c h e ) 的概 念，即在总的群体中还有具有相似构型的小生境。通过限定处于同- - , j , 生境中相 似个体的数量，群体的多样性得到了保证。该方法优化得到了l j l5 0 以下除l j 9 8 的新构型以外的所有团簇的最优结构，并且对那些非二十面最优结构的优化效率 比较高。 构象空间退火方法( c o n f o r m a t i o n a ls p a c ea n n e a l i n g ，c s a ) ：l e e 等结合了 m o n t ec a r l o a d 上局部极小化方法，g a 的群体策略，以及s a 的退火思想提出了一 种非常有效的杂交全局优化方法，叫做构象空间退火方法( c s a ) ，并成功应用于 蛋白质折叠问题的研究 3 4 , 3 5 】。图1 4 给出t c s a 搜索过程的示意图。首先，c s a 只考虑了局部极值的相空间，所有的构型都经过局部最小化处理( 如图中的叉号 所示) 。其次，受到遗传算法的启发，优化中采用了群体进化策略。c s a 首先随 机初始化产生一个比较大的基因库，然后从库中随机选取一些个体作为初始群体 中国科学技术大学博士论文第章 ( 图1 4 a 中所给出的例子的群体大小为4 ) 。每一个个体周围有一个半径为d c 。的 构象空间，表示为图中的实线圆。然后对群体中的个体进行微扰，得到新的构象 ( 表示为图中的加号) ，如果d 位于群体中个体a 的构象空间内并且能量比a 低， 那么个体a 就转移到a ，该个体的构象空间也由实线圆变为点线圆。最后结合了 s a 的思想，d 。随着迭代次数的增加逐渐减小，从而构象空间也逐渐减小，最后 收敛为图1 4 b 中的几个构象。d 。相当于s a 中的温度控制，可以通过控制d 。来 调整群体多样性和收敛数度。 矧 ( b ) c o f i gi - 4s c h e m a t i cf i g u r es h o w i n gt h es e a r c hp r o c e d u r eo f c s at h eb o x e sr e p r e s e n tt h ei d e n t i c a l p h a s es p a c e c s a 也被成功的应用于l j 团簇的结构优化问题，结果成功的优化出l j 2 0 1 以 内的所有己知最优结构团簇，并有着很高的成功率l ” 。 势能曲面变形方法；描述分子体系的势能函数曲面比较粗糙，其面上存在者 大量的局部极优，因此优化起来非常困难。该类方法的基本思想是用数学方法对 势能函数进行变形处理以减少局部极值的数量。比较有代表性的势能曲面变形方 法有d e m 方法( d i f f u s i o ne q u a t i o nm e t h o d ) 叽3 ”，d s m 方法( d i s t a n c es c a l i n g m e t h o d ) 阻4 ”，以及t r u s t 方法( t e r m i n a lr e p e l l e ru n c o n s t r a i n e ds u b e n e r g y t u n n e l i n g