基于改进粒子群算法的多分支电缆自动布线技术

刘召朝，张丹，周琛，左敦稳

(南京航空航天大学 机电学院，江苏 南京 210016)

0 引言

在机电一体化设备中电缆负责电气元件的能量输送与信号控制。在复杂机电产品中电缆被大量使用[1]。不合理的电缆布局会破坏系统的稳定性，导致产品故障率上升，如发动机空中停车故障事件有50%是由于管路、电缆和传感器损坏导致的[2]。在复杂机电产品电气系统中存在许多单根电缆和多分支电缆，单根电缆路径优化使用简单的路径搜索算法即可完成，多分支电缆布局优化往往被视为三维空间下路径和结构的组合优化问题[3]。属于典型避障Steiner最小树(SMT)的NP困难问题[4]。随着人工智能技术的发展，智能优化算法如遗传算法[5]、蚁群算法[6]等，可有效地求解Steiner最小树问题。本文基于改进粒子群算法针对面向多分支电缆的Steiner最小树问题进行优化，自动生成满足实际工程应用的电缆布局方案。

1 多分支电缆布局优化模型

1.1 基于SMT的多分支电缆优化问题

如图1所示，多分支电缆布局与SMT问题相似，可将其转化为SMT问题求解，但二者之间也存在以下差异：

1) 多分支电缆中端子要经多个分支点才到达另一端，而SMT中各点之间可直接相连。

2) SMT中Steiner点必须关联三条夹角为120°的边，而多分支电缆设计中分支点连接的端子数量不止3个，故分支路径的夹角存在多种形式。

3) 多分支电缆中只连接一个接线端子的分支点相当于一个路径点，可以将其删除。

基于上述分析，将分支电缆布局设计抽象为特殊的SMT进行优化，对其做如下规定：顶点关联的边有且只有一条；……