帶有停滯檢測(cè)的蟻群算法在2D HP格點(diǎn)模型中的應(yīng)用

劉　羽　熊壬浩

1(桂林理工大學(xué)機(jī)械與控制工程學(xué)院　廣西 桂林 541004)

2(桂林理工大學(xué)信息科學(xué)與工程學(xué)院　廣西 桂林 541004)

?

帶有停滯檢測(cè)的蟻群算法在2D HP格點(diǎn)模型中的應(yīng)用

劉羽1熊壬浩2

1(桂林理工大學(xué)機(jī)械與控制工程學(xué)院廣西 桂林 541004)

2(桂林理工大學(xué)信息科學(xué)與工程學(xué)院廣西 桂林 541004)

摘要為了提高蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測(cè)的求解效率，針對(duì)2D HP格點(diǎn)模型，研究蟻群ACO(Ant Colony Optimization)算法在該問(wèn)題上的應(yīng)用。采用四元組表示絕對(duì)的折疊方向，并建立構(gòu)象和解的一一對(duì)應(yīng)關(guān)系。通過(guò)實(shí)驗(yàn)對(duì)算法各階段的常用策略、方法進(jìn)行比較分析。為了防止搜索陷入停滯，引入位置信息素停滯比和序列信息素停滯比兩個(gè)參數(shù)，使用一種新的停滯檢測(cè)機(jī)制。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法在保證預(yù)測(cè)質(zhì)量的前提下，顯著地提升了收斂速度。

關(guān)鍵詞HP模型蛋白質(zhì)折疊蟻群算法停滯檢測(cè)遺傳算法

APPLICATION OF ANT COLONY OPTIMISATION ALGORITHM WITH STAGNATION DETECTION IN 2D HP LATTICE MODEL

Liu Yu1Xiong Renhao2

1(School of Mechanical and Control Engineering,Guilin University of Technology,Guilin 541004,Guangxi,China)2(School of Information Science and Engineering,Guilin University of Technology,Guilin 541004,Guangxi,China)

AbstractAiming at 2D HP lattice model we studied the application of ant colony optimisation algorithm on protein folding structure prediction in order to improve the efficiency of its solution. We used the quadruple to express absolute folding direction, and established the one-to-one correspondence between conformation and solution. Through experiment we made the comparative analyses on common strategies and methods in each stage of the algorithm. To prevent the search from going to stagnation, we introduced two parameters, the position pheromone stagnation ratio and the sequence pheromone stagnation ratio, and applied a new stagnation detection mechanism as well. Experimental results showed that the improved algorithm remarkably accelerated the convergence speed on the premise of ensuring prediction quality.

KeywordsHP modelProtein foldingAnt colony optimisationStagnation detectionGenetic algorithm

0引言

蛋白質(zhì)是一種復(fù)雜的有機(jī)化合物，是由氨基酸經(jīng)脫水縮合反應(yīng)形成多肽鏈，然后在空間進(jìn)行折疊后形成的。蛋白質(zhì)是細(xì)胞的基本構(gòu)成物質(zhì)，是生命的物質(zhì)基礎(chǔ)，在生物細(xì)胞中起著關(guān)鍵的生物和化學(xué)作用。蛋白質(zhì)折疊問(wèn)題的研究在醫(yī)學(xué)及生物工程等領(lǐng)域具有重大的科學(xué)價(jià)值和實(shí)用價(jià)值，其規(guī)律尚未被完全揭示。目前蛋白質(zhì)折疊結(jié)構(gòu)研究的主要方法包括實(shí)驗(yàn)方法以及理論預(yù)測(cè)兩類。X射線晶體學(xué)方法等生物化學(xué)實(shí)驗(yàn)方法對(duì)樣本的要求高、耗資大、周期長(zhǎng)，人們逐漸將注意力轉(zhuǎn)移到理論預(yù)測(cè)方法上來(lái)。最新研究進(jìn)展表明，一些小型蛋白質(zhì)的精確折疊結(jié)構(gòu)已使用計(jì)算機(jī)模擬得出[8]。如何從理論上建立相互作用模型是蛋白質(zhì)折疊理論的核心問(wèn)題。1989年Dill等提出的HP格點(diǎn)模型在內(nèi)的簡(jiǎn)化模型兼顧了折疊過(guò)程的物理機(jī)制以及計(jì)算機(jī)的計(jì)算能力，從而受到廣泛認(rèn)可。

HP格點(diǎn)模型上的預(yù)測(cè)算法主要包括進(jìn)化算法和蒙特卡羅算法兩類?；诿商乜_算法的預(yù)測(cè)算法應(yīng)用廣泛，但收斂速度較慢。2001年Liang等將遺傳算法引入蒙特卡羅算法，取得了一定效果。1996年Dorigo等提出了ACO算法，該算法成功應(yīng)用于旅行商問(wèn)題、車輛調(diào)度等問(wèn)題。隨后Shmygelska[4,7]等將ACO算法應(yīng)用于HP格點(diǎn)模型，取得了較好的效果。

目前已有較多文獻(xiàn)對(duì)HP格點(diǎn)模型上的ACO算法提出了進(jìn)一步改進(jìn)。例如，文獻(xiàn)[2]用PERM評(píng)價(jià)構(gòu)型好壞的標(biāo)準(zhǔn)作為蟻群更新時(shí)的跡，同時(shí)采用EO算法進(jìn)行局部搜索；文獻(xiàn)[5,7]分別在算法的局部搜索階段采用了牽引移動(dòng)的方法和長(zhǎng)距離移動(dòng)的方法；文獻(xiàn)[3]提出了一種先用遺傳算法生成信息素分布，再利用蟻群算法求優(yōu)化解的新的混合算法；文獻(xiàn)[4]引入了最大-最小蟻群系統(tǒng)中的信息素平滑機(jī)制等。這些改進(jìn)涉及ACO算法的各個(gè)階段，效果不一，但少有文獻(xiàn)對(duì)相關(guān)的策略方法進(jìn)行衡量，對(duì)算法停滯問(wèn)題的研究也較少。對(duì)此，本文通過(guò)大量實(shí)驗(yàn)比較分析ACO算法中常見(jiàn)的方法策略，在此基礎(chǔ)上使用一種新的停滯檢測(cè)機(jī)制，最后與其他ACO算法的效果進(jìn)行比較。

12D HP格點(diǎn)模型

圖1　序列H2P5H2PHPHP的一個(gè)構(gòu)象

HP格點(diǎn)模型(Hydrophobic-Polar Square Lattice Model)分為2D HP格點(diǎn)模型和3D HP格點(diǎn)模型，前者應(yīng)用較為廣泛。本文僅針對(duì)2D HP格點(diǎn)模，但可擴(kuò)展為3D HP格點(diǎn)模型。在2D HP格點(diǎn)模型中，氨基酸脫水縮合形成多肽鏈時(shí)被簡(jiǎn)化為疏水性和親水性兩種，蛋白質(zhì)則被表示為由疏水性殘基H和親水性殘基P組成的序列S。HP模型基于蛋白質(zhì)折疊的熱力學(xué)假說(shuō)，即天然構(gòu)象的蛋白質(zhì)處于熱力學(xué)最低的能量狀態(tài)。因此蛋白質(zhì)折疊的過(guò)程被表示為序列S在二維網(wǎng)格上盤(pán)旋成能量最低的“構(gòu)象”過(guò)程。網(wǎng)格上的一個(gè)格點(diǎn)只能被一個(gè)殘基占據(jù)。S中不相鄰，構(gòu)象C中相鄰的H-H對(duì)稱為H-H鍵。C的能量用H-H鍵的數(shù)目n表示，表達(dá)式為EC= -1 × n。例如，圖1所示殘基序列H2P5H2PHPHP的構(gòu)象，其自由能為-4。

2蟻群算法

2.1解的表示

圖2　折疊方向的定義

HP模型中的殘基序列可表示為S=s1,s2,…,sn,si∈{H,P}。向網(wǎng)格中放置序列中的殘基si時(shí)，常用相對(duì)的方向[2-5,7]表示折疊過(guò)程，此時(shí)折疊方向序列可表示為D′=d1,d2,…,dm,di∈{S,L,R}，其中S、L、R分別代表直行、左轉(zhuǎn)和右轉(zhuǎn)。例如圖1中構(gòu)象的方向序列為D′=RRSRSRLRRRRS。由于方向是相對(duì)的，必須至少固定兩個(gè)殘基的位置之后才能確定下個(gè)殘基的折疊方向，因此方向序列的長(zhǎng)度為m=n-2。與此不同，實(shí)現(xiàn)采用了與文獻(xiàn)[1]所述相似的表示方式。如圖2所示，將方向序列定義為D=d1,d2,…,dm,di∈{F,B,L,R}，即用4個(gè)絕對(duì)的折疊方向F、B、L和R表示，此時(shí)方向序列的長(zhǎng)度m=n-1。使用該定義圖1所示構(gòu)象的方向序列為D=FRBBLLFLFRFRR。絕對(duì)的折疊方向更加直觀。

殘基序列S和方向序列D共同構(gòu)成一個(gè)解。一個(gè)解只能表示一個(gè)構(gòu)象，但一個(gè)構(gòu)象可以用多個(gè)解表示。指定構(gòu)象的起始?xì)埢?圖1中用同心圓圈出)后，建立起解和構(gòu)象的一一對(duì)應(yīng)關(guān)系?？紤]到構(gòu)象在空間經(jīng)旋轉(zhuǎn)、翻轉(zhuǎn)等操作(或以上操作的組合)后得到的構(gòu)象實(shí)際上為同一構(gòu)象，此時(shí)方向序列可能不唯一。通常2D HP模型不考慮構(gòu)象的空間變換，但兩個(gè)不同的方向序列是否表示同一構(gòu)象是可以判定的。

2.2建立構(gòu)象

蟻群算法中，該階段每只螞蟻進(jìn)行一次構(gòu)象。構(gòu)象的建立從隨機(jī)選定的位置si(1≤i≤n)開(kāi)始，每增加一個(gè)殘基稱為“擴(kuò)展”。從位置i向i+1進(jìn)行擴(kuò)展時(shí)稱為“正向”擴(kuò)展，i向i-1稱為“反向”擴(kuò)展。以正向擴(kuò)展為例，從位置i以方向d進(jìn)行擴(kuò)展時(shí)，以概率Pi,d隨機(jī)選擇擴(kuò)展方向，公式為：

(1)

信息素τi, d和啟發(fā)信息ηi, d共同決定擴(kuò)展方向，其中d∈{F, B, L, R}，參數(shù)α和β分別反映了信息素和其發(fā)信息的重要程度。ηi,d的常見(jiàn)形式有以下兩種：

ηi,d=1+hi,d

(2)

(3)

其中，hi,d為從當(dāng)前位置i以方向d擴(kuò)展后增加的H-H鍵數(shù)目，T為取值[0.25, 0.35]的常數(shù)。下面將式(2)簡(jiǎn)稱為HR1，式(3)簡(jiǎn)稱為HR2。本文采用HR2，實(shí)驗(yàn)部分對(duì)HR1、HR2兩組啟發(fā)函數(shù)進(jìn)行了進(jìn)一步討論。

構(gòu)建過(guò)程中有可能出現(xiàn)網(wǎng)格上四個(gè)方向的鄰接格點(diǎn)都被占據(jù)而無(wú)法繼續(xù)擴(kuò)展的情況，稱為“阻塞”。常見(jiàn)的處理策略有重新構(gòu)造、回退、淘汰-克隆等策略。初步分析可知重新構(gòu)造、回退策略耗時(shí)較多，但搜索到更多不同構(gòu)象的可能性較大，而克隆策略耗時(shí)少同時(shí)易于實(shí)現(xiàn)?？寺〔呗蕴蕴瓱o(wú)效的構(gòu)象，并以概率Pi隨機(jī)從有效構(gòu)象克隆。設(shè)有效構(gòu)象共m個(gè)，從構(gòu)象Ci克隆的概率為：

(4)

本文采用回退策略，實(shí)驗(yàn)部分對(duì)回退、淘汰-克隆兩種策略進(jìn)行了進(jìn)一步討論。

2.3局部搜索

構(gòu)象構(gòu)建階段結(jié)束后，選擇一定比例具有較小能量的構(gòu)象，對(duì)每個(gè)構(gòu)象進(jìn)行若干次局部搜索。較好的局部搜索方法包括“長(zhǎng)距離移動(dòng)”[7]、“牽引移動(dòng)”[5,6]等。長(zhǎng)距離移動(dòng)是相對(duì)于“短距離移動(dòng)”，例如“單點(diǎn)變異”和“多點(diǎn)變異”等來(lái)說(shuō)的，它對(duì)于致密的構(gòu)象依然有效，而牽引移動(dòng)的優(yōu)點(diǎn)是只需調(diào)整少數(shù)頂點(diǎn)即可達(dá)到有效構(gòu)象。本文采用牽引移動(dòng)方法，實(shí)驗(yàn)部分對(duì)兩種方法進(jìn)行了進(jìn)一步討論。與殘基的擴(kuò)展類似，牽引移動(dòng)也有正向、反向兩個(gè)方向。仍以正向?yàn)槔S機(jī)選擇殘基序列中的位置i，另設(shè)網(wǎng)格中的兩個(gè)格點(diǎn)e、f，位置i、i+1與e、f構(gòu)成如圖3所示的矩形(不失正確性，假定i、i+1垂直排列)，其中i的對(duì)角為f。

圖3　正向牽引移動(dòng)示例

牽引移動(dòng)算法描述如下：

Step1若e位置為空，且f為空或i+2，轉(zhuǎn)至Step2，否則移動(dòng)失敗，退出算法；

Step2將i+1移動(dòng)到e。如果e與i+2相鄰，轉(zhuǎn)至Step5，否則轉(zhuǎn)至Step3；

Step3將i+2移動(dòng)的f。如果f與i+3相鄰，轉(zhuǎn)至Step5，否則轉(zhuǎn)至Step4；

Step4將j+3移動(dòng)到原殘基j+1所在位置(i≤j≤n-3)，直至形成一個(gè)可行的構(gòu)象，轉(zhuǎn)至Step5；

Step5若新構(gòu)象具有更小的能量，移動(dòng)成功，接受該構(gòu)象，退出算法，否則移動(dòng)失敗，退出算法。

以i、i+1為一條邊的矩形有兩個(gè)，對(duì)應(yīng)的兩對(duì)e、f分別在邊i、i+1的兩側(cè)。為了加快收斂速度，牽引移動(dòng)時(shí)使用了貪心策略，對(duì)兩對(duì)e、f先后進(jìn)行搜索，取較優(yōu)的結(jié)果。反向牽引移動(dòng)類似，將圖3中i+1, i+2,…變?yōu)閕-1, i-2,…可得到反向牽引移動(dòng)的一個(gè)示例。文獻(xiàn)[6]證明了牽引移動(dòng)并非完全可逆，本文采用了該文獻(xiàn)給出的修正版本。

2.4更新信息素

完成構(gòu)象的構(gòu)建和局部搜索后，信息素按下式衰減：

τi, d=ρτi, d

(5)

其中，ρ是信息素殘留比。然后選擇一定比例具有較小能量的構(gòu)象進(jìn)行信息素的增強(qiáng)：

τi, d=τi,d+ EC/Em

(6)

其中，Em是序列已知的最小能量值。初始狀態(tài)下τi,d= 0.25，隨著迭代的進(jìn)行，某些方向上的信息素不斷增加，如果這些方向上的信息素遠(yuǎn)大于其他方向上的信息素，造成選擇其他方向的概率非常低，搜索將會(huì)陷入停滯狀態(tài)。為了防止搜索陷入停滯狀態(tài)，常用類似于最大-最小蟻群系統(tǒng)中的方法對(duì)信息素進(jìn)行調(diào)整[4](下面簡(jiǎn)稱為MM)。每次更新信息素后，首先將τi,d標(biāo)準(zhǔn)化，使得∑d∈{F,B,L,R}τi,d=1。設(shè)τi, max和τi, min分別為τi, d中最大和最小的信息素，如果τi, min<θ，則令τi, max= τi, max- (θ - τi, min), τi, min=θ。

2.5帶有停滯檢測(cè)的蟻群系統(tǒng)(SD-ACO)

MM在每次更新信息素后進(jìn)行，可以避免系統(tǒng)陷入停滯狀態(tài)。MM的缺陷在于，它無(wú)法確定對(duì)信息素進(jìn)行調(diào)整的時(shí)機(jī)，具有一定的盲目性。分別針對(duì)各個(gè)位置i對(duì)τi,d進(jìn)行調(diào)整，全局性較差。同時(shí)，由于信息素的積累與構(gòu)象的方向選擇是一種正反饋機(jī)制，過(guò)早的調(diào)整信息素必然對(duì)收斂速度有所影響。若能通過(guò)某種方式對(duì)停滯做出檢測(cè)，將能很好地解決上述問(wèn)題。為此，引入位置信息素停滯比ε和序列信息素停滯比μ(0.5<ε<1，0<μ<1)兩個(gè)參數(shù)，并定義：

(7)

(8)

通過(guò)對(duì)大量實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)分析，發(fā)現(xiàn)使用G能夠很好表示停滯。使用上述ACO算法進(jìn)行搜索(參數(shù)設(shè)置參考實(shí)驗(yàn)部分)，正常更新信息素，但不進(jìn)行調(diào)整。迭代若干次，統(tǒng)計(jì)每次迭代后G的值以及問(wèn)題的求解比(當(dāng)前最優(yōu)能量/Em，見(jiàn)圖4中圖例Solve)，所有迭代完成后取平均。圖4給出了實(shí)驗(yàn)部分所述序列Ser10的統(tǒng)計(jì)結(jié)果，其中ε分別取四個(gè)不同的值，橫軸為迭代次數(shù)，縱軸為G值或求解比?？梢?jiàn)求解比和G值均在一定次數(shù)的迭代后趨于穩(wěn)定。實(shí)驗(yàn)中發(fā)現(xiàn)，G趨于穩(wěn)定后，特定方向上的τi,d持續(xù)增大，選擇其他方向的可能性減小，而且這種情況隨著搜索的繼續(xù)越來(lái)越嚴(yán)重，以至搜索陷入停滯。對(duì)其他序列的實(shí)驗(yàn)結(jié)果也得出相似的特征，這就為文中所述停滯檢測(cè)方法提供了可行性驗(yàn)證，也為ε和μ兩個(gè)參數(shù)的設(shè)置提供了依據(jù)。停滯檢測(cè)的具體方法為，若G>μ則認(rèn)為搜索已經(jīng)停滯，隨后放棄整個(gè)蟻群系統(tǒng)，對(duì)τi,d進(jìn)行重置。本文將這種機(jī)制稱為SD(Stagnation Detection)，將使用這種機(jī)制的蟻群系統(tǒng)稱為SD-ACO。

圖4　迭代次數(shù)與求解比、G值的關(guān)系

SD基于對(duì)τi,d的統(tǒng)計(jì)分析，相對(duì)于MM，SD先進(jìn)行停滯檢測(cè)，再進(jìn)行進(jìn)一步處理。它使用了更全面的信息，即所有位置i上τi,d的整體狀況作為判斷依據(jù)，能夠更好地反映信息素的全局狀況。SD-ACO借鑒了遺傳算法的淘汰機(jī)制，對(duì)陷入停滯的蟻群系統(tǒng)進(jìn)行淘汰，并用新的系統(tǒng)取而代之。實(shí)踐證明，SD-ACO更充分地利用了蟻群系統(tǒng)的構(gòu)象能力，保證了解的質(zhì)量，同時(shí)具有更快的收斂速度。SD還可與其他機(jī)制結(jié)合，例如與MM結(jié)合。即將SD用作單純的檢測(cè)機(jī)制，同時(shí)將MM作為平滑機(jī)制。用SD檢測(cè)到停滯后不重置τi,d，而是按照MM的方式進(jìn)行調(diào)整。文中將這種混合機(jī)制稱為SD-MM。實(shí)驗(yàn)部分對(duì)MM、SD和SD-MM進(jìn)行了比較。

3實(shí)驗(yàn)結(jié)果及分析

本文幾組實(shí)驗(yàn)對(duì)蟻群算法相關(guān)步驟中的一些策略、方法進(jìn)行了分析，最后比較了帶有停滯檢測(cè)的蟻群算法以及若干其他改進(jìn)的ACO算法。算法使用C語(yǔ)言實(shí)現(xiàn)，編譯器為pgcpp 13.6-0，運(yùn)行環(huán)境配置有Intel Core i5 @ 3.2 GHz處理器，操作系統(tǒng)為CentOS。為了更全面地評(píng)估算法的性能，實(shí)驗(yàn)使用了文獻(xiàn)[1]給出的15組基準(zhǔn)序列，并將其編號(hào)為Ser1到Ser15。如無(wú)特別說(shuō)明，實(shí)驗(yàn)參數(shù)設(shè)置均設(shè)置為α=1,β=2,ρ=0.8。螞蟻數(shù)均為200只，用于局部搜索和信息素更新的比例為1%，局部搜索次數(shù)500次，迭代次數(shù)為10 000次。實(shí)驗(yàn)結(jié)果中的時(shí)間均為CPU時(shí)間，單位秒。

3.1HR1與HR2的比較

下面對(duì)啟發(fā)函數(shù)HR1和HR2進(jìn)行實(shí)驗(yàn)比較。構(gòu)象調(diào)整的效果依賴于起始構(gòu)象的能量，較差的起始構(gòu)象很少能被調(diào)整為高質(zhì)量的解[4]。啟發(fā)函數(shù)對(duì)構(gòu)象的建立有重要的指導(dǎo)作用，較好的構(gòu)象為局部搜索調(diào)整出高質(zhì)量的解提供了更大的可能性。實(shí)驗(yàn)僅關(guān)注HR1、HR2的啟發(fā)能力，即啟發(fā)函數(shù)對(duì)構(gòu)象能量的影響，構(gòu)象構(gòu)造完成后不進(jìn)行局部搜索，也不對(duì)信息素進(jìn)行更新。不限制迭代次數(shù)，將運(yùn)行時(shí)間限制在1800 s內(nèi)，HR2中T取0.25。對(duì)于長(zhǎng)度不大于36的短序列Ser1-8，分別獨(dú)立運(yùn)行100次，對(duì)于長(zhǎng)序列Ser9-15運(yùn)行20次。圖5給出了Ser10-15的結(jié)果，縱軸為平均時(shí)間，百分比為達(dá)到能量的概率，“+”號(hào)后為得到的能量與Em的差值。

圖5　Ser9-Ser15兩組啟發(fā)函數(shù)的比較

對(duì)于短序列，兩者均能以100%的概率得到最優(yōu)解，但HR2所用時(shí)間遠(yuǎn)小于HR1。對(duì)于長(zhǎng)序列，HR2搜索到的解優(yōu)于HR1，且時(shí)間性能較好。此外，對(duì)于短序列，僅使用隨機(jī)搜索即可在較短時(shí)間內(nèi)得到最優(yōu)解。對(duì)于長(zhǎng)序列，隨機(jī)搜索的求解能力不足，且容易“早熟”。如對(duì)于Ser12-15，使用HR2分別早在485、648、1101和945 s已找到最終解。綜上，HR2的啟發(fā)能力明顯優(yōu)于HR1。后續(xù)實(shí)驗(yàn)中均使用HR2。

3.2阻塞處理與局部搜索

下面對(duì)回退、淘汰-克隆兩種處理策略和長(zhǎng)距離移動(dòng)、牽引移動(dòng)兩種局部搜索方法進(jìn)行實(shí)驗(yàn)比較。阻塞處理影響算法的收斂速度及解的質(zhì)量，與局部搜索密切相關(guān)。因此實(shí)驗(yàn)對(duì)上述策略、方法的四種組合，即RB-LRM、RB-PM、CLN-LRM、CLN-PM分別進(jìn)行了測(cè)試。局部搜索后不進(jìn)行信息素的更新，達(dá)到迭代次數(shù)后停止，各序列分別使用四種組合各自獨(dú)立運(yùn)行100次。RB中回退長(zhǎng)度為已折疊序列長(zhǎng)度的一半(向下取整)，CLN中選擇%1的有效構(gòu)象，LRM中選擇與上個(gè)殘基相同方向的概率為0.5。LRM與PM均使用了貪心策略，每次局部搜索選擇正向、反向搜索中較優(yōu)的構(gòu)象。為節(jié)約篇幅，表1和表2僅給出了Ser12-15的部分運(yùn)行結(jié)果，即100次運(yùn)行達(dá)到相應(yīng)能量(E)的概率(P)、平均時(shí)間(T)及平均迭代次數(shù)(R)?？招斜硎緵](méi)有達(dá)到相應(yīng)能量。

表1　RB-LRM與RB-PM的結(jié)果比較

表2　CLN-LRM與CLN-PM的結(jié)果比較

將表中數(shù)據(jù)RB-LRM與RB-PM相比、CLN-LRM與CLN-PM相比，PM的最終解更好，E相同時(shí)PM的收斂速度更快、概率更大。將RB-LRM與CLN-LRM相比、RB-PM與CLN-PM相比，E相同時(shí)RB的概率更大，但收斂速度慢于CLN。Ser14中CLN-PM的最終解好于RB-PM，但CLN-PM僅以1%的概率得到該解，其他情況下RB的解均較優(yōu)。Ser1-11的運(yùn)行結(jié)果相似。綜上，局部搜索方法采用PM，為了保證解的質(zhì)量，阻塞處理策略采用RB。后續(xù)實(shí)驗(yàn)中均采用RB-PM。

3.3MM、SD以及SD-MM的比較

除默認(rèn)參數(shù)外，其他參數(shù)θ=0.05，ε=0.75，μ=0.5。對(duì)于Ser1-13分別獨(dú)立運(yùn)行100次，Ser14-15運(yùn)行50次。表3僅給出了Ser12-15的部分運(yùn)行結(jié)果，SD-ACO的結(jié)果可參見(jiàn)表4所示。其中“*”號(hào)標(biāo)記的能量等于序列已知的最小能量(下同)。

表3　三種停滯處理機(jī)制的比較

易見(jiàn)無(wú)論是解的質(zhì)量還是收斂速度SD、SD-MM均優(yōu)于MM。Ser13中SD-MM的收斂速度遠(yuǎn)快于SD，但求得最優(yōu)解及次優(yōu)解的概率均較低。Ser1-15中，僅對(duì)于Ser14，SD-MM的最終解概率高于SD，其他無(wú)論在求解質(zhì)量還是收斂速度上，SD具有明顯優(yōu)勢(shì)。

3.4SD-ACO與其他ACO算法的比較

SD-ACO的最終版使用HR2及RB-PM，對(duì)Ser1-13分別獨(dú)立運(yùn)行100次，Ser14-15運(yùn)行50次。表4給出了Ser1-15的測(cè)試結(jié)果，同時(shí)列出了其他文獻(xiàn)報(bào)告的結(jié)果。除文獻(xiàn)中已給出其改進(jìn)ACO算法的命名外，其他均使用作者姓名首字母命名。表中數(shù)據(jù)第一行為能量值，“*”號(hào)標(biāo)記的能量等于序列已知的最低能量(下同)，第二行為時(shí)間，空白行表示文獻(xiàn)未給出，若得到解的概率不為1，還給出了求得相應(yīng)解的概率。

表4　SD-ACO與其他ACO算法的比較

對(duì)于Ser1-13，SD-ACO能夠保證解的質(zhì)量，且收斂速度較快。對(duì)于Ser14-15，SD-ACO的解質(zhì)量?jī)?yōu)于HSZ-ACO和HA，且收斂速度較快?？偟膩?lái)說(shuō)SD-ACO的效果明顯，但Ser14中SD-ACO的解劣于LYPS-ACO，Ser15中SD-ACO的解劣于ACO-HPPFP-3。兩者均為運(yùn)行較長(zhǎng)時(shí)間后得到的，為進(jìn)一步研究運(yùn)行時(shí)間對(duì)SD-ACO解質(zhì)量的影響，進(jìn)行下述實(shí)驗(yàn)。取消迭代次數(shù)限制，增加運(yùn)行時(shí)間并觀察實(shí)驗(yàn)結(jié)果。表4中，ACO-HPPFP-3以外其他算法列出的運(yùn)行時(shí)間均在7000 s內(nèi)，除Ser15外SD-ACO均達(dá)到了ACO-HPPFP-3所得的最優(yōu)能量。為驗(yàn)證同等時(shí)間條件下SD-ACO的效果，將時(shí)限設(shè)置為7200 s。此外，為比較不同時(shí)限下SD-ACO的運(yùn)行結(jié)果，從而進(jìn)一步分析運(yùn)行時(shí)間對(duì)算法效果的影響，還使用時(shí)限3600 s進(jìn)行了測(cè)試。對(duì)Ser12-15分別獨(dú)立運(yùn)行20次，實(shí)驗(yàn)結(jié)果如表5所示。

表5　兩組時(shí)限的測(cè)試結(jié)果比較

其中Ser12以100%的概率達(dá)到最優(yōu)解，平均時(shí)間穩(wěn)定在90 s內(nèi)。雖然Ser14在時(shí)限3600 s時(shí)未找到解-47，但在時(shí)限7200 s時(shí)找到該解，且概率明顯增大。兩個(gè)時(shí)限下Ser13的兩組解均優(yōu)于表4中的其他算法，Ser15求得-48的概率有較大提升。考慮到實(shí)際應(yīng)用，沒(méi)有使用更大的時(shí)限進(jìn)行測(cè)試，但從表5的結(jié)果可得出，隨著運(yùn)行時(shí)間的增加，達(dá)到相應(yīng)解的概率增大，且有可能得到質(zhì)量更好的解。

4結(jié)語(yǔ)

HP格點(diǎn)模型是學(xué)術(shù)界廣泛接受的蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測(cè)模型，將ACO算法應(yīng)用于2D HP格點(diǎn)模型取得了較好的效果。眾多文獻(xiàn)對(duì)此提出了進(jìn)一步改進(jìn)，但效果不一。為衡量常見(jiàn)策略方法的優(yōu)劣，本文比較分析了兩組啟發(fā)式函數(shù)、四對(duì)阻塞處理與局部搜索策略方法，并在此基礎(chǔ)上使用了一種新的停滯檢測(cè)機(jī)制SD，并進(jìn)行實(shí)驗(yàn)驗(yàn)證，對(duì)蟻群算法作出了進(jìn)一步改進(jìn)。SD使用全局信息，通過(guò)參數(shù)化的方式檢測(cè)停滯，并借鑒遺傳算法的淘汰機(jī)制進(jìn)行調(diào)整。與最大-最小蟻群系統(tǒng)中的停滯預(yù)防機(jī)制相比，SD不盲目調(diào)整信息素，檢測(cè)停滯的時(shí)機(jī)更為精準(zhǔn)。實(shí)驗(yàn)結(jié)果表明，將SD-ACO應(yīng)用于2D HP模型取得了較好的效果。此外，并行化是提升算法效率的重要手段，這也是后續(xù)的研究方向。

參考文獻(xiàn)

[1] Mario GarzaFabre,Eduardo RodriguezTello,Gregorio ToscanoPulido.Comparative Analysis of Different Evaluation Functions for Protein Structure Prediction Under the HP Model[J].Journal of Computer Science and Technology,2013,28(5):870-873.

[2] 陸恒云,楊根科,潘常春,等.改進(jìn)的蟻群算法求解蛋白質(zhì)折疊問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(8):1787-1788.

[3] 李晚霞,莫忠息,曾濤.混合遺傳算法和蟻群算法在HP模型中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(31):58-59.

[4] Alena Shmygelska,Holger H Hoos.An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem[J].BMC Bioinformatics,2005,6(30):18-21.

[5] 何蓮蓮,石峰,周懷北.改進(jìn)的蟻群算法在2D HP模型中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào):理學(xué)版,2005,51(1):35-37.

[6] Gy?rffy D,Závodszky P,Szilágyi A. ”P(pán)ull Moves” for Rectangular Lattice Polymer Models Are Not Fully Reversible[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2012,9(6):1847-1848.

[7] Alena Shmygelska,Holger H Hoos.An Improved Ant Colony Optimisation Algorithm for the 2D HP Protein Folding Problem[C]//Lecture Notes in Computer Science,2003,2671:405-417.

[8] Ken A Dill,Justin L MacCallum.The Protein-Folding Problem,50 Years On[J].Science,2012,338(6110):1042-1045.

中圖分類號(hào)TP18TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.053

收稿日期：2014-10-21。國(guó)家自然科學(xué)基金項(xiàng)目(41264005)；廣西教育廳科研項(xiàng)目(201102ZD018)。劉羽，教授，主研領(lǐng)域：并行計(jì)算，數(shù)據(jù)挖掘。熊壬浩，碩士。