李春泉，胡宇威，尚玉玲，王弘揚(yáng)

（桂林電子科技大學(xué) 機(jī)電工程學(xué)院，廣西 桂林 541004）

1 引言

線纜布局設(shè)計(jì)是機(jī)電產(chǎn)品研發(fā)工作中的重要環(huán)節(jié)之一，也是比較繁重的工作任務(wù)之一[1]。合理的線纜布局可以提升產(chǎn)品性能并且縮短研發(fā)成本和周期。在傳統(tǒng)的線纜布局中，布線人員憑借布線經(jīng)驗(yàn)和手工測(cè)量進(jìn)行布線，而隨著線纜數(shù)量的增加以及布線環(huán)境的復(fù)雜化，該技術(shù)無(wú)法合理的對(duì)線纜路徑進(jìn)行整體規(guī)劃。目前，虛擬環(huán)境下的線纜布局設(shè)計(jì)方法主要包括自動(dòng)布局設(shè)計(jì)和計(jì)算機(jī)輔助人機(jī)交互式布局。與計(jì)算機(jī)輔助人機(jī)交互式布局相比，線纜自動(dòng)布局設(shè)計(jì)可通過(guò)計(jì)算機(jī)軟件，運(yùn)用布線算法自動(dòng)完成線纜路徑的規(guī)劃，具有更高的布線效率。

早在1961年，文獻(xiàn)[2]提出了李氏算法，即迷宮算法，并以該算法對(duì)避障的最短路徑進(jìn)行求解。文獻(xiàn)[3]提出了利用機(jī)器人路徑規(guī)劃技術(shù)并把細(xì)胞分裂法作為搜索算法進(jìn)行管線自動(dòng)布局設(shè)計(jì)。文獻(xiàn)[4]為解決復(fù)雜環(huán)境中的線纜布局問(wèn)題，提出了先通過(guò)隨機(jī)路徑圖計(jì)算出初始路徑，之后考慮布線環(huán)境的約束并對(duì)初始路徑優(yōu)化，最終取得了較好的計(jì)算效率。文獻(xiàn)[5]以UG為開(kāi)發(fā)平臺(tái)，實(shí)現(xiàn)了三維環(huán)境下的線纜布局設(shè)計(jì)。文獻(xiàn)[6]提出了一種利用障礙物輪廓擴(kuò)展的方法進(jìn)行線路搜索，并解決了主干路徑中的“井”字問(wèn)題。這些方法雖然可以用于解決一部分的實(shí)際問(wèn)題，但由于線纜路徑規(guī)劃的復(fù)雜性，高效的線纜布局優(yōu)化算法仍有待開(kāi)發(fā)。

隨著優(yōu)化理論和工程實(shí)踐的發(fā)展，新型的人工智能優(yōu)化算法如人工魚(yú)群算法、螢火蟲(chóng)算法、蝙蝠算法得以提出[7-9]，由于線纜布線環(huán)境較為復(fù)雜，具有搜索空間較大，多約束條件的特點(diǎn)，上述算法不能夠很好的應(yīng)用于線纜布線中。因此將新型的人工智能算法應(yīng)用于線纜自動(dòng)布局中，分析了新型人工智能算法在線纜自動(dòng)布局中的特點(diǎn)，并設(shè)計(jì)了一種面向線纜路徑規(guī)劃的改進(jìn)的螢火蟲(chóng)算法，最后對(duì)該算法的可行性和有效性進(jìn)行了實(shí)例驗(yàn)證。

2 布線環(huán)境建模

采用柵格（grid）表示布線環(huán)境，可避免在處理障礙物邊界中的復(fù)雜計(jì)算。然后將布線空間離散化，對(duì)不同的柵格賦予不同的值。

2.1 環(huán)境的離散化和障礙邊界的處理

首先根據(jù)式（1）、式（2）確定柵格的粒度，以布線起點(diǎn)為原點(diǎn)建立坐標(biāo)系，且終點(diǎn)處于坐標(biāo)系內(nèi)。然后將以設(shè)定的柵格粒度對(duì)布線環(huán)境離散化。

式中：Aobs—障礙物的面積；Atotal—總體面積；lgrid—柵格粒度步長(zhǎng)；lmin—柵格最小粒度；lmax—柵格最大粒度。

在離散化的同時(shí)，對(duì)障礙邊界進(jìn)行處理：

（1）根據(jù)障礙物相對(duì)于起點(diǎn)的位置，得到障礙物的坐標(biāo)邊界。

（2）將不滿一個(gè)柵格的障礙物，視為一個(gè)柵格。

（3）有凹陷部分的障礙物，凹陷部分和障礙部分應(yīng)視為一個(gè)整體障礙物，避免局域死區(qū)。

2.2 模型的建立

路徑規(guī)劃的問(wèn)題表述如下：在環(huán)境A內(nèi)進(jìn)行布線，將環(huán)境A投影到一個(gè)二維平面從而得到布線環(huán)境C，并把C分為一個(gè)個(gè)大小相同的方格，方格的邊長(zhǎng)為 lgrid。有障礙物 obsi，i=1，2，3，…，n，obsi表示第i個(gè)障礙物的大小，并將obsi映射到布線環(huán)境C內(nèi)。避障空間，x表示布線環(huán)境中的某一點(diǎn)。路徑規(guī)劃就是在避障空間Cavo內(nèi)從布線起點(diǎn)到布線終點(diǎn)找出一條較優(yōu)的路徑。在二維矩陣graph中，用如下函數(shù)來(lái)描述布線環(huán)境中的障礙分布情況：

式中：Pos（x）=1—x坐標(biāo)處有障礙物；Pos（x）=0—x的坐標(biāo)處無(wú)障

礙物，整個(gè)布線環(huán)境由 Pos（x）=0 以及 Pos（x）=1 所組成。

用圖1，圖2作為空間模型建立的一個(gè)示例：一個(gè)將實(shí)際工作環(huán)境投影到二維平面上的布線環(huán)境，如圖1所示。其中圓形環(huán)表示布線起點(diǎn)；矩形環(huán)表示布線終點(diǎn)；黑色的區(qū)域表示布線環(huán)境中的障礙物；白色的區(qū)域表示布線環(huán)境中可進(jìn)行布線的區(qū)域，即避障空間。用上述建模方法可以得到圖2空間模型，其中圓形環(huán)表示線纜布線的起點(diǎn)；矩形環(huán)表示線纜布線終點(diǎn)；黑色的柵格為障礙柵格，表示布線環(huán)境中的障礙物；白色的柵格為可布線柵格，表示布線環(huán)境中可進(jìn)行布線的區(qū)域。

圖1 布線環(huán)境Fig.1 Wiring Environment

圖2 空間模型1 Fig.2 Spatial Model 1

在二維矩陣graph中，graph（a，b）表示該柵格四個(gè)頂點(diǎn)的坐標(biāo)分別為 x（a-1，b-1），x（a-1，b），x（a，b-1），x（a，b）。

3 螢火蟲(chóng)算法的基本思想

螢火蟲(chóng)算法（FA）是一種群體搜索的隨機(jī)優(yōu)化算法。每只螢火蟲(chóng)均朝向相對(duì)各自最亮的那只螢火蟲(chóng)方的向進(jìn)行移動(dòng)，最終所有個(gè)體移動(dòng)到亮度最高的螢火蟲(chóng)的位置上。從數(shù)學(xué)角度對(duì)螢火蟲(chóng)算法的描述如下描述：Iij=Ij×e-γ*r1j（5）

式中：γ—光強(qiáng)吸收系數(shù)；Ij—第j只螢火蟲(chóng)的熒光亮度；Iij—第i

只螢火蟲(chóng)所感受到第j只螢火蟲(chóng)的熒光亮度；rij—第i只螢

火蟲(chóng)到第j螢火蟲(chóng)的距離。

式中：βj—最大吸引度，表示第j只螢火蟲(chóng)的吸引度；βij—第j只

螢火蟲(chóng)對(duì)第i只螢火的吸引度。

式中：擾動(dòng)項(xiàng)（α×ε）—螢火蟲(chóng)的隨機(jī)走動(dòng)以此避免算法過(guò)早進(jìn)入局部最優(yōu)的狀態(tài)，α的取值范圍是［0，1］；ε—一個(gè)均勻分布的隨機(jī)數(shù)向量。

4 線纜布線算法設(shè)計(jì)

4.1 螢火蟲(chóng)的坐標(biāo)

對(duì)布線環(huán)境建模，得到一個(gè)（M×N）的graph矩陣，矩陣下標(biāo)可以表示布線環(huán)境的任一點(diǎn)的位并且能檢測(cè)該位置是否觸碰障礙。

根據(jù)矩陣列數(shù)為N，令螢火蟲(chóng)的位置具有N個(gè)維度，即Xi=（xi1，xi2，xi3，…，xiN），xiN表示第 i只螢火蟲(chóng)在矩陣的第 N 列的行數(shù)。

4.2 改進(jìn)的螢火蟲(chóng)算法（IFA）

由于螢火蟲(chóng)算法的原理可知，若初始群體分布不均勻，則算法的全局搜索能力不強(qiáng)，收斂速度較慢。隨機(jī)產(chǎn)生初始群體的螢火蟲(chóng)算法容易進(jìn)入局部最優(yōu)。而通過(guò)混沌所具有的遍歷性、隨機(jī)性和非周期性等特點(diǎn)，可提高螢火蟲(chóng)算法中初始解的質(zhì)量。

由文獻(xiàn)[10]可知，logistic映射所得解的均勻性差于立方映射，因此采用立方映射對(duì)螢火蟲(chóng)進(jìn)行初始化。且在布線模型中，存在障礙柵格，因此映射要在已排除障礙柵格的搜索環(huán)境下進(jìn)行。若搜索環(huán)境第d維度上共有n個(gè)連續(xù)的障礙區(qū)間，則區(qū)間長(zhǎng)度分別記為A1，A2，A3，…，An，且障礙區(qū)間距空間第d維度的下界越近，其下標(biāo)越小。每個(gè)障礙區(qū)間靠近環(huán)境下界的區(qū)間邊界記為lA1，lA2，lA3，…，lAn。同理，m 個(gè)連續(xù)的非障礙區(qū)間長(zhǎng)度可分為 S1，S2，S3，…，Sm，有 lS1，lS2，lS3，…，lSm。

令Ld表示搜索環(huán)境d維度的下界，Ud表示搜索環(huán)境d維度的上界。所有障礙區(qū)間長(zhǎng)度相加得到總障礙區(qū)間長(zhǎng)度記為L(zhǎng)A。則第 d 維的映射公式如下：

若第d維度上，不存在障礙區(qū)間，即n=0，則第d維度的映的射公式如下：

立方映射的實(shí)現(xiàn)過(guò)程如下：

Step1.有total只螢火蟲(chóng)在N維空間中，且隨機(jī)生成一個(gè)N維向量代表第一只螢火蟲(chóng)的位置，Y1=（y11，y12，y13，…，y1N），且 y1j∈［0 1］，1≤j≤N。

Step2.進(jìn)行total-1次迭代，得到其余螢火蟲(chóng)的位置。

Step3.將混沌的螢火蟲(chóng)位置按式（8）、式（9）、式（10）、式（11）映射到搜索環(huán)境中。

標(biāo)準(zhǔn)的螢火蟲(chóng)算法中，螢火蟲(chóng)通過(guò)相對(duì)亮度選擇移動(dòng)方向并進(jìn)行移動(dòng)，因此可能會(huì)導(dǎo)致熒光度最好的螢火蟲(chóng)向其他螢火蟲(chóng)移動(dòng)。在移動(dòng)后，該螢火蟲(chóng)的熒光度可能會(huì)比移動(dòng)之前的熒光度差，從而在下一輪迭代過(guò)程中，螢火蟲(chóng)不能朝著一個(gè)較優(yōu)的位置移動(dòng)。

因此，在每一輪迭代過(guò)程中，篩選出熒光度最好的螢火蟲(chóng)，并令該螢火蟲(chóng)進(jìn)行擇優(yōu)的移動(dòng)，第d維度的位置更新公式如下：

式中：Iinew—第i只螢火蟲(chóng)擇優(yōu)移動(dòng)后的螢光度；Iiold—第i只螢火蟲(chóng)擇優(yōu)移動(dòng)前的熒光度；M—布線環(huán)境處理中所得到矩陣的總行數(shù)；step—搜索步長(zhǎng)，且step=M/10。

對(duì)熒光度較差的Num只螢火蟲(chóng)使用遺傳算法的變異功能，且 Num=round（total/6）。

式中：mutate—變異概率，取值范圍［0 1］；round（）—四舍五入的

取整函數(shù)；total—螢火蟲(chóng)的總個(gè)數(shù)。

其余螢火蟲(chóng)第d維的位置移動(dòng)公式如下：

改進(jìn)的螢火蟲(chóng)算法實(shí)現(xiàn)過(guò)程如下：

Step1.初始化算法基本參數(shù)。設(shè)置最大迭代次數(shù)或搜索精度；螢火蟲(chóng)數(shù)目；最大吸引度；光強(qiáng)吸收系數(shù)；步長(zhǎng)因子；隨機(jī)移動(dòng)參數(shù)。

Step2.利用立方映射初始化種群得到total個(gè)初始解，并計(jì)算出所有螢火蟲(chóng)的熒光度。

Step3.對(duì)比螢火蟲(chóng)的熒光度，確定熒光度最好的螢火蟲(chóng)，根據(jù)相對(duì)熒光度以及螢火蟲(chóng)的相對(duì)吸引度確定其他螢火蟲(chóng)的移動(dòng)方向。

Step4.根據(jù)式（12）更新熒光度最好的螢火蟲(chóng)位置，根據(jù)式（14）更新其余螢火蟲(chóng)位置，判斷熒光度較差的螢火蟲(chóng)是否發(fā)生變異，若發(fā)生變異則轉(zhuǎn)入Step5,否則轉(zhuǎn)入Step6。

Step5.根據(jù)式（13），螢火蟲(chóng)發(fā)生變異。

Step6.根據(jù)更新后螢火蟲(chóng)的位置重新計(jì)算熒光度。

Step7.當(dāng)計(jì)算結(jié)果滿足精度或迭代次數(shù)達(dá)到最大時(shí)，則轉(zhuǎn)Step8，否則轉(zhuǎn)Step3，且迭代次數(shù)加1進(jìn)行下一次迭代。

Step8.輸出全局最優(yōu)值和最優(yōu)個(gè)體位置。

5 仿真結(jié)果

5.1 改進(jìn)螢火蟲(chóng)算法（IFA）的仿真結(jié)果

選取了空間模型作為算法的測(cè)試用例，如圖3所示。其中圓形環(huán)表示布線起點(diǎn)，矩形環(huán)表示布線終點(diǎn)，白色的柵格表示可布線柵格，黑色的柵格表示障礙物,且lgrid=1cm。

圖3 空間模型2Fig.3 Spatial Model 2

算法的參數(shù)設(shè)置：螢火蟲(chóng)數(shù)total=20；光強(qiáng)吸收系數(shù)γ=1；最大吸引度βj=1；搜索步長(zhǎng)step=1；隨機(jī)移動(dòng)參數(shù)α=2；迭代次數(shù)；mutate=0.4；iteration=200。將IFA運(yùn)行50次，并把全部收斂曲線進(jìn)行擬合所得到的趨勢(shì)曲線，如圖4所示。黑色箭頭表示該算法計(jì)算出的線纜路徑，如圖5所示。

圖4 IFA趨勢(shì)曲線Fig.4 IFA Trend Curve

圖5 線纜路徑Fig.5 Cable Route

5.2 與其他人工智能算法的對(duì)比

把與測(cè)試用例中同樣的布線環(huán)境用于IFA、基礎(chǔ)的螢火蟲(chóng)算法（FA）、蝙蝠算法（BA）、人工魚(yú)群算法（AFSA）和具有變異功能的粒子群算法（IPSO）運(yùn)行50次且最大迭代次數(shù)為200，結(jié)果如表1所示。

表1 算法對(duì)比Tab.1 Comparison of Algorithms

由表1可知，所有算法運(yùn)行50次時(shí)，IFA的最優(yōu)值與平均值之差僅為0.2517cm，最優(yōu)值與最差值之差僅1.1716cm，方差為僅為0.0973cm2，計(jì)算結(jié)果的波動(dòng)幅度遠(yuǎn)優(yōu)于IPSO、AFSA、FA，略差于BA。

AFSA、BA、IFA、IPSO、FA運(yùn)行50次，如圖6表示。并分別把每個(gè)算法的全部收斂曲線進(jìn)行擬合所得到的趨勢(shì)曲線。根據(jù)表1、圖6可知，相比于IFA，BA和AFSA具有較快的收斂速度，但算法易處于局部最優(yōu)的狀態(tài)，因此求得的最優(yōu)解誤差較大，尋優(yōu)率太低；IFA算法相比于表1中其他算法擁有較高的尋優(yōu)率，算法的收斂速度與IPSO以及FA相近，算法程序每次執(zhí)行后的最優(yōu)解波動(dòng)幅度較小。

圖6 趨勢(shì)曲線對(duì)比Fig.6 Comparison of Trend Curves

6 結(jié)語(yǔ)

對(duì)一種新型的人工智能算法-螢火蟲(chóng)算法進(jìn)行了研究，同時(shí)針對(duì)標(biāo)準(zhǔn)螢火蟲(chóng)算法收斂速度較慢、易陷入局部最優(yōu)等問(wèn)題，提出了一種改進(jìn)的螢火蟲(chóng)算法（IFA）并將其用于線纜路徑的自動(dòng)規(guī)劃。該算法首先利用混沌映射初始化螢火蟲(chóng)位置，使螢火蟲(chóng)較為均勻分布在環(huán)境內(nèi)；對(duì)精英的螢火蟲(chóng)采用擇優(yōu)移動(dòng)的策略，保證螢火蟲(chóng)移動(dòng)向較優(yōu)的方向移動(dòng)；對(duì)熒光度較差的個(gè)體進(jìn)行變異增加了算法全局搜索能力的局部搜索能力，使算法不易陷入局部最優(yōu)。最終，與各種人工智能算法對(duì)比，該改進(jìn)算法在保證收斂速度的同時(shí)，提高了線纜路徑的質(zhì)量以及尋優(yōu)率，驗(yàn)證了算法的可行性。

［1］劉瀟，劉檢華，劉佳順.基與改進(jìn)隨機(jī)路徑圖的分支線纜自動(dòng)布線技術(shù)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2014，20（12）：2952-2961.（Liu Xiao，Liu Jian-hua，Liu Shun-jia.Multi-branch cable automatic routing based on improved PRM ［J］.Computer Integrated Manufacturing Systems，2014，20（12）：2952-2961.）

［2］Lee C Y.An algorithm for path connections and its application［J］.IRE Transactions on Electronic Computer，1961，10（3）：346-364.

［3］Zhu D，Latombe J C.Pipe routing-path planning（With many constraints）［C］.Proceedings IEEE International Conference on Robotics and Automation，1991：1940-1947.

［4］KABUL I，GAYLE R，MING C.Cable route planning in complex environment using constrained Sampling［C］.Proceedings of 2007 ACM on Solid and Physical Modeling.New York：ACM，2007：395-402.

［5］蔡毅，王彥偉，黃正東.基于UG的三維自動(dòng)布線技術(shù)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（8）：68-72.（Cai Yi，Wang Yan-wei，Huang Zheng-dong.Research on 3D automatic electrical routing in UG system［J］.Computer Engineering and Applications，2012，48（8）：68-72.）

［6］李春泉，徐楚，張明.基于輪廓擴(kuò)展方法的電氣線纜布線技術(shù)研究［J］.機(jī)械設(shè)計(jì)與制造，2015（4）：266-269.（Li Chun-quan，Xu Chu，Zhang Ming.Routing technology of electric cables based on the method of contour extension［J］.Machinery Design&Manufacture，2005（4）：266-269.）

［7］李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚(yú)群算法［J］.系統(tǒng)工程理論于實(shí)踐，2002，22（11）：32-38.（Li Xiao-lei，Shao Zhi-jiang，Qian Ji-xin.An optimizing method based on autonomous animals：fish-swarm algorithm ［J］.System Engineering Theory and Practice，2002，22（11）：32-38.）

［8］YANG X-S.Nature-in Spired Metaheuristic Algorithm［M］.Frome：Luniver Press，2008：81-96.

［9］X S Yang.A New Metaheuristic Bat-inspired Algorithm［M］.Berlin：Springer，2010：65-74.

［10］周燕，劉培玉，趙靜.基與自適應(yīng)慣性權(quán)重的混沌粒子群算法［J］.山東大學(xué)學(xué)報(bào)：理學(xué)版，2012，47（30）：1-6.（Zhou Yan，Liu Pei-yu，Zhao Jing.Chaos particle swarm optimization based on the adaptive inertia weight［J］.Journal of Shandong University，2012，47（30）：1-6.）