基于改進多頭絨泡菌算法的布線空間預處理技術

摘 要：隨著機電產品中線纜布局設計難度的提高，布線設計自動化成為研究熱點，其中首先需要根據產品結構獲得離散化的搜索空間。為解決當前空間離散化時普遍存在的空間降維難題，提出基于多頭絨泡菌算法的空間預處理技術，根據布線敷設工藝要求建立初始離散空間，設計基于工藝約束的黏菌網絡流運動規則和網絡收斂策略；基于改進的多頭絨泡菌算法對初始離散空間進行降維處理，獲得布線空間離散模型，通過實例驗證了所提方法的有效性。

關鍵詞：自動布線；空間預處理；多頭絨泡菌算法

中圖分類號：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.