自適應蟻群算法在DNA序列比對中的應用
頁數(shù) 25 字數(shù) 12644

[摘要]
本文對標準蟻群算法、MMAS蟻群算法、自適應蟻群算法做了較詳細系統(tǒng)的總結，其中主要討論了自適應蟻群算法在DNA序列比對中的應用，主要的過程是：首先，我們設一個計分函數(shù)和一個得分策略，在任意給出一對DNA序列，建立一個序列比對矩陣?，F(xiàn)由4只螞蟻從左上角向右下角移動，并且最終到達右下角，那么這4只螞蟻隨意走出4條路徑，根據(jù)4條路徑得出4對等長的比對，再依照計分函數(shù)分別計算出4條路徑的比對得分，再由5.3式進一步驗證4條路徑的平均得分值，取其中得分最高（即最優(yōu)路徑）路徑；進行第二次信息素增量的調整，方法是根據(jù)螞蟻所走過的方向和該方向上得分比例計算出來的，信息素的變化量利用矩陣來存儲，那么下一次螞蟻所選的路徑就要根據(jù)以前在各條路徑上的信息素濃度總和的大小選擇移動方向，最終經過有限次迭代，螞蟻就會找到一條最優(yōu)路徑，也就是一條與原來DNA最相似的DNA鏈。


[關鍵詞] 標準蟻群算法，MMAS算法，自適應蟻群算法，DNA序列比對



目錄
1.引言……………………………………………………...……………………………………………..3
2 標準蟻群算法…………………………………………………………………………...…….3
2.1標準蟻群算法的原理……………………………………………….………...3
2.2標準蟻群算法的實現(xiàn)………………………………………….…………...…5
2.3標準蟻群系統(tǒng)的優(yōu)缺點………………………….………….........…......….7
2.3.1基本蟻群算法的優(yōu)點............................................................8
2.3.2基本蟻群算法的缺點…........................................................9
3.標準蟻群算法和MMAS(max-min ant system)蟻群算法….....8
3.1MMAS的概念…………………………………………………………...…………..…8
3.2AS與MMAS的對比………………………………………………………………..8
3.3MMAS和AS的區(qū)別………………………………………………………….….…8
3.4最好、最壞路徑信息素全局更新策略…………………...………...13
3.5MMAS蟻群算法的特點…………………………………………………….…...10
4.自適應蟻群算法……………...……………………………………………………….….….10
4.1.自適應蟻群算法的概述………………………………………...…….….…11
4.2.自適應的信息更新策略………………………………………........………..11
4.2.1引題…………………………………………………………….…....….12
4.2.2改進的蟻群算法實現(xiàn)過程……………………….……….12
4.2.3自適應蟻群算法的穩(wěn)定性和收斂性………….........13
5.自適應蟻群算法在DNA中的應用...........................................................................14
5.1序列比對…………………………………………..……………………..…….….…..14.
5.2自適應蟻群算法和DNA的聯(lián)系…………….……..……………….........15
6.結束語………………………………………………………………………..………………...….....22
致謝………………………………………………………………………………………………………...23
參考文獻…………………………………………………………………………………..….……...…24

參考文獻
[1]LORNILBE RTO, DORIGOM, MANIEZZO,Distributed optimization by ant colonies[c.proc,of the First European Conf on Artificial Life.Paris: Elsevier Publishing,1991,134—142.
[2]Dorigo M,Di Caro G.Ant Colony Optimization:A New Meta-Heuristie[J],Proceedings of the Evolutionary Computation,Washington DC,1999:1470~1477.
[3]Hidenori KAWAMURA, Masahito YAMAMOTO,KEIJI SUZUKI et Multiple ANT Colonies Algorithm Based on Colony Level interactions[J] IEEE TRANS Fundamentals,2000,E83—A(2).
[4]Christian Blum, Andrea Roli, Marco Dorgio, HC-ACO the Hyper—Cube Framework for ANT Colony Optimization[C].In:MIc 2001—4th Metaheuristcs，International Conference,2001:16—20.
[5]Fstutzle.H Hoose The Ant system and local search for traveling saleman problem[C], Proceeding of ICEC’97 IEEE 2000,33—50.