导航技术是采摘机器人研究领域中的关键技术，而路径规划则是导航研究课题中的重中之重，路径规划是指采摘机器人基于已给出的种植园地图，满足不碰撞障碍物的前提下，计算出一条从起点到终点的最短路径或耗时最少的路径^[1-2]。张毅等^[1]在遗传算法中新增了插入算子将间断路径转化为连续路径，删除算子用于删除路径中的冗余序号；卢月品等^[2]使用Dijkstra算法找出1条可行、最短但不保证精度和安全性的路径，然后采用改进的遗传算法提高路径精度；张超等^[3]结合混沌粒子群算法和遗传算法，提出了基于粒子群-遗传算法切换策略的路径规划方法；Kala^[4]提出了在1张地图中使用多个机器人共同寻找最佳路径，由其中的某个主机器人协调它们之间的合作关系；Masoud等^[5]提出了六边形环境建模法，可以在较短的时间内找出全局最佳路径；Yun等^[6]为了提高搜索效率，在产生初始种群时，引入了障碍物避免算法(OAA)和区分算法(DA)；Mohanta等^[7]在Petri网中引入了遗传算法，该算法基于一种迭代的、非线性搜索操作，能够充分利用环境的几何信息，产生适宜的航线角度。

已有的算法改进主要研究如何提高收敛速度，较少涉及从地图中获取多条最佳路径的问题；当搜索空间很大时，如何快速收敛到全局最优路径附近也是一个难题。针对这些问题，本文提出了一种基于分组和精英策略的遗传算法，以期快速、有效地获取地图中的所有最佳路径。

1 基于分组的改进遗传算法

基于Sigmoid函数对搜索空间分组后，在每组独立进行遗传操作，每一代适应度值最高的个体即为精英个体，将其完整保留到下一代中，并参与到每个个体的交叉和变异。

1.1 地图生成及编码

为了便于采摘机器人的移动，种植园中果树要求分布规则且间距较大(>5 m)，而移动中的机器人机械手处于收拢状态，所占区域长宽在[1.0 m, 1.5 m]内，因此可将机器人视为质点。栅格法生成的种植园地图如图1所示，图1中的带箭头的线段表示1条路径。初始化群体可采用2种编码方式：坐标法和序号法。坐标法和序号法的转换关系分别如下，其中x为横坐标，y为纵坐标，z为序号。

$\left\{ \begin{array}{l}x = 10\textit{z}\text{\%} \\y = z/10\end{array} \right.;$

$z = 10y + x\text{。}$

1.2 分组

对地图空间进行分组，使得种群在每组中分别进行遗传操作，其中分组数(k)是关键。k太大，适应度高的个体及其后代会很容易替代其他个体，导致陷入局部收敛；k太小，无法体现分组的优势^[8-9]。

人为指定法分组：根据经验给出1个可行的分组数，缺点是主观差异大。动态分组法：分组数随着种群的进化不断动态变化。初始时种群中的个体呈随机分布，差异大，k取较大值；随着种群的进化，个体差异变小，逐渐收敛于n条最佳路径(n≥1)，此时k随之变小。研究中k遵循Sigmoid函数^[10]，并结合了粗粒度并行遗传算法^[11-12]。

$k = {\mathop{\rm int}} \left(\displaystyle\frac{g}{{1 + {{\rm e}^t}}}\right) + \mu ,$

式中，g为初始分组数(5~8)，t为进化代数，μ是调整参数，一般取值为2。

首先初始化随机种群，设种群规模大小为n，即共有n条路径，po={pa₁, pa₂, …, pa_i…, pa_n}，po表示种群空间，pa_i表示第i个个体。初始设进化代数t=0，g=8，根据公式计算出分组数k=6。将种群空间po依次平均分为k组子种群，前k–1组子种群中，每个子种群有 ${\rm{av}} = \left\lfloor {{{n}}/{{k}}} \right\rfloor $ 个个体，最后1个子种群有 $\left[ {n - (k - 1)av} \right]$ 个个体，分组后的种群空间po={{pa₁, …, pa_av}, {pa_av+1, …, pa_2av}, …, {pa_1+(k-1)av, …, pa_n}}，在每组中依次进行遗传操作，可以避免早熟收敛。

每进化1代执行遗传操作之前，在空间po中按照一定概率p_swap，每2组之间随机交换 $\left\lfloor {{{{p}}_{{\rm{swap}}}}{\rm{av}}} \right\rfloor $ 个个体，即第1组和第2组， $\cdots $ ，第k组随机交换个体，若k为奇数，则最后一组保持不变。通过引入新的个体，增加了每个子种群的多样性，避免了局部收敛；同时，每个子种群在搜索空间的不同部分分别进化，加强了全局搜索能力。

经过观察发现，当t∈[0, 5]时，分组数k均为6；当t∈[6, 10]时，k为5；当 t∈[11, 19]时，k为4；当t∈[20, 66]时，k为3；随着种群的进化，最后分组数k稳定为2。也就是说，种群在第6、11、20、67代时会按照上述方法重新进行分组，而在其他代数时，采用上一代的分组结果。

1.3 适应度函数

根据给定的目标函数，计算适应度值。最优路径满足以下准则：无碰撞；路径长度最短。碰撞函数f(r_o)的公式为：

${{f(r_{\rm o}) = }}\left\{ \begin{array}{l}{\rm{1}},\text{路径上至少有一点为障碍点}\\[4pt]{\rm{0}},\text{路径上没有障碍点}\end{array} \right.,$

式中，r_o指序号法表示的路径。

路径长度函数l(r_c)的公式为：

$l({{r_{\rm c}}}) = \sum\limits_{i = 1}^{n - 1} {\sqrt {{{({x_i} - {x_{i + 1}})}^2} + {{({y_i} - {y_{i + 1}})}^2}} } ,$

式中，r_c指坐标法表示的路径； $({x_i},{y_i})$ 和 $({x_{{{i}} + {\rm{1}}}},{y_{i + 1}})$ 为路径上相邻的方格；n为路径上的方格数。

移动路径的评价函数g(r)公式为：

$ \displaystyle {{g(r)}} = \left\{ \begin{array}{l}\displaystyle\frac{C}{{l(r_{\rm c})}},f(r_{\rm o}) = 0\\[5pt]\tau ,f(r_{\rm o}) = 1\end{array} \right.,$

式中，C是放大系数；τ 是1个极小值。

显然当碰到障碍物时，适应度值低，繁殖后代的概率小。

1.4 遗传算子

精英个体指的是当前种群中适应度值最高的个体^[13]，可能不止一个。种群中精英个体和全局最优解之间的“血缘关系”要大于其他个体和全局最优解的“血缘关系”，所以要充分利用精英个体中的遗传信息。本文结合精英保留策略和轮赌盘操作选择个体，将每组中的精英个体不加改变地保留到下一代，并参与每个交叉和变异操作。根据交叉概率P_c，在选择后的个体中进行交叉操作。采用单点交叉，在2个父本中相同点(起点和终点除外)前后交换。如2条路径分别为(0, 11, 12, 23, 34, 44)和(0, 10, 11, 22, 33, 44)，都经过方格11，在该点前后交叉，交叉后为(0, 10, 11, 12, 23, 34, 44)和(0, 11, 22, 33, 44)。若2条路径(除起点和终点外)没有相同点，则不交叉；有多个相同点，随机选取一个作为基准点，进行交叉。交叉的父本之一必须是上一代的最优值，这样能保护种群的精英个体，加快收敛速度。随机产生1个0~1之间的数w，若w小于变异概率p_m，则进行变异操作，采用偏移节点方法^[4]。首先，在待变异个体上任选一点(x_i, y_i)，其前驱节点和后继节点分别为(x_i-1, y_i-1)和(x_i+1, y_i+1)；然后，设置1个半径常数r，并在0~360之间取随机数θ，变异后的节点为(x_i′, y_i′)，公式为：

$\left\{ \begin{array}{l}{x}^{\prime}_i = {x_i} + r\cos \theta \\[4pt]{y}^{\prime}_i = {y_i} + r\sin \theta \end{array} \right.,$

连接(x_i-1, y_i-1)和(x_i′, y_i′)、(x_i′, y_i′)和(x_i+1, y_i+1)，判断其是否经过障碍物，若经过，则舍弃该节点，重新生成一个节点并判断，直到满足条件为止；否则，用新节点替换旧节点。

2 算法收敛性分析

已知定理1：若随机过程或系统在t₀时刻所处的状态已知，在t>t₀时刻所处的条件分布与t₀之前所处的状态无关，则该过程或系统称为马尔科夫链^[14]。

根据定理1得出结论 1：GGABE算法的种群序列 $\left\{ {{X_t},t \geqslant 0} \right\}$ 是齐次马尔科夫链，其中t表示进化代数。证明如下：GGABE遗传算法中的选择、交叉、变异操作都是独立进行的，且每个子代都是由父代通过遗传操作得到的，与父代之前的个体无关。所以GGABE算法是齐次马尔科夫链。

结论 2：GGABE算法具有全局收敛性。证明如下：设S为种群状态空间， $S = \left\{ {{s_1},{s_2}, \ldots ,{s_k}, \ldots ,{s_{{n}}}} \right\}$ ，s_k表示第k代最优解对应的适应度值，p_k为得到最优值s_k的概率， ${p_k} > 0$ ，且 $\sum\limits_{k = 1}^n $ p_k=1。很显然，随着进化过程的推进，第k+1代最优解的适应度值一定大于等于第k代最优解的适应度值，因此S空间是一个单调非递减的有序空间。 ${p_{i,j}}$ 表示由状态 ${{\rm{s}}_i}$ 迁移到状态 ${{\rm{s}}_j}$ 的概率，由于GGABE遗传算法中每一代的最优个体都会复制到下一代中，除非下一代出现了适应度值更高的个体，否则这个最优个体会一直被保留，也就是说种群会一直向接近全局最优解的方向进化，而不会出现退化现象。因此，根据定理1， ${p_{_{i,j}}}\left\{ \begin{array}{l} = 0\;\;\;\;{{i}} > {{j}}\\ > 0\;\;\;\;{{i}} \leqslant {{j}}\end{array} \right.$ 。该算法的状态转移概率矩阵为：

$ {P} = \left[ {\begin{array}{*{20}{c}}{{p_{_{1,1}}}}&{{p_{_{1,2}}}}&{{p_{_{1,3}}}}& \cdots &{{p_{_{1,n}}}}\\0&{{p_{_{2,2}}}}&{{p_{_{2,3}}}}& \cdots &{{p_{_{2,n}}}}\\0&0&{p_{_{3,3}}^{}}& \cdots &{{p_{_{3,n}}}}\\ \vdots & \vdots & \vdots & {} & \vdots \\ 0&0&0& \cdots &{{p_{_{n,n}}}}\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}{A}&{B}\\0&{C}\end{array}} \right]$ ，

其中 ${C} = \left[ {{p_{n,n}}} \right]$ ，显然 ${p_{n,n}} = 1$ ；

${A} = \left[ {\begin{array}{*{20}{c}}{{p_{_{1,1}}}}&{{p_{_{1,2}}}}&{{p_{_{1,3}}}}&{ \cdot \cdot \cdot }&{{p_{_{1,n - 1}}}}\\0&{{p_{2,{2_{}}}}}&{{p_{_{2,3}}}}&{ \cdot \cdot \cdot }&{{p_{_{2,n - 1}}}}\\0&0&{{p_{_{3,3}}}}&{ \cdot \cdot \cdot }&{{p_{_{3,n - 1}}}}\\\vdots & \vdots & \vdots & {} & \vdots \\0&0&0&{ \cdot \cdot \cdot }&{{p_{_{n - 1,n - 1}}}}\end{array}} \right]$ ， ${B} = \left[ {\begin{array}{*{20}{c}}{{p_{_{1,n}}}}\\{{p_{_{2,n}}}}\\{{p_{_{3,n}}}}\\ \vdots \\{{p_{_{n - 1,n}}}}\end{array}} \right]$ ，

0是每一维都是零的向量。

${{P}^\infty } \!=\! \left[ {\begin{array}{*{20}{c}}{{A^\infty }}&{\sum\limits_{i = 0}^{k - 1} {{{A}^i}{B}{{C}^{k - i}}} }\\0&{{{C}^\infty }}\end{array}} \right] \!=\! \left[ {\begin{array}{*{20}{c}}{{{A}^\infty }}&{{{B}^\infty }}\\0&{{{C}^\infty }}\end{array}} \right],k \to \infty $ ，其中 ${{C}^\infty } = \left[ 1 \right]$ ， ${{A}^\infty } $ 为常数变量， ${{B}^\infty } = {\left[ {\begin{array}{*{20}{c}}1\\1\\1\\ \vdots \\1\end{array}} \right] }$ ，从而 ${{P}^\infty } = \left[ {\begin{array}{*{20}{c}}0&0&0&{ \cdot \cdot \cdot }&1\\0&0&0&{ \cdot \cdot \cdot }&1\\0&0&0&{ \cdot \cdot \cdot }&1\\0&0&0&{ \cdot \cdot \cdot }&1\\0&0&0&{ \cdot \cdot \cdot }&1\end{array}} \right]$ ，说明当遗传代数足够多

(趋于无穷大)时，可以收敛到最优解，因而GGABE 算法具有全局收敛性。

3 测试函数及结果 3.1 测试函数

选择了2个代表性的测试函数f₁(x)和f₂(x), 验证简单遗传算法(SGA)，未分组的精英遗传算法(EGA)和基于分组和精英策略的遗传算法(GGABE) 的收敛率及收敛速度。f₁(x)和f₂(x)公式如下：

$\begin{aligned}{f_1}(x) = & \sin (2x)\cos (2x) + \cos (2x)\cos (3x) + \\[3pt] & \cos (3x)\sin (3x),0 \leqslant x \leqslant 20,\end{aligned}$

${f_2}(x) = \left| {\left( {1 - {\rm{x}}} \right){x^2}\sin (200x)} \right|,0 \leqslant x \leqslant 1\text{。}$

3.2 测试结果及分析

3种遗传算法分别执行200次，种群大小为20，最大遗传代数T为100，p_c为0.99，p_m为0.1，η_c和b均为2，p_swap为0.6。根据函数图像中极值的分布对搜索空间进行人工分组，函数f₁(x)分为4组；函数f₂(x)不分组。以收敛率(sr)、平均收敛代数 (ast) 来评估算法性能^[15]，结果如表1所示。

${\rm sr} = \frac{1}{n}\sum\limits_{k = 1}^n {F({{\rm val}_k})} ,$

${\rm ast} = \frac{1}{n}\sum\limits_{k = 1}^n {{t_{k}}} ,$

式中，n为执行次数，val_k表示第k次试验计算的最优值，F(val_k)表示val_k是否收敛，收敛为1，否则为0，t_k表示第k次试验结束时种群进化次数。

根据表1分析对于同一函数：SGA收敛率最低，收敛速度最慢，平均迭代数最大，计算出的最优值误差最大；GGABE收敛率最高，收敛速度最快，平均收敛代数最小，计算的最优值误差最小，f₁(x)与实际最优值之差为 0.012，而f₂(x)与实际最优值之差为0。GGABE能够找出多极值函数的所有最优解而SGA和EGA只能找出1个。函数f₁(x)在[0, 20]内有4个最优解，200次试验中，GGABE算法有199次找出了4个最优值，而SGA和EGA算法每次均找出了1个最优值。

4 寻找最优路径 4.1 试验设计

试验设备为一台华硕笔记本，基本配置: i7Intel 处理器, 主频2.39 GHz，试验软件为Matlab2012A。设计了2幅不同规模的地图，第1幅为15×15(图2a、2b、2c)，第2幅为25×25(图2d、2e、2f), 地图中黑色区域为障碍物，左下角为起点，右上角为终点，实线为寻找到的最优路径(图2)。

4.2 结果分析

基于15×15和25×25的2幅地图进行路径搜索，3种算法的参数设置相同，种群规模30，循环100代，p_m为0.10，p_c为0.99，p_swap为0.60，3种算法均执行50次。结果如表2所示。

由表2可知，在15×15规模的地图上进行路径搜索时，GGABE算法收敛代数最少，收敛率最高，达94%，在满足无碰撞条件下寻找到的最优路径长度最短，仅为20.970 6。由于试验中使用的地图中存在8条最优路径，GGABE算法正确地找出了8条路径，而其他2种算法只能找到1条路径，且不是最短路径，说明本研究算法性能卓越。

由表2可知，在25×25规模的地图上进行路径搜索时，SGA和EGA的收敛速度和收敛率大幅下降，SGA算法的收敛率降为0.14，EGA的收敛率也降为0.56，而GGABE的性能变化不大，收敛率仅下降了0.04，最大收敛代数仅增加了4代，找到的最佳路径数是全部的8条。由此可见，即使在搜索空间增大的情况下，GGABE依然能够正确地找出所有的最佳路径，且有良好的收敛率和收敛速度。

4.3 验证试验

为了测试GGABE的性能，2017年在江苏省徐州市丰县宋镇楼的苹果园进行了样机测试。果树行距为4.0 m，株距为3.7 m，以安装了机械臂和扫描仪的履带驱动农业机器人为研究平台，在苹果园中规划路径。机器人的移动速度为0.68 m·s^–1，行走路径为果树行中心线。为防止破坏果树，机器人移动过程中收起机械臂，可看成一个质点。果园最佳路径必须满足2个条件：无碰撞(即不经过障碍物)；满足前面条件的前提下，保证路径长度最短。

为实现自动导航，需要确定果树位置信息。以扫描仪中心为坐标原点，机器人前进方向为x轴，建立直角坐标系。扫描仪射出的激光会在树干上形成1个交点，作为此树的标识，提取该点在坐标系中的坐标，就获得了果树位置。获得的位置坐标信息传入后台计算机，机器人可在GPS的帮助下移动。将果园栅格化为30×30地图(图3a)，黑色区域为果树，浅色网格为人为添加的障碍物，由起点至终点，由控制计算机基于GGABE算法找出1条或若干条遍历果园内所有果树的最佳路径，并发送控制指令驱动机器人前进。进行50次试验，计算机每次均找出3条最佳路径(图3b、3c、3d)，人为选中1条路径供机器人行走，前10次和后10次试验路径规划花费的平均时间分别为15.700 817 s和15.608 967 s；50次试验中最长规划时间为15.724 909 s，最短规划时间为15.184 906 s，平均时间为15.543 319 s。

5 结论

本文针对传统遗传算法效率低、收敛速度慢且无法处理多极值的问题，提出了一种基于分组和精英策略的遗传算法，并将其应用在采摘机器人路径规划研究中。研究中设计了15×15和25×25的2幅仿真地图，GGABE算法能以最快的速度，最高的收敛率找出所有正确的最短路径，而另外2种算法只能各找出1条路径，且不是最优。当搜索空间规模增大时，本文提出的算法依然能够快速收敛，找到多条最优路径。可见GGABE算法具有良好的鲁棒性和收敛速度。实地试验表明在庞大而复杂的果园中，GGABE算法依然能躲避障碍物，快速准确地找出所有遍历整个果园的最佳路径，本研究为后期机器人实现采摘任务提供了基础。

由于初始种群的优劣对路径规划有一定的影响，本文中初始种群为随机产生，今后将重点研究如何获得优质的初始种群，从而进一步提高算法的收敛率和收敛速度。