基于协同进化算法的分支线缆自动布局设计方法

徐金宝， 刘检华， 刘佳顺， 刘　潇

(北京理工大学机械与车辆学院，北京 100081)

基于协同进化算法的分支线缆自动布局设计方法

徐金宝， 刘检华， 刘佳顺， 刘潇

(北京理工大学机械与车辆学院，北京 100081)

针对分支线缆布局设计中分支点难以确定的问题，提出基于协同进化算法的分支线缆自动布局设计方法。首先建立分支线缆的线束模型，基于线缆的线束模型信息将分支线缆分解为多个一对一的单根线缆，每个单独的线缆代表一个种群；在此基础上采用改进的快速扩展随机树算法求解单根线缆的路径，然后基于协同进化的思想对分支线缆的分支点进行寻优，通过种群间相互影响适应度的评价使得分支线缆的布局结果达到最优；最后对最终优化得到的路径点进行拟合，从而获得线缆作为布局设计结果并输出。设计并开发了线缆自动布局设计软件原型系统，进行算例测试与实例应用，验证方法的可行性。

分支线缆；自动布局设计；协同进化；快速扩展随机树

线缆是航空、航天和船舶等行业的复杂机电产品的重要组成部分，作为传递能量和信号的介质，线缆布局设计质量直接影响着机电产品的性能与可靠性。传统的线缆布局设计通常通过物理样机来实现，随着CAD技术的出现和发展，线缆数字化布局设计技术获得越来越广泛地应用，并有效提高了线缆布局设计效率和质量。目前，线缆数字化布局设计主要包括人机交互式布局设计和自动布局设计两种方法，而自动布局设计技术由于具有更高的布线效率，已逐渐成为国内外研究热点。

线缆可以分为单根线缆和分支线缆。工程中的线缆零件往往是包含多个接插端子的分支线缆。与单根线缆相比，分支线缆的布局设计更为复杂，分支线缆在进行布局设计时不仅需考虑分支点位置的合理性，还需考虑线缆整体的布局特性以及满足单根线缆所需满足的布局约束条件。由于线缆分支点位置的不同，线束的成束拓扑会有相应的变化，进而线缆的长度、布局、捆扎位置也都有所不同。

在线缆人机交互式布局与装配仿真方面，中国工程物理研究院的魏发远等[1]提出了一种基于虚拟样机的交互式电缆布线方法以及在此基础上基于逆运动学的安装仿真方法。北京理工大学的尚炜等[2]针对复杂机电产品中柔性线缆结构复杂且在装配操作中发生变形而导致的装配过程仿真难的问题，系统提出了柔性线缆装配过程仿真的解决方案及其关键技术的实现方法。北京理工大学的王志斌等[3]针对机电产品中电缆布局设计中没有考虑物理特性导致电缆取样长度不准确的问题，提出了虚拟环境中基于物理特性的电缆布局设计方法。

目前国内外有关分支线缆自动布局设计的成果较少。Conru[4]采用遗传算法对分支线缆布局问题进行求解，首先确定分支点的位置，然后进行路径的求解，考虑了多种约束的路径成本，但并未考虑线缆的柔性。桂林电子工业学院的吴银锋等[5]采用最小斯坦纳树生成法求解一对多的线路问题，以自行开发的电子整机三围布线系统(3D routing system，3DRS)验证了该算法的可行性。北京航空航天大学的郭伟等[6]提出了一种在骨架模型中进行快速自动布线的方法，根据电连接器节点数据表与三维模型的连接关系，能够自动完成三维布线，生成线缆分支图以及各种线缆的信息报表。合肥工业大学的徐本柱等[7]将无向图布局理论中的力导向不算模型和算法引入到汽车线束连接图的布局中，实现了连接图主干的自动搜索和线束分支的约束对称布局，进而完成了汽车线束连接图的自动布局。此外，合肥工业大学的刘晓平等[8]提出基于工程语义约束的线束预装配自动规划方法，朱吉满等[9]提出了一种汽车线束工艺工序及工序关系自动生成方法。南京航空航天大学的王发麟等[10]针对复杂机电产品中线缆工程语义信息统一表达难、线缆复杂拓扑结构难以表示和存储的问题，提出基于本体和无向图的复杂线缆信息表达与存储分析方法。

与分支线缆布局技术研究成果的匮乏相比，分支管路布局设计的国内外研究成果相对多一些。华盛顿大学的 Park[11]提出了管路布局的单元生成法，将分支管路简化为端点分支和中点分支两种简单形式的混合，但是该方法难以确定分支点的位置。荷兰代尔夫特理工大学的 Asmara和Nienhuis[12]应用粒子群算法和Djikstra算法对分支管路布局问题进行了研究，首先用粒子群算法确定端点的连接顺序，然后依次用Djikstra算法搜索每次所选定的两个端点间的最短管路。北京航空航天大学的樊江等[13]应用改进的 Lee算法以及最小斯坦纳生成树法对分支管路端点进行串行连接，该方法首先选定两个端点并应用改进的 Lee算法进行连接，然后依次连通其余端点。哈尔滨工业大学的封海波[14]应用混沌算法和粒子群算法对分支管路敷设问题进行了研究，该方法需要事先确定主管路，然后在连通其余端点。东北大学的Liu和Wang[15]采用粒子群算法以及最小斯坦纳生成树法求解航空器表面的分支管路布局问题，并采用测地线的原理保证管路的最短路径。

综上所述，虽然国内外目前研究成果中针对分支管线布局有不同的优化方法，但都需要事先确定连通顺序或假定分支点的位置，然后以分支点为起点和其他终点相连寻找路径。由于分支管线敷设顺序和分支点位置的不确定性，使得已有的方法计算效率低，难以在工程中得到应用。

近年来，协同进化算法成为计算智能研究的热点。该算法扩展了传统进化算法的应用范围，具有较高的自适应能力，能有效地解决一些传统进化算法难以解决的复杂问题。协同进化最早由Ehrlich和 Raven[16]在讨论植物和植食昆虫(蝴蝶)相互之间的进化影响时提出的。协同优化算法在解决复杂问题时具有明显的优势，并在各学科领域得到了应用[17-18]。分支线缆由于结构的复杂性，导致其布局设计十分繁琐。本文基于协同进化算法求解复杂问题的优越性以及分支线缆的结构特点，将其分解为多个形式相对简单的单根线缆，采用协同进化算法优化分支点的位置，在此基础上开发了线缆自动布局设计原型系统，并通过实例对算法进行了测试与验证。

1　分支线缆自动布局设计问题描述

基于协同进化算法的分支线缆自动布局设计技术的总体思路如图 1所示。求解的具体流程为：①通过CAD数据接口，将不同类型的产品设计CAD模型转换为三维线缆布局设计环境中的模型，并构建产品的结构件虚拟数字样机，作为线缆布局设计的模型准备；②对线缆布局设计过程中的约束信息进行分析，并转化为线缆路径规划的约束，例如线缆贴壁的约束、弯曲半径的约束等；③导入电器原理设计阶段的连接关系文件，如接线图和接线表等，从而得到分支线缆的基本连通信息和部分几何信息，但此时分支线缆的分支点的位置和布局路径还未确定；④基于改进RRT算法进行线缆布局初始路径求解，并利用协同进化算法进行布局优化与分支点寻优，从而得到可行的线缆布局结果，最后结合工程需求完成线缆布局设计结果的输出。

图1　分支线缆自动布局设计技术总体思路

工程实践中，产品内部结构复杂，线缆布局空间极不规则，导致可供线缆布局的空间十分狭小。为了确保线缆工作的可靠性，本文所考虑的线缆布局约束主要包括：

(1) 合理的分支结构，并确保电路连通关系。复杂机电产品中线缆数量多，合理的分支结构不仅能确保连通关系，更能简化布局；

(2) 合理的分支点位置可保证线缆尽量短；

(3) 避障，不与环境中装配体、组件及已布局的线缆等发生干涉；

(4) 尽量沿着障碍物表面布局；

(5) 满足线缆最小弯曲半径，避免过弯而损坏线缆。

2　分支线缆线束模型

在复杂机电产品中，线缆数量庞大，连接关系较复杂，并存在大量分支线缆(如图2所示)。采用合理的模型不仅能准确表达分支线缆及信息，更能为分支线缆自动布局设计提供数据支持，简化分支线缆的自动布局设计问题。为了缩短走线路径、节省走线空间、使得线缆布局简单整洁，实际中有相同电气连接关系和共同路径的多根导线通常会安装套管等辅助材料形成线束，如图 3所示。

图2　线缆零件示意

图3　线束示意

为了建立线缆的线束模型，将线缆抽象为 3个基本元素：线缆零件、线束、线缆段。线缆零件是指工程中将导线、电缆经过捆扎、分支、包扎、安装电器连接后，具有一定拓扑连接结构和外形的柔性零件。线缆段表达线缆零件中不存在分支的部分，如图4(a)中的AE、EF、FD等。线束是线缆零件中两个接插端子间具有电器连接关系的导线束。如图4(a)所示，接头A至接头C包含一个连通的线束。图4(b)采用了邻接表的形式存储并表示了此线缆零件中的线缆段与线束的关系。

图4　线缆线束模型

3　基于协同进化算法的分支线缆自动布局设计

协同进化是提高进化算法性能的一个新方法，其使用分解协调的思想将复杂系统的优化问题分解为一系列子系统优化问题，各子系统可以分别进行优化，再从整体上进行协调。算法充分体现了“协作”的思想，个体适应度评价就是要考察个体与其他群体个体协作解决问题的能力。而且，各个群体也是在每一代中相互协调、同步向上进化的，具有较高的并行性和鲁棒性。

分支线缆布局设计是具有多个接插端的线缆布局问题，其形式很复杂。若能够将分支线缆进行合理巧妙的分解，形成多个种群，其能够完全表达分支线缆的布局问题，且这些种群之间并不是全无关系，而是相互关联、相互影响的，那么就可以利用协同进化算法来解决分支线缆布局优化问题。

3.1基于线束模型信息的分支线缆分解

分支线缆有多个接插端，即多个出发端点，布局十分复杂，是一对多的布局问题。本文提出将结构复杂的分支线缆分成多个一对一的单根线缆，然后分别采用改进的RRT算法进行单根线缆路径求解，以此降低问题的复杂度。线缆线束模型充分考虑了线缆的连接关系信息，表达其内部的连通关系。因此，可以基于线缆的线束模型信息，将复杂的线缆拆分成多个单根线缆。

线束模型详细表达了复杂线缆的电器连通关系以及接插端子信息。图 2所示的分支线缆，包含线束AC、AD、BD，其中线束模型接头A与C相连，接头A与D相连，接头B与D相连。将分支线缆分解为3个单根线缆AC、AD、BD，如图5所示。分解后的单根线缆既相互独立，又彼此关联。复杂的分支线缆分解为由单根线缆 AC、AD、BD组成的一个系统。针对分解后的单根线缆，就可以采用改进的RRT算法进行路径求解。

图5　分支线缆分解示意

3.2基于改进RRT算法的单根线缆路径求解

3.2.1基本RRT算法

RRT算法是一种基于采样的路径搜索算法，由美国伊利诺伊大学的 LaValle和 Kuffner[19]提出。其设计用来解决高维非凸空间中物体的运动规划问题，特点是无需对空间中的障碍物进行显式表达，通常也不需要对空间进行预处理。

基本RRT算法的执行流程如下：

步骤1. 初始化路径搜索的起点xinit、终点位置xgoal，搜索步长s、终止循环数N等；

步骤2. 创建搜索树T，该树初始时为空。先将起点xinit放入T中，在预先设定好的循环数范围内执行步骤3～7循环，对RRT进行扩展，如图6所示；

步骤3. 通过随机采样得到一个随机点xrand；

步骤4. 计算并获取距离该随机点最近的点xnear(在最初的循环中，该点即为起点)；

步骤5. 沿xnear到xrand方向，通过给定步长s获取新的扩展点xnew；

步骤6. 对xnear到xnew部分进行干涉检查，若干涉，则进入下一次循环，若不干涉则继续该循环；

步骤7. 将xnew加入T中，并判断该点是否足够接近终点，若足够接近，则直接与终点相连，算法结束，否则进入下一循环。

图6　快速扩展随机树算法扩展示意

3.2.2基于改进RRT算法的线缆路径求解

线缆自动布局设计的核心问题是三维空间的布局路径求解问题。三维空间中的线缆的布局路径求解问题，可看作求解空间中的球形刚体机器人的运动规划问题[20]。因此，可以采用RRT算法求解线缆的布局路径。RRT算法直接用于线缆自动布局，计算效率低，且不能满足线缆布局的各项约束，因此基于其良好的适应性，并对采样或扩展策略进行改进，以用于线缆路径搜索。

为了满足工程中线缆沿着障碍物表面敷设的约束，采用基于障碍物碰撞信息的扩展策略。如图7所示，构造方向沿xnear到xgoal、起点为xnear、长度为 d的向量 μgoal。若 μgoal与障碍物发生碰撞，则直接计算出碰撞面片法向量 N(如图 7(a)所示)；若μgoal不与环境中障碍物发生碰撞(如图7(b)所示)，则产生与μgoal垂直且长度为d的向量μ，直到 μ与障碍物发生碰撞。计算得到当前碰撞面片的法向量N，即N垂直于碰撞障碍物表面。定义角度θ为单位向量N与向量μ的夹角：

取与 N垂直的方向为新的扩展方向，μe=μsinθ。构造以 xnear的父节点 xpar为起点、xnear为终点的向量 μp，分别计算 μe与 μp的夹角α(0°≤α≤180°)，μe与 μgoal的夹角β(0°≤β ≤180°)。若xnear为根节点，即μp不存在，如果β大于 90°，则使 μe反向，反之 μe不变。若 μp存在，如果α大于90°，则使μe反向，反之μe不变。沿μe方向扩展一个步长s得到xnew，若xnear到xnew方向不发生碰撞，则扩展成功，本文取步长s=4。

图7　基于障碍物碰撞信息扩展示意图

在设定的求解空间中，根据设定的刚体半径和搜索步长，按照上述改进RRT算法进行计算，可得到分布于求解空间内的“树”以及一条连接起始和终止点的“路”。由于RRT算法是随机采样算法，每一次运算所得到的“树”和“路”并不相同，但所得路径一定是空间可行的，即球形刚体机器人沿该路径运动时不与障碍物发生干涉，可将该路径中的所有节点的位置坐标取出并保存，以便得到线缆的初始路径，如图 8所示。为了得到较短的线缆路径，采用多次RRT重复求解，选择其中的最优解。

图8　利用改进RRT算法得到的沿障碍物表面的路径图

经过路径搜索得到一系列离散点，但在实际中需要平滑的线缆布局路径，因此需剔除冗余点，采用曲线进行拟合得到光顺的路径，对路径中各点最小弯曲半径、最小应力等进行计算及修正[21]，最后根据线束属性生成线缆。

3.3基于协同进化算法的分支点寻优

在采用改进的RRT算法求解单根线缆路径的基础上，基于协同进化算法优化得到分支线缆分支点的位置，其分支线缆自动布局设计方法主要包含以下5部分：

(1) 问题的分解。基于线缆的线束模型信息将分支线缆分解，分解后的每根线缆对应一个种群，整个分支线缆构成一个多种群的生态系统；

(2) 各种群的进化方式。每一个种群采用改进的RRT算法实现各自的进化过程；

(3) 种群的进化次序。在每一代中，单根线缆的生成顺序随机，即每一代中种群的进化次序是随机的；

(4) 个体适应度的评价。采用最优个体配合协同模式，即任一种群中个体的进化环境由原始环境和当前其他种群中的最优个体所形成的小环境叠加而成，因此不同种群的进化环境各不相同，同一种群在不同的进化代数下所处的进化环境也可能不同，而种群个体适应度的评价取决于该个体所处的环境。其他种群的代表在适应值评估过程中只提供一个环境，其本身并不接受任何的奖赏或惩罚，组合在评估中所获得结果不会影响到这些代表自身的适应值；

(5) 终止条件。当整体最优解不再变化时，输出这个整体最优解作为分支线缆系统的全局整体最优解，或以某一固定的进化代数为终止条件。

综上所述，基于协同进化算法的分支线缆自动布局设计方法的流程如图9所示。

基于协同进化的思想，将分支线缆分解为单根线缆，每根线缆分别对应一个种群，所有种群构成了一个生态系统。分支线缆系统的多种群协同进化算法的核心思路是：每根线缆对应一个种群，在第 gen代进化中，随机生成种群进化顺序，并设置可以避免由于固定进化顺序而产生局部最优解，也就是说种群的进化与顺序无关，排除了线缆进化顺序的干扰。假设最先进化的为线缆i(即种群i)，种群i在原始环境中率先进化，得到线缆i的gen代解Gen-i，并将线缆i的路径作为整个分支线缆的主干；假设第 2个进化的种群为j，则种群j的进化环境是由初始环境和gen代中已经产生的线缆i的解Gen-i组成的新的生态系统 i，种群 j在生态系统 i中产生一个 gen代解Gen-j；假设第3个进化的种群为k，则种群k的进化环境是由初始环境和gen代中已经产生的线缆i的解Gen-i、线缆j的解Gen-j组成的新的生态系统ij，种群k在生态系统ij中产生一个gen代解Gen-k。以此类推直到规划完最后一根线缆，得到整个三维分支线缆系统的 gen代解 Gen-best，将gen代解Gen-best和至今最优解Global-best进行比较，如果当代解优于至今最优解，则 Gen-best成为至今最优解，否则不变。循环执行上面的过程，直到满足迭代终止条件，即分支线缆系统的整体最优解不再变化或者满足固定的进化代数。

图9　基于协同进化算法的分支线缆自动布局设计流程

在协同进化过程中，任一种群个体的进化环境都由原始环境和当前其他种群中的最优个体代表所形成的小环境叠加而成，不同种群的进化环境各不相同，同一种群在不同的进化代数下所处的进化环境也可能不同，而种群个体适应度的评价会受到该个体所处的环境的影响，如图 10所示。同时其他种群的代表在适应值评估过程中只提供一个环境，其本身并不接受任何的奖赏或惩罚，在评估中所获得结果并不会影响自身的适应值。

图10　分支线缆种群间的协作原理

线缆种群间的协作行为和相互影响主要是使分支线缆的总路径变得更短。在优化单根线缆路径的前提下，与其重合的单根线缆路径越长，说明其共用的线束越多，即总路径越短，经济性越好。由此可以看出，本文方法只需使单根线缆的路径最优且与其他单根线缆路径尽量重合，就可以得到合理的分支点的位置，使分支线缆的布局设计达到较优。

本文讨论的是求分支线缆的最短路径问题，约束条件是线缆不与障碍物相交，并沿着障碍物表面敷设，弯曲半径不易过小，映射到对某一线缆种群个体的评价，就是求其他线缆种群个体与被评价线缆代表重合最多的最短路径，优化目标函数表达如下：

浮笼多是出现在半笼或是钢筋笼底部配筋相对较少时，混凝土浇筑到上半部分时下部混凝土开始初凝，形成硬壳导致钢筋笼整体上升。

其中，Pi和 Pc(c≠i)是单个线缆种群的路径，L表示单个线缆种群的路径， Pi∩Pc代表两个线缆种群的共同路径，优化目标是使得在单个线缆种群路径尽量短的情况下，线缆种群之间的共同路径尽量大。因此，适应度函数定义如下：

其中，Lic是单个线缆种群 Pic的长度，Cic是单个线缆种群 Pic与主干路径(某一代进化中首次进化的线缆种群的路径)重合的长度，也就是线缆种群间的共同路径长度，a和b(a+b=1)是两个权值变量。

按照上述的思想，当某个线缆种群在某一代中首次进化时，在计算出线缆路径后，将其作为整个分支线缆的主干路径。将主干路径进行分解，并将所有节点当作其他线缆的终点，以便其他线缆更多地通过。这就意味着其他线缆尽量向主干路径“靠拢”，使其重合的主干路径最大化，并拥有共同的目标点。通过式(3)求得主干路径上适应度函数最大点Mi，然后利用改进的RRT算法求解Mi与剩余端点间的路径。在允许的耗费下，使整体的耗费降至最低。如图11所示，分支线缆是由4个接插端子组成，包含3个线束AC、AD、BD，对应3个种群，每个种群独自进化生成的路径如图11(a)所示。假设线缆种群BD首先进化，并将首次进化的线缆生成的路径作为主干路径，算法将已求解路径的每个节点当作其他路径的目标点。假设下个进化的线缆种群是AC，按照式(3)计算得到适应度函数最大的节点M1为终点，利用改进RRT算法分别求解路径AM1、得到路径2作为最优路径。同理，AD线缆种群进化得到最优路径 3，最终的布局结果如图 11(b)所示。此时3条路径的组合拥有最大的公共路径，工艺优化，整体的耗费达到最小。图11(c)、图11(d)表示的是随着进化代数的增加、进化顺序的不同，可能得到的布局设计结果。

图11　协同进化得到的布局设计结果

4　实例验证

为了验证算法的可行性与布局质量，开发出了虚拟环境下的线缆自动布局设计原型系统，系统的开发与运行环境如表1所示。

表1　系统的开发与运行环境

该系统利用Spatial公司的三维显示/交互工具包 HOOPS建立三维环境，采用三维实体造型引擎 ACIS进行模型的读取与解析。其中结构件模型是在 Pro/E中完成，并通过数据转换接口导入到本系统中，而线缆模型则是利用 ACIS进行实体造型，并通过 HOOPS工具包进行显示或操作。测试模型采用卫星结构版模型，其中适应函数的参数 a=0.9，b=0.1，最大进化代数为 10。部分测试结果如图 12所示，其中线缆零件含有AB、AC两个线束。

图12　关键点拟合线缆测试效果

本节讨论取不同a、b值对布局设计结果的影响。每一组数据均通过 5次平均值计算得到，其中AB为主干路径的数据如表2所示，AC为主干路径的数据如表3所示。由表2、3可以看出，当主干路径确定时，随着a、b取值的变化，可导致分支线缆的公共路径长度以及总长度发生变化。分支线缆公共路径长度增加，会导致整个线缆的总长度增加。因此，a、b的取值需要根据线缆布局的实际情况而定，如果需要公共路径长度大，a取值可尽量小；反之，a取值尽量大，本文取值为a=0.9，b=0.1。当a、b值确定时，通过协同进化算法求解的最优主干路径的分支线缆总长度小于其他主干路径，也证明了此方法的可行性。

表2　AB为主干路径不同a、b取值对线缆长度的影响

表3　AC为主干路径不同a、b取值对线缆长度的影响

5　结　论

(1) 针对分支线缆的自动布局设计问题，提出了分支线缆的线束模型，准确表达分支线缆的结构以及内部连通信息；在此基础上提出了基于协同进化算法的分支线缆自动布局设计方法；开发了线缆自动布局设计原型系统，并进行了实例验证，证明了算法的可行性。

(2) 该方法考虑了部分工程约束，能够对分支点的位置进行寻优，得到较优的分支线缆的布局方案。

图13　不同情况下的分支线缆自动布局测试结果

(3) 实际中的线缆布局设计问题更加复杂，需要考虑更多的约束；本文方法很难求出布局的全局最优解，算法得到的线缆路径更可能是次优解或者是满意解，如何提高算法的效率并考虑多个复杂的分支线缆的布局优化等内容都将在以后的工作中进一步探索。

[1] 魏发远, 陈新发, 王峰军. 电缆虚拟布线及其逆运动学仿真[J]. 计算机辅助设计与图形学学报, 2006, 18(10): 1623-1627.

[2] 尚炜, 宁汝新, 刘检华, 等. 复杂机电产品中的柔性线缆装配过程仿真技术[J]. 计算机辅助设计与图形学学报, 2012, 24(6): 822-831.

[3] 王志斌, 刘检华, 刘佳顺, 等. 电缆虚拟布线中的物理特性分析与布局设计技术[J]. 计算机辅助设计与图形学学报, 2014, 26(7): 1193-1202.

[4] Conru A B. A genetic approach to the cable harness routing problem [C]//Proceedings of the IEEE Conference on Evolutionary Computation. Orlando, USA, 1994, (1): 200-205.

[5] 吴银锋, 吴兆华, 李春泉. 电子整机三维自动布线技术研究[J]. 电讯技术, 2005, 45(2): 76-81.

[6] 郭伟, 刘艳芳, 赵辉, 等. 基于骨架模型的快速布线方法[J]. 计算机集成制造系统, 2012, 18(11): 2391-2397.

[7] 徐本柱, 程光春, 李忠泽, 等．基于力导向算法的线束连接图自动布局研究[J]. 工程图学学报, 2010, 31(6): 171-177．

[8] 刘晓平, 李忠泽, 徐本柱, 等. 基于工程语义约束的线束预装配自动规划方法[J]. 图学学报, 2012, 33(5): 44-50.

[9] 朱吉满, 徐本柱, 凌欣南, 等. 汽车线束工艺工序及工序关系自动生成[J]. 图学学报, 2013, 34(2): 38-46.

[10] 王发麟, 廖文和, 郭宇，等. 复杂机电产品线缆信息本体表达与存储分析[J]. 图学学报, 2015, 36(3): 376-383.

[11] Park J H. Pipe-routing algorithm development for a ship engine room design [D]. Washington: University of Washington, 2002.

[12] Asmara A, Nienhuis U. Automatic piping system in ship [C]//5th International Conference on Computer and IT Applications in the Maritime Industries, Sieca Repro (TUD), Delft, 2006: 269-280.

[13] 樊江, 马枚, 杨晓光. 航空发动机外部管路自动敷设研究[J]. 机械设计, 2003, 20(7): 21-23.

[14] 封海波. 机械设备管路自动敷设设计方法的研究[D].哈尔滨: 哈尔滨工业大学, 2009.

[15] Liu Q, Wang C G. Multi-terminal pipe routing by Steiner minimal tree and particle [J]. Enterprise Information Systems, 2012, 6(3): 315-327.

[16] Ehrlich P R, Raven P H. Butterflies and plants: a study in coevolution [J]. Evolution, 1964, 18: 586-608.

[17] 刘静, 钟伟才, 刘芳, 等. 组织协同进化分类算法[J]. 计算机学报, 2003, 26(4): 446-453.

[18] 郑皎凌, 唐常杰, 徐开阔, 等. 基于协同进化的异构种群挖掘混沌迭代函数[J]. 计算机学报, 2010, 33(4): 672-686．

[19] LaValle S M, Kuffner J J. Rapidly-exploring random trees: progress and prospects [C]//Algorithmic & Computational Robotics New Directions. Wellesley MA: A K Peters Ltd, 2000: 293-308.

[20] Zhu D, Latombe J C. Pipe routing=path planning (with many constraints) [C]//Proceedings of the 1991 IEEE International Conference on Robotics and Automation. Sacramento, California, 1991, (3): 1940-1947.

[21] 尚炜. 复杂产品线缆数字化布局设计与装配仿真技术[D]. 北京: 北京理工大学, 2012.

Branch Cable Automatic Routing Based on Co-evolutionary Algorithm

Xu Jinbao,Liu Jianhua,Liu Jiashun,Liu Xiao

(School of Mechanical Engineering, Beijing Institute of Technology, Beijing 100081, China)

Facing the problem that the middle forked point is difficult to determine which exists in the branch cable routing, a branch cable automatic routing method is proposed based on co-evolutionary algorithm. Firstly, the branch cable harness model is established. The approach divides the whole system of branch cable into a few single cables based on the cable harness model, and every single cable represents a population. Improved RRT (rapidly-exploring random trees, RRT) algorithm is used to obtain initial path of every single cable. Then middle forked points is optimized based on the idea of co-evolution, which is affected by other single cables during its evolution, and the branch cable routing optimized obtained. Finally, the final optimization of path points obtained were fitted to obtain the cable as a result. A 3D automatic routing prototype system is developed and some experiments are applied to verify the efficiency of the method.

branch cable; automatic routing; co-evolutionary algorithm; rapidly-exploring random tree algorithm

TP 391.9

10.11996/JG.j.2095-302X.2016010025

A

2095-302X(2016)01-0025-09

2015-09-24；定稿日期：2015-10-11

国家自然科学基金项目(51275047)；国防基础科研项目(A2220110008)；总装预先研究项目(51318010102)

徐金宝(1989–)，男，安徽安庆人，硕士研究生。主要研究方向为分支线缆自动布局设计技术。E-mail：xujb_1989@163.com

刘检华(1977–)，男，江西萍乡人，教授，博士，博士生导师。主要研究方向为数字化装配与检测。E-mail：jeffliu@bit.edu.cn