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

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

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

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

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

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

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

1.1 蟻群算法基本原理

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

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

圖1 螞蟻覓食過(guò)程

1.2 環(huán)境建模

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

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

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

(1)

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

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

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

2 TSP問(wèn)題

2.1 基本概念

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

(2)

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

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

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

(3)

(4)

(5)

(6)

xij∈{0,1}

(7)

式中：dij為ij兩點(diǎn)之間的距離。

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

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

圖3 TSP步驟

對(duì)于兩點(diǎn)之間的最短距離，用歐拉公式計(jì)算：

(8)

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

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

(9)

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

2.2 算法流程

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

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

圖4 矩陣表示柵格圖

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

(10)

nij=1/dij

(11)

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

圖5 移動(dòng)方向

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

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

(12)

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

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

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

(13)

(14)

(15)

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

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

3 案例分析

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

圖7 焊點(diǎn)編號(hào)

表1 實(shí)驗(yàn)參數(shù)設(shè)置

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

圖8 考慮ζ的最優(yōu)運(yùn)動(dòng)軌跡

圖9 考慮ζ的收斂曲線

表2 仿真實(shí)驗(yàn)結(jié)果

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

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

圖10 距離矩陣

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

圖12 各代的最短距離與平均距離對(duì)比

4 結(jié)論

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