混合群智能算法在模體識別中的應(yīng)用

楊 柳，劉鐵英，李雪蓮

（1.吉林工商學(xué)院 信息工程分院，長春 130062；2.長春職業(yè)技術(shù)學(xué)院 信息分院，長春 130033；3.吉林省財政廳 吉林省財稅信息中心，長春 130021）

混合群智能算法在模體識別中的應(yīng)用

楊 柳1，劉鐵英2，李雪蓮3

（1.吉林工商學(xué)院 信息工程分院，長春 130062；2.長春職業(yè)技術(shù)學(xué)院 信息分院，長春 130033；3.吉林省財政廳 吉林省財稅信息中心，長春 130021）

為了避免傳統(tǒng)吉布斯算法的諸多缺陷，提高算法的求解能力，對蟻群算法（ACO：Ant Colony Optimization）進行了改進：引入粒子群算法（PSO：Particle Swarm Optimization）動態(tài)調(diào)節(jié)ACO函數(shù)中的參數(shù)獲得最優(yōu)解。在奔騰PC機的實驗平臺上、Windows 2003Server操作系統(tǒng)下、開發(fā)工具為VB的模擬實驗中，結(jié)果證明，混合的群智能算法使經(jīng)典旅行商問題求解的計算時間縮短，提高了算法的收斂速度，有較好的發(fā)展前景。利用PSO處理連續(xù)優(yōu)化問題的優(yōu)點，將混合算法應(yīng)用于生物信息學(xué)的模體識別中，可實現(xiàn)更加快速的基序發(fā)現(xiàn)處理。

吉布斯算法；粒子群算法；模體識別

0 引 言

傳統(tǒng)的蟻群算法［1，2］在離散問題上取得了很好的研究結(jié)果，但有幾個突出問題制約了算法的應(yīng)用。其中重要的一點是，蟻群算法的參數(shù)繁多，設(shè)置參數(shù)時根據(jù)人工經(jīng)驗進行，所以對不同問題，蟻群算法的參數(shù)都需要進行改變，而且參數(shù)選擇往往對算法的結(jié)果有至關(guān)重要的影響。通常，同一問題，用同樣算法，由于參數(shù)設(shè)置的不同，結(jié)果大相徑庭。一個完善的算法不僅要有穩(wěn)定的適應(yīng)性，還要有輸出結(jié)果的一致性。現(xiàn)將具有全局優(yōu)化功能的群智能算法粒子群優(yōu)化算法（PSO：Particle Swarm Optimization）［3，4］應(yīng)用于蟻群算法（ACO：Ant Colony Optimization）模型中，對參數(shù)進行自動選擇，通過PSO自動調(diào)節(jié)參數(shù)的功能，使參數(shù)選擇不再依賴于人工經(jīng)驗，而且在特定的組合優(yōu)化經(jīng)典旅行商（TSP：Traveling Salesman Problem）問題中，這種混合算法都能得到比較滿意的結(jié)果。

在生物信息學(xué)問題上智能算法已經(jīng)取得很多成果，如，仿生類進化算法，人工神經(jīng)網(wǎng)絡(luò)［5］等。為提高傳統(tǒng)方法求解能力，筆者設(shè)計了一種通過粒子群算法自動調(diào)節(jié)蟻群算法主要參數(shù)的混合算法，使在解決TSP問題上得到較滿意應(yīng)用結(jié)果的前提下，將混合的群智能算法應(yīng)用于生物信息學(xué)中的模體識別問題，實驗結(jié)果證明混合的群智能算法避免吉布斯方法的冗余解，有效減少了算法的運行時間，取得了較好的結(jié)果。

1 PSO／ACO混和算法

群智能算法作為一種新興的演化計算技術(shù)，如同模擬進化算法，是通過群體中個體的有效解組成群體進化迭代實現(xiàn)尋求最優(yōu)解的過程［1－4］。

概率選擇是蟻群算法的主要思想，選擇參數(shù)設(shè)置要依賴于實驗人員經(jīng)驗設(shè)置。如果選擇的不合適，將使結(jié)果不理想。同是群智能算法的粒子群算法在連續(xù)問題上得到了很好的結(jié)果［6，7］，所以，將PSO算法用于ACO算法參數(shù)的自適應(yīng)調(diào)節(jié)以解決TSP問題的目標(biāo)函數(shù)

其中d（i，j）（i，j＝1，2，3，…，n）表示城市i與j之間的距離。

ACO在選路中的概率函數(shù)

其中ηij為距離因子，τij（t）為邊弧（i，j）信息素的強度，α表示信息素在選擇概率上的作用率；β是指路徑長度在選擇概率上的作用率。參數(shù)α與β對解的影響很大，為了選擇最優(yōu)參數(shù)，引入PSO算法。

PSO算法的計算如下

其中k為迭代次數(shù)，Vi為速度向量，Δt為時間間隔，Xi為第i個粒子的位置向量，c1和c2是非負(fù)常數(shù)，r1和r2是介于［0，1］的隨機數(shù)，w是慣性權(quán)重，隨著迭代的進行線性地減?。?］。

應(yīng)用PSO自動調(diào)節(jié)ACO中的參數(shù)：粒子被定義在一個范圍中，將每個粒子的位置定義為一個潛在的解，粒子群根據(jù)式（3）進行位置變換，由式（3），式（4）中第i個粒子的位置向量Xi，第i個速度向量V，自動優(yōu)化配置ACO中的主要參數(shù)α和β能使算法收斂，在奔騰PC機、操作系統(tǒng)為Windows 2003Server、開發(fā)工具為VB的的實驗平臺上進行TSP模擬實驗，優(yōu)化參數(shù)α和β后重新帶入式（2）中，在目標(biāo)函數(shù)中以St70，Att48作為ACO運算取值，計算概率函數(shù)，與單純ACO算法的概率函數(shù)運算時間和最優(yōu)解的對比結(jié)果如表1所示。

表1 PSO／ACO算法與ACO算法對比Tab.1 PSO／ACO and ACO algorithm comparion

從混合算法的實驗結(jié)果可以看出，在不同條件下，自適應(yīng)地對參數(shù)進行調(diào)節(jié)，改進算法較基本蟻群算法在運行速度和解的質(zhì)量上都有較明顯提高，說明改進有效。

2 生物信息學(xué)中的模體識別問題

生物信息學(xué)中的模體識別問題是揭示核酸和蛋白質(zhì)序列的生物意義的基本方法［8］。問題的關(guān)鍵是找到不同序列間的相似段落，類似數(shù)據(jù)結(jié)構(gòu)中的字符串匹配，是一種近似的方法求解模體，不必嚴(yán)格匹配。其中人們將具有某種特征模式的序列片段稱為模體，為了區(qū)分模體在核酸序列中的不同，通常在蛋白質(zhì)序列中叫模體，而在核酸序列中叫基序。在用計算機進行模體識別問題的處理時，基序的發(fā)現(xiàn)主要有兩種描述的方法：1）確定性的描述方法，但對海量數(shù)據(jù)是不能現(xiàn)實的；2）基于模糊查找方式，基于統(tǒng)計方法實現(xiàn)。統(tǒng)計方法主要有吉布斯采樣方法、Meme方法和Consensus方法。3種方法的共同特點是用統(tǒng)計思想設(shè)計算法，并實現(xiàn)對給定目標(biāo)的優(yōu)化。

目前，最多使用的方法是吉布斯方法［9］。其主要步驟如下。

第一步 初始化。生成任意n在各條序列中的起始位點，可以記為M＝｛Mi｝，i＝1，…，n。建立位置頻率矩陣Q。建立調(diào)控元件模型與背景模型。

第二步 更新。為了描述非模體區(qū)域的情況，需要建立背景模型。根據(jù)變化后的結(jié)果來計算位置頻率矩陣。

第三步 采樣。根據(jù)輪盤賭原理選擇新的候選調(diào)控元件，計算出兩種得分的比值，以較大的概率選取比值較高的候選調(diào)控元件，使其起始位點加入到M中。如果大于前一次得分，則轉(zhuǎn)到第二步，繼續(xù)迭代；否則，重復(fù)第三步，直到重復(fù)次數(shù)大于一個預(yù)設(shè)定值。如果所有序列都處理完，則轉(zhuǎn)第四步；否則，轉(zhuǎn)第二步。

第四步 結(jié)束。

3 混和算法在模體識別中的應(yīng)用

因為吉布斯方法在模體識別中取得了很好的應(yīng)用結(jié)果，所以在很多情況下，實踐應(yīng)用的方法都是在傳統(tǒng)的吉布斯抽樣方法基礎(chǔ)上進行改進的。傳統(tǒng)的吉布斯抽樣方法［10］主要有兩個明顯缺陷：1）在每個序列中都要選擇位置，雖然對于大規(guī)模的海量數(shù)據(jù)而言，以犧牲準(zhǔn)確率獲取速度，在一定范圍內(nèi)是準(zhǔn)許的，但將很大程度地降低算法的執(zhí)行效率；2）由于要對計算的每個起始位置進行打分，而很多打分是沒有任何意義的，只有采用優(yōu)化算法，提高算法的運算速度，才能更好地解決問題。

改進的步驟如下。

1）對一個找到的基序，對其中每個變量進行迭代采樣。迭代后，吉布斯采樣最終得到一個平穩(wěn)分布。準(zhǔn)確度打分函數(shù)如下

其中pik＝Q（i，ak），ak為A＝｛a1，…，aL｝中第k個字母，q為背景模型順序取值。應(yīng)用式（5）對子串進行打分。

2）在輸入序列找到一個基序的標(biāo)本。利用混合群智能算法在待查序列中找到一系列的最優(yōu)候選位置。概率計算如下

其中pk（li）表示螞蟻k在位置l選擇字符i的概率，α是信息素的影響因子，S是輸入的序列。τli（t）定義如下

3）對信息素的值進行更新后，由于在Ai中候選位置的數(shù)量取決于參數(shù)θ（θ為序列（1，2，4，16，64，…，n）的自選值），找到ni／θ個候選位置用來構(gòu)造Ai，對于每個候選位置，用式（5）計算打分，當(dāng)基序的候選子集變化時，退出程序。由得分函數(shù)（4）計算改進后與原始吉布斯算法的運算時間與準(zhǔn)確度打分對比實驗結(jié)果如表2所示。

實驗結(jié)果表明，由于混合群智能算法決定吉布斯采樣過程的候選序列，候選序列的大小取決于參數(shù)θ，θ越大，候選序列越小。隨著候選集規(guī)模的下降，雖然算法的執(zhí)行效率得到很大提高，但打分也隨之降低，從而影響了混合算法的精確度，但該精確度是在可接受范圍內(nèi)的。

改進的混合算法提供了一種新型的可用于連續(xù)優(yōu)化問題處理的方法。該方法擴大了參數(shù)選擇的范圍，更有利于算法找到最優(yōu)解。實驗結(jié)果證明了群智能算法在該領(lǐng)域有很好的應(yīng)用。

表2 混合算法與傳統(tǒng)吉布斯方法的比較Tab.2 Hybrid algorithm and Gibbs method comparison

4 結(jié) 語

筆者通過粒子群算法自動調(diào)節(jié)蟻群算法主要參數(shù)的混合算法，用于生物信息學(xué)中的模體識別問題，擴大了參數(shù)選擇的范圍，更有利于算法找到最優(yōu)解。模體識別問題本身適合于混合算法的數(shù)據(jù)模型，首先，應(yīng)用PSO／ACO混和算法在待查序列中找到一系列的最優(yōu)候選位置；然后，應(yīng)用吉布斯抽樣方法對找到的候選解中有用的候選解計算分值。模擬實驗表明，混合群智能算法較之傳統(tǒng)的吉布斯方法運算效率得到很大的提高，而且對于海量數(shù)據(jù)，犧牲準(zhǔn)確率換取速度的方法在一定范圍內(nèi)是被準(zhǔn)許的。所以，可以減少計算時間，從而提高了算法的效率，代價是犧牲了一定的穩(wěn)定性。PSO／ACO混和算法對大量模體特征的識別具有非常顯著的優(yōu)勢，提高了序列分類的準(zhǔn)確性。模體識別的實驗亦可證明群智能算法在該應(yīng)用領(lǐng)域中有很好的前景和較大的影響力。在今后的研究中還需進一步提高自動調(diào)控的準(zhǔn)確度和穩(wěn)定性，使群智能混合算法為各應(yīng)用領(lǐng)域的實際工程問題提供更好的解決方法。

［1］DORIGO M，MANIEZZO V，COLORNI A.The Ant System：Optimization by a Colony of Cooperating Agents［J］.IEEE Transactions on SMC，1996，26（1）：1-13.

［2］DORIGO M，GAMBARDELLA L M.Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem［J］.IEEE Transactions on Evolutional Comutation，1997，1（1）：53-66.

［3］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2001.

WANG Ling.Swarm Intelligence Algorithm and Its Application［M］.Beijing：Tsinghua University Press，2001.

［4］KCNNCDY J，EBERHART R C.Particle Swarm Optimization［C］∥Proc the IEEE International Joint Conference on Neural Networks.Orland，USA：［s.n.］，1995：588-590.

［5］林和平，張秉正，喬幸娟.回歸分析人工神經(jīng)網(wǎng)絡(luò)［J］.吉林大學(xué)學(xué)報：信息科學(xué)版，2010，28（2）：147-149.

LIN He-ping，ZHANG Bing-zheng，QIAO Xing－juan.Regression Analysis Artificial Neural Network［J］.Journal of Jilin University：Information Science Edition，2010，28（2）：147-149.

［6］EBERHART R C，KENNEDY J.A New Optimizer Using Particle Swarm Theory［C］∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya，Japan：［s.n.］，1995：39-43.

［7］LI Yan-jun，WU Tie-jun.A Nested Hybrid Ant Colony Algorithm for Hybrid Production Scheduling Problems［J］.Acta Auomatica Sinica，2003，29（1）：95-101.

［8］KEICH U，PEVZNER P A.Finding Motisf in the Twilight Zone［J］.Bioinofrmatics，2002，18（10）：1374-1381.

［9］THOMPSON W，ROUCHKA E C，LWARENCE C E.Gibbs Recursive Sampler：Finding Transcription Factor Binding Sites［J］.Nucleic Acids Research，2003，31（13）：3580-3585.

［10］NEUWALD A F，LIU J S，LWARENCE C E.Gibbs Motif Sampling：Detection of Bacterial Outer Membrane Repeats［J］.Protein Science，1995，4（8）：1618-1632.

Application of Hybrid Swarm Intelligence Alogrithm on Finding Motif Problem

YANG Liu1，LIU Tie-ying2，LI Xue-lian3

（1.Department of Information Engineering，Jilin Business and Technology College，Changchun 130062，China；2.School of Information Technology，Changchun Vocational Institute of Technology，Changchun 130033，China；3.Jilin Taxation Information Center，Jilin Provincial Finance Department，Changchun 130021，China）

In order to avoid many Gibbs algorithm defects，improve the ability of problem solving，improvements the ACO （Ant Colony Optimization）：PSO （Particle Swarm Optimization）is made to optimize the parameters in the ACO.Pentium PC machine is the experiment platform，operating system is Windows 2003Server，development tools is VB，the traveling salesman problem is tsimalated.Results show that the computing time of the algorithm can be reduced by new methods.It had great effects in practicality and rapid processing of motif discovary.

Gibbs algorithn；particle swarm optimization；finding motif

TP313

A

1671-5896（2012）01-0056-04

2011-09-01

吉林省教育廳“十二五”科學(xué)技術(shù)研究基金資助項目（吉教科合字［2012］第371號）

楊柳 （1979—），女，長春人，吉林工商學(xué)院講師，碩士，主要從事智能算法研究，（Tel）86-15584279857（E-mail）yangliu7025＠sina.com。

（責(zé)任編輯：何桂華）