《算法分析与设计》由会员分享，可在线阅读，更多相关《算法分析与设计（20页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析报告 题目名称：蚁群算法及其在序列比对中的应用研究综述院 系： * 班 级： * 姓 名： * 学 号： * 指导教师： * 2016年11月20日蚁群算法及其在序列比对中的应用研究综述摘要蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价
2、，最后指出了下一步的研究方向。关键词：蚁群算法；序列比对；信息素1 引言蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦被称为蚂蚁系统(Ant System)。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物
3、信息激素(Pheromone)，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(Trail)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制，因此，也可将蚁群系统理解成增强型学习系统。蚁群算法由意大利学者MDorigo等人在20世纪90年代初提出来的13。发展到今天已经有十几年的路程，在这一段时间里人们不断的对蚁群算法提出一些改进方法。有Dorigo等人提出的一种称之为AntQ System
4、4的蚁群算法，该算法只让每次循环中的最短路径上的信息量作更新，强化了信息的反馈。德国学者Stutzle和Hoos提出了一种最大最小蚂蚁系统(MAX-MIN ant system，MMAS) 5，MMAS对信息量的上下界作了限定，并且在算法中采用了轨迹平滑机制。直到今天，MMAS仍然是解决TSP、QAP等离散域优化问题的最好蚁群算法模型之一，很多对蚁群算法的改进策略都渗透着MMAS的思想。另外还有国内的学者吴庆洪等人提出了一种具有变异特征的蚁群算法6，他们在蚁群算法中引入了逆转变异机制。蚁群算法具有较好的鲁棒性，并行分布式计算及易于与其他启发式方法结合等优点，在短期内得到了很大发展，其应用领域也
5、不断得到扩展710。目前已有一些学者将蚁群算法应用到序列比对这一领域当中，其中梁栋等人将蚁群算法应用于序列比对，并提出基于自适应调整信息素的改进算法11，其结果表明，蚁群算法可以有效地运用于双序列比对问题。陈娟等人12,13提出了蚁群优化算法在多序列比对中的应用及渐进算法结合蚁群算法在多序列比较中的应用，并取得了较好的效果。Yixin Chenl等人14提出了基于分割方法的蚁群多序列比对方法。该算法采用蚁群算法将递归地将序列分割成垂直分割成若干子序列。SRJangam等人15 在遗传算法中嵌入使用了蚁群算法来解决双序列比对问题。Zne-Jung Le等人16结合了遗传算法和蚁群算法来解决多序列
6、比对问题。为了将这些分散的文献和资料集中起来,本文对蚁群算法及其在序列比对中的应用研究进行了较全面地综述。2 蚁群算法的原理用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征：(1) 察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹；(2) 释放自己的信息素；(3) 所遗留的信息素数量会随时间而逐步减少。由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取食物，也不知发现食物后如何返回自己的巢穴，因此它们仅仅依赖于同类散发在周围环境中的信息素，来决定自己何去何从。有趣的是，尽管没有任何先验知识，但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径，甚至在
7、该路线放置障碍物之后，它们仍然能很快重新找到新的最佳路线。这里，用一个形象化的图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上的相同，因
8、为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择BD而另5只将选择CD。在t=8时刻，前5个蚂蚁将返回巢穴，而AC，CD和BD上各有5个蚂蚁。在t=9时刻，前5个蚂蚁又回到A并且再次面对往左还是往右的选择。这时，AB上的轨迹数是20而AC上是15，因此将有较多数的蚂蚁选择往左，从而增强了该路线的信息素。随着该过程的继续，两条道路上信息素数量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线会有更多的机会被选择。蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性的搜索新的路
9、径，产生新的选择。其根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比，当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。3 基本蚁群算法的过程基本的蚁群算法可以应
10、用于基于图表示的组合优化问题中（如 TSP），其简单表述如下：在起始时刻进行初始化，将个蚂蚁随机放在个城市上，城市间的每一条边都有一个初始外激素强度值。每个蚂蚁的禁忌表的第一个元素为其初始城市。然后每个蚂蚁从城市到城市，依据概率函数 (1)选择将要移动的城市，这个概率取决于城市间的距离和信息素的强度。其中表示边上信息素的强度；表示城市间距离因子，通常取为距离的倒数；集合，和都是控制信息素与可见度的相对重要性的参数。可见转移概率是可见度和t时刻信息素强度的权衡。在n次循环后，所有蚂蚁的禁忌表都填满后，计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改该路径上的信息素 。信息素更新
11、的公式是：(2)(3)其中表示在某条边上的累加新增信息素的和，表示信息素消散的等级，表示在时刻t和t+ n之间第k个蚂蚁在边(i ,j)留下的信息素的数量。如果在时刻t和t+n之间第k个蚂蚁经过边(i,j)，则 (4)其中Q 为常量，为第k个蚂蚁周游的路径长度。这一过程重复直至达到最大迭代次数结束，或者所有蚂蚁都走同一路线。后一种情况被称为停滞状态。如果算法在NC次循环后终止，蚂蚁算法的复杂度为。4 改进的蚁群算法4.1最大最小蚂蚁系统MMAS(Max Min Ant System) 5是到目前为止解决 TSP、QAP 等问题最好的ACO 类算法。其特点在于：只对最佳路径增加外激素的浓度，从而
12、更好地利用了历史信息；为了避免算法过早收敛于局部最优解，将各条路径可能的外激素浓度限制于，超出这个范围的值被强制设为或者，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；将各条路径上外激素的起始浓度设为，这样便可以更加充分地进行寻优。4.2相遇算法相遇算法(Meet Max Min Ant System，MMMAS) 17的基本思路是将一只蚂蚁的一次周游分由两只蚂蚁分头进行，在路径中间相遇合成一次周游路径。此外，由于在一次循环中，蚂蚁进行多次周游，最短的一次周游影响路径信息素，因此，在一次周游中，选择一个城市后，即计算当前路径长度，如果长
13、度超过本次循环已得到的最小值即终止此次周游，这样可以进一步缩短计算时间。其步骤如下：(1) 初始化参数：(2) NC+(3) 一组蚂蚁开始执行相遇算法，循环变量k+(i) 两只蚂蚁选择同一起点城市，建立禁忌表(ii) 其中一只蚂蚁以式(1)计算的转移概率选择一个城市(iii) 另一只蚂蚁也以式(1)计算的转移概率选择一个城市(iv) 判断当前路径长度，如果大于本次相遇算法m组蚂蚁已找到的最短路径则终止此次两只蚂蚁周游，continue(v) 判断禁忌表，如果未满，转至(ii)(vi) 2-opt局部优化路径（可选） (4) 如果km转至(3)(5) 计算本次m组蚂蚁相遇循环的最短路径，置空禁忌
14、表(6) 用式(2)(4)更新路径信息素（最短路径增加，其他衰减） (7) 如果NC小于且未进入停滞状态，转至(2)(8) 输出最优解，算法停止.从算法描述可以看出，一次周游的两只蚂蚁共用一个禁忌表，这样保证两只蚂蚁不会选择重复的城市。5 蚁群算法的收敛速度分析应用研究的发展促进了学者们对蚁群算法理论的研究,主要内容在于算法数学模型、收敛性和收敛速度的分析. Gutjah针对一种特殊的蚁群算法(graph-based ant system)建立了概率转换模型, 并分析了该算法收敛的条件1820. 受此结果的启发Sttzle和Dorigo21进一步给出了保证蚁群算法收敛的一般性条件:最优解路径对
15、应信息素的下确界应大于0,以确保算法至少有一次找到全局最优解这个结论对于绝大多数蚁群算法的分析都是合适的,不过结论的证明类似于对非启发式随机搜索算法的分析,对算法性能评价以及设计方面的指导意义不明显. Dorigo等又将蚁群算法的收敛性分为两种类型22,23: (1) 值收敛(convergence in value) , 即当迭代时间趋于无穷时, 蚁群算法至少一次达到最优解; (2) 解收敛(convergence in solution) ,即当迭代时间趋于无穷时,蚁群算法找到最优解的概率趋于1.两种收敛性的证明22都类似于文献21的分析,结论充实了蚁群算法的收敛性理论.上面主要是基于概率模型的收敛性分析, 国内外学者还从
