（系统工程专业论文）两种群体智能算法的研究及其应用.pdf

摘要 群体智能是模拟自然界生物的群体行为而构造的随机优化算法，它为寻找一些复 杂问题如约束性，非线性和求极值等的解决方案提供了新的思路。蚁群算法与粒子群优 化算法是群体智能中的两种最重要的方法，将其应用到生物信息学中的基础任务序列比 对中正是本文的研究内容。 一方面，蚁群算法已被应用到序列比对中，但传统蚁群算法只能应用于相近长度的 序列比对且容易陷入局部最优。为通过蚁群算法获得一个准确的基因序列比对算法，本 文给出了一种新的基于蚁群算法的d n a 序列比对方法。该方法通过在不同时刻调节蚂蚁 起、止位置，修正信息素，来避免局部最优，特别是可以根据行走路径去除比对差异大 的路径得分，使算法具有较好比对不同长度序列的能力，一定程度上摆脱了传统方法的 应用局限性。实验结果表明这种新颖的序列比对算法是有效的和可行的。另一方面，粒 子群优化算法源于对鸟群运动行为的模拟，其特点是简单、需调整参数较少、收敛速度 快且易于实现，本文首先介绍了粒子群优化算法求解问题的优越性，并提出了一种粒子 群优化算法的改进：根据不同应用给出相应的自适性惯性权重，同时参考其它优秀粒子 的位置，均衡该粒子的当前最优位置，改进的粒子群算法具有使粒子更符合进化特点、 加快算法的收敛速度、改善粒子群优化算法的搜索性能、提高全局收敛的优点。本文将 粒子群优化算法应用于解决序列比对问题上，并结合序列比对特点给出了粒子初始位置 的约束条件和粒子在运动过程中的移动策略，通过实验说明了方法的可行性和有效性。 本文对改进后的蚁群算法和粒子群优化算法进行比较分别说明了各自算法在双序 列比对方面的特点。通过将改进后的蚁群算法和粒子群优化算法实际应用于松树e d n a 序列中特征的提取，证明了蚁群算法与粒子群优化算法在序列查找问题中的可行性，表 现了群体智能的广泛应用空间和令人满意的优化性能。 关键字：蚁群算法；粒子群算法；序列比对 a b s t r a c t s w a r mi n t e l l i g e n c ea l g o r i t h mi st h es t o c h a s t i co p t i m i z a t i o na l g o r i t h mw h i c hi ss i m u l a t e d t h eg r o u pb e h a v i o ro fb i o l o g i c a li nn a t u r e i tg i v e san e ww a yt of i n dt h es o l u t i o no fs o m e c o m p l e xp r o b l e m ss u c ha sc o n s t r a i n t s ，n o n l i n e a ra n dt h ee x t r a c t i o no fe x t r e m ev a l u e a n t c o l o n yo p t i m i z a t i o na l g o r i t h m ( a c o ) a n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ( p s o ) a r e t w oi m p o r t a n tm e t h o d so fs w a r mi n t e l l i g e n c ea l g o r i t h m i nt h i sp a p e r , a ni n - d e p t hr e s e a r c h w i l lb e d o n eu s i n gt h e s et w om e t h o d so ns e q u e n c ea l i g n m e n t o nt h eo n eh a n d ，t h et r a d i t i o n a la c oh a sb e e na p p l i e di ns e q u e n c ea l i g n m e n t ，b u ti ti s l i m i t e dt ot h ea l i g n m e n to fs i m i l a rl e n g t hs e q u e n c e sa n dl o c a lo p t i m u m t h u sd e v e l o p i n ga n a c c u r a t eg e n es e q u e n c ea l i g n m e n ta l g o r i t h mr e m a i n st ob eav e r yd i f f i c u l tc o m p u t e rp r o b l e m an e ws e q u e n c ea l i g n m e n tm e t h o db a s e do na c ow a sb r o u g h tf o r w a r di nt h ep a p e r t h e m e t h o dc o u l da v o i dl o c a lo p t i m u m ；e s p e c i a l l yr e m o v et h ew i d ed i f f e r e n c ep a t h s s c o r e sb y r e g u l a t i n gt h ei n i t i a la n df i n a lp o s i t i o no fa n t sa n dm o d i f y i n gp h e r o m o n e si nd i f f e r e n tt i m e t h e r e f o r et h em e t h o dh a st h ea b i l i t yo fa l i g n i n gs e q u e n c e so fd i f f e r e n tl e n g t ha n da v o i d i n g t h el o c a lo p t i m a lc a u s i n gb yt r a d i t i o n a la l g o r i t h m s t h er e s u l t ss h o wt h a tt h en o v e ls e q u e n c e a l i g n m e n ta l g o r i t h mi se f f i c i e n ta n df e a s i b l e o nt h eo t h e rh a n d ，p s os i m u l a t e st h eb i r d s m o t i o nb e h a v i o r , t h ec h a r a c t e ri ss i m p l e ，f a s tc o n v e r g e n c ea n de a s yt oi m p l e m e n t t h i sp a p e r f i r s ti n t r o d u c e dt h es u p e r i o r i t yo fp s of o rs o l v i n gt h ep r o b l e m s ，a n dt h e ng i v e nan e w i m p r o v e dp s o ：a c c o r d i n gt od i f f e r e n ta p p l i c a t i o n su s i n gt h ec o r r e s p o n d i n ga d a p t i v ei n e r t i a w e i g h t ，t a k i n gi n t oa c c o u n tt h ep o s i t i o n so fo t h e rp a r t i c l e st ob a l a n c eo ft h ec u r r e n tp a r t i c l e s p o s i t i o n t h ea d v a n t a g e so ft h i si m p r o v e m e n ti st h a tm a k i n gp a r t i c l em o r ec o n f o r mt ot h e e v o l u t i o nc h a r a c t e r i s t i c s ，h e l p i n gt os p e e du pt h ea l g o r i t h mc o n v e r g e n c e ，i m p r o v i n gt h e s e a r c hp e r f o r m a n c eo fp s o ，r e d u c i n gs h o r t c o m i n g so fl o c a lo p t i m i z a t i o na n di n c r e a s i n gt h e g l o b a lc o n v e r g e n c ec a p a c i t y t h i sa r t i c l ew a sa p p l y i n gp s o o nt h es e q u e n c ea l i g n m e n t ，g i v e n t h ec o n s t r a i n tc o n d i t i o no fi n i t i a lp o s i t i o no fp a r t i c l e sa n dm o v i n gs t r a t e g yi nt h ep r o c e s so f p a r t i c l e s f l y i n g b a s e do nt h ee x p e r i m e n t a l ，i tp r o v e dt h i sm e t h o di sf e a s i b l ea n de f f e c t i v e t h i sp a p e rc o m p a r e st h ei m p r o v e da c oa n dp s ow i t ht h es a m ed a t a , s h o w st h e i rs e l v e s c h a r a c t e r s u s i n gs e q u e n c ea l i g n m e n tt of i n dt h ef r a g m e n ti si m p o r t a n tf o rt h ee x t r a c t i o no f c l e a ns e q u e n c e t h i sp a p e ra l s oa p p l i e sa c oa n dp s ot ot h ee x t r a c t i o nt h ef r a g m e n to f c d n as e q u e n c e s ，p r o v e st h a tt h et w om e t h o d so ns e a r c h i n gs e q u e n c ef r a g m e n ta r ef e a s i b i l i t y ； s h o w sa c oa n dp s oh a v et h eg r e a tp o t e n t i a la n ds a t i s f a c t o r yo p t i m a lp e r f o r m a n c e k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ；s c o r e 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人 在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以适当 方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的资助， 在() 实验室完成。( 请在以上括号内填写课题或课题组 负责人或实验室名称，未有此项声明内容的，可以不作特别声明。) 声明人( 签名) ：超参哆斗 2 p 口7 年月z 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等 规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包 括纸质版和电子版) ，允许学位论文进入厦f - j ：k 学图书馆及其数据库被查 阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共 建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、 缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文，于 年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文应是 已经厦门大学保密委员会审定过的学位论文，未经厦f - j ：k 学保密委员会审 定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论 文，均适用上述授权。) 声明人( 签名) ： 吒 赵鲫 年歹月工日 第一章绪论 第一章绪论 从2 0 世纪5 0 年代中期开始，仿生学日益受到人们的重视。随着计算机技术的飞速 发展，计算技术的手段和方法也不断更新和升级，许多新理论和新技术不断向算法领域 移植和渗透，其中仿生学的发展为算法设计提供了更广阔的外延空间。生物在进化过程 中形成的极其精确和完善的机制，使它们具备了适应内外环境变化的能力。生物界具有 许多卓有成效的本领。如体内的生物合成、能量转换、信息的接受和传递、对外界的识 别、导航、定向计算和综合等，造就了适应生态环境的生物系统，显示出许多机器所不 可比拟的优越之处，。因此，利用仿生学创造在结构、功能、控制、能耗等诸方面更具 有竞争力的计算方法，越来越受到学者的重视。涉及仿生学的仿生方法将会在更多、更 深、更广的层次达到广泛应用。 1 1 仿生学 仿生学( b i o n i c s ) 是模拟生物界动物和植物的功能来解决人类技术上问题产生的一 门交叉学科，涉及了生物学、物理学、控制论、工程学等学科领域。它以自然进化和共 同进化为基础，以分析生物过程和结构、并将这些分析用于未来的设计为目的，以自然 生物系统构造和生命活动过程作为技术创新设计的标准，有意识地进行复制，它是使人 类社会逐步由向自然索取转入向自然界学习和创造世界的新纪元u 1 。 1 9 6 0 年由美国j e s t e e l e 最先提出仿生学( b i o n i c s ) ，仿生学这一名词由希腊语 b i o s ( 意思是生命) 和n i c ( 意思是具有的性质) 共同构成的，也是近几年国际学术讨 论一个热门主题。这个新的科学研究方法论给科学、生产、社会，甚至人类发展、更新 开辟了一条新的途径，是寻找并解决人类问题的生物科学与技术科学之间的边缘学科。 目前对于仿生学的研究范围和领域很难予以划定和区分，其主要原因：( 1 ) 从生物 系统获取灵感的范围和数量相当巨大；( 2 ) 相当复杂的协调体系和集合性功能。因此， 要简单地归纳若干仿生范围或领域是很困难的。一般可将仿生学划定为：结构与材料、 机理和能量、行为与控制、信息传递与传感器、生殖与生命活动等覆盖面较大的领域： 随着时代的发展变化，仿生学越来越受到人们的关注，正以令人吃惊的程度影响着 新技术的革新。未来将有更多的科学家关注自然界的规律，在长期向大自然学习的过程 两种群体智能算法的研究及其应用 中，积累经验，通过观察生物界的系统结果和性质，探索新的技术和设计原理。同时， 随着科学的高速发展和人们对自然界认识的不断提高，仿生学的应用具有巨大的潜力和 发展前景，它正以意想不到的速度渗入生命科学，揭示生命活动过程的奥秘的同时，也 拥有了更广泛的用武之地。 1 2 进化算法 进化算法( e a ，e v o l u t i o n a r ya l g o r i t h m ) ，也称进化计算，是根据生物进化和遗传 的规律，借助群体的繁殖、竞争、突变等过程，实现“生存竞争，优胜劣汰”，逐步逼 近目标问题的最优解，是一种具有自适性的模拟自然进化过程的随机优化方法。与传统 的优化技术比较，进化算法的主要特点是群体搜索策略和群体间个体之间的信息交换。 它们的优越性主要表现在：首先，进化的操作规则是概率性的而非确定性的，在搜索过 程中不易陷入局部最优；其次，由于它们固有的并行性，进化结果不局限于单值解，非 常适合求解复杂的多目标问题；再次，进化算法采用自然进化机制来表现复杂现象，充 分利用适应值函数而不需要其它先验知识，能够快速解决传统方法难以解决的问题乜1 。 进化算法( e v 0 1 u t i o n a r ya l g o r i t h m s ) 包括遗传算法、遗传规划，进化策略，进化规 划四种典型方法。它们都是将生物界中进化与遗传的机理与其他技术手段相结合的方 式，各自发挥特长，综合解决复杂的技术问题。 同样，受进化算法的启发，人们提出了一系列新的进化算法分支，如t b a c k 的专著 进化算法的理论与实践：进化策略、进化规划、遗传算法阐明了许多传统的复杂优 化问题，现阶段已从深度和广度上发展成为较成熟的优化算法。随着时间的推移，进化算 法会与其它学科不断交叉渗透，具有更广阔的应用范围并发挥越来截止重要的作用。 群体智能( s w a r mi n t e l l i g e n c e ) 这个概念来自对自然界中蚂蚁和蜜蜂等昆虫群体行 为的观察。群居昆虫以集体的力量进行觅食、御敌、筑巢等，单个个体只能完成简单的 任务，而由单个个体组成的群体却能完成复杂的任务。3 。如蚂蚁觅食、蜜蜂采蜜，只 蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，但蜂群或蚁群 却能够共同完成任务，建立巢穴，搬运食物、养育后代，因此它们是可以呈现高度的社 会组织性智能行为。由于群群体的合作，蚂蚁群体可以实现复杂的工作，这大大超过蚂 蚁个体的能力。这种群居性生物表现出来的集体智慧和行为被称为群体智能。 群体智能方法是通过模拟自然界生物的集体智能行为来实现人工智能，群智能科学 与其它学科相互渗透，已应用于电子、通讯、自动控制、医疗、光学和生物学等领域。 2 第一章绪论 可以建立群体智能的数学模型h 1 ： 设有一个群体，包含有以个个体( 每个个体的能力均相同) ，每个个体具有一个能力 厂。即每个个体能完成某一函数运算厂。其次，每个个体可以与邻近的个体进行“通讯 ， 即将某一信息传递给对方。每个个体的行动是随机的。当每个个体接收到终止的指令， 就停止工作。这时，整个任务就完成。 群智能优化，是利用群体的协作、交互和组织来进行智能优化的理论，它的目的是 利用他们的某些特点去解决实际问题。由于个体所能获得的信息远比它通过自身感觉器 官所取得的多，其根本原因在于个体之间存在着信息交互能力。因此，通过如何研究通 过群内单个个体的沟通、信息交流、组织来了解产群体的智能优化行为是非常重要的课 题。群体智能中的个体指具有简单的智能和能力的个体。群体是指“互相之间可以进行 某种简单的直接通信或通过改变环境间接通信，从而受外界和内部条件影响并自我调节 的主体”。群体智能的优点啼1 可以描述如下： 1 ) 分布性：群体中相互合作的个体是分布式的，不存在中心控制。这样的分布式更 适合于网络环境下的工作状态。 2 ) 稳健性：系统没有集中的控制指令与数据存储，这样的系统更具有鲁棒性，会由 于某一个或者某几个个体的故障而影响整个问题的求解进程。 3 ) 可扩充性：系统不通过个体之间的直接通信，而通过非直接通信方式进行信的传 输与合作，这样的系统具有更好的可扩充性，由于系统中个体的增加而增加的信开销也 较小。 4 ) 简单性：系统中每个个体的能力十分简单，每个个体的执行时间也比较短，且实 现较为方便。 5 ) 自组织性：群体表现出来的复杂行为是通过简单个体的交互过程突现出来的能 ( e m e r g e n ti n t e lli g e n c e ) 。 目前由于所研究实际系统的大多是非线性系统，而且规模大，约束条件多系统异 常复杂，致使系统优化难度越来越大，因此，探寻智能的适合大规模并行计算疗法将成 为各学科的研究热点，正是在这个大背景下出现了基于群体机制的智能优化研究。较经 典的优化方法，比如遗传算法、禁忌搜索和模拟退火等，相对而言已经比较成熟。站在 群体协作的智能优化研究角度考虑问题将是智能优化领域的一个重要发展趋势。 群智能方法在大多数优化问题的应用领域都表现出较好的性能。现在已应用到其应 3 两种群体智能算法的研究及其应用 到多目标优化、数据分类和聚类、模式识别、电信管理、生物系统建模、流程规划、信 号处理、机器人控制、决策支持以及仿真和系统辩识等领域，为解决这些应用问题提供 了新的途径。在计算智能领域已取得成功的两种基于群智能的优化算法是蚁群优化算法 和粒子群优化算法。 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 是为解决组合选择问题 而设计的启发式算法。是由意大利学者d o r i g o m ，m a n i e z z o v ，c o l o r i n i a 等在2 0 世纪 9 0 年代初首先提出的，并称之为蚂蚁系统( a n ts y s t e m ，a s ) ，用来解决复杂优化问题。 从那时开始，很多相关文章中算法中出现有关蚁群算法基本原理中参数的研究。蚁群算 法的主要特征是通过将分布式个体之间的间接通信将可能具有前景的信息和已获得的 信息相结合。启发式算法不同于以往的传统算法，其起源于一些启发示的算法：可能是 建设性启发式算法，也可能是局部搜索启发式算法，通过一个完全解并适时调整参数迭 代获得更好的解。实际上，作为一种新型的模拟进化算法，与其它优化算法相比，a c o 算法的特点是适应性好、鲁棒性强、具有正反馈结构。正反馈过程使得该算法能够发现较好 解：分布式计算使得该算法易于并行实现，更快得到较好解：与启发式算法相结合，使得 该算法易于朝着可能含有高质量解的搜索空间进行搜索，这些特点为相关的难解复杂组 合优化问题提供了解决方式。 蚁群算法一经提出，便引起了学术界的广泛关注，许多研究者对其产生了浓厚的兴 趣，并成功地应用到了许多领域，首先应用于求解旅行商问题并取得较好的效果，学者 们对该算法进行了各种改进，并陆续渗透到更广泛的领域中，如应用到车辆调度哺1 、系 统辨识、数据挖掘以及负载平衡问题等问题中。例如在解决典型的组合优化问题t s p 问 题时，和遗传算法等其它进化算法相比，蚁群算法获得了更好的实验结果：而对于其它复 杂的组合优化问题、分布控制问题以及聚类分析问题也提供了很好的解决思路。受其影 响，蚁群算法逐渐引起了更多学者的注意，并在此基础上提出了许多改进的算法。通过这 些算法，一些比较复杂的大规模组合优化问题得到了很好的解决。随着蚁群算法在世界 范围内的广泛应用，从1 9 9 8 年丌始蚁群算法国际研讨会陆续召开，在推动了蚁群算法的 发展的同时，也显示了其发展的巨大潜力。自1 9 9 8 年国内研究蚁群算法的学者越来越 多，且算法发展水平较快，现已成为相关领域的热门研究方向，在启发式方法范畴蚁群算 法已成为一个独立的分支，其应用层出不穷，说明它是一种很有发展前景的模仿自然生 物的新型寻优算法。 4 第一章绪论 微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 也称为粒子群优化算法，是属 于计算智能领域，除了蚁群优化算法以外的另一种群体智能算法。与大家熟悉的遗传算 法( g a ) 相似，p s o 是通过个体间的合作和竞争逐次迭代来实现全局的搜索。是美国社会 心理学家j a m e sk e n n e d y 和电气工程师r u s s e l le b e r h a r t 于1 9 9 5 年共同提出的。鸟群在 飞行过程中经常会突然改变方向、散开、聚集口3 ，但鸟群具有强烈的总体性，p s o 原理是 启发于上述对早期对鸟类群体捕食行为研究，并根据生物学家f r a n kh e p p n e r 的生物群 体模型而构建的结果。 在微粒群算法的改进方面，首先也是由k e n n e d y 和e b e r h a r t 提出的二进制p s o 算法， 主要应用于p s o 算法与遗传算法的性能比较。s h i e 和b e r h a r t 于1 9 9 8 年对p s o 算法做出改 进，在速度项引入了惯性权重国，为了平衡收敛的全局性和收敛速度，提高算法的收敛 性能，使得粒子在空间中的探索能力得到合理的分配，提出在进化过程中动态调整惯性 权重，被相关学者称之为标准p s o 算法。1 9 9 9 年c l e r c 为保证算法的收敛性，同时降低速 度的限制，在标准p s o 算法中引入收缩因子。该方法已被有关学者进行了详细的算法分 析，并给出了指导性建议，如参数的选择等。1 9 9 9 年a n g e li n e 将进化计算的选择概念引 入p s o 算法中。为提高算法的收敛性，算法将各个粒子的适应值相比较，并淘汰适应奉较 差的粒子，从而复制具有较高适应值的粒子。而l o v b j e r g 等人进一步将复制、交叉等进 化计算机制应用于p s o 算法，为说明算法性能利用典型测试函数通过仿真实验证实了算 法的有效性。 p s o 算法的行为、收敛性方面和应用方面陋1 学者们也进行了大量的研究。为保证收敛 给出了参数选择范围，主要操作是将代数方法用于几种典型的p s o 的运行机制并分析了 其运行轨迹。在收敛性方面，根据s o l i s 和w e t s 关于随机性算法的收敛准则，f r a n sv a n d e nb e r g h 证明了标准p s o 不能收敛于全局最优解，甚至于局部最优解。证明了保证收敛 的p s o 算法能够收敛于局部最优解，而不能保证收敛于全局最优解。最早人们将p s o 算法 应用于人工神经网络的训练方法，并成功地将p s o 算法应用于分类x o r 问题的神经网络训 练咖。随后，p s o 算法成功的应用于函数优化问题、带约束优化问题。”：、极大极小问题、 多目标优化n 妇等问题中，特别是在电力系统、集成电路设计、系统辨识、状态估计等问 题中的应用均有报道阳1 。 1 3 本文的主要工作 本文以蚁群算法和粒子群优化算法两种主要的群体智能算法为主要研究内容，主要 5 两种群体智能算法的研究及其应用 工作包括三个方面： 1 ) 在前人已提出的a c o 比对算法的基础上，给出一种改进型a c o 序列比对方法。此 算法运用蚁群算法结合局部优化的机制来求解d n a 序列比对，首先给出蚁群双序列比对 模型，并在此基础上为解决标准蚁群算法的易陷入局部最优的问题，提出了新的蚁群比 对算法，通过一种新方式调节蚂蚁起始位置，更新信息素，设置多个终止位置，并去除 行走路径比对差异大的得分，来避免局部收敛并提高搜索全局最优解的能力，并通过基 本a c o 序列比对方法与改进后的蚁群序列比对来证实该改进算法能更快收敛的能力。 2 ) 改进标准粒子群优化算法，在算法中将该粒子当前的局部最优位置与其它好的 粒子当前局部最优位置做比较，共同决定该粒子的局部最优位置，同时根据实际应用动 态地改变惯性权值，这些改进使粒子运动更符合事物发展原理，收敛更易接近全局最 优；使粒子群优化算法具有较强的全局收敛能力。将粒子群优化算法应用到双序列比对 中，根据序列比对特点将粒子群优化算法进行改造，构造了序列对矩阵，粒子以矩阵左 上角为起始位置，以矩阵右下角为终点，作为一次迭代，根据粒子最优坐标点为最优比 对，目标函数系数根据字符是否匹配设定，若粒子移动到下一行，下一列，则原来经过 的行、列不能再次经过，通过该方法寻找最优匹配的子序列。实验验证了该改进算法更 具有搜索解空间的能力。 3 ) 将改进后的a c o 序列比对方法与粒子群序列比对优化算法进行比较，体现了两者 各方面的优缺点。并将改进后的a c o 序列比对方法和p s o 序列比对方法应用于查找c d n a 序 列( 与r n a 链互补的碱基序列的单链d n a 即c o m p l e m e n t a r yd n a ) 特征的实验，验证蚁子该 方法在长度差异大的序列中具有很强的发现较好解的能力，不容易陷入局部最优，可收 敛于解空间的某一子集；p s o 序列比对方法相对于a c o 序列比对方法能够较快收敛于某一 解，但查找较模糊。 1 。4 本文组织 本文共分五章，主要内容如下： 1 ) 第一章介绍了仿生学，进化算法及其中的群体智能研究现状、发展趋势，介绍 了两种常见的群集智能算法一蚁群算法、粒子群优化算法。给出了本课题的研究意义。 详细介绍了蚁群算法和粒子群优化算法的研究现状及在组合优化问题中的应用。最后， 阐明了本论文的主要任务和研究意义。 6 第一章绪论 2 ) 第二章分别研究蚁群优化算法与粒子群算法的原理、参数设置等问题。首先针 对t s p 问题构建模型，介绍了基本a c o 序列比对方法，其次详细阐述了粒子群优化算法的 基本原理，并构建算法模型，同时在已有研究理论的基础上，给出将改进粒子群优化算 法的思路和方法。并通过实验比较了改进前后的粒子群优化算法。对两种算法进行比较， 分析各自特点。 3 ) 第三章提出了一种可应用于查找子序列的a c o 序列比对方法的改进策略，将原算 法与改进后算法做比较：将粒子群优化算法应用于序列比对。将改进后的a c o 序列比对方 法与粒子群序列比对优化算法分别应用于查找e d n a 序列的实际问题中。首先给出序列比 对的基本知识，并将两种算法分别应用于长短序列比对，分析实验结果和给出结论。 4 ) 第四章比较两种模型在解决双序列比对一类离散问题性能。分别对长短序列特 征查找给出实验与结果，并对结果进行分析，比较了两种序列比对方法各自优缺点。 5 ) 第六章结束语，总结本文的主要工作，指出未来的研究方向。 7 两种群体智能算法的研究及其应用 第二章蚁群算法与粒子群算法 2 1 蚁群算法 自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一就是 探索自然界生物的群体行为，从而在计算机上构建其群体模型。通常，群体行为可以由 几条简单的规则进行建模，如鱼群、鸟群等。虽然每一个个体群体是非常简单的行为规 则，但群体的行为却非常复杂。群体智能一种新生的进化算法，从提出到现在，虽然仅短 短十几年的时间，但是由于在解决离散型组合优化问题时表现突出，所以引起了人们的 广泛关注。 蚂蚁群体，可以看作是一个分布式系统。单个个体都非常简单的整个蚂蚁群体系统 却呈现出一种高度结构化的群体组织。蚂蚁群体之所以能完成一些单只蚂蚁个体能力难 以负荷的复杂工作，正是因为这个群体组织的存在。群体中的个体之间以及个体与环境 之间的信息传递大部分是依据蚂蚁产生的化学物质进行的。这些化学物质被称为信息素 ( p h e r o m o n e ) ，不同于人类以及其他高级种群之间所使用的感知方式，蚂蚁这种特有 的信息传递方法。而路径信息素对于某些蚂蚁来说，在它们的群居生活中具有极其重要 的使用。蚂蚁正是通过对其他蚂蚁释放的路径信息素做出反应，依据其强度来沿途觅食。 a c o 算法的灵感来源正是这种根据其他蚂蚁所释放的化学物质信息来判断群体的路径选 择的行为方式。当蚂蚁食物源与蚁穴运动时，都会在经过的路径上留下的信息素，从而 形成了一条含有信息素的路径。蚂蚁可以对路径上信息素的浓度大小进行判断，并且做 出概率上的选择信息素浓度最高的路径，因此蚁群总是能够找到从巢穴到食物源之间的 一条最短路径口引。 2 1 1 双桥实验 d e n e u b o u r g 及其同事通过“双矫实验 n 钔对蚁群的觅食行为进行了研究，他们使 用了一个双桥来连接蚂蚁的蚁穴和食物源。他们在实验的过程中测试了一级不同比例的 ，= ，l 值，其中，是双桥上的上两个分支之间的长度比例，是较长分支的长度，而 是较短分支的长度。在第一个实验中，桥上的两个分支的长度是相同的即( 广= 1 ，如图 2 1 a 所示) 。开始的时候，蚂蚁可以自由地在蚁穴和食物源之间来回移动，实验目的就 8 第二章蚁群算法与粒子群算法 是观察蚂蚁随时问选择两条分支中某一条的百分比。实验的最终结果显示，尽管最最初 蚂蚁通常随机选择某一条分支，但是最后所有蚂蚁都会选择同一条分支。这个实验结果 可以用以下方法进行解释。由于刚开始时两条分支上都不存在信息素，因此蚂蚁对这两 条分支的选择就不存在任凭偏向性，以相同的概率在这两条分支间进行选择。然而，由 于随机波动的出现，选择某一条分支上的蚂蚁数量可能会比另外一条多。正是因为蚂蚁 在移动的过程中会释放比另多 l - - 条多；而这种更高浓度的信息素将会促使更多的蚂蚁再 次选择这一条分支，这个过程一直进行，直到最后所有蚂蚁都集中到某一条分支路径上。 这种自身仿佛或者正反馈的过程，实际上就是蚂蚁实现自组织行为的一个例子，一种宏 观模式的出现来自于微观层次上的过程与交互作用。在这个实验中，蚂蚁的路径集中到 某一条分支上的过程显示的是宏观上的群体行为，此行为可以通过蚂蚁的微观行为得到 解释，也就是通过群体中个体之间的局部交互过程来解释。 在第二个“非对称双桥”u 副实验中，两条分支的长度比例设为，= 2 ，因此较长的 那条分支的长度是较短那条的两倍( 如图2 - 1 b ) ，在这种设置条件下，大部分实验结果 显示，经过一段时间后所有的蚂蚁都会选择较短的那条分支，与第一个实验样，蚂蚁 离开蚁穴探索环境，它们到达了一个决策点，在这里需要在两条分支之间做出选择。一 开始两条分支对蚂蚁来说都是一样的，因此它们会随机选择两条中的一条。正因为这样， 尽管有时会由于出现一些随机摆而使得某一条分支比另外一条分支上的蚂蚁数量多，但 平均而言，仍然可以期望会有一半的蚂蚁选择较短的分支，而另外一半选择较长的分支。 然而，此实验采取了一个与先前的实验完全不同的设置：由于一条分支比另外一条分支 短，选择了较短分支的那些蚂蚁会首先到达食物源，并开始返回它们的巢穴。当返回的 蚂蚁需要再次在短分支和长分支之间做出选择时，短分支上的高浓度信息素将会影响它 们的决定。正因为短分支上的信息素积累速度要比长分支的快，最终所有蚂蚁都会选择 较短的那条分支。 与两条分支长度相同的实验相比，在本实验中仞始随机波动的影响大大减少，起作 用的主要是媒介质、自身催化和差异路径长度等机制。有趣的是，据观察，虽然较长的 分支是短分支长度的两倍，但并不是所有蚂蚁都会使用较短的分支，相反有很小比例的 蚂蚁会选择较长的分支。这种情况可以解释为一种“路径探索”行为。 9 两种群体智能算法的研究及其应用 图2 一l a图2 1 b 2 1 2 人工蚁群算法 由前面可知，受到自然界中真实蚁群集体行为的启发，意大利学者m d o r i g 于1 9 9 1 年首次系统地提出了一种基于蚂蚁种群的新型优化算法一蚁群算法，更恰当的说法应该 是“人工蚁群算法”，他设计了一种人工蚂蚁，这种蚂蚁运动行为具有以下特性： 1 ) 假设时间是离散的，在每一时间点中，蚂蚁都以一个恒定速度向相邻点移动； 2 ) 人工蚂蚁是真实蚂蚁行为的一种抽象，即具有真实蚁群觅食行为中关键的部分： 3 ) 每只人工蚂蚁会在经过的边上释放同等量的信息素，并在移动过程中是基于一 定概率选择路径，朝向问题的邻近状态移动； 4 ) 每只人工蚂蚁通过移动能够得到一个解决方案，但是目标解决方案是整个蚁群 合作的结果。 5 ) 人工蚂蚁通过对系统演化过程中自调节作用，使问题的解朝着全局最优解的方 向进化，最终有效的获得相对较优解。 6 ) 人工蚁群算法中存在着一种挥发机制，这种方式可以使蚂蚁不容易受过去群体 经验的过分约束，有利于其向着各个方向进行搜索，选择一个新的方向，避免过早收敛。 人工蚁群算法的行为实际上是一种分布式的协同优化机制，虽然蚂蚁个体能够找到 蚁穴与食物源之间的一条路径方案，但是找到最短路径的可能性很小，只有当蚁群寻找 食物源时，其集体行为才突现出蚂蚁的群体协作智能一发现最短路径的能力n 引。蚁群通 过使用了一种间接的通信方式来寻找最短路径，即在经过的路径上释放一定量的信息 素，在接下来时刻其它蚂蚁若经过这条路径，通过感知信息素的浓度来选择下一步要走 的路。即信息素在蚁群的协作和沟通中起到一种间接媒介的作用。因此，通过更新问题 的状态变量，人工蚂蚁可以模拟真实蚂蚁更新信息素的行为。觅食行为中存在一种重要 的机制一正反馈机制，它将指引蚁群找到高质量的问题解空间，但要注意尽量避免早熟 现象：同时，蚁群算法还有另外两个机制：信息素挥发机制( p h e r o m o n e t r a i1 e v a p o r a t i o n ) 1 0 第二章蚁群算法与粒子群算法 和后台行为( d a e m o n a e t i o n s ) 。一种高级的智能行为被称为遗忘( f o r g e t t i n g ) ，路径上 的蚂蚁留下的信息素作为遗忘的一种形式，会随着时间推移不断挥发，有利于人工蚂蚁 探索解空间中新的领域，从而避免蚁群在搜索解空间过程中过早陷入局部最优解的情 况。后台行为包括局部搜索过程以及目标的全局信息收集过程。蚁群算法是一种基于种 群的构造型的自然启发式优化算法，如果这种构造与改进型迭代方法相结合，如局部搜 索，效果会更好。总的来说，人工蚁群算法的主要特点u 7 1 可以概括为以下几点： 1 ) 采用分布式控制，不存在中心控制： 2 ) 每个个体只能感知局部的信息，不能直接使用全局信息： 3 ) 个体可以改变环境，并通过环境来进行间接通讯： 4 ) 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能： 5 ) 是一类概率型的全局搜索方法，这种非确定性是算法能够有更多的机会求得全局 最优解： 6 ) 其优化过程不依赖于优化问题本身的严格数学性质，比如连续性、可导性以及目 标函数和约束函数的精确数学描述： 7 ) 是一种基于多主体( m u l t l a g e n t ) 的智能算法，各主体之问通过相互协作来更好的 适应环境： 8 ) 具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行。 这种分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法 的运行效率和快速反应能力。 首先，蚁群算法是一种并行算法。蚂蚁在搜索的过程中相互独立，只通过信息素进 行间接的通讯，而并行计算是可以显著减少计算时间的，所以蚁群算法在计算量较大的 情况下可考虑选择的好方法。同时，蚁群算法也是一种正反馈算法。在整个过程中若在 一段路径上的残留信息素较高，将更容易吸引其它蚂蚁选择这条路径，从而会使得这条 路径的残留的信息素水平增加。正是由于诈反馈的存在，使得整个搜索过程加速收敛。 相对于其它算法，蚁群算法的初始条件的设置对将来结果的不会有太大的影响，即蚁群 算法的搜索结果不依赖于初始路径的选择。蚁群算法的搜索过程是通过完全自行调节 的，相对于那些需要进行人工干预的算法( 例如模拟退火算法) ，蚁群算法就有了那些它 们所没有的优越性，从而使蚁群算法可以在不需要人工干预的情况完成从初始化到得到 搜索结果的整个计算过程。 两种群体智能算法的研究及其应用 由于蚁群算法上述等特点，在解决小规模的问题时效果显著，但对于规模较大的问 题，在性能方面容易迅速恶化。主要原因是，算法的初始阶段，各路径上的信息素水平 基本相等，蚂蚁的搜索呈现的随机性较大。但经过较长时间后，信息素水平不同呈现出 明显不同的引导效果。另外，由于蚁群算法的正反馈性，使算法速度收敛较快的同时， 也容易陷入局部最优。蚁群算法的上述不足，导致其在处理大规模复杂性问题时性能下 降明显d 8 1 。为解决大规模旅行商问题，1 9 9 6 年，m d o r i g o 提出了以三点对蚁群算法的 改进：蚂蚁选择目标城市的方式，信息素的全局更新及信息素的局部更新。自此以后， 蚁群算法逐渐引起广大学者的关注，而大量有价值的相关研究成果的陆续发表拓宽了蚁 群算法的应用领域。 2 1 3 算法模型 最早提出的一种蚁群算法主要是以求解n 个城市旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e mt s p ) ，下面以t s p 问题为例说明基本蚁群系统模型，t s p 问题就是商人从自己 所在城市出发，希望找到一条既能经过给定顾客所在城市，又能在回家前遍访每一个城 市一次的最短路径。 每只蚂蚁都具有以下特性： 1 ) 完成每次循环，蚂蚁在其访问过的每条边上留下相应的信息素： 2 ) 蚂蚁根据一定概率选择下一个将要访问的城市，这个概率由两城市间距离及连 接两个城市的边上信息量来决定： 3 ) 为了满足问题的约束条件，在一个循环中，不允许蚂蚁选择己经访问过的城市， 该过程由蚂蚁的禁忌表来控制。若蚂蚁在经过城市歹以后，就将城市加入到自己的禁忌 表中，下次将不会再选择城市。 则t s p 的蚁群算法表述如下： 1 ) 设俄是蚁群中蚂蚁的数量，d 时( f ，歹= 1 , 2 ，嚣) 表示城市f 和城市，之间的距离， 2 ) 6 l ( f ) 表示，时刻位于城市f 的蚂蚁的个数，有，6 i ( f ) = m ， i = l 3 ) 勺( f ) 表示f 时刻在城市f 和城市，之间上的残留的信息素，当蚂蚁完成了一次循 环之后，相应边上的信息素必须进行更新处理，信息素有一定的初始时刻，设各条路径 上信息量决相等， 1 2 第二章蚁群算法与粒子群算法 当经过刀个时刻，蚂蚁完成了一次循环之后，相应边上的信息素必须进行更新处理， 蚂蚁根据下式调整为： 勺( f + 刀) = p 。r o ( t ) + a r v 勺= 瑶 (