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

關(guān)鍵詞：自動布線；空間預(yù)處理；多頭絨泡菌算法

中圖分類號：TP391.9文獻(xiàn)標(biāo)志碼：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 引言

在航空航天機電產(chǎn)品中，線纜起著電子設(shè)備間通信與能量傳輸?shù)淖饔?，其特點是種類眾多、布線密度大、敷設(shè)空間小等［1］。隨著航空航天設(shè)備向著高度集成化發(fā)展，布線環(huán)境變得日趨復(fù)雜，線纜布局設(shè)計難度大大提升，布線設(shè)計效率成了亟需解決的問題。目前線纜布局的主要研究方向是自動化布線［2］：通過對布線環(huán)境的空間預(yù)處理，把三維連續(xù)空間轉(zhuǎn)化為可供算法計算的離散空間；再使用智能優(yōu)化算法求解線束路徑與拓?fù)浣Y(jié)構(gòu)。這其中，布線空間離散化模型的有效降維對線束布局的求解效率與質(zhì)量有著重要影響。

目前針對空間離散化模型的降維技術(shù)主要有八叉樹法［3］、混沌柵格法［4］以及3D連接圖［5］等。但上述方法存在降維性能不足、適用性低、構(gòu)建方式復(fù)雜等問題，無法保證為后續(xù)布線算法提供高效的搜索空間。針對以上問題，本文提出基于多頭絨泡菌算法改進(jìn)的柵格預(yù)處理模型，以算法的網(wǎng)絡(luò)優(yōu)化能力在保留空間重要節(jié)點的同時對布線空間進(jìn)行有效精簡，同時基于布線工藝約束對算法做出改進(jìn)，提高預(yù)處理方法的適用性。

1 面向布線問題的多頭絨泡菌模型

1.1 離散布線空間模型

線纜的布局設(shè)計通常以離散布線空間為基礎(chǔ)，在一定工程約束下通過布線優(yōu)化算法求得合理的線束分支結(jié)構(gòu)與走線路徑。其中離散布線空間可看成由離散點與離散點間的連通關(guān)系構(gòu)成的網(wǎng)絡(luò)，每個離散點記錄相應(yīng)位置的工藝屬性與坐標(biāo)信息。為保證布線環(huán)境信息的完備性，布線空間模型的離散點規(guī)模通常十分龐大，這對于布線優(yōu)化算法的求解效率和質(zhì)量會產(chǎn)生不利影響。相反，若盲目地簡化模型，則容易導(dǎo)致優(yōu)質(zhì)解的丟失。因此布線規(guī)劃需要同時考慮空間降維與關(guān)鍵節(jié)點的保留。

1.2 多頭絨泡菌模型

在一次生物實驗中，TERO等［6］發(fā)現(xiàn)多頭絨泡菌具有構(gòu)建最短網(wǎng)絡(luò)的生物智能。它在覓食時能將自身形態(tài)轉(zhuǎn)變?yōu)檫B接各個食物源的最短網(wǎng)絡(luò)。 研究人員通過分析它的生物特性，建立了多頭絨泡菌數(shù)學(xué)模型（以下簡稱PMM）。

PMM將該菌的覓食網(wǎng)絡(luò)看成是節(jié)點與原生質(zhì)管道的集合。每個節(jié)點vi具有各自的壓強pi，每條原生質(zhì)管道ei，j具有管道長度Li，j、導(dǎo)通性Di，j、流量Qi，j等屬性?；诓疵C葉定律，其各屬性間的關(guān)系如式（1）所示。

在PMM中，通過設(shè)置源節(jié)點vs與匯節(jié)點ve來表示食物源位置，根據(jù)基爾霍夫定律，從源節(jié)點流入的初始流量Io會全部從匯節(jié)點流出，如式（2）所示。

式（1）與式（2）刻畫了原生質(zhì)管道中流體的流動規(guī)律，而管道的導(dǎo)通性Di，j會隨著流量Qi，j自適應(yīng)地變化，其變化規(guī)律如式（3）所示。

式中：f（|Qi，j |）為單調(diào)遞增函數(shù)，滿足f（0）=0，它表示下一時刻導(dǎo)通性的增長量；δ為管道的衰減率；δDi，j代表管道下一時刻的衰退量。在網(wǎng)絡(luò)優(yōu)化中，f（|Qi，j |）采用式（4）會有更好的效果。

初始化網(wǎng)絡(luò)后，在時間間隔t下可通過式（2）確定各節(jié)點壓力p，再由式（1）算出當(dāng)前各管道內(nèi)的流量Qt。Qt通過式（3）作用到Dt+1，重復(fù)上述步驟，將導(dǎo)通性D小于閾值的邊刪除，網(wǎng)絡(luò)將最終收斂到連通各食物源節(jié)點的最短路徑。

PMM能根據(jù)食物源的相對位置收縮冗余路徑，強化連通食物源的最短路徑，這一生物特性對布線空間離散點的簡化具有啟發(fā)意義，兩者的映射關(guān)系如圖1所示。其中覓食環(huán)境中的食物源類比于布線環(huán)境中的接線端口，黏菌的原生質(zhì)管道即離散點間的連通路徑，黏菌的避光性對應(yīng)于線纜布局時需遠(yuǎn)離熱源與電磁源的原則。將該方法運用到布線空間預(yù)處理中，能有效降低空間維度與復(fù)雜度，縮小后續(xù)優(yōu)化算法的探索空間。

2 基于PMM改進(jìn)的布線空間模型

基于PMM算法的布線空間模型創(chuàng)建分為3個階段，其流程如圖2所示。首先是初始規(guī)劃階段，根據(jù)布線空間尺寸創(chuàng)建柵格連通圖，依托特殊組件位置信息設(shè)置離散點的工藝屬性。第2步為PMM算法運行階段，根據(jù)工藝約束的引導(dǎo)強化可布線區(qū)間內(nèi)邊的導(dǎo)通性，引入冗余點的概念提高算法效率。第3步為離散單元精簡階段，以各邊導(dǎo)通性均值DAvg過濾大量節(jié)點，以更新后的柵格連通圖作為最終的布線空間模型。

2.1 柵格連通圖的創(chuàng)建

PMM是基于圖的網(wǎng)絡(luò)優(yōu)化，因此需要將空間數(shù)據(jù)模型以圖的形式構(gòu)建出來。本文采用均勻柵格劃分布線空間，結(jié)合線束敷設(shè)工藝賦予每個離散單元屬性值并創(chuàng)建鄰接關(guān)系。具體步驟如下。

步驟1：確定布線空間邊界長度以及特殊組件與端口的位置。以最粗線纜的最小彎曲半徑為柵格間距，均勻劃分三維布線空間，以柵格單元中心點作為節(jié)點，創(chuàng)建點集V。

步驟2：根據(jù)柵格單元與障礙物邊界的距離，設(shè)置節(jié)點屬性值貼壁點集Vw、浮空點集VS以及障礙點集Vo，將距離接線端口最近的節(jié)點設(shè)置為端口點集Vp。

步驟3：將除障礙點集Vo外的所有點按空間6個方向進(jìn)行鄰域連通，構(gòu)成邊集E。

步驟4：以電氣元件和發(fā)熱元件為幾何中心構(gòu)建干擾區(qū)域，將該區(qū)域內(nèi)的點所構(gòu)成的邊標(biāo)記為干擾邊集Et，根據(jù)干擾信號強弱計算每個節(jié)點的工藝信息值。

步驟5：由貼壁點構(gòu)成的邊標(biāo)記為貼壁邊集Ew，若Ew內(nèi)的邊屬于Et，則不改變邊的屬性。

通過上述過程產(chǎn)生的柵格連通圖，滿足多頭絨泡菌優(yōu)化網(wǎng)絡(luò)的計算需求并將空間幾何信息與工藝信息有機結(jié)合，有利于后續(xù)優(yōu)化算法的求解質(zhì)量。圖3為節(jié)點數(shù)據(jù)的層次結(jié)構(gòu)。

2.2 基于工藝約束的黏菌網(wǎng)絡(luò)流運動規(guī)則

傳統(tǒng)PMM解決的是無約束情況下的網(wǎng)絡(luò)尋優(yōu)問題，而實際布線環(huán)境中存在多種工藝約束，這些約束將影響線束布局的走向，因此利用PMM對離散單元進(jìn)行簡化時應(yīng)充分考慮這些因素。本文提出兩項規(guī)則來模擬實際布線環(huán)境下的工藝約束，進(jìn)而影響?zhàn)ぞW(wǎng)絡(luò)流的運動方向，使之沿著更符合布線條件的路徑流動。

規(guī)則一：源匯節(jié)點動態(tài)更新規(guī)則

機電產(chǎn)品中常見的是多分支線纜結(jié)構(gòu)，通常由某一端口伸出的線纜需要經(jīng)過多個分支點才能到達(dá)目標(biāo)端口。而傳統(tǒng)的PMM只考慮網(wǎng)絡(luò)間的最短距離，每次計算時只選取一對源匯節(jié)點進(jìn)行迭代更新，缺少全局性考慮，可能會造成潛在優(yōu)質(zhì)分支點的遺失。鑒于此，本文的源匯節(jié)點動態(tài)更新規(guī)則如下。

1）在每一次迭代過程中，從端口點集VP中按序選擇一節(jié)點為源節(jié)點vs，點集VP中其余節(jié)點均設(shè)置為匯節(jié)點ve，從源節(jié)點流入的流量將均勻地從匯節(jié)點流出。將式（2）替換為

2）布線模型中可能存在專為布線預(yù)留的結(jié)構(gòu)空間，根據(jù)其機械結(jié)構(gòu)特征，可人為設(shè)置分支點位置，將其加入端口點集Vp中，使得合理的布線空間最大限度地保留。

規(guī)則二：基于工藝約束的導(dǎo)通性變化規(guī)則

線纜在敷設(shè)過程中傾向于貼壁敷設(shè)，且要繞開熱源、電磁源的干擾。因此需要在PMM收斂的過程中加入新的約束條件。本文對在熱源與電磁源影響范圍內(nèi)的邊集Et與貼壁邊集Ew的導(dǎo)通性公式做出修改：

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

式中：ei，j為節(jié)點i，j之間的邊；λ為修正系數(shù)；函數(shù)G（ei，j）的主要作用是通過增減節(jié)點流量的方式保留更適合布線的離散單元，其增減量如式（7）所示。

式中：DAvg表示上一時刻所有邊導(dǎo)通性的均值；nw與nt分別表示邊集Ew與邊集Et中的邊數(shù)。

2.3 加速策略

為了加速算法收斂，本文參考文獻(xiàn)［7］中冗余邊與冗余點的概念，在迭代過程中加入刪減節(jié)點的操作。柵格連通圖中的冗余邊可定義為導(dǎo)通值小于自設(shè)閾值的邊，在圖4中以虛線表示，它將在迭代過程中刪除。初始離散空間中，單個節(jié)點會有6條連通邊，如圖4中V1所示。隨著冗余邊的刪除，會出現(xiàn)兩類冗余點的情況。

第一類冗余點：只有兩條連通邊的節(jié)點，且兩條連通邊處于同一直線上，如節(jié)點V2。此類點的存在不會對最終結(jié)果造成影響，因此可以保留節(jié)點信息，將它的兩條連通邊合并為一條。通過這樣的方式減少算法的計算量。

第二類冗余點：僅有一條或沒有連通邊的節(jié)點，如節(jié)點V3與節(jié)點V4，此類點與網(wǎng)絡(luò)間的連通關(guān)系太少，因此可以不保留節(jié)點信息直接刪除。

2.4 離散單元精簡策略

柵格連通圖中含有大量節(jié)點，為了在少量的迭代次數(shù)下快速精簡節(jié)點數(shù)量。本文以端口點集數(shù)|Vp|作為最大迭代次數(shù)，在PMM迭代結(jié)束時以各邊平均導(dǎo)通值DAvg為基準(zhǔn)，提取導(dǎo)通值大于DAvg的邊集，再以構(gòu)成這些邊集的節(jié)點作為最終留存的離散點集。

3 性能評價方法

為了全面地評估預(yù)處理技術(shù)的性能，本文綜合考慮布線模型對實際布線空間的覆蓋率、表述性以及對布線算法的搜索效率、搜索精度等多個因素的影響，建立布線空間模型的性能評估指標(biāo)體系，如圖5所示。結(jié)合文獻(xiàn)［8］中的改進(jìn)雷達(dá)圖法對布線空間模型進(jìn)行直觀、定性的評價。

4 實例分析

本文對兩種不同結(jié)構(gòu)特征的機電模型進(jìn)行測試，如圖6所示。圖6（a）為機艙模型，其特點是空間開敞、零部件分布間距大，應(yīng)著重考慮空間降維因素。圖6（b）為衛(wèi)星模型，屬于封閉空間，工藝約束較多，對空間模型的開敞性要求更高。兩者的各項指標(biāo)權(quán)重如表1所示。

目前常用的布線離散空間模型有八叉樹法與Escape法，因此本文選取這兩種方法與PMM改進(jìn)的柵格預(yù)處理法進(jìn)行對比分析?；诒?中的權(quán)重參數(shù)，各項指標(biāo)值經(jīng)過正向化與標(biāo)準(zhǔn)化處理后，得到的性能評價結(jié)果如圖7與圖8所示。3種預(yù)處理方法構(gòu)建的布線空間模型如圖9所示。

分析雷達(dá)圖可知，在降維性方面，PMM改進(jìn)的柵格法在兩種模型中的表現(xiàn)最好，這得益于離散點的精簡策略。而Escape法在兩模型中的降維性表現(xiàn)卻是相反的，主要原因是Escape法是根據(jù)模型幾何平面與障礙物的交點構(gòu)建的，其交點數(shù)量取決于模型的復(fù)雜程度。在開敞性與代表性方面，八叉樹法要優(yōu)于另外兩種方法，原因是八叉樹采用不均勻的空間劃分方式，提高了狹窄空間與開敞空間的連通性，且不均勻的離散單元對空間的覆蓋率更高，更具代表性。而PMM改進(jìn)的柵格法在精簡空間時犧牲了一定數(shù)量的離散單元，空間代表性較差，但在開敞性方面表現(xiàn)良好。在算法穩(wěn)定性與預(yù)處理效率上，三者的差異并不明顯。綜上，采用PMM改進(jìn)的柵格法能有效降低空間維度，且有較好的綜合性能表現(xiàn)。

為進(jìn)一步驗證預(yù)處理方法的有效性，本文以粒子群算法作為布線優(yōu)化算法，得到的分支線纜結(jié)構(gòu)如圖10所示，性能分析結(jié)果如表2所示。分析可知，基于PMM改進(jìn)的柵格預(yù)處理法得到的線纜組件結(jié)構(gòu)最優(yōu)，且算法運行時間最短。這主要歸結(jié)于PMM通過全局遍歷的方式將大量冗余離散單元刪去，縮小了最優(yōu)解的搜索范圍，使粒子群算法步入局部最優(yōu)的可能性減小，且降維后的求解空間更有利于算法的搜索效率。因此基于PMM改進(jìn)的柵格預(yù)處理法具有一定的優(yōu)越性。

5 結(jié)語

針對現(xiàn)有布線離散空間普遍存在的降維難題，本文基于改進(jìn)的多頭絨泡菌算法對離散空間進(jìn)行降維處理，通過實例驗證了所提方法的有效性。

參考文獻(xiàn)：

［1］ 駱飛平，韓冰，楊鋒，等. 飛機線纜自動檢測系統(tǒng)布局優(yōu)化設(shè)計研究［J］. 測控技術(shù)，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］ 耿琪，張丹，劉召朝，等. 面向機電產(chǎn)品布線規(guī)劃的空間預(yù)處理技術(shù)［J］. 航空精密制造技術(shù)，2019，55（3）：25-30.

［4］ 付宜利，封海波，孫建勛，等. 基于混沌算法的機電產(chǎn)品管線自動敷設(shè)研究［J］. 計算機集成制造系統(tǒng)，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］ 程寶鵬， 方洋旺， 彭維仕， 等. 基于雷達(dá)圖法的群智能算法綜合性能評估［J］. 北京航空航天大學(xué)學(xué)報：2022： 1-14.