程 鑫，張 帆，同軍超，張衛(wèi)超

(1.武漢理工大學(xué) 機電工程學(xué)院，湖北 武漢 430070；2.湖北省磁懸浮工程技術(shù)研究中心，湖北 武漢 430070)

印刷電路板(printed cricuit board，PCB)是電子元器件連接的載體，大大減小了布線和裝配差錯[1]。目前PCB板朝著高密度、多層數(shù)、高可靠性等方向發(fā)展，但也使得焊點的焊接越來越困難，尋找通過所有焊點的最優(yōu)路徑成為一個亟待解決的難題。

PCB板上存在多個目標(biāo)焊點以及大電容等阻礙焊接的元件，若不進(jìn)行路徑規(guī)劃，焊頭可能與焊接工件上的障礙物相撞，導(dǎo)致焊頭報廢甚至危及員工安全。按照某種順序在有障礙物的有限環(huán)境中，尋找焊頭通過多個目標(biāo)焊點的最優(yōu)路徑，且在運動過程中能安全、無障礙的繞過所有障礙物[2]。這個難題既要找到使總路程最短的路徑，又要保證焊點與焊點之間路徑的安全性，既涉及到多點路徑規(guī)劃問題，又涉及到焊點避障問題，是一個NP(non-deterministic polynomial,非確定性多項式)問題，對于這個難題的研究有著重要的理論研究價值和廣泛的工程應(yīng)用價值。

多點路徑規(guī)劃問題可歸結(jié)為TSP(traveling salesman problem,旅行商問題)問題，在解決TSP問題上，目前使用的方法有蟻群算法、遺傳算法、粒子群算法等。文獻(xiàn)[3]中應(yīng)用Matlab對蟻群算法和遺傳算法求解TSP問題進(jìn)行對比研究，發(fā)現(xiàn)無論城市個數(shù)多少、城市間距離遠(yuǎn)近，蟻群算法都優(yōu)于遺傳算法。文獻(xiàn)[4]中設(shè)計了一種包含蟻群算法和改進(jìn)PRM(probabilistic road map)算法的融合算法，可一次規(guī)劃多個目標(biāo)點的路徑，但規(guī)劃出來的路徑具有隨機性。文獻(xiàn)[5]將蟻群算法與遺傳算法和粒子群算法對比，蟻群算法可靠性高、適應(yīng)性強、精確度高。文獻(xiàn)[6]先計算點與點之間的最短安全距離，然后找到使總路徑最短的順序，最后進(jìn)行點與點之間的路徑規(guī)劃，這種方法所找到的總路徑不一定最短，且計算量較大。

筆者提出了一種改進(jìn)的蟻群算法來解決在PCB板上焊點焊接最優(yōu)路徑的問題，先對焊頭所處的工作環(huán)境進(jìn)行建模，然后進(jìn)行點與點之間的軌跡規(guī)劃，得出點與點之間最短路徑，最后將多點相互間的最短距離矩陣代入到TSP問題中，得到使總路徑最短的順序及最短路徑的長度。

1 蟻群算法基本原理與環(huán)境建模

1.1 蟻群算法基本原理

蟻群算法其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)最優(yōu)路徑的行為,具有分布計算、信息正反饋和啟發(fā)式搜索的特征，其本質(zhì)實際上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法[7]。在尋找食物的過程中螞蟻會分泌大量信息素，信息素分泌的多少與路經(jīng)長度成反比，而螞蟻在選擇路徑時會根據(jù)狀態(tài)轉(zhuǎn)移概率以較大概率選擇信息素多的路徑[8]，隨著大量螞蟻個體不斷搜索，最優(yōu)路徑上的信息素越來越多，而較長路徑上的信息素會慢慢變少或消失，螞蟻選擇最優(yōu)路徑的概率越大，最終整個蟻群會找出一條最優(yōu)路徑。

圖1表示螞蟻在覓食過程中的3個過程，其中點A為螞蟻蟻穴，點D為食物所在地，四邊形BECF為蟻穴與食物之間的障礙物，螞蟻若想獲得食物，可隨機選擇路徑BEC或BFC。如圖1(b)所示，開始時，兩條路徑上都無信息素，在點A的螞蟻隨機選擇路徑，兩條路徑上螞蟻數(shù)量相等。由于路徑BFC比路徑BEC長度要短一倍，一段時間后，選擇路徑BFC的螞蟻比選擇路徑BEC多一倍，于是路徑BFC上積累的信息素濃度是路徑BEC上積累的信息素濃度的兩倍，隨著時間的推移，螞蟻將以更大的概率選擇路徑BFC，最終所有的螞蟻都會選擇路徑BFC到達(dá)食物目的地，如圖1(c)所示。由此可見，螞蟻覓食是一個正反饋過程。

圖1 螞蟻覓食過程

1.2 環(huán)境建模

針對焊頭的路徑規(guī)劃問題，焊頭實際運行的工作環(huán)境是真實的物理空間，而用來路徑規(guī)劃的空間是虛擬空間，需要將物理空間轉(zhuǎn)換成虛擬空間，抽象出能為建立模型起作用的機理，摒棄掉與建立模型無關(guān)的因素，這個環(huán)節(jié)稱為環(huán)境建模[9]。環(huán)境建模是對焊頭所處工作環(huán)境的有效描述，其質(zhì)量好壞直接影響路徑規(guī)劃的復(fù)雜度以及后續(xù)算法性能的效率。

環(huán)境建?？梢苑譃閮深悾夯诰W(wǎng)絡(luò)或圖的模型和基于柵格的模型[10]?；诰W(wǎng)絡(luò)或圖的建模方法主要有頂點圖像法、自由空間法、廣義錐法，其模型精確度高，適用于對軌跡精度要求高的場合，但其模型建立計算量大，路徑曲線控制難度大，應(yīng)用于實際工程問題還需解決很多問題。基于柵格的模型建立簡單，易在編程中實現(xiàn)，路徑曲線易控制。筆者采用柵格法，假定焊頭的空間信息已知，無障礙物的柵格為可行柵格，焊頭可自由運動，有障礙物的柵格為不可行柵格，焊頭需繞開障礙物運動。

對于柵格的標(biāo)識方法有兩種：直角坐標(biāo)法和序號法。兩者之間是可以相互轉(zhuǎn)換的，其映射關(guān)系為：

(1)

式中：Xi為坐標(biāo)的行；Yi為坐標(biāo)的列；N為柵格序號；K為每行每列的柵格數(shù)；mod為取余，即取N/K的余數(shù)；int為取整，即取N/K的整數(shù)。

采用的工作環(huán)境柵格圖如圖2所示，假定工作環(huán)境為20×20的矩形區(qū)域，按從左向右、從上到下的順序依次標(biāo)記為1，2，…，400，每個序號代表一個柵格，令S={1，2，…，400}來表示柵格序列號，黑色柵格為障礙物，灰色柵格為目標(biāo)焊點，白色柵格為可運行區(qū)域。為避免焊頭與障礙物相撞，焊頭當(dāng)作質(zhì)點忽略不計，障礙物不滿一個柵格按一個柵格處理，且將障礙物向外膨脹，多占用一個柵格，使焊頭能在規(guī)劃好的路徑中暢通無阻。

圖2 工作環(huán)境柵格圖

2 TSP問題

2.1 基本概念

TSP問題即在已知一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經(jīng)過所有頂點的封閉回路。其實質(zhì)就是在一個帶權(quán)重的完全無向圖中，找到一個權(quán)值總和最小的哈密頓回路，且需滿足如下的目標(biāo)函數(shù)：

(2)

式中:vi為城市號，取值為1到n之間的自然數(shù)；d(vi,vj)為城市i與城市j之間的權(quán)值，對于對稱式TSP問題，有d(vi,vj)=d(vj,vi)。

其數(shù)學(xué)模型可表示為：G=(V,E)為賦權(quán)完全圖，V=(1,2,…,n)為頂點合集；E為邊集，各頂點間的距離為Cij，即：

已知Cij>0，i,j∈V，TSP問題的數(shù)學(xué)描述為：

(3)

(4)

(5)

(6)

xij∈{0,1}

(7)

式中：dij為ij兩點之間的距離。

式(3)的目標(biāo)函數(shù)要求距離之和最小；式(4)表示從城市i出發(fā)；式(5)中xij=1表示走過的路線，包括城市i到城市j之間的距離，xij=0表示選擇走別的路線；式(4)和式(5)確保每個城市都會經(jīng)過一次，但不能保證無回頭路。式(6)確保不會走回頭路。

蟻群算法解決TSP問題可靠性高、適應(yīng)性強、精確度高，但不能安全的進(jìn)行多點路徑規(guī)劃。常用的解決TSP問題的步驟如圖3所示。

圖3 TSP步驟

對于兩點之間的最短距離，用歐拉公式計算：

(8)

式中：(xi，yi),(xj,yj)分別為i點和j點的坐標(biāo)。

當(dāng)兩點之間有障礙物時，兩者之間距離發(fā)生改變，且取決于障礙物的大小、位置和個數(shù)，因此引進(jìn)環(huán)境復(fù)雜度系數(shù)ζ，當(dāng)ζ=1時即為普通的TSP問題。

(9)

在PCB板上焊點和障礙物是隨機分布的，點與點之間的復(fù)雜度系數(shù)不一樣，兩點間最短路徑需重新規(guī)劃，因此在解決焊點避障的TSP問題時，需先解決避障問題求得各焊點之間的相互距離，再進(jìn)一步解決TSP問題，完成多點間的軌跡規(guī)劃。

2.2 算法流程

為了解決避障問題求得各焊點之間的相互距離，在各焊點之間采用蟻群算法，初始化參數(shù)時對焊點、障礙物的位置、大小進(jìn)行標(biāo)識，得到焊點的個數(shù)n，i為大于等于1小于n的正整數(shù)，j為大于等于2小于等于n的正整數(shù)，再構(gòu)造解空間，在柵格環(huán)境中螞蟻按照狀態(tài)轉(zhuǎn)移概率選擇下一節(jié)點，最后更新信息素。當(dāng)達(dá)到目標(biāo)條件后，輸出距離矩陣并記錄路徑信息，帶入到TSP問題中求解。其具體步驟為：

(1)初始化參數(shù)。對工作環(huán)境的柵格圖用0和1組成的矩陣來表示，0表示可行柵格，1表示不可行柵格，如圖4所示。設(shè)置螞蟻數(shù)量m，信息素啟發(fā)因子α，期望啟發(fā)因子β，信息素?fù)]發(fā)因子ρ，迭代次數(shù)Nc、目標(biāo)焊點柵格序號。初始化可選節(jié)點D={0,1,2,…,n-1},爬行路線和爬行路線長度。將禁忌表Bk(螞蟻k當(dāng)前走過的柵格點)初始化為空集，其中k為1，2，…,m。

圖4 矩陣表示柵格圖

(2)構(gòu)造解空間。在已初始化的柵格圖中，將螞蟻放在初始目標(biāo)焊點，其按照狀態(tài)轉(zhuǎn)移概率選擇下一個節(jié)點，直至到達(dá)下一個目標(biāo)焊點。在第t次迭代中，螞蟻k由節(jié)點i選擇下一個節(jié)點j的轉(zhuǎn)移概率為：

(10)

nij=1/dij

(11)

式中:allowk為下一個時刻螞蟻k從當(dāng)前節(jié)點i到下一個所有可到達(dá)節(jié)點的集合；τij為路徑(i,j)的信息素濃度；nij為啟發(fā)信息；dij為當(dāng)前節(jié)點和待選節(jié)點j的歐式距離;α為信息素啟發(fā)因子；β為期望啟發(fā)因子。

圖5 移動方向

(3)更新信息素。在每一只螞蟻選擇某一節(jié)點后將會對該節(jié)點的信息素進(jìn)行更新，稱為實時信息素更新，更新方式為：

τij(t+1)=(1-ρ)τij(t)+ρτ0

(12)

式中：τ0為信息素初始值；ρ為區(qū)間[0,1]的信息素?fù)]發(fā)因子。

在蟻群完成一次迭代后，所有螞蟻到達(dá)了目標(biāo)焊點，對蟻群走過路徑上的信息素進(jìn)行更新，其他路徑上的殘留信息素被揮發(fā)，這種路徑信息素更新的方法為：

τij(t+1)=(1-ρ)τij(t)Δτij

(13)

(14)

(15)

本文采用的算法執(zhí)行流程如圖6所示。

圖6 改進(jìn)蟻群算法流程

3 案例分析

筆者采用柵格法來研究焊頭在二維空間上的路徑規(guī)劃，對圖2中的所有目標(biāo)焊點按從左到右、從上到下的順序進(jìn)行編號，焊點編號如圖7所示。為驗證蟻群算法的準(zhǔn)確性，采用Matlab對從S5點到S6點、從S3到S4點、從S1到S7點進(jìn)行路徑規(guī)劃仿真實驗。在仿真過程中，所設(shè)置的實驗參數(shù)如表1所示?？紤]環(huán)境復(fù)雜度ζ的最優(yōu)運動軌道和收斂曲線如圖8和圖9所示。

圖7 焊點編號

表1 實驗參數(shù)設(shè)置

從圖8和圖9可知，自起點出發(fā)，找到了一條避開所有障礙物的最短路徑，均在最大迭代次數(shù)前達(dá)到了穩(wěn)定狀態(tài)。仿真實驗結(jié)果如2所示，從表2可知，隨著距離越長達(dá)到穩(wěn)定的迭代次數(shù)增加，花費的總時間增加，且由于環(huán)境復(fù)雜度ζ的存在，迭代次數(shù)也隨之增加，總時間進(jìn)一步增加，穩(wěn)定性越來越差。由于障礙物的大小、位置和個數(shù)的不同，造成的環(huán)境復(fù)雜度ζ不同，導(dǎo)致規(guī)劃的軌跡最優(yōu)長度難以預(yù)測，因此需要對所有焊點進(jìn)行避障處理。

圖8 考慮ζ的最優(yōu)運動軌跡

圖9 考慮ζ的收斂曲線

表2 仿真實驗結(jié)果

對如圖7所示的所有目標(biāo)焊點進(jìn)行避障處理后，計算出各焊點之間的最短距離，焊點i到焊點j與焊點j到焊點i的最短距離相等，所得到的目標(biāo)矩陣如圖10所示，為對稱矩陣。為保證分母不為0，特將對角線上的元素修正為一個非常小的正數(shù)10-4。

在經(jīng)過多次迭代計算后，得到優(yōu)化路徑和各代的最短距離與平均距離，如圖11和圖12所示。根據(jù)圖11和圖12可知，最短路徑為：S7-S4-S2-S5-S3-S1-S6-S9-S8-S7，其長度為65.941 126,在尋優(yōu)過程中快速找到最短安全路徑。

圖10 距離矩陣

圖11 蟻群算法優(yōu)化路徑

圖12 各代的最短距離與平均距離對比

4 結(jié)論

針對印刷電路板上的焊點焊接問題，為了使焊頭能按照某種順序在有障礙物的有限環(huán)境中，找到一條通過多個目標(biāo)焊點的最優(yōu)路徑，且在運動過程中能安全、無障礙的繞過所有障礙，筆者在蟻群算法解決TSP問題的基礎(chǔ)上，提出一種精度高、安全性好的多目標(biāo)多障礙路徑規(guī)劃的改進(jìn)蟻群算法，該方法能精確地計算出點與點之間的最短安全距離，再根據(jù)點與點之間的最短安全距離得到遍歷所有目標(biāo)點的最短安全路徑。經(jīng)過仿真驗證，證實了該方法的可行性和有效性，能在尋優(yōu)過程中快速找到最短安全路徑，克服了目前TSP問題中未考慮安全性的難題。