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

初元紅

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

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

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

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

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

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

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

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

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

1.1 工作空間

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

1.2 柵格化工作空間

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

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

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

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

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

1.3 蟻群算法

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

在初始時(shí)刻，[m]只螞蟻隨機(jī)放置于首發(fā)柵格中，各條路徑上的信息素初始值相等，設(shè)為：[τij（0）=τ0]為信息素初始值，可設(shè)[τ0=mLm]，[Lm]是由最近鄰啟發(fā)式方法構(gòu)造的路徑長(zhǎng)度。其次，螞蟻[k（k=1，2，…m）]，按照隨機(jī)比例規(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]下一步被允許訪問(wèn)的柵格集合[5]。

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

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

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

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

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

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

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

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

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

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

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

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

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

第7步：繪圖輸出。

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 杜利峰，牛永潔.蟻群算法在 MATLAB 中的實(shí)現(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個(gè)案例分析[M].北京：北京航空航天大學(xué)出版社，2011：205-228.

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

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

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