基于蟻群算法的復(fù)雜空間電纜排布優(yōu)化方法

初元紅

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

關(guān)鍵詞：電纜排布；蟻群算法；柵格化；優(yōu)化設(shè)計

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

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

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

1 蟻群算法優(yōu)化原理

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

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

柵格法是平面運動路徑規(guī)劃的一個抽象模型，是目前研究最廣泛的路徑規(guī)劃方法之一。柵格法是由M.B.Metea首先提出的[4]，用于解決分等級地形的自動化路徑規(guī)劃問題。它將工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元，工作空間中障礙物的位置和大小一致，并且在運動過程中，該物的位置和大小不發(fā)生變化。用尺寸相同的柵格對機器人的二維工作空間進行劃分。柵格的大小以任務(wù)目標(biāo)自身的尺寸為參照，自由空間和障礙物均可表示為柵格塊的集成。問題可以進一步具體化為：初始時，任務(wù)目標(biāo)未知柵格圖的格子信息，但是，任務(wù)目標(biāo)具有感知能力與記憶能力，對于所處位置的鄰接?xùn)鸥裥畔⒖梢愿兄瑢τ诟兄降臇鸥裥畔⒖梢杂涗洝ＤＰ褪紫仁且蝿?wù)目標(biāo)從給定柵格圖的起點，繞過障礙，找出通往終點的路線，要求極小化該路線所經(jīng)過的柵格數(shù)。

1.1 工作空間

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

1.2 柵格化工作空間

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

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

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

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

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

1.3 蟻群算法

螞蟻系統(tǒng)是經(jīng)典的蟻群算法。其搜索過程如下：

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

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

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

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

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

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

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

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

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

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

第1步：狀態(tài)初始化；

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

第3步：轉(zhuǎn)輪賭法選擇下一步走法；

第4步：狀態(tài)更新和記錄；

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

第6步：更新信息素，判斷循環(huán)或結(jié)束；

第7步：繪圖輸出。

2 優(yōu)化結(jié)果

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

圖5為布線位置的優(yōu)化計算結(jié)果。根據(jù)圖中所示路徑布線將實現(xiàn)最優(yōu)布線路徑。

3 結(jié)論

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

參考文獻：

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

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

[3] 杜利峰，牛永潔.蟻群算法在 MATLAB 中的實現(xiàn)[J].信息技術(shù)，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].北京：北京航空航天大學(xué)出版社，2011：205-228.

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

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

【通聯(lián)編輯：張薇】