（计算机软件与理论专业论文）基于免疫进化与协同进化的移动机器人路径规划.pdf

摘要 移动机器人的研究和开发近年来受到了人们的高度重视。人们要 求机器人在运动过程中能够根据周围环境的变化而自主的采取相应 措施的能力也越来越强。因此，作为机器人智能的一个重要因素 路径规划就显得尤为重要。路径规划是按照某一性能指标搜索一条从 起始状态到目标状态的最优或近似最优的无碰路径。本文作者主要针 对移动机器人路径规划及其相关的一些关键技术展开了研究。论文的 主要研究工作如下： 首先介绍了移动机器人路径规划及其相关理论( 包括机器人导航、 人工免疫系统和协同进化计算等三个方面) 的研究背景和国内外研究 现状。接着重点探讨了结合免疫进化和协同进化算法的单机器人和多 机器人路径规划问题。 对于单机器人路径规划，针对现有基于进化算法的路径规划方法 所存在的易陷入局部最优和缺乏指导性的缺点，本文作者提出了一种 基于免疫进化的路径规划方法。该方法针对机器人路径规划的实际应 用，优化了变异算子，引入了免疫接种，免疫克隆等免疫机制，使得 较优个体能较早的生成，从而保证了算法的收敛速度和种群的多样 性，防止了早熟收敛，提高了全局搜索能力。仿真结果表明，该方法 对复杂地图有良好的适应能力，能有效地保证路径的规划效率并改善 路径规划的质量。 针对多机器人路径规划的特点，根据协同进化模型以及免疫机制， 提出了一种基于协同免疫进化的多机器人路径规划方法。该方法通过 免疫进化方法在保证单个机器人路径的质量的同时，同时利用各群之 问的信息交换，有效的保证机器人互相之间的路径的协调性，在机器 人避障的同时有效的避碰。通过仿真实验和机器人实验表明，该方法 能有效果的对多机器人进行路径规划。 关键词路径规划，免疫进化，协同进化，多机器人 a b s t r a c t t h er e s e a r c ha n dd e v e l o p m e n to fm o b i l er o b o t sh a v eb e e np a i dg r e a t a r e n t i o nt oi nr e c e n t y e a r s t h er e q u i r e m e n to fi t sa b i l i t y t ot a k e c o r r e s p o n d i n gm e a s u r e si na c c o r d a n c ew i t ht h ee n v i r o n m e n t a lc h a n g e si n i t sm o v i n gc o u r s e sh a sb e c o m eh i g h e ra n dh i g h e r t h e r e f o r e ，t h ep a t h p l a n n i n g ，a sa ni m p o r t a n tf i e l di nr o b o ti n t e l l i g e n c e ，a p p e a r sp a r t i c u l a r l y s i g n i f i c a n t p a t hp l a n n i n gi ss e a r c h i n gao p t i m a lp a t hw i t h o u tt o u c hf o r m t h es t a r tt ot h ee n du n d e rw a yap e r f o r m a n c ei n d i c a t o r s t h ea u t h o r m a i n l yf o c u s e so nt h es t u d yo ft h ep a t hp l a n n i n go fm o b il er o b o t sa n di t s r e l e v a n tp r o b l e m s f o l l o w i n ga r et h em a i nc o n t e n to f t h i st h e s i s ： f i r s t l y , t h i sd i s s e r t a t i o ni n t r o d u c e st h er e s e a r c hb a c k g r o u n da n d s t a t u sq u oo fp a t hp l a n n i n ga n dr e l a t i v et h e o r y a f t e r w a r d s ，an e wr o b o t p a t hp l a n n i n gm e t h o da n dan e wm u l t i r o b o t sp a t hp l a n n i n gm e t h o d p r o p o s e db ya u t h o ra n di n t e g r a t e db yt h ev i r t u eo fi m m u n eo p e r a t i o na n d c o e v o l u t i o n a r y c o n s i d e r i n gt h ed r a w b a c ko fe a s i l yb e i n gt r a p p e di nal o c a ls o l u t i o n a n dl a c ko fg u i d a n c eo ft r a d i t i o n a le v o l u t i o na l g o r i t h mo ns i n g l e r o b o t p a t hp l a n n i n g ，an e wr o b o tp a t hp l a n n i n gm e t h o db a s e do ni m m u n e e v o l u t i o na l g o r i t h mh a sb e e nd i s c u s s e d t h i sm e t h o di n t r o d u c et h e i m m u n i t yo p e r a t i o na n do p t i m i z et h eo p e r a t o rw h i c hc a ng e n e r a t eg o o d i n d i v i d u a l se a r l i e ra n da c c e l e r a t et h ea l g o r i t h m sc o n v e r g e n c e a tt h e s a m et i m e ，i tc a nm a i n t a i nd i v e r s i t yo ft h ea n t i b o d i e sa n di m p r o v eg l o b a l s e a r c ha b i l i t y t h er e s u l t so fs i m u l a t i o ns h o wt h a tm e t h o dh a sb e r e r a d a p t i v ea b i l i t yt o w a r d sc o m p l e xm a p sa n di ti sf e a s i b l ea n de f f i c i e n tf o r i m p r o v i n gt h ep e r f o r m a n c ea n dq u a l i t yo fp a t hp l a n n i n gf o rm o b i l er o b o t a c c o r d i n gt ot h e f e a t u r eo fm u l t i r o b o t s p a t hp l a n n i n g a n dt h e c o e v o l u t i o n a r ym o d e l ，an e wm u l t i r o b o t sp a t hp l a n n i n gm e t h o db a s e d o n i m m u n ec o e v o l u t i o n a l g o r i t h m h a sb e e nd i s c u s s e d i tc a np r e v e n t m u l t i r o b o t sc o l l i s i o nw h e nk e e ph i g hq u a l i t yp a t hp l a n n i n gr e s u l tt ot h e e v e r ys i n g l ep a t h f r o mt h er e s u l t so fs i m u l a t i o na n dt h em u l t i r o b o t p a r k i n ge x p e r i m e n t ，w ec a nc o n c l u d et h i sm e t h o di sh i g he f f i c i e n ti n p e r f o r m i n gt h em u l t i - r o b o t sp a t hp l a n n i n g k e yw o r d sp a t h p l a n n i n g ，i m m u n e e v o l u t i o n a l g o r i t h m ， c o e v o l u t i o na l g o r i t h m ，m u l t ir o b o t s i l i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：坐盈年工月鱼日 硕+ 学位论文第一章概述 第一章概述 本章主要回顾本文相关方向的发展历史和研究背景，并分析了这些相关方向 的研究现状。最后为本文的章节安排。 1 1 研究背景 1 1 1 机器人导航与路径规划 导航是移动机器人不可缺少的基本能力，因此移动机器人导航技术从6 0 年 代就开始得到了研究。移动机器人在它的运动过程中始终要解决三个关键导航问 题：( 1 ) “我现在在何处? ”；( 2 ) “我要往何处去? ”；( 3 ) “我要如何到达 该处? 刀。其中( 1 ) 是移动机器人导航的定位问题。问题( 2 ) 和( 3 ) 是移动机器人 导航系统中的路径规划问题。 路径规划是移动机器人导航技术中不可缺少的重要组成部分，它要求机器人 根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标路径 规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化幢1 程度的重 要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路 径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高 移动机器人的智力水平，减少移动机器人在移动过程中存在的不确定状态，提高 移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机器人、探测机器 人、服务机器人、汽车自动驾驶系统打下基础。 根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划 基本上可分为以下几类：( 1 ) 已知环境下的对静态障碍物的路径规划；( 2 ) 未知环 境下的对静态障碍物的路径规划；( 3 ) 已知环境下对动态障碍物的路径规划：( 4 ) 未知环境下的对动态障碍物的路径规划。另外，根据路径规划解决方案的不同， 机器人路径规划又可以分为两种类型，一种是基于环境先验完全信息的全局路径 规划，另一种是基于传感器信息的局部路径规划。全局路径规划的任务是根据先 验地理环境信息找出从起始点到目标点的符合定性能的可行或最优路径。然 而，移动机器人的行为必须根据给定的任务和变化的环境实时控制。因此，首先 它要对给定的任务做出全局路径规划，并在行使过程中，通过传感系统不断感知 周围环境信息和自身状态信息，然后对这些信息进行融合处理，最后做出局部路 径规划，生成一条无障碍、可通行的路径，实现任务目标。 硕士学位论文 第一章概述 多机器人的路径规划意味着在同一工作空间中为多个机器人规划路径。其要 求规划结果能有效保证每一时刻机器人与机器人之间无碰撞，机器人与环境之间 无碰撞，即涉及机器人之间的路径协调与避碰问题。 1 1 2 协同进化计算 协同进化( c o - e v o l u t i o n ) 的概念首先来自于生物学，由埃利希和雷文 ( e h r l i c h & r a v e n ，1 9 6 4 ) 在讨论植物与植食性昆虫相互作用对进化的影响时最 早提出的。而严格的被广泛引用的协同进化的定义直至1 9 8 0 年才由扬岑给出， 即：一个物种的某一特性由于回应另一物种的某一特性而进化，而后者的该特性 也同样由于回应前者的特性而进化口 1 。协同进化的概念提出了物种之间相互作 用的思想。1 9 6 4 年关于蝴蝶与植物协同进化的研究是这一领域里的一个重要基 石。 在自然界，任何物种或个体，任何一个种群和群落都处于一定的生态系统之 中，既不存在脱离于生态系统的孤立物种和个体，种群和群落，也不存在脱离于 生物物种和特体，种群和群落的生态系统。生态系统内的生物个体，物种，种群， 群落的内部，以及它们之间，它们与环境的关系，是既有竞争，又有协同的。协 同进化算法正是源于这种思想。在遗传算法中，个体之间仅仅存在着竞争关系， 通过个体之间的竞争而淘汰差的个体，保留优秀个体，从而使得解群体不断向最 优解逼近。而在协同进化算法中，个体之间不仅存在竞争关系，同时也存在相互 合作、相互促进的关系。 协同进化算法自提出以来已经取得了一定的研究成果，但由于其研究才刚刚 开始，研究领域也不全面，因此从生物学协同理论出发，多层次多角度研究协同 进化算法尤为必要。 1 1 3 人工免疫系统 人工免疫系统是模仿自然免疫系统功能的一种智能方法，它实现一种受生物 免疫系统启发，通过学习外界物质的自然防御机理的学习技术，提供噪声忍耐、 无教师学习、自组织、记忆等进化学习机理，结合了分类器、神经网络和机器推 理等系统的一些优点，因此具有提供新颖的解决问题方法的潜力墙3 其研究成果 涉及到控制、数据处理、优化学习和故障诊断等许多领域，已经成为继神经网络、 模糊逻辑和进化计算后人工智能的又一研究热点n 1 制 生物体是一个复杂的大系统，其信息处理功能是由时间和空间尺寸相异的三 个子系统完成的，即：脑神经系统、免疫系统和内分泌系统人工智能对神经系统 2 硕士学位论文 第一章概述 的借鉴和模拟的成果很丰富，已经有比较成熟的方法和模型以资利用，相比较而 言对免疫系统和内分泌系统的相应研究还处于初级阶段计算机实现的数字化免 疫系统智能计算模型作为智能策略的研究也只是近十几年的事，是人工智能的一 个新兴研究领域。 1 2 研究现状 1 2 1 机器人导航与路径规划 路径规划技术是机器人研究领域中的一个重要分支。所谓机器人的最优路径 规划问题，就是依据某个或某些优化准则( 如工作代价最小、行走路线最短、行 走时间最短等) ，在其工作空间中找到一条从起始状态到目标状态的能避开障碍 物的最优路径。机器人路径规划方法大致可以分为两类：传统方法和智能方法。 ( 1 ) 传统路径规划方法 ( a ) 自由空间法。为了简化问题，通常采用结构空间来描述机器人及其周围 的环境。这种方法将机器人缩小成点，将其周围的障碍物及边界按比例相应地扩 大，使机器人点能够在自由空间中移动到任意一点，而不与障碍物及边界发生碰 撞。 ( b ) 图搜索法。图搜索方法中的路径图由捕捉到的存在于机器人一维网络曲 线( 称为路径图) 自由空间中的节点组成。建立起来的路径图可以看作是一系列 的标准路径。而路径的初始状态和目标状态同路径图中的点相对应，这样路径规 划问题就演变为在这些点间搜索路径的问题。通过起始点和目标点及障碍物的顶 点在内的一系列点来构造可视图。连接这些点，使某点与其周围的某可视点相连 ( 即使相连接的两点间不存在障碍物或边界) 。然后机器人沿着这些点在图中搜 索最优路径。 ( c ) 栅格解耦法。栅格解耦法是目前研究最广泛的路径规划方法。该方法将 机器人的工作空间解耦为多个简单的区域，一般称为栅格。由这些栅格构成了一 个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径，这条路径是 用栅格的序号来表示的。栅格解耦法包括确切的和不确切的两种。确切的解耦法 用来描述整个自由空间，这将使复杂环境的解耦速度变慢，其原因是许多复杂的 多边形可能需要与障碍物的边界相匹配。这种方法可以保证只要起始点到目标点 之间存在路径，就完全能搜索到这条路径。在不确切的解耦法中，所有的栅格都 是预定的形状，为了研究方便假设全部为矩形。整个图被分割成多个较大的矩形， 每个矩形之间都是连续的。如果大矩形内部包含障碍物或者边界，则又被分割成 4 个小矩形，对所有较大的栅格都进行这种划分，然后在划分的最后界限内形成 硕士学位论文第一章概述 的小栅格问重复执行程序，直到达到解的界限为止。这种解耦的结构称为“四叉 树 。四叉树法在计算机图形和机器人视觉中己得到了广泛的应用，并已在此基 础上又发展了许多的操作算法。在进行下一层更细的划分之前，应在每一层上的 起点和目标点间找到一条路径，如果该路径满足起点到目标点间无障碍物的要求 则停止搜索。 ( d ) 人工势场法。传统的人工势场法把移动机器人在环境中的运动视为一种 在抽象的人造受力场中的运动，目标点对移动机器人产生“引力，障碍物对移 动机器人产生“斥力 ，最后通过求合力来控制移动机器人的运动。 ( 2 ) 智能路径规划方法 近年来，随着遗传算法等智能方法的广泛应用，机器人路径规划方法也有了 长足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上。其中， 应用较多的算法主要有模糊方法、神经网络和遗传算法。 ( 8 ) 基于模糊逻辑的机器人路径规划。 模糊逻辑方法是在线规划中通常采用的一种规划方法，包括建模和局部规 划。庄晓东等n 卅提出一种基于模糊概念的动态环境模型，参照物体的位置和运动 信息构造二维隶属度函数；然后通过模糊综合评价对各个方向进行综合考察，得 到搜索结果。该方法在移动障碍物和移动目标的环境中能有效地实现机器人避碰 和导航。李彩虹等提出了一种在未知环境下移动机器人的模糊控制算法，并对此 算法进行了推导与仿真，证明该算法鲁棒性强，可消除传统算法中存在的对移动 机器人的定位精度敏感、对环境信息依赖性强等缺点，使移动机器人的行为表现 出很好的一致性、连续性和稳定性。 ( b ) 基于神经网络方法的机器人路径规划 禹建丽等n 6 1 提出了一种基于神经网络的机器人路径规划算法，研究了障碍物 形状和位置已知情况下的机器人路径规划算法，其能量函数的定义利用了神经网 络结构，根据路径点位于障碍物内外的不同位置选取不同的动态运动方程，规划 出的路径达到了折线形的最短无碰路径，计算简单，收敛速度快。 ( c ) 基于遗传算法的机器人路径规划 遗传算法是目前机器人路径规划研究中应用较多的一种方法，无论是单机器 人静态工作空间，还是多机器人动态工作空间，遗传算法及其派生算法都取得了 良好的路径规划结果。 综上所述，这些路径规划方法都在一定程度上解决了机器人的路径规划问 题，但是，由于各种算法自身的局限，使得路径规划问题的探讨仍具魅力，新的 算法也在不断地涌现与发展n 刀【l 8 1 。 4 硕士学位论文第一章概述 1 2 2 协同进化计算 传统的进化算法有着巨大的优越性，但同时也有一些不足的地方：首先是适 应度函数是预先定义好的，而真正的适应性是个体在环境作斗争时自然形成的以 及随着环境变化而变化的。其次进化算法只考虑了生物之间的竞争，而没有考虑 到生物之间协作的可能性，真实的情况是竞争与协作并有，这就是协同进化。 协同进化算法是近十几年来在协同进化论基础上提出的类新的进化算法， 协同进化算法与进化算法的区别在于：协同进化算法在进化算法的基础上，考 虑了种群与环境之间，种群与种群之间在进化过程中的协调。虽然在这方面的研 究起步比较晚，但由于协同进化的优越性，越来越多的学者对次进行了研究，目 前协同进化算法已经成为了当前进化计算的一个热点问题。 根据算法采用的生物模型不同，协同进化算法可以分为以下几类： ( 1 ) 基于种群之间竞争机制的协同进化算法 这类算法把种群分成几个子种群，这几个子种群处于竞争关系，但同时又存 在合作行为。种群之间通过个体的迁移来达到信息的交流。 并行遗传( 进化) 算法是一种最简单的协同进化算法，它包括三种模型：踏 脚石模型n 蚪副，粗粒度模型乜3 儿2 4 3 和细粒度模型2 5 j 。这三种模型都是通过种群之间 个体的迁移等手段达到信息交换目的，从而实现各种群的协同进化。但这种协同 进化并没有考虑到种群之间的差异，既每个种群的竞争系数都为1 ，定期或不定 期的进行信息交换。 ( 2 ) 基于捕食猎物机制的协同进化算法 捕食猎物关系是一种遭受选择压力个体问的一种反馈机制，这种反馈机制为 系统走向复杂提供了有力的驱动。猎物为了尽可能不被猎食，通过发展某些手段 更好的保护自己，但同时导致捕食者发展更好的攻击策略，这种协同进化过程导 致捕食者和猎物之间的复杂性逐步增加。 ( 3 ) 基于共生机制的协同进化算法 这类算法是把问题分解成几个子问题，每个子问题对应一个种群，并且每一 个种群用一个进化算法来进化。面对一个待求解问题，每一个进化个体只对应问 题的部分解，由不同种群个体构成的一个共生体对应问题的一个完整解。不同算 法的区别在于个体适应度计算方法不同。 1 2 3 人工免疫系统 随着对免疫系统研究的深入，在基于免疫系统的诸多特性上，发展起来了许 多的免疫算法，主要包括：根据免疫系统的自己非己的区别原则的否定选择算 硕士学位论文 第一章概述 法嘶1 、基于免疫系统的局部记忆学说和免疫网络学说的免疫a g e n t 算法啪鹪1 、 引入疫苗接种理论的免疫优化算法乜引、引入自我调节机制的免疫算法、基于免 疫应答的免疫优化算法b 1 j 、基于免疫抗体记忆的免疫算法口2 l 、借鉴生物独特性网 络调节的进化算法口3 ，3 4 l 、具有免疫体亲近性特征的遗传算法m 1 等。这些改进算法 可以快速求出满足一定精确度要求的最优解，对解决工程应用问题具有用价值。 同时也出现了与其它智能策略相结合的混合免疫方法，如：k r i s h n a k u m a r 等 将神经网络和免疫系统机理结合提出了“免疫神经控制( i n c ) 的结构m 1 ；s a s a k i 等提出了一种基于免疫系统反馈机理的自适应学习的神经网络控制器口7 l ；李亭鹤 等针对凹形重叠区难以精确寻点的问题，提出了一种新的洞点搜索方法m 1 ：感染 免疫法，实际应用表明，该方法无论是寻点能力还是在通用性方面都优于传统模 式。 在人工免疫系统的理论研究方面。如借助数学、非线性、复杂、混沌、智能 主体等理论研究人工免疫系统的机制、免疫计算原理等。这方面的研究成果还非 常少。虽然人工免疫系统已经被广大研究者逐渐重视，然而与已经有比较成熟的 方法和模型以资利用的人工神经网络研究相比，不论是对免疫机理的认识，或是 免疫算法的构造，还是工程应用，人工免疫系统相应的研究都处在一个相对不高 的水平。 基于克隆选择原理的克隆算法。代表性的算法是c a s t r o 等的克隆选择算法 ( c s a ) 儿删以及k i m n n 2 1 等在h o f m e y r 的基础上提出了一种动态克隆选择算法， 并用于解决连续变化环境中异常探测的问题等等。 1 3 主要研究内容与章节安排 1 3 1 主要研究内容 论文主要针对移动机器人路径规划及其相关关键技术展开了研究。在单机器 人路径规划方面，论文主要探讨了免疫进化算法，详细阐述了该算法的流程以及 相关算子和参数，并根据单机器人路径规划的特点，结合改进后的免疫进化算法 提出一种基于免疫进化的单机器人路径规划。并根据仿真实验验证了该方法的有 效性和优越性。在多机器人路径规划方面，论文进一步探讨了协同进化模型，并 结合该模型和免疫进化方法提出一种基于协同免疫进化的多机器人路径规划。并 根据仿真实验和机器人相关实验验证该方法的有效性。 6 硕士学位论文第一章概述 1 3 2 章节安排 第一章为概述，主要介绍了论文课题的研究背景与研究现状以及章节安排； 第二章主要介绍了免疫克隆算法的基本流程和相关知识，为基于免疫进化的路径 规划算法提供相关理论知识；第三章主要介绍了基于免疫进化的单机器人路径规 划，内容包括了基于免疫进化的路径规划算法和相关的仿真实验；第四章主要介 绍了协同进化算法的模型，为基于协同进化的多机器人路径规划提供框架模型； 第五章主要介绍了基于协同免疫进化的多机器人路径规划，内容包括了其算法的 介绍和其相关实验等。第六章为总结与展望，对本论文的研究内容和创新点进行 了总结，分析了论文中的缺陷和不足，最后对今后的研究发展方向进行了展望。 7 硕士学位论文 第二章免疫克隆算法 第二章免疫克隆算法 实参数的函数优化问题在工程实际中有重大的意义，很多时候人们都需要对 某些实数向量进行优化，解决这类问题的方法很多，包括传统的基于梯度的算法， 以及一些迭代算法。而对于高维、非凸、且有多个局部极值点的函数优化问题， 其理想解往往很难获得。免疫系统作为一种分布式自学习系统，能自适应地维持 群体多样性及具有自我调节功能，导致基于免疫机制的算法具有整体、局部搜索 能力强的特点，使得这类算法在函数优化、组合优化、模式识别、数据挖掘及机 器学习等方面得到了有效应用。 基于免疫学原理而发展的新兴智能一人工免疫系统已经用于处理计算机安 全等多种工程和科学问题h3 i 。克隆选择算法h 钔( c l o n a ls e l e c t i o na l g o r i t h m ) 是由 d ec a s t r o 和v o nz u b e n 在2 0 0 0 年提出的一种算法，其灵感来自生物获得性免疫的 克隆选择原理h5 l 。在生物免疫系统中，一旦病原体侵入肌体就被分解为抗原片段， b 淋巴细胞能够为产生相应的抗体与抗原结合，同时活化、增殖和分化，产生浆 细胞，通过中和、溶解和调理等作用，最终使抗原从体内清除。另有一些b 细 胞变成了长期存活的记忆细胞，它通过血液、淋巴和组织液循环，为下一次快速、 高效的消除相同或者类似抗原引起的感染奠定了基础。 2 1 免疫克隆算法 2 1 1 免疫克隆算法步骤 克隆选择算法模拟生物免疫系统的克隆选择原理，一般将待优化的目标函数 及其约束条件视为抗原，其算法步骤如下： ( 1 ) 初始化：随机产生n 个抗体对应问题的可能解。 ( 2 ) 评价和选择1 ：将n 个抗体分解成由m 和r 个抗体组成的两部分a m ，a r ， 分别表示进入记忆集的抗体和剩下的部分，其中进入记忆集的都是适应度较高的 抗体。 ( 3 ) 克隆：在适应度最高的抗体中选择k 个进行克隆，一般来说克隆的数量 与其适应度成正比。 ( 4 ) 变异：模拟生物克隆选择中的变异过程，对克隆后的抗体执行变异操作， 变异按某一变异概率以一定规模随机进行。 ( 5 ) 评价和选择2 ：重新计算变异后的抗体的适应度，若克隆变异后的抗体 8 硕士学位论文第二章免疫克隆算法 中适应度最高的抗体比原抗体的适应度还要高，就用该抗体替换原抗体，形成新 的记忆集。 消亡：模拟生物克隆选择中一定比例的b 细胞自然消亡的过程，在a r 中选择d 个适应度最低的抗体重新初始化，以保证抗体的多样性。 ( 6 ) 检查是否满足终止条件，若是，终止，否则转到2 ，进入下一次迭代。 第k 代抗体群 上 适应度评价1 上，上 i 记忆集保留集淘汰集 l 上上 i免疫克隆消亡 l 上 l 变异算子 上 i 评价选择2随机抗体集 1 第k + l 代抗体群 图2 1免疫克隆算法框架 ( 1 ) 编码 用n 个具有任意基因片段的个体抗体组成种群，其中最主要的是对参数的 编码。编码就是将问题的解用一种码来表示，从而将问题的状态空间与算法的码 空间相对应，这很大程度上依赖于问题的性质，并将影响其他操作的设计。由于 算法的优化过程不是直接作用在问题参数本身，而是在一定的编码机制对应的码 空间上进行的，因此编码的选择是影响算法性能与效率的重要因素。 ( 2 ) 适应度 在免疫克隆算法中适应度是用来描述抗体与抗体之间的匹配程度。对环境中 适应度程度高的抗体获得更多的机会保留下来，而适应度低的抗体，其保存下来 9 硕士学位论文 第二章免疫克隆算法 的机会就会相对较少，甚至逐渐灭绝。适应度是抗体的一个最基本的特征信息， 为算法的各种算子以及算子的优化提供了基础。 ( 3 ) 适应度函数 适应度函数用于对个体抗体进行评价，也就是优化过程发展的依据，对算法 的性能有一定的影响。在简单问题的函数优化时，通常可以直接利用目标函数变 换成适应度函数；在复杂问题的函数优化和复杂的实际应用问题时，往往需要构 造合适的评价函数，使其适应算法进行优化。 2 1 2 算子定义 ( 1 ) 克隆算子 克隆是将抗体复制一定的数量，以扩大搜索空问。一般来说，抗体克隆的数 量与其适应度成正比，适应度越高，克隆的数量越多。 ( 2 ) 变异算子 变异就是随机地改变群体中个体的某些基因座上的值，它通常以很 小的概率p m ( 即变异概率) 发生。 变异操作本身是一种局部随机搜索，与选择算子结合在一起，就能避免由于 选择算子而引起的某些信息的永久性丢失，保证了算法的有效性，使算法具有局 部的随机搜索能力，同时使得遗传算法保持群体的多样性，以防止出现未成熟收 敛。 ( 3 ) 选择算子 选择也称为再生算子( r e p r o d u c t i o n ) ，是指从群体中选择优良的个体， 并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体，被 选择的可能性就越大，它的“子孙 在下一代的个数就越多在免疫选择中，选择 算子实际是将适应度更高的抗体选入记忆集，代替a m 中适应度较低的抗体。 目前常用的选择方法有：赌轮方法( r o u l e t t ew h e e lm o d e l ) 、也称适应 度比例法( f i t n e s sp r o p o r t i o n a lm o d e l ) ，最佳个体保留方法( e l i t i s tm o d e l ) ， 期望值方法( e x p e c t e dv a l u em o d e l ) ，排序选择方法( r a n k - b a s e dm o d e l ) ，联 赛选择方法( t o u r n a m e n ts e l e c t i o n ) 等 ( 4 ) 消亡算子 消亡算子将抗体重新初始化为定义域中的值。在抗体的记忆集之外取得d 个 适应度最低的抗体运用消亡算子予以抛弃，将其重新初始化，可保持种群的多样 性。 1 0 硕+ 学位论文第二章免疫克隆算法 ( 5 ) 多样性 进化计算经过多年的研究和应用实践，人们发现进化计算的性能与一个称之 为多样度的指标紧密相关。进化计算的一个最大问题是可能出现早熟收敛，出现 早熟收敛的一个特征是往往多样性很低。如果多样性足够大，就可以避免早熟收 敛现象，但多样性太大，个体太分散，进化计算的开采能力会下降，可能导致收 敛速度慢。因此，需要合理地使用多样性来达到避免早熟收敛和收敛速度之间的 平衡。通常进化过程中多样度的选择可以采用原则进化初期多样度高，进化后期 多样度低，进化中期的多样度以从高到低的趋势而动态变化。 2 1 3 相关优化 通常认为影响进化计算性能( 其中包括能否克服早熟，是否有快速收敛能力 和最终解的质量等) 的主要参数是选择压力和变异概率，以及在生成子代时的概 率分布。 ( 1 ) 变异概率 适应度是衡量一个抗体当前对抗原的匹配程度，一般来说，其设置变异操作 概率的共同思想为对适应度小的个体，加快其更新速度，采用较大的变异操作力 度，对适应度大的个体，由于是较优个体，要保证不易丢失，宜选用较小的操作 概率。 多样度主要用于克服早熟收敛，当多样度非常小时，说明种群目前开采的范 围较窄，可能会陷入局部极值，需要增加具有全局搜索能力的变异操作力度，扩 大开采范围相反，当多样度很大时，说明种群目前开采的范围很大，种群中的个 体过于分散，可能会使进化收敛速度缓慢，需要减少变异的力度，缩小开采范围。 因此通过多样度调整变异概率，有可能提高进化计算的进化能力。 由于多样度和适应度都是度量进化计算能力的指标，其作用各有特色，如何 根据多样度和适应度来引导变异算子概率，直接影响到算法的各项性能。 ( 2 ) 选择压力 文献【4 6 】研究发现，在并行进化计算中选择压力的性能对算法的性能影响很 大，有时甚至其性能取决于选择压力的大小。m i c h a l e w i c z 提出了一种基于概率 的选择方法h 7 1 ，文献 4 8 1 通过概率分布方法研究了选择操作中被选择个体的期望 值问题，文献【4 9 】分析了几种基本选择操作方法的性能，并指出进化前期宜使用 较小的选择压力，进化后期使用较大的选择压力。 进化计算的性能与选择压力有紧密的联系，一般来说，选择压力太大，可能 导致早熟收敛，选择压力太小，就严重影响收敛速度，这是大家的共识。不同的 问题在进化的不同阶段需要不同的选择压力，当选择压力在某个范围内变化时， 硕士学位论文第二章免疫克隆算法 不显著影响进化计算的性能，也就是说选择压力有一定的鲁棒性。然而针对具体 的问题，选择压力的鲁棒性变化范围是不相同的。 总的来说，选择压力是影响进化计算性能其中包括能否克服早熟和是否有快 速收敛能力的主要参数之一，同时多样度与选择压力是负相关的，换言之，选择 压力增大，则多样度减小，并且选择压力影响收敛速度和解的质量。 所以根据选择压力的关系，如何根据适应度和多样度的信息引导的免疫选择 算子对算法是极其重要的。 ( 3 ) 采样函数 进化算法等智能优化算法的一个关键环节是生成子代时概率分布的选择。好 的采样能引导进化的方向，同收敛性能和解的质量都有紧密关系。目前可把采样 函数归纳为下面几种。 ( a ) 均匀采样 均匀分布采样是均匀采样方式，其优点是对搜索空间采样均匀，缺点是没有 采样的方向性和着重点搜索区域，常用于种群初始化和二进制遗传算法中。 ( b ) 父体为着重点搜索区域的采样 柯西分布采样、高斯分布采样、非均匀变异一和双指数变异方法都是属于第 种范式。 ( c ) 边界点为中心的着重点搜索区域采样 边界变异所使用的分布属于这种采样范式。这种采样范式对有些问题，比如 解位于边界上或者边界附近的问题，是非常有用的。混沌采样方式也可以按所使 用的混沌模型将其归入这类中。 ( d ) 父体两旁为中心的着重点搜索区域采样。 逆正态分布采样方法属于这类采样范式。其逆正态分布能够增加局部极值点 逃逸能力，但也有其不足的地方，如在进化后期，由于局部搜索能力很弱，会减 慢收敛速度，并影响解的精度。 采样函数同算法的性能有着紧密的联系。根据具体问题，采用合适的采样分 布函数引导各进化算子产生新的子代，能有效的提高算法的各种性能。 2 2 仿真实验 采用基于高斯采样函数的变异算子，变异算子作用到的个体分量为 x 。= x ；+ n m ；半n ( 0 ，1 ) 。其中n ( 0 ，1 ) 是一个服从标准正态分布的随机数；而n m ；则对 应抗体的变异率，其中的n m ；计算公式为： n m f p 丛兰1 2 ( 2 一i ) 。m a x ( f ( x o ) 1 2 硕+ 学位论文 第二章免疫克隆算法 即抗体的变异率是与其适应度成反比的，适应度越高变异率越小，抗体在每 次迭代过程中根据适应度自适应的调整变异步长，使得在适应度高的抗体周围集 中搜索以提高收敛速度，同时保持种群的多样性。p 为变异常数，用来调整变异 强度。用来调整变异强度，与搜索的空间大小和种群规模相关，这里取 ( 2 2 ) 同时算法的选择方法采用最佳个体保留方法。即实际是将适应度更高的抗体 选入记忆集，代替a m 中适应度较低的抗体。 为测试算法性能采用了以下3 个典型测试函数： f l ( x ) ：兰( x i 2 一i oc o s ( 2 z x i ) + i o ) 一5 1 2 册5 1 2( 2 - 3 ) i = i 刀疗 一 f 2 ( x ) = 石；4 0 0 0 一兀c o s ( x ，4 0 + 1 6 0 册6 0 0 ( 2 - 4 ) f 3 ( x ) = 兰( 1 0 0 ( z ，+ 1 一工孑) 2 + ( 1 - x i ) 2 ) 一3 0 n 3 0 ( 2 5 ) l = l 是r a s t r i g r i n 函数，多峰，在厮= 0 ( 卢1 ，2 ，n ) 时达到全局极小 点，在( - 5 1 2 ，5 1 2 ) 范围内约存在1 0 n 个局部极小点。 是g r i e w a n k 提出的，全局极小在x i = 0 ( i = l ，2 ，n ) 时达到，局部 极小值在置七刀f ( i = l ，2 ，n ；k = o ，l ，2 ，n ) 时达到。 厶是r o s e n b r o c k 函数，非凸、病态函数，在西= l 时达到极小值点。 初始种群大小为1 0 0 ，维数为2 0 ，最大截止代数为4 0 0 的情况下，优化后的 克隆选择算法连续l o 次实验的结果与原克隆选择算法( 采用均匀采样和无自适 应变异和选择算子) 比较见表2 1 。 表2 1 实验结果 硕士学位论文 第二章免疫克隆算法 实验结果表明，优化后算法在三个函数上均优于原克隆选择算法，收敛速度 和精度都有明显提高。 2 3 本章小结 本章主要为下章基于免疫进化的单机器人路径规划介绍了其理论基础。对于 免疫克隆选择算法本章主要做了如下几个方面的工作： ( 1 ) 介绍了免疫克隆选择算法的算法流程以及对其算子进行了介绍。 ( 2 ) 分析了选择压力和变异概率，以及在生成子代时的概率分布等几项与免 疫克隆选择算法各性能的关系。并利用函数优化的仿真实验来说明了有效的利用 其关系能有效的提高算法的性能。 1 4 硕士学位论文第三章基于免疫进化的单机器人路径规划 第三章基于免疫进化的单机器人路径规划 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从 给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有 的障碍物。障碍环境中机器人的无碰撞路径规划是智能机器人研究的重要课题之 一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好 地解决。 本章结合了免疫进化算法提出了一种基于免疫进化的移动机器人路径规划 方法。 3 1 基于免疫进化的移动机器人路径规划 基于免疫进化的路径规划算法中，将待求的最终优化规划路径结果视为抗 原，进化过程实质上就是一个抗体匹配抗原的过程。 3 1 1 算法步骤 基于免疫进化的路径规划算法可以描述为下面的过程： ( 1 ) 初始化规模为n 的抗体群a ； ( 2 ) 对群体中的所有抗体进行适应度评价； ( 3 ) 如果群体中的最优个体满足条件就输出结果，否则进入s t e p 4 ； ( 4 ) 基于适应度，选择最佳的m 个抗体的记忆集a m ，其余的适应度低的进入 规模为r 的集合办； ( 5 ) 对记忆集a m 里的每个抗体进行免疫克隆操作，对每个抗体克隆的结果组 成一个集合乃，克隆个体的规模拧同父体的适应度成正比； ( 6 ) 由变异算子对集合7 7 里的每个新抗体进行混合变异操作，得到玎，变异 的幅度根据混合变异的概率函数确定； ( 7 ) 对变异后集合盯中的抗体以一定概率进行疫苗接种；得到集合”； ( 8 ) 对集合玎中的抗体重新进行适应度评价，根据退火选择将集合玎中选择 合适抗体代替父体进入集合a 历或保留父体； ( 9 ) 将抗体集合彳，淘汰部分适应度低的抗体，补充加入同数量随机产生的新 抗体，保持多样性； ( 1 0 ) 更新抗体总集合a ：a 研+ a ，- ，返回( 3 ) 。 硕士学位论文 第三章基丁免疫进化的单机器人路径规划 3 1 2 路径编码 图3 - 1免疫进化路径规划流程图 一条路径是从起始位置到终止位置、由若干线段组成的折线，线段的端点叫 节点，用平面坐标( x ，y ) 表示，一条路径上的节点个数是变化的，绕过了障碍 物的路径为可行路径。一条路径对应种群中的一个抗体，用路径上的节点坐标( x ， y ) 表示。抗体p 可表示如下： x = ( 而，y 0 ，( x 2 ，耽) ( 而，) ， ( 3 1 ) 其中( x l ，y 1 ) 和( x 。，y 。) 是固定的，分别表示起始位置和终止位置。 抗体按随机方式产生，预先给定抗体的最大长度n ，随机产生区间 2 , n 】内 的一个整数n 作为抗体p 的长度，再按随机方式产生n 2 个坐标点( x 2 ，y 2 ) ，( x n 1 ， y n 1 ) 。 1 6 硕士学位论文 第三章基于免疫进化的单机器人路径规划 3 1 3 适应度函数 免疫进化算法中的操作是基于适应度函数来进行路径抗体群更新的，所以适 应度函数的选取有着重要的地位，它会直接影响的到算法收敛速度以及最终的路 径规划结果，同时适应度的选择还应该同具体的实际问题相结合。 根据机器人路径规划的要求，有多种因素来评价一条路径规划结果。比较重 要的有下面几个方面：路径的环境下路径总长度短，路径的路径平滑度，以及因 为路径和障碍相交，要求机器人时实时避障的次数等等，所以适应度函数主要从 上述三个方面考虑。 ( 1 )