（控制理论与控制工程专业论文）焊接机器人路径规划问题的算法研究.pdf

武汉科技大学 研究生学位论文创新性声明 l l l l l l ll l l l l l l l l l ul ll ll ti i i i i i 、t17 3 9 6 5 6 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：丝丝 日期：竺鱼! 圣 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名：么幺 指导教师签名：叠塑生 日 骞 警 武汉科技大学硕士学位论文第1 页 摘要 本文讨论了目前在焊接机器人路径规划领域广泛使用的智能算法：遗传算法和 h o p f i e l d 神经网络。针对这些算法处理路径优化问题时的不足，提出了基于d n a 计算处理 焊接机器人路径规划问题的算法。基于焊接机器人路径规划问题的数学模型，将焊接机器 人路径规划问题转化为完全正权无向图的最短h 锄i l t o n 环路问题；结合焊接机器人工作的 实际情况，运用d n a 算法获得最短h m i l t o n 环路路程，从而实现焊接机器人的工具原点运 动的最优化；最后通过算例证明了方法的有效性。针对已有的d n a 计算模型的缺点，采取 了相应的改进，把包含重复顶点的闭链剔除出去，满足了实际规划问题中不重复焊接同一 焊点的要求。 本文还讨论了聊蛆计算实现实际工作中焊接机器人路径规划时出现的几个问题，并提 出了作者的一些想法，为以后研究这些问题指出了努力的方向。 关键词：焊接机器人；路径规划；d n a 计算；t s p 问题 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t d i s c u s s i o no ft h ec u r r e n tf i e l do fw e l d i n gp a t hw i d e s p r e a du s eo fi n t e l l i g e n ta l g o r i t h m s ： g e n e t i ca l g o r i t h m sa n dh o p f i e l dn e u r a ln e t w o r k s t h e s ea l g o r i t h m sa d d r e s st h el a c ko fp a t h o p t i m i z a t i o np r o b l e m si sp r o p o s e dw d d m gr o b o tp a t hp l a n n i n ga l g o r i t h m sb a s e do nd n a c o m p u t i n g b a s e do nt h em a t h e m a t i c a lm o d e l ，t h ew e l d i n gr o b o tp a t hp l a n n i n gp r o b l e mi s t r a n s f o r m e di n t ot h es h o r t e s tc o m p l e t e l yw e i g h t e du n d i r e c t e dg r a p ho fh a m i l t o nl o o pp r o b l e m ； c o m b i n a t i o no ft h ea c t u a ls i t u a t i o no ft h er o b o t ，t h eu s eo fd n am e t h o dw a st h es h o r t e s t h a m i l t o nc i r c l ed i s t a n c et ot h eo r i g i no fw e l d i n gr o b o t - m o v e m e n to p t i m i z a t i o nt o o l ；f i n a l l y , a n u m e r i c a le x a m p l ed e m o n s t r a t e st h ee f f e c t i v e n e s so ft h em e t h o d d n ac o m p u t i n gm o d e lf o rt h e e x i s t i n gs h o r t c o m i n g s ，t a k e ac o r r e s p o n d i n gi m p r o v e m e n t , t oi n c l u d er e m o v i n gd u p l i c a t e v e r t i c e so fc l o s e d c h a i no u tt om e e tt h ea c t u a lp l a n n i n gp r o b l e m sd on o tr e p e a tt h es a m es o l d e r w e l d i n gr e q u i r e m e n t s t h i sa r t i c l ea l s od i s c u s s e st h ep r a c t i c a lw o r ko fd n ac o m p u t i n gf o rw e l d i n gr o b o tp a t h p l a n n i n g , s e v e r a li s s u e se m e r g e da n dm a d eo fs o m eo ft h ei d e a sf o rt h ef u t u r es t u d yo ft h e s e i s s u e st h a td i r e c t i o n k e y w o r d s ：k e yw o r d s ：w e l d i n gr o b o t s ；r o u t e sp l a n n i n g ；d n ac o m p u t i n g ；t s pp r o b l e m 武汉科技大学硕士学位论文第l i i 页 目录 摘要i a b ；i 【。a ：i i 第一章绪论l 1 1 机器人应用情况。l 1 1 1 机器人的定义l 1 1 2 机器人的应用1 1 1 3 焊接机器人的应用3 1 1 4 焊接机器人路径规划问题。3 1 2 现代路径规划算法。4 1 2 1 遗传算法4 1 2 2h o p f i e l d 神经网络算法4 1 2 3d n aj 汁算5 第二章智能优化方法6 2 1 遗传算法6 2 1 1 遗传算法的理论基础6 2 1 2 遗传算法的生物原理6 2 1 3 遗传算法的基本操作8 2 1 4 遗传算法的优化结果。1 0 2 2 神经网络优化方法13 2 2 1 神经网络理论基础1 3 2 2 2 离散时间的二元神经元网络1 5 2 2 3 连续时间的梯度神经元网络1 5 2 2 4 连续型h o p f i d d 网络在路径规划中应用16 2 2 5 优化结果18 第三章d n a 计算的优化方法21 3 1d n a 计算基本理论2l 3 1 1d n a 计算的原理2 2 3 1 2d n a 分子的结构j 一2 2 3 1 3d n a 分子的基本生物操作2 3 3 2d n a 计算应用领域2 9 3 2 1 双链d n a 计算模型3 0 3 2 2 单链d n a 计算模型3 0 3 2 3 质粒d n a 计算模型3 0 3 2 4 表面d n a 计算模型3l 第页武汉科技大学硕士学位论文 3 2 5 粘贴d n a 计算模型3l 3 2 6 剪接d n a 计算模型3 l 3 2 7 三维d n a 计算模型3 l 第四章基于d n a 算法的焊接机器人路径规划3 3 4 1 背景3 3 4 2 焊接机器人路径规划的数学模型3 6 4 3d n a 计算算法的实现3 6 4 4 算例3 7 4 4 1 算例一3 7 4 4 2 算例二4 l 4 5 结论4 5 第五章总结4 6 5 1 总结4 6 5 2 进一步研究的方向4 6 5 3 经验和体会4 6 参考文献。4 8 致谢! ；：； 附录( 攻读硕士学位期间发表的论文) 5 4 武汉科技大学硕士学位论文第1 页 第一章绪论 1 1 机器人应用情况 1 1 1 机器人的定义 机器人指的是一种自主引导，能够自己完成赋予任务的机器。机器人另一个基本的特 性就是可以通过行动反应其拥有的意愿和意图。在二十一世纪的今天，机器人被应用在社 会生活的方方面面，这一局面是人类创造机器人之初未曾预想到的。 在机器人科学和机器人的发展过程中，各种科技不断涌现。其中一种技术是进化机 器人技术( 一系列不同功能的机器人接受测试，表现最好的作为制造下一代机器人的模 型) ，另一种技术是发展机器人技术( 跟踪在某一领域内用于解决问题的功能变化与发展) 。 目前，机器人大部分被设置在工厂或者家庭，从事体力劳动。与此同时，在世界范围 内，在实验室里制造出各种性能更出色的机器人。大量机器人技术的研究不仅着眼于执行 特殊的工业任务，而且还专注于研究、设计、制造新式的机器人和新式的机器人制造方法。 当那些新式机器人成为现实，可以期待它们能处理现实世界的一系列问题。 1 1 2 机器人的应用 机器人大量参与对于人类来说危险、繁重、环境恶劣和难以完成的工作，在制造业、 建筑业、石油钻探、矿石开采、太空探索、水下探索、毒害物质清理、搜救、医学、军事 等领域辅助或替代人类的劳动。由图1 1 1 3 可见，介绍了几种典型的机器人。 图1 1 腹腔镜手术机器人 如果将机器人从事的领域进行一个粗略的分类，那么主要分为服务机器人和工业机器 第2 页武汉科技大学硕士学位论文 人两类。截止到2 0 0 8 年，世界上有大约7 0 0 万个服务机器人和10 0 万个工业机器人在使 用。 工业机器人的正式定义是可自动控制、可重复编程、可完成多种目标任务和具备三个 以上轴的机械手，主要用于产品的生产和分发。工业机器人的典型应用包括焊接、着色、 装配、挖掘、包装、装运、成品检验和测试。 图1 2 军用遥控排爆机器人 具体地说，在包装业中，广泛地使用工业机器人包装和码放生产出的产品，比如快速 的将传送带上的饮料盒放进箱子晕。 图1 3 德国食品工业中的机器人在码放面包和吐司 在电子业中，取放机器人专门用于生产大量的印刷电路板，它能从盘子里取出很小的 武汉科技大学硕士学位论文第3 页 电子组件精确地放置在电路板上，一小时可以安装数十万个组件，在速度、精度和可靠性 上远超人力的水平。 在汽车制造业中，机器人在汽车厂里占主导地位超过三十年。在一个典型的汽车制造 厂里，全自动生产线上包含一百多个机器人，一个机器人相当于十个工人。在一个自动生 产线上，一个在传送带上的汽车底盘由按序排列的机器人站完成焊接、胶合、上漆和最后 的组装。 总之，机器人可以以高强度、高速度和高精度来完成各种不同的任务。 1 1 3 焊接机器人的应用 机器人焊接就是使用机器人在抓握加工件的同时对工件进行焊接，从而自动完成焊接 作业。类似气体保护金属极电弧焊这样的作业尽管常常是自动完成的，但是仍然需要操作 员为其准备材料，而不能被称为机器人焊接。机器人焊接通常应用于如汽车制造业这种要 求高级加工的焊接作业中。 机器人焊接作为机器人技术的应用，直到十九世纪六十年代才被第一次引入到美国的 工厂。机器人在焊接方面使用的突破是上世纪八十年代的事。那时自动化的工厂开始广泛 使用机器人进行点焊作业。从那以后，工厂罩运行的机器人的数量增长迅猛。截止2 0 0 5 年，超过1 2 0 0 0 0 台机器人在北美工厂里运行，其中大约有一半的机器人从事焊接作业。 阻碍机器人增长的主要原因是机器人高昂的成本和应用方向的不确定。 机器人弧焊是最近才开始快速增长的，目前占工业机器人总量的2 0 。焊接机器人主 要的部件是机械臂和作为机器人“大脑”的控制单元。能使机器人运动的机械手臂根据其设 计可以分为几种普通的类型，如水平的多关节机械手臂和直角坐标机器人( 使用并行且不 同的系统指挥手臂上的机械) 。 i i a 焊接机器人路径规划问题 车身制造是点焊机器人的一个典型的应用领域。在规划车身焊接生产线时，一般布置 多个机器人工位，完成超过6 0 的焊点。在德国大众推出的m u l t i v 雏t 5 车型的焊接生产 线上，7 6 的工作由7 5 0 台机器人完成，代替了1 4 3 0 个工人的工作量。在5 3 2 7 个焊点中， 4 6 7 4 个焊点由点焊机器人完成。 在国内，点焊机器人主要用于车身焊接的侧围、车身总成合焊等工位。点焊机器人的 广泛使用，实现了车身焊接的柔性化生产方式多品种的混线生产。在大批量生产中使 用机器人来替代工人，可以降低劳动强度和制造成本，提高制造质量。因此，点焊机器人 工位是车身焊接生产线上重要的组成部分。点焊机器人工位的规划是规划的重点之一，而 在点焊机器人工位规划中，焊接路径规划又是工位规划的重点之一。 第4 页武汉科技大学硕士学位论文 点焊机器人的运动可以分为两个部分：1 从作业原点移动到焊点( 或者从焊点返回到 作业原点) 。2 从一个焊点移动到另一个焊点。从机器人的作业原点( 也叫待机位姿) 到焊 点进行的是p t p ( p o i n tt op o i n t ，点到点) 运动，机器人在焊点与焊点之间的运动形式也是 p t p 。p t p 运动指的是只考虑起始点和目标点，而不考虑两点之间的具体轨迹。 对机器人焊接路径进行合理的规划，可以减少机器人工位的生产时间，大大的缩短整 体工时，提高生产效率，降低生产成本；又由于点焊机器人的路径规划具有典型性，研究 成果不仅适用于焊接机器人的路径规划，同样适用于汽车自动驾驶、挖掘机器人、服务机 器人以及仓库叉车的路径规划问题。因此本文的研究具有一定的社会效益和经济效益。 路径规划问题是机器入学中很重要的一个方面，大多数国内外文献将此问题称为p a t h p l a n n i n g , f i n d d p a t hp r o b l e m ，c o l l i s i o n - - f r e e ，o b s t a c l ea v o i d a n c e ，m o t i o np l a n n i n g ，e t c 就 最简单的形式，路径规划问题可以按如下定义：机器人路径规划是指在其工作空间中，为 机器人完成某一给定任务提供一条安全、高效的运动路径。一般来说，机器人完成给定任 务可选择的路径有多条。实际应用中往往要选择一条在一定准则下为最优( 或近似最优) 的 路径。常用的准则有：路径最短、消耗能量最少或使用时间最短等。因此，机器人路径规 划实质上是一个有约束的优化问题。 1 2 现代路径规划算法 为了解决路径规划问题，路径规划问题领域的专家们已探索出很多有效的求解方法。 这些方法大致可以分为两大类：传统方法和智能方法。传统方法包括拓扑法、几何法、栅 隔解耦法、单元分解法、人工势场法和数学分析法等方法。路径规划领域中的很多问题都 可以用这些方法来解决。它们也不是互相排斥的，而常常结合起来共同地实现路径规划。 随着路径规划问题的越来越复杂，新的智能方法也被引入到路径规划问题当中来，并且越 来越受到路径规划专家们的重视，例如禁忌搜索，免疫算法，模拟退火，神经网络掣。 1 2 1 遗传算法 遗传算法是目前机器人路径规划研究中应用较多的一种方法。它是模拟生物进化过程 的计算模型。作为一种全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理以及 应用范围广等显著特点，越来越多的受到人工智能领域学者们的关注。 根据路径规划问题的目的只是求最短路径，传统解法( 如贪心法) 非常在意得到路 径的过程，而遗传算法则直接将目标指向距离最短( 因是n p 完全问题，只能是距离满意) ， 能较快地得到问题的解答。 1 2 2h o p f i e l d 神经网络算法 h o p f i e l d 神经网络是一种非线性动力学模型，它引入类似于l y a p u n o v 函数的能量函数 武汉科技大学硕士学位论文第5 页 概念，把神经网的拓扑结构( 用连接权矩阵表示) 与所求问题( 用目标函数描述) 相对应，并将 其转换为神经网动力学系统的演化问题。 应用h o p f i d d 神经网络的能量函数，把机器人路径规划问题的目标函数转换成网络的 能量函数，把问题的变量对应于网路的状态，解决机器人工作空间各点之间路径规划的问 题，使总行程达到最短。 1 2 3d n a 计算 d n a 计算作为一种全新的计算模式，以其海量的存储量和运算的并行性弥补了传统计 算机电子计算机的致命缺陷，使得d n a 计算有望解决当今在电子计算机上许多无法解决 的问题，如n p 完全问题。因此，d n a 计算深深地吸引了不同学科、不同领域的众多的科 学家的注意力。 d n a 计算是一种运用d n a 、生物化学和分子生物学技术的计算形式。，d n a 计算有时 也称作分子计算，是一个快速发展的跨学科领域。这方面的研究与发展关注d n a 的理论、 试验和应用。通过对d n a 分子进行合理的编码，并通过设计可控的生化实验次序来完成各 种实际问题的求解。比如文献 2 】对路径规划问题给出了d n a 算法及其生化实现的过程，可 以较快地产生路径规划问题的全部精确最优解的集合等。 第6 页武汉科技大学硕士学位论文 第二章智能优化方法 2 1 遗传算法 2 1 1 遗传算法的理论基础 早在1 9 5 4 年，n i l sa a l lb a r r i c e l l i 在普林斯顿大学先进科学学院就开始了用计算机模拟 生物进化的工作。不过他在1 9 5 4 发表的论著尚未被广泛的关注【3 1 。量子遗传学家a l e xf r a s e r 发表了一系列关于利用模拟生物体人工选择解决多位点控制一个可测特性的论文。从那以 后，在二十世纪六十年代初期生物学家利用计算机模拟生物进化变得越来越普遍。f r a s e r 的模拟方法包含了现代遗传算法所有的基本要素。此外，h a n sb r e m e r m a n n 在同时期出版 的论文中采用解空间处理优化问题，其中同样也包含了重组、变异和选择等现代遗传算法 的基本要素。其它值得注目的先驱还有r i c h a r df r i e d b e r g 、g e o r g ef r i e d m a n 和m i c h a e l c o n r a d 。 虽然b a r r i c e l l i 已在1 9 6 3 年发表的论文中证明模拟生物进化具备解决简单问题的能力， 然亓i i n g or e c h e n b e r g 和h a n s p a u ls c h w e f e l 在二十世纪六十年代的工作、r e c h e n b e r g 集团在 二十世纪七十年代早期使用进化战略解决复杂的工程问题才使人工进化成为广泛承认的 优化方法。另一个应用是l a w r e n c ej f o g e l 的进化编程技术产生人工智能。进化编程最 先是用有限状态机预测环境和用变异及选择优化预测的逻辑性。特别是通过j o h nh o l l a n d 在二十世纪七十年代早期的工作，尤其是他在1 9 7 5 年出版的著作( a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s ) ) 使得遗传算法变得普及。h o l l a n d 在这方面的研究始于他和学生在密歇根 大学主持的有关细胞自动机的研究工作。h o l l a n d 弓l 入一种规范化的结构来预测细胞下一代 的质量，称作h o l l a n d 模式定理。当第一届国际遗传算法大会在宾西法尼亚州的匹兹堡召开 时，在遗传算法领域的研究还处于大量理论研究阶段，直n - 十世纪八十年代中叶。 随着理论研究的深入，大幅度增加的桌面计算能力增加了对新技术的实际应用。到了 上世纪八十年代末，通用电气第一个出售遗传算法的产品( 一种基于大型机的用于工业工 序的工具) 。在1 9 8 9 年，a x c e l i s 公司发布了e v o l v e r 程式，作为世界上第二款遗传算法产品 和第一款为台式机设计的遗传算法产品。 2 1 2 遗传算法的生物原理 遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下3 个 方面。 1 ) 遗传 生物的普遍特征，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而 武汉科技大学硕士学位论文第7 页 子代总是和亲代具有相同或相似的性征，物种才能稳定存在 2 ) 变异 亲代和子代之间及子代的不同个体之间总是有些差异的，这种现象称为变异。变异是 随机发生的，变异的选择和积累是生命多样性的根源。 3 ) 生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行，其结果是 适者生存，即具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰。通过 一代一代的生存环境的选择作用，性状逐渐与祖先有所不同，演变为新的物种。这种自然 选择过程是一个长期的、缓慢的、连续的过程。 遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群 体中，按所选择的适配值函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适配 值高的个体被保留下来，组成新的群体，新的群体既继承上一代的信息，又优于上一代。 这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单， 可并行处理，并能得到全局最优解。 遗传算法简称g a ( g e n e t i ca l g o r i t h m s ) ，是美国m i c h i g a l l 大学h o l l a l l d 【4 】教授在1 9 6 2 年 提出通过模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。 作为一种用于计算最优化和搜索问题最优解或近似最优解的方法，遗传算法属于全局 的启发式搜索，是进化算法的一个特殊的分类。受进化生物学影响并发展起来的进化算法 使用的技术包括遗传、变异、选择和交叉等。 遗传算法通常表现为一种计算机模拟。对于一个最优化问题，一定数量的候选解( 称 为个体) 的抽象表示( 称为染色体) 的种群向更好的解进化。传统上，解是用二进制表示 的( 即o 和1 的串) ，但也可以用其它表示方法。进化从完全随机个体的种群开始，之后一 代一代的发生。在每一代中，评价整个种群的适应度，从当前种群中随机地选择多个个体 ( 基于它们的适应度) ，通过自然选择和突变产生新的生命种群，该种群在算法的下一次 迭代中成为当前种群。 在计算机仿真中遗传算法针对某一优化问题，备选的各显型中的染色体可以演化出更 好的解。解的一般表现为一串二进制数，当然其他的编码也行。进化通常由一群随机产生 的个体在繁殖时开始。在每一代中，种群中每个个体的适应度都在进化。若干个个体被从 当前种群中随机的挑选出来( 根据它们的适应度) ，经改变( 重组和随机的变异) 形成新 的种群。算法的新一轮迭代又从新的种群开始。当繁殖的代数达到最大值或者种群的适应 度达到满意值时，算法终止。 第8 页武汉科技大学硕士学位论文 2 1 3 遗传算法的基本操作 1 ) 初始化( i n i t i a l i z a t i o n ) 随机产生的初始化个体解组成了一个初始的种群。待解问题的特点决定了种群的大 小，通常包含数百个可能的解。在习惯上，种群包含搜索空间内全部的可能解。有时也从 可能存在最优解的范围中去选取解。 2 ) 选择( s e l e c t i o n ) 每个成功的一代将有一部分被用于繁殖下一代。经过适应度评价，适应度高的解将更 有可能被选择出来。某些选择方法评价每个解的适应度并优先选择最好的解。为了节约时 间，有的选择方法只评价种群的一个随机样本。 大部分的函数是随机的和事先设计好的，保证仅有少部分的次优解保留下来。这将保 证种群的多样性，防止种群过小，产生过早收敛的解。选择方法还包括赌轮选择和竞赛选 择。 选择是遗传算法中的一个阶段，在这个阶段中个体染色体被从种群中挑选出来用于繁 殖下一代。通常的遗传选择步骤如下： 每个个体都有由适应度函数评价产生的标准化适应度。所谓标准化的意思是用所 有个体适应度的和除以每个单个的值，以至所有结果的适应度的总和相等。 根据适应度对种群划分。 计算适应度( 累加个体的适应度就是将它本身的适应度加上前面全部个体适应 度) 。最后一个个体累计适应度必须是l ，否则说明标准化环节出错。 在0 和1 之间一个随机数r 。 被选中的个体是第一个累计标准化值大于r 的个体。 如果这个步骤重复执行，直到有足够多的个体，这种选择方法称作适应度比例选择或 赌轮选择。如果不采用对一个指针旋转多次，而采用若干个等分的指针在一个轮盘罩，只 旋转一次，称作随机普遍取样。竞赛选择是从一个随机选择子集罩反复选择最好的个体。 平截选择是从个体中选出二分之一、三分之一或者某一比例的方法。 还有另一种选择方法，不对所有的个体选择，而仅仅选择适应度高于给定值的个体。 把一代中最好的个体不变地保留到下一代，称作精英选择。这是产生新种群的一种不错的 派生方法。 3 ) 复制( r e p r o d u c t i o no p e r a t o r ) 通过遗传算子：交叉或者变异，从个体种群中选择出的解生成第二代种群。 为了繁殖新一代的解，用于繁殖的一对亲代解被从解空间里选出。使用交叉、变异的 算子产生的子代解具备其亲代的很多特性。一代一代的持续繁殖，直到产生出适当大小的 武汉科技大学硕士学位论文第9 页 新种群。尽管复制方法是基于生物学两个亲代产生一个后代的启发，然而有些研究表明超 过两个亲代可复制出更好的染色体。 以上的进程最终使后代种群与初始种群不同。既然只有最好的个体从第一代中选出， 因此平均适应度会增加。 4 ) 变异( m u t a t i o no p e r a t o r ) 在遗传算法的计算中，变异是一种遗传算子，在产生新一代的过程中用于保留遗传的 多样性，与生物学上的变异相似。 变异算子的经典例子就是遗传序列中任意一位改变原来的位置。一个常见的应用是对 序列中每一位产生一个随机的变量。这个随机变量决定某数位是否改变。基于生物学的点 突变，这个变异进程叫做单点突变。其他一些类型的变异包括倒置变异和浮点变异。在处 理排列问题时，基因编码受到严格的限制，变异就是交换、倒置和攀登。 遗传算法中变异的目的是保留和引入多样性。变异使算法避免局部极小，防止染色体 的群组间过于类似，导致进化减慢或停止。 5 ) 交叉( c r o s s o v e ro p e r a t o r ) 在遗传算法中，基于繁殖和生物学上的交叉用于丰富繁殖过程中的编码。很多的交叉 技术存在于有机体中，而有机体通过不同的数据结构保存自己。交叉具体的有分为一点交 叉、两点交叉和剪切拼接。 一点交叉( c r o s s o v e r p o i n t ) ：一点交叉指的是在两个亲代染色体序列中有一个交叉点。 所有亲代染色体中在交叉点前的数据交换，产生子代染色体。如图2 1 所示。 一i v m a n t $ ； lc t o i i $ o v e ro o m t 嘲一 i 了、c ，e n 瞳一 图2 1 一点交叉示意图 两点交叉( c r o s s o v e rp o i n t s ) ：两点交叉要求选择亲代染色体上的两个点。两点间的序列 在两个染色体之间交换，产生两个子代染色体。如图2 2 所示。 一 r ，a r a r 一毒： c r o s t o v wo o t t t t j 1 1 j c a r a n 图2 2 两点交叉示意图 剪切拼接( c u ta n ds p l i c e ) ：另一种交叉叫做剪切拼接，这一操作会导致子代染色体的长 度改变。原因是每个亲代的交叉点不同。如图2 3 所示。 第1 0 页武汉科技大学硕士学位论文 b ： l n 蚶n ： 图2 3 剪切拼接示意图 2 1 4 遗传算法的优化结果 结合一个具体的例子，介绍采用遗传算法进行路径优化的基本步骤，通常分为以下几 步： 第一步：对参数编码和初始群体设定 针对路径优化问题，采用对焊点序列进行排列组合的方法编码。某个路径的染色体个 体就是该焊接路径所经焊点的顺序。 取迸制编码，即每个基因仅从l 到n 的整数里面取一个值，每个个体的长度为， 为焊点的总数。定义一个s 行f 列的矩阵来表示群体，f 表示焊点个数+ l ，即n + i ，s 为 样本中的个体数目。针对3 0 个焊点的路径规划问题，f 取3 l ，矩阵每一行前3 0 个元素表示 经过的焊点编号，最后一个元素表示经过这些焊点要经历的距离或者消耗。 第二步：适应度函数的设计 用距离的总和作为适应度函数，来衡量结果是否为最优。将矩阵中每一行中表示经过 的距离或消耗的最后一个元素作为适应度函数。 任意两个焊点m 、n 之间的距离或者消耗表示为： z 。= ( 一毛) 2 + ( 一只) 2 通过样本的路径长度或者消耗得到目标函数和自适应度函数。 焊点的组合数是t 一2 组，目标函数为： t - 2 ，( f ) = a ( j ) ( 2 1 ) 根据t 的定义，每两个 ( 2 2 ) 自适应度函数取目标函数的倒数，即： 巾) 2 南 眨3 ) 第三步：计算选择算子 选择就是从个体中选择优秀的个体，淘汰劣质的个体的操作，这是建立在群体当中个 体适应度评估基础上的。 仿真中采用最优保存方法，即将群体中适应度最大的c 个个体直接替换适应度最小的 c 个个体。这里取c = 1 5 。 武汉科技大学硕士学位论文第1 1 页 第四步；计算交叉算子 交叉算子在遗传算法中起着核心作用，它是指将个体进行两两配对，并以交叉概率以 将配对的亲代个体加以替换重组而生成新的个体的操作。取见= 0 9 0 。 有序交叉算子能有效地继承双亲的部分基因成分，达到了进化过程中的遗传功能，使 该算法并不是盲目的搜索，而是趋向于使群体具有更多的优良基因，最后实现寻优的目的。 第五步：计算变异算子 变异操作时以变异概率p 卅对群体中的个体某些基因位上的基因值作变动，若变异后子 代的适应度值更加优秀，则保留子代染色体，否则保留亲代染色体。仿真中取成= 0 2 。 我们在这里采用倒置变异法。 导致变异法简单的将就是假设当前个体x 为( 572341698 ) ，如果当前的随机概 率值小于，则随机选择来自同一个体的两个点m 。和m ：，然后倒置该两点间部分，产生 新的个体。 例如，假设随机选择个体x 的两个点位“2 ”和“6 ”，则倒置该两个点的中间部分，即将 “3 4 1 ”变为“1 4 3 ”，产生新的个体x 为( 572l43698 ) 。 综上，遗传算法参数设定为群体中的个体数为s = 5 0 0 ，交叉概率为阢= 0 9 0 ，变异概 率为以= 0 2 。通过改变进化代数k ，寻找最优的路径组合。仿真结果如图2 4 - 2 6 所示，为 不同迭代次数下路径优化的仿真结果。根据图示可以看出当经过6 0 0 0 次迭代后，路径距离 达到最小。 图2 4 进化代次数为5 次时的轨迹 移动距离= 4 9 3 1 4 6 3 第1 2 页武汉科技大学硕士学位论文 图2 5 进化代次数为1 0 0 0 次时的轨迹 移动距离= 4 5 5 8 2 1 3 0 1 。一二一l 一l l 1 01 0 2 0 3 0加7 0 图2 6 进化代次数为砷o o 次时的轨迹 移动距离= 4 2 1 3 9 6 5 与其它优化算法相比，使用遗传算法存在的一些问题：对于复杂的问题，适应度函数 的反复评估是抑制了人工进化算法的主要方面。在寻找复杂的高维、多模态问题的最优方 案时，我们往往需要付出高昂的代价去评估适应度函数。在现实世界的问题中，如优化问 题，单一的函数评估可能需要几个小时到几天的时间完成模拟。典型的优化方法不能处理 一 一 一 一 。 一 。，肛7 一 ，、 ， 一 厂 、 、移 、 0 一 一：、 ，以 弦 ， 0 、 幻 武汉科技大学硕士学位论文第1 3 页 这种类型的问题。在这种情况下，我们可能需要放弃一个确切的评价而去使用近似的，但 是有效率的适应度f 钳】。很明显，近似模型的合并可能是最有前途的方法之一，使我们令人 信服地利用遗传算法解决复杂的实际生活问题。 在处理很多问题时，遗传算法表现出收敛于任意点或者局部最优，而不是我们所希望 得到的全局最优解。换句话说，就是它不知道如何去放弃短期的适应度而去寻求长期的适 应度。发生这种情况的可能性取决于适应度的状况：某些问题可以很容易的上升到全局最 优，有些则很容易的上升到局部最优。使用不同的适应度函数、增加变异率、通过选择技 术、维持不同解的规模可能处理此类问题，虽然“没有免费午餐定理 证明没有解决这个 问题的一般方法。 强加一个“特殊的惩罚 以保持多样性是一个常见的技术。对任何有足够多相似性的 群体做出惩罚，减少该种群在随后几代中的数量，与此同时保证其它的个体在种群中继续 存在。但是这一方法也未必有效，这都取决于问题的范围。多样性对于遗传算法来说非常 重要，因为均匀的种群是不会产生新的解的。在进化策略和进化规划时，多样性就没有那 么的必要了，因为突变才是更大的依赖。 因为基因组的早期就开始收敛于不再可能的有效解，所以在动态数据集上运行是困难 的。目前提了出来一些改进的方法：在解的质量下降时，增加突变的概率( 称作触发超变 异) ；增加遗传多样性防止早熟收敛；在基因分子库里推出全新的、随机生成的元素( 称 为随机移民) 等。同样，进化策略和进化规划可以实施所谓“逗号战略”，也就是说亲代是 不被保留的，新的亲代只从后代中选择，这样可以更加有效的处理动态问题。 遗传算法不能有效地解决例如决策问题这类只有一个单一的适应度评价( 正确或是错 误的评价) 的问题，因为没有办法能让解收敛。在这种情况下，随机搜索可能会和遗传算 法一样快的找到一个解决方案。但是，如果情况允许成功或失败的判断重复给予( 可能) 不同的结果，那么可以对失败率和成功率提供了一个合适的适应度评价。 对于具体的优化问题和解决问题的情况，可能会发现其它优化算法比给予同等数额计 算时间的遗传算法要好。替代和互补的算法包括进化策略、进化规划、模拟退火、高斯适 应、爬山、群体智能( 例如：蚁群优化、粒子群优化) 和整数线性规划的方法等【9 o l 。 2 2 神经网络优化方法 2 2 1 神经网络理论基础 1 9 8 6 年美国物理学家j j h o p f i e l d ：乖l j 用非线性动力学系统理论中的能量函数方法研究反 馈人工神经网络的稳定性，提出t h o p f i e l d 神经网络，并建立了求解优化计算问题的方程， 并证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。通过路径规划 第1 4 页武汉科技大学硕士学位论文 问题的成功解决【1 1 】，开辟了神经网络模型在计算机科学应用中的新天地，并受到广泛关注 和应用。 基本的h o p 6 e l d 神经网络是一个非线性元件构成的全连接型单层反馈系统，h o p f i e l d 网 络中的每一个神经元都将自己的输出通过连接权传送至所有的其它神经元，同时又都接收 所有的其它神经元传递过来的信息。h o p 6 e l d 神经网络是一个反馈型的神经网络，网络中 的神经元在t 时刻的输出状态实际上间接地与自己的t l 时刻的输出状态有关，其状态变化 可以用差分方程描述。反馈型的网络的一个相当重要的特点是具有稳定状态时，也就是它 的能量函数达到最小的时候。作为按内容寻址的存储系统，h o p f i e l d 神经网络系统使用二 元化阈值单元。保证这些单元收敛于局部最小，但不保证收敛于存储图案之中的一个。 所有真实的计算机都是动态系统。它们在执行运算时，状态都伴随着时间的变化而变 化。一台数字计算机可以被看做是拥有大存储量的二进制寄存器。在一个特定的时间，计 算机的状态是一个长二进制字。开始计算时，首先要设定计算机的初始状态。标准初始化、 编制程序和数据是初始状态的决定因素。根据设计计算机时设定的规则，计算机计数器的 每次计数都会伴随状态的改变。经过一段时间，计算机停止改变状态，从寄存器的一个子 集中读出计算的结果。状态空问运动的二维示意图如图2 7 所示。 图2 7 状态空间运动的二维示意图 蓝色小点表示数字状态，箭头线表示状态转移的方向，红点表示最终状态( 没有向外 转换状态) 。 除了不能描述离散状态变量和时间情况外，状态空间流程图可以描述神经网络计算或 者相似的计算。对于普通的神经网络，根据动态方程的具体细节是了解未来相当长时间状 态的唯一途径。 h o p f i e l d 神经网络在动态方程的后面有一个能量函数e 。它可以帮助我们理解可能的 终止状态。能量函数在约束条件下以单调的形式下降。可以认为计算的过程开始于初始状 武汉科技大学硕士学位论文第1 5 页 态，止于终止状态，这个过程中能量函数e 逐渐减小。因为存在一个基本的能量函数，唯 一可能的渐近线结果在吸引子上。h o p f i e l d 神经网络展现出在图灵意义上普遍计算的能力。 h o p f i e l d 神经网络分为两种类型：离散型和连续型。下面简单的介绍这两种网络。 2 2 2 离散时间的二元神经元网络 最初的h o p f i e l d 神经网络使用两值表示活性的神经元模型，活性取值1 或者0 。表示 从神经元k 到神经元的突触强度。神经网络的状态向量y 在时刻t ，元件l 描述t 时刻神 经元，的活性。系统的动态方程定义如下： l j p 十1 ，= 三：证o t h e r 奄w 乃i s e u ) + 弓 。 ( 2