基于DSO算法的印刷電路板焊點測試路徑優化

吳亞帥，劉新妹,2*，殷俊齡，高志亨

(1.中北大學信息與通信工程學院，太原 030051;2.中北大學電子測試技術國家重點試驗室，太原 030051)

目前針對印刷電路板(pint circuit board,PCB)自動檢測系統研究，多集中在圖像處理和運動控制[1-2]等方面，通過對PCB焊點檢測路徑規劃的研究來尋求一種高效的檢測路徑的算法研究尚少[3-4]。而今PCB的制造已廣泛采用計算機輔助設計，在其輸出磁盤文件中已包含著各元器件及焊點的類型、位置等信息[5-6]。針對其焊點的質量檢測，目前較先進的辦法是控制PCB自動測試平臺的探針進行逐點測試，將探針連接測試儀器儀表，將測試數據返回給測試系統與設計文件的焊點信息進行比較，判斷被測單元是否故障，并給出故障原因及建議[7]。

整個過程是在已知所有待測焊點信息的前提下合理規劃測試順序，遍歷所有待測焊點后完成全部測試，測試時長取決于遍歷行走路線的長短[8-9]。從檢測效率最高的角度來講是，得到的總行走時間和行走路徑最短是最優方案。

而PCB板測試中，通常探針從原始位置出發，途經各個被測焊點，最終回到原始位置，完成一個工作循環。這與旅行商問題(traveling salesman problem,TSP)的數學模型有著相似之處，尤其效果突出的是群智能算法[10]。焦青等[11]將蟻群(ant colony optimization,ACO)算法應用在電能質量擾動源定位中，實現了擾動方向信息不可靠時的準確定位；張濤等[12]將遺傳算法(genetic algorithm,GA)應用在地震救援的路徑優化問題中，結合啟發式規則并引入多項決定因素，有效地提高了地震救援的定位精度；孫秀巧等[13]構建了高速公路巡邏車路徑和調度優化模型，將連通的路徑作為染色體，基于改進的GA算法和模擬退火(simulated annealing,SA)算法，并引入動態規劃算法進行尋優求解，顯著的提高了計算效率和響應時間；李景文等[14]對模擬退火算法進行改進，以旅游效用值為目標函數提出一種改進的旅游路線定制模型，加快了運行速度且更容易提供合理的旅游路線；陶麗華等[15]和趙鐵軍等[16]將遺傳算法應用在點焊機器人的路徑規劃中，取得了不俗的優化效果。上述算法應用到不同領域，其性能的優劣程度也不盡相同，因此在進行試際問題的求解時，要根據所求目標問題的特性選取合適的優化算法[17-18]。

驢和走私者(donkey and smuggler optimization,DSO)算法是Shamsaldin等[19]在2019年提出的一種基于種群的新型智能優化算法，該算法合并了兩個物種(驢和走私者)之間的溝通和協作行為，建立了一種新模型，用來尋找路徑協同的工作方式。DSO算法由于結構簡單、無參數無派生的特性而易于實現，應用于旅行商問題，網絡路由尋優等優化問題的求解中，且表現出較好的性能優勢[20]。因此，現提出基于DSO算法優化PCB焊點測試路徑，在MATLAB平臺分別對DSO算法、ACO算法、GA算法和SA算法對TSP標準數據集中的Bays29和Kroa100進行測試求解，將各算法的試驗結果進行對比來驗證提出的方法有效性，最后通過具體對實際PCB焊點的測試進行路徑優化，降低檢測時間，提高檢測效率。

1 PCB焊點測試路徑優化模型

PCB焊點的測試過程與測試路徑可描述為：測試機的探針從被設定的第一個焊點開始，沿程序指定的路徑對焊點依次進行測試，直到PCB上所有的焊點都被檢測完畢。

結合TSP問題模型，將PCB焊點測試路徑的優化過程歸納如下。

(1)設定變量。設有n個待測焊點的集合D={x1,x2,… ,xn}，dpq表示任意兩個待測焊點xp、xq之間的直線距離。

(2)約束條件。探針遍歷所有該PCB板上的焊點，且每個待測焊點只被測試一次，測試完所有焊點之后，探針回到起點以等待下一次測試。

(1)

2 DSO算法及路徑優化設計

DSO是受驢的搜索行為啟發，通過模擬驢的運輸行為，建立兩種模式來實現算法中的搜索行為和路徑選擇。走私者通過查找所有可能路徑，然后確定最佳路徑;求出的最優路徑的適應性發生變化的情況下，利用驢的多種行為求解次優解。

2.1 驢的社會行為

驢具有一系列的社會行為，在一定程度上可以將它們與其他動物區分開來，如具有良好的記憶力和快速輕松學習的能力，走私者可以通過一系列的訓練行為，從而使驢可以獨立地進行活動。結合相關材料，驢具有的社會行為可以總結如下。

(1)逃避過去使它們痛苦的人或經歷事件。

(2)在它們感到危險時戰斗或防御機制將會被觸發，當情況達到驢再也無法忍受的程度時將會自殺。

(3)當遇到困難或需要幫助時會互相支持。

即可以簡單歸納為逃離、面對和自殺、面對和支持。而DSO算法就是通過模擬驢和走私者的行為，利用走私者和驢的一些行為構造了一個由兩部分組成的算法，可以尋找到最佳解決方案并且能夠對任何發生變化的情況作出反應以維持最佳解決方案。

2.2 DSO算法

DSO主要建立一種模仿驢的社會行為的新模型，兩種模式分別為走私者模式(非適應部分)、驢子模式(自適應部分)。在算法的走私者部分中，走私者在理想情況下在一次迭代中評估所有可能的解決方案，并根據其適應性對解決方案進行排序后確定最佳解決方案。在驢子模式中，嘗試維持最佳解決方案，以防萬一它不再適用。且該算法可保持評估過程的運行并更新解決方案的適用性，并且將繼續評估種群并根據算法程序更新最佳解決方案。

DSO算法的主要實現部分如下。

(1)走私者模型：首先進行參數初始化，確定每個解決方案的參數，利用式(2)計算每個可能解的適應度，其中適應度函數是問題中的全體解與其適應度之間的一種對應關系，采取最優選取的準則，并將選擇的最優解傳遞至驢子部分。

(2)

式(2)中：xij為可能的解；i為可能解的數量；j、J為與之成正比的每個可能解的參數數量；z、Z為與之成反比的每個可能解的參數數量。

(2)驢子模式：根據適應度評估當前解決方案，如果有擁堵跡象，進行以下行為選擇。

① 逃離：重新評估所有可能解的適應度，并更新最優解。

② 面對和自殺：利用式(3)，確定第2個解決方案，可以作為一個最優解。此步驟無需計算所有可能解的適應度。

bestsolution=f(xi)-f(bestsolution)

(3)

式(3)中：i是可能的解的數量，從可能解的適應度中減去最優解的適應度，將差值最小的解視為新的最優解。

③ 面對和支持：當最優解過載時，使用第2個的解決方案作為最優解(這2種解決解決方案的用途相同)，直到初始的最優解恢復常態。此步驟無需計算所有可能解的適應度。

secondbestsolution=f(bestsolution)-f(xi)

(4)

bestsupport,solution=bestsolution+second,bestsolution

(5)

在式(4)中，將通過從最優解的適用度中減去可能解決方案的適用度來確定將哪個方案作為次優解決方案;在式(5)中，將最優解與次優解決方案結合起來，以生成使用兩條路徑執行一項任務的最佳解決方案。

DSO算法流程框圖如圖1所示。

圖1 DSO算法流程框圖Fig.1 DSO algorithm flow diagram

2.3 PCB焊點測試路徑優化的設計

結合DSO算法的理論，基于MATLAB進行程序設計，將PCB焊點測試路徑的步驟優化如下。

(1)依據PCB板的電路圖，從Altium Designer軟件獲取PCB板上各個元器件的焊點的位置坐標信息。

(2)采用自然數序列1,2,…，N對印制電路板待檢測的焊點的坐標位置進行編號，根據待測焊點的數目N以及坐標信息，計算出各個焊點之間的距離，存放在距離矩陣Dis。

(3)根據距離矩陣Dis，計算前往將每個焊點視為一次出發起點及最后返回的終點所有可能路徑的距離(其中定義適應度的值為抵達所有焊點的距離和)。

(4)根據式(2)進行適應度計算評估，確定從每個焊點出發并返回的最短路徑，每次迭代都重復此步驟，并結合式(3)～式(5)，以確定從不同測試點出發遍歷所有焊點的最短路徑；

(5)由算法比較得出所有出發焊點中的最短路徑，并通過MATLAB軟件輸出最短路徑的仿真軌跡圖及仿真時間。

結合上述步驟，基于DSO算法的PCB焊點測試路徑優化設計流程，如圖2所示。

圖2 基于DSO算法的PCB焊點測試路徑優化流程框圖Fig.2 Flow chart of PCB solder joint test path optimization based on DSO algorithm

3 算法仿真與分析

3.1 算法有效性驗證

為了對比DSO算法、蟻群算法和遺傳算法對 TSP 問題的求解效果。測試數據選擇旅行商問題的公共數據集TSPLIB中的Bays29和KroA100。對比試驗的運行環境均為Windows10系統，測試平臺為MATLAB 2014a，試驗次數為30次。

仿真中，依據上述算法參數設置的規律，經過多次仿真試驗后，各測試算法參數如下：ACO算法中，螞蟻個數為50，信息素重要程度因子為1，啟發函數重要程度因子為5，信息素揮發因子取0.1，信息素釋放總量取1，最大迭代次數是200，迭代次數初值取1；GA算法中，種群個數為100，交叉概率為0.8，變異概率為0.2，最大遺傳代數1 000；SA算法中，降溫速率為0.99，初始溫度2 000，終止溫度0.001，鏈長取400。

結果對比如表1所示。

Bays29數據集經過4種算法運行后的最優路徑軌跡如圖3所示。

KroA100數據集經過DSO、ACO、GA和SA 4種算法運行的最優路徑軌跡如圖4所示。

對比表1及圖3、圖4可得：

(1)在數據的節點規模較小時，基于DSO的算法最優解路徑長度與蟻群算法、遺傳算法三者十分接近；但平均運行時間基于DSO的算法為2.19 s，明顯了快很多。

(2)在數據的節點規模較大時，基于DSO的算法最優解路徑長度為22 698 mm，ACO算法是22 387 mm，GA算法是22 627 mm，SA算法為22 562 mm。可以看出：接近ACO算法、GA算法和SA算法的最優解路徑長度，且平均運行時間為11.26 s，求解速度明顯快與兩者，表明基于DSO的算法耗時短。

表1 Bays29和KroA100數據集由4種算法的求解結果Table 1 The result of solving the Bays29 and KroA100 dataset through different algorithms

圖3 Bays29數據集由不同算法求解后的最優路徑Fig.3 The optimal path of Bays29 data set after being solved by different algorithms

圖4 KroA100數據集由不同算法求解后的最優路徑Fig.4 The optimal path of KroA100 data set after being solved by different algorithms

基于DSO的算法求解過程中耗時少，具有更高的求解速度，可以判定基于DSO的算法在PCB焊點檢測路徑優化中可行且有效。

3.2 PCB實例焊點測試

為驗證上述結果對PCB焊點測試路徑優化的可行性，選尺寸為120 mm×180 mm PCB(圖5)進行仿真測試試驗的驗證。設電路板左下角為坐標原點(見標注)，通過Altium Designer獲取PCB板上待測焊點(88個點)位置坐標信息，按照2.2節路徑優化設計的步驟，對試際PCB焊點的測試路徑測試。

圖5 PCB板試例原理圖Fig.5 PCB schematic diagram

據上得到88個待測焊點的位置分布圖，如圖6所示。

首先，利用隨機初始解生成初始路線，按該路線進行測試，軌跡為50→73→72→8→4→61→85→44→18→88→82→17→79→25→20→24→19→78→7→39→31→81→54→70→64→67→38→32→28→87→37→5→74→68→35→15→30→34→47→6→57→14→13→42→2→1→23→29→45→60→9→49→21→12→51→27→69→41→77→62→36→75→11→52→3→66→63→10→33→46→56→53→40→65→76→55→58→84→83→59→43→22→86→80→16→26→48→71→50，總距離5 907.76 mm，運行時間146.20 s。

焊點初始測試路徑圖如圖7所示。

圖6 待測焊點位置信息分布圖Fig.6 Distribution map of solder joints to be tested

圖7 焊點初始測試路徑Fig.7 Oringinal test path roadmap of solder joints

可見，按照該初始路徑進行檢測，路徑明顯無序，無可尋規律。

通過本設計的DSO算法對被測PCB板進行測試，發現用時最少，距離最短的軌跡為34→33→78→35→36→86→22→17→18→70→31→40→41→32→37→28→27→66→83→58→12→84→67→59→57→25→26→13→24→38→23→45→82→55→29→56→54→44→75→76→62→74→10→73→2→43→11→80→72→77→1→6→5→42→4→47→65→51→64→46→8→3→52→53→9→68→39→14→71→69→30→81→7→48→50→79→49→63→61→60→16→19→15→20→88→85→87→21→34，運行的總距離為1 068.08 mm，運行時間8.14 s。

得到的最佳路線軌跡，如圖8所示。

通過基于DSO的算法按設計的步驟對試際PCB焊點進行測試，總距離由優化前的5 907.76 mm縮短為1 068.08 mm，是原來的18.07%；運行時間由146.20 s 縮短為8.14 s。

圖8 DSO最優路徑軌跡圖Fig.8 Best path trajectory of DSO

對基于DSO的算法，可有效優化PCB自動測試中的焊點檢測路徑，優化后的路徑距離與時間明顯縮短，且效果明顯。

4 結論

基于DSO算法的PCB焊點檢測路徑優化方法對解決PCB自動測試中的路徑優化問題可行有效，且速度快，耗時遠小于蟻群算法、遺傳算法和模擬退火算法。為解決PCB自動測試中的路徑優化問題，提供有效理論依據和解決辦法。