基于机器视觉与改进遗传算法的机械手分拣方法研究*

周志霄 王 宸② 张秀峰 刘 超 唐 禹 张 伟

(①湖北汽车工业学院机械工程学院，湖北 十堰 442000；②上海大学上海市智能制造与机器人重点实验室, 上海 200072)

零件分拣在工业生产过程中是非常重要的一个环节，传统的人工分拣不仅效率低下，而且耗时耗力，已经无法满足现代化生产需要。目前已有部分企业将工业机器人应用在分拣作业中，但是其分拣方式单一，无法适应复杂的场景。机器视觉技术具有自动化、非接触和高精度等特点，将机器视觉应用到工业机器人分拣过程中能有效提高工作效率。

彭刚等人[1]提出了一种基于Surf和 Freak算法的元器件分拣方法，该算法加快了模型的建立，减少了目标分类的时间。廖家骥等人[2]设计了一种针对不同形状的工件分拣系统，主要采用模板匹配对工件进行分类和定位，该系统可对任意位置的工件进行分类。伍锡如等人[3]针对工业分拣机器人识别工件速度慢、精度低等问题，提出了一种基于深度学习的识别工件算法，该算法具有良好的可行性。以上基于机器视觉的自动分拣方法，相较于人工分拣在速度和效率上都有了较大提高，但没有考虑优化分拣路径进一步完善分拣系统。

零部件分拣[4]、无人机队列调整[5]等路径规划问题可以归约到旅行商问题(travel sale problem，TSP)的研究上来，TSP是一类经典的组合优化问题，该问题可以描述为一个商人要去若干个城市，且每座城市只能经过一次，最终返回出发点城市所经过的最短路径。

目前许多学者对TSP求解算法进行了研究，由于单一的智能优化算法存在局限性，因此此类算法多采用几种算法相结合或者对原有算法的算子改进的办法。Wu C等人[6]在头脑风暴(BSO)算法的基础上设计了一种新型交叉算子来求解TSP，该算法求解精度高，不易陷入局部最优。吕文壮等人[7]设计了一种改进蚁群(PSO-ACO)算法解决TSP，该算法利用粒子群算法对蚁群算法产生的较优解进行交叉和变异，得到更加优质的种群，但是该算法在实际应用时求解速度较慢。Wei B等人[8]将概率策略和遗传算子引入粒子群优化算法中，设计出了混合粒子群优化算法(IHPSO),并应用于求解TSP，该算法保证了种群的多样性，具有较高的收敛精度。Jiang X Y等人[9]于2018年提出了天牛须搜索算法( beetle antennae search algorithm, BAS)，该算法原理简单、计算量少，求解速度快，然而当前将BAS用于求解TSP问题的研究还较少。

基于以上分析，通过改进智能优化算法的算子能够有效解决TSP问题，然而上述算法存在算法复杂度较高、求解速度慢等缺陷，因此本文在遗传算法的基础上设计了一种基于天牛须算法的启发式变异算子求解TSP，并应用到零件自动分拣中，提高了规划路径的速度，缩短机械臂运动轨迹的长度。

1 系统概述

1.1 实验系统

本文采用如图1所示的实验系统，该实验系统包括：机械手、工业摄像头和计算机。具体型号如表1所示。

表1 实验平台硬件及软件型号

1.2 总体流程

本文基于机器视觉技术，采用改进遗传算法(BAS-GA)规划机械手抓取的路径，主要为以下3个步骤：第一步，使用图像处理软件对零件图像进行预处理；第二步，对零件进行识别和定位，得到目标零件坐标；第三步，使用BAS-GA算法对机械手的抓取路线进行规划，实现机械手对零部件进行快速分拣。

2 零件识别及定位

2.1 图像预处理

由于噪声、光照等外界环境或设备本身的原因，通常所获取的原始图像质量不是非常高，为了使图像更加清晰，突出图像特征，便于进一步对图像进行识别和分析，需要对模板零件和待匹配零件图像预处理。主要包括灰度化处理[10]、中值滤波[11]、自适应阈值[12]和开操作处理[13]。

2.2 零件识别与定位

本文采用文献[14]的方法对零件进行识别与定位，该方法首先使用Sift算法对模板零件图像和待匹配零件图像进行识别，找到目标零件，然后通过仿射矩阵将模板零件中心坐标转换为目标零件的中心坐标。

2.3实验

选取20个零件作为实验对象，其中包括4个方斜垫片，4个圆形垫片，4个弹垫以及8个螺母。随机将这些零件散落在抓取区域内，将其中8个螺母作为目标零件，启动工业摄像头采集图像并显示在交互界面上，使用Halcon 20.1软件采用前文的方法，获取螺母的位置坐标。图3为零件定位图像，表2为得到的螺母中心坐标。

表2 螺母中心坐标

3 基于改进遗传算法的机械手路径规划

3.1 路径建模

在完成螺母零件识别和定位后，开始对机械手分拣螺母零件路径进行规划。设f为一组移动序列，v1,v2,...,vn为n个目标零件，Rd为这个移动序列下的机械手分拣路径：

f=(v1,v2,…,vn)

(1)

(2)

其中:d(vi,vi+1)为零件vi到vi+1零件的距离。可以看出此模型可归结为TSP问题。

3.2 遗传算法

遗传算法(genetic algorithm，GA)是模拟自然界中生物进化的过程，根据优胜劣汰原理，通过种群进化得到最优解。

GA算法求解过程为：首先对每个目标零件进行编码，各个编码在基因序列中出现的先后顺序作为个体，即一个机械手分拣路径。编码完成后，随机产生一个有规模限制的种群，相当于各种分拣路径的集合。适应度函数在寻优过程中有着重要作用，在机械手分拣路径优化过程中以分拣路径最短为目的，由式(2)定义适应度函数为：

(3)

在确定适应度函数后，开始对种群进行多次选择、交叉、以及变异操作，计算每个个体的适应度，输出适应度最高的个体，即机械手分拣的最优路径。其中的变异操作是随机改变种群中个体的基因位置，常见的变异操作有交换变异、逆转变异和倒换变异。逆转变异包括以下步骤：

第一步：随机选择2个插入点(a和b)，如图4所示。

第二步：将两个插入点中间部分的编码顺序颠倒得到子代，如图5所示。

3.3 天牛须搜索算法

天牛须搜索算法(BAS)是根据天牛觅食的原理而开发的算法。天牛长有两只触角，在天牛搜寻食物时，两只触角感知食物气味的浓度，如果右边触角感受到的气味浓度比左边大，则往右移动，反之亦然。天牛须搜索算法具有全局搜索速度快、求解精度高等特点，目前已在各工业领域得到广泛应用[15～18]。

3.4 BAS变异算子

如3.2所述GA算法中的逆转变异是以一定的概率改变种群中个体的某些基因的值，具有较大的随机性，容易产生适应度较差的子代，影响着算法的效率和速度。为提高算法效率，根据本文问题结合BAS算法的思想，设计了一种启发式变异算子。即在每个操作回路中，只能选择距离最近的相邻目标零件作为下一个到达的位置。

过程为父代记作A= (a1,a2,…,an)，即一种分拣路径。所产生的新个体记作B，从父代A中随机选择一个目标零件，将此零件记为α，并将α记作B的起点。α两边的零件记作αl、αr，零件αl、αr与α的距离分别为dl、dr。这里α可以理解为天牛当前的位置，αl和αr对应着天牛的左须跟右须，dl和dr则对应着左右须气味的强度。通过比较两边气味强度来确定天牛下一步的位置，并将得到的位置添加到B中。流程如图6所示。

BAS-GA算法具体流程如图7所示。

为了验证所提出算子的有效性，采用国际标准TSPLIB标准数据集中burma14进行实验， burma14已知最优解为30.87，最优路径图如图8所示。

随机选取父代P作为实验对象，父代P的路径为[5 7 13 10 9 11 8 1 2 3 4 14 12 6],如图9所示，对应的路径长度为32.567 6。

使用BAS-GA算法中特定的变异算子对父代P进行排序，随机选取了父代P中序列为7的基因作为子代起点，即城市8，比较父代P中与城市8相邻两城市的距离，取其中距离近的城市作为子代下一个城市，经过多轮迭代，可得到路径：[8 1 11 9 10 2 13 7 3 4 14 12 6 5]，路径长度为31.299 8。可以看出改进后的变异算子得到了适应度更好的子代，从而以更快的速度找到最优解。

4 实验验证

4.1 仿真实验

为验证BAS-GA算法的性能，选取TSPLIB中的数据Ulysses22、att48、eil101进行仿真实验，以上数据为旅行商问题实例的城市坐标，主要用来测试TSP相关算法性能。本文采用不同算法进行对比实验，为了保证实验的公平性，所有实验都在同一环境下进行，具体仿真环境为：操作系统Windows 10，CPU型号为AMD 3100,运行环境为Matlab2020a。BAS-GA算法中种群数量为100，交叉率为0.3，变异率为0.7，最大迭代次数为500。比较对象为模拟退火算法(SA),遗传算法(GA)以及文献[7]中的改进蚁群算法(PSO-ACO)。测试结果如表3所示。

表3 BAS-GA算法与其他算法实验结果比较

表3中Set表示集合类型，Opt表示官方公布的最优解，Best表示实验得到的最优路径长度，Time表示得到最优路径的时间。为了使得到的数据更直观，本文采用相对误差ER对算法求解准确性进行评估，即绝对误差与真值的比值乘以100%得到的数值：

(4)

根据相对误差公式，对表3中数据进行处理，得到表4。

表4 算法性能对比

从表3和表4可以看出，针对中小型数据集Ulysses22、att48，对比SA算法、GA算法和PSO-ACO算法，BAS-GA算法的求解精度更高、求解时间更短。同时，对数据集Ulysses22，BAS-GA算法搜索到比官方数据更短的路径。但从数据集eil101来看，BAS-GA算法在处理大型数据集时，可能会陷入局部最优，且与PSO-ACO算法相比，虽然BAS-GA算法在求解时间上有所领先，但在求解精度上略微落后，后期有待改进。

4.2 机械手分拣路径规划实验

将表2中的螺母零件中心坐标输入分拣程序中，然后分别采用初始路径和经过优化后的路径控制机械手进行抓取，并记录两种路径下机械手运动轨迹的长度。

实验表明机械手抓取的初始路径为1 510.89mm，经过改进遗传算法优化后，得到长度为1 330.1mm的路径，路径缩短了11%。

5 结语

本文为提高零部件自动分拣效率，运用机器视觉技术识别并定位零件，对得到的目标零件坐标建立TSP模型，设计了BAS-GA算法对模型进行求解。通过BAS-GA算法与多种算法比较，BAS-GA算法路径规划时间短，求解精度较高。该算法具有较好的优越性和可行性，适合工程实际应用。