基于變鄰域蟻群算法的自動光學(xué)檢測路徑規(guī)劃

鄧 璘，王 琳，盛步云，蕭 箏+

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.武漢理工大學(xué) 數(shù)字制造湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070)

0 引 言

路徑規(guī)劃問題是一個NP難問題，可采用傳統(tǒng)算法、圖形學(xué)算法和智能仿生學(xué)算法進(jìn)行求解[1]。智能仿生學(xué)算法是目前主流的路徑規(guī)劃求解方法，主要包括：蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法、遺傳算法等[2-4]。針對自動光學(xué)檢測系統(tǒng)中的路徑規(guī)劃問題，近年來相關(guān)學(xué)者提出的解決方法有：以印刷電路板鉆孔和焊點(diǎn)為檢測對象，利用改進(jìn)的模擬退火算法和粒子群算法進(jìn)行取像窗口檢測路徑規(guī)劃[5,6]；利用混合遺傳算法在規(guī)劃取像窗口訪問路徑時通過修改基因結(jié)構(gòu)及遺傳算子等方法實(shí)現(xiàn)檢測路徑規(guī)劃[6-8]。上述方法均取得了一定的成效，但仍存在收斂速度慢和未考慮取像窗口位置調(diào)整對檢測路徑的影響等問題。

針對上述問題，本文利用蟻群算法在路徑規(guī)劃問題中具有尋優(yōu)能力強(qiáng)、魯棒性高等特點(diǎn)，在蟻群算法的基礎(chǔ)上提出一種基于變鄰域蟻群算法的自動光學(xué)檢測路徑規(guī)劃方法。使用變鄰域路徑搜索對蟻群算法進(jìn)行改進(jìn)，在更大的搜索空間中以更高的搜索效率獲得最佳的取像窗口訪問順序；在此基礎(chǔ)上，通過分析由3個取像窗口組成的三元鄰域窗口組的幾何位置關(guān)系，采用變鄰域窗口位置調(diào)整方法解決取像窗口位置調(diào)整問題以獲得最短的檢測路徑。實(shí)驗(yàn)結(jié)果表明，該方法可高質(zhì)量快速求解大規(guī)模自動光學(xué)檢測路徑規(guī)劃問題。

1 自動光學(xué)檢測路徑規(guī)劃問題模型

近年來，基于機(jī)器視覺的自動光學(xué)檢測(automatic optical inspection，AOI)系統(tǒng)正逐步取代傳統(tǒng)的人工目視檢測等方法進(jìn)行印刷電路板(printed circuit board，PCB)表面缺陷檢測。出于檢測精度要求，工業(yè)相機(jī)的單次取像視野遠(yuǎn)小于PCB的版幅面積，為獲取PCB中所有待檢電子元件，AOI的工業(yè)相機(jī)需要通過運(yùn)動控制臺移動到不同取像窗口進(jìn)行取像。為提高AOI檢測效率，需要對工業(yè)相機(jī)的多個取像窗口的訪問路徑進(jìn)行合理規(guī)劃，以最短的時間完成取像任務(wù)。

在自動光學(xué)檢測路徑規(guī)劃問題中，設(shè)取像窗口的面積為AFOV，取像窗口所包含的完整電子元件的總面積為Acomponent，為確保取像窗口能覆蓋相應(yīng)電子元件，AFOV通常會大于Acomponent，因此每個取像窗口均存在一定的移動范圍。對于一條按一定訪問順序遍歷各取像窗口的路徑，通過調(diào)整取像窗口的幾何位置，檢測路徑的訪問順序及其總長將發(fā)生變化，如圖1所示。

圖1 取像窗口位置調(diào)整對路徑的影響

在確定取像窗口最少數(shù)量及其約束移動范圍的前提下，設(shè)W={wi=1≤i≤n} 為所有取像窗口集合，在保證各取像窗口所覆蓋的檢測對象不變的前提下，將該問題抽象為：

記G=(V,E) 為賦權(quán)圖，將W初始化狀態(tài)下各取像窗口的幾何中心構(gòu)成窗口節(jié)點(diǎn)集V={1,2,…,n}，E為邊集。則該問題的數(shù)學(xué)模型定義為

(1)

2 變鄰域蟻群算法設(shè)計

2.1 蟻群算法工作原理及局限性

蟻群算法的基本思想是蟻群中的每一只螞蟻在尋找食物的路徑上都會留下信息素，蟻群內(nèi)的螞蟻對信息素具有感知能力，它們將沿著信息素濃度高的路徑覓食，經(jīng)過一段時間后，整個蟻群能尋找到一條到達(dá)食物源最短的路徑[9]。

對于含有N個取像窗口的自動光學(xué)檢測路徑規(guī)劃問題，蟻群算法的工作原理為：

初始化m只螞蟻，使用貪婪算法獲得初始路徑，根據(jù)初始路徑中各邊的長度計算初始信息素濃度τ0即

τ0=m/Lnn

(2)

式中：m為螞蟻的數(shù)量，Lnn為初始路徑的長度。

(3)

式中：τij為某時刻取像窗口i到取像窗口j的信息素濃度；ηij為啟發(fā)式信息能見度，是兩取像窗口間距離的倒數(shù)，α和β分別是信息素和能見度的權(quán)重，Jk(i)為螞蟻k在取像窗口i之后還需要訪問的取像窗口集合。

依據(jù)上述準(zhǔn)則，所有螞蟻完成各自的路徑構(gòu)造后即完成了一次迭代，此時需要更新相應(yīng)邊的信息素濃度，更新準(zhǔn)則為

(4)

(5)

最終蟻群算法在達(dá)到迭代終止條件后將輸出最優(yōu)取像窗口訪問路徑。

雖然蟻群算法可以用于解決路徑規(guī)劃問題，但其存在收斂速度慢和易陷入局部最優(yōu)解兩方面的缺陷[10]。其次在利用蟻群算法求解自動光學(xué)檢測路徑問題時，蟻群算法無法將相應(yīng)取像窗口的移動范圍等因素考慮在內(nèi)，丟失了部分解空間，因此蟻群算法最終獲得的路徑不是最優(yōu)解。

2.2 算法優(yōu)化策略

針對自動光學(xué)檢測路徑規(guī)劃問題，本文以蟻群算法為基礎(chǔ)框架，從提高求解速度和求解質(zhì)量兩方面對蟻群算法進(jìn)行改進(jìn)。首先利用蟻群算法獲得可行解；對可行解進(jìn)行變鄰域路徑搜索，加速算法收斂速度并獲得優(yōu)化解，最后對優(yōu)化解進(jìn)行變鄰域窗口位置調(diào)整，提高優(yōu)化解的質(zhì)量獲得最優(yōu)解。

2.2.1 變鄰域路徑搜索

變鄰域搜索算法(variable neighborhood search，VNS)是一種改進(jìn)型的局部搜索算法，該算法利用不同動作組成的鄰域結(jié)構(gòu)在解空間中進(jìn)行交替搜索，可以在集中性和疏散性中獲得良好的平衡。變鄰域搜索算法依賴于以下事實(shí)[11]：

(1)一個鄰域結(jié)構(gòu)的局部最優(yōu)解不一定是另一個鄰域結(jié)構(gòu)的局部最優(yōu)解；

(2)全局最優(yōu)解是所有可能鄰域的局部最優(yōu)解。

在變鄰域搜索中，鄰域結(jié)構(gòu)是一個動作函數(shù)，通過該函數(shù)對可行路徑S進(jìn)行搜索，可以產(chǎn)生其相應(yīng)的鄰域路徑解集。因此對于變鄰域搜索算法，針對具體問題設(shè)計不同的鄰域結(jié)構(gòu)至關(guān)重要。本文針對自動光學(xué)檢測路徑規(guī)劃問題設(shè)計了3種鄰域結(jié)構(gòu)。

(1)3近鄰插入鄰域N1(S)，如圖2所示。

圖2 3近鄰插入鄰域

設(shè)S為問題的可行路徑集，S1和S2是屬于S的兩條路徑，隨機(jī)選擇當(dāng)前路徑S1中的某一取像窗口，規(guī)定在S1中與該取像窗口相距3個節(jié)點(diǎn)單位以內(nèi)的窗口為該取像窗口的3近鄰窗口，將該取像窗口隨機(jī)插入到3近鄰窗口間，并重新連接成回路得到新路徑S2。

(2)順序重排鄰域N2(S)，如圖3所示。

圖3 順序重排鄰域

隨機(jī)選擇當(dāng)前路徑S1中的兩個取像窗口i和j，將其作為新路徑S2的頭部節(jié)點(diǎn)，剩余取像窗口以頭部節(jié)點(diǎn)i為起點(diǎn)按照其在S1中訪問順序進(jìn)行遍歷并將其依次加入到S2中，并重新連接成回路得到新路徑S2。

(3)2-opt鄰域N3(S)，如圖4所示。

圖4 2-opt鄰域

隨機(jī)選擇當(dāng)前路徑S1中的兩個取像窗口i和j，將i之前的路徑不變添加到新路徑S2中，將i到j(luò)之間的路徑翻轉(zhuǎn)其順序后添加到S2中，將j之后的路徑不變添加到S2中。并重新連接成回路得到新路徑S2。

由于采用貪婪算法構(gòu)建初始路徑易導(dǎo)致蟻群算法的初始信息素匱乏，從而降低求解速度，本文采用文獻(xiàn)[12]的方法初始化各邊的信息素濃度。在此基礎(chǔ)上通過蟻群算法獲得的每一代的可行路徑集S， 然后利用變鄰域路徑搜索對路徑集中的路徑進(jìn)行變形擴(kuò)展從而獲得更大的優(yōu)質(zhì)解空間。優(yōu)質(zhì)解空間有助于增加算法獲得質(zhì)量更加優(yōu)異的路徑的可能性，并且避免算法過早陷入局部最優(yōu)解；同時可以減少劣質(zhì)解的求解次數(shù)從而加快算法收斂速度。綜上，變鄰域路徑搜索算法如下：

算法1：變鄰域路徑搜索算法

輸入：蟻群算法各初始化參數(shù)，螞蟻數(shù)量m，取像窗口數(shù)量N，取像窗口初始中心位置(Nix,Niy)(i=1,2,3,…n)， 3種鄰域結(jié)構(gòu)Nk(k=1,2,3)

輸出：最佳訪問順序優(yōu)化路徑S

(1) while (t≤T) do //迭代終止條件

(2) S=solve(ACO，data)； //利用蟻群算法獲得每一代的可行路徑集S

(3) for (j=1;j≤m;j++){ //對每一條可行路徑進(jìn)行變鄰域路徑搜索

(4)S=Sj，f(S)=length(Sj)；

(5) while(k≤3) do //依次使用3種鄰域結(jié)構(gòu)進(jìn)行路徑擴(kuò)展

(6)S+=Nk(S)；

(7) if (f(S+)

(8)S=S+，f(S)=f(S+)，k=1；

(9) elsek=k+1；

(10) end if；

(11) end while；}

(12) update S；//更新可行路徑集

(13) updateτij& R；//更新信息素濃度及路徑向量，進(jìn)行下一輪迭代

(14) end while；

(15) returnS&f(S)；

2.2.2 變鄰域窗口位置調(diào)整

在變鄰域路徑搜索階段可以快速獲得質(zhì)量更加優(yōu)異的路徑，有效解決了蟻群算法收斂速度慢和易陷入局部最優(yōu)解的問題。但在該階段并未對取像窗口的位置移動范圍進(jìn)行考慮，因此在通過變鄰域路徑搜索獲得的待優(yōu)化路徑S的基礎(chǔ)上，提出變鄰域窗口位置調(diào)整算法對待優(yōu)化路徑S進(jìn)行改善以獲得最優(yōu)路徑。

針對一條待優(yōu)化的自動光學(xué)檢測路徑，從Mark點(diǎn)開始，按照訪問順序依次將路徑上的3個相鄰窗口組合成為一個三元鄰域窗口組NWi={wi-1,wi,wi+1}， 因此一條含有n個取像窗口的檢測路徑，總共含有n+1個鄰域窗口組。其中n個鄰域窗口組的中間窗口分別為n個取像窗口；剩余一個鄰域窗口組的中間窗口為位置無法移動的Mark點(diǎn)，該鄰域窗口組不參與位置調(diào)整。如圖5所示。

圖5 對優(yōu)化路徑S進(jìn)行鄰域窗口組劃分

因?yàn)闄z測路徑總長等于各鄰域窗口組內(nèi)局部路徑長度之和，基于變鄰域搜索的性質(zhì)，本文將全局檢測路徑最短化問題轉(zhuǎn)化為求解各鄰域窗口組內(nèi)路徑最短化問題，將搜索更新后各鄰域窗口組的最短局部路徑去除重疊部分后組合成全局最短路徑。

(6)

令 |AC|=a， |BB′|=b， |AB′|=c， 則f(P)可以轉(zhuǎn)換為

(7)

隨著B點(diǎn)位置的變化，b和c的值也會隨之改變，從而局部路徑P的長度發(fā)生變化。對上式進(jìn)行求導(dǎo)可知，f(P)在c=a/2處取得最小值。

圖6 鄰域窗口組內(nèi)局部路徑最短化問題

為快速求解中心點(diǎn)B的最佳位置，針對鄰域窗口組內(nèi)3個取像窗口不同的幾何位置關(guān)系，本文對中間窗口的位置調(diào)整設(shè)計了一套調(diào)整規(guī)則，令中間窗口中心可調(diào)整范圍矩形(position rectangle，PR)的4個頂點(diǎn)為錨點(diǎn)；令PR中指引點(diǎn)B進(jìn)行位置調(diào)整的邊為指引邊，如圖7所示。

圖7 鄰域窗口組內(nèi)中間窗口位置調(diào)整規(guī)則

同時設(shè)置路徑總長變化閾值δ， 當(dāng)發(fā)生以下2種情況時將忽略此次位置更新，并跳轉(zhuǎn)到下一個鄰域窗口組開始新一輪路徑搜索：

(1)當(dāng)前鄰域窗口組內(nèi)發(fā)生路徑更新時，但更新后的路徑與原路徑總長的變化程度未超過δ。

(2)由于下一個鄰域窗口組發(fā)生路徑更新造成當(dāng)前鄰域窗口組重新進(jìn)行路徑搜索時，但更新后的路徑與原路徑總長的變化程度未超過δ。

對于當(dāng)前鄰域窗口組內(nèi)的3個窗口，調(diào)整中間窗口的位置使得局部路徑P的長度發(fā)生變化，若在當(dāng)前鄰域窗口組內(nèi)無法搜索出一條比當(dāng)前局部路徑長度更短的路徑時，則跳轉(zhuǎn)到下一個鄰域窗口組進(jìn)行搜索，如圖8中虛線箭頭所示；若在當(dāng)前鄰域窗口組內(nèi)搜索出一條比當(dāng)前路徑長度更短的路徑時，則跳回到上一個鄰域窗口組重新開始路徑搜索，如圖8中點(diǎn)劃線箭頭所示。綜上，變鄰域窗口位置調(diào)整算法如下。

圖8 鄰域窗口組間搜索規(guī)則

算法2：變鄰域窗口位置調(diào)整算法

輸入：優(yōu)化路徑S，取像窗口中心可調(diào)整范圍PRk(k=1,2,3,…n)

輸出：最短路徑S+

(1) divide (S)->NWi(i=1,2,3,…n+1)； //對路徑進(jìn)行鄰域窗口組劃分

(2) while (i≤n+1) do；//對每個鄰域窗口組進(jìn)行位置調(diào)整

(3) x=NWi-> Positional relationship； //解析當(dāng)前鄰域窗口組內(nèi)窗口位置關(guān)系

(4)f(Pi)=length(NWi)； //當(dāng)前鄰域窗口組局部路徑P的長度

(5) switch(x) { //依據(jù)窗口位置關(guān)系進(jìn)行位置調(diào)整

(6) case a: do movement1；break；

(7) case b: do movement2；break；

(8) case c: do movement3；break；

(9) case d: do movement4；}

(10) updatef(Pi+)；//位置調(diào)整后的局部路徑

(11) if ((f(Pi)-f(Pi+))/f(Pi)>δ) //判斷位置調(diào)整的有效性

(12)Pi=Pi+，f(Pi)=f(Pi+)，i=i-1；(13) elsei=i+1；

(14) end if；

(15) updateS+=diff(Pi-1&Pi)+Pi； //更新全局路徑

(16) end while；

(17) returnS+&f(S+)；

3 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為：CPU：Intel Core i5-4210U 2.40 GHz，內(nèi)存：8 GB DDR3L，操作系統(tǒng)：windows7。結(jié)合文獻(xiàn)[13]和本文研究問題的性質(zhì)設(shè)置本文算法的相關(guān)參數(shù)：信息素相對重要度因子α=1， 啟發(fā)式信息相對重要性因子β=2， 信息素?fù)]發(fā)因子ρ=0.1， 偽隨機(jī)比例動作選擇因子Q0=0.9， 螞蟻數(shù)量m=10， 最大迭代次數(shù)T=400， 路徑總長變化閾值δ=0.01。 實(shí)驗(yàn)對象為某電氣企業(yè)設(shè)計制造的印刷電路板。

表1給出了本文算法和基本蟻群算法在取像窗口數(shù)量為10、51、83的情況下的求解時間和路徑長度的對比；結(jié)果表明本文算法在求解相同規(guī)模問題時，通過加入了變鄰域路徑搜索，本文算法可以大幅減少求解時間，獲得的路徑長度相較于基本蟻群算法減少了30%左右，路徑質(zhì)量更高，更加符合工業(yè)現(xiàn)場檢測要求，能有效提高AOI在線檢測效率。

表1 變鄰域蟻群算法與基本蟻群算法規(guī)劃結(jié)果對比

針對圖9中的含有10個取像窗口的待檢PCB對象圖，使用本文算法對其進(jìn)行求解，分別提取初始路徑的各取像窗口中心位置和采用了變鄰域窗口位置調(diào)整優(yōu)化后的各取像窗口中心位置，表2給出了相應(yīng)結(jié)果對比，結(jié)果表明變鄰域窗口位置調(diào)整方法可以有效優(yōu)化路徑長度。

圖9 變鄰域窗口位置調(diào)整結(jié)果

4 結(jié)束語

本文提出了求解自動光學(xué)檢測路徑規(guī)劃問題的變鄰域蟻群算法，該算法由變鄰域路徑搜索和變鄰域窗口位置調(diào)整兩部分組成。首先利用變鄰域路徑搜索改進(jìn)蟻群算法，加速路徑規(guī)劃速度并獲得質(zhì)量更加優(yōu)異的優(yōu)化路徑；然后

表2 取像窗口調(diào)整前后中心位置變化及路徑總長變化

針對取像窗口位置可調(diào)整問題，通過分析三元鄰域窗口組內(nèi)的窗口幾何位置關(guān)系，利用變鄰域窗口位置調(diào)整改進(jìn)優(yōu)化路徑獲得最短檢測路徑。最后，通過與基本蟻群算法進(jìn)行實(shí)驗(yàn)對比，結(jié)果表明變鄰域蟻群算法收斂速度與效果更佳，驗(yàn)證了方法的有效性。