基于螞蟻算法的PCB板路徑優化研究

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

引言

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

1.實際焊接生產過程分析

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

1）人機視角方式。這種方式的特點是設備附加成本低，易于實現。適用于印刷線路板上焊點數少或產品批量大的情況。但其效率較低，示教時有漏點的可能性，操作者勞動強度大。

2）圖像處理方式。自動化程度高，能適用各種情況，但設備成本高、復雜及調研周期長。

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

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

2.優化方案的技術路線

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

1）將問題轉化成TSP旅行商問題的數學模型，并使用相應算法得到優化焊接順序。

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

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

3.優化算法論證

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

表1 3種算法在5組隨機城市上的仿真結果[2]

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

圖1 蟻群算法流程圖

圖2 收斂曲線

圖3 路徑優化結果

在這里采用蟻群系統作為蟻群算法的代表，與遺傳算法以及模擬退火算法進行比較。考慮兩組實驗：第1組由5個隨機產生的50個城市TSP問題組成；第2組包括3個在50和100個城市之間的幾何問題。在這兩組TSP測試問題上進行實驗是很重要的，因為這兩組問題具有結構上的不同，這使得它們對于一個算法實現起來很困難，而同時對于另一個算法卻很簡單，保證了對比的公平性。表l給出了在隨機問題上運行的結果，黑體數字為已知最優解。

收斂速度是評價一個算法好壞的重要方面，因此我們對3種算法的收斂速度進行比較。從表2中可以看出，在同規模的測試問題上3種算法收斂到最優解的迭代次數相差很大。在Oliver30中，蟻群系統收斂到最優解是在第1470代，遺傳算法是在第3200代，而模擬退火法是24617代。隨著城市規模的增大，差距也隨之增大。在Eil75中.蟻群系統收斂到最優解是在第4393代，遺傳算法是在第80000代，而模擬退火法的收斂速度最慢，在第173250代才收斂到最優解。以上結果表明，蟻群算法的收斂速度最快。

以上兩個的實驗結果對比顯示。ACS算法在求解節點數為5-100的組合優化問題上，選用合適的參數，其優化結果普遍好于遺傳算法（GA）和模擬退火算法（SA）。

4.蟻群算法及技術方案的實現

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

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

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

q0∈（0,1)為實現變異的參數，β為參數表示啟發函數，

當每只螞蟻都按狀態規則確定了下一步要焊接的焊點，局部修改規則為：

其中：ρ∈（0,1)，

τ0=（Lmin*m)-1，Lmin為記錄中的螞蟻最小的完工時間。

當所有的螞蟻全部運動結束后，記錄當前循環中所有螞蟻中的最小完工時間Lmin，全局修改規則為：τ（r,s)=（1-α)*τ（r,s)+α* L-1min

α∈（0,1）

根據上述流程在MATLAB中編寫了相應的優化程序，將焊點坐標導入程序。選20個待測焊點路徑順序為[16 11 15 20 17 18 7 13 3 1 19 12 8 6 10 9 14 5 2 4]，所用時間為65.290162S，結果如圖2、圖3所示。

最后根據焊接工藝特點及具體情況進行適當的修正，獲得最終結果。

結論

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

經過對PCB板的焊接路徑優化，最終仿真結果比未優化的生產時間少15s，使得該PCB板工位的生產效率得以提高。同時也證明基于蟻群算法的PCB板路徑規劃方法是有效的。

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

[2]李士勇,陳永強,李研.蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社,2004.

[3]王穎,謝劍英.一種自適應蟻群算法及其仿真研究[J].系統仿真學報,2002,14(1).