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

(1.中北大學(xué)信息與通信工程學(xué)院，太原 030051;2.中北大學(xué)電子測(cè)試技術(shù)國家重點(diǎn)試驗(yàn)室，太原 030051)

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

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

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

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

1 PCB焊點(diǎn)測(cè)試路徑優(yōu)化模型

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

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

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

(2)約束條件。探針遍歷所有該P(yáng)CB板上的焊點(diǎn)，且每個(gè)待測(cè)焊點(diǎn)只被測(cè)試一次，測(cè)試完所有焊點(diǎn)之后，探針回到起點(diǎn)以等待下一次測(cè)試。

(1)

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

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

2.1 驢的社會(huì)行為

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

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

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

(3)當(dāng)遇到困難或需要幫助時(shí)會(huì)互相支持。

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

2.2 DSO算法

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

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

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

(2)

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

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

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

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

bestsolution=f(xi)-f(bestsolution)

(3)

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

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

secondbestsolution=f(bestsolution)-f(xi)

(4)

bestsupport,solution=bestsolution+second,bestsolution

(5)

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

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

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

2.3 PCB焊點(diǎn)測(cè)試路徑優(yōu)化的設(shè)計(jì)

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

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

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

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

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

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

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

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

3 算法仿真與分析

3.1 算法有效性驗(yàn)證

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

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

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

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

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

對(duì)比表1及圖3、圖4可得：

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

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

表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的算法求解過程中耗時(shí)少，具有更高的求解速度，可以判定基于DSO的算法在PCB焊點(diǎn)檢測(cè)路徑優(yōu)化中可行且有效。

3.2 PCB實(shí)例焊點(diǎn)測(cè)試

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

圖5 PCB板試?yán)韴DFig.5 PCB schematic diagram

據(jù)上得到88個(gè)待測(cè)焊點(diǎn)的位置分布圖，如圖6所示。

首先，利用隨機(jī)初始解生成初始路線，按該路線進(jìn)行測(cè)試，軌跡為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，運(yùn)行時(shí)間146.20 s。

焊點(diǎn)初始測(cè)試路徑圖如圖7所示。

圖6 待測(cè)焊點(diǎn)位置信息分布圖Fig.6 Distribution map of solder joints to be tested

圖7 焊點(diǎn)初始測(cè)試路徑Fig.7 Oringinal test path roadmap of solder joints

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

通過本設(shè)計(jì)的DSO算法對(duì)被測(cè)PCB板進(jìn)行測(cè)試，發(fā)現(xiàn)用時(shí)最少，距離最短的軌跡為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，運(yùn)行的總距離為1 068.08 mm，運(yùn)行時(shí)間8.14 s。

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

通過基于DSO的算法按設(shè)計(jì)的步驟對(duì)試際PCB焊點(diǎn)進(jìn)行測(cè)試，總距離由優(yōu)化前的5 907.76 mm縮短為1 068.08 mm，是原來的18.07%；運(yùn)行時(shí)間由146.20 s 縮短為8.14 s。

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

對(duì)基于DSO的算法，可有效優(yōu)化PCB自動(dòng)測(cè)試中的焊點(diǎn)檢測(cè)路徑，優(yōu)化后的路徑距離與時(shí)間明顯縮短，且效果明顯。

4 結(jié)論

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