改进遗传算法在油茶果采摘机优化中的应用

宋莹莹,王福林,兰佳伟

(东北农业大学 工程学院,哈尔滨 150030)

0 引言

遗传算法是一种特殊的元启发式优化算法,它以生物进化理论为基础,利用统计学方法对一个大而有限的解空间进行智能搜索,是目前最常用、最有效的进化算法,被成功地应用于多个领域[1-6]。

遗传算法的搜索能力主要受两个因素影响,即种群竞争压力与多样性[5]。竞争压力过小,算法的搜索过程会变得随机,降低收敛速度;而如果迭代初期种群就失去多样性,会使算法搜索过程停滞,陷入局部最优区域。由此可知,种群竞争压力与多样性成反比关系,增大竞争压力会加速种群多样性的丧失,而维持种群多样性则抵消了竞争压力的影响[7]。因此,只有当种群同时具有多样性与竞争压力时,算法才会有较强的搜索能力。

竞争压力通常受交叉算子的影响,只有当交叉算子能够产生多个优质新个体时,才会向种群内部引入较大的竞争压力,而替换操作则是通过决定哪一新个体能够进入种群取代旧个体来维持种群多样性水平,消除竞争压力对多样性的影响。

因此,设计有效的交叉算子与替换操作对提升算法性能十分重要。现有交叉算子的搜索方向过于单一,无法扩展算子的搜索范围,且替换操作需要计算复杂的种群结构,影响算法的运行速度。

为了避免上述弊端,提出了一种改进交叉算子(IX)与替换操作(SSR)。IX算子利用配对父代的遗传信息,通过在不同的交叉方向上产生个体以实现扩大算子的搜索范围,提升解的质量与收敛速度。SSR操作主要考虑了个体目标函数值与多样性贡献率两个特征,父代中特征值差的个体会被替换;同时,替换操作还通过模拟方波函数的形式对种群进行周期性的局部初始化操作,以维持种群多样性。

1 改进算法简介

1.1 目标函数的构造方法

为了将有约束优化问题转化为无约束优化问题,引入罚函数概念[3],通过惩罚不可行解将约束条件附加至原目标函数中形成一个增广目标函数,转换形式为

F(x)=f(x)+MC

(1)

(2)

式中f(x)—约束优化问题的原目标函数;

M—惩罚系数;

C—惩罚项。

惩罚系数通常选取一个足够的大的数,而惩罚项由p个不等式约束gi(x)与q个等式约束hj(x)构成。当gi(x)为负值时,符号‘< >’表示操作数的绝对值;当gi(x)为非负数时,则返回零值。

1.2 选择算子

选择算子作用于整个种群,选择最具潜力的个体参与交叉操作,目的在于将有利基因遗传到下一代。本文选用排序分组选择,根据目标函数值将种群分为两组:一组由目标函数值较好的个体构成,另一组由目标函数值较差的个体构成。两组个体依次配对能够增大配对个体差异性,避免近亲繁殖[7]。

1.3 交叉算子

交叉算子通过混合遗传数据,重组父代基因的方式产生优质个体,增大种群内部竞争压力,改善种群特性,被认为是影响算法收敛的核心算子[4]。为了提高算法收敛速度与搜索能力,提出了IX算子。设参与交叉的配对个体为X1与X2(X1的目标函数值优于X2),IX算子按照如下公式产生个体,即

(3)

式中m—变量维数;

r1—取值范围[0,1]均匀分布的随机数;

r2—取值范围[-1,0]均匀分布的随机数。

IX算子首先利用了配对个体中目标函数值较优的个体X1,确定了一个基准方向X2X1,通过给定步长r的不同取值范围使算子能够更加全面地探索交叉区域,增大优质个体产生概率,提升算法搜索能力与收敛速度。为了能够更加直观地了解IX算子的搜索范围,以二维空间为例,IX算子产生交叉方向的示意图如图1所示。

图1 IX算子产生交叉方向的二维空间示意图

图1中带箭头实线代表了配对个体在IM操作下产生的两个交叉方向。由图1可知:IX算子明显增大了算子的搜索区域,而且在配对个体不同的分布状态下,即便IM算子不能产生直接指向最优解Xbest的方向,也能产生1个引导种群向最优区域进化的交叉方向。

1.4 变异算子

本文改进的算法选用高斯变异算子,保证变异操作作用于个体附近的局部区域内,有助于提升算子的局部搜索能力[7-8]。

1.5 替换操作

对于多数实际问题,算法在优化搜索空间的同时会逐渐丧失种群多样性,这是造成早熟收敛的主要原因[9]。种群多样性对算法搜索能力的影响如图2所示。其中,图2(a)中种群多样性水平较低,算法在全局最优解附近无解,而图2(b)中种群多样性水平较高,算法在全局最优解附近有解,算法在图2(b)中有更多的机会从点C到达全局最优解,因此算法在图2(b)中的搜索能力要强于图2(a)。由此可见,种群多样性对算法的搜索能力至关重要。

图2 种群多样性对算法搜索能力的影响

为了更好地维持种群多样性、精炼搜索空间,本文提出了一种基于方波函数的替换操作SSR。SSR主要考虑了种群中个体的两大特征值,即目标函数与多样性贡献率,并以方波函数的模式对种群中部分个体进行周期性的初始化操作。

规模为n的种群中个体c的多样性贡献率被定义为与其最邻近个体间的欧氏距离[5],即

(4)

式中d—个体间的欧式距离函数。

种群多样性为种群中个体多样性贡献率之和。由此可见,只有个体与其最临近个体间有较大距离时才会对种群多样性做出贡献。

本文提出的替换操作具体步骤为:通过对比遗传操作产生的新个体与父代个体的目标函数值大小,搜索父代个体中目标函数值次于新个体的群体,用新个体去替换群体中多样性贡献率最差的父代个体,更新种群。同时,替换操作通过模拟方波函数的特定周期与幅值变化对种群进行局部初始化操作,即当算法运行至相应的迭代周期次数(T)时,替换操作从更新后的种群中选择目标函数值最差的K个个体进行初始化操作(K

图3 种群局部初始化的周期方案

图4 改进遗传算法的进化策略流程图

2 实例分析

2.1 油茶果采摘机优化模型建立

随着我国油茶果种植面积的不断扩增,油茶果采摘效率低下制约着其产业的发展,因此优化油茶果采摘机具有重大的研究意义[10]。

油茶果采摘机的优化主要包括两方面:一是采摘臂长度的优化,二是采摘机工作空间的优化。油茶果采摘机的执行机构及油茶果分布空间的详细信息如文献所示[11]。采摘机优化过程中涉及的变量包括:主柱高L1,主臂长L2,副臂长L3,主臂的转角θ2,副主臂的转角θ3。通过固定限制角的分段作图法得出采摘机执行机构末端在二维平面内的工作空间图,如图5(a)所示。工作空间由4条曲线构成,曲线的方程依次为

(5)

图5 油茶果采摘机空间示意图

根据油茶果的分布图,可以将所需的工作空间定义为一个4.5m×4.5m×2.7m的空间立方体,通过分析可将其转化为4.5m×2.7m的平面矩形ABCD。由此可知,采摘机的工作空间需要满足油茶果分布的平面矩形,主截面如图5(b)所示。现将工作空间分为S2与S3两部分,分析可知S1=S3,因此工作空间的总面积S=S1+S2,且S1与S2均在圆C1与C2之间。假设ABCD等4点的坐标依次为A(a,b),B(a,d),C(c,d),D(c,d),由此可以建立采摘机的优化模型。

油茶果采摘机优化模型的目标函数为在满足作业空间的要求下,执行机构的臂长之和最小;其次,执行机构的实际工作空间与所需的工作空间之差最小。因此,目标函数为

(6)

约束条件关键在于确定边界点,主要包括轨迹区域约束、执行机构臂长约束和关节变量约束。

轨迹区域约束为

(7)

执行机构臂长约束条件为

(8)

关节变量约束条件为

(9)

2.2 优化计算结果分析

根据油茶果的生长范围对a、b、c、d进行赋值,依次为a=1.5、b=0.3、c=1.9、d=2.8。利用本文改进的算法进行求解,本文改进算法的参数设置如表1所示。

表1 改进算法的参数设置

为了验证本文改进算法对于优化采摘机的有效性,选取近期发表较为先进的遗传算法进行对比实验,算法依次记为RCGA-1[12]、 RCGA-2[6]、RCGA-3[7],对比算法的参数设置如相应文献所示。为了实验的公平性,所有算法均在同一实验条件下进行,将算法的最大迭代次数设为1 000代,且每个算法均运行1 000次,取目标函数的最小值(min)、最大值(max)、均值(mean)和方差(std)作为实验评价指标,实验结果如表2所示。取各算法求解的最优值为最终结果,则油茶果采摘机优化后各变量的取值如表3和表4所示。

表2 不同算法优化的实验结果

表3 最优结果对应的变量取值

表4 最优结果对应的变量取值

由表2可知:本文改进的算法RCGA求得的最优解的均值最小,表明了RCGA在优化采摘机模型时算法的整体性能最好。结合表3与表4可知:RCGA-1、RCGA-2与RCGA-3求得的最优解相应的变量中均有取值为负数的变量,不满足实际约束条件。因此,相比于对比算法,本文改进的算法具有较好的性能。对比优化前与RCGA算发优化后的油茶果采摘机的参数值进行对比,如表5、表6所示。

表5 优化前后采摘机的参数值

表6 优化前后采摘机的参数值

由表5～表6的实验结果可知,RCGA将目标函数f(x)提升了63.49%。可见,改进的算法能够有效地优化油茶果采摘机的臂长及工作空间。

3 结论

为了提升算法搜索性能,提出了一种简单的IX交叉算子及SSR替换操作。IX算子的特点在于通过增加交叉方向,扩大算子的搜索区域来提升解的质量与收敛速度。SSR操作的特点则是根据父代目标函数值与多样性贡献率两个因素更新种群,同时对种群进行周期性的初始化操作,以维持种群多样性。将改进后的算法应用于油茶果采摘机的优化问题上,通过对比实验可知:改进的算法性能优于其他先进的算法,且改进的算法能够明显优化采摘机模型,使采摘机能够在满足工作空间的前提下机械臂的长度最小。