面向線纜路徑規(guī)劃的改進螢火蟲算法研究

李春泉，胡宇威，尚玉玲，王弘揚

（桂林電子科技大學 機電工程學院，廣西 桂林 541004）

1 引言

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

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

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

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

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

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

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

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

在離散化的同時，對障礙邊界進行處理：

（1）根據障礙物相對于起點的位置，得到障礙物的坐標邊界。

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

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

2.2 模型的建立

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

式中：Pos（x）=1—x坐標處有障礙物；Pos（x）=0—x的坐標處無障

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

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

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

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

在二維矩陣graph中，graph（a，b）表示該柵格四個頂點的坐標分別為 x（a-1，b-1），x（a-1，b），x（a，b-1），x（a，b）。

3 螢火蟲算法的基本思想

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

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

只螢火蟲所感受到第j只螢火蟲的熒光亮度；rij—第i只螢

火蟲到第j螢火蟲的距離。

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

螢火蟲對第i只螢火的吸引度。

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

4 線纜布線算法設計

4.1 螢火蟲的坐標

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

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

4.2 改進的螢火蟲算法（IFA）

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

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

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

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

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

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

Step2.進行total-1次迭代，得到其余螢火蟲的位置。

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

標準的螢火蟲算法中，螢火蟲通過相對亮度選擇移動方向并進行移動，因此可能會導致熒光度最好的螢火蟲向其他螢火蟲移動。在移動后，該螢火蟲的熒光度可能會比移動之前的熒光度差，從而在下一輪迭代過程中，螢火蟲不能朝著一個較優(yōu)的位置移動。

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

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

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

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

取整函數(shù)；total—螢火蟲的總個數(shù)。

其余螢火蟲第d維的位置移動公式如下：

改進的螢火蟲算法實現(xiàn)過程如下：

Step1.初始化算法基本參數(shù)。設置最大迭代次數(shù)或搜索精度；螢火蟲數(shù)目；最大吸引度；光強吸收系數(shù)；步長因子；隨機移動參數(shù)。

Step2.利用立方映射初始化種群得到total個初始解，并計算出所有螢火蟲的熒光度。

Step3.對比螢火蟲的熒光度，確定熒光度最好的螢火蟲，根據相對熒光度以及螢火蟲的相對吸引度確定其他螢火蟲的移動方向。

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

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

Step6.根據更新后螢火蟲的位置重新計算熒光度。

Step7.當計算結果滿足精度或迭代次數(shù)達到最大時，則轉Step8，否則轉Step3，且迭代次數(shù)加1進行下一次迭代。

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

5 仿真結果

5.1 改進螢火蟲算法（IFA）的仿真結果

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

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

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

圖4 IFA趨勢曲線Fig.4 IFA Trend Curve

圖5 線纜路徑Fig.5 Cable Route

5.2 與其他人工智能算法的對比

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

表1 算法對比Tab.1 Comparison of Algorithms

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

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

圖6 趨勢曲線對比Fig.6 Comparison of Trend Curves

6 結語

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

［1］劉瀟，劉檢華，劉佳順.基與改進隨機路徑圖的分支線纜自動布線技術［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的三維自動布線技術研究［J］.計算機工程與應用，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］李春泉，徐楚，張明.基于輪廓擴展方法的電氣線纜布線技術研究［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］李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法［J］.系統(tǒng)工程理論于實踐，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］周燕，劉培玉，趙靜.基與自適應慣性權重的混沌粒子群算法［J］.山東大學學報：理學版，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.）