基于变邻域蚁群算法的自动光学检测路径规划

邓 璘，王 琳，盛步云，萧 筝+

(1.武汉理工大学 机电工程学院，湖北 武汉 430070；2.武汉理工大学 数字制造湖北省重点实验室，湖北 武汉 430070)

0 引 言

路径规划问题是一个NP难问题，可采用传统算法、图形学算法和智能仿生学算法进行求解[1]。智能仿生学算法是目前主流的路径规划求解方法，主要包括：蚁群算法、神经网络算法、粒子群算法、遗传算法等[2-4]。针对自动光学检测系统中的路径规划问题，近年来相关学者提出的解决方法有：以印刷电路板钻孔和焊点为检测对象，利用改进的模拟退火算法和粒子群算法进行取像窗口检测路径规划[5,6]；利用混合遗传算法在规划取像窗口访问路径时通过修改基因结构及遗传算子等方法实现检测路径规划[6-8]。上述方法均取得了一定的成效，但仍存在收敛速度慢和未考虑取像窗口位置调整对检测路径的影响等问题。

针对上述问题，本文利用蚁群算法在路径规划问题中具有寻优能力强、鲁棒性高等特点，在蚁群算法的基础上提出一种基于变邻域蚁群算法的自动光学检测路径规划方法。使用变邻域路径搜索对蚁群算法进行改进，在更大的搜索空间中以更高的搜索效率获得最佳的取像窗口访问顺序；在此基础上，通过分析由3个取像窗口组成的三元邻域窗口组的几何位置关系，采用变邻域窗口位置调整方法解决取像窗口位置调整问题以获得最短的检测路径。实验结果表明，该方法可高质量快速求解大规模自动光学检测路径规划问题。

1 自动光学检测路径规划问题模型

近年来，基于机器视觉的自动光学检测(automatic optical inspection，AOI)系统正逐步取代传统的人工目视检测等方法进行印刷电路板(printed circuit board，PCB)表面缺陷检测。出于检测精度要求，工业相机的单次取像视野远小于PCB的版幅面积，为获取PCB中所有待检电子元件，AOI的工业相机需要通过运动控制台移动到不同取像窗口进行取像。为提高AOI检测效率，需要对工业相机的多个取像窗口的访问路径进行合理规划，以最短的时间完成取像任务。

在自动光学检测路径规划问题中，设取像窗口的面积为AFOV，取像窗口所包含的完整电子元件的总面积为Acomponent，为确保取像窗口能覆盖相应电子元件，AFOV通常会大于Acomponent，因此每个取像窗口均存在一定的移动范围。对于一条按一定访问顺序遍历各取像窗口的路径，通过调整取像窗口的几何位置，检测路径的访问顺序及其总长将发生变化，如图1所示。

图1 取像窗口位置调整对路径的影响

在确定取像窗口最少数量及其约束移动范围的前提下，设W={wi=1≤i≤n} 为所有取像窗口集合，在保证各取像窗口所覆盖的检测对象不变的前提下，将该问题抽象为：

记G=(V,E) 为赋权图，将W初始化状态下各取像窗口的几何中心构成窗口节点集V={1,2,…,n}，E为边集。则该问题的数学模型定义为

(1)

2 变邻域蚁群算法设计

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

蚁群算法的基本思想是蚁群中的每一只蚂蚁在寻找食物的路径上都会留下信息素，蚁群内的蚂蚁对信息素具有感知能力，它们将沿着信息素浓度高的路径觅食，经过一段时间后，整个蚁群能寻找到一条到达食物源最短的路径[9]。

对于含有N个取像窗口的自动光学检测路径规划问题，蚁群算法的工作原理为：

初始化m只蚂蚁，使用贪婪算法获得初始路径，根据初始路径中各边的长度计算初始信息素浓度τ0即

τ0=m/Lnn

(2)

式中：m为蚂蚁的数量，Lnn为初始路径的长度。

(3)

式中：τij为某时刻取像窗口i到取像窗口j的信息素浓度；ηij为启发式信息能见度，是两取像窗口间距离的倒数，α和β分别是信息素和能见度的权重，Jk(i)为蚂蚁k在取像窗口i之后还需要访问的取像窗口集合。

依据上述准则，所有蚂蚁完成各自的路径构造后即完成了一次迭代，此时需要更新相应边的信息素浓度，更新准则为

(4)

(5)

最终蚁群算法在达到迭代终止条件后将输出最优取像窗口访问路径。

虽然蚁群算法可以用于解决路径规划问题，但其存在收敛速度慢和易陷入局部最优解两方面的缺陷[10]。其次在利用蚁群算法求解自动光学检测路径问题时，蚁群算法无法将相应取像窗口的移动范围等因素考虑在内，丢失了部分解空间，因此蚁群算法最终获得的路径不是最优解。

2.2 算法优化策略

针对自动光学检测路径规划问题，本文以蚁群算法为基础框架，从提高求解速度和求解质量两方面对蚁群算法进行改进。首先利用蚁群算法获得可行解；对可行解进行变邻域路径搜索，加速算法收敛速度并获得优化解，最后对优化解进行变邻域窗口位置调整，提高优化解的质量获得最优解。

2.2.1 变邻域路径搜索

变邻域搜索算法(variable neighborhood search，VNS)是一种改进型的局部搜索算法，该算法利用不同动作组成的邻域结构在解空间中进行交替搜索，可以在集中性和疏散性中获得良好的平衡。变邻域搜索算法依赖于以下事实[11]：

(1)一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解；

(2)全局最优解是所有可能邻域的局部最优解。

在变邻域搜索中，邻域结构是一个动作函数，通过该函数对可行路径S进行搜索，可以产生其相应的邻域路径解集。因此对于变邻域搜索算法，针对具体问题设计不同的邻域结构至关重要。本文针对自动光学检测路径规划问题设计了3种邻域结构。

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

图2 3近邻插入邻域

设S为问题的可行路径集，S1和S2是属于S的两条路径，随机选择当前路径S1中的某一取像窗口，规定在S1中与该取像窗口相距3个节点单位以内的窗口为该取像窗口的3近邻窗口，将该取像窗口随机插入到3近邻窗口间，并重新连接成回路得到新路径S2。

(2)顺序重排邻域N2(S)，如图3所示。

图3 顺序重排邻域

随机选择当前路径S1中的两个取像窗口i和j，将其作为新路径S2的头部节点，剩余取像窗口以头部节点i为起点按照其在S1中访问顺序进行遍历并将其依次加入到S2中，并重新连接成回路得到新路径S2。

(3)2-opt邻域N3(S)，如图4所示。

图4 2-opt邻域

随机选择当前路径S1中的两个取像窗口i和j，将i之前的路径不变添加到新路径S2中，将i到j之间的路径翻转其顺序后添加到S2中，将j之后的路径不变添加到S2中。并重新连接成回路得到新路径S2。

由于采用贪婪算法构建初始路径易导致蚁群算法的初始信息素匮乏，从而降低求解速度，本文采用文献[12]的方法初始化各边的信息素浓度。在此基础上通过蚁群算法获得的每一代的可行路径集S， 然后利用变邻域路径搜索对路径集中的路径进行变形扩展从而获得更大的优质解空间。优质解空间有助于增加算法获得质量更加优异的路径的可能性，并且避免算法过早陷入局部最优解；同时可以减少劣质解的求解次数从而加快算法收敛速度。综上，变邻域路径搜索算法如下：

算法1：变邻域路径搜索算法

输入：蚁群算法各初始化参数，蚂蚁数量m，取像窗口数量N，取像窗口初始中心位置(Nix,Niy)(i=1,2,3,…n)， 3种邻域结构Nk(k=1,2,3)

输出：最佳访问顺序优化路径S

(1) while (t≤T) do //迭代终止条件

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

(3) for (j=1;j≤m;j++){ //对每一条可行路径进行变邻域路径搜索

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

(5) while(k≤3) do //依次使用3种邻域结构进行路径扩展

(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；//更新信息素浓度及路径向量，进行下一轮迭代

(14) end while；

(15) returnS&f(S)；

2.2.2 变邻域窗口位置调整

在变邻域路径搜索阶段可以快速获得质量更加优异的路径，有效解决了蚁群算法收敛速度慢和易陷入局部最优解的问题。但在该阶段并未对取像窗口的位置移动范围进行考虑，因此在通过变邻域路径搜索获得的待优化路径S的基础上，提出变邻域窗口位置调整算法对待优化路径S进行改善以获得最优路径。

针对一条待优化的自动光学检测路径，从Mark点开始，按照访问顺序依次将路径上的3个相邻窗口组合成为一个三元邻域窗口组NWi={wi-1,wi,wi+1}， 因此一条含有n个取像窗口的检测路径，总共含有n+1个邻域窗口组。其中n个邻域窗口组的中间窗口分别为n个取像窗口；剩余一个邻域窗口组的中间窗口为位置无法移动的Mark点，该邻域窗口组不参与位置调整。如图5所示。

图5 对优化路径S进行邻域窗口组划分

因为检测路径总长等于各邻域窗口组内局部路径长度之和，基于变邻域搜索的性质，本文将全局检测路径最短化问题转化为求解各邻域窗口组内路径最短化问题，将搜索更新后各邻域窗口组的最短局部路径去除重叠部分后组合成全局最短路径。

(6)

令 |AC|=a， |BB′|=b， |AB′|=c， 则f(P)可以转换为

(7)

随着B点位置的变化，b和c的值也会随之改变，从而局部路径P的长度发生变化。对上式进行求导可知，f(P)在c=a/2处取得最小值。

图6 邻域窗口组内局部路径最短化问题

为快速求解中心点B的最佳位置，针对邻域窗口组内3个取像窗口不同的几何位置关系，本文对中间窗口的位置调整设计了一套调整规则，令中间窗口中心可调整范围矩形(position rectangle，PR)的4个顶点为锚点；令PR中指引点B进行位置调整的边为指引边，如图7所示。

图7 邻域窗口组内中间窗口位置调整规则

同时设置路径总长变化阈值δ， 当发生以下2种情况时将忽略此次位置更新，并跳转到下一个邻域窗口组开始新一轮路径搜索：

(1)当前邻域窗口组内发生路径更新时，但更新后的路径与原路径总长的变化程度未超过δ。

(2)由于下一个邻域窗口组发生路径更新造成当前邻域窗口组重新进行路径搜索时，但更新后的路径与原路径总长的变化程度未超过δ。

对于当前邻域窗口组内的3个窗口，调整中间窗口的位置使得局部路径P的长度发生变化，若在当前邻域窗口组内无法搜索出一条比当前局部路径长度更短的路径时，则跳转到下一个邻域窗口组进行搜索，如图8中虚线箭头所示；若在当前邻域窗口组内搜索出一条比当前路径长度更短的路径时，则跳回到上一个邻域窗口组重新开始路径搜索，如图8中点划线箭头所示。综上，变邻域窗口位置调整算法如下。

图8 邻域窗口组间搜索规则

算法2：变邻域窗口位置调整算法

输入：优化路径S，取像窗口中心可调整范围PRk(k=1,2,3,…n)

输出：最短路径S+

(1) divide (S)->NWi(i=1,2,3,…n+1)； //对路径进行邻域窗口组划分

(2) while (i≤n+1) do；//对每个邻域窗口组进行位置调整

(3) x=NWi-> Positional relationship； //解析当前邻域窗口组内窗口位置关系

(4)f(Pi)=length(NWi)； //当前邻域窗口组局部路径P的长度

(5) switch(x) { //依据窗口位置关系进行位置调整

(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+)；//位置调整后的局部路径

(11) if ((f(Pi)-f(Pi+))/f(Pi)>δ) //判断位置调整的有效性

(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 实验结果与分析

本实验的实验环境为：CPU：Intel Core i5-4210U 2.40 GHz，内存：8 GB DDR3L，操作系统：windows7。结合文献[13]和本文研究问题的性质设置本文算法的相关参数：信息素相对重要度因子α=1， 启发式信息相对重要性因子β=2， 信息素挥发因子ρ=0.1， 伪随机比例动作选择因子Q0=0.9， 蚂蚁数量m=10， 最大迭代次数T=400， 路径总长变化阈值δ=0.01。 实验对象为某电气企业设计制造的印刷电路板。

表1给出了本文算法和基本蚁群算法在取像窗口数量为10、51、83的情况下的求解时间和路径长度的对比；结果表明本文算法在求解相同规模问题时，通过加入了变邻域路径搜索，本文算法可以大幅减少求解时间，获得的路径长度相较于基本蚁群算法减少了30%左右，路径质量更高，更加符合工业现场检测要求，能有效提高AOI在线检测效率。

表1 变邻域蚁群算法与基本蚁群算法规划结果对比

针对图9中的含有10个取像窗口的待检PCB对象图，使用本文算法对其进行求解，分别提取初始路径的各取像窗口中心位置和采用了变邻域窗口位置调整优化后的各取像窗口中心位置，表2给出了相应结果对比，结果表明变邻域窗口位置调整方法可以有效优化路径长度。

图9 变邻域窗口位置调整结果

4 结束语

本文提出了求解自动光学检测路径规划问题的变邻域蚁群算法，该算法由变邻域路径搜索和变邻域窗口位置调整两部分组成。首先利用变邻域路径搜索改进蚁群算法，加速路径规划速度并获得质量更加优异的优化路径；然后

表2 取像窗口调整前后中心位置变化及路径总长变化

针对取像窗口位置可调整问题，通过分析三元邻域窗口组内的窗口几何位置关系，利用变邻域窗口位置调整改进优化路径获得最短检测路径。最后，通过与基本蚁群算法进行实验对比，结果表明变邻域蚁群算法收敛速度与效果更佳，验证了方法的有效性。