一种基于贪心遗传算法的钵苗稀植移栽路径优化方法

技术领域

本发明涉及农业机械中用于钵苗的移栽方法，尤其是涉及一种基于贪心遗传算法的钵苗稀植移栽路径优化方法。

背景技术

温室穴盘育苗中，高密度穴盘内的钵苗需要稀植移栽到低密度穴盘内，同时穴盘内的成苗率在80-95%之间。传统通过人工进行辨识移栽作业，效率低，劳动强度大，且移栽苗的一致性不好；温室钵苗稀植移栽机通过机器视觉检测钵苗健康状况和位置信息，通过末端执行器抓取移栽，可解决上述问题。

低密度穴盘孔穴多、高密度穴盘内健康苗所处位置的随机性大，移栽机控制末端执行器从原点出发至各穴孔移栽的先后选择性多，即进行稀植移栽路径的长度可变；由于孔穴数据量大，控制器计算筛选最短最优路径的方法无法满足控制实时性的要求。该种钵苗稀植移栽的路径规划方法有待开发。

发明内容

本发明的目的在于提供一种基于贪心遗传算法的钵苗稀植移栽路径优化方法，可减少温室钵苗稀植移栽机末端执行器的行走距离，提高作业效率。

为了达到上述目的，本发明采用的技术方案是：

本发明通过机器视觉己获知温室钵苗稀植移栽机的移栽穴盘内钵苗的健康信息，分别对移栽穴盘内健康苗穴位和目的穴盘内空穴位进行标记编码；贪心遗传选优原则为目的穴盘空穴孔按列分区进行局部遗传算法的当前路径优化；目的穴盘某列空穴孔编码与移栽穴盘内未规划的有苗穴孔编码综合，生成随机路径编码构成局部遗传算法的初始种群，循环进行选择、交叉、变异和重插入操作直到预设收敛代数，将种群适应度最大个体作为该局部最优路径；将先后各列规划的局部最优路径合并，即生成整个目的穴盘稀植移栽路径。

所述分别对移栽穴盘内健康苗穴位和目的穴盘内空穴位进行标记编码，具体为密度高的移栽穴盘和密度低的目的穴盘的各穴孔在移栽机系统的位置已经固定，对移栽穴盘内健康苗穴孔按从上至下、从左至右的顺序进行正实数标记，对目的穴盘内各空穴孔按从上至下、从左至右的顺序进行负实数标记，由此标记编码实际隐含有穴孔位置和钵苗健康信息。

所述目的穴盘空穴孔按列分区进行局部遗传算法的当前路径优化，具体为目的穴盘空穴孔负标记编码按穴盘列分区，按从左至右或从右至左的列顺序，先后与移栽穴盘内未规划的有苗穴孔负标记编码综合，进行局部遗传算法的当前最优路径规划。

所述目的穴盘某列空穴孔编码与移栽穴盘内未规划的有苗穴孔编码综合，生成随机路径编码构成局部遗传算法的初始种群，循环进行选择、交叉、变异和重插入操作直到预设收敛代数，将种群适应度最大个体作为该局部最优路径，具体局部遗传算法过程描述如下：

a) 局部遗传算法的初始种群生成方法具体为：假设目的穴盘某列空穴孔的负标记编码集为{-1，-2，-3，-4，-5，-6，-7，-8}，移栽穴盘内未规划的有苗穴孔正标记编码集为{1，2，3，……，48，49，50}，则移栽路径从原点出发和正负标记编码集随机交叉，可形成如（0，3，-2，8，-4，9，-7，10，-1，7，-6，13，-3，5，-5，16，-8，0）的初始种群的一条染色体，算法设置生成一定数量染色体，即构成初始种群；

b) 个体种群适应度具体为：每个染色体中的编码实际对映的移栽坐标系的位置已知，则具体每个染色体的对映的路径长度也可计算，设为l(x)，其中l_min和l_max分别表示种群染色体的最短和最长路径；定义个体种群适应度为C= (l_max- l(x))/( l_max-l_min)；

c) 局部遗传算法循环进行的选择操作为：初始种群作为父代，按照随机顺序，以染色体适应度为选择概率，选择概率M>C的染色体作为子代种群；

d) 局部遗传算法循环进行的交叉操作为：初始种群选择操作生成子代种群后，随机排序，进行交叉操作；①假设有O=（0，14，-4，9，-2，8，-7，12，-1，19，-3，13，-6，15，-8，26，-5，0），P=（0，13，-7，8，-4，9，-2，10，-1，7，-5，28，-8，5，-6，16，-3，0），Q=（0，12，-6，30，-3，19，-8，11，-1，16，-2，5，-4，14，-5，10，-7，0）三条子代种群染色体；②产生2个介于1至16之间的随机数j和k，其中j作为交配指示位，k作为交配步长，则三条子代染色体的第j+1位至j+k位递进互换；若j+k≥16,令取为16；设j=8，k=4,可得到交叉后个体：O₁=（0，14，-4，9，-2，8，-7，12，-1，16，-2，5，-6，15，-8，26，-5，0），P₁=（0，13，-7，8，-4，9，-2，10，-1，19，-3，13，-8，5，-6，16，-3，0），Q₁=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，-5，10，-7，0）；③扫描除原点0的交叉后个体位，若相同则用800代替，即可得O₂=（0，14，-4，9，-2，8，-7，12，-1，16，800，5，-6，15，-8，26，-5，0），P₂=（0，13，-7，8，-4，9，-2，10，-1，19，-3，800，-8，5，-6，16，800，0），Q₂=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，800，10，-7，0）；④扫描除原点0的上一步个体，将数800依次使用有效个体位代替；若数800处于偶数位，则将目的穴盘内该列所有标记编号顺序扫描与个体位除原点0后的每个偶数位对比，若未曾出现过，则以此来代替800；若数800处于奇数位，则将移栽穴盘内未规划的所有有苗标记编号顺序扫描与个体位除原点0后的每个奇偶数位对比，将未曾出现过的标记随机产生一个来代替800；即可得到O₃=（0，14，-4，9，-2，8，-7，12，-1，16，-3，5，-6，15，-8，26，-5，0），P₃=（0，13，-7，8，-4，9，-2，10，-1，19，-3，28，-8，5，-6，16，-5，0），Q₃=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，-2，10，-7，0）；

e) 局部遗传算法循环进行的变异操作为：对上述交叉操作产生的种群随机排序，进行变异操作；产生2个介于1至16之间的随机数r和s，作为个体除原点0的2个变异位：

若变异位的标记编码为负，则从目的穴盘列其它负标记编码随机选择一个，从变异个体中扫描找到该值与变异位互换：假设r＝2，子代个体O₃=（0，14，-4，9，-2，8，-7，12，-1，16，-3，5，-6，15，-8，26，-5，0），则在除-4标记数的{-1，-2，-3，-5，-6，-7，-8}中产生一个随机数，设为-7，则变异后新子代个体O₄=（0，14，-7，9，-2，8，-4，12，-1，16，-3，5，-6，15，-8，26，-5，0）；

若变异位的标记编码为正，则从移栽穴盘内未规划的所有有苗正标记编码随机选择一个进行互换，并遍历基因替换后的子代个体，若有同的正标记编码，则用原标记编码数代替：假设s＝9，子代个体P₃=（0，13，-7，8，-4，9，-2，10，-1，19，-3，28，-8，5，-6，16，-5，0），则在除19标记数的{1，2，3，……，48，49，50}中产生一个随机数，设为20，则变异后新子代个体P₃=（0，13，-7，8，-4，9，-2，10，-1，20，-3，28，-8，5，-6，16，-5，0）；

f) 局部遗传算法循环进行的重插入操作为：对上述初始种群经选择、交叉、变异后产生的子代个体进行适应度计算，重插入初始种群代替最不适应的父代个体，保持初始种群规模；

局部遗传算法通过对上述初始种群循环进行选择、交叉、变异和重插入操作，到达预设收敛代数停止，取该收敛代的种群适应度最大个体作为该局部最优路径。

待所有目的穴盘各列的局部最优路径获得后，按照从左至右或从右至左的列顺序合并，生成整个目的穴盘的稀植移栽路径。

本发明具有的有益效果是：

本发明通过机器视觉检测得到高密度移栽穴盘钵苗健康状况和位置信息，运用贪心遗传算法为技术手段，完成快速优化高密度移栽穴盘钵苗向低密度目的穴盘稀植移栽路径，从而提高末端执行器作业效率。

附图说明

图1是本发明基于贪心遗传算法的钵苗稀植移栽路径优化方法的流程图。

图2是移栽穴盘和目的穴盘的标记编码图。

图3是局部遗传优化中优化代数变化图。

图4是目的穴盘单列穴孔局部遗传优化结果。

图5是各列顺序综合后稀植移栽路径图。

具体实施方式  

下面结合方法流程图和实施例对本发明作进一步说明。

本发明的方法流程图如图1所示：本发明通过机器视觉获知穴盘内钵苗的健康信息，分别对移栽穴盘内健康苗穴位和目的穴盘内空穴位进行标记编码（如图2所示）。贪心遗传选优原则为目的穴盘空穴孔按列分区进行局部遗传算法的当前路径优化；目的穴盘某列空穴孔编码与移栽穴盘内未规划的有苗穴孔编码综合，生成随机路径编码构成局部遗传算法的初始种群，循环进行选择、交叉、变异和重插入操作直到预设收敛代数（如图3所示），将种群适应度最大个体作为该局部最优路径（如图4所示）；将先后各列规划的局部最优路径合并，即生成整个目的穴盘稀植移栽路径（如图5所示）。

P1：密度高的移栽穴盘和密度低的目的穴盘的各穴孔在移栽机系统的位置已经固定，移栽穴盘内钵苗健康信息也通过机器视觉获得，对移栽穴盘内健康苗穴孔按从上至下、从左至右的顺序进行正实数标记，对目的穴盘内各空穴孔按从上至下、从左至右的顺序进行负实数标记，由此标记编码实际隐含有穴孔位置和钵苗健康信息。如图2所示，目的穴盘4×8规格，空穴孔标记编码集为{-1，-2，-3，……，-32}；移栽穴盘5×10规格，含健康钵苗42株，标记编码集为{1，2，3，……，40，41，42}。

P2：目的穴盘空穴孔按列分区进行遗传算法的当前最优路径规划，具体为目的穴盘空穴孔负标记编码按穴盘列分区，按从左至右或从右至左的列顺序，先后与移栽穴盘内未规划的有苗穴孔负标记编码综合，进行局部遗传算法优化的初始种群。以图2稀植移栽模型为例，目的穴盘最左列标记编码{-1，-2，-3，-4，-5，-6，-7，-8}，移栽穴盘当前未规划有苗穴孔标记编码{1，2，3，……，40，41，42}，从原点出发、相互随机交叉综合，可形成如（0，3，-2，8，-4，9，-7，10，-1，7，-6，13，-3，5，-5，16，-8，0）的初始种群的一条染色体，设置生成一定数量染色体，即构成初始种群。

P3： 每个染色体中的编码实际对映的移栽坐标系的位置已知，则具体每个染色体的对映的路径长度也可计算，设为l(x)，其中l_min和l_max分别表示种群染色体的最短和最长路径；定义个体种群适应度为C= (l_max- l(x))/( l_max-l_min)。初始种群作为父代，按照随机顺序，以染色体适应度为选择概率，选择概率M>C的染色体作为子代种群。

P4： 初始种群选择操作生成子代种群后，随机排序，进行交叉操作。①假设有O=（0，14，-4，9，-2，8，-7，12，-1，19，-3，13，-6，15，-8，26，-5，0），P=（0，13，-7，8，-4，9，-2，10，-1，7，-5，28，-8，5，-6，16，-3，0），Q=（0，12，-6，30，-3，19，-8，11，-1，16，-2，5，-4，14，-5，10，-7，0）三条子代种群染色体；②产生2个介于1至16之间的随机数j和k，其中j作为交配指示位，k作为交配步长，则三条子代染色体的第j+1位至j+k位递进互换；若j+k≥16,令取为16；设j=8，k=4,可得到交叉后个体：O₁=（0，14，-4，9，-2，8，-7，12，-1，16，-2，5，-6，15，-8，26，-5，0），P₁=（0，13，-7，8，-4，9，-2，10，-1，19，-3，13，-8，5，-6，16，-3，0），Q₁=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，-5，10，-7，0）；③扫描除原点0的交叉后个体位，若相同则用800代替，即可得O₂=（0，14，-4，9，-2，8，-7，12，-1，16，800，5，-6，15，-8，26，-5，0），P₂=（0，13，-7，8，-4，9，-2，10，-1，19，-3，800，-8，5，-6，16，800，0），Q₂=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，800，10，-7，0）；④扫描除原点0的上一步个体，将数800依次使用有效个体位代替；若数800处于偶数位，则将目的穴盘内该列所有标记编号顺序扫描与个体位除原点0后的每个偶数位对比，若未曾出现过，则以此来代替800；若数800处于奇数位，则将移栽穴盘内未规划的所有有苗标记编号顺序扫描与个体位除原点0后的每个奇偶数位对比，将未曾出现过的标记随机产生一个来代替800；即可得到O₃=（0，14，-4，9，-2，8，-7，12，-1，16，-3，5，-6，15，-8，26，-5，0），P₃=（0，13，-7，8，-4，9，-2，10，-1，19，-3，28，-8，5，-6，16，-5，0），Q₃=（0，12，-6，30，-3，19，-8，11，-1，7，-5，28，-4，14，-2，10，-7，0）。

P5：对上述交叉操作产生的种群随机排序，进行变异操作。产生2个介于1至16之间的随机数r和s，作为个体除原点0的2个变异位：

若变异位的标记编码为负，则从目的穴盘列其它负标记编码随机选择一个，从变异个体中扫描找到该值与变异位互换：假设r＝2，子代个体O₃=（0，14，-4，9，-2，8，-7，12，-1，16，-3，5，-6，15，-8，26，-5，0），则在除-4标记数的{-1，-2，-3，-5，-6，-7，-8}中产生一个随机数（设为-7），则变异后新子代个体O₄=（0，14，-7，9，-2，8，-4，12，-1，16，-3，5，-6，15，-8，26，-5，0）；

若变异位的标记编码为正，则从移栽穴盘内未规划的所有有苗正标记编码随机选择一个进行互换，并遍历基因替换后的子代个体，若有同的正标记编码，则用原标记编码数代替：假设s＝9，子代个体P₃=（0，13，-7，8，-4，9，-2，10，-1，19，-3，28，-8，5，-6，16，-5，0），则在除19标记数的{1，2，3，……，48，49，50}中产生一个随机数（设为20），则变异后新子代个体P₃=（0，13，-7，8，-4，9，-2，10，-1，20，-3，28，-8，5，-6，16，-5，0）。

P6：局部遗传算法循环进行的重插入操作为：对上述初始种群经选择、交叉、变异后产生的子代个体进行适应度计算，重插入初始种群代替最不适应的父代个体，保持初始种群规模。

P7：局部遗传算法判断是否到达预设收敛代数停止，未到达则对种群循环进行P3至P6的选择、交叉、变异和重插入操作；若到达则进入下一步P8。

P8：到达预设收敛代数停止，并输也优化结果。如图3所示，取第70代作为收敛代数，种群适应度最大个体作为该局部最优路径为（0，4，-4，11，-3，2，-1，1，-2，3，-5，5，-8，7，-7，6，-6，0），如图4所示。

P9：判断目的穴盘各列是否均已经完成局部路径优化，若未完成则按顺序逐列从P2步骤开始循环，如图4按从左至右的顺序；若各列均已经完成，进入下一步P10。

P10：合并全部列的局部优化路径，生成整个目的穴盘的稀植移栽路径。如图5所示，合并路径为（0，4，-4，11，-3，2，-1，1，-2，3，-5，5，-8，7，-7，6，-6，14，-15，15，-16，22，-13，18，-9，9，-10，8，-11，10，-12，12，-14，23，-24，24，-23，13，-21，19，-18，17，-20，30，-22，21，-19，16，-17，36，-30，25，-31，33，-29，20，-28，29，-27，28，-25，27，-26，31，-32，0）。