（计算机应用技术专业论文）基于信息素强度的蚁群算法及其应用研究.pdf

高校教师硕 ：学位论文 摘要 蚁群算法是意大利学者m d o r i g o ，v m a n i e z z o 和a c o l o m i 通过模拟蚁群觅食行为而 提出的一种基于种群的模拟进化算法。作为一种全局搜索的方法，蚁群算法具有正反馈 性、并行性、分布性、自组织性等特点，该算法自提出以来己经在组合优化、函数优化、 系统辨识、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计 等领域获得了广泛的应用，并取得了较好的效果。 本文首先对蚁群算法和蚁群序列比对进行了研究。然后针对现有的蚁群算法在选择 路径的时候都是同时考虑信息素和路径长度两个因素而导致搜索过程未能很好的模拟 真实蚂蚁的| u j 题，提出了一种基于信息素强度的蚁群算法，该算法在选择路径的时候只考 虑信息素强度，在信息素强度初始化和信息素强度更新的时候考虑了路径长度这一因素， 而在路径选择的时候只考虑信息素强度这一因素，更加接近于真实的蚂蚁行为，经过试 验验证这一算法可以取得较好的搜索效果。最后基于信息素强度蚁群算法和简化的网格 模型，提出了一种蚁群双序列比对算法，仿真实验结果证实了该算法的有效性和可行性， 其性能高于a c a 算法。 关键词：双序列比对；蚁群算法；信息素；t s p 问题 i i 幕于信息素强度的蚁群算法及其虑用研究 a b s t r a c t ap o p u l a t i o n b a s e ds i m u l a t e d e v o l u t i o n a r ya l g o r i t h m c a l l e da n t c o l o n y a l g o r i t h m ( a c af o rs h o r t ) w a sp r o p o s e db yi t a l i a nr e s e a r c h e r sm d r i g o ，v m a n i e z z o a n da c o l o r n i a sag l o b a ls e a r c h i n ga p p r o a c h ，a c ah a ss o m ec h a r a c t e r i s t i c ，s u c ha s p o s i t i v ef e e d b a c k ，d i s t r i b u t i n g ，p a r a l l e l i n g ，s e l f - o r g a n i z i n g ，e t c ，a n ds i n c ei tw a s i n t r o d u c e d ，t h ea l g o r i t h mh a sb e e nw i d e l ya p p l i e dt ot h ef i e l d so fc o m b i n a t o r i a l o p t i m i z a t i o n ，f u n c t i o no p t i m i z a t i o n ，s y s t e mi d e n t i f i c a t i o n ，n e t w o r kr o u t i n g ，p a t h p l a n n i n go fr o b o t ，d a t am i n i n ga n dp r e m i s e sd i s t r i b u t i o no fl a r g es c a l ei n t e g r a t e d c i r c u i te t c ，a n dg o o de f f e c t so f a p p l i c a t i o na r eg a i n e d t h i sp a p e rf o c u s e so nt h ea c aa n di t sa p p l i c a t i o no nt h ep a i r w i s ea l i g n m e n t i n n o w a d a y s ，m a n yo ft h ea n tc o l o n ya l g o r i t h m sh a v eas a m ec h a r a c t e r i s t i c w h e ns e l e c t t h en e x tp a t h ，t h e yr e f e rt ot h ei n f o r m a t i o no fb o t hp h e r o m o n ea n dd i s t a n c e t h i s c h a r a c t e r i s t i cc a n ts i m u l a t et h er e a la n tv e r yw e l l i n s p i r e db yt h i sp h e n o m e n o n ，a n a n tc o l o n ya l g o r i t h mb a s e do nt h ei n t e n s i t yo fp h e r o m o n e ( o p a c o ) w a sp r o p o s e d ， w h i c ho n l y d e p e n do nt h ei n t e n s i t yo fp h e r o m o n et o s e l e c tt h en e x tc i t y t h i s a l g o r i t h mu s e st h ei n f o r m a t i o no fd i s t a n c ew h e ni n i t i a l i z ea n du p d a t et h ep h e r o m o n e ， a n di ti n t r o d u c e das t r a t e g yo fd y n a m i cp h e r o m o n eu p d a t i n g t h i sa l g o r i t h mc a nw e l l s i m u l a t et h er e a la n t c o l o n y m o r eb yt h e s e s t r a t e g i e s t h e n ，a n a n tp a i r w i s e a li g n m e n tw a sp r o p o s e db a s e do nt h ep r o p o s e do p a c oa n d s i m p l i f i e dg r i d s i m u l a t e d e x p e r i m e n t s f o rt h e s e q u e n c ea l i g n m e n t s h o wt h e v a l i d i t y a n dt h e f e a s i b i l i t yo ft h ep r o p o s e da l g o r i t h m ，a n dt h a tt h ea l g o r i t h mp e r f o r m sb e t t e rt h a nt h e a n tc o l o n ys y s t e m ( a c s ) k e yw o r d s ：p a i r w i s ea l i g n m e n t ；a n tc o l o n ya l g o r i t h m ；i n t e n s i t yo fp h e r o m o n e ； t s pp r o b l e m i i i 高校教师硕i ：学位论文 插图索引 图2 1 序列g a c g g a t t a g 和g a t c g g a a t a g 的比对结果8 图2 2 双序列点阵图示9 图2 3 相似打分矩阵s 1 0 图2 4 例l 中的比对结果1 0 图2 5 相似打分矩阵h 1 l 图2 6 例2 中的最好匹配片段1 l 图2 7 例3 中的相似打分矩阵h 1 2 图2 8 例3 对应的最优比对1 2 图2 9 蚁群路径搜索实例1 4 图2 1 0 蚁群双序列比对模型1 5 图2 1l 蚂蚁的行走路线1 6 图2 1 2 序列s 和t 的比对结果1 6 图2 1 3 蚂蚁选择字符示意图1 7 图3 1e i l 5 1 的收敛过程2 3 图3 2e i l 7 6 的收敛过程一2 3 图4 1 简化网格模型2 5 图4 2 实验1 中基于信息素强度算法的一个比对结果2 9 图4 3 实验l 中基于基本蚁群算法的一个比对结果2 9 图4 4 实验3 中基于信息素强度算法的一个比对结果3 0 图4 5 实验3 中基于基本蚁群算法的个比对结果31 图4 6 实验4 中基于信息素强度算法的一个比对结果3 2 图4 7 实验4 中基于基本蚁群算法的一个比对结果3 2 图4 8 实验5 中基于信息素强度算法的一个比对结果3 3 图4 9 实验5 中基于基本蚁群算法的一个比对结果3 4 v i 基于信息素强度的蚁群算法及j e 心用研究 附表索引 表3 1e i l 51 的运算结果2 2 表3 2a s r a n k ，a s 和o p a c o 的比较2 3 表3 3e i l 7 6 的运算结果2 3 表4 1 平均长度约为5 0 的两序列2 8 表4 2 实验1 中两种算法的比较2 8 表4 3 实验2 中两种算法的比较2 9 表4 4 实验3 中两种算法的比较3 0 表4 5 实验4 中两种算法的比较一3 1 表4 6 实验5 中两种算法的比较3 3 表4 7 实验5 中的最优解3 3 v i i 高校教师硕j ：学位论文 第1 章绪论 蚁群算法( a n tc o l o n ya l g o r i t h m ) 是近年来发展起来的一种新型模拟进化算 法，它是由意大利学者m d o r i g o 等人在2 0 世纪9 0 年代初提出来的【l 艺l 。这种算法模 仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用 到不同的领域。 生物信息学计算的核心是序列比较，在生物学的研究中，将未知序列同已知 序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分的问 题在计算机科学领域中主要体现为序列或字符串的问题。现有的方法是采用序列 的字符表示，利用序列比对来解决，而序列比对大多数也是通过在打分矩阵中寻 找最优路径来获得比对结果，这些方法大多数是时间复杂度高，不但不能提供获 得优化比对结果的保证，还具有鲁棒性和序列个数不敏感等缺陷。 蚁群算法具有良好的鲁棒性是其可应用于序列比对的基础。蚁群序列比对算 法是通过修改基本的蚁群算法模型，在序列比对结果和蚂蚁走过的路径之间建立 联系来获得。本文在系统研究蚁群算法的基础之上，提出一种基于信息素强度的 蚁群算法，并将其应用于t s p 问题和双序列比对。 1 1 选题背景和意义 寻找序列相似性的过程称为序列比对，序列比对是序列分析的基本手段。通 过序列比较可以发现生物序列中的功能、结构和进化的信息。序列比较的根本任 务是通过比较生物分子序列，发现它们的相似性，找出序列之间共同的区域，同 时辨别序列之间的差异。在分子生物学中，序列之间的相似性是多方面的，可能 是序列之间的相似，可能是结构的相似，也可能是功能的相似。一个普遍的规律 是序列决定结构，结构决定功能。研究序列相似性的目的之一是通过相似的序列 得至0 相似的结构或相似的功能，另一个目的是通过序列的相似性，判别序列之间 的同源性，推测序列之间的进化关系。因此序列研究已成为生物信息学领域中一 个非常重要的研究课题。 蚁群算法( a n tc o l o n ya l g o r i t h m ) 是由意大利学者d o r i g o 等人i l 也j 于2 0 世纪 9 0 年代初期通过研究自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启 发式仿生算法。经研究发现：蚂蚁在觅食过程中能够在所经过的路径上留下一种 称为信息素的物质，而且蚂蚁在觅食过程中能够感知这种物质的存在及其强度， 并以此指导自己的运动方向，它们倾向于朝该物质强度高的方向移动。因此，由 基于信息素强度的蚁群算法及其应用研究 大量蚂蚁组成的集体觅食行为就表现出一种信息正反馈现象，某一路径越短，该 路径上走过的蚂蚁就越多，所留下的信息素强度也就越大，后面的蚂蚁选择该路 径的概率因此就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并达到搜 索食物的目的。蚁群算法就是模拟蚁群这一觅食行为而建立起来的优化算法。 目前蚁群算法在序列比对中的应用都仅限于在原始的字符序列上寻找最优比 对结果。这种运用蚁群算法直接在原始字符序列上求解比对结果的方法一般是从 一个序列出发依次在接下来的序列上选择一个字符或者选择插入空格来匹配的策 略，没有考虑到其它序列的影响，这种基于两两比对的多序列比对方法在全局性 上存在一定的欠缺，没有充分考虑所有序列的信息，这必定对整体比对结果有一 定影响。本项课题就是旨在将比对模型在某些方面作一些修改使其在结合蚁群算 法来解决序列比对问题时具有更好的运算效果，另一方面我们要建立合适的数学 模型使我们可以将蚁群算法更合理的应用到序列比对当中，并且可以更好的解决 序列比对问题。 1 2 研究现状 1 2 1 序列比对 序列比对算法( s e q u e n c ea l i g n m e n ta l g o r i t h m ) ，就是根据一个给定的计分函数 计算得到两个或多个字符串序列的最优比对。即对两个或多个字符串序列，通过 匹配相对应的字符或插入“”来表示插入或删除，得到序列之间的最大相似性排 列。比对的结果反映了算法在多大程度上反映序列之间的相似性关系以及它们的 生物学特征。两条序列的比对是指这两条序列中各个字符的一种一一对应关系， 或字符对比排列。序列的比对是一种关于序列相似性的定性描述，它反映在什么 部位两条序列相似，在什么部位两条序列存在差别。最优比对揭示两条序列的最 大相似程度，指出序列之间的根本差异。序列比对算法有双序列比对和多序列比 对之分，目前多序列比对问题任然是n p 问题。 解决双序列比对问题一般都是应用动态规划算法来求得最优比对结果，例如 n e e d l e m a n 和w u n s c h 提出了基于动态规划思想的双序列比对算法1 3 j 。利用动态规 划算法解决双序列比对问题的方案描述如下，计算得分矩阵s ，在得分矩阵中回 溯寻找最优比对序列。 s i ，j 】- m a x s i - 1 ，j 一1 + s ( a i ，b j ) ，m a x x 2 l ( s 【i x ，j - w x ) ，m a x y 之i ( s i ，j - y 】w y ) ( 1 1 ) 在得分矩阵中，到达位置为( i , j ) 的某一个元素有三种可能的路径：对角线方 向元素、同一行或同一列的元素。位置( i 1 , j 1 ) 的对角方向，没有空位罚分；通 过列j 的垂直方向和通过行i 的水平方向，空位罚分的值取决于插入空格的个数。 若两个序列为a = a l a 2 a 。和b = b i b 2 b 。，则s 【i ，j 】是到达序列a 中第i 位字符 高校教师硕：l ：学位论文 与序列b 中第j 位字符的比对得分值，s ( a i ，b j ) 是字符a i 与b j 的计分值，w x 是在序 列a 上空格长度为x 的空位罚分值，w y 是在序列b 上空格长度为y 的空位罚分 值。在此注意，s i j 是得分矩阵中从三个方向上得到的一条最佳比对路径得分值。 当得分矩阵的所有元素s i j 被计算出来后，最佳路径的终点是在最后行最后一 列的位置。从这一点丌始根据上面公式在得分矩阵中回溯寻找得到的路径就是一 条最优路径。t e m p l es m i t h 和m i c h a e lw a t e r m a n 于1 9 81 年提出了一种局部排列 动态规划算法，该算法也需要计算得分矩阵来寻找最优匹配片段 4 1 。 而多序列比对算法分成两种，第一种为全局性的优化搜索算法。其中一类全 局性算法是对n e e d l e m a n 和w u n s c h l 3 】提出的基于动态规划( d p ) 的双序列比对算法 简单地扩展至n 维，由此产生了一类多序列比对算法，但这种算法庞大的计算量 导致了它的实用性不高；另一类则是基于随机性搜索策略的，如隐马尔可夫模型、 模拟退火和遗传算法等，这类算法被证明是具有一定的柔性并且有效的方法，但 不具有一般算法的稳定性而且计算时间较长。另一种为启发式算法，这类算法的 基本思想是通过引入其他的信息或者计算工具来降低计算量并且提高比对精度。 多序列比对的启发式计算方法通常在适度牺牲j 下确性的基础上来提高计算效率。 c l u s t a lw 【5 】是应用最为广泛的多序列比对软件。它是高效的渐进方法的代表。 c l u s t a lw 是在f e n g 和d o o l i t t l e 5 1 提出的算法上作了一系列的改进，使得结果的 正确性得到进一步提高，从而在生物信息学中得到了广泛的应用。但是渐进方法 是以序列的两两比对为基础的，而两两比对的局部结果在多重序列比对中往往并 不最优。这样会对多重序列比对带来错误信息，并且这些错误信息不能在后期阶 段被纠正。针对渐进方法的缺点，一些算法采用预处理或迭代优化等来对比对算 法进行改进。这些算法包括基于迭代细化策略的p r r n p r r p t 、基于傅立叶变换 的m a f f t s 】、基于多重迭代的m u s c l e l 9 1 和t - c o f f e e 1 1 】。这些算法均在不同程 度上提高了多序列比对的速度和精度，开辟了新的研究思路。 1 2 2 蚁群算法 蚁群算法( a n tc o l o n ya l g o r i t h m ) 是近年来发展起来的一种新型模拟进化算 法，它是由意大利学者m d o r i g o 等人在2 0 世纪9 0 年代初提出来的【卜2 1 。这种算法模 仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用 到不同的领域。 自从1 9 9 1 年m d o r i g o 等人首先提出蚁群算法以来，吸引了许多研究人员对 该算法进行研究，它最早成功应用于解决著名的旅行商问( t r a v e l i n gs a l e s m a n p r o b l e m ，t s p ) ，该算法采用了分布式正反馈并行计算机制，易于与其他方法结合， 而且具有较强的鲁棒性。蚁群算法发展到今天已经有十几年的路程。在这一段时 间罩人们不断的对蚁群算法提出一些改进方法，并且将蚁群算法应用到了许多领 域。其中的一些改进方法有d o r i g o 等人提出的一种称之茭j a n t qs y s t e m i i - 1 3 】的蚁 群算法，该算法只让每次循环中的最短路径上的信息量作更新，强化了信息的反 馈。还有基于等级的蚁群算法r a s ( r a n k b a s e da s ) 【1 4 】。德国学者s t u t z l e 和h o o s 提 出了一种最大最小蚂蚁系统( m a x m i na n ts y s t e m ，m m a s ) 1 5 】，m m a s 对信息量 的上下界作了限定，并且在算法中采用了轨迹平滑机制。初始时m m a s 将所有路径 弧段上的信息量设为最大值t m a x ，每次迭代后，按挥发系数p 减小信息量，只有 最佳路径上的弧段才允许增加其信息量：同时为了避免发生早熟现象，该算法将 各条路径可能的信息量限制在区间 f m i n ，t m a x 之内，这样可以有效地避免某条路 径上的信息量远大于其他路径，使得所有的蚂蚁都集中到同一条路径上，从而使 算法不再扩散。直到今天，m m a s 仍然是解决t s p 、q a p 等离散域优化问题的最 好蚁群算法模型之一，很多对蚁群算法的改进策略都渗透着m m a s 的思想【1 6 4 7 1 。 另外还有国内的学者吴庆洪等人提出了一种具有变异特征的蚁群算法【”】，在蚁群 算法中引入了逆转变异机制。 现有蚁群算法的应用主要体现在以下几个方面1 1 9 1 ： ( 1 ) 蚁群算法在组合优化问题中的应用 蚁群算法在旅行商( t s p ) 、作业调度问题( j s p ) 等组合优化问题当中均有较好 的应用。其中在旅行商问题( t s p ) 中的研究是最普遍的，国内在对蚁群算法的研究 上，大多是基于旅行商问题进行理论探索和仿真实验的。 ( 2 ) 蚁群算法在电信中的应用 蚁群算法在电信路由中的应用有比较成功的例子，h p 公司和英国电信公司 在9 0 年代中后期都丌展了这方面的研究，在所采用的蚁群路由算法( a n tc o l o n y r o u t i n g ，a c r ) 中，蚂蚁根据它在网络上的经验与性能，动态地更新路由表项 ( r o u t i n g t a b l ee n t r i e s ) 。如果蚂蚁因为它经过了网络中堵塞的路段，而导致了比 较大的延迟，那么就对相应的表项做较小的增强，如果某条路段比较顺利，那么 就对该表项做较大的增强同时应用挥发机制，就可以做到系统信息的更新，使得 那些过期的路由信息不再保留。在当前最优路径出现阻塞时，a c r 算法能很快 找到另一条可替代的最优路径，从而提高网络的均衡性、网络负载量以及网络的 利用率。 ( 3 ) 蚁群算法在经济领域的应用 蚁群算法在经济领域也有很好的应用前景，比如利用它对内河航道提供科学 合理的规划，解决集装箱的集散问题。 ( 4 ) 蚁群算法在序列比对中的应用 1 2 3 蚁群比对 蚁群比对算法关键之处在于模型的建立和蚁群算法的选择2 0 - 3 3 1 。陈娟等人【2 1 高校教帅硕i ：学位论义 2 7 五8 】提出了蚁群优化算法在多序列比对中的应用及渐进算法结合蚁群算法在多序 列比较中的应用。其基本策略是利用了人工蚂蚁逐个选择各个序列中的字符进行 配对。算法首先对序列1 分配一个蚂蚁，令蚂蚁从序列1 中的第1 个字符出发， 依次选择序列2 、序列n 中的某字符( 即结点) 与之匹配。选择的概率取决于 字符的匹配程度、匹配的位置偏差以及路径上的信息素。蚂蚁也可以按照一定的 概率选择一个空位插入序列中的某个位置。在算法中，蚂蚁根据信息素、字符匹 配得分以及位置偏差等信息决定选择各序列中的字符的概率，通过信息素的更新 与调节相结合的策略，以及参数的动态自适应调节方法，较为有效的解决了局部 收敛的问题，加强了算法寻求全局最优解的能力。后者先对所有序列进行预处理。 以避免早期错误的发生，采用蚁群优化算法及概率一致性更新计算出这些序列中 所有字符。这里，后验概率p ( s k ( 1 ) s 。( r e ) i s ) 是指在s k 和s 。比对时，特定位置上 的字符s k ( 1 ) 和s 。( m ) 出现在最终序列组s 的比对s 的概率。在计算后验概率的 时候已经考虑到了所有其它序列所提供的一致性信息，这样就预防了早期的比对 中不一致的发生。当计算得到所有字符对的后验概率后用渐进比对方法来构造序 列的多重比对，即首先计算所有两两序列之问的距离，根据近邻优先结合的原则 构造引导树然后根据引导树所指引的顺序用动态规划算法两两合并序列或序列 组。实验显示，该算法可以有效解决多序列比对问题。 彭东海等人【2 0 】提出了一种基于信息素智能更新的蚁群双序列比队算法，该算 法利用历史最优信息来更新信息素，需要建立一个数组z u i o a o f e n 保存每轮比 对中的最高分。当循环迭代次数大于m 时，先对数组z u i g a o f e n 排序，然后对 得分前n 名的相应蚂蚁所经过的每个位置上的信息素进行更新。 陈娟等人【2 8 】提出求解多重序列比对问题的蚁群算法，利用人工蚂蚁逐个选择 各个序列中的字符进行配对。在算法中，蚂蚁根据信息素、字符匹配得分以及位置 偏差等信息决定选择各序列中字符的概率，通过信息素的更新与调节相结合的策 略较为有效地解决了局部收敛的问题，加强了算法寻求全局最优解的能力。另外在 该算法的基础上，提出了基于分治策略的多序列比对蚁群求解算法，不但减少了原 算法的计算时间，而且显著改善了算法所求得的解的质量。 梁栎等人1 2 9 】提出一种基于自适应调整信息素的改进蚁群比对算法，根据解的 搜索情况，动态地调整信息素的分配。 z n e j u n gl e e 等人【3 0 l 提出了一种运用遗传算法和蚁群算法的多序列比对算 法。算法运用遗传算法得到初步的比对结果之后，再利用蚁群算法来对一些比对 片段进行修诈，来改善局部片段的比对效果。这样将蚁群算法作为局部搜索嵌入 到遗传算法的求解过程中来对遗传算法的结果进行局部优化以便得到较好的比对 结果。 s r j a n g a m 等人【3 1 1 提出了一种基于遗传算法和蚁群算法的双序列比对算法。 算法预先设定每两个相邻字符之间插入空格的最大个数，例如最大空格个数为3 时，每两个字符之间可选择的方式就有4 种，分别为插入0 、l 、2 、3 个空格的情况。 每一步算法用一个子路径s i j 表示，s i j 表示的是某一条序列的第i 对字符之间插入了 j 个空格。蚂蚁分别在两条序列上选择一串子路径，最后就形成了一个比对。然后 将用蚁群算法得到的比对结果再利用遗传算法中的交叉算子来进行改进。 廖波等i ) 2 j 提出了一种基于离散点阵图的蚁群双序列比对算法，算法是依照修 改后的点阵图将两条序列在平面上表示出来，然后运用蚁群优化算法来寻找一个 较好的比对结果。他们还提出了一种基于多维图形的对序列比对算法，算法预先 提出了一种基于多维图形的多序列表示方式。图形的维数与序列的条数相对应。 基于这种表示方法可以将多序列比对中的每一种情况都考虑进去，并将各个顶点 的标号与空格插入的个数对应了起来。然后基于这种表示方法还定义了具体的空 格插入表示方法、可选路径的启发信息值、针对各个维数的评分规则。根据这些 规则，再运用蚁群优化算法在具体的图上寻找代表较优比对结果的路径【3 3 1 。 1 3 本文的主要工作 本文的研究工作主要有以下几个方面： ( 1 ) 对蚁群算法和序列比对算法进行了系统的研究与分析。 ( 2 ) 针对现有的蚁群算法在选择路径的时候都是同时考虑信息素和路径长度 两个因素而导致搜索过程未能很好的模拟真实蚂蚁的问题，提出了一种基于信息 素强度的蚁群算法，该算法在选择路径的时候只考虑信息素强度，在信息素强度初 始化和信息素强度更新的时候考虑了路径长度这一因素，而在路径选择的时候只 考虑信息素强度这一因素，更加接近于真实的蚂蚁行为，经过试验验证这一算法 可以取得较好的搜索效果。 ( 3 ) 基于信息素强度蚁群算法和简化的网格模型，提出了一种蚁群双序列比对 算法，仿真实验结果证实了该算法的有效性和可行性，其性能高于a c a 算法。 1 4 本文的章节安排 论文的章节安排如下： 第一章为绪论，主要介绍了选题的背景、意义，并简要说明了本文所做的主 要研究工作和章节安排。 第二章介绍序列比对、蚁群算法和蚁群比对算法的基本思想和主要方法，将 为新算法核心模型的提出提供基础。 第三章基于信息素强度的蚁群算法。提出的算法o p a c o 在各路径信息素初 始化的时候引入信息素强度的概念，在蚂蚁的转移概率求解的时候只利用了信息 6 高校教师硕 ：学位论文 素强度这一因素，在信息素强度更新的时候运用了用距离代替时间的理念与动态 更新的思想。 第四章，改进的蚁群算法在双序列比对中的应用。 最后是对全文的一个总结。 2 1 序列比对 第2 章研究基础 生物序列的比较是计算分子生物学或生物信息学中最基本的操作。其作用有： 同源性的判断、相似性的搜索、功能区的预测、基因突变的判断、复制区域的判 断等。如设有两条序列：g a c g g a t t a g ，g a t c g g a a t a g ，其比对结果如图2 1 ： 比对结果1 ：比对结果2 ： g a c g g a t t a gg ac g g a t t a g g a t c g g a u r a gg a t c g g a a t a g 图2 1 序列g a c g g a t t a g 和g a t c g g a a t a g 的比对结果 在生物序列比较分析中，存在以下几类常见的问题： 有两个字母表相同、长度相同的串( 几万字符) 。已知序列几乎是相同的， 仅有少数几个差异，如字符的插入、删除、替换等。这些差异的频率很低，几百 个字符出现一个。我们需发现差异出现的位置一基因突变的位点。 有两个字母表相同的序列，各自长数百字符。我们需要知道一个序列的前 缀是否与一个序列的后缀相似。 问题同，但有几百个序列，每一个需与所有其他序列进行比对。而且绝 大部分序列之间是无关的，即它们缺乏应有的相似度。 有两个字母表相同的序列，各自长数百字符。我们需要知道它们之间是否 存在相似的子串。 问题同，但不是两个序列，而是一个序列与数干个序列比较。 常见的序列比对算法的基本思想是采用用打分矩阵描述序列两两对比，即将 两条序列分别作为矩阵的两维，矩阵元素是两维上对应两个残基的相似分数，分数 越高说明两个残基越相似。因此，序列比对问题变成在矩阵里寻找最佳比对路径。 具体地讲，对两个序列a 和b ，求出它们的扩张序列，使它们的扩张序列的罚分 为最小d ( a ，b ) 。 序列比对有双序列比对和多序列比对之分，常见的双序列比对算法点阵图方 法和动态规划算法，而多序列比对算法主要有渐进比对和迭代比对两大类【3 。10 1 。 1 ) 点阵图法 点阵图法【3 4 。3 5 】的基本思想是通过将一条序列排在上端，另一条序列纵列在左 端，两个序列在任何位置上若出现相同残基，就在两个序列对应位置上标注一个点， 做成一个图排列成对角线的点列体现出两条序列间具有相同的字符串，从而形象 高校教帅颂l ：学位论文 地表明序列问的相似性，双序列点阵图示如图2 2 所示。 a t c g i ii l a t c g ( - ) 序列比较矩阵标记图 ( c )反向序列矩阵标记图 c b )相同子序列矩阵标记图 la tc cgcctc ( d ) 多个相同子序萝矩阵标记图 t t 一一6 c c t i ii| ii l t a t c c g c 盯c 图2 2 双序列点阵图示 点阵图法的主要优点在于可以找到序列问的所有可能的残基匹配，但主要的 局限是点阵计算机程序并不能显示真实的比对排列。 2 ) 动态规划算法 动态规划算法主要有全局排列和局部排列两大类。 全局排列动态规划算法是由n e e d l e m a n 和w u n s c h 于1 9 7 0 年首先提出的【3 】， 算法的基本思想是：用比对的两条序列构建一个相似打分矩阵s ，矩阵中的元素 s ；。可通过公式( 2 1 ) 获得。 s ，川+ s g ，b ，) = m a x s 。j一致 s i 、 _ y wy a ，与6 ，匹配或不匹配 删除 插入 ( 2 1 ) 这里，墨是序列a 在位置i 和序列b 在位置j 的分值。j b ，6 j ) 是序列a 位置 i 和序列b 位置j 上排列性状的分值。畋是序列a 中长度为x 的间隔罚分，是 序列b 中长度为y 的| 日j 隔罚分。由于算法遍历矩阵的每个点，s u 具有最佳罚分。 例i ：对序列a = g c t g a t a t a g c t ，b = g g g t g a t t a g c t , 选择参数 s ( a ，a ) = 1 ，s ( a ，b ) = 1 ，插入删除单个字母的罚分为2 ，计算相似打分矩阵s 如图2 3 。 皋十信息豢强度的蚁群算法及j e 心用研究 0 2 4 6 8 10 12 1 4 一l6 18 - 2 0 - 2 2 - 2 4 g - 2 ggtga 一468一l0 一l2 一3 5 一了一9 叭一2- 4 6 8 蓦霾1 孕瓣 一52 一 一2 。豆、二2 7432 2 、p 一96523一l l1 8一了一4 32 一l3 1 0 9654 15 1 2 1 1 874 17 一1 4 11 一l0 76 19 1 6 1 3 12 98 21 18 15 12 一l1 一l0 ttagct 1 4 一l6 一l8 - 2 0 - 2 2 - 2 4 一l1 1 3 一l5 17 19 21 10 12 1 4 一l6 16 一l8 791l 一1 3 一l5 15 4 6 8一l0 12 1 4 f1 35一t一911 、习0- 2 468 榭一占二主二要 一3 1 呈、坦一1 3 5 3 0 、3 。! 一1 7 5 2 卜小、呈 一一6 4 1 入弓、 图2 3 相似打分矩阵s 根据上述矩阵可得最优比对如图2 4 所示： 6c tgatatag ct i ii lii ii i liii gg g t gat tagct 图2 4例l 中最优比对结果 局部排列动态规划算法是由t e m p l es m i t h 和m i c h a e lw a t e r m a n 于1 9 8 1 年 提出的【4 1 ，同样算法也是通过比对的两条序列构建一个相似打分矩阵( 记为h ) ， 矩阵中的元素，可通过公式( 2 2 ) 获得。 h ( i ，o ) = 0 , 1 i 肌； h ( o ，j ) = 0 , 1 甩； ( 2 2 ) f h f 1 - l + w - ，b )a t 与6 j 匹配或不匹配 髓：荔 般 【0 这里，h ，是序列a 在位置i 和序列b 在位置j 的分值。w k ，b ，) 是序列a 位 置i 和序列b 位置j 上排列性状的分值。暇是序列a 中长度为x 的间隔罚分，帆 是序列b 中长度为y 的间隔罚分。 例2 ：设s ( a ，a ) = 2 ，s ( a ，b ) 一1 ，插入删除一个字母的罚分为2 ，比较序列 a = c g t t g a g a t a c t b = g c t c t g c g a a t a ，计算相似打分矩阵h 如图2 5 。 l o g c t g a t a t a g c t 高校教师颀l j 学位论文 2 l 5 图2 5 相似打分矩阵h 通过上述矩阵可获得最好的匹配片段如图2 6 所示： gat i i f gat 图2 6例2 中最好的匹配片段 袁春欣等人【3 6 】提出了一种m r n a 序列和蛋白序列比对的动态规划算法，该算 法定义从a 中删除k 个字母的成本函数为磊= 口+ 屈( 七- 1 ) ，从b 中删除k 个字母的 成 本函 数为 皖= 口：+ 屐( 七一1 )，三 联体对应的打分为 坼尸矿= 警蹴：羔斛藤过蛐2 剐获得 h ( i ，o ) = 0 , 1 i 甩； h ( o ，j ) - 0 , 1 脚； h t 。j 。m a x 一。+ 5 ( g ( a t - 2 a , - l a , ) ，6 ，) h f i 一口1 h ，j l 一口2 0 ( 2 3 ) 其中，日u = h 一。+ m a x 4 9 ( 口卜。q 一口，) ，b ，l s b g 一口m 口h ) ，6 ，l s b 0 卜。口，一：口i ) 6 ，) 一口。 例3 设a = u u u u a c u g c g g c c a c u g c g g c c ，b = f y c g f t a a ，口i = 口2 = 1 ， sa , i a , 2 a , ，, b j ) = 2 | i 3 一f 1 | q 0 ，按照采用轮盘赌的方式决定 下一方向。 因此，蚂蚁在选择方向时，有两种可能一是选择转移概率最大的，二是按轮 盘赌的方式选取。这种策略的优点是消除了蚂蚁的盲目性又扩大了解空间，但具 有一定的随机性。有些情况，根据蚂蚁的上一方向、序列的当前字符、下一字符 可以预测一个有利提高解的位置。因此采取了记忆、预测的方法，定义了修正蚂 蚁位置的三条简单规则：顶部与底部网格不能轮流选取；序列当前两字符相 同只能选取中间网格；序列当前两字符不同，但某一序列的字符与另一序列的 下一字符相同，在该序列中插入空格。通过上述三条简单易行的规则，算法有了 很明显的提高。 第三步：信息素的全局更新。 当所有的蚂蚁都从起始位置找到一个有效终点时，就完成了一轮迭代，这时 要对信息块进行全局更新。在进行信息素全局更新时，引入了启发信息，根据计 分公式简币的规定：只有当i - - 1 且序列s 与序列t 的两个字符相同时，网格( i ，j ) 的启发信息r l i j = 2 ，其它情况i l l j = l 。定义p ( o ，1 ) 为挥发系数，那么1 - p 便是信息素 的剩余度，信息素更新公式如下： z y ( t + 1 ) = ( 1 - p ) xr 。( f ) + 乃 ( 4 8 ) 其中么t i j 表示本次迭代中网格( i ，j ) 中信息素的增量，定义如下： a r ，= 三巧 ( 4 9 ) m 表示蚂蚁的数量，1 t 0 为第z 只蚂蚁在网格( i ，j ) 中留下的信息素。定义 如下： 巧：i q x q ux ( s c o r e z + m a x _ s c o r e ) f 口玎，zp 鲫s 矿f d ( f ，) ( 4 1 0 ) 【 5如 q 为一个j 下常数，一般较小，s c o r e 2 表示蚂蚁z 的得分。由于在序列比对中 分值可正可负，因此使用m a x s c o r e 将其映射成正值。比对分值越高，留下的信 息素也越多。 一轮迭代结束，重置所有蚂蚁到起点，开始下一轮迭代，直到满足终止条件。 茄子信息素强度的蚁群算法及其应用研究 终止条件有两个：达到最大迭代轮数；最优解连续数代( 如1 0 ) 保持不变， 即算法已收敛。 4 3 实验结果与分析 下面，使用基本的蚁群序列比对算法及基于信息素强度的蚁群序列比对算法， 对几组长度不同，相似度不同的序列( 含d n a 序列和蛋白质序列) 进行比对， 从比对速度、寻求最求较优解能力上对两种算法进行比较。 实验l 、对平均长度较短的两序列进行比对 表4 1 平均长度约为5 0 的两序列 初始序列 比对结果 序列1 ：a c g c t c g c a g g a c a c t t t t c a g a t c t a t g a c t c a g g a c g g c t g c t a a t a 序列2 ：a c c t c g c a g g a g a c t t t t a c a g a a t c t a t g a c t t c a g a c g g c a g c t a t a 序列1 ：a c g c t c g c a g g a c a c t t t t - c a g a - t c t a t g a c t c a g g a c g g c t g c t a a t a 序歹02 ：a c - c t c g c a g g a g a c t t t t a c a g a a t c t a t g a c t t c a g a c g g c a g c t a - t a 设定基本参数： 基本蚁群算法：蚂蚁数l0 、a = l 、p = 5 、q o = 0 3 、p = 0 2 、q = o 1 、 g o = 10 、 m a x s c o r e = 0 基于信息素强度算法：蚂蚁数1 0 、q o = o 3 、p = o 2 、q = o 1 、 t o = 10 、m a x s c o r e = 0 对于表4 1 中平均长度约为5 0 的两序列，基本算法及基于信息素强度的蚁群 序列比对算法都能求得最优解并收敛到最优解。基于公式( 4 1 ) ，最优解得分为 8 0 ，匹配数4 4 ，不匹配2 ，空格6 。 用两种算法分别对上述序列进行10 0 次比对，每2 0 次为一组，记录最优得分， 最差得分，平均得分，及平均用时，记录如表4 2 ( 平均用时保留4 位有效数字) 。 表4 2 实验1 中两种算法的性能比较 由上表4 2 可知，在对上述平均长度约为5 0 的两序列进行比对时，两种算法 寻求最优解的能力未见区别，但基本算法的平均用时是基于信息素