蚁群算法及其在序列比对中的应用研究综述
蚁群算法及其在序列比对中的应用研究综述摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。
关键词：蚁群算法；序列比对；信息素
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 的禁忌表k Tabu 的第一个元素为其初始城市。然后每个蚂蚁从城市i 到城市j ，依据概率函数
(1) 选择将要移动的城市，这个概率取决于城市间的距离和信息素的强度。其中)(t ij τ表示边),(j i 上信息素的强度；ij η表示城市间距离因子，通常取为距离的倒数；集合}{},,2,1{k k Tabu n allowed -= ，α和β都是控制信息素与可见度的相对重要性的参数。可见转移概率是可见度和t 时刻信息素强度的权衡。
在n 次循环后，所有蚂蚁的禁忌表都填满后，计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改该路径上的信息素 。信息素更新的公式是：
(2)
(3) 其中ij τ?表示在某条边上的累加新增信息素的和，ρ表示信息素消散的等级，k ij
τ?表示在时刻t 和t+ n 之间第k 个蚂蚁在边(i ,j)留下的信息素的数量。如果在时刻t 和t+n 之间第k 个蚂蚁经过边(i,j)，则
(4) 其中Q 为常量，k L 为第k 个蚂蚁周游的路径长度。
这一过程重复直至达到最大迭代次数max NC 结束，或者所有蚂蚁都走同一路线。后一种情况被称为停滞状态。如果算法在NC 次循环后终止，蚂蚁算法的复
???????∈=∑∈,0,]
[)]([][)]([)(k allowed s is is ij ij k ij allowed j t t t p k βαβ
αητητ∑=?=?l
k k ij
ij 1ττ()()ij
ij ij t t ττρτ?+=+.1?????∈=?0),(,j i edge ant L Q k k k ij τ
杂度为)(2m n NC O ??。
4 改进的蚁群算法
4.1最大最小蚂蚁系统
MMAS(Max Min Ant System) [5]是到目前为止解决 TSP 、QAP 等问题最好的ACO 类算法。其特点在于：只对最佳路径增加外激素的浓度，从而更好地利用了历史信息；为了避免算法过早收敛于局部最优解，将各条路径可能的外激素浓度限制于[min τ，max τ]，超出这个范围的值被强制设为min τ或者m a x τ，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；将各条路径上外激素的起始浓度设为max τ，这样便可以更加充分地进行寻优。
4.2相遇算法
相遇算法(Meet Max Min Ant System ，MMMAS) [17]的基本思路是将一只蚂蚁的一次周游分由两只蚂蚁分头进行，在路径中间相遇合成一次周游路径。此外，由于在一次循环中，蚂蚁进行多次周游，最短的一次周游影响路径信息素，因此，在一次周游中，选择一个城市后，即计算当前路径长度，如果长度超过本次循环已得到的最小值即终止此次周游，这样可以进一步缩短计算时间。其步骤如下：
(1) 初始化参数：m Tabu NC k ,,],0[,,,,min max max ττρβα
(2) NC++
(3) 一组蚂蚁开始执行相遇算法，循环变量k++
(i) 两只蚂蚁选择同一起点城市，建立禁忌表k Tabu
(ii) 其中一只蚂蚁以式(1)计算的转移概率选择一个城市1j
{}k Tabu n j -∈,,2,1//1
(iii) 另一只蚂蚁也以式(1)计算的转移概率选择一个城市2j
{}{}12,,2,1//j Tabu n j k --∈
(iv) 判断当前路径长度，如果大于本次相遇算法m 组蚂蚁已找到的最短路
径则终止此次两只蚂蚁周游，continue
(v) 判断禁忌表，如果未满，转至(ii)
(vi) 2-opt 局部优化路径（可选）
(4) 如果k (5) 计算本次m 组蚂蚁相遇循环的最短路径，置空禁忌表 (6) 用式(2)~(4)更新路径信息素（最短路径增加，其他衰减） (7) 如果NC 小于m a x NC 且未进入停滞状态，转至(2) (8) 输出最优解，算法停止. 从算法描述可以看出，一次周游的两只蚂蚁共用一个禁忌表，这样保证两只蚂蚁不会选择重复的城市。 5 蚁群算法的收敛速度分析 应用研究的发展促进了学者们对蚁群算法理论的研究,主要内容在于算法数学模型、收敛性和收敛速度的分析. Gutjah 针对一种特殊的蚁群算法(graph-based ant system)建立了概率转换模型, 并分析了该算法收敛的条件[18~20]. 受此结果的启发Sttzle 和Dorigo [21]进一步给出了保证蚁群算法收敛的一般性条件:最优解路径对应信息素的下确界应大于0,以确保算法至少有一次找到全局最优解这个结论对于绝大多数蚁群算法的分析都是合适的,不过结论的证明类似于对非启发式随机搜索算法的分析,对算法性能评价以及设计方面的指导意义不明显. Dorigo 等又将蚁群算法的收敛性分为两种类型[22,23]: (1) 值收敛(convergence in value) , 即当迭代时间趋于无穷时, 蚁群算法至少一次达到最优解; (2) 解收敛(convergence in solution) ,即当迭代时间趋于无穷时,蚁群算法找到最优解的概率趋于 1.两种收敛性的证明[22]都类似于文献[21]的分析,结论充实了蚁群算法的收敛性理论. 上面主要是基于概率模型的收敛性分析, 国内外学者还从随机过程的角度研究了蚁群算法的收敛性. Badr 和 Fahmy [24]利用随机游走模型(random ranching)分析了一种特殊蚁群算法的收敛性.但是由于约束条件较多,其结论难以进行推广.国内Ke 和Yang 等[25,26]则是利用有限Markov 链模型(Markov chain)作为研究ACO 收敛性的工具; 但是, 分析结论只能适用于信息素矩阵状态有限的特殊蚁群算法. 黄翰等建立了吸收态 Markov 过程数学模型,与以往蚁群算法的Markov 链模型相比,有着更加广泛的适用性。 6 蚁群算法在序列比对中的应用 6.1 双序列比对 6.1.1 双序列比对问题描述 双序列比对是多序列比对和序列数据库搜索的基础。Needlernan 和Wunsch 提出的比对方法属于动态规划范畴[27]。 对于一个序列S ，|S|是S 中字符的个数，S[i]表示序列的第i 个字符. S[1..i]表示序列的前i 个字符组成的子序列。S 中的字符有某个有限字符集合Ω确定(如DNA 由4种核糖核酸A 、T 、C 、G 确定)。基因序列在突变中的变化包括替代、插入和删除，我们用“-”来表示插入和删除所产生的空位。对于}{,-?Ω∈y x ， 定义),(y x σ为打分函数，表示x ，y 比较时的得分，设匹配得分为2，失配为-1，空位罚分为-2，则有： ?? ???--=212),(y x σ (1) 序列S 和T 的一个比对A 用序列S '和T ' (插入空位后的序列S 和T)中字符一一对应表示，有||||T S '='。序列比对A 的得分为： (2) 序列比对的主要目标是如何寻找出序列间的最大相似度的比对。那么如何找到两个序列S 和T 的全局最优比对呢?一方面依赖于选择什么样的目标函数，另一方面要依靠算法的执行。 目标函数是用来对比对结果进行衡量的一个打分机制。在序列比对的过程中，需要引入空位，空位的引入是为了补偿那些插入或缺失，使序列的比对能更紧密地符合某种所期望的模型，但是在序列的比对中引入的空位不能不加限制，否则比对结果即使较高，也缺乏生物学依据。因此，必须有一种机制，对空位的引入加以限制。常用的方法就是空位罚分，即每插入一个空位，就在总分值中减去一定分值(叫罚分值)，即加上一负分值。因此，序列比对最终结果的得分值是两个序列之间匹配残基的总分值与空位罚分的总和[28]。 6.1.2 蚁群双序列比对算法的设计 对序列S=CAGGA 和T=CGGTTA ，仿照动态规划法那样阵建立矩阵(如图1)。蚂蚁从矩阵左上角出发选择一条路线到达右下角，就形成一个比对，我们规定在水平或垂直方向上移动一格，表示在相应的序列中插入一个空位，沿对角线移动一格表示到达的新位置对应字符的匹配。图1中的路线表示了如下比对结果： 序列S ’：CAGG 一一A 序列T ’：C —GG T T A C G G T T A C A '∑∈=y x ∑=='1' '])[],[()(S i i T i S A Score σ'∑∈≠y x ""-=x ""-=y or G G A 图1 单个蚂蚁的行走路线 与TSP 问题不同，蚂蚁在每个位置选择移动方向的数目是固定的，总是向右，向下，沿对角线向右下三个方向，序列比对对加入的空位数量也有一定要求。所以蚁群比对算法的设计与TSP 问题有所不同。 用 表示t 时刻蚂蚁在(i,j)位置上沿着k 方向的路径上的信息素浓度， k=1,2,3分别表示水平向右、垂直向下和沿对角线三个方向。蚂蚁路径选择时的转移概率计算：蚂蚁从矩阵左上角出发，每走一步都要根据当前位置可选择的各条路径上的信息素浓度以及启发信息决定下一个移动的方向。这里的启发信息包括表示字符匹配程度的矩阵D 及方向权值d 。 (3) 蚂蚁在路径选择时采用的策略是：首先设定)1,0(0∈q ，然后产生一个随机数，当这个随机数小于0q 时,选择对角线方向移动；当这个随机数大于0q 时，计算三个方向的概率 ，然后用轮盘赌法在三个方向中选择一个移动。 当所有的蚂蚁通过不同的路线到达矩阵右下角，得到一组比对结果，就完成了寻找最优路线的一次循环。这时要对每条路径的信息素进行全局更新。信息素的更新公式如下： (4) 0)(>Z S c o r e （5） 0)(>Z Score 其中canshu 为信息素增量转化参数，它用来将比对得分小于0的分数转化成正数增量，Q 为信息素增加强度系数。 6.1.3 改进的蚁群双序列比对算法 蚁群算法通过正反馈机制来强化较好的解，但容易出现停滞，陷入局部最优解[29]。针对这个问题，提出自适应调整信息素的方法，根据解的搜索情况，动态地调整信息素的分配。 )(t k ij τ∑=++++=31)][][)](([][][)]([)(k k ijk ijk k ijk ijk ijk d D t d D t t p γβαγ βαττ)(t p ijk τ τρτ?+?=+)()1 (t t ij ij ???+=?Q canshu z Score Q z Score z *)/)(1(*)(τ 采用式(6)的时变函数Q(t)来代替式(5)中的常数Q 。进化初期为了增大搜索空问，Q(t)取较小的值，随着算法的推进取值逐步增大，强化较好的解。在算法的仿真中，我们采用Q1=0.0001，Q2=0.0005，Q3=0.001以及T1=30，T2=60。 (6) 在陷入局部最优解时，某条路径上的信息素在数量上占绝对优势，因此我们对信息素的最大值和最小值进行了限制，如规定05.0)(=t ijk τ，0.30)(=t ijk τ。限制最大值可以防止某条路线的信息素浓度过大，限制最小值可以防止搜索后期没走过的路径信息素浓度过低，使较差的路线被强化。 为了鼓励解质量的改善，又不减小搜索空间，在进化一定代数以后，采用式 (7)根据解的情况动态地调整信息素的分配。若路线ijk R 上取得的解(即比对得分) 为Score ，较目前得到的最优解max Score 有所改善，则增大路线ijk R 上的信息素增 量的分配，并更新max Score 的值，若低于最优解，则减小信息素增量的分配。 (7) 如果最优解在几代内没有改善，则可以适当减小要添加的信息素，以求摆脱局部最优解。 6.2 多序列比对 6.2.1 多序列比对问题描述 多重序列的某个比对[30]实际上就是多个序列之间的一种排列方式。图 2 是六个蛋白质序列片段的多重比对的例子。我们用字符 “ -” 表示插入的空位。 - GRRRSVOWCAVSNPEATKCFOWORNMRKVR --- GPPVSCLKRDSPIOCIOAI ---- KTVRWCAVNDHEASKCANFRDSMKKVLPEDGPRIICVKKASYLDCIKAI ------ VKWCVKSEOELRKCHDLAAKVAE -------- FSCVRKDGSFECIOAI -- KEKOVRWCVKSNSELKKCKDLVDTCKNK ---- EIKLSCVEKSNTDECSTAI ----- EVRWCATSDPEOHKCGNMSEAFREAGI -- OPSLLCVRGTSADHCVOLI APPKTTVRWCTISSAEEKKCNSLKDHMOOER ---- VTLSCVOKATYLDCIKAI 图2 多重序列比对 对于一个比对，可以用SP 模型对它打分以评价比对的好坏。我们假设得分函数具有加和性， 即多重比对的得分是各列得分总和那么，我们首先考虑如何给比对的每一列打分。 对于一列字符打分可用SP 函数，SP 函数定义为一列中所有字符对得分之 ?????<≤<≤<=) 2(3)21(2)10(1)(t T Q T t T Q T t Q t Q ijk ijk Score Score ττ??=?max 和： ∑∑-=+==-11121),(),,,(N i N i j j i n c c p c c c Score SP (8) 其中，i c 表示该列中的第i 个字符，),(j i c c p 表示字符i c 和字符j c 比较所得分 值。将各列的分值加起来就成为比对的总得分。我们进行序列多重比对的目标是要在许多比对方案中，寻找得分最高的比对和在此比对的分值，以其代表序列之间的相似性。 6.2.2 蚁群多序列比对算法的设计 设有N 个序列，其中第i 个序列长度为||i S ，我们将序列中的字符看作是蚂蚁所要走过路径上的节点。 算法首先对序列1 分配一个蚂蚁，令蚂蚁从序列1中的第一个字符出发， 依次选择序列 2，…，序列N 中的某个字符（即节点）与之匹配。选择的概率取决于字符的匹配程度、 匹配的位置偏差以及路径上的信息素。蚂蚁也能以一定的概率选择一个空位插入序列中的某个位置。在完成第一个字符的匹配后，便得到一条路径。这条路径所经过的各个序列中的字符便为与序列1第一个字符相匹配的字符。 蚂蚁接着从序列1中的第二个字符出发， 再依次选择其他序列中的节点或空位与之匹配，如此处理序列1中的各个字符。在蚂蚁选择路径时，不允许出现线段交叉的情况，因为这意味着不可能的比对。当蚂蚁走完时，便得到||1S 条路径所对应的一个比对。 其他蚂蚁也以同样的方式选择各自的路径集合。为了使解具有多样性，这些蚂蚁的处理过程不一定都从序列1开始，我们均匀地分布各个蚂蚁的开始序列。从第i 条序列开始的蚂蚁，从序列i 中的字符出发， 依次选择序列 i+ 1，i+ 2， …，N ，1，2， …，i- 1 中的某字符（即节点）与之匹配。 通过蚂蚁求出的每个路径集合， 我们可找出对应的一个比对， 路径中的节点便是蚂蚁所选择的相匹配的字符。对于不在路径上的字符， 我们可以用其他方法简单地求出它们在比对中的位置， 如靠左对齐、 右边加空位， 以得到一个完整的比对。 在所有蚂蚁完成路径的集合后， 算法根据打分机制求出各个比对的得分， 根据分值的高低对路径上的信息素进行更新以增大分值高的路径上的信息素。这样当下一个蚂蚁选择节点时， 就以新的信息素作为选择的依据， 从而构成信息学习的正反馈机制。 （1） 概率选择公式 设在第k 个序列的第l 个字符选择第n 个序列中的第m 个字符的概率为: ∑+=?+?+??+?+?=h n l k loc n l k loc r c r n l k dev b r n l k mat a r n l k phe c m n l k dev b m n l k mat a m n l k phe m n l k p ),,(),,(),,,(),,,(),,,(),,,(),,,(),,,(),,,( （9） 其中，),,,(m n l k phe 是在第k 个序列的第l 个字符处选择第n 个序列的第m 个字符的信息素指标；),,,(m n l k mat 是第k 个序列的第l 个字符和第n 个序列的第m 个字符的匹配得分；),,,(m n l k dev 是第n 个序列的m 位置与第k 个序列的第1-l 个字符选择的第n 个序列的字符位置的偏差；c b a ,,分别为信息素、 匹配程度、 位置偏差三个指标相应的重要性参数；),,(n l k loc ）是从第k 个序列的第l 个字符出发选择第n 个序列中的字符时起始的字符位置； h 是允许最大的字符选择的范围参数。 这样的概率公式可以使得信息素较高、 匹配程度较好且相对位置偏离较小的字符被选中的概率较大。 （2） 蚂蚁字符选择方法 在第k 个序列的第 l 个字符)(l S k 选择第n 个序列中某个字符时，首先对允许范围内的所有字符计算选择概率， 得到使得选择概率最大的字符)(m S n ，如果)()(l S m S k n =，则选择该字符；否则以一定的概率选择空位， 以剩余的概率选择字符)),,((n l k loc S n 。 （3） 信息素的全局更新 设定信息素全局更新的蒸发系数为evap1，每当一个蚂蚁走完得到一个比对时，对蚂蚁所经过的所有节点上的信息素按式（10）进行更新。 (10) （4） 信息素的调节 在经历了一定代数以后，由于信息素的渐渐集中，算法会陷入局部最优。为了解决这个问题，我们采取了以下措施：预先设定参数 start ，在第 start 代以后， 若某代中蚂蚁得到的比对得分不高于前d 代蚂蚁得到的比对得分（start ， d 都是可调节的参数），则对信息素进行局部更新。更新策略是对于信息素高于某一阈值的路径上的信息素，依据一定的蒸发系数evap2进行蒸发，使得下一代的蚂蚁尽量选择没走过的路径去走。 6.2.3 改进的蚁群多序列比对算法 （1） 蚁巢食物源的往返策越[31] 由于多条序列的长度不一致，而且不同序列间比对是一定字符范围的概率选择，造成了从蚁巢到食物端和食物端到蚁巢的比对过程是不对称的，因此可以通 1))(()11(),,,(),,,(evap avgS A Score evap m n l k phe m n l k phe ?-+-?= 过蚁巢食物源的往返策越，来增加寻优空间。 （2）随机分配蚂蚁的起始序列 蚂蚁在开始新的一列比对时，采用随机的方式分配蚂蚁的起始序列，使得在比对的过程中，不会偏向任何一条序列，而是把多条序列作为一个整体来进行比对。 （3）分治策略与蚁群算法结合[32] 为降低多重序列比对的计算量，可以采用分治策略将序列集在适当的位置划分成若干个由较短序列构成的子序列集，然后对各个子序列集用蚁群算法求解比对。 7 讨论与结束语 本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在序列比对中的应用进行了详细的研究和分析，针对蚁群算法容易陷入局部最优的缺陷，分别指出了蚁群算法在双序列比对和多序列比对中的多种改进方案。 蚁群算法收敛速度分析是机器学习领域中的公开难题，收敛性分析理论仅仅告诉我们蚁群算法存在最终找到全局最优解的可能性, 较难用于实际算法性能的对比评价. 只有对蚁群算法收敛速度进行分析,才能知道算法求解最优解的计算消耗时间. 在未来的工作中可集中研究提高蚁群算法收敛速度的参数优化设计方法以及对比分析蚁群算法性能的理论与方法.同时, 可以考虑一次迭代的时间复杂度和ACO算法的辅助策略, 从而完善对收敛速度的分析。 此外，蚁群算法的一个特点是易于并行化，基于蚁群算法的多重序列比对方法可以用简单的策略实现算法的并行化，从而降低了算法的运算时间，提高求解效率。 相信在今后的研究中，蚁群算法在序列分析以及生物信息学中其它领域的应用前景会更加广阔。 参考文献 [1]M Dorigo, V Maniezzo and A Colorni．The Ant System：Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-part B, 1996, 26(1):1-13 [2]Colorni A，Dorigo M，Maniezzo V，et a1．Distributed optimization by ant colonies[C]．In：Proceedings of the 1 st European a Conference on Artificial Life．Paris，France：Elsevier Publishing，1 99 1，1 34-1 42 [3]Dorigo M，Gambardella L M．Ant colonies for the traveling salesman problem[J]．BioSystems，1997，43(2)：73-81 [4]Gambardella L M，Dorigo M．Ant-Q：a reinforcement learning approach to the traveling salesman problem[C]．In：Proceedings of the 1 2th International Conference on Machine Learning．Tahoe City，CA：Morgan Kaufman，1995，255-260 [5]Stfitzle T，Hoos H H．MAX-MIN Ant System[J]．Future Generation Computer Systems，2000，16(9)：889-914 [6]吴庆洪，张纪会，徐心和．具有变异特征的蚁群算法[J]．计算机研究与发 展，1999，36(10)：1240-1245 [7]Socha K．ACO for continuous and mixed—variable optimization．In：Proc of the 4th International Workshop on Ant Colony Optimization and Swann Intelligence． Brussels，2004：300·30 [8]PEI Jian，HAN Jia．wei，MAO Run—ying．C10set：an efflcient algorimm for mining frequent closed itemsets．In：Proc of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery．Dallas，rexas，2000：21-30 [9]Alupoei S，Katkoori S．Ant colony system application to macrocell oVerlap removal．IEEE Trans on Vbry Large Scale Integration(VLSI)Systems，2004， 1 2 (10)：1118-1122 [10]Yu-Min Chiang, Huei-Min Chiang , Shang-Yi Lin. The application of ant colony optimization for gene selection in microarray-based cancer classification. Machine Learning and Cybernetics, 2008 International Conference on.2008, 7: 4001 - 4006 [11]梁栋，霍红卫. 自适应蚁群算法在序列比对中的应用. 计算机仿真，2005， 22(1)：100-106 [12]陈娟，陈峻．多重序列比对的蚁群算法．计算机应用，2006，26(1)：124．128 [13]陈娟，陈峻．渐进方法结合蚁群算法求解多序列比对问题．计算机工程与 应用．2006，42(21)：38-42 [14]Yixin Chen，Yi Pan，Juan Chen，Wei Liu，et a1．Multiple seqence alignment by ant colony optimization and diVide-and—conquef．In：Proc of ICCS．Brelin，2006，646-653 [15]S R Jangam，N Chakraborti．A noVel method for alignment of two nucleic acid sequences using ant c010ny optimization and genetic algorithms．Applied Soft Computing，2007，7(3)：1121-1130 [16]Lee Z J，Su S F，Chuang C C，et a1．Genetic algorithm with ant colony optimization(GA—ACO)for multiple sequence alignment[J]．Applied Soft Computing，2008，8(1)：55—78 [17]吴斌，史忠植，一种基于蚁群算法 TSP 问题的求解方法，计算机学报，2001， 24(12)：1328-1333。 [18]Gutjahr W J . A generalized convergence result for the graph-based ant system met aheuristic. Department of Statistics and Decision Support Systems, University of Vienna, Austria:Technical Report 9 -09, 1999 [19]Gutjahr W J. A graph-based ant system and its convergence.Future Generation Computer Systems, 2000, 16 ( 9 ) : 873 -888 [20]Gutjahr W J . ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters,2002, 82( 3) : 145 -153 [21]Sttzle T , Dorigo M. A short convergence proof for a class of ant colony opimization algorithms . IEEE T rans act ions on Evolutionary Computation, 2002, 6( 4) : 358 -365 [22]Dorigo M, Sttzle T . Ant Colony Opt imizat ion. CambridgeMA: MIT Press, 2004 [23]Dorigo M, Blum C. Ant colony opt imizat ion th eory: A survey. Theoretical Computer Science, 2005, 344 ( 2 - 3) : 243 -278 [24]Badr A, Fahmy A. A proof of convergence for Ant algorithms. Information Sciences, 2004, 160( 1 - 4) : 267-279 [25]Ke Liang - Jun, Feng Zu -Ren, Fen g Yuan -Jing. Ant colony optimization algorithm with finite grade pherom one. Act a Autom at ica Sinica, 2006, 32( 2) : 296 -303(in Chinese) [26]Yang Wen -Guo, Guo T ian -De. An Ant colo y optimization algorithm for the minimum Steiner tree problem and its convergence proof . Act a Mathematicae Applicat ae Sin ica, 2006,29( 2) : 352 -361( in Chinese) [27]R P Lippmann．Pattern Classification using Neural Networks[J]．IEEE comm， Magazine，Nov．1989，47—64． [28]MM Miyamoto，WM Fitch．Testing the covarion hypothesis of molecular evolution．Molecular Biology and Evolution，1995,12：503—513 [29]S Y Kung，ttu Yu Hen．A Frobenius Approximation Reduction(FARM) for Detennining Optimal Number of Hidden Units[J]．IEEE，1991，II：163—168．[30]Wallace I M，Blackshields G，Higgins D G．Multiple sequence alignments[J]．Current Opinion in Structural Biology，2005，15(3)：261-266 [31]彭东海，骆嘉伟，陈斐. 基于改进蚁群算法的多序列比对．计算机工程与 应用．2009, 45(33): 114-116 [32]陈娟，陈峻．求解多重序列比对问题的蚁群算法．计算机应用研究．2007， 1(25)：25-30 大连理工大学 研究生必修课 作业 课程名称：现代物流管理 研究生姓名：徐静学号：21511149 作业成绩： 任课教师(签名) 交作业日时间：2016 年6 月1日 蚁群算法在TSP问题上的应用 摘要蚁群算法是受现实蚂蚁群体行为启发而得出的一类仿生算法。本文以解决TSP问题为基础,系统地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法。在阐述算法基本思想的前提下，着重论述算法的创新之处。 关键词蚁群算法，TSP问题，蚁群优化 1引言 蚁群算法也称作蚁群优化(Ant Colony Optimization，ACO)，最早是由Dorigo及其研究同伴所提出，用于求解诸如旅行商问题之类的组合优化问题。自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素)，该物质会吸引蚁群中的其它成员再次选择该段路径；食物与巢穴之前较短的路径容易积累较多的信息素，因而使得更多的蚂蚁选择走该段路径，最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。Dorigo等从此现象中抽象出路径选择和信息素积累的数学模型，作为蚁群算法的核心，并通过对蚂蚁寻找最短路径的计算机模拟，实现了对TSP问题的求解。自此，蚁群算法越来越多地被用于求解其它的组合优化问题，也被推广到工业工程上应用。 蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中，利用蚁群在问题空间中同时构造问题的多个解体现了算法的并发性。蚁群不会因为单个蚂蚁寻找到较差的解或者因为问题空间发生改变而使得算法丧失作用，这体现了算法的鲁棒性。在蚂蚁构造问题解的过程中，以蚁群觅食行为为例，会在经过的解路径上释放信息素，而解空间中获得信息素越多的路径，对蚂蚁的吸引力就越大，使更多的蚂蚁经过该路径并进一步在上面释放信息素，这体现了算法的正反馈性。 TSP问题代表一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例。求其最优解的代价是指数级的，因此对其近似解的研究一直是算法设计的一个重要课题。 TSP问题是典型的NP完全问题，许多算验证法及算法效率测试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统,就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统、最大——最小蚂蚁系统。 本文以TSP问题为基础,对蚁群算法的基本问题及典型的蚁群算法进行了综述。涉及到算法的基本问题、算法描述、算法改进及意义。通过研究总结了蚁群算法的发展历程和实现思想。 生物信息学的进展综述 韩雪晴 （生物工程1201班，学号：201224340124） 摘要：生物信息学是一门研究生物和生物相关系统中信息内容和信息流向的综合性系统科学。80年代以来新兴的一门边缘学科，信息在其中具有广阔的前景。伴随着人类基因组计划的胜利完成与生物信息学的发展有着密不可分的联系，生物信息学的发展为生命科学的发展为生命科学的研究带来了诸多的便利，对此作了简单的分析。 关键词：生物信息学；进展；序列比对；生物芯片 A review of the advances in Bioinformatics Han Xueqing （Bioengineering, Class1201，Student ID：201224340124） Abstract: Bioinformatics is the science of comprehensive system of information content and information flows to a study on the biological and bio related in the system. The edge of an emerging discipline since 80, has broad prospects in which information. With the human genome project was completed and the development of bioinformatics are inextricably linked, for the life science research development of bioinformatics for the development of life science has also brought a lot of convenience, has made the simple analysis. Keywords: bioinformatics；progress；Sequence alignment；biochip 1、生物信息学的产生背景 生物信息学是20世纪80年代末开始，随着基因组测序数据迅猛增加而逐渐兴起的一门学科[1]。应用系统生物学的方法认识生物体代谢、发育、分化、进化以及疾患发生规律的不可或缺的工具[2]。及时、充分、有效地利用网络上不断增长的生物信息数据库资源，已经成为生命科学和生物技术研究开发的必要手段，从而诞生了生物信息学。 2、生物信息学研究内容 主要是利用计算机存储核酸和蛋白质序列，通过研究科学的算法，编制相应的软件对序列进行分析、比较与预测，从中发现规律。白细胞介素-6(IL-6)是机体重要的免疫因子,但在两栖类中未见报道。采用生物信息学方法对两栖类模式动物非洲爪蟾IL-6进行分析[3]。以人IL-6基因对非洲爪蟾数据库进行搜索、分析,并采用RT-PCR方法对所得序列进行验证。结果表明,非洲爪蟾IL-6基因位于scaffold_52基因架上,具有保守的IL-6家族基序[4]。采用生物信息新方法进行不同物种的免疫基因挖掘、克隆,是一种有效的方法[5]。 2.1序列比对 比较两个或两个以上符号序列的相似性或不相似性。序列比对是生物信息学的基础。两个序列的比对现在已有较成熟的动态规划算法，以及在此基础上编写的比对软件包BLAST和FASTA[6]。序列数据库搜索最著名且最常用的工具之一便是BLAST算法。FASTA算法是另一族常用的序列比对及搜索工具[7]。 2.2结构比对 比较两个或两个以上蛋白质分子空间结构的相似性或不相似性。 2.3蛋白质结构预测 从方法上来看有演绎法和归纳法两种途径。前者主要是从一些基本原理或假设出发来预测和研究蛋白质的结构和折叠过程。分子力学和分子动力学属这一范畴。后者主要是从观察和总结已知结构的蛋白质结构规律出发来预测未知蛋白质的结构[8]。 3、生物信息学的新技术 第２４卷第∞期计算机仿真 文章编号：１００６—９３４８（２００７）０８０１６７—０４ 双信息素蚁群算法及其在ＴＳＰ中的应用研究 薛莉，戴居丰，魏志成 （天津大学电子信息二程学院，人津３０００７２） 摘要：提出了一种新的蚁群箅法，通过在算法中引人双信息素，很好地改进ｒ算法在解决ＴＳＰ（旅行商）问题¨的收敛眭和最优解的仝局性。一方而通过提高全局信息素对城市路释选择的影响度，很大程度上缩短了算法寻优时｜１１Ｊ，使算法收敛悱得到很大的改善；另一方面通过刘接近最优解的定范围内次优解进行局部更新，避免了舅珐容易收敛于局部最优解的欹点，极大地改进了最优解的全局特一阡。神：ＭＡＴＬＡＢ中构建了摹于蚁群算法的ＴＳＰ问题模型，仿真结果表明，独立的全局信息索使蚁群很快集中于各个次优解区域搜索，局部更新策略又使蚁群跳出局部级值寻找最优，仿真结果证明算法的改进｜１分有救。 关键词：蚁群算法；双信息素；旅行阿问题 中图分类号：ＴＰ３０１，６文献标识码：Ａ ＡｐｐｌｉｃａｔｉｏｎｏｆＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ ｗｉｔｈＴＷＯＫｉｎｄｓｏｆＰｈｅｒｏｍｏｎｅｉｎＴＳＰ ＸＵＥＬｉ．ＤＡＩＪｕ—ｆｅｎｇ．ＷＥＩＺｈｉ—ｅｈｅｎｇ （ＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＤｅｐａｒｔｍｅｎｔ，ＴｉａｎｊｉｎＵｎｉｖｅｒｓｉｔｙ，Ｔｉｍｔｊｉｎ３０００７２，Ｃｈｉｎａ）ＡＢＳＴＲＡＣＴ：Ｔｈｉｓｐａｐｅｒｇｉｖｅｓａｎｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｗｉｔｈｔｗｏｋｉｎｄｓｏｆｐｈｅｒｏｍｏｎｅ，ｉｔｃａｎｏｖｅｒｃｏｍｃｔｈｅｄｅｆｉｃｉｅｎｃｉｅｓｏｆｔｈｅｐｒｉｍａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＴｏｓｏｌｖｅＴＳＰ．ｉｔｓｈｏｒｔｅｎｓｔｈｅｔｉｍｅｏｆｔｈｅｃｏｕｒｓｅｔｏｆｉｎｄｔｈｅｂｅｓｔｖａｌｕｅｂｙｅｎｈａｎｃｉｎｇｔｈｅｇｌｏｂａｌｐｈｅｒｏｍｏｎｅｗｅｉｇｈｔ．ＡｌｓｏａｌｏｃａｌｕｐｄａｔｉｎｇｉｓｉｎｔｒｏｄｕｃｅｄｗｈｅｎｔｈｅｖａｌｕｅｉｓｉｎａｒａｎｇｅｏｆｔｈｅｂｅｓｔｖａｌｕｅｇｉｖｅｎｉｎＴＳＰＬＩＢ．Ｓｏｔｈｉｓｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｃ０１１ｆｉｎｄｔｈｅｄｅｓｉｒｅｄｖａｌｕｅｆｌｅｅｔｌｙａｎｄａｃｃｕｒａｔｅｌｙ．Ａｔｌａｓｔ，ｔｈｅｍｏｄｕｌｅｏｆＴＳＰｉｓｄｅｖｅｌｏｐｅｄ，ｔｈｅｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｓｉｍｕｌａｔｃｄｉｎＭＡＴＬＡ．Ｂ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｉｓｉｍｐｒｏｖｅｄｏｂｖｉｏｕｓｌｙ ＫＥＹＷＯＲＤＳ：Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；’ｌ＇ｗｏｋｉｎｄｓｏｆｐｈｅｒｏｍｏｎｅ；ＴＳＰ １引言 ’ｒｓｐ“１（旅行商）问题是一个经典的组合优化问题，问题要求得到一条遍历所有给定城市的最短闭合路径，属于ＮＰ难问题。随着城市数目的不断增加，导致求懈空间成指数级增长，通过穷举法根奉元法求解，因此用优化算法解决ＴＳＰ问题就十分必要。因此对一些性能较好的优化算法就呼之欲出。 随着人们对现代生物特性的不断研究，一些进化仿生优化算法可以比较理想地解决复杂的组合优化问题。目前求解。Ｉ，＇ＳＰ问题的典型优化算法主要有遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ）和蚁群算法（ＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ）。蚁群算法是由意大利学者ＭａｃｒｏＤｏｒｉｇｏ等，通过对蚂蚁觅食过程的研究而提出的。，该算法应用了蚂蚁觅食中个体行动、整体协作的 收稿日期：２００６—０８—３０修同Ｈ期：２００６—０９—０７工作特性，通过信息素（Ｐｈｅｒｏｍｏｎｅ）这个中间纽带将多个个体（蚂蚁）的动作联系起来，最终完成ｒ谣个蚁群系统的觅食（寻优）过程。 自加世纪９０年代蚁群算法诞生以来，各位专家学者肘它进行了不断的研究和改进４’ｌ。，蚁群算法虽然可以解央ＴＳＰ问题，但是普遍存在收敛速度慢、求解结果易收敛于局部最优解等缺陷。为此本文提出了种新的蚁群算法一双信息素蚁群算法，该算法不仅可以寻找到最优ＴＳＰ路径，相对于ＭＭＡＳ，ＡＣＡ，ＧＡ算法极大地缩短了算法的寻优时间．极大地改进了算法的全局特性。本文通过在ＭＡＴＬＡＢ中构建基于蚁群算法的ＴＳＰ标准问题模璎，仿真了算法的寻优过程。最后通过分析仿真结果，发现双信息索蚁群算法相比传统优化算法在寻优特性和最优解的收敛性上都有ｒ很大改进。 ２蚁群算法 自然界中蚂蚁之所以总能够发现巢穴副食物问的最短 一１６７— 万方数据万方数据 [生工0902] BLOSUM矩阵及其在生物 信息学中的应用 生物信息学 齐阳，汪锴，袁理 2011/11/25 什么是BLOSUM矩阵？BLOSUM矩阵有什么应用？ BLOSUM矩阵及其在生物信息学中的应用 齐阳汪锴袁理 摘要BLOSUM矩阵是一种蛋白质序列对比的算法，在生物信息学领域中被广泛应用。本文综述了BLOSUM矩阵的由来、如何构建BLOSUM矩阵和其打分规则、应用以及现代算法。并指出了BLOSUM矩阵的发展前景。 关键词BLOSUM矩阵；生物信息学；应用 0 引言 序列比对是现代生物学最基本的研究方法之一, 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系，进而可以有效地分析和预测一些新发现基因的功能。目前各种蛋白质序列对比算法主要利用一种替代矩阵来计算序列间的相似性，过去所普遍使用的Dayhoff矩阵只能用来进行相似度85%以上的序列对比「1」，为了满足大量生命科学研究的需求，1992年Henikoff夫妇从蛋白质模块数据库BLOCKS中找出一组替代矩阵，即BLOSUM系列，很好的解决了序列的远距离相关的问题，此后十几年来BLOSUM及其衍生替代矩阵已经成为蛋白质多序列对比的常用方法。 1BLOSUM矩阵概况 序列比对是现代生物学最基本的研究方法之一，常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系，进而可以有效地分析和预测一些新发现基因的功能。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变「2」。在序列比对中，需要找到最优的比对即将匹配的数量最大化，将空格和不匹配的数量最小化。为了确定最优的比对，必须为每个比对进行评估和打分，于是引入了打分函数「3」。 智能控制之蚁群算法 1引言 进入21世纪以来，随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。 智能控制技术的主要方法有模糊控制、基于知识的专家控制、神经网络控制和集成智能控制等,以及常用优化算法有:遗传算法、蚁群算法、免疫算法等。 蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。研究表明该算法具有并行性，鲁棒性等优良性质。它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。 2 蚁群算法概述 1、起源 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。 在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。然而当考虑的对象是人工蚂蚁时，情况就不同了。实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。 2、基于蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设： （1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的环境作出反应，也只对其周围的局部环境产生影响。 （2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的自适应表现，即蚂蚁是反应型适应性主体。 （3）在个体水平上，每只蚂蚁仅根据环境作出独立选择；在群体水平上，单 蚁群算法及其在序列比对中的应用研究综述摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。 关键词：蚁群算法；序列比对；信息素 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)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强 启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题 时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 生物序列分析中几个典型算法介绍 生物信息学研究背景与方向 序列家族的序列谱隐马尔可夫模型（Profile HMMs for sequence families ） 模体识别（Motif Discovery ） 刘立芳计算机学院西安电子科技大学 生物秀－专心做生物！ ｗｗｗ．ｂｂｉｏｏ．ｃｏｍ 背景知识 DNA脱氧核糖核酸 1、DNA的分子组成 核甘(nucleotides) ?磷酸盐(phosphate) ?糖(sugar) ?一种碱基 9腺嘌呤(A denine) 9鸟嘌呤(G uanine) 9胞嘧啶(C ytosine) 9胸腺嘧啶(T hymine) 2、碱基的配对原则 ?A(腺嘌呤)—T(胸腺嘧啶) ?C(鸟嘌呤)—G(胞嘧啶) 3、一个嘌呤基与一个嘧啶基通过氢键联结成一个碱基对。 4、DNA分子的方向性 5’→3’ 5、DNA的双螺旋结构 RNA、转录和翻译 1、RNA(核糖核酸)：单链结构、尿嘧啶U代替胸腺嘧啶T、位于细胞核和细胞质中。 2、转录: DNA链→RNA链信使RNA(mRNA)，启动子。 3、翻译: mRNA上携带遗传信息在核糖体中合成蛋白质的过程。 变异 1、进化过程中由于不正确的复制，使DNA内容发生局部的改变。 2、变异的种类主要有以下三种： 9替代(substitution) 9插入或删除(insertion or deletion) 9重排(rearrangement) 基因 intron exon 基因组 任何一条染色体上都带有许多基因，一条高等生物的染色体上可能带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为genomes（基因组）。 人类基因组计划（Human Genome Project） 基因的编码 1、基因编码是一个逻辑的映射，表明存储在DNA和mRNA中的基因信息决定什么样的蛋白质序列。 2、每个碱基三元组称为一个密码子(codon) 3、碱基组成的三元组的排列共有43＝64种，而氨基酸共有20种类型，所以不同的密码子可能表示同一种氨基酸。 蚁群算法综述 控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景 蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。 从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。 二、蚁群算法的研究发展现状 国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。提出一种基于蚁群算法的TSP问题分段求解算法。王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。 随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。ACO-MH为蚁群算法的理论研究和算法设计提供了技术上的保障。在蚁群优化的收敛性方面，W.J.Gutjahr做了开创性的工作，提出了基于图的蚂蚁系统元启发式(Graph-Based Ant System Metaheuristic)这一通用的蚁群优化 的模型，该模型在一定的条件下能以任意接近l的概率收敛到最优解。T.StBtzle 和M.Dorigo对一类ACO算法的收敛性进行了证明，其结论可以直接用到两类实验上，证明是最成功的蚁群算法——MMAs和ACS。N.Meuleau和M.Dorigo研究了 南京航空航天大学金城学院毕业设计（论文）开题报告 题目基于蚁群算法的TSP问题研究 系部XXXX系 专业XXXX 学生姓名XXXX学号XXXX 指导教师XXXX职称讲师 毕设地点XXXX 年月日 填写要求 1．开题报告只需填写“文献综述”、“研究或解决的问题和拟采用的方法”两部分内容，其他信息由系统自动生成，不需要手工填写。 2．为了与网上任务书兼容及最终打印格式一致，开题报告采用固定格式，如有不适请调整内容以适应表格大小并保持整体美观，切勿轻易改变格式。 3．任务书须用A4纸，小4号字，黑色宋体，行距1.5倍。 4．使用此开题报告模板填写完毕，可直接粘接复制相应的内容到毕业设计网络系统。 1.结合毕业设计（论文）课题任务情况，根据所查阅的文献资料，撰写1500～2000字左右的文献综述： 1.1蚁群算法的发展和应用 在计算机自动控制领域中,控制和优化始终是两个重要问题。使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大,特性上的非线性及不确定性等使得难以建立精确的“数学模型”。人们从生命科学和仿生学中受到启发,提出了许多智能优化方法,为解决复杂优化问题(NP-hard问题)提供了新途径。 蚁群算法(Ant Colony Algorithm,ACA)是Dorigo M等人于1991年提出的。 经观察发现,蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向。蚁群的集体行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。它充分利用了生物蚁群通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。同时，该算法还被用于求解二次指派问题以及多维背包问题等，显示了其适用于组合优化问题求解的优越特征。 蚁群算法应用于静态组合优化问题,其典型代表有旅行商问题(TSP)、二次分配问题(QAP)、车间调度问题、车辆路径问题等。在动态优化问题中的应用主要集中在通讯网络方面。这主要是由于网络优化问题的特殊性,如分布计算,随机动态性,以及异步的网络状态更新等。例如将蚁群算法应用于QOS组播路由问题上,就得到了优于模拟退火(SA)和遗传算法(GA)的效果。蚁群优化算法最初用于解决TSP 问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域获得成功的应用，其中最成功的是在组合优化问题中的应用。 1.2蚁群算法求解TSP问题 （1）TSP问题的描述 TSP问题的简单形象描述是:给定n个城市,有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市,要求找出一条最短的巡回路径。 （2）TSP问题的理论意义 该问题是作为所有组合优化问题的范例而存在的。它已经成为并将继续成为测 文章编号"#$$#%&’’()*$$’+$,%$*#’%$- 生物序列比对算法分析与比较 钟 诚#.宋 彬* )#/广西大学计算机与电子信息学院.广西南宁(,$$$’0*/中国科学技术大学计算机科学技术系.安徽合肥*,$$*&+ 摘要"序列比对是生物信息学的一个非常重要的操作/它可以预测生物序列的功能1结构和进化过程等/文中首先介绍双序列比对的基本算法0接着分析和比较多序列比对的四个常用模型和三类算法以及并行比对算法0最后.给出一些研究问题/ 关键词"生物信息学0双序列比对0多序列比对0精确算法0近似算法0启发式算法中图分类号"23,$#04-##文献标识码"5 生物信息学是一门综合数学1计算机科学和生物学的交叉学科6#7 / 生物信息学内涵非常丰富.其核心是基因组信息学.包括基因组信息的获取1处理1存储1分配和解释/基因组信息学的关键是8读懂9基因组的核苷酸顺序.即全部基因在染色体上的确切位置以及各:;5片段的功能0 在发现新基因信息之后模拟和预测蛋白质空间结构. 然后依据特定蛋白质的功能进行药物设计/生物序列中的信息在系统进化1生态守恒1疾病控制1病毒起源甚至<=>病毒统计和传播等的研究中是一个非常重要的基本工具6*7 .因此.序列比对是生物信息学的基础/序列比对分为全局比对)?@A B C @5@D E F G H F I +和局部比对)J A K C @5@D E F G H F I +/全局比对要求把一个序列中的所有符号和另一个序列中的所有符号进行匹配比较. 它描述整个序列的相似性/将两个序列进行比对就是双序列比对.它是比较两个生物序列相似性的重要工具/ 这个分析工具已经成功地运用到预测生物序列的结构1功能和进化例程中/随着生物医学中有更多的序列合成出来.人们开始用多序列比对来更好地研究生物序列/将多个序列进行比对就是多序列比对问题.它是一个将不等长的多个序列通过插入空格变成等长的过程.这些位 置上的空格代表着相比较的序列从共同的祖先通过插入L 删除操作的进化过程6,7 / 求解多序列比对问题的算法主要分为精确算法1近似算法和启发式算法三种/ #双序列比对 对于两个长度分别为M 的序列有*M N O M P )*M +Q )M Q +)M Q +R **M S T M 种比对情况.这是一个指数级复杂度的计算问题/#U &$年.;H H V @H G C F 和WX F Y K Z 基于动态规划方法6’7提出了第一个双序列比对算法6(7 #U -*年.?A I A Z 对其做了进一步的改进6[7/ 一、引言 目前，最广泛使用的验证网络协议的正确性和测试相关性能的方法是通过虚拟环境进行模拟仿真。NS2是最流行的进行网络模拟的软件之一，是由美国加州大学的LNBL网络研究组于1989年开发的一个开放源代码的网络仿真软件［1］，已广泛被科研院所和各大高校用于网络分析、研究和教学。 蚁群算法是M．Dorigo提出的一种基于生物习性的启发式算法，用于解决复杂组合优化问题。它能在一个合理的时间内对复杂问题有一个较优的结果，在网络路由方面，该算法也体现出了很好的路由性能。虽然NS2集成了大量典型的有线和无线网络下各个层的协议，但还没有提供蚁群算法协议功能，因此以下主要论述把蚁群算法集成到NS2中，并能在Otcl脚本中使用的实现方法。 二、NS2原理［2］ NS2是一个离散事件模拟器，其核心部分是一个离散事件模拟引擎。NS2中有一个“调度器”类，负责记录当前时间，调度网络时间队列中的事件，并提供函数产生新事件，指定事件发生的时间。在一个网络模拟器中，典型的时间包括分组到达，时钟超时等，模拟时钟的推进由事件发生的时间量决定。模拟处理过程的速率不直接对应着实际时间。一个事件的处理可能又会产生后继的时间。模拟器所做的就是不停地处理一个个事件，直到所有的事件都被处理完或者某一特定事件发生为止。 NS2还有一个丰富的构件库，有了这个构件库，用户可以完成自己所要研究的系统的建模工作。NS2的构件库所支持的网络类型包括广域网、局域网、移动通信网、卫星通信网等，所支持的路由方式包括层次路由、动态路由、多播路由等。NS2还提供了跟踪和检测的对象，可以把网络系统中的状态和事件记录下来以便分析。NS2构件库的部分类层次结构如图1所示。 NS2中的网络构件一般由相互关联的两个类来实现，一个在C＋＋中，一个在Otcl中，这种方式称为分裂对象模型。构件的主要功能是在C＋＋中实现的，Otcl中的类则主要提供C＋＋对象面向用户的接口。C＋＋对象和Otcl对象之间的这种连接机制就是TclCL。这种分裂对象模型增强了可扩展性和可组合性。 NS2中蚁群算法路由协议的实现 田克纯，农秀凤，王方 （桂林电子科技大学信息与通信学院，广西桂林541004） 摘要：网络模拟是当前网络通信研究中的重要手段之一，在网络通信的建设开发过程中起着不可替代的作用。 NS2由于其扩展性强、执行效率高，已被广泛应用于各种网络的仿真。首先介绍NS2的原理，然后结合 蚁群算法介绍如何添加新协议到NS环境下并实现，最后给出新协议AntSense的仿真结果。 关键词：网络模拟；NS2；蚁群算法；新协议 中图分类号：T P319文献标识码：A文章编号：1008-3545（2010）04-0043-04 43 生物序列比对算法研究现状与展望 张 敏1,2 (1.大连理工大学计算机科学与工程系,辽宁大连116024;2.大连大学信息工程学院,辽宁大连 116622)Ξ 摘 要:序列比对是生物信息学研究的一个基本方法,寻求更快更灵敏的序列比对算法一直是生物信息学 研究的热点.本文给出了生物序列比对问题的定义,综述了目前常用的各类比对算法,并对每一类算法的 优缺点以及应用范围进行了分析,最后指出序列比对算法目前存在的问题以及未来的发展方向. 关 键 词:生物信息学;两序列比对;多序列比对;算法 中图分类号:TP301 文献标识码:A 文章编号:100822395(2004)0420075205 Current and prospect of bio 2sequence alignment algorithm ZH ANG Min 1,2 (1.Department of C om puter Science and Engineering ,Dalian University of T echnology ,Dalian 116024,China ;2.C ollege of In formation Engineering ,Dalian University ,Dalian 116622,China ) Abstract :Sequence alignment is a basic and important tool in bioin formatics.The research of fast and sensitive biology sequence alignment alg orithm is a current hot topic of bioin formatics.This paper introduces a definition of sequence align 2 ment ;as wellas the research advance of alignment alg orithms at present ,and describes the advantage and limit of the al 2 g orithms and applicable https://www.wendangku.net/doc/c715755700.html,stly ,the problems and development directions are pointed out. K ey w ords :bioin formatics ;pair 2wise alignment ;multiple alignment ;alg orithm 随着人类基因组计划的实施,DNA 和蛋白质序列数据库的规模已呈指数增长,单纯依靠实验手段研究、理解这些生物大分子的生物意义已远远不能满足目前分子生物学发展的要求.生物信息学(Bioin for 2matics )作为一门综合运用分子生物学、数学和计算机等学科的理论和方法的交叉学科为阐明和理解这些海量数据所包含的生物意义提供了可能.序列比对是生物信息学研究的重要方法之一,它通过对DNA 和蛋白质序列进行相似性比较,指明序列间的保守区域和不同之处,为进一步研究它们在结构、功能以及进化上的联系提供了重要的参考依据. 本文给出了生物序列比对问题的定义,综述了目前常用的各类比对算法,分析了每一类算法的应用范围,最后指出了序列比对目前存在的问题以及未来发展方向. 1 序列比对问题的定义与分类 定义:序列比对问题可以表示为一个五元组MSA =( ∑’,S ,A ,F ),其中: (1)∑’=∑∪{-}为序列比对的符号集;“-”表示空位(gap );∑表示基本字符集,对于DNA 序列,∑={a ,c ,g ,t}代表4个碱基;对于蛋白质序列,∑由20个字符组成,每个字符代表一种氨基酸残 Ξ收稿日期:2003207215基金项目:大连市科技计划项目(2002年) 作者简介:张 敏(1966-),女,副教授,博士生. 第25卷 第4期2004年8月大连大学学报J OURNA L OF DA LI AN UNI VERSITY Vol.25 No.4Aug. 2004 《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年 蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理蚁群算法应用
生物信息学论文
双信息素蚁群算法及其在TSP中的应用研究
BLOSUM矩阵及其在生物信息学中的应用
蚁群算法综述
蚁群算法及其在序列比对中的应用研究综述
启发式优化算法综述
生物序列分析中几个典型算法介绍
蚁群算法研究综述
基于蚁群算法的TSP问题研究
生物序列比对算法分析与比较
NS2中蚁群算法路由协议的实现_田克纯
生物序列比对算法研究现状与展望
蚁群算法综述