基于改进粒子群算法的线缆路径规划方法研究.pdf

年 月第 卷 第 期机床与液压 ：本文引用格式：屈力刚，蒋帅，杨野光，等基于改进粒子群算法的线缆路径规划方法研究 机床与液压，（）：，（）：收稿日期：基金项目：辽宁省兴辽人才基金（）作者简介：屈力刚（），男，教授，研究方向为数字化设计与制造、数字化检测技术。：。通信作者：杨野光（），男，学士，工程师，研究方向为数字化装配。：。基于改进粒子群算法的线缆路径规划方法研究屈力刚，蒋帅，杨野光，李静（沈阳航空航天大学机电工程学院，辽宁沈阳）摘要：针对复杂机电产品布线路径规划过程中存在的效率较低、可应用性差等问题，提出一种改进粒子群算法，使用栅格法对布线空间进行划分，对障碍物建模并进行方向包围盒处理。为了避免算法在迭代过程中陷入局部最优，引入非线性逐渐递减的惯性权重与异步变化的学习因子，并且将贴壁约束加入到路径规划的过程中，保证线缆在敷设时路径的合理性。最后在仿真试验中，与标准粒子群算法进行对比，验证了改进后算法的合理性与可行性。关键词：自动布线；路径规划；改进粒子群算法；贴壁约束规则中图分类号：，（，）：，：；前言随着近些年来中国机械行业的快速发展，大量电气化设备在复杂机械产品中被广泛应用，这些设备承担着系统平台中的信号传递、电力传输等重要功能，因此，用于连接各设备部件的线缆便显得尤为重要。线缆布置过程中应用不合理的敷设方案可能会导致机械产品在运作过程中出现故障，严重的甚至导致停车事故的发生。美国通用公司曾对飞机发动机出现故障的原因进行分析，发现因为飞机线缆管路出现问题进而引发故障的比例占到了。由此可见，线缆敷设质量的高低对机电产品的安全性有着重大的影响。在飞机线缆敷设的工作流程中，完成线缆的路径规划是一个关键步骤。传统的线缆路径规划工作主要依赖于技术人员的经验，在物理样机上进行反复调试，效率较为低下，敷设精度也较低。自 世纪 年代以来，计算机辅助设计（，）软件的涌现改变了制造业传统的设计方法，其中比较有代表性的软件有、等。这些软件大都提供了专门适用于柔性线缆的敷设模块，但由于这些模块主要采用人机交互式的布局方式，自动化程度不高，并且在敷设过程中需要手动设置大量的接口端子与连接件等诸多零部件，操作较为繁琐，自动化程度仍然较低。近年来群体智能算法的发展为线缆敷设路径规划提供了新的思路。荷兰学者 和 将粒子群算法和 算法应用在分支管路布局研究问题上，端点之间相互的连接顺序通过粒子群算法确定，然后采用 算法搜索确定的两个端点间的最短空间距离。付宜利等建立混沌栅格预处理模型，应用混沌算法生成了线缆在布线空间中的路径。李春泉等对线束可布线区域进行栅格化处理，使用改进后的萤火虫算法成功在二维环境中搜索出线缆的路径。黄鑫等人改进了 算法，应用双向拓展随机数策略生成线缆的初始路径，然后利用 算法优化路径。杨旭等人在考虑线缆路径长度、弯线槽材料成本等约束条件的同时，通过拟物拟人算法以及改进后的 算法成功得到了线缆束的布线路径。柳强等人将改进 算法和双联卡箍约束应用在航空发动机多管路成束敷设领域，可同时规划出双联卡箍布置与多管成束敷设路径。本文作者基于以往学者的研究，通过改进后的粒子群算法，实现三维环境下线缆的路径规划。布线空间预处理 布线空间建模为了提高算法在敷设空间的搜索效率，需要对线缆敷设环境进行建模，并对其进行栅格化划分，方便之后应用算法进行路径规划。对布线空间建模作如下描述：假设布线空间为，将其投影在平面 中，并对其用正方形栅格划分，障碍物投影用 表示，其中 ，。在平面 中，可行布线区域设为，为 中的某一个点，线缆敷设路径规划即需要用点 规划出一条从起始点 到目标点 并且符合要求的较优路径。同时对障碍物作如下定义：（），（）（），（）当（）时，表示点 坐标处有障碍；当（）时，表示点 坐标处无障碍，处于可行布线区域。本文作者对障碍物应用方向包围盒（，）的处理方法使其简化，合理的简化处理可以提高算法的搜索效率。布线空间栅格划分及障碍物布置采用文献提出的空间等分网格法，将抽象建立的三维笛卡尔坐标系 的原点（），布线空间沿 轴方向投影为，沿 轴方向投影为，沿 轴方向投影为，从而便可模拟出整个敷设环境的长方体空间模型，如图 所示。为了将布线空间进行栅格划分，首先将 进行 等分，这样便得到了 个垂直于 轴的平面（，），同理，将 进行 等分，进行 等分，得到 个平面的交点。图 布线空间栅格划分 综上，将线缆敷设环境抽象成一个立体三维模型，建立三维坐标系，起始点在图上用红色圆圈表示，目标点在图中用蓝色方块表示，蓝色立方体与圆柱体表示障碍物，如图 所示。图 布线环境建模 线缆敷设粒子群算法设计与改进 标准 算法粒子群优化（，）算法是由 和 在 年提出的一种新型启发式优化算法，被大范围地应用在多目标优化等领域。粒子群算法认为搜索区域中的每个粒子只有速度与位置，不具有质量和体积的物理属性。在 年，和 提出在基本粒子群算法的速度项前加入惯性权重系数，从而形成了现在通用的标准 算法。假设在一个 维空间中有 个粒子组成一个群落，那么每个粒子的空间位置都对应了优化问题的一个候选解，每个粒子（，）的空间位置可以表示为（，），粒子 的速度可以表示为 （，），第 个粒子搜索到的最优位置称为个体极值，记为 （，），整个粒子群搜索到的最优位置称为全局极值，记为 （，），在更新到第 代时，机床与液压第 卷粒子 根据以下公式来更新自己的速度与位置：（）（）（）（）（）（）（）（）（）（）（）其中：（）表示当前代粒子 的历史最优位置；（）表示当前代种群的全局历史最优位置；为非负惯性权重，较大的 值有利于全局搜索，而较小的 值有利于局部开发；、为加速因子，通常取值在 之间；、为区间，之间的两个随机数。为防止粒子在算法迭代的过程中越过最大的搜索边界，需要规定粒子速度与位置的最大取值，若限定，则可将速度设为，其中。标准粒子群算法流程如图 所示。图 标准粒子群算法流程 改进 算法 非线性递减的惯性权重粒子群算法迭代过程中，惯性权重的取值是决定粒子的全局与局部搜索能力重要影响因素之一，提高粒子的全局搜索能力需要惯性权重数值较大，提高粒子局部搜索能力则需要惯性权重数值偏小。在算法迭代的早期，粒子的全局搜索能力更加重要，以便能够更快地完成对可行区域的搜索，而在算法迭代的后期，则需要对局部空间有着更强的搜索能力。逐渐递减的惯性权重有利于防止粒子出现早熟收敛的情况，避免陷入局部最优。有学者提出了线性递减的惯性权重，迭代公式如下：（）文中采用一种非线性惯性权重，计算公式如式（）所示，两种惯性权重的变化曲线如图 所示。()（）（）式中：，；为当前迭代次数；为最大迭代次数；为区间，上的随机数。图 改进前后惯性权重函数图象变化对比 异步变化的学习因子公式（）中的学习因子 与 可以使粒子具备两个重要能力：（）粒子的自我归纳和总结能力；（）逐渐向群体中适应度值更加优秀的粒子靠拢，进而靠近群体或相邻区域中的最优点。在寻优的初期，需要突出粒子的自我学习能力；在寻优的后期，为避免陷入局部最优并能够逐渐在全局最优解处收敛，此时则需要突出的社会学习能力。因此，为避免陷入局部最优与提高算法的寻优能力，应用随迭代次数异步变化的学习因子，学习因子 与 的变化公式设为 （）（）式中：学习因子 ，。与 的异步变化函数图像如图 所示。图 异步变化的学习因子函数图像 增加贴壁约束机械产品内部线缆敷设时往往会遇到两个需要连接的端口距离较远的问题，出现这种情况技术工人往往会将若干根线缆通过连接件连接组成一根较长的线缆，以便日后的维护与更换。此时线缆就需要添加辅助固定装置，进而便于安装，减小振动，提高系统工作的稳定性。辅助固定装置可以在敷设空间平面以及障碍物表面添加。这就要求规划出的线缆路径保持贴壁，尽量避免线缆产生悬空的工作状态，进而满足线第 期屈力刚 等：基于改进粒子群算法的线缆路径规划方法研究 缆敷设的工程要求。本文作者作者在算法中加入布线空间中 轴方向的约束，通过判断粒子在空间中的位置进而对其进行调整。当粒子位于障碍物内部时将粒子的 轴方向坐标调整为所在障碍物的高度值，如果处于可布线空间中则限制在 平面中与布线空间表面保持贴壁。通常情况下，在线缆敷设路径规划的流程中，一般先利用智能算法规划出一条大致的路径，然后再对路径进行优化修正，加入各种约束条件，使得最终能够产生一条能够满足要求的路径。但这样会导致步骤稍显繁琐，故本文作者将约束条件加在粒子群算法中，让仿真出的路径尽可能直接满足敷设要求，减少工作中不必要的流程，提高工作效率。并在算法中加入适当数量的关键点，运用算法优化每个关键点的位置。通过对标准粒子群算法进行以上改进后，线缆的路径规划流程如图 所示。图 改进后粒子群算法流程 线缆路径规划的算法仿真实现算法模拟测试时的运行环境如下：处理器为 （）（），；运行内存为 ；操作系统为 ；仿真软件为。应用文中提出的改进粒子群算法进行测试，将未应用贴壁约束的标准粒子群算法路径规划结果与改进后的方法进行对比，以验证改进后算法性能的优越性。粒子群算法的基本参数设置如表 所示。表 粒子群算法基本参数设置 种群规模关键点个数最大迭代次数 地图规格为起始点坐标为（，），目标点坐标为（，），线缆路径用红色曲线表示。在布线空间中添加障碍物包围盒模型，长方体障碍物与圆柱体障碍物模型参数分别如表 和表 所示。表 长方体障碍物数据 中心点坐标长、宽、高（，），（，），（，），（，），（，），（，），表 圆柱体障碍物数据 中心点坐标半径高（，）（，）通过优化算法中设置的关键点的空间位置，其他的点通过插值生成，最后通过三次样条数据插值拟合出最终路径。图 为未添加贴壁约束时粒子群算法规划的线缆路径，可以看出虽然标准粒子群算法规划出了一条从起始点到目标点的路径，路径整体也未与障碍物发生干涉，并且路径长度远小于改进粒子群算法，但路径位姿大部分为悬空状态，不符合线缆敷设工程要求。图 为算法改进前迭代的适应度变化曲线，图 为添加贴壁约束后的路径，线缆路径保持贴壁，方便添加卡箍对线缆进行固定，符合线缆敷设工程要求。虽然改进后的路径在线缆经济性方面不如改进前，但满足敷设工程要求这项指标的优先级高于经济性。图 为算法改进后迭代的适应度变化曲线。图 未加入路径贴壁约束的仿真结果 图 未加入路径贴壁约束的适应度变化曲线 机床与液压第 卷图 加入路径贴壁约束的仿真结果 图 加入路径贴壁约束的适应度变化曲线 表 为改进前后粒子群算法路径规划的线缆长度与程序运行时间的对比。表 改进前后生成路径长度与规划时间对比 方法规划路径长度规划时间 标准 算法改进 算法 综合以上结果可以看出改进后粒子群算法可以在多障碍物模型中较快地搜索出一条安全合理的路径。相较于标准粒子群规划出的线缆路径，在路径空间位姿形态上改进后的粒子群算法展现出更佳的优越性。结语针对标准粒子群算法易陷入局部最优的问题，应用改进粒子群算法对线缆敷设问题展开研究。首先对算法中的几个重要参数进行改进，然后加入贴壁约束条件，并且在仿真试验中证明了改进粒子群算法规划出的线缆路径位姿更符合工程实际，满足敷设要求，可以为机电产品的线缆敷设问题提供一定的参考。参考文献：孔瑞莲航空发动机可靠性工程北京：航空工业出版社，黄国振构建数字化样机：钣金设计与三维布线北京：人民邮电出版社，（），：付宜利，封海波，孙建勋，等基于混沌算法的机电产品管线自动敷设研究计算机集成制造系统，（）：，（）：李春泉，胡宇威，尚玉玲，等面向线缆路径规划的改进萤火虫算法研究机械设计与制造，（）：，（）：黄鑫，袁庆霓，李思良基于改进 算法的线缆路径规划研究计算机仿真，（）：，（）：杨旭，周德俭，宋微，等一种考虑复杂约束的线缆束路径规划方法西安电子科技大学学报，（）：，（）：柳强，刘贝贝，于嘉鹏，等考虑双联卡箍约束的航空发动机多管成束敷设优化方法机械工程学报，（）：，（）：胡小兵，黄席樾基于蚁群算法的三维空间机器人路径规划重庆大学学报（自然科学版），（）：，（），（）：，：，：，（），：，：朱振方基于微粒群和遗传优化的文本过滤关键技术研究济南：山东师范大学，第 期屈力刚 等：基于改进粒子群算法的线缆路径规划方法研究