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

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

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

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

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

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

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