一种基于万有引力加速布谷鸟算法的圆度误差评定方法

摘要

一种基于万有引力加速布谷鸟算法的圆度误差评定方法，基于万有引力搜索无需学习外部环境因素的变化亦能感知全局最优信息的特点，将布谷鸟巢穴赋予不同的个体质量，因此其在优化过程中遵循万有引力定律；对布谷鸟算法中的Levy飞行随机游动和偏好随机游动同时利用优化个体间存在的万有引力进行加速搜索，获得相应的布谷鸟寄生巢穴个体更新位置；在万有引力的作用下，有效的平衡了布谷鸟算法的全局搜索能力和局部寻优能力，避免算法执行末期陷入局部极值点而出现的迟滞现象，提高算法的全局搜索效率和收敛精度。本发明待优化的圆度误差E能快速趋于稳定的最优值，并求解出两个同心圆的理想圆心

说明书

技术领域

本发明涉及圆周误差评定技术领域，更具体地说，涉及一种基于万有引力加速布谷鸟算法的圆度误差评定方法。

背景技术

圆度误差评定是回转体零件加工过程重要的评价指标，其精度的高低直接影响加工工件的质量及使用寿命。评定圆度误差经典的方法有最小二乘法、最小外接圆法、最大内切圆法和最小区域圆法。最小二乘法理论相对成熟，但是涉及非线性运算，算法复杂度高。同时，其评定结果误差较大，不能满足最小条件的圆度误差评定结果。最小外接圆法是把实际被测圆的最小外接圆作为外包圆，以最小外接圆的圆心为中心作实际圆的内包圆，因此，圆度误差为此两圆的半径差。最大内切圆法与最小外接圆法评定误差原理类似，都存在工件评定区域过大，造成评定过程累积的误差增大，导致评定的圆度误差增大。最小区域圆法是国际通用的误差评定方法。相比于其他3种方法，最小区域圆法具有更高的测量精度，并且是唯一的。它能够真实的反映加工工件的圆度误差数值，因此本发明中圆度误差评定采用最小区域圆法。

布谷鸟算法(Cuckoo Search,CS)作为一种新型优化算法，与其他智能启发式算法类似，也存在搜索效率不高的问题，尤其是易于陷入局部极值点，算法执行后期出现迟滞现象。为此国内外学者对该算法进行相应的改进以提高算法的收敛性能。归纳起来，目前学者研究的改进算法主要包括两方面：布谷鸟算法控制参数的改进以及与其它算法融合的混合策略。文献“Ong P.Adaptive cuckoo search algorithm for unconstrainedoptimization[J].The Scientific World Journal,2014,14(9):1-8.”对CS算法的搜索步长设置为自适应变化，提高了算法的收敛性能。文献“Naik M,Nath M R,Wunnava A,etal.A new adaptive Cuckoo search algorithm[C].IEEE International Conference onRecent Trends in Information Systems.2015:1-5.”在文献文献“Ong P.Adaptivecuckoo search algorithm for unconstrained optimization[J].The ScientificWorld Journal,2014,14(9):1-8.”的基础上进一步研究，将搜索步长的更新调整为由函数适应度值自适应的确定，而不依赖Levy分布的步长因子。文献“Wang Lijin,Yin Yilong,etal.Cuckoo search with varied scaling factor[J].Frontiers of Computer Science,2015,9(4):623-635.”设置Levy分布的步长因子为均匀分布的随机数，极大提高了CS算法的全局搜索性能。但该方法没有考虑局部搜索的性能，导致算法执行后期易发生迟滞现象。文献“王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法[J].软件学报,2013,24(11):2687-2698.”提出一种逐维更新的函数评价策略，将各维逐一更新，同时采用贪婪更新方式接受改善解。该算法具有一定的竞争力，但是采用逐维更新的评价策略导致函数评价次数急剧增加，因此算法执行效率较低。文献“Walton S,Hassan O,Morgan K,et al.Modifiedcuckoo search:A new gradient free optimisation algorithm[J].Chaos Solitons&Fractals,2011,44(9):710-718.”将发现概率设置为动态变化数值，增强了算法的收敛性能。但是由于改进的算法搜索步长可容许的范围过小，因此算法全局收敛性能较差。另一方面，针对布谷鸟算法与其它算法融合的混合策略，不少学者取得了较好的研究成果。文献“Wang G G,Gandomi A H,Chu H C,et al.Hybridizing harmony search algorithm withcuckoo search for global numerical optimization[J].Soft Computing,2016,20(1):1-13.”将和声优化算法与布谷鸟算法结合，在算法执行过程中增加和声算法中的变异操作判定结果，并把该结果反馈到搜索过程，加快了算法的收敛速度。文献“Guo J,Sun Z,TangH,et al.Hybrid optimization algorithm of particle swarm optimization andcuckoo search for preventive maintenance period optimization[J].DiscreteDynamics in Nature&Society,2016,1(1):1-12.”借鉴粒子群算法良好的局部优化性能，在CS算法中引入粒子群组件，提高了CS算法的收敛精度。文献“Li XT,Yin MH.Parameterestimation for chaotic systems using the cuckoo search algorithm with anorthogonal learning method[J].Chinese Physics B,2012,21(5):113-118.”和“Li XT,Wang J,Yin MH.Enhancing the performance of cuckoo search algorithm usingorthogonal learning method[J].Neural Computing&Applications,2014,24(6):1233-1247.”在Levy飞行之后的偏好随机扰动引入一种正交学习机制，以提高CS算法的整体搜索性能。综合起来，此类改进算法虽然提高了搜索过程中的综合性能，例如种群的多样性，收敛精度等，但代价是增加了函数评价次数及算法的复杂度。当处理高维度优化问题时，特别是多峰函数、脊峰函数和奇异函数时，算法的自适应调节能力较差，导致寻优效果不理想。同时，现有的此类改进算法通常是将两种算法机械的结合在一起，没有深入挖掘种群寻优过程的内部机理，算法执行效率较低。因此，研究新的改进算法具有积极的意义。

发明内容

本发明的目的是在现有的方法上做改进，提供一种基于万有引力加速布谷鸟算法的圆度误差评定方法，基于万有引力搜索无需学习外部环境因素的变化亦能感知全局最优信息的特点，将布谷鸟巢穴赋予不同的个体质量，因此其在优化过程中遵循万有引力定律；对布谷鸟算法中的Levy飞行随机游动和偏好随机游动同时利用优化个体间存在的万有引力进行加速搜索，获得相应的布谷鸟寄生巢穴个体更新位置；在万有引力的作用下，有效的平衡了布谷鸟算法的全局搜索能力和局部寻优能力，避免算法执行末期陷入局部极值点而出现的迟滞现象，提高算法的全局搜索效率和收敛精度。本发明将万有引力加速布谷鸟算法应用于圆度误差评定，具有较好的鲁棒性，待优化的圆度误差E能快速趋于稳定的最优值，并求解出两个同心圆的理想圆心和从而使得两同心圆之间的区域为最小区域。

本发明采用如下技术方案：

一种基于万有引力加速布谷鸟算法的圆度误差评定方法，包括如下步骤：

(1)优化的圆度误差函数为E(X⁽¹⁾,X⁽²⁾)＝min(R_y-R_x)，其中,(X⁽¹⁾,X⁽²⁾)为待优化的圆心，E为圆度误差，R_x和R_y分别为嵌套在工件实际轮廓的两个同心圆的半径，(u_i,v_i)为工件轮廓测量点的坐标值，i∈[1,s]，s为测量点数；设置算法的最大进化代数为W、发现概率为P_a、初始时刻万有引力系数为G₀、算法控制参数为θ、γ₀、p、宿主巢穴的初始移动速度为V₀、初始宿主巢穴位置X_0,m,m∈[1,N]、N为种群个数、优化的圆度误差函数空间维度为D＝2；

(2)根据E(X⁽¹⁾,X⁽²⁾)＝min(R_y-R_x)计算初宿主巢穴位置X_0,m对应的适应度函数值

(3)计算第r次进化时物质个体的万有引力常数G_r；同时计算当前优化函数的适应度最优值E_r,best和最差值E_r,worst，以及对应的最优解X_r,gb，其中r为进化代数；

(4)计算出作用物质个体m在第r次进化时的惯性质量M_r,pm和作用物质个体k在第r次进化时的惯性质量M_r,ak；

(5)根据G_r、M_r,pm、M_r,ak、第r代第m个种群的候选解X_r,m的第j维度上的数值及第r代第k个种群的候选解X_r,k的第j维度上的数值计算当前进化代数的宿主巢穴所受到的万有引力合力和加速度其中，j表示优化的圆度误差函数的第j维度，j＝1,2；

(6)计算得到Levy飞行随机游动方式的宿主巢穴X_r+1,m，同时，按照发现概率P_a舍弃一部分第r+1代宿主巢穴位置X_r+1,m；其中，表示点对点乘法，L(β)服从Levy概率分布；

(7)计算X_r+1,m＝X_r,gb+p·(X_r,k-X_r,z-a_r,m)，得到偏好随机游动方式产生的宿主巢穴X_r+1,m并替换步骤(6)中被舍弃的相同部分的第r+1代宿主巢穴位置X_r+1,m，其中k,z∈[1,N]且k,z均为随机整数；

(8)计算步骤(7)中种群产生的宿主巢穴位置X_r+1,m对应的适应度函数值同时更新当前最优值E_r+1,best和最差值E_r+1,worst，以及对应的最优解X_r+1,gb；

(9)若满足算法进化代数为W，则输出当前进化的最优解和并停止算法，否则返回步骤(3)重复执行算法，和即为两个同心圆的理想圆心。

优选的，适应度最优值E_r,best和最差值E_r,worst的求解过程如下：

其中，E_r,m是圆度误差的适应度值，表示进化至第r代的第m个物质个体的适应度值。

优选的，惯性质量M_r,pm和惯性质量M_r,ak的求解过程如下：

其中，E_r,k是圆度误差的适应度值，表示进化至第r代的第k个物质个体的适应度值。

优选的，万有引力合力和加速度的求解过程如下：

其中，d_j为区间(0,1)内均匀分布的一个随机数，b为物质个体质量按降序排列后的前排个体数目；表示在维度j上，物质个体m对物质个体k的万有引力；

由牛顿第二定律，物质个体m在维度j上第r次进化时的加速度定义如下：

其中，M_r,mm为进化至第r代时作用于物质个体m本身的惯性质量。

优选的，万有引力的求解过程如下：

其中，ε为一个无穷小的常数，M_r,pm表示被作用物质个体m在第r次进化时的惯性质量，M_r,ak表示为作用物质个体m在第r次进化时的惯性质量，R_r,mk为物质个体m和物质个体k的欧氏空间距离，即R_r,mk＝||X_r,m,X_r,k||₂，G_r表示第r次进化时物质个体的万有引力常数。

优选的，万有引力常数G_r的求解过程如下：

G_r＝G(G₀,r)＝G₀·e^-θ·r/W

其中，G₀表示进化初始时刻物质个体的万有引力系数，θ为算法控制参数。

优选的，控制参数θ＝20。

优选的，L(β)的求解过程如下：

L(β)～u＝t^-1-β,0<β≤2

搜索路径与时间t具有幂次方概率密度函数的特性，通过数学代换得到，

其中β＝1.5,u和v服从标准高斯分布，即u,v∈N(0,1)。

提供一种基于万有引力加速布谷鸟算法(Gravitational Acceleration Searchbased Cuckoo Search,GASCS)的圆度误差评定方法，将布谷鸟算法(Cuckoo Search,CS)和万有引力搜索算法(Gravitational search algorithm,GSA)相结合应用到圆度误差评定上，在万有引力的作用下，有效的平衡了布谷鸟算法的全局搜索能力和局部寻优能力，避免算法执行末期陷入局部极值点而出现的迟滞现象，提高算法的全局搜索效率和收敛精度，待优化的圆度误差E能快速趋于稳定的最优值，并求解出两个同心圆的理想圆心和从而使得两同心圆之间的区域为最小区域。

附图说明

图1是本发明的GASCS算法与GSA及CS算法的圆度误差随进化代数变化图；

图2是本发明的GASCS算法与GSA及CS算法运行次数与圆度误差随变化图。

具体实施方式

以下通过具体实施方式对本发明作进一步的描述。

圆度误差属于形位误差，由国家标准规定需要符合理想位置的最小化条件。圆度误差的最小区域圆法是用两个同心圆覆盖评定的加工工件实际轮廓，两同心圆之间的区域为最小区域，则圆度误差为这两同心圆的半径差。假设(u_i,v_i),(i＝1,2,…,s)为工件轮廓测量点的坐标值，s为测量点的数目。同时，假设理想圆的圆心为待优化的圆心为(X⁽¹⁾,X⁽²⁾)，圆度误差为E。

根据最小区域圆的误差评定可得两同心圆之间的区域为最小区域。因此需要满足以下数学关系式：

其中，R_x，R_y分别为嵌套在工件实际轮廓的两个同心圆的半径。由如上两式可以得到，因此R_y≥R_x。则两个同心圆的半径差为

r＝R_y-R_x

因此，算法搜索的目的是在满足工件轮廓测量点坐标值对应的及条件下，尽可能使r＝R_y-R_x最小化，也即是求解E(X⁽¹⁾,X⁽²⁾)。因此圆度误差评定问题转化为求解目标函数极小值问题。

基于上述要解决的问题，本发明一种基于万有引力加速布谷鸟算法的圆度误差评定方法，包括如下步骤：

(1)优化的圆度误差函数为E(X⁽¹⁾,X⁽²⁾)＝min(R_y-R_x)，其中,(X⁽¹⁾,X⁽²⁾)为待优化的圆心，E为圆度误差，R_x和R_y分别为嵌套在工件实际轮廓的两个同心圆的半径，(u_i,v_i)为工件轮廓测量点的坐标值，i∈[1,s]，s为测量点数；设置算法的最大进化代数为W、发现概率为P_a、初始时刻万有引力系数为G₀、算法控制参数为θ、γ₀、p、宿主巢穴的初始移动速度为V₀、初始宿主巢穴位置X_0,m,m∈[1,N]、N为种群个数、优化的圆度误差函数空间维度为D＝2；

(2)根据E(X⁽¹⁾,X⁽²⁾)＝min(R_y-R_x)计算初宿主巢穴位置X_0,m对应的适应度函数值

(3)计算第r次进化时物质个体的万有引力常数G_r；同时计算当前优化函数的适应度最优值E_r,best和最差值E_r,worst，以及对应的最优解X_r,gb，其中r为进化代数；

(4)计算出作用物质个体m在第r次进化时的惯性质量M_r,pm和作用物质个体k在第r次进化时的惯性质量M_r,ak；

(5)根据G_r、M_r,pm、M_r,ak、第r代第m个种群的候选解X_r,m的第j维度上的数值及第r代第k个种群的候选解X_r,k的第j维度上的数值计算当前进化代数的宿主巢穴所受到的万有引力合力和加速度其中，j表示优化的圆度误差函数的第j维度，j＝1,2；

(6)计算得到Levy飞行随机游动方式的宿主巢穴X_r+1,m，同时，按照发现概率P_a舍弃一部分第r+1代宿主巢穴位置X_r+1,m；其中，表示点对点乘法，L(β)服从Levy概率分布；

(7)计算X_r+1,m＝X_r,gb+p·(X_r,k-X_r,z-a_r,m)，得到偏好随机游动方式产生的宿主巢穴X_r+1,m并替换步骤(6)中被舍弃的相同部分的第r+1代宿主巢穴位置X_r+1,m，其中k,z∈[1,N]且k,z均为随机整数；

(8)计算步骤(7)中种群产生的宿主巢穴位置X_r+1,m对应的适应度函数值同时更新当前最优值E_r+1,best和最差值E_r+1,worst，以及对应的最优解X_r+1,gb；

(9)若满足算法进化代数为W，则输出当前进化的最优解和并停止算法，否则返回步骤(3)重复执行算法，和即为两个同心圆的理想圆心。

优选的，适应度最优值E_r,best和最差值E_r,worst的求解过程如下：

其中，E_r,m是圆度误差的适应度值，表示进化至第r代的第m个物质个体的适应度值。

优选的，惯性质量M_r,pm和惯性质量M_r,ak的求解过程如下：

其中，E_r,k是圆度误差的适应度值，表示进化至第r代的第k个物质个体的适应度值。

优选的，万有引力合力和加速度的求解过程如下：

其中，d_j为区间(0,1)内均匀分布的一个随机数，b为物质个体质量按降序排列后的前排个体数目；表示在维度j上，物质个体m对物质个体k的万有引力；

由牛顿第二定律，物质个体m在维度j上第r次进化时的加速度定义如下：

其中，M_r,mm为进化至第r代时作用于物质个体m本身的惯性质量。

优选的，万有引力的求解过程如下：

其中，ε为一个无穷小的常数，M_r,pm表示被作用物质个体m在第r次进化时的惯性质量，M_r,ak表示为作用物质个体m在第r次进化时的惯性质量，R_r,mk为物质个体m和物质个体k的欧氏空间距离，即R_r,mk＝||X_r,m,X_r,k||₂，G_r表示第r次进化时物质个体的万有引力常数。

优选的，万有引力常数G_r的求解过程如下：

G_r＝G(G₀,r)＝G₀·e^-θ·r/W

其中，G₀表示进化初始时刻物质个体的万有引力系数，θ为算法控制参数。

优选的，控制参数θ＝20。

优选的，L(β)的求解过程如下：

L(β)～u＝t^-1-β,0<β≤2

搜索路径与时间t具有幂次方概率密度函数的特性，通过数学代换得到，

其中β＝1.5,u和v服从标准高斯分布，即u,v∈N(0,1)。

为了验证本发明提出的基于GASCS算法的圆度误差评定，将该算法同GSA算法和CS算法同时应用于圆度误差评定。算法初始化设置：种群为N＝20个宿主巢穴，发现概率Pa＝0.2，控制参数θ＝20，γ₀＝0.1和p＝1，s＝100，算法最大进化代数W＝100。GASCS算法、GSA算法和CS算法的圆度误差随进化代数变化关系如图1所示。同时，对这3种算法分别独立运行30次，每次优化结果与运行次数的变化关系如图2所示。

由图1和图2可知，GASCS算法较CS算法和GSA算法具有明显的寻优优势，圆度误差评定结果最小。GSA算法在圆度误差评定中的算法搜索性能与CS算法相比，具有明显的差距，搜索性能不佳。并且在30次算法独立运行中，每次圆度误差评定的结果偏差过大，即算法的鲁棒性较差，使得寻优结果不够稳定。对加工工件的圆度误差评定的结果表明，该算法是一种高效的圆度误差评定算法。

上述实施例仅仅用以说明本发明，而并非用作对本发明的限定。只要是依据本发明的技术实质，对上述实施例进行变化、变型等都将落在本发明的权利要求范围内。