原子團簇結(jié)構(gòu)預(yù)測的現(xiàn)實途徑—高性能啟發(fā)式算法.pdf

1、原子(或分子)團簇的幾何結(jié)構(gòu)是其最基本的特征之一,直接影響著團簇的其它物理化學(xué)性質(zhì)。因此,預(yù)測團簇的基態(tài)結(jié)構(gòu)常常是團簇研究的第一步。然而,由于團簇構(gòu)型空間隨團簇大小呈指數(shù)型增長,該問題在理論上被證明是NP-hard問題。
　　對于NP-hard問題,目前計算機科學(xué)界普遍認(rèn)為不存在多項式時間復(fù)雜度的精確算法。在這種背景下,國內(nèi)外學(xué)者提出了大量的啟發(fā)式算法。啟發(fā)式算法雖然不能保證獲得問題的最優(yōu)解,但它能在合理的計算時間內(nèi)給出滿足一定要

2、求的次優(yōu)解,從而成為求解NP-hard問題的現(xiàn)實途徑。
　　本文針對以下三種團簇設(shè)計了四個啟發(fā)式算法,即Lennard-Jones團簇,多體勢能建模的金屬團簇及二元合金團簇。Lennard-Jones團簇由對勢能(pair potential)建模;由于在表述及計算上的簡單性,它已成為團簇優(yōu)化算法的試金石;另一方面,由于在勢能形式上過于簡單,它只能用于建模少數(shù)惰性氣體團簇。對于更復(fù)雜的團簇,如金屬團簇及合金團簇,多體勢能可以更精確

3、地描述原子間的相互作用,從而被物理化學(xué)家廣泛采用。在目前的研究中,我們采用了Gupta多體勢能給金屬團簇與合金團簇建模。
　　對于Lennard-Jones團簇的優(yōu)化,我們提出了一個混合的啟發(fā)式算法,即含內(nèi)部算子及兩階段局部下降的動態(tài)格子搜索算法。在該算法的前一階段,內(nèi)部算子將若干能量較高的表面原子移入團簇的內(nèi)部,從而逐漸地降低團簇的勢能并使其構(gòu)型有序;并且,兩階段局部下降算法通過利用一個修改的勢能模型把搜索過程引入有前途的構(gòu)型區(qū)

4、域,極大地提高了算法的成功率。在算法的后一階段,一個動態(tài)格子搜索算法對團簇表面的原子進行優(yōu)化,進一步降低了團簇的勢能。算法在N＜680范圍內(nèi)的團簇上進行了測試。計算結(jié)果表明,當(dāng)前算法在計算效率上明顯優(yōu)于文獻中已有的算法;而且,對于LJ533、LJ536這兩個算例,當(dāng)前算法改進了先前的最好結(jié)果。此外,為了強調(diào)搜索的無偏性,提出了該算法的一個變種;計算結(jié)果表明了它的有效性。
　　對于Gupta勢能描述的金屬團簇,提出了一個改進的動態(tài)格

5、子搜索算法。在先前的文獻中,動態(tài)格子搜索算法被用于搜索Ag原子團簇的最低能量結(jié)構(gòu),其中單個原子的能量使用了傳統(tǒng)的定義。然而,計算結(jié)果表明,這種動態(tài)格子搜索算法的性能不夠理想。為了使動態(tài)格子搜索算法更好地應(yīng)用于金屬團簇,我們?yōu)閳F簇中單個原子的勢能提出了一種新的定義,并對動態(tài)格子搜索算法進行了改進,得到了一種改進的動態(tài)格子搜索算法。計算結(jié)果表明,改進的動態(tài)格子搜索算法其性能優(yōu)于先前的動態(tài)格子搜索算法,而且能為大量的金屬團簇找到新的最低能量構(gòu)

6、型。
　　二元合金團簇由兩類金屬原子構(gòu)成,相應(yīng)的結(jié)構(gòu)優(yōu)化問題涉及到連續(xù)優(yōu)化和組合優(yōu)化,其中連續(xù)優(yōu)化目的在于為團簇找到最優(yōu)的幾何構(gòu)型,而組合優(yōu)化目的在于為兩類原子找到最優(yōu)的排布。針對該問題的特征,我們提出了一種啟發(fā)式優(yōu)化算法,其中三種優(yōu)化操作被聯(lián)合地使用,即有啟發(fā)式擾動的單調(diào)跳坑算法(MBH),表面優(yōu)化算子,迭代的局部搜索算法(ILS)。通過對三種合金團簇進行優(yōu)化,本算法找到了11個新的最低能量構(gòu)型,并且,對于剩下的團簇證實了先前的