郭学鹏，朱永国+，王发麟，宋利康，陈大伟

(1.南昌航空大学 航空制造工程学院，江西 南昌 330063； 2.江西洪都航空工业集团有限责任公司 经理部，江西 南昌 330024； 3.辽阳海关，辽宁 辽阳 111000)

0 引言

线缆作为传输电流和信号的介质，广泛使用在汽车、飞机、武器装备、雷达、卫星等各类复杂机电产品中[1]。在复杂机电产品的布线工艺规划过程中，由于线缆的种类和数量众多，产品内部工件复杂，导致线缆布线繁琐、易反复，因此产品中线缆的布线顺序已成为影响产品装配的一个重要因素。在线缆布线顺序规划方面，尚无一套可供操作，完善且科学的研究方法。传统的线缆布线方法是在实物样机的基础上，依据工人经验、参考设计接线表来完成线缆布线。布线开敞性不足，工人布线经验要求高等不利因素导致线缆布线顺序不合理，降低了布线质量，增加了制造成本，延长了研制周期。因此，研究一种有效的线缆布线顺序规划方法，对提高线缆布线质量和优化产品装配工艺具有重要的意义[2]。

Conru等[3-4]提出一种并行工程的方法来进行线缆布线设计，并采用遗传算法来求解线缆布线的全局最优位置;Hermansson等[5]针对线缆布线路径规划中易变形等问题，提出一种低维线缆布线路径规划算法，用于自动规划和寻找线束安装中的连接器的平滑且无碰撞的安装;王金芳等[6]基于Pro/E平台，开发了线缆装配工艺规划原型系统，研究了线缆分支装配顺序和线缆分支路径规划;王发麟等[7]针对电磁场会干扰线缆敷设顺序的现象，提出一种多尺度混沌变异粒子群算法的线缆敷设路径求解方法;刘潇等[8]提出基于扩展碰撞信息的路径优化方法，对线缆初始布线路径进行优化。张丹等[9]针对航天产品装配序列规划的多目标和非线性的特点，将粒子群算法和遗传算法进行结合;居露等[10]利用线束装配工艺信息建立线束装配空间约束矩阵，并结合改进遗传算法进行线束装配序列规划。上述研究为线缆布线顺序规划提供了一定的技术基础，但线缆布线顺序规划作为非确定性多项式(Nondeterministic Polynomial，NP)难题[11]，已有研究还存在以下2点不足：①只针对线缆敷设路径或线缆干涉等进行研究，未见线缆布线顺序规划方面的研究;②只研究了纯刚性结构件的装配序列规划问题，未涉及到复杂结构产品线缆的布线顺序规划。

近年来虚拟装配技术的出现为解决线缆装配工艺规划问题提供了方便。虚拟装配技术可在无实物样机的情况下对产品装配工艺规划进行分析、预测和规划，并实现对装配工艺的仿真与优化[12]。Caudell是第一个提出将虚拟装配和线缆布线相结合的学者，其利用增强现实技术对线缆布线进行仿真[13];Ng等[14]针对一般CAD系统使用人工智能进行线缆自动化或者半自动化布线效率低等问题，在虚拟环境中开发了一套沉浸式的人机交互布线系统，并检验了其布线效率;Robinson等[15]开发了一套沉浸式线缆布线设计系统Co-Star，并进行了一系列的前期测试和验证，提高了线缆设计的精确度和效率;高纪开达等[16]认为线缆是空间中一系列截面中心点相连而成的连续折线段，并利用虚拟装配的特点，提出了基于离散控制点的线缆建模技术;王志斌等[17]在考虑柔性线缆的物理特性、静态位姿、弯曲变形等特点的基础上，在虚拟环境下进行了电缆布局设计。

综合以上分析，为克服传统线缆布线方法效率低、易反复的不足，本文在基于虚拟装配技术的线缆布线研究的基础上，提出一种基于个体扰动变异粒子群优化(Individual Disturbance Mutation Particle Swarm Optimization，IDMPSO)算法的线缆布线顺序规划方法，开发了线缆布线顺序规划原型系统，并通过标准测试函数和实例对算法进行了测试和验证。

1 线缆布线顺序数学模型构建

1.1 线缆虚拟装配

线缆虚拟装配是在虚拟环境下以柔性线缆为基础，利用虚拟现实技术、人工智能、可视化技术、决策理论和仿真等技术，通过人机交互的方式在计算机上对线缆布线进行分析与仿真的全过程。线缆虚拟装配技术不仅能够检验、评价和预测线缆的可布线性和整体布线性能，还能对线缆的布线顺序、布线路径和布线方法等问题进行分析和决策。线缆虚拟装配技术对提高线缆设计质量，缩短产品设计和制造周期具有重大意义[18]。线缆虚拟装配的主要内容如图1所示。

1.2 线缆布线顺序可行性数学模型构建

线缆布线顺序可行性评价数学模型包括线缆干涉数学模型和线缆布线过程流畅性数学模型2个模型

(1)线缆干涉数学模型构建

产品装配序列规划中，碰撞干涉分析是一个无法避免的关键问题，如何有效地避免零部件之间的碰撞干涉是获得产品合理装配序列的前提和基础。线缆作为柔性零件，在受到外力作用时容易发生变形和接触不良等问题，因此，在布线时更需要考虑空间干涉问题。本文从两个方面来分析线缆布线顺序的空间干涉问题：①线缆碰撞干涉分析；②线缆与电连接器之间固定方式所采用工具的可操作性。

1)线缆碰撞干涉分析Ni。

线缆碰撞干涉主要包括线缆与线缆之间的碰撞干涉、线缆与刚性结构件的碰撞干涉。其中，线缆与刚性结构件的碰撞干涉在线缆布线路径设计中已经考虑，故本文的线缆布线顺序规划中只考虑线缆与线缆之间的碰撞干涉。依据线缆装配工程实际，将线缆进行分组。定义各线缆组之间的干涉矩阵如下：

p1p2p3…pn

(1)

其中：pi为第i组线缆，n为线缆组数量，i、j≤n；aij为线缆组pi与线缆组pj之间的干涉情况，当aij=aji=0时，表示线缆组pi与线缆组pj之间不存在干涉，且规定i=j时，aij=0；当aij=aji=1时，表示线缆组pi与线缆组pj之间存在碰撞干涉。设线缆组pi为未装线缆，i>1,则线缆组pi对于已装线缆序列P*={p1,p2,…,pk,…,pi-1}的干涉情况为：

(2)

式中Pi为线缆组pi对于已装线缆序列P*={p1,p2,…,pk,…,pi-1}的干涉情况。当Pi=0时，表示线缆组pi对于已装线缆序列P*={p1,p2,…,pk,…,pi-1}没有干涉；当Pi=1时，表示线缆组pi对于已装线缆序列P*={p1,p2,…,pk,…,pi-1}存在干涉。

将任意产品线缆布线顺序记为P={p1,p2,…,pi,…,pn}，n为线缆组号，建立其线缆与线缆之间的干涉数学模型：

(3)

式中Nnci为线缆布线序列P的干涉次数。Nnci越大，表示干涉次数越多，线缆布线序列P不合理；反之，表示干涉次数越少，线缆布线序列P越合理。

2)线缆与电连接器之间固定方式所采用工具的可操作性。

(4)

式中：Ti为第i组线缆与电连接器的连接中采用固定工具的操作空间情况；Nfto为在线缆布线顺序P中，固定工具操作空间不足的次数。

结合以上分析，对于任意线缆布线序列P，建立线缆干涉数学模型如下：

fitf=Nnci+Nfto。

(5)

式中fitf表示P对于Nnci与Nfto的干涉情况。Nnci或者Nfto越大，fitf也越大，线缆布线序列P的干涉次数越多，说明布线序列有待改进；Nnci与Nfto越小，线缆布线序列P的干涉次数越少，说明规划的布线序列比较合理。

(2)线缆布线过程流畅性数学模型构建

1)线缆布线长度模型Nccl：

(6)

式中：Nccl为线缆布线长度分析模型，在线缆布线顺序P中，应该遵循先布短线，后布长线的原则来进行布线；Li为在线缆布线顺序P中，pi与pi+1之间的长度比较，若li>li+1，则Li=1，表示P存在一次不合理的线缆布线，通过对P的求和计算，即可求得P中存在不合理的线缆布线次数。Nccl越大，线缆布线序列P的不合理次数越多，说明布线序列有待改进；Nccl越小，线缆布线序列的不合理次数越少，说明规划的布线序列比较合理。

2)线缆布线空间整体位置模型：

(7)

综合以上分析，对于任意线缆布线顺序，建立线缆布线过程流畅性数学模型如下：

fflu=Nccl+Nsdr。

(8)

式中fflu为线缆布线顺序的流畅程度。fflu越大，线缆布线序列P的流畅度越差，说明布线序列有待改进；fflu越小，线缆布线序列的流畅度越好，说明规划的布线序列比较合理。

2 基于IDMPSO算法的线缆布线顺序规划

2.1 粒子群算法在线缆布线顺序中的离散化

粒子群优化(Particle Swarm Optimization, PSO)算法是一种群体智能优化算法，能够很好地解决线缆布线顺序规划这种NP难题[20-21]。基本PSO算法在迭代过程中，其速度和位置更新公式为：

(9)

(10)

线缆布线顺序规划是一种整数离散化问题，而基本粒子群算法的位置与速度是实值计算，不适合线缆布线顺序规划。为此，本文对基本粒子群算法进行离散化，重新定义粒子的位置、速度以及粒子之间的更新操作和运算。

定义1粒子位置。粒子的位置表示线缆各组号之间的排列，第i个粒子的位置为Xi=(xi1,xi2,…,xid,…,xin)，其中xid∈{1,2,…,n}为线缆组的编号。

定义2粒子速度。线缆各组号之间的排列通过粒子速度来更新。种群中第i个粒子的速度矢量为Vi=(vi1,vi2,…,vid,…,vin)，其中vid∈{1,2,…,n}，为粒子i速度矢量的第d维元素，表示粒子i中xid对应的速度，当vid≠0时，表示线缆xid在Xi中的排列位置需要发生改变。

定义4粒子相互位置的减法。两个粒子位置相减产生一个新速度，设X1=(x11,x12,…,x1d,…,x1n)，X2=(x21,x22,…,x2d,…,x2n)，则定义Vi=X2ΘX1，其中Vi为一个新速度，Vi的求解方法为：若x1d=x2d，则vid=0；若x1d≠x2d，则vid=x2d。

定义5粒子速度的加法。重新定义粒子速度的加法Vk=Vi⊕Vj，其中，Vk的求解方式如下：

(11)

式中r为分布于[0,1]区间的随机数。

定义6粒子速度的乘法。重新定义粒子速度的乘法Vj=c⊗Vi，c∈[0 1]，Vj表达式的值为：

(12)

式中r为分布于[0,1]区间的随机数。

定义7粒子位置和速度更新。重新定义粒子位置和速度更新：

(13)

(14)

式中c1、c2、r1、r2为分布于[0,1]区间的随机数。

2.2 IDMPSO算法目标函数

以线缆干涉、线缆布线过程流畅性为约束，设计IDMPSO算法目标函数。层次分析法(Analytic Hierarchy Process, AHP)[22]是决策者对复杂、模糊问题做出决策并确定复杂、模糊问题中各影响因素权重的一种方法，为此本文采用AHP法对3个影响因素进行权重的确定。通过层次分析法对线缆布线顺序可行性因素集的决策，求解出IDMPSO算法的目标函数：

F=0.473 4×fitf+0.526 6×fflu

=0.473 4×(0.5×Nnci+0.5×Nfto)+

0.526 6×(0.5×Nccl+0.5×Nsdr)。

(15)

式中：fitf、fflu分别表示线缆布线干涉模型、线缆布线过程流畅性模型；0.473 4表示线缆布线干涉因素对线缆布线顺序的影响程度；0.526 6表示布线过程的流畅程度对线缆布线顺序的影响程度。系数越接近1，说明该约束对线缆布线顺序的影响程度越大；反之，则该约束对线缆布线顺序的应先程度越小。

2.3 基于个体扰动变异的粒子群算法

PSO算法在迭代寻优过程中，粒子群中其他粒子会向某一个找到当前最优位置的粒子靠拢，当该粒子发现当前最优位置不是全局最优位置，即局部最优解时，粒子群会因为“惰性”不会继续在解空间内搜索，因而使算法陷入局部最优并出现早熟现象。针对这一不足，本文在基本粒子群算法的基础上，在算法中对粒子进行干扰和变异，以提高粒子的寻优能力，避免算法发生早熟现象。首先，利用混沌搜索机制生成不同的混沌变量对微粒进行干扰，生成新的微粒，以提高算法的搜索精度；然后，利用变异机制以一定的概率对新微粒进行变异操作，避免算法过早陷入局部最优。

(1)基于混沌搜索机制的微粒干扰

粒子的混沌搜索具有极度敏感性、遍历性、规律性等特点，能够使部分微粒跳出局部最优并保持种群的多样性。产生混沌变量的模型有Lozi映射、Logistic映射、Ushiki映射和Sinusoidal映射。Logistic映射具有计算复杂度低,实现简单等优点，适合于对IDMPSO算法微粒进行干扰，采用Logistic映射来产生混沌变量，混沌每次迭代都能产生不同的新解，且产生的混沌变量遍布于整个解空间，具有很大的随机性。Logistic映射函数定义如下：

(16)

(2)微粒变异

通过计算种群适应度方差σ2能够较好的判断算法是否发生早熟现象。对于种群容量为M的种群，定义该种群适应度方差

(17)

式中：fi为第i粒子的适应度值;favg为当前种群平均适应度值。

种群适应度方差σ2能够反映种群的聚集程度和种群多样性，σ2越大，种群多样性越大，σ2越小，种群多样性越小。当σ2=0，表示种群多样性消失，种群陷入局部最优或者找到全局最优解;当σ2

2.4 IDMPSO算法流程

通过对标准粒子群算法的整数离散化，结合个体扰动变异思想，得到IDMPSO算法的详细步骤(如图2)：

步骤1初始化。设置算法参数ωmax、ωmin、c1、c2、最大迭代次数Tmax、混沌迭代次数Gcmax、种群容量M和理论阈值gm。

步骤2初始化种群速度V，种群位置P，初始化种群迭代次数T1=1。

步骤3计算种群中各粒子适应度值fi、种群平均适应度值favg和种群适应度方差σ2。

步骤4判断适应度方差σ2与理论阈值gm的大小，若σ2

步骤5在初始化的种群中选择0.2×M个适应度值较差的粒子作为混沌变异的新种群N，初始化混沌迭代次数g=1。

步骤10令g=g+1，判断g与Gcmax的大小。若g

步骤11找到种群中个体最优值Pbest和全局最优值Gbest。

步骤12计算新种群最小适应度值fmin、最大适应度值fmax和平均适应度值favg，并根据公式对惯性权重ω进行更新。

步骤13根据式(13)和式(14)更新粒子(布线顺序)位置和速度。

步骤14种群迭代次数T1=T1+1，并判断T1与Tmax的大小，若T1

步骤15输出最佳布线顺序和最佳适应度值，算法结束。

3 实例验证

为验证IDMPSO算法的效果，以某型相控阵雷达为研究对象，对雷达内部空间中的线缆进行布线顺序规划。如图3所示，在相控阵雷达模型中，共有17组柔性线缆，每一组线缆数量各不相同，且线缆交错排布于各刚性结构件之间。相控阵雷达由于内部空间复杂，包含各种电子部件、元器件和柔性线缆，且线缆与电子部件、元器件紧密的连接在一起，造成雷达内部空间十分狭小，使得线缆在布线时操作困难。因此，为解决上述线缆布线的难点问题，需要一个合理的线缆布线顺序来指导布线工人对雷达内部线缆进行布线。

依据构建的线缆布线顺序数学模型和IDMPSO算法，对CREO 2.0平台进行二次开发，开发出线缆布线顺序规划功能模块。该功能模块主要由对话框资源文件和相应的控制程序两大部分构成。对话框资源文件的内容定义了对话框的组成、外观和属性。控制程序由Microsoft Visual Studio 2010通过C++编程实现，用来在CREO/TOOLKIT环境嵌入对话框资源、显示对话框、设置动作和退出对话框等。如图4所示为IDMPSO算法开发的线缆布线顺序规划功能界面。

在运用算法进行线缆布线顺序求解之前，需要利用开发的线缆布线顺序规划功能模块自动获取线缆信息系和电连接器信息，然后对模型线缆信息进行分组处理，如图5所示。在实例计算中，设置如下算法参数：ω采用非线性的动态惯性权重系数，ωmax=0.9，ωmin=0.4；学习因子c1、c2取值均为2；种群规模N=40；算法最大迭代次数Tmax=1 000，混沌迭代次数Gcmax=20；理论阈值gm=0.8；统计50次试验运行结果。算法运行结果如图6和图7所示，从图7中可以看到，算法最佳适应度值在第600代左右收敛于最优解17.167，并一直稳定在该值。从图6中可得，算法在收敛后，求出的最佳布线顺序为P={15-14-16-17-10-1-2-8-9-3-4-13-5-6-7-11-12}。

为进一步验证本文IDMPSO算法在求解线缆布线顺序的可行性与优越性，在保证布线模型、目标函数以及算法相关参数不变的情况下，将IDMPSO算法与基本PSO算法进行比较，分析两种算法在运行50次试验时求解线缆布线顺序时得到的最优布线顺序次数、算法平均寻优时间、以及最优适应度值之间的关系，如表1所示。从表1中可以得出，随着种群容量的增加，两种算法能够求得的可行布线序列也随着增加，但是无论种群容量为40、60还是100，本文IDMPSO算法得到的可行布线序列总是比基本PSO算法得到的多，说明本文改进的IDMPSO算法的寻优能力比基本PSO算法强；其次，算法的平均运行时间随着种群容量的增加而增加，但总体而言，IDMPSO算法由于引入的个体扰动变异思想，其平均运行时间比基本PSO算法稍长，但其运算时间均在可接受范围之内；最后，本文IDMPSO算法得到的最佳适应度值均比基本PSO算法小，说明在求解线缆布线顺序时，本文IDMPSO算法求解的线缆布线顺序更合理、可行。综上所述，本文所提方法和算法能求解出一套较为合理的线缆布线顺序，对相控阵雷达这种内部空间紧密、操作不便的机电产品的线缆布线过程中，有很好的指导作用。

表1 两种算法实验结果对比

4 结束语

利用线缆虚拟装配技术，在虚拟环境下构建线缆布线顺序可行性数学模型，确定影响线缆布线顺序的因素，为求解算法适应度函数打下基础。针对基本粒子群算法实值运算，且容易陷入局部最优解和早熟收敛等缺点，在基本粒子群算法的基础上对算法进行整数离散化，同时引入个体扰动变异搜索机制对算法进行改进，提高了算法的全局搜索能力和局部寻优能力。以某型相控阵雷达为例，将本文所提算法应用于线缆布线顺序规划过程中，证明了本文所提个体扰动变异粒子群算法的优越性。对于复杂机电产品的线缆敷设顺序规划，由于产品内部结构的复杂性以及线缆敷设顺序需遵循的规则较多，为提高产品线缆敷设效率，在后续研究中需要考虑更多的敷设顺序约束条件和敷设规则，以适用于多约束、多规则产品的线缆敷设顺序规划。