基于量子遗传算法的移动机器人的一种路径规划方法

第３９卷第４期　２０１１年４月　同济大学学报（自然科学版）　Ｊ０ＵＲＮＡＩ．０Ｆ　１ＵＮＧＪＩ　ＩＨ　ＩＶＥＲＳＩＴＹ（ＮＡ，兀瓜ＡＩ．ＳＣＩＥＮＣＥ）　ＶＯ１．３９Ｎｏ．４　Ａｐｒ．２０１１　

文章编号：０２５３—３７４Ｘ（２０１１）０４—０５７６—０５　ＤＯＩ：ｉ０．３９６９／ｊ．ｉｓｓｎ．Ｏ２５３—３７４ｘ．２０１１．０４．０２０　

基于遗传算法的白车身机器人焊接路径规划　

张春伟，刘海江，姜冬冬　

（同济大学机械工程学院，上海２０１８０４）　

摘要：分析了轿车白车身制造过程中机器人拼焊工位焊接路　

径规划的特征，将焊点与机器人的工具原点抽象为空问点，　

根据图论理论建立各点的关系图．将约束条件转化为局部有　向关系矩阵，以机器人空间运动最短距离为目标，建立货郎　

担问题数学模型，利用遗传算法求解．依据关系矩阵产生合　

法初始种群，并确定选择、交叉、变异等遗传算子，以　

ＭＡＴＬＡＢ语言编程计算．行李箱盖补焊工位焊接路径规划结　果表明，该方法能够对机器人焊接路径合理规划，规划方案　

已成功用于工程实际．　

关键词：白车身；机器人焊接；有向图；遗传算法；货郎担问题　

中图分类号：ＴＨ　１６２　文献标识码：Ａ　

Ｒｏｂｏｔ　Ｗ＿ｅｌｄｉｎｇ　Ｒｏｕｔｅ　Ｐｌａｎｎｉｎｇ　ｉｎ　Ｃａｒ．Ｂｏｄｙ　

Ｗｅｌｄｉｎｇ　Ｐｒｏｃｅｓｓ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　

ｇＨＡＮＧ　Ｃｈｕｎｗｅｉ，ＬＩＵｔｔａｉｊ￣　３　Ｇ　Ｄ０嘲删　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎｇｊｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０１８０４．Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｃｏｍｂｉｎｅｄ　ｗｉｔｌ１　ｇｒａｐｈ　ｔｈｅｏｒｙ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｗｅｌｄｉｎｇ　ｒｏｕｔｅ　

ｐｌａｎｎｉｎｇ　ｉｎ　ｃａｒ　ｂｏｄｙ－ｉｎ－ｗｈｉｔｅ　ｍａｎｕｆａｃｔｕｒｅ．Ｂｙ　ｒｅｇａｒｄｉｎｇ　ｔｈｅ　ｗｅｌｄｉｎｇ　ｐｏｉｎｔ　ａｎｄ　ｔｏｏｌ　ｃｅｎｔｅｒ　ｐｏｉｎｔ　ｆｒａｍｅ　ａｓ　ｓｐａｔｉａｌ　ｐｏｉｎｔ　ｔｏ　ｅｓｔａｂｌｉｓｈ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｇｒａｐｈ，ｔｒａｎｓｆｏｒｍｉｎｇ　ｃｏｎｓｔｒａｉｎｔ　ｆａｃｔｏｒｓ　ｉｎｔｏ　ｄｉｒｅｃｔｅｄ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｍａｔｒｉｘ　ａｎｄ　ｕｓｉｎｇ　ｍｉｎｉｍｕｍ　ｍｏｔｉｏｎ　

第３８卷　

ｖ０Ｉ．３８　第９期　

Ｎｏ．９　计算机工程　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１２年５月　

Ｍａｙ　２０１２　

・人工智能及识别技术・　文章编号：１ｏ０　一３４２８（２ｏ１２）０９—＿０１６６－一０４　文献标识码：Ａ　中圈分类号：ＴＰ１８　

基于关键链遗传操作的机器人路径规划　

粱金泉，周之平，黎明，万国　

（南昌航空大学信息工程学院，南昌３３００６３）　

摘要：针对复杂环境下遗传算法规划路径难的问题，提出一种基于关键链遗传操作的机器人路径规划方法。将回退策略和禁忌策略与启　

发式邻域搜索相结合保证路径的可行性。通过提取初始可行路径中的关键链，降低算法所需存储空间及计算代价。对关键链进行局部自适　

应变异和交叉操作，增强算法的优化能力。实验结果表明，该方法能有效地规划复杂环境下的机器人运动路径，算法性能优于同类算法，　

规划时间可满足实际应用需求。　

关健词：关键链；路径规划；可视性检测；遗传算法；回退策略；禁忌策略　

Ｒｏｂｏｔ　Ｐａｔｈ　Ｐｌａｎｎｉｎｇ　Ｂａｓｅｄ　０ｎ　Ｋｅｙ　Ｃｈａｉｎ　Ｇｅｎｅｔｉｃ　Ｏｐｅｒａｔｉｏｎ　

ＬＩＡＮＧ　Ｊｉｎ—ｑｕａｎ，ＺＨＯＵ　Ｚｈｉ—ｐｉｎｇ，ＬＩ　Ｍｉｎｇ，ＷＡＮ　Ｇｕｏ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｎｃｈａｎｇ　Ｈａｎｇｋｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ　３３００６３，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ｜Ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆｒｏｂｏｔ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｕｎｄｅｒ　ｃｏｍｐｌｉｃａｔｅｄ　ｅｎｖｉｒｏｎｍｅｎｔ，ａ　ｇｅｎｅｔｉｃ　ｏｐｅｒａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｋｅｙ　ｃｈａｉｎｓ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｂｏｔｈ　

ｒｅｔｒｏｖｅｒｓｉｏｎ　ａｎｄ　ｔａｂｏｏ　ｓｔｒａｔｅｇｙ　ａｒｅ　ｉｎｃｏｒｐｏｒａｔｅｄ　ｉｎｔｏ　ｈｅｕｒｉｓｔｉｃ　ｎｅｉｇｈｂｏｒｉｎｇ　ｓｅａｒｃｈ　ｔｏ　ｇｕａｒａｎｔｅｅ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ｏｆ　ｐａｔｈ．Ｔｈｅ　ｍｅｍｏｒｙ　ｒｅｑｕｉｒｅｍｅｎｔ　ａｎｄ　

基于遗传算法的输电线路无人机巡检路径规划

当前输电线路检验手段主要分为人工检验和机器检验两类，人工检验面临庞大的工作量和恶劣的工作环境。机器检验主要依赖先进的机器进行排查，在检验过程中，机器的工作效率决定检查效率。目前，使用无人机进行输电线路巡检的方法逐渐兴起，使用无人机巡检输电线路要提前规划巡检路径，其巡检路径包括：作业起飞点、降落点以及巡检作业目标点经纬度位置信息等。总之，使用无人机可以做到自主巡检，极大的提升工作效率。

标签：遗传算法;输电线路;无人机巡检;规划

随着社会经济的不断加快，人们的生活水平得到了提高，对用电量的需求不断增加，并且对电力系统有了更高的要求。然而电力系统的正常运行，离不开对输电线路的运行和维护工作，是确保电网稳定运行的基础，所以需要加强对输电线路的建设工作。安全第一、预防为主的原则来确保输电线路运行的稳定性，这就需要运行维护部门要在日常工作中做好线路的巡视、检测、维修和管理工作。利用先进的技术，不断在工作中积累经验，从而使线路能够在安全运行的状态下工作。

一、遗传算法的基本原理

与旧的搜索算法不同，GA从种群的初始解决方案开始其搜索过程。群体中的每个个体被称为染色体。在迭代过程中染色体的不断更新称为遗传。GA主要通过交叉、变异、选择算子来实现。染色体的优点和缺点通常通过适应性来评估。根据适合度值的大小，从父母和后代中选择一定比例的个体作为后代的群体，然后继续迭代计算直到它收敛到全局最佳染色体。适应度是遗传算法用来评价种群在进化的过程中所能达到的最优值的一个概念。为了证明染色体的适应性，引入了测量每条染色体的功能函数，称为适应度函数。

二、遗传算法的特点

通过了解遗传算法的基本步骤，我们可以总结出遗传算法的几个特点：遗传算法以参数的编码集作为运算对象，并且在执行搜索过程中，不受优化函数连续性及其导数求解的限制，因而具有很强的通用性。遗传算法直接使用由目标函数确定的适应度函数信息，以群体为单位执行搜索过程，加快搜索到适应度较好的搜索空间，因而具有较强的全局搜索能力。遗传算法简单通用，普适性强，易于与其它算法结合构成混合智能算法，并且该算法具有很强的鲁棒性，因而在众多领域得到了广泛的应用。

遗传算法是根据生物界的优胜劣汰、适者生存　

的原则提出来的一种搜索和优化算法，它采用随机　

运算规则，对搜索空间无特殊要求，需要求导，具有　

运算简单、收敛速度快等优点，并且在全局寻优方面　

具有高效性和隐含的并行性，所以是一个较好的路　

径规划方法，越来越受到重视。遗传算法有两个重　

要组成部分，首先，遗传算法的执行应具备一定的种　

群规模，每个个体代表一条从起点到终点的可行路　

径；其次，编码的方法也很重要，它关系到运算的复　

杂程度及程序执行的时间。　

标准的遗传算法包含四个步骤：　

①适应值函数的选择：每个个体的适应值函数　

（即目标函数）均是与寻优标准相对应的；　②选择操作：把当前种群作为父辈，以适应值函　

数为标准从中选择部分个体；　

③重组操作：通过交叉和变异来产生新的个体　

（称为子代）；　

④替代操作：用适应值大的子代个体替代父代　

中适应值小的个体。　２路径规划算法　

２．１环境模型的建立　

ｔ　本文采用ｍｘ　１７１的二维栅格作为机器人的工作　

环境模型，用直角坐标法在矩形的工作空间中建立　

多个等值大小的小栅格，栅格的尺寸以保证机器人　

在其中自由活动为准。确定起始栅格Ｓ和目标栅格　

ｇ，工作环境模型中的障碍物随机产生，以适应未知　

环境的要求。图一所示为随机产生障碍物的四种环　

境模型。　

２．２种群初始化　

用一个个体代表一条路径，采用序号编码的方　

法减少个体的长度，降低算法的复杂度及运算时间。　

假设其个体长度为Ｌ，则令起点Ｓ处于０序号位置，　

目标点ｇ处于（Ｌ—１）序号位置。序号编码与直角坐　

标相对应，根据需要相互转换，令Ｐ代表栅格序号，　

则其对应关系为：　

ｐ＝ｘ＋１０ｙ　（１）　

而在ＭＡＴＬＡＢ语言中，Ｘ和ｙ与Ｐ的关系为：　图一障碍物位置不确定的环境模型　

的建立（ｚａ为障碍物的数目）　

，Ｘ＝ｒｅｉｎ（Ｐ，１０）＋Ｏ．５　ｉ），＝ｆｉｘ（ｐ，１０）＋０．５　（２）　

式（２）中，ｒｅｉｎ表示取佘操作，ｆｉｘ表示取整操作。　

对已建立的栅格随机产生障碍物，并加入序号编码。