基于贪心遗传算法的穴盘苗补栽路径优化

贺磊盈 杨太玮 武传宇 俞亚新 童俊华 陈成锦

(1.浙江理工大学机械与自动控制学院， 杭州 310018； 2.浙江省种植装备技术重点实验室， 杭州 310018; 3.浙江三锋实业有限公司， 金华 321300)

基于贪心遗传算法的穴盘苗补栽路径优化

贺磊盈1,2杨太玮1武传宇1,2俞亚新1,2童俊华1,2陈成锦3

(1.浙江理工大学机械与自动控制学院， 杭州 310018； 2.浙江省种植装备技术重点实验室， 杭州 310018; 3.浙江三锋实业有限公司， 金华 321300)

温室育苗需要通过补苗移栽作业用健康钵苗替换穴盘内未发芽或劣质的钵苗，保证钵苗的质量。自动补苗移栽机可利用机器视觉获取穴盘苗健康信息，控制末端执行器抓取钵苗进行补苗作业，移栽效率高。穴盘内需补苗孔穴的位置具有随机性，对补栽路径进行规划，可进一步提高补栽效率。本文综合贪心算法和遗传算法的特性提出一种贪心遗传算法，在分段步长取8，优化代数取100时，可实现稀疏和密集穴盘的补栽路径优化，具有鲁棒性。贪心遗传算法所规划补苗路径长度与全遗传算法接近，均值差在443 mm以内；相比优化前的固定顺序法，贪心遗传算法路径长度可缩短33.8%～41.3%，缩短长度随空穴数量增加而加长；贪心遗传算法与全遗传算法规划补栽路径耗时分别为1.81 s和5.59 s。对比可知，贪心遗传算法更有利于自动移栽机输送单元和移栽单元间的动作衔接，可进一步提高自动移栽机效率。

自动移栽机； 穴盘苗； 温室； 路径优化； 贪心遗传算法

引言

温室穴盘育苗技术已被广泛采用，穴盘苗出厂前需将未发芽或长势不好的苗剔除，并用健康苗补种。钵苗自动移栽机可以解决传统人工作业劳动强度大、效率低的问题，且移栽质量好。国外自20世纪80年代末开始研究钵苗移栽机[1-3]，TING等[4-5]研制出2种夹持器安装于SCARA工业机器人上，进行600孔至48孔固定顺序的稀植移栽作业。RYU等[6]开发一种由CCD相机检测和三维移动平台构建的自动移栽机，其气缸驱动的末端执行器可实现98%的移栽成功率。国内学者近年也开展了适合本土育苗实际的钵苗自动移栽机研究[7-9]，例如，田素博等[10]设计了穴盘苗输送、定位及自动控制装置。孙国祥等[11]基于虚拟样机技术对一种电动机驱动的末端执行器进行设计。TONG等[12]基于改进型分水岭分割算法对相邻穴孔钵苗叶片存在重叠的穴盘苗进行健康识别。韩绿化等[13]设计了一种两指四针钳夹式取苗末端执行器，并对影响夹钵取苗效果的含水率、入钵角和深度等因素进行统计试验分析。上述研究主要针对钵苗自动移栽机的系统设计[14-15]、钵苗健康检测[16-18]、末端执行器开发[19-21]等方面的关键技术研究，适用于穴盘苗出厂后大田或花卉盘[22-24]的机械化移栽作业。

此外，优化自动移栽机关键机构尺寸和移栽路径也是研究的热点。HU等[25]通过建立移栽机运动学和动力学仿真模型，优化二自由度五杆并联机构的几何尺寸和抓取苗轨迹中的驱动速度。童俊华等[26]采用全遗传算法对50孔的穴盘间补苗移栽路径进行优化，相比固定顺序路径长度缩短8.5%以上。但针对目的穴盘为空盘的稀植移栽作业时，若采用全遗传算法规划，生成的整条路径编码长，计算量大，耗时长。为此，童俊华等[27]又采用贪心算法分别对稀疏穴盘(50孔移栽至32孔)和密集穴盘(128孔至72孔)进行稀植移栽路径优化，可使路径长度缩短10.6%以上。

在对密集穴盘采用全遗传算法[26]进行补栽路径规划时发现，穴孔数量的增加会使单个染色体基因数增加，使整体路径取优的运算量增大，不能适应自动移栽机高效率实时性作业的要求。为此，本文综合前期研究，提出一种贪心遗传算法，对补栽路径规划采用贪心分段式遗传优化再组合的方法，以减少运算时间，缩短补栽路径，进一步提高移栽机末端执行器的工作效率。

1 钵苗补苗移栽路径规划描述

1.1 温室钵苗自动移栽机补苗作业原理

温室钵苗自动移栽机的样机如图1所示，其基本尺寸长×宽×高为3 800 mm×1 100 mm×2 300 mm。其中包含视觉检测、苗盘传输、三坐标移栽和控制器4个单元。视觉检测单元可识别出穴盘各穴孔内健康钵苗、未发芽或长势不好的劣质钵苗，并记录钵苗在穴盘内的位置。苗盘传输单元包含前端、中间转换和并行双末端3段输送带，如图2所示。穴盘苗在前段输送带上完成检测，然后通过中间转换输送带送至并行双末端输送带上进行补苗。三坐标移栽单元中的三维移动机械臂驱动末端执行器剔除并行双末端输送带上补苗穴盘劣质钵苗穴孔后，将输送带上供苗穴盘内的健康钵苗逐一进行补种移栽。控制器单元包含配有Intel Core i7 CPU的研华701G2工控机和三菱PLC。

图1 温室钵苗自动移栽机样机Fig.1 Prototype automated transplanter in greenhouses1.视觉检测单元 2.苗盘传输单元 3.三坐标移栽单元 4.控制单元

图2 苗盘传输单元示意图Fig.2 Diagram of tray transfer unit1.前端输送带 2.中间转换输送带 3.并行双末端输送带

供苗(或补苗)穴盘补种作业完成后，新穴盘苗从中间转换输送带送至三坐标移栽单元的作业位置距离L2为1 000 mm,假设输送带平稳输送速度为0.5 m/s，则需要2 s时间。补苗路径控制算法若能在2 s内完成规划，将不影响自动移栽机苗盘传输单元和三坐标移栽单元间作业节拍的衔接，满足实时性要求。

1.2 补苗移栽路径规划分析

温室育苗穴盘外观尺寸为250 mm×500 mm，穴孔数G有32、50、72和128等规格。图3为50孔规格供苗穴盘向补苗穴盘移栽的路径示意图：穴盘格内小圆圈代表健康钵苗穴孔，空格代表劣质钵苗穴孔；末端执行器从原点出发，按照一定顺序逐一将供苗穴盘内的健康钵苗移栽补种至补苗穴盘中的空穴孔内。补苗移栽路径规划的目的是确定往复移栽的先后顺序，在机械臂驱动速度一定的情况下缩短补栽路径，提高移栽机工作效率。

图3 补苗移栽路径示意图Fig.3 Diagram of seedlings replugging tour

2 固定顺序和贪心算法补苗路径规划方法

2.1 固定顺序补苗移栽路径规划方法

补苗移栽固定顺序方法(FS)采用文献[27]中常规固定顺序方案中较稳定的方案2作为参照对比方案。具体步骤为：从左至右、从上至下顺序扫描供苗穴盘，依次将健康钵苗按从右至左、从上至下的顺序补种移栽至补苗穴盘的空穴孔内，最终路径如图4所示。

图4 固定顺序补苗移栽路径规划方法Fig.4 Fixed sequence method for seedlings replugging tour

2.2 贪心算法补苗移栽路径规划方法

补苗移栽贪心算法(GAS)采用文献[27]在稀植移栽规划试验中的最优方案3。具体为：保持补苗穴盘从上至下、从右至左的扫描移栽顺序；比较供苗穴盘内健康钵苗所有健康钵苗穴孔与补苗穴盘空穴孔间距离，以最短穴孔的健康钵苗为移栽对象；依照此方法对未完成补苗填充的补苗穴盘空穴按秩序扫描移栽，结果如图5所示。

图5 贪心算法补苗移栽路径规划方法Fig.5 Greedy algorithm for seedlings replugging tour

3 全遗传算法和贪心遗传算法补苗路径规划方法

3.1 全遗传算法补苗移栽路径规划方法

全遗传算法(GA)补苗移栽路径规划方法与文献[26]一致，对供苗穴盘内的健康钵苗和补苗穴盘内的空穴孔进行正负标记和交叉编码染色体路径，通过选择、交叉、变异和重插入操作，优选出种群适应度最大个体。遗传算子与前期研究相同，选择、交叉和变异概率分别取0.9、0.8和0.3，种群规模取40。遗传优化代数随编码染色体基因加长而增加，对128孔的密集穴盘遗传规划运算取600代时能得到收敛，图6为重复运算10次遗传过程中种群最优路径长度和种群路径长度均值随优化代数变化的结果。确定全遗传算法各算子参数后，进一步对图3所示补苗移栽模型的路径进行优化，结果如图7所示。

图6 128孔穴盘10次运算路径长度随遗传优化代数变化曲线Fig.6 Path changing curves along with hereditary algebra for 128 holes

图7 全遗传算法补苗移栽路径规划方法Fig.7 Genetic algorithm for seedlings replugging tour

3.2 贪心遗传算法补苗移栽路径规划方法

遗传算法具有全局搜索优化的能力，补苗穴盘待补苗空穴孔数量增加使其搜索的运算量加大；为提高运算效率，引入贪心算法局部取优的思想组合成一种贪心遗传算法(GGA)，用于穴盘苗补苗移栽路径规划。方法可描述为：①将补苗穴盘内的待补苗空穴孔按秩序区域分段。②遗传算法搜索优化的移栽路径，确定各分段空穴孔对应供苗穴盘内健康钵苗的移栽秩序。③各分段的优化路径前后拼接，可得到贪心遗传算法的整体优化路径。结合图3中的补苗移栽模型对该算法具体实施步骤加以阐述。

3.2.1 穴孔标记和分段编码

路径规划前将补苗穴盘内待补苗空穴孔和供苗穴盘内的健康钵苗按顺序标记，并与三坐标移栽单元内的坐标值相映射。补苗穴盘内m个空穴孔按从上至下、从右至左的扫描顺序进行负标记(-1,-2,…,-m)；供苗穴盘内n株健康钵苗按从上至下、从左至右的扫描顺序进行正标记(1,2,…,n)，如图8所示。

图8 穴孔标记示意图Fig.8 Diagram of tray hole marker

对补苗穴盘的负标记序列分段，以p为分段步长；若m≤p，则保持(-1,-2,…,-m)序列长不变；若m>p，m/p=u，余数为v,标记序列可分段为u+1段，分别为: (-1,-2,…,-p)，(-p-1,-p-2,…,-2p)，…，(-(u-1)p-1,-(u-1)p-2,…,-up),(-up-1,-up-2,…, -up-v)。按分段顺序第1分段p个负标记与n个正标记随机交叉编码，进行该局部分段的遗传算法路径优化；第2分段负标记则与前次遗传优化后余下的正标记进行交叉编码和遗传优化；依此执行，直至负标记的第u+1段。若v≠1，仍按遗传优化方法执行，若v=1，则按贪心算法直接计算对最后1株补苗移栽的最短路径。图7所示模型，假设取p=4,则第1分段可随机交替生成一条含2p=8个基因的局部路径编码染色体(32，-3，25，-2，12，-4，9，-1)，相比3.1节所述的遗传算法染色体路径基因可减少10个，采用同样的方法生成总共N个编码染色体构成该分段遗传算法的初始种群。

3.2.2 适应度函数和选择操作

路径优化的目标是寻找最短移栽路径值，通过编码染色体所映射的路径长度来构建遗传算法的适应度函数，从而判别编码染色体在该种群内的适应度。假设R(i)为染色体i的适应度，Si表示染色体i对应的路径长度，Smax和Smin表示该种群染色体对应路径最大和最小长度，可定义出介于0～1之间变化的染色体适应度函数为

采用轮盘赌选择法选择种群染色体中适应度大的作为子代种群，种群选择比率为f,即有适应度大的前Nf个染色体将被选作子代种群。

3.2.3 交叉和变异操作

交叉操作是遗传算法的主要操作，组合出新个体在串空间内进行有效搜索。针对补苗移栽路径的编码染色体具有正负交叉、基因不重复的特点，本文改进了交叉操作方法，具体过程如下。

假设p=4,移栽穴盘的前4个待补苗孔穴和供苗穴盘的43株健康钵苗孔穴编码可随机产生移栽路径，任选2条作交叉操作示例。A=(32，-3，25，-2，12，-4，9，-1)，B=(28，-1，32，-3，20，-2，16，-4)。随机生成2个介于1与2p之间的常数a和b，将A、B染色体的第a位开始至a+b位基因互换。设a=2，b=3，可得A1=(32，-1，32，-3，12，-4，9，-1)，B1=(28，-3，25，-2，20，-2，16，-4)。若a+b>2p，则令a+b=2p。最后遍历A1、B1，将其中相同的基因用不在该染色体中的其它基因随机替换，可得A2=(32，-1，18，-3，12，-4，9，-2)，B2=(28，-3，25，-2，20，-1，16，-4)。通过以上交叉操作可扩大搜索范围，也保持了补苗路径染色体的编码要求。

变异操作可使遗传算法避免过早收敛于非全局最优点，保持种群多样性。常用的单点基因变异也不适合于补栽路径染色体正负交叉、基因不重复的编码特点。改进后的方法具体如下。

随机生成1个介于1～2p之间的常数c，将交叉操作后产生的染色体(设为A2)的第c位进行变异。首先判别c位基因的正负性，选择相应的其它正负基因随机替换，并遍历染色体其它基因位，若出现相同替换基因，则用原变异基因替换。设c=3，则A2的负基因位变异，可变异得到A3=(32，-1，18，-4，12，-3，9，-2)；设c=5，则A2的正基因位变异，可变异得到A4=(32，-1，18，-3，6，-4，9，-2)。通过增加判别步骤进行基因点变异，可满足特有的补苗路径染色体变异操作的要求。

图9 贪心遗传算法补苗移栽路径规划方法Fig.9 Greedy genetic algorithm for seedlings replugging tour

3.2.4 重插入和算法终止

重插入操作使种群个体被不断筛选和进化时保持规模不变。初始种群经选择、交叉和变异操作，形成Nf个染色体的新种群；再将初始种群适应度大的前N～Nf个染色体合并构成子代种群。

该分段遗传算法的目标是找寻该分段优化补苗路径，经过M代种群进化，新产生种群的适应度基本保持不变，可判定算法已基本收敛。通过预设种群优化的代数作为该分段遗传算法的终止条件，种群内的最优个体即为该分段的优化路径。

第1分段补苗路径遗传优化后，按上述分段编码方法对第2分段进行初始种群编码，以及选择、交叉、变异和重插入等操作，如此循环，直至最后分段；将各分段的优化路径从原点开始首尾相接，得到该贪心遗传算法的补苗移栽路径。本文各分段的先后顺序采用前期贪心算法研究中的扫描顺序的最优方案[27]，即补苗穴盘从上至下、从右至左的分段顺序进行规划。

贪心遗传算法的各遗传算子保持与全遗传算法一致，各分段遗传均能有效收敛，图9a和图9b分别为图8所示补苗移栽模型的第1分段和整体的贪心遗传算法优化路径。

4 试验与结果分析

4.1 贪心遗传算法分段步长选择

本文所提出的路径规划的贪心遗传算法的本质是将全遗传算法[26]分拆为多段进行局部遗传运算。贪心遗传算法的分段步长对规划路径的影响通过试验分析得到。

假设温室育苗劣质苗比例占5%～20%，随机生成5组空穴孔数分别为2～6的32孔和8组空穴孔数分别为3～10的50孔补苗穴盘，另外对应随机生成含最少空穴孔数的供苗穴盘，各组为20个样本；同样，随机生成11组空穴孔数分别为4～14的72孔和21组空穴孔数分别为6～26的128孔补苗穴盘，及相对应含最少空穴孔数的供苗穴盘，各组为20个样本；采用不同分段步长的贪心遗传算法分别对上述稀疏和密集穴盘组进行总共6 960次的补苗移栽路径规划，其中分段步长取值介于穴盘空穴孔数和该规格穴盘含最少空穴孔数之间。对各规格含不同空穴孔数的穴盘组补苗规划路径长度取平均值进行统计分析，图10为32孔、50孔、72孔和128孔规格穴盘补苗路径长度均值与分段步长的关系,图例中的数字表示空穴孔数。

图10 各种穴盘补苗路径长度均值与分段步长关系Fig.10 Relationships between average replugging path length and segmentation step value for various seedling trays

由图10可知不同空穴孔数的穴盘补苗路径分层明显，所规划补苗路径长度随穴盘的空穴孔数增加而增加。不同分段步长对相同空穴数穴盘规划路径的最大最小极差值在733 mm范围内变化，小于补苗总路径的6.5%。图11为不同分段步长对应各规格穴盘所有样本路径波动均值。进一步通过方差分析，按α=0.05水准，不同分段步长对32、50、72和128孔规格穴盘路径波动的显著性检验结果分别为不显著(p=0.171)、显著(p=0.018)、极显著(p=0.001)和极显著(p=0.001)。由于前期研究全遗传算法[26]对稀疏穴盘(50孔以下、空穴孔数在10以内)进行补苗规划，其运算时间满足苗盘传输单元和移栽单元间的作业节拍衔接。为使本文的贪心遗传算法规划密集穴盘的补苗路径运算时间也满足上述要求，需将分段步长取值在10以内；而分段步长在8～10范围内所对应72孔和128孔密集穴盘的路径波动均值最小。经收敛性测试，分段步长取8，优化代数取100时能使128孔密集穴盘的各分段得到图6所示全遗传算法优化600代的收敛水平，平均运算时间为1.81 s。

图11 不同分段步长对应各规格穴盘路径波动均值Fig.11 Average path fluctuation of different segmentation step values for all seedling trays

在21组128孔穴盘样本中随机每组选择1个样本，采用贪心遗传算法和全遗传算法对各样本重复运算20次进行路径规划，对应各空穴孔数穴盘的多次规划路径的极差范围分别为7～511 mm和7～432 mm。通过t检验，两种算法得到的结果差异不显著(p>0.281)，说明贪心遗传算法具有和全遗传算法一样的可重复性，适合补苗路径规划。

4.2 密集穴盘补苗移栽路径规划比较

为检验该贪心遗传算法对密集穴盘补苗移栽路径规划效果，随机生成的11组空穴孔数分别为4～14的72孔和21组空穴孔数分别为6～26的128孔补苗穴盘，及相应随机生成含最少空穴孔数的供苗穴盘，各组为20个样本，进行路径规划比较。图12、13为上述4种方案分别对72孔和128孔穴盘规划路径长度均值与穴盘空穴数变化的关系。

图12 72孔穴盘补苗路径长度均值与穴盘空穴数关系Fig.12 Relationships between average replugging path length and vacancy holes for 72 holes seedling tray

图13 128孔穴盘补苗路径长度均值与穴盘空穴数关系Fig.13 Relationships between average replugging path length and vacancy holes for 128 holes seedling tray

对比可知，4种方案从规划路径最短目标的优劣角度排序，依次为全遗传算法(GA)、贪心遗传算法(GGA)、贪心算法(GAS)和固定顺序方法(FS)。全遗传算法和贪心遗传算法规划路径均值差在0.443 m以内，从图12、13的路径均值中可看出，两者非常接近。贪心遗传算法对72孔和128孔穴盘规划补苗路径，长度均值相比固定顺序方法分别缩短1.253～4.024 m和1.903～7.353 m,优化幅度分别为33.8%～37.7%和34.5%～41.3%，缩短距离与穴盘空穴数成正比。图14为贪心遗传算法对128孔含空穴穴盘进行补苗移栽路径规划示例。

图14 贪心遗传算法补苗移栽路径规划示例Fig.14 Example of replugging path planning by GGA

穴盘空穴孔数量增加使路径规划算法的运算量加大，同时也延长了算法的运算时间。本文对含最大空穴数26的128孔规格穴盘补苗规划，从而得到规划算法的最大运算时间，全遗传算法、贪心遗传算法、贪心算法和固定顺序方法的运行平均时间分别为：5.59、1.81、0.000 4、0.000 3 s。综上可见，全遗传算法和贪心遗传算法对补栽路径的优化性能相近，均优于贪心算法和固定顺序方法，而贪心遗传算法的运算时间则更加有利于苗盘传输单元和移栽单元间的作业节拍衔接。这是因为贪心遗传算法利用贪心算法为框架筛选、快速将补栽空穴孔排序分段，再融合遗传算法对各分段空穴孔补栽路径优化。此融合缩短了遗传算法的路径编码，减少了运算时间，从而提高算法的综合性能。

5 结论

(1)贪心遗传算法分段步长取8，优化代数取100时，可实现对稀疏和密集穴盘的补苗路径优化，重复运算的极差小于511 mm，具有鲁棒性。

(2)该贪心遗传算法的构建结合了贪心算法和全遗传算法的特点，所规划补苗路径要优于贪心算法，与全遗传算法规划路径差值在443 mm以内。

(3)该贪心遗传算法所规划补苗路径比未经优化的固定顺序补苗路径缩短33.8%～41.3%，其优化长度随穴盘空穴数增加而加长。

(4)该贪心遗传算法对稀疏和密集穴盘路径规划运算可在1.81 s内完成，比全遗传算法的5.59 s要短，更加有利于自动移栽机苗盘传输单元和移栽单元间的作业节拍衔接。

1 KUTZ L J, MILES G E, HAMMER P. Robotic transplanting of bedding plants[J]. Transactions of the ASAE, 1987, 30(3): 586-590.

2 YANG Y, TING K C, GIACOMELLI G A. Factors affecting performance of sliding-needles gripper during robotic transplanting of seedlings[J]. Applied Engineering in Agriculture, 1991, 7(4): 493-498.

3 TAI Y W, LING P P, TING K C. Machine vision assisted robotic seedling transplanting[J]. Transactions of the ASAE, 1994, 37(2): 661-667.

4 TING K C, GIACOMELLI G A, SHEN S J. Robot workcell for transplanting of seedlings. Part Ⅰ: layout and materials flow[J]. Transactions of the ASAE, 1990, 33(3): 1005-1010.

5 TING K C, GIACOMELLI G A, SHEN S J, et al. Robot workcell for transplanting of seedlings. Part Ⅱ: end-effector development[J]. Transactions of the ASAE, 1990, 33(3): 1013-1017.

6 RYU K H, KIM G, HAN J S. Development of a robotic transplanter for bedding plants[J]. Journal of Agricultural Engineering Research, 2001, 78(2): 141-146.

7 缪小花, 毛罕平, 韩绿化, 等. 黄瓜穴盘苗拉拔力及钵体抗压性能影响因素分析[J/OL]. 农业机械学报, 2013, 44(增刊1): 27-32. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=2013s106&journal_id =jcsam. DOI: 10.6041/j.issn.1000-1298.2013.S1.006. MIAO Xiaohua, MAO Hanping, HAN Lühua, et al. Analysis of influencing factors on force of picking plug seedlings and pressure resistance of plug seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(Supp.1): 27-32. (in Chinese)

8 蒋焕煜, 施经挥, 任烨, 等. 机器视觉在幼苗自动移钵作业中的应用[J]. 农业工程学报, 2009,25(5):127-131. JIANG Huanyu, SHI Jinghui, REN Ye, et al. Application of machine vision on automatic seedling transplanting[J].Transactions of the CSAE, 2009,25(5):127-131. (in Chinese)

9 韩绿化, 毛罕平, 胡建平, 等. 穴盘苗自动移栽钵苗力学特性试验[J]. 农业工程学报, 2013, 29(2): 24-29. HAN Lühua, MAO Hanping, HU Jianping, et al. Experiment on mechanical property of seedling pot for automatic transplanter[J]. Transactions of the CSAE, 2013, 29(2): 24-29. (in Chinese)

10 田素博, 王荣华，邱立春. 温室穴盘苗自动移栽输送系统设计[J]. 沈阳农业大学学报, 2009, 40(4): 620-622. TIAN Subo, WANG Ronghua, QIU Lichun. Design on conveyor system of automatic transplanting for plug seedling in greenhouse[J]. Journal of Shenyang Agricultural University, 2009, 40(4): 620-622. (in Chinese)

11 孙国祥, 汪小旵, 何国敏, 等. 穴盘苗移栽机末端执行器设计与虚拟样机分析[J]. 农业机械学报, 2010,41(10):48-53. SUN Guoxiang, WANG Xiaochan, HE Guomin, et al. Design of the end-effector for plug seedlings transplanter and analysis on virtual prototype[J]. Transactions of the Chinese Society for Agricultural Machinery, 2010, 41(10): 48-53. (in Chinese)

12 TONG J H, LI J B, JIANG H Y. Machine vision techniques for the evaluation of seedling quality based on leaf area[J]. Biosystems Engineering, 2013, 115(3): 369-379.

13 韩绿化, 毛罕平, 严蕾, 等. 穴盘育苗移栽机两指四针钳夹式取苗末端执行器[J/OL]. 农业机械学报, 2015, 46(7):23-30. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20150704&journal_id=jcsam. DOI:10.6041/j.issn.1000-1298.2015.07.004. HAN Lühua, MAO Hanping, YAN Lei, et al. Pincette-type end-effector using two fingers and four pins for picking up seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(7): 23-30. (in Chinese)

14 丁文芹, 毛罕平, 胡建平, 等. 穴盘苗自动移栽机的结构设计及运动仿真分析[J]. 农机化研究, 2011,33(10):75-77, 137. DING Wenqin, MAO Hanping, HU Jianping, et al. Structure design and simulation analysis on the plug seedlings auto-transplanter[J]. Journal of Agricultural Mechanization Research, 2011, 33(10):75-77, 137.(in Chinese)

15 冯青春, 王秀, 姜凯, 等. 花卉幼苗自动移栽机关键部件设计与试验[J]. 农业工程学报, 2013,29(6):21-27. FENG Qingchun, WANG Xiu, JIANG Kai, et al. Design and test of key parts on automatic transplanter for flower seedling[J]. Transactions of the CSAE, 2013, 29(6):21-27.(in Chinese)

16 杨扬, 曹其新, 盛国栋, 等. 基于机器视觉的育苗穴盘定位与检测系统[J/OL]. 农业机械学报, 2013, 44(6):232-235. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130640&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.06.040. YANG Yang, CAO Qixin, SHENG Guodong, et al. Plug tray localization and detection system based on machine vision[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(6): 232-235. (in Chinese)

17 杨振宇, 张文强, 李伟，等. 基于单目视觉的移栽钵苗叶片朝向的调整方法[J]. 农业工程学报, 2014, 30(14): 26-33. YANG Zhenyu, ZHANG Wenqiang, LI Wei, et al. Monocular vision-based method for direction adjustment of transplanting potted-seedling leaves[J]. Transactions of the CSAE, 2014, 30(14): 26-33.(in Chinese)

18 孙国祥, 汪小旵, 何国敏. 基于边缘链码信息的番茄苗重叠叶面分割算法[J]. 农业工程学报, 2010, 26(12): 206-211. SUN Guoxiang, WANG Xiaochan, HE Guomin. Segmentation algorithm of overlapping tomato seedling leaves based on edge chaincode information[J]. Transactions of the CSAE, 2010, 26(12): 206-211.(in Chinese)

19 韩绿化, 毛罕平, 缪小花, 等. 基于穴盘苗力学特性的自动取苗末端执行器设计[J/OL]. 农业机械学报, 2013, 44(11): 260-265. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20131144&journal_id=jcsam. DOI: 10.6041/j.issn.1000-1298.2013.11.044. HAN Lühua, MAO Hanping, MIAO Xiaohua, et al. Experiment on mechanical property of seedling pot for automatic transplanter[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013,44(11):260-265.(in Chinese)

20 张丽华, 邱立春, 田素博, 等. 指针夹紧式穴盘苗移栽爪设计[J]. 沈阳农业大学学报, 2010, 41(2):235-237. ZHANG Lihua, QIU Lichun, TIAN Subo, et al. Design of a needle clamping claw for plug seedling transplanting[J]. Journal of Shenyang Agricultural University, 2010, 41(2): 235-237.(in Chinese)

21 童俊华, 蒋焕煜, 蒋卓华, 等. 钵苗自动移栽机器人抓取指针夹持苗坨参数优化试验[J]. 农业工程学报, 2014, 30(16):8-16. TONG Junhua, JIANG Huanyu, JIANG Zhuohua, et al. Experiment on parameter optimization of gripper needles clamping seedling plug for automatic transplanter[J]. Transactions of the CSAE, 2014, 30(16): 8-16. (in Chinese)

22 金鑫, 杜新武, 杨传华, 等. 蔬菜移栽穴盘苗自动输送装置设计与试验[J/OL]. 农业机械学报, 2016, 47(7): 103-111. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160715&journal_id=jcsam. DOI: 10.6041/j.issn.1000-1298.2016.07.015. JIN Xin, DU Xinwu, YANG Chuanhua, et al. Design and experiment on automatic transporting mechanism for vegetable potted seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(7): 103-111. (in Chinese)

23 赵雄, 王川, 杨茂祥, 等. 非圆齿轮行星轮系自动取苗机构逆向设计分析[J]. 农业工程学报, 2015, 31(6): 30-36. ZHAO Xiong, WANG Chuan, YANG Maoxiang, et al. Reverse design and analysis of automatic seedling pick-up mechanism with non-circular gear planetary train[J].Transactions of the CSAE, 2015, 31(6):30-36. (in Chinese)

24 俞高红, 俞腾飞, 叶秉良, 等. 一种旋转式穴盘苗取苗机构的设计[J]. 机械工程学报, 2015, 51(7): 67-76. YU Gaohong, YU Tengfei, YE Bingliang, et al. Design of a rotary plug seedling pick-up mechanism[J]. Journal of Mechanical Engineering, 2015, 51(7): 67-76.(in Chinese)

25 HU Jianping, YAN Xiaoyue, MA Jun. Dimensional synthesis and kinematics simulation of a high-speed plug seedling transplanting robot[J]. Computers and Electronics in Agriculture, 2014, 107(3): 64-72.

26 童俊华, 蒋焕煜, 周鸣川. 基于遗传算法的穴盘苗自动移钵路径优化[J/OL]. 农业机械学报, 2013,44(4):45-49. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130408&journal_id=jcsam. DOI:10.6041/j.issn.1000-1298.2013.04.008. TONG Junhua, JIANG Huanyu, ZHOU Mingchuan. Optimization of seedling transplanting path based on genetic algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013,44(4):45-49.(in Chinese)

27 童俊华, 蒋焕煜, 武传宇. 基于贪心算法的温室钵苗稀植移栽路径优化[J/OL]. 农业机械学报, 2016, 47(3):8-13. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160302&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2016.03.002. TONG Junhua, JIANG Huanyu, WU Chuanyu. Optimization of seedlings lower density transplanting path based on greedy algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(3):8-13.(in Chinese)

Optimization of Replugging Tour Planning Based on Greedy Genetic Algorithm

HE Leiying1,2YANG Taiwei1WU Chuanyu1,2YU Yaxin1,2TONG Junhua1,2CHEN Chengjin3
(1.FacultyofMechanicalEngineeringandAutomation,ZhejiangSci-TechUniversity,Hangzhou310018,China2.ZhejiangProvincialKeyLaboratoryofTransplantingEquipmentandTechnology,Hangzhou310018,China3.ZhejiangSanfengIndustrialCo.,Ltd.，Jinhua321300,China)

Replugging tasks make seedling in well consistency in greenhouses. Healthy seedlings are used to replace the ungerminated or poor growth seedlings. This task is labor intensive by traditional manual method. And automated transplanters do the replugging task in high efficiency and good quality. According to the seedlings healthy information which is detected by machine vision, end-effector grasping healthy seedlings does the repetitive replugging task. The position of vacancy holes in plug tray are randomly. Optimizing the seedling grasping sequence can decrease the transplanting path which can improve working efficiency. A greedy genetic algorithm (GGA) was proposed for replugging tour planning which combined the character of greedy algorithm (GAS) and genetic algorithm (GA). The algorithm was robustness. The GGA was suitable for sparse and dense trays’ path optimization when segmentation step value and hereditary algebra were 8 and 100, respectively. The average path deviation of GGA and GA was 443 mm. And their effectiveness was better than that of GAS. Compared with fixed sequence method (FS), the range of optimization amplitude for GGA was 33.8%～41.3%. GA and GGA could finish the optimization operation in 1.81 s and 5.59 s, respectively. The results showed that GGA was more suitable for the action requirement between delivery unit and transplanting unit. The working efficiency of automated transplanter was further improved.

automated transplanter; seedlings; greenhouses; path optimization; greedy genetic algorithm

2016-12-22

2017-02-17

国家自然科学基金项目(51675488)、浙江省自然科学基金项目(LQ16E050006)、浙江省科技厅公益项目(2017C32048)、浙江省重大科技专项重点农业项目(2015C02004)和浙江理工大学科研启动基金项目(14022211-Y)

贺磊盈(1983—)，男，讲师，博士，主要从事农业机器人技术研究，E-mail: hlying@zstu.edu.cn

武传宇(1976—)，男，教授，博士生导师，主要从事智能农业装备研究，E-mail: cywu@zstu.edu.cn

10.6041/j.issn.1000-1298.2017.05.004

S24

A

1000-1298(2017)05-0036-08