基于多变异分组遗传算法的多机协同作业静态任务分配

王 猛 赵 博 刘阳春 汪凤珠 伟利国 方宪法

(中国农业机械化科学研究院土壤植物机器系统技术国家重点实验室， 北京 100083)

0 引言

农业生产一般具有很强的“农时”性和严格的作业窗口期。随着农机自动导航技术的发展和推广，智能农机及其导航技术已成为智慧农业的重要组成部分，多台农机或多种农机的协同作业技术可发挥机群作业优势、提高农机作业效率，已逐渐成为新的研究热点[1-3]。

多机协同作业技术在机器人、无人机等领域已进行了较多的研究，任务分配是其研究热点之一，即给定一个机器人(或无人机)集合、一个任务集合及系统性能评价指标，为每个子任务寻找一台合适的机器人(或无人机)负责执行该子任务，且使机器人(或无人机)系统完成任务集合中的全部任务时所获得的收益最大[4]。通过对多机作业进行任务分配可以加快机群任务执行速度、降低系统消耗，并提高工作效率[5-15]。多机协同任务分配技术在机器人工业生产、水下机器人搜索、无人机作战和无人机灾难搜索等领域已进行了较深入的试验研究和应用[16-20]。多机协同任务分配技术在农业领域研究较少，相比于无人机或机器人的任务分配问题，农机作业情况更加复杂，农机需依次到达目的地，并且在目的地完成作业。JENSEN等[21]提出1台运粮车为多台收获机运粮的路径规划方法，多台收获机在不同的地块进行收获作业，运粮车根据自身速度和收获机的作业位置、作业路径和作业速度等参数，通过Dijkstar算法规划运粮车田间和田内路径，实现了行驶距离和用时的最优，该方法不仅实现了运粮车田间的路径规划，也实现了田内的路径规划，具有较高的参考价值。以前，农机常常分散在农村多个机主手中，农机数量和性能与需要作业的任务地块参数未知，不具备任务分配条件。我国农机合作社的发展和农机作业远程平台的研发为农机任务分配技术提供了必要性和可行性条件[22-23]。

本文根据我国农机合作社农机实际作业模式，综合考虑机群的作业时间、作业油耗和路程代价等因素，构建多机协同目标函数，根据多机协同作业特点构建多变异分组遗传算法，设计两段式编码、分组交叉算子和多种变异算子，优化目标函数，降低系统代价，以实现多机协同静态任务分配。

1 多机协同场景

农机多机协同作业静态任务分配指农机机群作业前将作业任务和任务顺序分配给指定农机的过程。以某个作业季农机合作社中常见作业场景为例，即合作社的多台同种农机同时从车库出发，分别完成各自多个指定的任务后又回到车库。用集合{a1，a2，…，am}表示m台作业农机；用集合{T1，T2，…，Tn}表示n个作业任务。第i台农机的性能参数表示为ai={vwi，di，wi，vi，tti，cwi，cvi}(i=1，2，…，m)，其中vwi表示第i台农机作业的平均速度(km/h)，di表示第i台农机的作业幅宽(m)，wi表示第i台农机的平均作业能力(m2/h)，vi表示第i台农机非作业状态行驶平均速度(km/h)，tti表示第i台农机作业中每次调头的平均时间(h)，cwi表示第i台农机作业时单位时间的平均油耗(L/h)，cvi表示第i台农机非作业状态行驶单位时间的平均油耗(L/h)；第j个任务的参数表示为Tj={x1j，y1j，x2j，y2j，x3j，y3j，x4j，y4j，dTj，lTj，Sj}(j=1，2，…，n)，其中(x1j，y1j)、(x2j，y2j)、(x3j，y3j)和(x4j，y4j)分别表示任务Tj地块4个顶点的坐标，dTj表示任务Tj垂直作业路径的宽度，lTj表示任务Tj平行作业路径的长度，Sj表示任务Tj的作业面积，如图1所示。

2 多机协同代价数学模型

2.1 多机协同作业基本假设

农机协同作业实际情况复杂，为了简化问题，方便计算，根据农机合作社的作业特点设定的基本假设如下:①农机性能参数和任务参数已知。②需要作业的任务数量大于农机的数量。③每个任务地块只能有一台农机作业，单台农机可以完成多地块作业。④每个任务地块分配给指定农机后，任务地块路径规划结果已知。⑤每个作业任务面积适中。⑥农机同时从车库出发，完成分配的全部任务后回到车库。⑦全部农机完成分配的任务回到车库后认为任务全部完成。

2.2 多机协同代价函数

农机完成作业任务的代价包括农机到达指定任务和回到车库的路程、总的作业时间和油耗等，并根据每个部分的重要程度定义该部分的权重。

对于m台农机，n个作业任务的情况，给出以下目标函数

(1)

式中f——多机协同代价

si——第i台农机完成作业任务时路上的总路程

α、β、γ——权重，α、β、γ∈[0,1]

ci——第i台农机完成任务的油耗

ti——第i台农机完成任务的时间

(1)总路程si由3部分组成：农机ai从车库到其第1个任务Tj的路程s(ai，Tj)；农机ai从其第j个任务Tj到下一个任务Tk的路程s(ai，TjTk)；农机ai从其最后一个任务Tl回到车库的路程s(ai，Tl)，其中j、k、l∈{1，2，…，n}。

(2)

其中

(3)

(4)

(5)

(2)油耗ci由3部分组成：农机路上油耗、作业过程中调头油耗和作业油耗。

(6)

其中

(7)

(8)

式中kij——第i台农机在第j个任务地块作业行数

「⎤——向上取整运算符

(3)完成任务时间ti由3部分组成：农机路上时间、农机作业时间和农机田间调头时间。

(9)

(4)将车库作为起点，即第1个点，n个任务依次作为第2到n+1个点，任意两点间实际可行驶的最短距离的矩阵D为

(10)

式中di,j——第i-1个任务点到第j-1个任务点之间可行驶的最短距离(i、j=2,3，…,n+1，i≠j)，km

如果j、k2个任务地头相邻且作业过程中农机可从地头连接处进入地块，如图2所示，则该2个任务点之间的最短距离为0。矩阵D是一个对角线为0的对称矩阵，第1行d1，j(j=2,3，…,n+1)表示农机从车库到第j-1个任务点的距离。

式(2)中s(ai，Tj)=d1，j+1，s(ai，Tl)=d1，l+1。农机进入任务地块的方式分为从路上进入和从地头连接处进入，令x=0表示农机从路上进入任务地块，x=1表示农机从地头连接处进入任务地块；令y=0表示农机在该任务完成后回到路边，y=1表示农机在该任务完成后回到地头连接处。农机进入第1个任务地块时从路上进入，第i台农机在第j个任务地块作业完成后的位置

yij=(kij+xij)%2

(11)

式中xij——第i台农机进入第j个任务地块的标识

%——求余运算符

当dj+1,k+1≠0时，农机ai从任务j到任务k的距离为

s(ai，TjTk)=dj+1，k+1+yijlTj

(12)

xik=0

(13)

当dj+1，k+1=0时，任务i、j地头相连，此时农机ai从任务j到任务k的距离为

s(ai，TjTk)=|yij-1|lTj

(14)

xik=1

(15)

3 任务分配方法

遗传算法通常包括选择、交叉和变异3个基本步骤，本文提出一种多变异分组遗传算法，设计了两段式编码，采用了轮盘赌选择染色体的方法，设计了交叉和多种变异算子，有效地解决了多机协同任务分配问题。

3.1 算法设计

3.1.1编码

根据文献[24]设计了两段式编码，如图3所示。第1段表示任务的排序，n个任务由1到n，n个数字表示，共n位；第2段表示分组的位置，共m-1位(n=12，m=3)。第i台农机的任务用集合Ci表示，则某一个父代染色体由集合p={C1，C2，…，Cm}表示。

3.1.2选择算子

定义适应度函数，适应度越高的染色体表示任务分配效果越好。适应度函数

(16)

(1)交叉算子选择

采用轮盘赌选择法选择种群中进行交叉的个体。

(2)最优个体保留

为提高算法效率采用最优个体保留方法。最优个体保留步骤:①找出当前群体中适应度最高的个体和适应度最低的个体。②若当前群体中最佳个体适应度比迄今为止最佳个体的适应度高，则以当前种群中的最佳个体作为迄今为止最佳个体。③用迄今为止最佳的个体替换当前群体中最差的个体。

3.1.3交叉算子

分组交叉算子设计过程如图4所示，其实现方式如下：①用轮盘赌方法选择2个父代，同时产生1到m的随机序列。②按随机序列的顺序进行分组遗传，设随机序列第1个数为k，产生随机数Rr∈[0,1)，如果Rr<0.5则第1个父代的第k组作为子代的第k组，如果Rr≥0.5则第2个父代的第k组作为子代的第k组。③从2个父代中删除子代中包含的任务，按照步骤②方式进行序列第2到m位代表的组数进行分组交叉遗传。④将未参与交叉运算的剩余任务随机插入到子代中得到最终的子代。

3.1.4变异算子

为了加快进化过程，增加基因多样性，提高遗传算法效率，提出几种变异算子。

3.1.4.1组间转移变异算子

设计了组间转移变异算子(ITVO)，过程如图5所示。①在某条染色体随机选取2个不同的组作为移出组和移入组Ogroup、Igroup∈{1，2，…，m}。②如果移出组Ogroup中任务数量大于1，则随机从移出组和移入组选取2个点Opoint、Ipoint作为移出任务位置和移入任务位置。③将移出任务位置Opoint对应的任务移动到移入位置Ipoint对应的任务前完成组间转移，并相应修改分组间断点的值。

3.1.4.2组间交换变异算子

为了提高染色体多样性，加快算法的收敛，设计了一种组间交换算子(IEVO)，交换算子的实现形式如图6所示。①从染色体的第1到m组分别随机选择用做交换任务的点。②移除选中点的任务。③将移除的任务进行排序，并按排列后的顺序插入到交换任务点。

3.1.4.32-opt局部优化变异算子

2-opt属于局部搜索算法，是解决组合优化问题的有效工具，该算法的实现方式：①在染色体的某组内随机选取2个点i、j。②i前的路径不变添加到新路径中，将i到j之间的路径翻转其编码后添加到新路径，将j之后的路径不变添加到新路径。

2-opt算法示意图如图7所示，该示意图中基因分组间断点为3、9，2-opt优化组在第2组，2-opt变异点为4、8。

3.1.4.4突变算子组合

将3种变异算子组合成多变异算子网络，如图8所示，每个节点表示一个算子，有向边表示上一个算子结束后选择下一个算子的概率。

3.2 算法流程

本文设计算法的流程如图9所示，具体为：

(1)根据编码方式产生数量为N的初始种群作为父代，计算每个父代的适应度，定义分组交叉概率Pc、组间转移变异概率Pm1、组间交换变异概率Pm2、2-opt局部优化变异概率Pm3和迭代次数K。

(2)基于轮盘赌方法选择2个父代，产生随机数Rr∈[0,1)，如果RrPc，适应度较好的父代直接复制到子代，计算子代适应度和种群数量，如果子代种群数量小于N，重复步骤(2)。

(3)从子代第1个个体开始，产生随机数Rr∈[0,1)，如果Rr

(4)将此时的子代作为当前种群，计算变异后每个个体的适应度，执行最优个体保留方法。

(5)判断是否达到迭代次数，如果未达到迭代次数，执行步骤(2)；如果达到迭代次数，则选择当前种群适应度最高的个体作为该任务分配的解。

4 仿真分析

为了确定算法参数并验证算法的有效性，设计了12个任务地块和3台农机的仿真试验，假设任务分配过程中，任务地块作业路径方向与任务地块现有实际作业路径方向相同。确定参数过程中取目标函数式(1)中系数α=0、β=0、γ=1，即直接用完成任务时用时最长的农机作业时间作为机群代价优化目标函数，试验任务电子地图如图10所示。图中1～12表示任务地块编号。

3台农机的性能如表1所示，根据平台得到任务参数如表2所示。

表1 农机性能参数

表2 任务参数

多变异遗传算法包括Pc、Pm1、Pm2和Pm34个参数，采用正交试验方法研究每个参数对算法的影响，每个参数取4个水平，根据单个算子优化试验结果，选择交叉算子概率Pc取值0.4～1，间隔0.2；组间转移变异算子概率Pm1取值0.4～1，间隔0.2；组间交换变异算子概率Pm2取值0.4～0.7，间隔0.1；2-opt变异算子概率Pm3取值0.4～1，间隔0.2。

根据参数的水平选择正交试验表L16(45)，计算20次每种组合计算结果的平均值作为该种组合的优化结果，迭代次数为1 000次，通过计算极差得到参数对结果的影响从大到小依次是Pm2、Pm3、Pm1和Pc，取使计算结果得到最小值的参数水平：Pm2=0.7、Pm3=1、Pm1=0.6和Pc=0.6。

为验证算法的有效性，分别采用确定参数后的多变异分组遗传算法(MGGA)与文献[23]改进的分组遗传算法(IGGA-SS)和文献[24]多染色体遗传算法(MGA)对试验任务进行仿真试验，迭代次数取1 000次，重复20次，每次迭代的值取20次试验的平均值，得到图11所示结果。可以看到多变异遗传算法可以在较小的迭代次数下得到较优的结果。

针对3种算法进行9、12、15个任务的任务分配试验，分别使用多变异遗传算法(MGGA)、改进分组遗传算法(IGGA-SS)和多染色体遗传算法(MGA)对几种任务分配问题独立做250、500、750、1 000次迭代试验，每个算法每次迭代20次取平均值，得到的平均时间代价和平均用时如表3所示。

表3 3种算法对几种问题的解

由表3可知：相同迭代次数下，多变异遗传算法(MGGA)运行时间最长、效果最优，最小代价降低1%～5%；在分组数量和迭代次数相同条件下，随着任务数量的增加多变异遗传算法(MGGA)运行时间未出现明显的增加；在相同运行时间条件下，多变异遗传算法(MGGA)可以在较低的迭代次数下得到最优结果；对不同数量的任务和分组，多变异遗传算法(MGGA)具有很好的鲁棒性；在得到相同结果的条件下多变异遗传算法(MGGA)可减少50%以上的迭代次数和减少30%以上的运行时间。

为得到更为全面的仿真结果，选择12个任务和3台农机分别以不同的权重进行仿真试验，试验结果如表4所示。

表4 不同权重的仿真结果

由表4可知，代价的权重越大任务分配后该代价越小，在不同权重条件下，总油耗代价变化较小，总路程代价和最长作业时间代价变化较大。当γ取值较大、α和β取值较小时可以得到各个代价较均衡的任务分配效果，此时的任务分配结果更加符合实际农机作业情况。

5 实际深松作业验证试验

为验证本文提出的任务分配方法在实际作业中的效果，对实际作业情况进行任务分配试验。图12为吉林省公主岭市一合作社某日深松作业情况，该合作社共3台深松设备，该日共完成23个任务。设备性能参数和任务参数如表5、6所示，数据来源于“农业机械化精准作业平台”的实际作业数据。

表5 农机性能参数

3台深松设备实际作业情况如图13所示，第1台深松设备的作业顺序14→15→22→20→18→6→8，第2台深松设备的作业顺序10→11→17→12→13→4→3→2→1，第3台深松设备的作业顺序16→23→21→19→5→7→9。机群的理论多机协同作业时间为12.57 h，理论总路程为7.0 km。

表6 任务参数

分别以不同的权重进行静态任务分配，任务分配结果如表7所示。

表7 不同权重下试验结果

由试验结果可知，在不同的权重条件下多机协同代价均有明显下降，代价的权重越大，任务分配后该代价越小。当总路程代价权重较小、时间代价权重较大时，多机协同任务分配后路程代价和时间代价均有明显下降，且路程和时间代价较为均衡，各农机分配到的任务较为平均，该种情况符合农业生产实际作业需求；当总路程代价权重较大、时间代价权重较小时，多机协同任务分配后路程代价明显降低，时间代价降低不明显甚至增加，此时会出现一些农机执行大量任务其他农机执行极少量任务的情况，该种情况不符合农业生产实际作业需求。由于时间代价包含了一个农机的总路程和总任务面积等信息，因此，时间代价权重取值较大时会得到时间和总路程较均衡的任务分配结果，该结果较符合实际农业生产需求。试验结果表明，基于多变异分组遗传算法的多机协同静态任务分配方法可有效解决多机协同静态任务分配问题。

6 结论

(1)对同种作业农机多机协同静态任务分配问题进行了研究，构建了多机协同作业代价函数模型。

(2)设计了分组交叉算子和3种变异算子对遗传算法进行改进，提出了基于多变异分组遗传算法的多机协同静态任务分配方法。

(3)对基于多变异分组遗传算法的多机协同静态任务分配方法和参考算法进行对比，结果表明，多变异分组遗传算法对于不同数量的任务和分组都具有很好的任务分配效果，当迭代次数相同时，可降低1%～5%的代价，计算出相同代价可降低50%以上的迭代次数和30%以上的运行时间。

(4)选取不同的权重分别进行仿真分析和实际作业场景试验分析，得到不同权重系数下的任务分配结果，实际作业场景试验任务分配后，多机协同代价比实际作业代价降低了29.48%～55.00%，表明基于多变异分组遗传算法的多机协同静态任务分配方法可较好地解决多机协同静态任务分配问题。