自适应蚁群算法在dna序列比对中的应用.doc

自适应蚁群算法在DNA序列比对中的应用
页数 25 字数 12644

[摘要]
本文对标准蚁群算法、MMAS蚁群算法、自适应蚁群算法做了较详细系统的总结，其中主要讨论了自适应蚁群算法在DNA序列比对中的应用，主要的过程是：首先，我们设一个计分函数和一个得分策略，在任意给出一对DNA序列，建立一个序列比对矩阵。现由4只蚂蚁从左上角向右下角移动，并且最终到达右下角，那么这4只蚂蚁随意走出4条路径，根据4条路径得出4对等长的比对，再依照计分函数分别计算出4条路径的比对得分，再由5.3式进一步验证4条路径的平均得分值，取其中得分最高（即最优路径）路径；进行第二次信息素增量的调整，方法是根据蚂蚁所走过的方向和该方向上得分比例计算出来的，信息素的变化量利用矩阵来存储，那么下一次蚂蚁所选的路径就要根据以前在各条路径上的信息素浓度总和的大小选择移动方向，最终经过有限次迭代，蚂蚁就会找到一条最优路径，也就是一条与原来DNA最相似的DNA链。


[关键词] 标准蚁群算法，MMAS算法，自适应蚁群算法，DNA序列比对



目录
1.引言……………………………………………………...……………………………………………..3
2 标准蚁群算法…………………………………………………………………………...…….3
2.1标准蚁群算法的原理……………………………………………….………...3
2.2标准蚁群算法的实现………………………………………….…………...…5
2.3标准蚁群系统的优缺点………………………….………….........…......….7
2.3.1基本蚁群算法的优点............................................................8
2.3.2基本蚁群算法的缺点…........................................................9
3.标准蚁群算法和MMAS(max-min ant system)蚁群算法….....8
3.1MMAS的概念…………………………………………………………...…………..…8
3.2AS与MMAS的对比………………………………………………………………..8
3.3MMAS和AS的区别………………………………………………………….….…8
3.4最好、最坏路径信息素全局更新策略…………………...………...13
3.5MMAS蚁群算法的特点…………………………………………………….…...10
4.自适应蚁群算法……………...……………………………………………………….….….10
4.1.自适应蚁群算法的概述………………………………………...…….….…11
4.2.自适应的信息更新策略………………………………………........………..11
4.2.1引题…………………………………………………………….…....….12
4.2.2改进的蚁群算法实现过程……………………….……….12
4.2.3自适应蚁群算法的稳定性和收敛性………….........13
5.自适应蚁群算法在DNA中的应用...........................................................................14
5.1序列比对…………………………………………..……………………..…….….…..14.
5.2自适应蚁群算法和DNA的联系…………….……..……………….........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.