蚁群算法及其在序列比对中的应用研究综述 摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。 关键词：蚁群算法；序列比对；信息素 Abstract: Ant colony algorithm (ACA) is a novel bionic evolutionary algorithm. As a global searching approach，ACA has some characteristic，such as positive feedback, distributing，paralleling, self-organizing, etc，and from it was introduced, it has been used to solve all kinds of complex optimization problem. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes. In this paper, the basic principles of ACA are introduced at length, and various improvements and convergence Analysis of ACA are also presented. Then the current study of double sequence alignment and multiple sequence alignment based on ant colony algorithm are reviewed and evaluated. Finally, some future research directions about ACA are proposed. Key words: Ant Colony Algorithm; Sequence Alignment; Pheromone

1 引言

蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦被称为蚂蚁系统(Ant System)。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物——信息激素(Pheromone)，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(Trail)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强蚁群算法及其在序列比对中的应用研究综述 度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制，因此，也可将蚁群系统理解成增强型学习系统。 蚁群算法由意大利学者M．Dorigo等人在20世纪90年代初提出来的[1~3]。发展到今天已经有十几年的路程，在这一段时间里人们不断的对蚁群算法提出一些改进方法。有Dorigo等人提出的一种称之为Ant—Q System[4]的蚁群算法，该算法只让每次循环中的最短路径上的信息量作更新，强化了信息的反馈。德国学者Stutzle和Hoos提出了一种最大最小蚂蚁系统(MAX-MIN ant system，MMAS) [5]，MMAS对信息量的上下界作了限定，并且在算法中采用了轨迹平滑机制。直

到今天，MMAS仍然是解决TSP、QAP等离散域优化问题的最好蚁群算法模型之一，很多对蚁群算法的改进策略都渗透着MMAS的思想。另外还有国内的学者吴庆洪等人提出了一种具有变异特征的蚁群算法[6]，他们在蚁群算法中引入了逆转变异机制。蚁群算法具有较好的鲁棒性，并行分布式计算及易于与其他启发式方法结合等优点，在短期内得到了很大发展，其应用领域也不断得到扩展[7~10]。 目前已有一些学者将蚁群算法应用到序列比对这一领域当中，其中梁栋等人将蚁群算法应用于序列比对，并提出基于自适应调整信息素的改进算法[11]，其结果表明，蚁群算法可以有效地运用于双序列比对问题。陈娟等人[12,13]提出了蚁群优化算法在多序列比对中的应用及渐进算法结合蚁群算法在多序列比较中的应用，并取得了较好的效果。Yixin Chenl等人[14]提出了基于分割方法的蚁群多序列比对方法。该算法采用蚁群算法将递归地将序列分割成垂直分割成若干子序列。S．R．Jangam等人[15] 在遗传算法中嵌入使用了蚁群算法来解决双序列比对问题。Zne-Jung Le等人[16]结合了遗传算法和蚁群算法来解决多序列比对问题。为了将这些分散的文献和资料集中起来,本文对蚁群算法及其在序列比对中的应用研究进行了较全面地综述。

2 蚁群算法的原理

用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征： (1) 察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹； (2) 释放自己的信息素； (3) 所遗留的信息素数量会随时间而逐步减少。 由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取食物，也不知发现食物后如何返回自己的巢穴，因此它们仅仅依赖于同类散发在周围环境中的信息素，来决定自己何去何从。有趣的是，尽管没有任何先验知识，但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径，甚至在该路线放置障碍物之后，它们仍然能很快重新找到新的最佳路线。这里，用一个形象化的图2.01来说明 蚂蚁群体的路径搜索原理和机制。 图2.01蚂蚁从蚁穴移至食物源 假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源：Nest-ABD-Food和Nest-ACD-Food，分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。在t=0时刻，20只蚂蚁从巢穴出发移动到A。它们以相同概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，10只走右侧。在t=4时刻，第一组到达食物源的蚂蚁将折回。在t=5时刻，两组蚂蚁将在D点相遇。此时BD上的信息素数量与CD上的相同，因为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择BD而另5只将选择CD。在t=8时刻，前5个蚂蚁将返回巢穴，而AC，CD和BD上各有5个蚂蚁。在t=9时刻，前5个蚂蚁又回到A并且再次面对往左还是往右的选择。这时，AB上的轨迹数是20而AC上是15，因此将有较多数的蚂蚁选择往左，从而增强了该路线的信息素。随着该过程的继续，两条道路上信息素数量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线会有更多的机会被选择。 蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性的搜索新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比，当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最蚁群算法及其在序列比对中的应用研究综述 终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。

3 基本蚁群算法的过程

基本的蚁群算法可以应用于基于图表示的组合优化问题中（如 TSP），其简单表述如下：在起始时刻进行初始化，将m个蚂蚁随机放在n个城市上，城市间的每一条边都有一个初始外激素强度值)0(ij。每个蚂蚁k的禁忌表kTabu的第一个元素为其初始城市。然后每个蚂蚁从城市i到城市j，依据概率函数

(1) 选择将要移动的城市，这个概率取决于城市间的距离和信息素的强度。其中)(tij表示边),(ji上信息素的强度；ij表示城市间距离因子，通常取为距离的倒

数；集合}{},,2,1{kkTabunallowed，α和β都是控制信息素与可见度的相对重要性的参数。可见转移概率是可见度和t时刻信息素强度的权衡。 在n次循环后，所有蚂蚁的禁忌表都填满后，计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改该路径上的信息素 。信息素更新的公式是：

(2) (3) 其中ij表示在某条边上的累加新增信息素的和，ρ表示信息素消散的等级，kij



表示在时刻t和t+ n之间第k个蚂蚁在边(i ,j)留下的信息素的数量。如果在时刻t和t+n之间第k个蚂蚁经过边(i,j)，则

(4) 其中Q 为常量，kL为第k个蚂蚁周游的路径长度。 这一过程重复直至达到最大迭代次数maxNC结束，或者所有蚂蚁都走同一路线。后一种情况被称为停滞状态。如果算法在NC次循环后终止，蚂蚁算法的复





,0,][)]([][)]([)(kallowedsisisijijkijallowedjt

t

tpk





lkkijij1

ijijijtt.1





0),(,jiedgeant

L

Q

kkk

ij