基于螞蟻算法的PCB板路徑優(yōu)化研究

中北大學(xué)信息與通信工程學(xué)院 劉 鵬 姜 偉 劉新妹 殷俊齡

引言

在印刷電路板（PCB）焊接生產(chǎn)、故障檢測(cè)以及維修過程中，現(xiàn)行以人工方式為主的路徑規(guī)劃方法缺乏嚴(yán)格的數(shù)學(xué)論證，特別在生產(chǎn)過程中由此制定的規(guī)劃方案存在很大的隨機(jī)性，經(jīng)常發(fā)生自動(dòng)化作業(yè)順序不合理的情況，導(dǎo)致生產(chǎn)周期過長，影響整條生產(chǎn)線的生產(chǎn)。如何根據(jù)PCB板焊接的實(shí)際工作情況以及通用路徑規(guī)劃技術(shù)來尋求一種高效的路徑規(guī)劃解決方案，已成為PCB板制造業(yè)中的一個(gè)研究重點(diǎn)。

1.實(shí)際焊接生產(chǎn)過程分析

PCB板焊接過程中，必須先獲得PCB板每一個(gè)焊點(diǎn)的確切位置和類型信息（以下統(tǒng)稱為焊點(diǎn)信息）。獲得焊點(diǎn)信息的方法有三種：

1）人機(jī)視角方式。這種方式的特點(diǎn)是設(shè)備附加成本低，易于實(shí)現(xiàn)。適用于印刷線路板上焊點(diǎn)數(shù)少或產(chǎn)品批量大的情況。但其效率較低，示教時(shí)有漏點(diǎn)的可能性，操作者勞動(dòng)強(qiáng)度大。

2）圖像處理方式。自動(dòng)化程度高，能適用各種情況，但設(shè)備成本高、復(fù)雜及調(diào)研周期長。

3）從CAD文件提取方式。印刷線路板的制造目前已廣泛采用計(jì)算機(jī)輔助設(shè)計(jì)方法。在印刷線路板的輸出磁盤文件中已包含了各元器件及焊點(diǎn)的類型、位置等完整信息。

本文將采取從CAD文件提取焊點(diǎn)信息，通過逐點(diǎn)焊接的方式，控制系統(tǒng)驅(qū)動(dòng)工作臺(tái)移動(dòng)，當(dāng)待焊焊點(diǎn)到達(dá)激光斑點(diǎn)位置時(shí)工作臺(tái)停止，系統(tǒng)按給定的加熱功率及時(shí)間輸出激光，此焊點(diǎn)焊接完成后，再移動(dòng)到下一個(gè)焊點(diǎn)繼續(xù)以相應(yīng)的規(guī)范焊接，一直到所有焊點(diǎn)焊接完畢。顯然當(dāng)焊點(diǎn)的焊接規(guī)范給定后，全部焊接時(shí)間決定于總的行走路線。從焊接效率最高的角度分析，希望得到總的行走時(shí)間和行走路徑最短的方案，但實(shí)現(xiàn)時(shí)費(fèi)時(shí)巨大，首先要計(jì)算所有兩焊點(diǎn)之間的距離，其次所有可能路徑的計(jì)算也需要數(shù)目很大的加法運(yùn)算，因此計(jì)算時(shí)間隨著焊點(diǎn)數(shù)的增加而劇增。

2.優(yōu)化方案的技術(shù)路線

在焊接PCB板工作過程中，焊槍從原始位置出發(fā)，途徑各個(gè)焊點(diǎn)，最終回到原始位置，完成一個(gè)工作循環(huán)。這與TSP旅行商問題的數(shù)學(xué)模型非常類似，不同之處在于在PCB板焊接過程中還要考慮到焊槍和工件或夾具的干涉問題，這方面可以用增加虛焊點(diǎn)修正的方法加以解決。據(jù)此確定如下解決方案技術(shù)路線：

1）將問題轉(zhuǎn)化成TSP旅行商問題的數(shù)學(xué)模型，并使用相應(yīng)算法得到優(yōu)化焊接順序。

2）根據(jù)焊接工藝以及干涉等情況，加以修正。

3）最終確定合理焊接順序。

3.優(yōu)化算法論證

旅行商問題的一般描述為：旅行商從駐地出發(fā)，經(jīng)過所有目的地一次后返回原地，應(yīng)如何安排其旅行路線，才能使旅行距離最小。旅行商問題存在多種類型的求解算法，目前較為先進(jìn)的多為仿生算法，其中包括窮蟻群算法、遺傳算法和模擬退火法，神經(jīng)網(wǎng)絡(luò)法等。在此我們將分析目前最常用的3種算法：蟻群算法（ACS）、遺傳算法（GA）和模擬退火法（SA）優(yōu)化方法各自的特點(diǎn)，并對(duì)其收斂速度和優(yōu)化精度進(jìn)行論證對(duì)比。

表1 3種算法在5組隨機(jī)城市上的仿真結(jié)果[2]

表2 3種算法在3組幾何問題上的仿真結(jié)果

圖1 蟻群算法流程圖

圖2 收斂曲線

圖3 路徑優(yōu)化結(jié)果

在這里采用蟻群系統(tǒng)作為蟻群算法的代表，與遺傳算法以及模擬退火算法進(jìn)行比較?？紤]兩組實(shí)驗(yàn)：第1組由5個(gè)隨機(jī)產(chǎn)生的50個(gè)城市TSP問題組成；第2組包括3個(gè)在50和100個(gè)城市之間的幾何問題。在這兩組TSP測(cè)試問題上進(jìn)行實(shí)驗(yàn)是很重要的，因?yàn)檫@兩組問題具有結(jié)構(gòu)上的不同，這使得它們對(duì)于一個(gè)算法實(shí)現(xiàn)起來很困難，而同時(shí)對(duì)于另一個(gè)算法卻很簡單，保證了對(duì)比的公平性。表l給出了在隨機(jī)問題上運(yùn)行的結(jié)果，黑體數(shù)字為已知最優(yōu)解。

收斂速度是評(píng)價(jià)一個(gè)算法好壞的重要方面，因此我們對(duì)3種算法的收斂速度進(jìn)行比較。從表2中可以看出，在同規(guī)模的測(cè)試問題上3種算法收斂到最優(yōu)解的迭代次數(shù)相差很大。在Oliver30中，蟻群系統(tǒng)收斂到最優(yōu)解是在第1470代，遺傳算法是在第3200代，而模擬退火法是24617代。隨著城市規(guī)模的增大，差距也隨之增大。在Eil75中.蟻群系統(tǒng)收斂到最優(yōu)解是在第4393代，遺傳算法是在第80000代，而模擬退火法的收斂速度最慢，在第173250代才收斂到最優(yōu)解。以上結(jié)果表明，蟻群算法的收斂速度最快。

以上兩個(gè)的實(shí)驗(yàn)結(jié)果對(duì)比顯示。ACS算法在求解節(jié)點(diǎn)數(shù)為5-100的組合優(yōu)化問題上，選用合適的參數(shù)，其優(yōu)化結(jié)果普遍好于遺傳算法（GA）和模擬退火算法（SA）。

4.蟻群算法及技術(shù)方案的實(shí)現(xiàn)

蟻群算法的原理和計(jì)算流程如圖1所示。

假設(shè)有n個(gè)待焊點(diǎn)，m只螞蟻，τ（i,j）（i,j=1,2,…,n)表示順序焊接的焊點(diǎn)i和j之間的殘余信息量，初始時(shí)刻t（i,j)=c（c是常數(shù))，螞蟻k（k=1，2，…，m)在運(yùn)動(dòng)過程中根據(jù)信息量選擇下一個(gè)要焊接的焊點(diǎn)，正在焊接的焊點(diǎn)r利用以下狀態(tài)規(guī)則選擇下一個(gè)要焊接的焊點(diǎn)S：

其中：allowed（k)表示螞蟻k選擇未焊接的焊點(diǎn)集合，η（I,j)表示t時(shí)刻焊接焊點(diǎn)i時(shí)選擇焊點(diǎn)j為下一批焊接的焊點(diǎn)的啟發(fā)函數(shù)，q為[0,1]的隨機(jī)數(shù)，

q0∈（0,1)為實(shí)現(xiàn)變異的參數(shù)，β為參數(shù)表示啟發(fā)函數(shù)，

當(dāng)每只螞蟻都按狀態(tài)規(guī)則確定了下一步要焊接的焊點(diǎn)，局部修改規(guī)則為：

其中：ρ∈（0,1)，

τ0=（Lmin*m)-1，Lmin為記錄中的螞蟻?zhàn)钚〉耐旯r(shí)間。

當(dāng)所有的螞蟻全部運(yùn)動(dòng)結(jié)束后，記錄當(dāng)前循環(huán)中所有螞蟻中的最小完工時(shí)間Lmin，全局修改規(guī)則為：τ（r,s)=（1-α)*τ（r,s)+α* L-1min

α∈（0,1）

根據(jù)上述流程在MATLAB中編寫了相應(yīng)的優(yōu)化程序，將焊點(diǎn)坐標(biāo)導(dǎo)入程序。選20個(gè)待測(cè)焊點(diǎn)路徑順序?yàn)閇16 11 15 20 17 18 7 13 3 1 19 12 8 6 10 9 14 5 2 4]，所用時(shí)間為65.290162S，結(jié)果如圖2、圖3所示。

最后根據(jù)焊接工藝特點(diǎn)及具體情況進(jìn)行適當(dāng)?shù)男拚?，獲得最終結(jié)果。

結(jié)論

當(dāng)蟻群算法用于PCB板的焊接路徑優(yōu)化時(shí)，螞蟻之間通過一種簡單的傳遞信息的方式—信息素來完成尋優(yōu)工作。其核心問題是：1）選擇機(jī)制：信息素越多的路徑，被選中的概率越大；2）信息素更新機(jī)制：路徑越短，跡增加越快；3）協(xié)作機(jī)制：個(gè)體之間通過信息素進(jìn)行交流。

經(jīng)過對(duì)PCB板的焊接路徑優(yōu)化，最終仿真結(jié)果比未優(yōu)化的生產(chǎn)時(shí)間少15s，使得該P(yáng)CB板工位的生產(chǎn)效率得以提高。同時(shí)也證明基于蟻群算法的PCB板路徑規(guī)劃方法是有效的。

[1]王濤,俞承芳.一種改進(jìn)的粒子群算法在PCB板元件檢測(cè)中的應(yīng)用[J].微電子學(xué)與計(jì)算機(jī),2007,24(12).

[2]李士勇,陳永強(qiáng),李研.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004.

[3]王穎,謝劍英.一種自適應(yīng)蟻群算法及其仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2002,14(1).