基于DSO算法的印刷電路板焊點測試路徑優(yōu)化

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

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

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

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

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

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

1 PCB焊點測試路徑優(yōu)化模型

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

結(jié)合TSP問題模型，將PCB焊點測試路徑的優(yōu)化過程歸納如下。

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

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

(1)

2 DSO算法及路徑優(yōu)化設(shè)計

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

2.1 驢的社會行為

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

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

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

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

即可以簡單歸納為逃離、面對和自殺、面對和支持。而DSO算法就是通過模擬驢和走私者的行為，利用走私者和驢的一些行為構(gòu)造了一個由兩部分組成的算法，可以尋找到最佳解決方案并且能夠?qū)θ魏伟l(fā)生變化的情況作出反應(yīng)以維持最佳解決方案。

2.2 DSO算法

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

DSO算法的主要實現(xiàn)部分如下。

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

(2)

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

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

① 逃離：重新評估所有可能解的適應(yīng)度，并更新最優(yōu)解。

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

bestsolution=f(xi)-f(bestsolution)

(3)

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

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

secondbestsolution=f(bestsolution)-f(xi)

(4)

bestsupport,solution=bestsolution+second,bestsolution

(5)

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

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

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

2.3 PCB焊點測試路徑優(yōu)化的設(shè)計

結(jié)合DSO算法的理論，基于MATLAB進行程序設(shè)計，將PCB焊點測試路徑的步驟優(yōu)化如下。

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

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

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

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

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

結(jié)合上述步驟，基于DSO算法的PCB焊點測試路徑優(yōu)化設(shè)計流程，如圖2所示。

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

3 算法仿真與分析

3.1 算法有效性驗證

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

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

結(jié)果對比如表1所示。

Bays29數(shù)據(jù)集經(jīng)過4種算法運行后的最優(yōu)路徑軌跡如圖3所示。

KroA100數(shù)據(jù)集經(jīng)過DSO、ACO、GA和SA 4種算法運行的最優(yōu)路徑軌跡如圖4所示。

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

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

(2)在數(shù)據(jù)的節(jié)點規(guī)模較大時，基于DSO的算法最優(yōu)解路徑長度為22 698 mm，ACO算法是22 387 mm，GA算法是22 627 mm，SA算法為22 562 mm?？梢钥闯觯航咏麬CO算法、GA算法和SA算法的最優(yōu)解路徑長度，且平均運行時間為11.26 s，求解速度明顯快與兩者，表明基于DSO的算法耗時短。

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

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

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

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

3.2 PCB實例焊點測試

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

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

據(jù)上得到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

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

通過本設(shè)計的DSO算法對被測PCB板進行測試，發(fā)現(xiàn)用時最少，距離最短的軌跡為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的算法按設(shè)計的步驟對試際PCB焊點進行測試，總距離由優(yōu)化前的5 907.76 mm縮短為1 068.08 mm，是原來的18.07%；運行時間由146.20 s 縮短為8.14 s。

圖8 DSO最優(yōu)路徑軌跡圖Fig.8 Best path trajectory of DSO

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

4 結(jié)論

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