基于改进多头绒泡菌算法的布线空间预处理技术

摘 要：随着机电产品中线缆布局设计难度的提高，布线设计自动化成为研究热点，其中首先需要根据产品结构获得离散化的搜索空间。为解决当前空间离散化时普遍存在的空间降维难题，提出基于多头绒泡菌算法的空间预处理技术，根据布线敷设工艺要求建立初始离散空间，设计基于工艺约束的黏菌网络流运动规则和网络收敛策略；基于改进的多头绒泡菌算法对初始离散空间进行降维处理，获得布线空间离散模型，通过实例验证了所提方法的有效性。

关键词：自动布线；空间预处理；多头绒泡菌算法

中图分类号：TP391.9文献标志码：A文章编号：1671-5276（2024）03-0132-05

Wiring Space Pre-processing Technology Based on Improved Physarum Algorithm

Abstract：With the increasing difficulty of cable layout design in electromechanical products， the automation of wiring design has become a research hotspot. The first step in automatic wiring is to obtain a discrete search space according to the product structure. Aiming at the ubiquitous problem of space dimensionality reduction in the current space discretization， this paper proposes a space pre-processing technology based on the physarum algorithm. The initial discrete space is established according to the requirements of the wiring laying process， and the slime mold network flow movement rules and network convergence strategy are designed based on process constraints. The initial discrete space is reduced in dimension by the improved physarum algorithm， and the discrete model of wiring space is obtained. Experiment examples verify the effectiveness of the proposed method.

Keywords：auto wiring; spatial pre-processing; physarum algorithm

0 引言

在航空航天机电产品中，线缆起着电子设备间通信与能量传输的作用，其特点是种类众多、布线密度大、敷设空间小等［1］。随着航空航天设备向着高度集成化发展，布线环境变得日趋复杂，线缆布局设计难度大大提升，布线设计效率成了亟需解决的问题。目前线缆布局的主要研究方向是自动化布线［2］：通过对布线环境的空间预处理，把三维连续空间转化为可供算法计算的离散空间；再使用智能优化算法求解线束路径与拓扑结构。这其中，布线空间离散化模型的有效降维对线束布局的求解效率与质量有着重要影响。

目前针对空间离散化模型的降维技术主要有八叉树法［3］、混沌栅格法［4］以及3D连接图［5］等。但上述方法存在降维性能不足、适用性低、构建方式复杂等问题，无法保证为后续布线算法提供高效的搜索空间。针对以上问题，本文提出基于多头绒泡菌算法改进的栅格预处理模型，以算法的网络优化能力在保留空间重要节点的同时对布线空间进行有效精简，同时基于布线工艺约束对算法做出改进，提高预处理方法的适用性。

1 面向布线问题的多头绒泡菌模型

1.1 离散布线空间模型

线缆的布局设计通常以离散布线空间为基础，在一定工程约束下通过布线优化算法求得合理的线束分支结构与走线路径。其中离散布线空间可看成由离散点与离散点间的连通关系构成的网络，每个离散点记录相应位置的工艺属性与坐标信息。为保证布线环境信息的完备性，布线空间模型的离散点规模通常十分庞大，这对于布线优化算法的求解效率和质量会产生不利影响。相反，若盲目地简化模型，则容易导致优质解的丢失。因此布线规划需要同时考虑空间降维与关键节点的保留。

1.2 多头绒泡菌模型

在一次生物实验中，TERO等［6］发现多头绒泡菌具有构建最短网络的生物智能。它在觅食时能将自身形态转变为连接各个食物源的最短网络。 研究人员通过分析它的生物特性，建立了多头绒泡菌数学模型（以下简称PMM）。

PMM将该菌的觅食网络看成是节点与原生质管道的集合。每个节点vi具有各自的压强pi，每条原生质管道ei，j具有管道长度Li，j、导通性Di，j、流量Qi，j等属性。基于泊肃叶定律，其各属性间的关系如式（1）所示。

在PMM中，通过设置源节点vs与汇节点ve来表示食物源位置，根据基尔霍夫定律，从源节点流入的初始流量Io会全部从汇节点流出，如式（2）所示。

式（1）与式（2）刻画了原生质管道中流体的流动规律，而管道的导通性Di，j会随着流量Qi，j自适应地变化，其变化规律如式（3）所示。

式中：f（|Qi，j |）为单调递增函数，满足f（0）=0，它表示下一时刻导通性的增长量；δ为管道的衰减率；δDi，j代表管道下一时刻的衰退量。在网络优化中，f（|Qi，j |）采用式（4）会有更好的效果。

初始化网络后，在时间间隔t下可通过式（2）确定各节点压力p，再由式（1）算出当前各管道内的流量Qt。Qt通过式（3）作用到Dt+1，重复上述步骤，将导通性D小于阈值的边删除，网络将最终收敛到连通各食物源节点的最短路径。

PMM能根据食物源的相对位置收缩冗余路径，强化连通食物源的最短路径，这一生物特性对布线空间离散点的简化具有启发意义，两者的映射关系如图1所示。其中觅食环境中的食物源类比于布线环境中的接线端口，黏菌的原生质管道即离散点间的连通路径，黏菌的避光性对应于线缆布局时需远离热源与电磁源的原则。将该方法运用到布线空间预处理中，能有效降低空间维度与复杂度，缩小后续优化算法的探索空间。

2 基于PMM改进的布线空间模型

基于PMM算法的布线空间模型创建分为3个阶段，其流程如图2所示。首先是初始规划阶段，根据布线空间尺寸创建栅格连通图，依托特殊组件位置信息设置离散点的工艺属性。第2步为PMM算法运行阶段，根据工艺约束的引导强化可布线区间内边的导通性，引入冗余点的概念提高算法效率。第3步为离散单元精简阶段，以各边导通性均值DAvg过滤大量节点，以更新后的栅格连通图作为最终的布线空间模型。

2.1 栅格连通图的创建

PMM是基于图的网络优化，因此需要将空间数据模型以图的形式构建出来。本文采用均匀栅格划分布线空间，结合线束敷设工艺赋予每个离散单元属性值并创建邻接关系。具体步骤如下。

步骤1：确定布线空间边界长度以及特殊组件与端口的位置。以最粗线缆的最小弯曲半径为栅格间距，均匀划分三维布线空间，以栅格单元中心点作为节点，创建点集V。

步骤2：根据栅格单元与障碍物边界的距离，设置节点属性值贴壁点集Vw、浮空点集VS以及障碍点集Vo，将距离接线端口最近的节点设置为端口点集Vp。

步骤3：将除障碍点集Vo外的所有点按空间6个方向进行邻域连通，构成边集E。

步骤4：以电气元件和发热元件为几何中心构建干扰区域，将该区域内的点所构成的边标记为干扰边集Et，根据干扰信号强弱计算每个节点的工艺信息值。

步骤5：由贴壁点构成的边标记为贴壁边集Ew，若Ew内的边属于Et，则不改变边的属性。

通过上述过程产生的栅格连通图，满足多头绒泡菌优化网络的计算需求并将空间几何信息与工艺信息有机结合，有利于后续优化算法的求解质量。图3为节点数据的层次结构。

2.2 基于工艺约束的黏菌网络流运动规则

传统PMM解决的是无约束情况下的网络寻优问题，而实际布线环境中存在多种工艺约束，这些约束将影响线束布局的走向，因此利用PMM对离散单元进行简化时应充分考虑这些因素。本文提出两项规则来模拟实际布线环境下的工艺约束，进而影响黏菌网络流的运动方向，使之沿着更符合布线条件的路径流动。

规则一：源汇节点动态更新规则

机电产品中常见的是多分支线缆结构，通常由某一端口伸出的线缆需要经过多个分支点才能到达目标端口。而传统的PMM只考虑网络间的最短距离，每次计算时只选取一对源汇节点进行迭代更新，缺少全局性考虑，可能会造成潜在优质分支点的遗失。鉴于此，本文的源汇节点动态更新规则如下。

1）在每一次迭代过程中，从端口点集VP中按序选择一节点为源节点vs，点集VP中其余节点均设置为汇节点ve，从源节点流入的流量将均匀地从汇节点流出。将式（2）替换为

2）布线模型中可能存在专为布线预留的结构空间，根据其机械结构特征，可人为设置分支点位置，将其加入端口点集Vp中，使得合理的布线空间最大限度地保留。

规则二：基于工艺约束的导通性变化规则

线缆在敷设过程中倾向于贴壁敷设，且要绕开热源、电磁源的干扰。因此需要在PMM收敛的过程中加入新的约束条件。本文对在热源与电磁源影响范围内的边集Et与贴壁边集Ew的导通性公式做出修改：

Dt+1i，j=f（Qi，j）－δDti，j+λG（ei，j）（6）

式中：ei，j为节点i，j之间的边；λ为修正系数；函数G（ei，j）的主要作用是通过增减节点流量的方式保留更适合布线的离散单元，其增减量如式（7）所示。

式中：DAvg表示上一时刻所有边导通性的均值；nw与nt分别表示边集Ew与边集Et中的边数。

2.3 加速策略

为了加速算法收敛，本文参考文献［7］中冗余边与冗余点的概念，在迭代过程中加入删减节点的操作。栅格连通图中的冗余边可定义为导通值小于自设阈值的边，在图4中以虚线表示，它将在迭代过程中删除。初始离散空间中，单个节点会有6条连通边，如图4中V1所示。随着冗余边的删除，会出现两类冗余点的情况。

第一类冗余点：只有两条连通边的节点，且两条连通边处于同一直线上，如节点V2。此类点的存在不会对最终结果造成影响，因此可以保留节点信息，将它的两条连通边合并为一条。通过这样的方式减少算法的计算量。

第二类冗余点：仅有一条或没有连通边的节点，如节点V3与节点V4，此类点与网络间的连通关系太少，因此可以不保留节点信息直接删除。

2.4 离散单元精简策略

栅格连通图中含有大量节点，为了在少量的迭代次数下快速精简节点数量。本文以端口点集数|Vp|作为最大迭代次数，在PMM迭代结束时以各边平均导通值DAvg为基准，提取导通值大于DAvg的边集，再以构成这些边集的节点作为最终留存的离散点集。

3 性能评价方法

为了全面地评估预处理技术的性能，本文综合考虑布线模型对实际布线空间的覆盖率、表述性以及对布线算法的搜索效率、搜索精度等多个因素的影响，建立布线空间模型的性能评估指标体系，如图5所示。结合文献［8］中的改进雷达图法对布线空间模型进行直观、定性的评价。

4 实例分析

本文对两种不同结构特征的机电模型进行测试，如图6所示。图6（a）为机舱模型，其特点是空间开敞、零部件分布间距大，应着重考虑空间降维因素。图6（b）为卫星模型，属于封闭空间，工艺约束较多，对空间模型的开敞性要求更高。两者的各项指标权重如表1所示。

目前常用的布线离散空间模型有八叉树法与Escape法，因此本文选取这两种方法与PMM改进的栅格预处理法进行对比分析。基于表1中的权重参数，各项指标值经过正向化与标准化处理后，得到的性能评价结果如图7与图8所示。3种预处理方法构建的布线空间模型如图9所示。

分析雷达图可知，在降维性方面，PMM改进的栅格法在两种模型中的表现最好，这得益于离散点的精简策略。而Escape法在两模型中的降维性表现却是相反的，主要原因是Escape法是根据模型几何平面与障碍物的交点构建的，其交点数量取决于模型的复杂程度。在开敞性与代表性方面，八叉树法要优于另外两种方法，原因是八叉树采用不均匀的空间划分方式，提高了狭窄空间与开敞空间的连通性，且不均匀的离散单元对空间的覆盖率更高，更具代表性。而PMM改进的栅格法在精简空间时牺牲了一定数量的离散单元，空间代表性较差，但在开敞性方面表现良好。在算法稳定性与预处理效率上，三者的差异并不明显。综上，采用PMM改进的栅格法能有效降低空间维度，且有较好的综合性能表现。

为进一步验证预处理方法的有效性，本文以粒子群算法作为布线优化算法，得到的分支线缆结构如图10所示，性能分析结果如表2所示。分析可知，基于PMM改进的栅格预处理法得到的线缆组件结构最优，且算法运行时间最短。这主要归结于PMM通过全局遍历的方式将大量冗余离散单元删去，缩小了最优解的搜索范围，使粒子群算法步入局部最优的可能性减小，且降维后的求解空间更有利于算法的搜索效率。因此基于PMM改进的栅格预处理法具有一定的优越性。

5 结语

针对现有布线离散空间普遍存在的降维难题，本文基于改进的多头绒泡菌算法对离散空间进行降维处理，通过实例验证了所提方法的有效性。

参考文献：

［1］ 骆飞平，韩冰，杨锋，等. 飞机线缆自动检测系统布局优化设计研究［J］. 测控技术，2019，38（11）：9-19.

［2］ ZHANG D，LIU Z C，ZHOU C，et al. Multi-objective layout optimization of aircraft multi-branch cable harness based on MOPSO/D［C］//2021 12th International Conference on Mechanical and Aerospace Engineering （ICMAE）. Athens，Greece： IEEE，2021：139-144.

［3］ 耿琪，张丹，刘召朝，等. 面向机电产品布线规划的空间预处理技术［J］. 航空精密制造技术，2019，55（3）：25-30.

［4］ 付宜利，封海波，孙建勋，等. 基于混沌算法的机电产品管线自动敷设研究［J］. 计算机集成制造系统，2007，13（3）：497-501.

［5］ QU Y F，JIANG D，YANG Q Y. Branch pipe routing based on 3D connection graph and concurrent ant colony optimization algorithm［J］. Journal of Intelligent Manufacturing，2018，29（7）：1647-1657.

［6］ TERO A，TAKAGI S，SAIGUSA T，et al. Rules for biologically inspired adaptive network design［J］. Science，2010，327（5964）：439-442.

［7］ WANG D，ZHANG Z L. A novel physarum-based optimization algorithm for shortest path［M］//Lecture Notes in Computer Science. Cham：Springer International Publishing，2021：94-105.

［8］ 程宝鹏， 方洋旺， 彭维仕， 等. 基于雷达图法的群智能算法综合性能评估［J］. 北京航空航天大学学报：2022： 1-14.