算法分析與設(shè)計

1、 算法設(shè)計與分析報告 題目名稱：蟻群算法及其在序列比對中的應(yīng)用研究綜述院 系： * 班 級： * 姓 名： * 學(xué) 號： * 指導(dǎo)教師： * 2016年11月20日蟻群算法及其在序列比對中的應(yīng)用研究綜述摘要蟻群算法是一種新穎的仿生進(jìn)化算法。作為一種全局搜索的方法，螞蟻算法具有正反饋性、并行性、分布性、自組織性等特點(diǎn)，自提出以來，便在求解復(fù)雜組合優(yōu)化問題上顯示出了強(qiáng)大的優(yōu)勢。序列比對是生物信息學(xué)的基礎(chǔ)，通過在比對中獲得大量的序列信息，可以推斷基因的結(jié)構(gòu)、功能和進(jìn)化關(guān)系。本文首先詳細(xì)闡述了蟻群算法的基本原理、各種改進(jìn)技術(shù)及收斂性分析，然后對蟻群算法在雙序列比對和多序列比對的應(yīng)用研究進(jìn)行了綜述和評價

2、，最后指出了下一步的研究方向。關(guān)鍵詞：蟻群算法；序列比對；信息素1 引言蟻群算法(Ant Algorithm)是一種源于大自然中生物世界的新的仿生類算法，作為通用型隨機(jī)優(yōu)化方法，它吸收了昆蟲王國中螞蟻的行為特性，通過其內(nèi)在的搜索機(jī)制，在一系列困難的組合優(yōu)化問題求解中取得了成效。由于在模擬仿真中使用的是人工螞蟻概念，因此有時亦被稱為螞蟻系統(tǒng)(Ant System)。據(jù)昆蟲學(xué)家的觀察和研究發(fā)現(xiàn)，生物世界中的螞蟻有能力在沒有任何可見提示下找出從其窩巢至食物源的最短路徑，并能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。作為昆蟲的螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物

3、信息激素(Pheromone)，使得一定范圍內(nèi)的其他螞蟻能夠察覺到并由此影響它們以后的行為。當(dāng)一些路徑上通過的螞蟻越來越多時，其留下的信息激素軌跡(Trail)也越來越多，以致信息素強(qiáng)度增大（隨時間的推移會逐漸減弱），后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度，這種選擇過程被稱之為螞蟻的自催化行為。由于其原理是一種正反饋機(jī)制，因此，也可將蟻群系統(tǒng)理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)。蟻群算法由意大利學(xué)者M(jìn)Dorigo等人在20世紀(jì)90年代初提出來的13。發(fā)展到今天已經(jīng)有十幾年的路程，在這一段時間里人們不斷的對蟻群算法提出一些改進(jìn)方法。有Dorigo等人提出的一種稱之為AntQ System

4、4的蟻群算法，該算法只讓每次循環(huán)中的最短路徑上的信息量作更新，強(qiáng)化了信息的反饋。德國學(xué)者Stutzle和Hoos提出了一種最大最小螞蟻系統(tǒng)(MAX-MIN ant system，MMAS) 5，MMAS對信息量的上下界作了限定，并且在算法中采用了軌跡平滑機(jī)制。直到今天，MMAS仍然是解決TSP、QAP等離散域優(yōu)化問題的最好蟻群算法模型之一，很多對蟻群算法的改進(jìn)策略都滲透著MMAS的思想。另外還有國內(nèi)的學(xué)者吳慶洪等人提出了一種具有變異特征的蟻群算法6，他們在蟻群算法中引入了逆轉(zhuǎn)變異機(jī)制。蟻群算法具有較好的魯棒性，并行分布式計算及易于與其他啟發(fā)式方法結(jié)合等優(yōu)點(diǎn)，在短期內(nèi)得到了很大發(fā)展，其應(yīng)用領(lǐng)域也

5、不斷得到擴(kuò)展710。目前已有一些學(xué)者將蟻群算法應(yīng)用到序列比對這一領(lǐng)域當(dāng)中，其中梁棟等人將蟻群算法應(yīng)用于序列比對，并提出基于自適應(yīng)調(diào)整信息素的改進(jìn)算法11，其結(jié)果表明，蟻群算法可以有效地運(yùn)用于雙序列比對問題。陳娟等人12,13提出了蟻群優(yōu)化算法在多序列比對中的應(yīng)用及漸進(jìn)算法結(jié)合蟻群算法在多序列比較中的應(yīng)用，并取得了較好的效果。Yixin Chenl等人14提出了基于分割方法的蟻群多序列比對方法。該算法采用蟻群算法將遞歸地將序列分割成垂直分割成若干子序列。SRJangam等人15 在遺傳算法中嵌入使用了蟻群算法來解決雙序列比對問題。Zne-Jung Le等人16結(jié)合了遺傳算法和蟻群算法來解決多序列

6、比對問題。為了將這些分散的文獻(xiàn)和資料集中起來,本文對蟻群算法及其在序列比對中的應(yīng)用研究進(jìn)行了較全面地綜述。2 蟻群算法的原理用于優(yōu)化領(lǐng)域的人工螞蟻算法，其基本原理吸收了生物界中螞蟻群體行為的某些顯著特征：(1) 察覺小范圍區(qū)域內(nèi)狀況并判斷出是否有食物或其他同類的信息素軌跡；(2) 釋放自己的信息素；(3) 所遺留的信息素數(shù)量會隨時間而逐步減少。由于自然界中的螞蟻基本沒有視覺，既不知向何處去尋找和獲取食物，也不知發(fā)現(xiàn)食物后如何返回自己的巢穴，因此它們僅僅依賴于同類散發(fā)在周圍環(huán)境中的信息素，來決定自己何去何從。有趣的是，盡管沒有任何先驗知識，但螞蟻們還是有能力找到從其巢穴到食物源的最佳路徑，甚至在

7、該路線放置障礙物之后，它們?nèi)匀荒芎芸熘匦抡业叫碌淖罴崖肪€。這里，用一個形象化的圖2.01來說明螞蟻群體的路徑搜索原理和機(jī)制。圖2.01螞蟻從蟻穴移至食物源假定障礙物的周圍有兩條道路可從螞蟻的巢穴到達(dá)食物源：Nest-ABD-Food和Nest-ACD-Food，分別具有長度4和6。螞蟻在單位時間內(nèi)可移動一個單位長度的距離。開始時所有道路上都未留有任何信息素。在t=0時刻，20只螞蟻從巢穴出發(fā)移動到A。它們以相同概率選擇左側(cè)或右側(cè)道路，因此平均有10只螞蟻走左側(cè)，10只走右側(cè)。在t=4時刻，第一組到達(dá)食物源的螞蟻將折回。在t=5時刻，兩組螞蟻將在D點(diǎn)相遇。此時BD上的信息素數(shù)量與CD上的相同，因

8、為各有10只螞蟻選擇了相應(yīng)的道路。從而有5只返回的螞蟻將選擇BD而另5只將選擇CD。在t=8時刻，前5個螞蟻將返回巢穴，而AC，CD和BD上各有5個螞蟻。在t=9時刻，前5個螞蟻又回到A并且再次面對往左還是往右的選擇。這時，AB上的軌跡數(shù)是20而AC上是15，因此將有較多數(shù)的螞蟻選擇往左，從而增強(qiáng)了該路線的信息素。隨著該過程的繼續(xù)，兩條道路上信息素數(shù)量的差距將越來越大，直至絕大多數(shù)螞蟻都選擇了最短的路線。正是由于一條道路要比另一條道路短，因此，在相同的時間區(qū)間內(nèi)，短的路線會有更多的機(jī)會被選擇。螞蟻有能力在沒有任何提示下找到從其巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性的搜索新的路

9、徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物源時，能在其走過的路上釋放信息素，隨著時間的推移該物質(zhì)會逐漸揮發(fā)，后來的螞蟻選擇該路徑的概率與當(dāng)時這條路徑上該物質(zhì)的強(qiáng)度成正比，當(dāng)一定路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度。而強(qiáng)度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機(jī)制。通過這種正反饋機(jī)制，螞蟻最終可以發(fā)現(xiàn)最短路徑。特別地，當(dāng)螞蟻巢穴與食物源之間出現(xiàn)障礙物時，螞蟻不僅可以繞過障礙物，而且通過蟻群信息素軌跡在不同路徑上的變化，經(jīng)過一段時間的正反饋，最終收斂到最短路徑上。3 基本蟻群算法的過程基本的蟻群算法可以應(yīng)

10、用于基于圖表示的組合優(yōu)化問題中（如 TSP），其簡單表述如下：在起始時刻進(jìn)行初始化，將個螞蟻隨機(jī)放在個城市上，城市間的每一條邊都有一個初始外激素強(qiáng)度值。每個螞蟻的禁忌表的第一個元素為其初始城市。然后每個螞蟻從城市到城市，依據(jù)概率函數(shù) (1)選擇將要移動的城市，這個概率取決于城市間的距離和信息素的強(qiáng)度。其中表示邊上信息素的強(qiáng)度；表示城市間距離因子，通常取為距離的倒數(shù)；集合，和都是控制信息素與可見度的相對重要性的參數(shù)?？梢娹D(zhuǎn)移概率是可見度和t時刻信息素強(qiáng)度的權(quán)衡。在n次循環(huán)后，所有螞蟻的禁忌表都填滿后，計算每個螞蟻走過的路徑的長度，并找到最短路徑保存，記錄此路徑并更改該路徑上的信息素 。信息素更新

11、的公式是：(2)(3)其中表示在某條邊上的累加新增信息素的和，表示信息素消散的等級，表示在時刻t和t+ n之間第k個螞蟻在邊(i ,j)留下的信息素的數(shù)量。如果在時刻t和t+n之間第k個螞蟻經(jīng)過邊(i,j)，則 (4)其中Q 為常量，為第k個螞蟻周游的路徑長度。這一過程重復(fù)直至達(dá)到最大迭代次數(shù)結(jié)束，或者所有螞蟻都走同一路線。后一種情況被稱為停滯狀態(tài)。如果算法在NC次循環(huán)后終止，螞蟻算法的復(fù)雜度為。4 改進(jìn)的蟻群算法4.1最大最小螞蟻系統(tǒng)MMAS(Max Min Ant System) 5是到目前為止解決 TSP、QAP 等問題最好的ACO 類算法。其特點(diǎn)在于：只對最佳路徑增加外激素的濃度，從而

12、更好地利用了歷史信息；為了避免算法過早收斂于局部最優(yōu)解，將各條路徑可能的外激素濃度限制于，超出這個范圍的值被強(qiáng)制設(shè)為或者，可以有效地避免某條路徑上的信息量遠(yuǎn)大于其余路徑，使得所有的螞蟻都集中到同一條路徑上，從而使算法不再擴(kuò)散；將各條路徑上外激素的起始濃度設(shè)為，這樣便可以更加充分地進(jìn)行尋優(yōu)。4.2相遇算法相遇算法(Meet Max Min Ant System，MMMAS) 17的基本思路是將一只螞蟻的一次周游分由兩只螞蟻分頭進(jìn)行，在路徑中間相遇合成一次周游路徑。此外，由于在一次循環(huán)中，螞蟻進(jìn)行多次周游，最短的一次周游影響路徑信息素，因此，在一次周游中，選擇一個城市后，即計算當(dāng)前路徑長度，如果長

13、度超過本次循環(huán)已得到的最小值即終止此次周游，這樣可以進(jìn)一步縮短計算時間。其步驟如下：(1) 初始化參數(shù)：(2) NC+(3) 一組螞蟻開始執(zhí)行相遇算法，循環(huán)變量k+(i) 兩只螞蟻選擇同一起點(diǎn)城市，建立禁忌表(ii) 其中一只螞蟻以式(1)計算的轉(zhuǎn)移概率選擇一個城市(iii) 另一只螞蟻也以式(1)計算的轉(zhuǎn)移概率選擇一個城市(iv) 判斷當(dāng)前路徑長度，如果大于本次相遇算法m組螞蟻已找到的最短路徑則終止此次兩只螞蟻周游，continue(v) 判斷禁忌表，如果未滿，轉(zhuǎn)至(ii)(vi) 2-opt局部優(yōu)化路徑（可選） (4) 如果k<m轉(zhuǎn)至(3)(5) 計算本次m組螞蟻相遇循環(huán)的最短路徑，

14、置空禁忌表(6) 用式(2)(4)更新路徑信息素（最短路徑增加，其他衰減） (7) 如果NC小于且未進(jìn)入停滯狀態(tài)，轉(zhuǎn)至(2)(8) 輸出最優(yōu)解，算法停止.從算法描述可以看出，一次周游的兩只螞蟻共用一個禁忌表，這樣保證兩只螞蟻不會選擇重復(fù)的城市。5 蟻群算法的收斂速度分析應(yīng)用研究的發(fā)展促進(jìn)了學(xué)者們對蟻群算法理論的研究,主要內(nèi)容在于算法數(shù)學(xué)模型、收斂性和收斂速度的分析. Gutjah針對一種特殊的蟻群算法(graph-based ant system)建立了概率轉(zhuǎn)換模型, 并分析了該算法收斂的條件1820. 受此結(jié)果的啟發(fā)Sttzle和Dorigo21進(jìn)一步給出了保證蟻群算法收斂的一般性條件:最優(yōu)

15、解路徑對應(yīng)信息素的下確界應(yīng)大于0,以確保算法至少有一次找到全局最優(yōu)解這個結(jié)論對于絕大多數(shù)蟻群算法的分析都是合適的,不過結(jié)論的證明類似于對非啟發(fā)式隨機(jī)搜索算法的分析,對算法性能評價以及設(shè)計方面的指導(dǎo)意義不明顯. Dorigo等又將蟻群算法的收斂性分為兩種類型22,23: (1) 值收斂(convergence in value) , 即當(dāng)?shù)鷷r間趨于無窮時, 蟻群算法至少一次達(dá)到最優(yōu)解; (2) 解收斂(convergence in solution) ,即當(dāng)?shù)鷷r間趨于無窮時,蟻群算法找到最優(yōu)解的概率趨于1.兩種收斂性的證明22都類似于文獻(xiàn)21的分析,結(jié)論充實了蟻群算法的收斂性理論.上面主要是

16、基于概率模型的收斂性分析, 國內(nèi)外學(xué)者還從隨機(jī)過程的角度研究了蟻群算法的收斂性. Badr和 Fahmy24利用隨機(jī)游走模型(random ranching)分析了一種特殊蟻群算法的收斂性.但是由于約束條件較多,其結(jié)論難以進(jìn)行推廣.國內(nèi)Ke和Yang等25,26則是利用有限Markov 鏈模型(Markov chain)作為研究ACO收斂性的工具; 但是, 分析結(jié)論只能適用于信息素矩陣狀態(tài)有限的特殊蟻群算法. 黃翰等建立了吸收態(tài) Markov過程數(shù)學(xué)模型,與以往蟻群算法的Markov鏈模型相比,有著更加廣泛的適用性。6 蟻群算法在序列比對中的應(yīng)用6.1 雙序列比對6.1.1 雙序列比對問題描述

17、雙序列比對是多序列比對和序列數(shù)據(jù)庫搜索的基礎(chǔ)。Needlernan和Wunsch提出的比對方法屬于動態(tài)規(guī)劃范疇27。對于一個序列S，|S|是S中字符的個數(shù)，Si表示序列的第i個字符. S1.i表示序列的前i個字符組成的子序列。S中的字符有某個有限字符集合確定(如DNA由4種核糖核酸A、T、C、G確定)?；蛐蛄性谕蛔冎械淖兓ㄌ娲?、插入和刪除，我們用“-”來表示插入和刪除所產(chǎn)生的空位。對于，定義為打分函數(shù)，表示x，y比較時的得分，設(shè)匹配得分為2，失配為-1，空位罰分為-2，則有： (1)序列S和T的一個比對A用序列和 (插入空位后的序列S和T)中字符一一對應(yīng)表示，有。序列比對A的得分為： (

18、2)序列比對的主要目標(biāo)是如何尋找出序列間的最大相似度的比對。那么如何找到兩個序列S和T的全局最優(yōu)比對呢?一方面依賴于選擇什么樣的目標(biāo)函數(shù)，另一方面要依靠算法的執(zhí)行。目標(biāo)函數(shù)是用來對比對結(jié)果進(jìn)行衡量的一個打分機(jī)制。在序列比對的過程中，需要引入空位，空位的引入是為了補(bǔ)償那些插入或缺失，使序列的比對能更緊密地符合某種所期望的模型，但是在序列的比對中引入的空位不能不加限制，否則比對結(jié)果即使較高，也缺乏生物學(xué)依據(jù)。因此，必須有一種機(jī)制，對空位的引入加以限制。常用的方法就是空位罰分，即每插入一個空位，就在總分值中減去一定分值(叫罰分值)，即加上一負(fù)分值。因此，序列比對最終結(jié)果的得分值是兩個序列之間匹配殘基

19、的總分值與空位罰分的總和28。6.1.2 蟻群雙序列比對算法的設(shè)計對序列S=CAGGA和T=CGGTTA，仿照動態(tài)規(guī)劃法那樣陣建立矩陣(如圖1)。螞蟻從矩陣左上角出發(fā)選擇一條路線到達(dá)右下角，就形成一個比對，我們規(guī)定在水平或垂直方向上移動一格，表示在相應(yīng)的序列中插入一個空位，沿對角線移動一格表示到達(dá)的新位置對應(yīng)字符的匹配。圖1中的路線表示了如下比對結(jié)果：序列S：CAGG一一A序列T：CGG T T AC G G T T A C A G G A 圖1 單個螞蟻的行走路線與TSP問題不同，螞蟻在每個位置選擇移動方向的數(shù)目是固定的，總是向右，向下，沿對角線向右下三個方向，序列比對對加入的空位數(shù)量也有一

20、定要求。所以蟻群比對算法的設(shè)計與TSP問題有所不同。用 表示t時刻螞蟻在(i,j)位置上沿著k方向的路徑上的信息素濃度，k=1,2,3分別表示水平向右、垂直向下和沿對角線三個方向。螞蟻路徑選擇時的轉(zhuǎn)移概率計算：螞蟻從矩陣左上角出發(fā)，每走一步都要根據(jù)當(dāng)前位置可選擇的各條路徑上的信息素濃度以及啟發(fā)信息決定下一個移動的方向。這里的啟發(fā)信息包括表示字符匹配程度的矩陣D及方向權(quán)值d。 (3)螞蟻在路徑選擇時采用的策略是：首先設(shè)定，然后產(chǎn)生一個隨機(jī)數(shù)，當(dāng)這個隨機(jī)數(shù)小于時,選擇對角線方向移動；當(dāng)這個隨機(jī)數(shù)大于時，計算三個方向的概率 ，然后用輪盤賭法在三個方向中選擇一個移動。當(dāng)所有的螞蟻通過不同的路線到達(dá)矩陣

21、右下角，得到一組比對結(jié)果，就完成了尋找最優(yōu)路線的一次循環(huán)。這時要對每條路徑的信息素進(jìn)行全局更新。信息素的更新公式如下： (4) （5） 其中canshu為信息素增量轉(zhuǎn)化參數(shù)，它用來將比對得分小于0的分?jǐn)?shù)轉(zhuǎn)化成正數(shù)增量，Q為信息素增加強(qiáng)度系數(shù)。6.1.3 改進(jìn)的蟻群雙序列比對算法蟻群算法通過正反饋機(jī)制來強(qiáng)化較好的解，但容易出現(xiàn)停滯，陷入局部最優(yōu)解29。針對這個問題，提出自適應(yīng)調(diào)整信息素的方法，根據(jù)解的搜索情況，動態(tài)地調(diào)整信息素的分配。采用式(6)的時變函數(shù)Q(t)來代替式(5)中的常數(shù)Q。進(jìn)化初期為了增大搜索空問，Q(t)取較小的值，隨著算法的推進(jìn)取值逐步增大，強(qiáng)化較好的解。在算法的仿真中，我們

22、采用Q1=0.0001，Q2=0.0005，Q3=0.001以及T1=30，T2=60。 (6)在陷入局部最優(yōu)解時，某條路徑上的信息素在數(shù)量上占絕對優(yōu)勢，因此我們對信息素的最大值和最小值進(jìn)行了限制，如規(guī)定，。限制最大值可以防止某條路線的信息素濃度過大，限制最小值可以防止搜索后期沒走過的路徑信息素濃度過低，使較差的路線被強(qiáng)化。為了鼓勵解質(zhì)量的改善，又不減小搜索空間，在進(jìn)化一定代數(shù)以后，采用式(7)根據(jù)解的情況動態(tài)地調(diào)整信息素的分配。若路線上取得的解(即比對得分)為Score，較目前得到的最優(yōu)解有所改善，則增大路線上的信息素增量的分配，并更新的值，若低于最優(yōu)解，則減小信息素增量的分配。 (7)如果

23、最優(yōu)解在幾代內(nèi)沒有改善，則可以適當(dāng)減小要添加的信息素，以求擺脫局部最優(yōu)解。6.2 多序列比對6.2.1 多序列比對問題描述多重序列的某個比對30實際上就是多個序列之間的一種排列方式。圖2 是六個蛋白質(zhì)序列片段的多重比對的例子。我們用字符 “ -” 表示插入的空位。- GRRRSVOWCAVSNPEATKCFOWORNMRKVR - GPPVSCLKRDSPIOCIOAI- KTVRWCAVNDHEASKCANFRDSMKKVLPEDGPRIICVKKASYLDCIKAI- VKWCVKSEOELRKCHDLAAKVAE - FSCVRKDGSFECIOAI- KEKOVRWCVKSNSELKK

24、CKDLVDTCKNK - EIKLSCVEKSNTDECSTAI- EVRWCATSDPEOHKCGNMSEAFREAGI - OPSLLCVRGTSADHCVOLIAPPKTTVRWCTISSAEEKKCNSLKDHMOOER - VTLSCVOKATYLDCIKAI圖2 多重序列比對對于一個比對，可以用SP模型對它打分以評價比對的好壞。我們假設(shè)得分函數(shù)具有加和性， 即多重比對的得分是各列得分總和那么，我們首先考慮如何給比對的每一列打分。 對于一列字符打分可用SP函數(shù)，SP函數(shù)定義為一列中所有字符對得分之和： (8)其中，表示該列中的第個字符，表示字符和字符比較所得分值。將各列的分值加起來

25、就成為比對的總得分。我們進(jìn)行序列多重比對的目標(biāo)是要在許多比對方案中，尋找得分最高的比對和在此比對的分值，以其代表序列之間的相似性。6.2.2 蟻群多序列比對算法的設(shè)計設(shè)有N個序列，其中第i個序列長度為，我們將序列中的字符看作是螞蟻所要走過路徑上的節(jié)點(diǎn)。算法首先對序列1 分配一個螞蟻，令螞蟻從序列1中的第一個字符出發(fā)， 依次選擇序列 2，序列N中的某個字符（即節(jié)點(diǎn)）與之匹配。選擇的概率取決于字符的匹配程度、 匹配的位置偏差以及路徑上的信息素。螞蟻也能以一定的概率選擇一個空位插入序列中的某個位置。在完成第一個字符的匹配后，便得到一條路徑。這條路徑所經(jīng)過的各個序列中的字符便為與序列1第一個字符相匹配

26、的字符。螞蟻接著從序列1中的第二個字符出發(fā)， 再依次選擇其他序列中的節(jié)點(diǎn)或空位與之匹配，如此處理序列1中的各個字符。在螞蟻選擇路徑時，不允許出現(xiàn)線段交叉的情況，因為這意味著不可能的比對。當(dāng)螞蟻走完時，便得到條路徑所對應(yīng)的一個比對。其他螞蟻也以同樣的方式選擇各自的路徑集合。為了使解具有多樣性，這些螞蟻的處理過程不一定都從序列1開始，我們均勻地分布各個螞蟻的開始序列。從第i條序列開始的螞蟻，從序列i中的字符出發(fā)， 依次選擇序列 i+ 1，i+ 2， ，N，1，2， ，i- 1 中的某字符（即節(jié)點(diǎn)）與之匹配。通過螞蟻求出的每個路徑集合， 我們可找出對應(yīng)的一個比對， 路徑中的節(jié)點(diǎn)便是螞蟻所選擇的相匹配

27、的字符。對于不在路徑上的字符， 我們可以用其他方法簡單地求出它們在比對中的位置， 如靠左對齊、 右邊加空位， 以得到一個完整的比對。在所有螞蟻完成路徑的集合后， 算法根據(jù)打分機(jī)制求出各個比對的得分， 根據(jù)分值的高低對路徑上的信息素進(jìn)行更新以增大分值高的路徑上的信息素。這樣當(dāng)下一個螞蟻選擇節(jié)點(diǎn)時， 就以新的信息素作為選擇的依據(jù)， 從而構(gòu)成信息學(xué)習(xí)的正反饋機(jī)制。概率選擇公式設(shè)在第k個序列的第l個字符選擇第n個序列中的第m個字符的概率為: （9）其中，是在第個序列的第個字符處選擇第個序列的第個字符的信息素指標(biāo)；是第個序列的第個字符和第個序列的第個字符的匹配得分； 是第個序列的位置與第個序列的第個字符

28、選擇的第個序列的字符位置的偏差；分別為信息素、 匹配程度、 位置偏差三個指標(biāo)相應(yīng)的重要性參數(shù)；）是從第個序列的第個字符出發(fā)選擇第個序列中的字符時起始的字符位置； 是允許最大的字符選擇的范圍參數(shù)。這樣的概率公式可以使得信息素較高、 匹配程度較好且相對位置偏離較小的字符被選中的概率較大。螞蟻字符選擇方法在第個序列的第 個字符選擇第個序列中某個字符時，首先對允許范圍內(nèi)的所有字符計算選擇概率， 得到使得選擇概率最大的字符，如果，則選擇該字符；否則以一定的概率選擇空位， 以剩余的概率選擇字符。信息素的全局更新設(shè)定信息素全局更新的蒸發(fā)系數(shù)為evap1，每當(dāng)一個螞蟻走完得到一個比對時，對螞蟻所經(jīng)過的所有節(jié)點(diǎn)

29、上的信息素按式（10）進(jìn)行更新。 (10)信息素的調(diào)節(jié)在經(jīng)歷了一定代數(shù)以后，由于信息素的漸漸集中，算法會陷入局部最優(yōu)。為了解決這個問題，我們采取了以下措施：預(yù)先設(shè)定參數(shù) start，在第 start 代以后， 若某代中螞蟻得到的比對得分不高于前d代螞蟻得到的比對得分（start， d都是可調(diào)節(jié)的參數(shù)），則對信息素進(jìn)行局部更新。更新策略是對于信息素高于某一閾值的路徑上的信息素，依據(jù)一定的蒸發(fā)系數(shù)evap2進(jìn)行蒸發(fā)，使得下一代的螞蟻盡量選擇沒走過的路徑去走。6.2.3 改進(jìn)的蟻群多序列比對算法（1） 蟻巢食物源的往返策越31由于多條序列的長度不一致，而且不同序列間比對是一定字符范圍的概率選擇，造成

30、了從蟻巢到食物端和食物端到蟻巢的比對過程是不對稱的，因此可以通過蟻巢食物源的往返策越，來增加尋優(yōu)空間。（2）隨機(jī)分配螞蟻的起始序列螞蟻在開始新的一列比對時，采用隨機(jī)的方式分配螞蟻的起始序列，使得在比對的過程中，不會偏向任何一條序列，而是把多條序列作為一個整體來進(jìn)行比對。（3）分治策略與蟻群算法結(jié)合32為降低多重序列比對的計算量，可以采用分治策略將序列集在適當(dāng)?shù)奈恢脛澐殖扇舾蓚€由較短序列構(gòu)成的子序列集，然后對各個子序列集用蟻群算法求解比對。7 討論與結(jié)束語本文首先詳細(xì)闡述了蟻群算法的基本原理、各種改進(jìn)技術(shù)及收斂性分析，然后對蟻群算法在序列比對中的應(yīng)用進(jìn)行了詳細(xì)的研究和分析，針對蟻群算法容易陷入局

31、部最優(yōu)的缺陷，分別指出了蟻群算法在雙序列比對和多序列比對中的多種改進(jìn)方案。蟻群算法收斂速度分析是機(jī)器學(xué)習(xí)領(lǐng)域中的公開難題，收斂性分析理論僅僅告訴我們蟻群算法存在最終找到全局最優(yōu)解的可能性, 較難用于實際算法性能的對比評價. 只有對蟻群算法收斂速度進(jìn)行分析,才能知道算法求解最優(yōu)解的計算消耗時間. 在未來的工作中可集中研究提高蟻群算法收斂速度的參數(shù)優(yōu)化設(shè)計方法以及對比分析蟻群算法性能的理論與方法.同時, 可以考慮一次迭代的時間復(fù)雜度和ACO算法的輔助策略, 從而完善對收斂速度的分析。此外，蟻群算法的一個特點(diǎn)是易于并行化，基于蟻群算法的多重序列比對方法可以用簡單的策略實現(xiàn)算法的并行化，從而降低了算法

32、的運(yùn)算時間，提高求解效率。相信在今后的研究中，蟻群算法在序列分析以及生物信息學(xué)中其它領(lǐng)域的應(yīng)用前景會更加廣闊。參考文獻(xiàn)1 M Dorigo, V Maniezzo and A ColorniThe Ant System：Optimization by a colony of cooperating agentsJ. IEEE Transactions on Systems, Man, and Cybernetics-part B, 1996, 26(1):1-132 Colorni A，Dorigo M，Maniezzo V，et a1Distributed optimization by a

33、nt coloniesCIn：Proceedings of the 1 st European a Conference on Artificial Life Paris，F(xiàn)rance：Elsevier Publishing，1 99 1，1 34-1 423 Dorigo M，Gambardella L MAnt colonies for the traveling salesman problemJ BioSystems，1997，43(2)：73-814 Gambardella L M，Dorigo MAnt-Q：a reinforcement learning approach to

34、the traveling salesman problemCIn：Proceedings of the 1 2th International Conference on Machine LearningTahoe City，CA：Morgan Kaufman，1995，255-2605 Stfitzle T，Hoos H HMAX-MIN Ant SystemJFuture Generation Computer Systems，2000，16(9)：889-9146 吳慶洪，張紀(jì)會，徐心和具有變異特征的蟻群算法J計算機(jī)研究與發(fā)展，1999，36(10)：1240-12457 Socha

35、KACO for continuous and mixedvariable optimizationIn：Proc of the 4th International Workshop on Ant Colony Optimization and Swann IntelligenceBrussels，2004：300·308 PEI Jian，HAN Jiawei，MAO RunyingC10set：an efflcient algorimm for mining frequent closed itemsetsIn：Proc of the ACM SIGMOD Workshop on

36、 Research Issues in Data Mining and Knowledge DiscoveryDallas，rexas，2000：21-309 Alupoei S，Katkoori SAnt colony system application to macrocell oVerlap removalIEEE Trans on Vbry Large Scale Integration(VLSI)Systems，2004，1 2 (10)：1118-112210 Yu-Min Chiang, Huei-Min Chiang , Shang-Yi Lin. The applicati

37、on of ant colony optimization for gene selection in microarray-based cancer classification. Machine Learning and Cybernetics, 2008 International Conference on.2008, 7: 4001 - 400611 梁棟，霍紅衛(wèi). 自適應(yīng)蟻群算法在序列比對中的應(yīng)用. 計算機(jī)仿真，2005，22(1)：100-10612 陳娟，陳峻多重序列比對的蟻群算法計算機(jī)應(yīng)用，2006，26(1)：12412813 陳娟，陳峻漸進(jìn)方法結(jié)合蟻群算法求解多序列比對問

38、題計算機(jī)工程與應(yīng)用2006，42(21)：38-4214 Yixin Chen，Yi Pan，Juan Chen，Wei Liu，et a1Multiple seqence alignment by ant colony optimization and diVide-andconquefIn：Proc of ICCSBrelin，2006，646-65315 S R Jangam，N ChakrabortiA noVel method for alignment of two nucleic acid sequences using ant c010ny optimization and g

39、enetic algorithmsApplied Soft Computing，2007，7(3)：1121-113016 Lee Z J，Su S F，Chuang C C，et a1Genetic algorithm with ant colony optimization(GAACO)for multiple sequence alignmentJApplied Soft Computing，2008，8(1)：557817 吳斌，史忠植，一種基于蟻群算法 TSP 問題的求解方法，計算機(jī)學(xué)報，2001，24(12)：1328-1333。18 Gutjahr W J . A general

40、ized convergence result for the graph-based ant system met aheuristic. Department of Statistics and Decision Support Systems, University of Vienna, Austria:Technical Report 9 -09, 199919 Gutjahr W J. A graph-based ant system and its convergence.Future Generation Computer Systems, 2000, 16 ( 9 ) : 873 -88820 Gutjahr W J . ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002, 82( 3) : 145 -15321 Sttzle T , Dorigo M. A short convergence proof for a class of ant colony opimization alg