基于粒子群與蟻群混合算法的AOI路徑規劃

東苗

(上海行健職業學院 信息技術與機電工程系， 上海 200070)

0 引言

自動光學檢測(Automated Optical Inspection，AOI)是基于光學原理獲取被測對象的照明圖像并數字化，采用計算機進行圖像分析，用于對焊接生產中遇到的常見缺陷進行檢測和處理[1]。近年來，AOI已廣泛應用在印刷電路板(Printed Circuit Board，PCB)組裝質量檢測中。在圖像采集時，受到CCD視野、測量精度的要求等因素的影響，需要將整張PCB劃分成多個檢測窗，通過移動CCD或PCB的方式進行多次數據采集來完成取像工作。在傳統的檢測方法中多采用順序取像法，依次取像后再進行拼接得到全局圖像。其優點是CCD移動控制簡單，但是取像次數較多、圖像拼接難度大、測量精度較低[2]。因此必須對檢測窗的位置和移動路徑進行合理規劃[3]，以確保圖像采集的效率。選取檢測窗位置時需要以待檢測對象在PCB上的二維坐標信息為屬性，以CCD視場(Field of View, FOV)大小作為約束條件，對待檢測目標進行區域聚類劃分。結果中聚類的個數即檢測窗的個數，聚類的大小與FOV的尺寸差異即檢測窗位置的容差。將檢測窗位置容差與CCD移動次序進行組合求解確定檢測窗位置及拍攝序列。

蟻群算法(Ant Colony Optimization, ACO)是一種群體智能優化算法，在20世紀90年代由Dorigo M最早提出并將其應用于解決經典的路徑規劃旅行商問題(TSP)。蟻群算法具有強烈的正反饋和分布并行能力，但是由于初期信息素匱乏導致在搜索初期具有很強的盲目性，搜索速度變慢，容易陷入局部最優解。粒子群優化算法(Particle Swarm Optimization, PSO)通過每個粒子在解空間內追隨當前搜索到的最優值來尋找全局最優值，具有較強的并行搜索能力和較快的全局搜索速度，但存在計算后期容易陷入局部最優，收斂速度慢的缺點。

本文算法混合的思路是在前期利用粒子群算法快速的全局收斂性能進行初步搜索，在一定次數的迭代后找到問題的次優解，然后用求得的次優解初始化蟻群算法的信息素矩陣，提高收斂速度，改善蟻群算法初期搜索的盲目性和易陷入局部最優的問題，從而找到問題的全局最優解。

1 檢測窗的劃分

劃分檢測窗時需要滿足以下條件：以最少的檢測窗來覆蓋所有的檢測目標，而且窗口的大小必須小于或等于FOV的大??；為提高檢測精度，每個檢測目標只能唯一地被包含在一個檢測窗中。為了解決本問題，在約束條件下對待檢測目標進行聚類，聚類結果中類別的個數即檢測窗個數。

1.1 檢測窗劃分的數學模型

假定PCB上共有m個待檢測目標，規劃后共有n個檢測窗。

所有待檢測目標的集合,如式(1)。

O={oi|1≤i≤m}

(1)

規劃后檢測窗的集合，如式(2)。

A={aj|1≤j≤n}

(2)

目標函數如式(3)。

Min(n)

(3)

聚類的約束條件為式(4)。

(4)

式中，Pij表示檢測窗j是否包含檢測目標i；Qji表示檢測目標j是否被檢測窗i訪問過；Wi和Hi分別表示檢測窗i的長度和寬度；WFOV和HFOV分別表示FOV的長度和寬度[4]。

1.2 ISODATA算法

迭代自組織數據(Iterative Self-Organizing Data，ISODATA)算法在K-均值算法的基礎上，根據設定的分類條件不斷地對聚類進行合并和分割，移動聚類的中心來自我調整，直至相鄰兩次迭代的聚類中心不再變化為止[4]。在本問題中應用改進的ISODATA算法，基本步驟如下。

步驟1 初始化，從左上角開始將PCB板用FOV大小的網格覆蓋，每一個網格作為一個初始聚類；

步驟2 刪除不包含任何檢測目標的無效網格；

步驟3 對每個聚類，重新修正它的中心坐標，使其包含更多的待檢測目標；

步驟4 對每個聚類，縮小它的幾何尺寸，使之達到最??；

步驟5 在網格大小必須小于或等于FOV尺寸的前提下，將相鄰的幾個網格合并以組成新的網格；

步驟6 如果存在檢測目標不屬于任何網格，則新增網格來包含它們；

步驟7 重復步驟3—步驟6直到沒有可以合并的網格，也沒有遺漏的檢測目標。

改進的ISODATA聚類算法流程圖如圖1所示。

圖1 改進的ISODATA聚類算法流程圖

2 CCD移動路徑規劃

完成檢測窗的劃分之后，CCD應當找到一條盡可能最短的移動路徑以提高檢測效率，此過程與經典的旅行商問題(Traveling Salesman Problem,TSP)相類似，其不同之處在于：由前一步的ISODATA算法流程可知，聚類結果的范圍均小于或等于FOV的尺寸，所以檢測窗中心點的位置存在容差R。因此在進行路徑規劃時不僅要考慮CCD移動的次序，還需要在每個檢測窗中心可移動的范圍內調整中心位置，以減少總的路徑長度[5]。

2.1 CCD移動路徑規劃的數學模型

以下針對該問題建立數學模型，本問題的目標函數如式(5)。

(5)

式中，n表示檢測窗的個數，Tcam表示CCD拍攝一張圖像的時間(常數)；dij表示相機從第ai個檢測窗中心(拍攝點)移動到第aj個檢測窗中心的時間；zij表示移動路徑中ai和aj是否相鄰,如式(6)。

(6)

對于檢測窗集合：A={ai|1≤i≤n}中的任意ai，其取像位置容差Ri的范圍為式(7)。

(7)

2.2 粒子群與蟻群混合算法

粒子群與蟻群混合算法步驟如圖2所示。

圖2 粒子群與蟻群混合算法流程圖

步驟1 算法開始，初始化種群中各粒子的位置和速度；

假設一個由N個粒子組成的粒子群分布在一個D維空間中，粒子i(i=1,2,…,N)在空間中的位置表示為：Xi=(x1,x2,…,xD)，粒子i的速度定義為粒子在D維空間中每次迭代走過的距離，表示為：Vi=(v1,v2,…,vD)。

步驟2 代入粒子位置和速度，評價每個粒子的適應度；

在路徑規劃問題中，移動距離最短是首要考慮的目標，因此將路徑總長度作為粒子的適應度函數。

步驟3 更新個體極值和群體極值；

在每一次迭代中，粒子i在時間(t+1)速度和位置更新為式(8)、式(9)。

vid(t+1)=ωvid(t)+c1r1[Pid-xid(t)]+

c2r2[Pgd-xid(t)]

(8)

xid(t+1)=xid(t)+vid(t),d=1,2,…,D

(9)

式中,vid(t)為粒子i第d維的當前速度；xid(t)為粒子i第d維的當前位置；Pid為個體極值；Pgd為全局極值；c1、c2為加速常數；r1、r2為0～1之間均勻分布的隨機數；ω為慣性權重。

步驟4 如果滿足約束條件(達到最大迭代次數)進入步驟5，否則返回步驟2；

步驟5 初始化蟻群參數，使用粒子群算法得到的次優解對蟻群算法的信息素矩陣分布進行初始化[6],如式(10)。

τs=c+τp

(10)

式中，c為一個信息素常數；τp為由粒子群算法得到的初始信息素增量。將粒子群算法得到的次優解區域范圍作為主要信息素分布區域，并將每一點的最佳適應度值作為蟻群算法的初始信息素增量,如式(11)。

τp=Pgd(j)

(11)

步驟6 將螞蟻隨機置于任一節點上，計算螞蟻轉移概率，并選擇下一步路徑；

當螞蟻在t時刻完成檢測窗ai的拍攝后，選擇aj作為下一個拍攝窗口的概率，如式(12)。

(12)

式中，ηij為由ai轉移到aj的啟發信息，即兩檢測窗的距離對螞蟻選擇的影響；τij(t)為t時刻，從ai到aj的路徑上的信息素濃度；α分別為啟發信息ηij對路徑選擇概率的影響參數；β為信息素τij對路徑選擇概率的影響參數；allowedk為螞蟻k下一步允許到達的檢測窗集合，在此集合中包含螞蟻k尚未到達的所有檢測窗的集合，保證所有檢測窗均經歷且只經歷一次。

步驟7 逐次逼近調整檢測窗位置；

每只螞蟻完成一次循環后，考慮本次路徑中各個檢測窗的可移動范圍。如圖3所示，若選擇移動路徑A-B-C，則移動檢測窗B的中心位置，使A-B-C的路徑最短，然后根據B-C-D來移動檢測窗C的中心位置，使B-C-D的路徑最短……重復直到經過所有檢測窗。這樣計算得到本次路徑的最短距離，并用于計算更新各分支路徑的信息素[3]，如圖3所示。

步驟8 更新信息素濃度；

當經過n個時刻，m只螞蟻均遍歷整條路徑后，更新各條路段上的信息素,如式(13)、式(14)。

τij(t+n)=ρ×τij(t)+Δτij

(13)

(14)

(15)

式中，Lk為螞蟻k完成本次遍歷的路徑長度；Q為常數。

步驟9 如果滿足約束條件(達到最大循環次數)，程序結束，輸出最優解；否則返回步驟6。

3 實驗仿真結果與分析

為了驗證本文算法的有效性，在給定參數下進行仿真實驗。相機FOV的尺寸為12 mm×10 mm，如果尺寸為226 mm×90 mm，則包含1 128個待測對象的PCB上進行測試。獲取每個待檢測對象的坐標信息后首先利用改進的ISODATA聚類算法進行檢測窗的劃分,如圖4、圖5所示。

圖4 待檢測PCB

圖5 檢測窗劃分結果

得到檢測窗劃分結果之后分別采用標準蟻群算法以及本文算法對CCD的移動路徑進行規劃，分析算法性能的差別。在蟻群算法中，設定群體規模等于檢測窗個數、啟發信息因子α=1.0、信息素濃度因子β=5.0、軌跡持久性因子ρ=0.3、最大迭代次數iter=100；在粒子群與蟻群混合算法中，首先設定使用粒子群算法迭代50次得到次優解后，根據式(10)、(11)初始化蟻群算法中的信息素分布，再使用蟻群算法進行優化。

蟻群算法在第78次迭代時收斂，最短路徑為14 127 mm，粒子群與蟻群混合算法在第31次迭代時收斂，最短路徑為12 673 mm；同時從迭代過程可以看出，由于混合算法的信息素矩陣分布由次優解進行初始化，改善了搜索初期的盲目性，因此混合算法的起點較高。

為進一步驗證粒子群與蟻群混合算法的算法性能，繼續在不同規格的PCB上進行測試。

使用粒子群與蟻群混合算法可以得到最短的規劃路徑，而且混合算法得到最優解所需的迭代次數最少，收斂速度最快,如圖6、圖7和表1所示。

表1 取像路徑優化仿真實驗結果

4 總結

本文采用改進的ISODATA聚類算法進行檢測窗劃分，然后采用粒子群與蟻群混合算法進行取像路徑的優化。在混合算法的第一階段采用粒子群算法，利用粒子群算法前期收斂的快遞性和全局性得到問題的次優解，用次優解初始化蟻群算法中的信息素分布，充分發揮蟻群算法的局部尋優能力，考慮了檢測窗口的可移動范圍從而縮短了路徑長度。使用不同規格的PCB進行實驗，混合算法在求解性能上均優于標準蟻群算法，驗證了本文算法的可行性和有效性。