改进的蜂群算法评定空间直线度误差

辛帅，李研

（重庆大学 光电技术及系统教育部重点实验室，重庆 400030）

直线是构成实体零件的最基本的几何元素，常作为设计、加工、装配和检测的基准，直线度误差的大小对产品的质量及其使用寿命至关重要，因而高效准确地对直线度误差进行评定，具有重要的工程意义。

根据零件的功能要求，直线度误差的评定可分为在给定平面内、在给定方向上和空间任意方向上3种情况。评定直线度误差的方法有最小区域包容法、最小二乘中线法和两端点连线法。其中，最小区域包容法是一种与公差带概念完全吻合的评定方法，可以得到理想误差值。在给定平面和方向上的直线度评定较简单且已非常成熟，本文基于最小区域包容法来讨论空间直线度误差的评定。

目前，许多学者致力于空间直线度误差的研究。Huang[1]提出了用最小平行六面体包络的方法计算空间直线度误差，但只能提供误差计算的近似值。Zhang[2-3]建立了基于最小区域条件的数学模型，根据偏微分理论的求解来判断误差评定是否达到最小条件，并用几何判别方法对最后的误差评定结果进行验证。廖平[4]和CUI[5]分别提出了基于遗传算法（Genetic Algorithms，GA）的空间直线度误差评定方法；茅健[6]则提出使用粒子群算法（Particle Swarm Optimization，PSO）对空间直线度进行评定，相比于遗传算法在一定程度上提高了计算精度。这两种智能进化算法虽然能够解决传统算法存在的不足[7]，但是依然存在设置参数较多，鲁棒性欠佳的问题。

笔者提出将蜂群算法引入空间直线度评定，采用混沌序列初始化改进蜂群算法，进一步提高其收敛速度与鲁棒性。该算法相对于经典的智能优化算法，在评定空间直线度误差问题上具有一定的优势。

1 基本人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）由土耳其人Karaboga在2005年提出[8]，是受启于蜜蜂采蜜过程用于搜寻最优解的群智能优化算法，以其在很多研究领域表现出来的比其他算法更佳的优化性能而成为目前学术界的研究热点。

ABC算法模拟蜂群采蜜的过程，通过不同角色蜜蜂间的交流、转换和协作来实现群体智能。被优化问题的备选解被称为食物源，蜜蜂采蜜的过程就是搜寻最优解的过程，食物源的价值通过收益度值衡量，即优化问题的适应度值。适应度函数是算法的判决依据，直接决定优化的方向，算法的目标就是求解适应度函数的最优解。在ABC算法中，将人工蜂群分为 3 种：雇佣蜂（employer）、观察蜂（onlooker）和侦查蜂（scout）。规定雇佣蜂与观察蜂的数量相等，均为蜂群数量的一半，一个雇佣蜂对应一个确定的蜜源（source）。单次迭代的过程如下：雇佣蜂随机寻找蜜源，并在该蜜源邻域内寻找新的蜜源，雇佣蜂通过舞蹈、气味等将蜜源信息反馈给等待区的观察蜂，观察蜂则按照蜜源收益度概率通过轮盘赌方式选择蜜源，并在其邻域内搜索收益度更高的蜜源。如果在迭代过程中某雇佣蜂在设定的搜索次数limit内没有找到更好的蜜源，便放弃这个蜜源，同时雇佣蜂成为侦查蜂，侦查蜂随机寻找新的蜜源。算法中，蜜源的位置对应函数优化问题的一个可行解，蜜源的收益度（蜜量）对应函数问题的适应度（函数值），寻找并采集蜜源的速度代表解决问题的速度。

假设种群规模 S，有 SN 个蜜源，每个解 xi（i=1，2，...SN）是一个D维向量，即搜索空间为D维，蜜蜂对所有蜜源进行搜索，总的循环搜索次数为MCN（Maximum Number of Cycles）。蜜蜂找到蜜源后根据公式（1）计算蜜源的收益度，式（2）为蜜源的邻域搜索公式。

式中 k∈{1，2，...SN}，j∈{1，2，...D}，k≠i，xij表示更新前的蜜源，xkj为邻域内蜜源，φij为[-1，1]的随机数，控制 xij邻域的生成范围。

基本蜂群算法中，观察蜂根据雇佣蜂的蜜源收益度信息，用轮盘赌方法选择蜜源。选择概率如式（3）所示。迭代中由于蜜源经过限定的limit次搜索后仍然没有得到改善的蜜蜂变为侦查蜂，根据式（4）重新选择蜜源。

2 改进的蜂群算法评定空间直线度

2.1 空间直线度误差的最小区域评定模型

空间直线度的定义为 “包容被测轮廓且直径最小的圆柱的直径”。根据形状误差的定义，应该按最小条件评定空间直线度误差值，其大小可以用最小区域的直径来表示。空间直线通常有3种表达方式：一般方程、点向式和参数式，这里采用点向式表示以将评定参数减少为4个。假定测量点坐标集为{xi，yi，zi}，i=1，2，...，n，假定按最小包容区域确定的基准直线方程为：

则测量点到空间直线的距离为：

根据最小包容区域条件，MABC算法评定空间直线度的目标函数可定义为：

由公式（7）可知，优化参数个数为4，待求的优化变量为a，b，l，m。

2.2 改进的蜂群算法

由于评定直线度误差时，数据点越多，最后得到的评定结果就越精确，而大量的数据加大了算法的计算难度，因此采用混沌序列初始化蜂群[9]，混沌是自然界广泛存在的一种非线性现象，具有随机性、遍历性、初始条件敏感性等特点，已被广泛应用于随机优化，在局部寻优领域具有优越的性能。改进的ABC算法利用混沌序列的遍历性可使产生的种群初始解随机性均匀分布于整个解空间，从而提高收敛速度和算法鲁棒性。

改进的ABC算法评定直线度误差的步骤如下：

步骤1 混沌初始化蜂群。设初始化规模为S，其中50%为雇佣蜂，50%为观察蜂。

首先利用Logistic映射产生混沌序列：

式中 i∈[1，N]，i∈[1，D]。 μ 是系统混沌状态的控制参数，本文中 μ=4，此时系统处于完全混沌状态。 L（i），j表示 Li的第 j维变量。 向量 L1=[l1，1，l1，2，…，l1，D]包含有 D 个微小差异的初值，将其代入（3）式迭代N-1次即可得到N×D维的混沌序列。

然后运用（10）式执行载波操作，将混沌序列映射到整个解空间。

其中，xi，j表示第 i个初始解的第 j维的坐标，xmin和 xman表示每一维的最小和最大取值。

步骤2 计算个体收益度。对雇佣蜂进行邻域搜索，并根据贪婪机制选择收益度较高的解来更新蜜源。计算雇佣蜂蜜源收益度，并记录下最优蜜源位置Best。

步骤3 雇佣蜂招募观察锋。观察蜂根据雇佣蜂的蜜源收益度信息，用轮盘赌方法选择蜜源，即收益度较大的蜜源有较大的概率招募到更多的观察蜂，选择概率由公式（3）获得。观察蜂在选择的蜜源附近搜寻新的可行解，并保留收益度较好的解，放弃收益度较低的解。

步骤4 放弃停止更新且收益度较低的蜜源。假如某一蜜源经过限定的limit次搜索后仍然没有得到改善，强制放弃该蜜源，该处的雇佣蜂转变为侦查蜂。侦查蜂在设定范围内随机选择新的蜜源。

步骤5 判断是否满足终止条件或达到最大迭代次数，若是则得到球度误差的最优解，若否则跳至步骤2。

3 实验测试

实验选用文献[4]和文献[6]中的原始数据，以方便对比本文算法和GA、PSO评定直线度误差的效果。原始数据如表1所示。

表1 测量的原始数据Tab.1 Original data of measurement

根据原始数据，对本文算法进行参数设置，由于空间直线度的优化参数为a，b，l，m，所以将候选解维数D设置为4；limit在ABC算法中起着至关重要的作用，通常设置将其设置为迭代次数的 15%～20%，这里迭代次数为 300，limit为50，其余参数的具体设置如表2所示。

表2 控制参数Tab.2 Control parameters

文献[4]分别用遗传算法和首末两端点法对该直线度的误差进行了评定，采用首末两端点法计算空间的直线度误差为0.034 mm，采用遗传算法的计算结果为0.026 mm。文献[6]采用粒子群算法对该直线度进行了评定，计算结果为0.024 932 mm。

应用本文算法评定空间直线度耗时10.069 s，运行50次求平均值得到空间直线的参数为：a=-49.412 4，b=-24.211 5，l=2.970 56，m=1.960 77。所得到的空间直线度的平均误差为：0.00 902 366 mm，最大误差为0.01 012 586 mm，最小值为0.00 895 716 mm。图1是改进的ABC算法的迭代曲线。实际计算结果表明，本文算法评定空间直线度误差的精度比GA算法、两端点法和PSO算法高，而且计算速度较快，鲁棒性较好。经验证算法符合最小区域法的评定标准。

图1 ABC算法的迭代曲线Fig.1 Iterative curve of ABC algorithm

4 结 论

提出了基于混沌序列初始化的蜂群算法，并将其应用于空间直线度误差评定。对最小包容区域空间直线度误差的实例测试表明，相对于GA和PSO算法，本文算法的精确度高、鲁棒性强，非常适用于空间直线度误差的精确评定。同时，该算法也可应用于其他形状误差的评定和非线性优化问题，具有很强的应用价值。

[1]HUANGST，FANKC.WUJH.Anewminimumzone method for evaluating straightness errors[J].Precision Engineering， 1993，15（3）：158-165.

[2]ZHANG Qing， FAN Guang-zhao， LI Zhu.Evaluation method for spatial straightness errors based on minimum zone condition[J].Precision Engineering， 1999（23）：264-272.

[3]张青，范光照，徐振高，等.按最小条件评定空间直线度误差的理论研究[J].计量学报，1998，19（4）：246-253.ZHANG Qing， FAN Guang-zhao， XU Zhen-gao， et al.Theory research for spatial straightness error evaluation based on minimum zone condition[J].Acta Metrologica Sinica，1998， 19（4）：246-253.

[4]廖平，喻寿益.基于遗传算法的空间直线度误差的求解[J].中南工业大学学报，1998，29（6）：586-588.LIAO Ping，YU Shou-yi.A method of calculating 3-D line error using genetic algorithms[J].J Cent South Univ Technol，1998， 29（ 6） ：586-588.

[5]CUI Chang-cai， CHE Ren-sheng， HUANG Qing-cheng.Genetic algorithm-based evaluation of spatial straightness error[J].Journal of Harbin Institute of Technology， 2003， 10（4）：418-421.

[6]茅健，曹衍龙.基于粒子群算法的空间直线度误差评定[J].工程设计学报， 2006， 13（5）：291-294.MAO Jian，CAO Yan-long.Evaluation method for spatial straightness errors based on particle swarm optimization[J].Journal of Engineering Design， 2006， 13（5）：291-294.

[7]刘永超，陈明.形位公差的进化算法 [J].计量学报，2001，22（ 1） ：18-22.LIU Yong-chao，CHEN Ming.A new evaluation met ho d for form and position errors[J].Acta Metrologica Sinica， 2001，22（1）：18-22.

[8]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06， Erciyes University，2005.

[9]孟红记，郑鹏，梅国晖，等.基于混沌序列的粒子群算法[J]，控制与决策，2006，21（3）：263-266.MENG Hong-ji， ZHENG Peng， MEI Guo-hui， et al.Particle swarm optimization algorithm based on chaotic series[J]，Control and Decision， 2006，21（3）：263-266.