改進(jìn)的模擬退火算法用于團簇結(jié)構(gòu)優(yōu)化

劉鳳萍

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0 引言

團簇是由幾個乃至上千個原子、分子或離子通過物理或化學(xué)結(jié)合力組成的相對穩(wěn)定的微觀或亞微觀聚集體，其物理和化學(xué)性質(zhì)與其結(jié)構(gòu)息息相關(guān)，不同的原子數(shù)目所能形成的穩(wěn)定結(jié)構(gòu)也不相同，因此研究不同原子數(shù)目的團簇的穩(wěn)態(tài)結(jié)構(gòu)是當(dāng)今物理學(xué)和化學(xué)中的一個重要的前沿課題。應(yīng)用儀器通過實驗實現(xiàn)團簇穩(wěn)態(tài)結(jié)構(gòu)的測定是十分困難而又不切實際的，目前為止，用的較為廣泛的一種辦法是：找到一種能夠表示團簇能量與其空間結(jié)構(gòu)關(guān)系的能量函數(shù)，進(jìn)而使用搜索算法搜索該能量函數(shù)的最小值點。該方法叫做從頭預(yù)測方法，其原理是基于熱物理理論：團簇的最穩(wěn)定結(jié)構(gòu)即為其能量最低時候的結(jié)構(gòu)。

用于解決團簇結(jié)構(gòu)優(yōu)化問題的算法主要有遺傳算法[1-3]、模擬退火算法[4]和粒子群算法[5-6]等。隨原子數(shù)目增加，團簇的空間結(jié)構(gòu)自由度也迅速增長，傳統(tǒng)搜索算法對團簇結(jié)構(gòu)的優(yōu)化效果也迅速減弱。對傳統(tǒng)的優(yōu)化算法進(jìn)行改進(jìn)，是更好的選擇。因模擬退火算法具有計算過程簡單、魯棒性強等優(yōu)點，故本文在模擬退火算法的基礎(chǔ)上進(jìn)行算法改進(jìn)。

1 能量模型

本文選擇蘭納瓊斯（Lennard-Jones）勢能公式來表示團簇能量與其空間結(jié)構(gòu)之間的關(guān)系。

蘭納瓊斯勢是數(shù)學(xué)家John Lennard-Jones在1924年提出的，主要是用于模擬兩個電中性的分子或原子間相互作用勢能的數(shù)學(xué)模型，其表示見公式（1）。

上述公式中：ε表示勢能阱的深度，σ表示互相作用的勢能恰為零時的兩分子或原子間的距離，為了便于實驗結(jié)果的對比，本文的實驗中ε、σ兩個參數(shù)均參考文獻(xiàn)[7]，設(shè)置為1。rij表示兩體間的歐幾里得度量，其計算公式如下（2）：

含N個原子的團簇的蘭納瓊斯總勢能為：

2 搜索算法

2.1基本模擬退火算法

模擬退火算法思想受啟發(fā)于固體的退火過程：溫度很高的固體，其內(nèi)部粒子都在做高速無序運動，具有較大的內(nèi)能。當(dāng)固體的溫度逐漸降低時，其內(nèi)能也逐漸減小，內(nèi)部粒子逐漸趨于有序狀態(tài)。直到固體溫度到達(dá)常溫時，其內(nèi)能將至最低，這時內(nèi)部粒子最為穩(wěn)定。這恰似求解優(yōu)化問題時，搜索目標(biāo)函數(shù)最優(yōu)解的過程。

模擬退火算法用于求解優(yōu)化問題時，先從初始溫度出發(fā)，隨機生成初始解x，并計算其對應(yīng)的目標(biāo)函數(shù)值f(x)，溫度每降低一次產(chǎn)生一個新解，并計算其對應(yīng)的目標(biāo)函數(shù)值f)。當(dāng)新解優(yōu)于原解的時候接受新解，否則根據(jù)Metropolis準(zhǔn)則判斷是否接受新解。Metropolis準(zhǔn)則定義為：首先計算新解對應(yīng)的目標(biāo)函數(shù)值與原解目標(biāo)函數(shù)值的差值?E，如下公式（4），若?E＞0，則接受新解；否則按概率P接受新解，概率P的計算見公式（5）。

算法流程如下：

Step1：設(shè)置初始溫度t，終止溫度tf，退火速度speed，隨機生成初始解x，計算目標(biāo)函數(shù)f(x)；

Step2：若t＞tf，擾動產(chǎn)生新的解x，，計算對應(yīng)目標(biāo)函數(shù)f(x，)，否則終止算法；

Step3：根據(jù)Metropolis準(zhǔn)則判斷新解是否被接受：如果接受則令變。t=t*speed，跳到Step2。

2.2基于種子策略的模擬退火算法的提出

（1）種子策略的提出

基本的SA算法具有較強的跳出局部最優(yōu)解的能力，但是當(dāng)搜索空間較大時，因其產(chǎn)生的解在多樣性上的局限性，很難求解出全局最優(yōu)解。針對該問題，提出一次性產(chǎn)生多個初始解，分別對這些解進(jìn)行適應(yīng)度計算后，對產(chǎn)生的每個初始解進(jìn)行擾動以產(chǎn)生一批新解，進(jìn)而通過Metropolis準(zhǔn)則判斷是否接受新解，循環(huán)直至到達(dá)終止溫度。

基本SA算法用于求解原子數(shù)目較少的團簇具有較好的效果，但是隨著原子數(shù)目增多，原子的空間結(jié)構(gòu)自由度呈指數(shù)增長，基本SA算法的效果大大降低。考慮這樣一個現(xiàn)象：當(dāng)某個含有N(其中N＞1)個原子的團簇W處于其能量最低狀態(tài)，也就是其穩(wěn)定結(jié)構(gòu)時，假設(shè)此時W中各原子的空間坐標(biāo)為(X1,X2,…,Xi,…XN)，其中Xi表示第i個原子的三維坐標(biāo)，即可表示為此時我們再往該團簇W中增加一個原子，該原子的坐標(biāo)在區(qū)域范圍內(nèi)隨機選取，設(shè)為產(chǎn)生一個新的團簇W，，此時新的團簇W，未必能達(dá)到其穩(wěn)定狀態(tài)，但是一般情況下，這樣產(chǎn)生的團簇的能量會比隨機生成N+1個原子的三維坐標(biāo)組合在一起的能量小，因此，本文采用了參考已求得其穩(wěn)定狀態(tài)的原子數(shù)相對少的團簇的空間結(jié)構(gòu)，初始化所求的原子數(shù)相對多的團簇的空間結(jié)構(gòu)，進(jìn)而再通過模擬退火算法進(jìn)行結(jié)構(gòu)優(yōu)化的策略，此種策略稱為種子策略。

（2）算法流程

Step1：設(shè)置初始溫度t，終止溫度tf，退火速度speed，根據(jù)種子策略生成p個初始解x1,x2,…,xp，并計算各個解對應(yīng)的目標(biāo)函數(shù)

Step2：若t＞tf，擾動產(chǎn)生新的解，計算對應(yīng)目標(biāo)函數(shù)，否則終止算法；

Step3：根據(jù)Metropolis準(zhǔn)則判斷新解是否被接受，t=t*speed，跳到 Step2。

3 實驗結(jié)果與分析

3.1參數(shù)設(shè)置

為檢驗提出的SS-SA算法對解決團簇結(jié)構(gòu)優(yōu)化問題的效果，選擇原子數(shù)在2到14之間的團簇的Len?nard-Jones勢能進(jìn)行測試，并與基本模擬退火算法進(jìn)行效果對比，進(jìn)行試驗的兩個算法參數(shù)設(shè)置見下表1，其中t表示初始溫度，tf表示終止溫度，speed表示降溫速度。

表1 SA算法和SS-SA算法的參數(shù)設(shè)置

3.2實驗結(jié)果

SS-SA算法和SA算法對原子數(shù)為3到14的團簇結(jié)構(gòu)優(yōu)化的結(jié)果如表2，對于原子數(shù)相同的團簇，分別列出了SA算法和SS-SA算法對其Lennard-Jones勢能函數(shù)上獨立運行20次所得優(yōu)化后勢能的最優(yōu)值、平均值和標(biāo)準(zhǔn)差。表2中所展示的團簇對應(yīng)的Lennard-Jones勢能的理想值參考于文獻(xiàn)[7]。

表2 SA算法和SS-SA算法對團簇結(jié)構(gòu)的優(yōu)化結(jié)果

SS-SA算法和SA算法分別對包含不同原子數(shù)的團簇單獨進(jìn)行20次優(yōu)化，可求得的團簇最低勢能與理想勢能之間存在一定誤差，誤差曲線見圖1；20次單獨優(yōu)化過程中，SS-SA算法和SA算法對原子數(shù)目不同的團簇優(yōu)化的結(jié)果的平均值與理想勢能也存在一定誤差，誤差曲線見圖2。

3.3結(jié)果分析

根據(jù)表2可知，當(dāng)團簇的原子數(shù)目為3到5時，SA算法和SS-SA算法運行20次都可求出團簇的最穩(wěn)定結(jié)構(gòu)，而參考平均值和標(biāo)準(zhǔn)差，可知SS-SA算法穩(wěn)定性強于SA算法；當(dāng)原子數(shù)為6到10的時候，SA算法所能搜索到的對應(yīng)團簇的最穩(wěn)定結(jié)構(gòu)已和理想值有所差距，但是SS-SA算法可求得團簇的最穩(wěn)定結(jié)構(gòu)；當(dāng)原子數(shù)為11到14時，SA算法所求得的其最優(yōu)結(jié)構(gòu)已和其理想結(jié)構(gòu)相去甚遠(yuǎn)，而此時SS-SA所能求得的最優(yōu)值與理想最優(yōu)值誤差相對較小，認(rèn)為此時可求得團簇的近似穩(wěn)定結(jié)構(gòu)，再參考均值和方差可知其較為穩(wěn)定。綜上，對原子數(shù)在3到14之間的團簇進(jìn)行結(jié)構(gòu)優(yōu)化時，本文提出的SS-SA算法，優(yōu)化能力強于SA算法。

圖1 SA和SS-SA算法所求團簇能量最優(yōu)值與理想值的誤差曲線

圖2 SA和SS-SA算法所求團簇能量平均值與理想值的誤差曲線

4 結(jié)語

為了解決團簇結(jié)構(gòu)優(yōu)化問題，本文所提出的在基本模擬退火算法的基礎(chǔ)上，增加了種子策略的算法——基于種子策略的模擬退火算法（SS-SA），提高了基本SA的算法性能。經(jīng)過實驗驗證：用于解決團簇結(jié)構(gòu)優(yōu)化問題時，SS-SA算法能求得原子數(shù)目為3到10的團簇的穩(wěn)定結(jié)構(gòu)，對原子數(shù)目為11到14的團簇，能求得其近似最優(yōu)結(jié)構(gòu)。