算法分析与设计

算法设计和分析报告蚁群算法及其在序列比对中的应用综述教员：* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *等级：* * * * * * * * * * * * * * * * *姓氏：* * * * * * *学校编号：* * * * * * * * * * * * * * * * *讲师：* * * * * * * * * * * * * *2016年11月20日蚁群算法及其在序列比对中的应用研究综述摘要蚁群算法是一种新型仿生进化算法。蚂蚁算法作为一种全局搜索方法，具有正反馈、并行、分布式、自组织等特点。自提出以来，它在解决复杂的组合优化问题方面显示出强大的优势。序列比对是生物信息学的基础。通过获得大量序列比对信息，可以推断基因的结构、功能和进化关系。本文首先详细介绍了蚁群算法的基本原理、各种改进技术和收敛性分析，然后对蚁群算法在双序列比对和多序列比对中的应用研究进行了总结和评价，最后指出了下一步的研究方向。关键词：蚁群算法；序列比对；信息素介绍蚂蚁算法是源于自然界生物世界的一种新型仿生算法。作为一种通用的随机优化方法，它吸收了昆虫王国中蚂蚁的行为特征，并通过其固有的搜索机制解决了一系列困难的组合优化问题。因为模拟中使用了人工蚂蚁的概念，所以它有时被称为蚂蚁系统。根据昆虫学家的观察和研究，生物世界中的蚂蚁能够在没有任何可见提示的情况下找到从它们的巢穴到食物来源的最短路径，并且能够随着环境的变化而变化，适应性地寻找新的路径并产生新的选择。在寻找食物来源时，蚂蚁作为昆虫可以在它们行走的道路上释放一种信息素，这是蚂蚁特有的分泌物，这样在一定范围内的其他蚂蚁就可以发现并影响它们以后的行为。当越来越多的蚂蚁通过一些路径时，它们会留下越来越多的信息素踪迹，这增加了信息素的强度(随着时间的推移逐渐减少)。后来，蚂蚁选择路径的概率也更高，从而增加了路径的信息素强度。这个选择过程被称为蚂蚁自催化行为。因为它的原理是正反馈机制，蚁群系统也可以理解为一个增强的学习系统。蚁群算法是意大利学者M.Dorigo等人在20世纪90年代初提出的13。它发展至今已有十多年了。在这段时间里，人们对蚁群算法提出了一些改进方法。Dorigo等人提出了一种称为ant-q系统4的蚁群算法，它只更新每个周期中最短路径上的信息，并加强信息的反馈。德国学者斯图兹尔和胡斯提出了最大最小蚂蚁系统(MMAS) 5。MMAS定义了信息的上下限，并在算法中采用了轨迹平滑机制。直到今天，MMAS仍然是解决离散域优化问题的最佳蚁群算法模型之一，如TSP和QAP。蚁群算法的许多改进策略都渗透了MMAS的思想。此外，国内学者吴庆红等人提出了一种具有变异特征的蚁群算法6，并在蚁群算法中引入了反向变异机制。蚁群算法具有鲁棒性好、并行分布式计算、易于与其他启发式方法结合等优点。它在短时间内得到了很大发展，其应用领域也在不断扩大710。目前，一些学者将蚁群算法应用于序列比对领域，其中董亮等人将蚁群算法应用于序列比对，提出了一种基于自适应信息素调整的改进算法11。结果表明，蚁群算法可以有效地应用于双序列比对。陈娟等人12，13提出了蚁群优化算法在多序列比较中的应用，以及进化算法与蚁群算法相结合在多序列比较中的应用，并取得了良好的效果。Yixin Chenl等人14提出了一种基于分割方法的蚁群多序列比对方法。该算法利用蚁群算法将序列垂直递归地划分成若干个子序列。詹甘姆等15在遗传算法中嵌入蚁群算法来解决双序列比对问题。Zne-Jung Le等人16将遗传算法和蚁群算法相结合来解决多序列比对问题。为了收集这些零散的文献和数据，本文对蚁群算法及其在序列比对中的应用进行了全面的综述。2蚁群算法的原理用于优化领域的人工蚂蚁算法的基本原理吸收了生物学中蚁群行为的一些显著特征：(1)检测小区域情况，判断是否有食物或其他类似的信息素痕迹；(2)释放信息素；(3)剩余信息素的数量将随着时间的推移而逐渐减少。因为自然界中的蚂蚁视力很差，既不知道去哪里寻找食物，也不知道在找到食物后如何返回它们的巢穴，它们只能依靠周围环境中同一物种分布的信息素来决定去哪里。有趣的是，尽管没有先验知识，蚂蚁仍然有能力找到从它们的巢穴到食物来源的最佳路线，即使在路线上设置了障碍，它们也能很快找到新的最佳路线。这里，用一个可视化的图2.01来说明蚁群路径搜索的原理和机制。图2.01蚂蚁从巢到食物来源的迁移假设障碍物周围有两条路从蚁巢到达食物源：巢-食物和巢-食物，长度分别为4和6。蚂蚁每单位时间可以移动一单位长度的距离。起初，所有的道路上都没有信息素。在时间t=0时，20只蚂蚁从它们的巢穴出发，向a移动。它们以相同的概率选择左边或右边的路，所以平均10只蚂蚁走左边，10只走右边。在时间t=4时，到达食物来源的第一群蚂蚁会返回。在时间t=5时，两组蚂蚁将在d点相遇。此时，BD上的信息素数量与CD上的相同，因为10只蚂蚁各自选择了相应的道路。因此，5只返回的蚂蚁将选择BD，另外5只选择CD。在时间t=8时，前5只蚂蚁将返回它们的巢，而在交流电、直流电和直流电上分别有5只蚂蚁。在时间t=9时，前5只蚂蚁回到a，再次面对左或右的选择。此时，AB上的轨迹数是20，AC上是15，所以更多的蚂蚁会选择离开，从而增强了路线的信息素。随着这一过程的继续，两条道路之间信息素数量的差异将变得越来越大，直到大多数蚂蚁选择最短的路线。正因为一条路比另一条路短，所以在相同的时间间隔内，较短的路线会有更多的选择机会。蚂蚁能够在没有任何提示的情况下找到从巢穴到食物来源的最短路径，并且能够随着环境的变化而变化，适应性地寻找新的路径并产生新的选择。最根本的原因是蚂蚁在寻找食物来源的过程中会释放信息素。随着时间的推移，这种物质会逐渐挥发。蚂蚁选择路径的概率与当时路径上物质的强度成正比。当更多的蚂蚁经过某条路径时，蚂蚁留下的信息素轨迹也越来越多。蚂蚁选择路径的概率也更高，因此增加了路径的信息素强度。强信息素会吸引更多的蚂蚁，从而形成正反馈机制。通过这种正反馈机制，蚂蚁最终可以找到最短的路径。特别是当蚁巢和食物源之间有障碍物时，蚂蚁不仅可以绕过障碍物，还可以通过改变不同路径的蚂蚁信息素轨迹，在一段时间的正反馈后收敛到最短路径。3基本蚁群算法流程基本蚁群算法可应用于基于图表示的组合优化问题(如旅行商问题)，其简单表达如下：初始化在开始时进行，10只蚂蚁随机放置在10个城市，城市之间的每条边都有一个初始信息素强度值。每只蚂蚁禁忌列表的第一个元素是它最初的城市。然后每只蚂蚁根据概率函数从一个城市到另一个城市(1)选择城市迁移的概率取决于城市之间的距离和信息素的强度。其中指示了边缘上信息素的强度；代表城市间距离一个因素，通常被认为是距离的倒数；集合和是控制信息素和可见度相对重要性的参数。可见转移概率是在时间t的可见性和信息素强度之间的折衷。n次循环后，填充所有蚂蚁的禁忌列表，计算每只蚂蚁行进的路径长度，找到最短路径并保存，记录路径并改变路径上的信息素。信息素更新的公式为：(2)(3)其中表示信息素消散的水平和第k只蚂蚁在时间t和t n之间在边缘(I，j)上留下的信息素的数量。如果第k只蚂蚁在时间t和t n之间经过边缘(I，j)，则(4)其中q是常数，是第k只蚂蚁行进的路径长度。重复这个过程，直到达到最大迭代次数，或者所有蚂蚁走相同的路线。后一种情况称为停滞。如果算法在数控循环后终止，蚂蚁算法的复杂度为。4改进的蚁群算法4.1最大和最小蚂蚁系统MMAS(最大最小蚂蚁系统)5是迄今为止解决TSP、QAP等问题的最佳蚁群算法。它的特点是只有外源激素的浓度增加了最佳途径，从而更好地利用历史信息；为了避免算法过早收敛到局部最优解，将每条路径可能的信息素浓度限制在，并强制将超出此范围的值设置为or，这样可以有效地防止一条路径上的信息含量远大于其他路径上的信息含量，使所有蚂蚁都集中在同一条路径上，从而使算法不再扩散。外源激素在每条路径中的初始浓度被设置为，以便可以更充分地进行优化。4.2相遇算法满足最大最小蚂蚁系统(MMMAS) 17的基本思想是将一只蚂蚁的行程分成两只蚂蚁，在路径中间相遇，形成一条行程路径。此外，由于蚂蚁在一个周期中旅行多次，并且最短的旅行影响路径信息素，所以在一次旅行中选择一个城市之后计算当前路径长度，并且如果长度超过在这个周期中获得的最小值，则旅行终止，从而进一步缩短计算时间。步骤如下：(1)初始化参数：(2)数控(3)一群蚂蚁开始执行相遇算法，