基于蟻群算法的復雜空間電纜排布優化方法

初元紅

摘要：在水下航行體或航空器的閉合空間內安裝較多的電子元件、電路板部件和其他機械組件時，各個電子部件歸總起來的多芯電纜排布問題比較煩瑣復雜，合理的布線路徑不僅可以使布線更加科學，最重要的是在該產品有苛刻的重量要求時，最短的布線優化可以最大程度的減輕系統的總體重量。通過選定狹小空間內的典型工作區域，并對該區域進行柵格化處理，應用蟻群智能算法，對該特定空間范圍內的電線、電纜排布進行優化設計，可以使系統設計更加科學合理。

關鍵詞：電纜排布；蟻群算法；柵格化；優化設計

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1009-3044（2018）28-0179-03

目前，在狹小復雜空間中的電路導線排布（如水下航行體內部）基本是按照技術人員的經驗進行的。無論是細小電線的排布或者是組合電纜的排布，均未進行在長度方面的詳細技術參數分析，僅具備基本的合理性，距離達到全面的科學性還有很大差距。如果要求技術人員對每根導線都進行對比分析，工作量將非常巨大，且效果不一定好。因此，需要一種能夠合理優化布線設計的技術和理論來作為技術設計人員的輔助設計手段，使之能夠在最大程度上縮短線纜長度，減輕系統重量，使設計更加合理科學。

仿生優化算法是人工智能研究領域中的一個重要分支，其中包括模擬生物界中自然選擇和遺傳機制的遺傳算法，模擬螞蟻群體覓食行為的蟻群算法以及模擬鳥類群體捕食行為的微粒群算法等[1]。各種群體智能算法目前在各個工業、軍工和民用領域得到了廣泛的應用。人工蟻群算法是一種新型的模擬自然界真實蟻群的覓食行為而形成的模擬進化算法，該算法是由意大利學者M.Dorigo等人首先提出，被應用于求解分配問題，作業調度問題等，取得了較好的成果。受其影響，蟻群系統模型逐漸引起了其他研究者的注意，近來也被引入到人工智能的路徑規劃之中[2]。

1 蟻群算法優化原理

在螞蟻尋找食物的過程中，總能找到一條從蟻穴到距離很遠的食物之間的最短路徑。每個螞蟻事先并不知道食物在什么位置，只是在本身能夠看得見的局部范圍內搜索，在搜索過程中將以一定的概率向其他螞蟻留下的信息素濃度高的方向移動，同時自己也釋放信息素，信息素的濃度與經過的路徑長度成反比，同時所有螞蟻的信息素將會以一定的速率揮發，經過一段時間的搜索，最短路徑上的信息素將會越來越濃，按照最短路徑移動的螞蟻將會越來越多，進而形成一個正反饋，使得它們可以找到最短路徑[3]。

路徑規劃是蟻群算法最常見的任務之一。根據對環境信息掌握的程度的不同，路徑的規劃基本上可分為兩種類型：一個是基于環境完全信息的全局路徑規劃，另一個是基于傳感信息的局部路徑規劃。其中局部路徑規劃按工作空間模型表達方法的不同存在三種比較典型的環境建模方法：構型空間法、自由空間法和柵格法。

柵格法是平面運動路徑規劃的一個抽象模型，是目前研究最廣泛的路徑規劃方法之一。柵格法是由M.B.Metea首先提出的[4]，用于解決分等級地形的自動化路徑規劃問題。它將工作環境分解成一系列具有二值信息的網格單元，工作空間中障礙物的位置和大小一致，并且在運動過程中，該物的位置和大小不發生變化。用尺寸相同的柵格對機器人的二維工作空間進行劃分。柵格的大小以任務目標自身的尺寸為參照，自由空間和障礙物均可表示為柵格塊的集成。問題可以進一步具體化為：初始時，任務目標未知柵格圖的格子信息，但是，任務目標具有感知能力與記憶能力，對于所處位置的鄰接柵格信息可以感知，對于感知到的柵格信息可以記錄。模型首先是要任務目標從給定柵格圖的起點，繞過障礙，找出通往終點的路線，要求極小化該路線所經過的柵格數。

1.1 工作空間

在某個水下航行體需要布線的局部區域，選擇比較典型的空間作為本方案的分析目標。圖1是一個小工作區的模擬圖，圖中包括了電路板、電源、機械構件和其他組件等，分別布置在同一個平面內。

1.2 柵格化工作空間

為進行蟻群算法需要對圖1所示工作空間進行柵格化，將圖中各個元件和空余位置收納到柵格內。將該區域有元器件或組件的位置設定為障礙物，根據尺寸對比，合理設計柵格。柵格化得到圖2的25×25柵格地形圖結果。

在軟件中建立25×25地形圖矩陣，1表示障礙物，0表示可布線空間。矩陣化后如矩陣G表示。

在柵格地圖中，每一個柵格相當于一個節點；而在一條路徑中，各個柵格是相鄰的。對于有障礙的地圖，障礙柵格和任何柵格都不相鄰。

利用矩陣表示的柵格如下：

觀察圖3中矩陣G，可以看出矩陣元素為1時，即為障礙物所在位置，矩陣元素為0時，對應空白區域。

1.3 蟻群算法

螞蟻系統是經典的蟻群算法。其搜索過程如下：

在初始時刻，[m]只螞蟻隨機放置于首發柵格中，各條路徑上的信息素初始值相等，設為：[τij（0）=τ0]為信息素初始值，可設[τ0=mLm]，[Lm]是由最近鄰啟發式方法構造的路徑長度。其次，螞蟻[k（k=1，2，…m）]，按照隨機比例規則選擇下一步要轉移的柵格，其選擇概率為：

[pkij（t）=[τij（t）]α[ηij（t）]βs∈allowedk[τis（t）]α[ηis（t）]β，j∈allowedk0，否則] （1）

其中，[τij]為邊[（i，j）]上的信息素，[ηij=1dij]為從柵格[i]轉移到柵格[j]的啟發式因子，[allowedk]為螞蟻[k]下一步被允許訪問的柵格集合[5]。

為了不讓螞蟻選擇已經訪問過的柵格，采用禁忌表[tabuk]來記錄螞蟻[k]當前所走過的柵格。經過[t]時刻，所有螞蟻都完成一次周游，計算每只螞蟻所走過的路徑長度，并保存最短的路徑長度，同時，更新各邊上的信息素。首先是信息素揮發，其次是螞蟻在它們所經過的邊上釋放信息素，其公式如下：

[τij=（1-ρ）τij] ，其中[ρ]為信息素揮發系數，且[0<ρ≤1]。

[τij=τij+k=1mΔτkij]，其中[Δτkij]是第[k]只螞蟻向它經過的邊釋放的信息素，定義為：[Δτkij=1dij，如果邊（i，j）在路徑Tk上0，否則] （2）

根據式（2）可知，螞蟻構建的路徑長度[dij]越小，則路徑上各條邊就會獲得更多的信息素，則在以后的迭代中就更有可能被其他的螞蟻選擇。

螞蟻完成一次循環后，清空禁忌表，重新回到初始柵格，準備下一次搜索。

在蟻群算法的實現過程中，關鍵的步驟有三個：1）螞蟻的移動操作，2）釋放自身的信息素，3）信息素的更新操作。程序算法流程圖見圖4。

在柵格化工作空間和構造啟發式信息矩陣后，蟻群算法按下述步驟進行：

第1步：狀態初始化；

第2步：節點選取，下一步可以前往的節點；

第3步：轉輪賭法選擇下一步走法；

第4步：狀態更新和記錄；

第5步：記下每一代、每一只螞蟻的覓食路線和路線長度；

第6步：更新信息素，判斷循環或結束；

第7步：繪圖輸出。

2 優化結果

在圖5中，選定布線起始點和終止點。以圖3中柵格矩陣G為藍圖，運行預先編制好的Matlab程序，程序輸出界面上將自動繪制最優路徑線條。在G矩陣中第1行第1列對應柵格圖的坐標（1，25）格，第25行第25列對應的柵格圖位置坐標在（25，1）。在選擇起始點為20（20，25），終止點為607（7，1）時，運行結果見圖5。

圖5為布線位置的優化計算結果。根據圖中所示路徑布線將實現最優布線路徑。

3 結論

在水下航行體或空中航行體設計過程中，通常對整體重量有比較苛刻的要求，在狹小閉合的空間內安裝較多的電路板部件和其他機械組件時，各個電子部件歸總起來的多芯電纜排布問題比較復雜，人工布線難以達到科學合理。在滿足功能要求的同時，布線兩端路徑最短的要求顯得非常重要。經工作空間選擇、空間柵格化、蟻群算法優化等步驟設計后，不僅可以使布線合理，最重要的是最短的布線優化可以最大程度的減輕系統的總體重量。至于設計時還要考慮到線纜直徑、連接方式、電磁干擾等因素暫不涉及。

參考文獻：

[1] 段海濱.蟻群算法原理及其應用[M].北京：科學出版社，2005：1.

[2] 張美玉，黃翰，郝志峰，楊曉偉.基于蟻群算法的機器人路徑規劃[J].計算機工程與應用，2005（25）：34-37.

[3] 杜利峰，牛永潔.蟻群算法在 MATLAB 中的實現[J].信息技術，2011（6）：115-118.

[4] M.B.Metea.Route，planning for intelligent autonomous land vehiclesusing hierarchical terrain representation[C].In：Prnc of IEEE Int Confon R obotics and Automation，1987：1947-1952.

[5] 史峰，王輝，郁磊，胡斐.智能算法30個案例分析[M].北京：北京航空航天大學出版社，2011：205-228.

[6] 春花，特日格勒，任哲明.關于蟻群算法的參數設置研究[J].內蒙古民族大學學報，2011（7）：402-404.

[7] 朱慶寶，張玉蘭.基于柵格法的機器人路徑規劃蟻群算法[J].機器人，2005（3）：132-135.

【通聯編輯：張薇】