农业机器人协同作业算法研究

农业机器人协同作业算法研究

李作山，付江龙，王雨，嵇艳东，张普印

（绥化学院，黑龙江 绥化 152000）

摘要：为了解决农业机器人协同作业问题，分析了在寻找多目标优化问题Pareto最优解的遗传算法时，保存Pareto最优解的意义和必要性。提出了一种基于Pareto最优解数据库的多目标优化遗传算法。新算法在很大程度上提高了算法的性能，提高了算法的质量。新算法不仅能得到分布均匀的Pareto最优解，而且算法稳定，不受自身随机性的影响。

关键词：农业机器人；协同作业；遗传算法；多目标优化；帕累托最优

课题项目：黑龙江省大学生创新创业训练计划项目（编号：202110236029）

1 引言

本文致力于研究一种复杂环境下异质农业机器人群的任务分配及全区域覆盖策略。农业机器人的协同作业可以认为是一种多目标优化问题。农业机器人在协同作业的时候，各个作业目标很大程度上存在彼此矛盾的情况，没有一个最优解能够同时满足优化多个互相矛盾的作业目标。处理多目标优化的目的是找到能够近似同时优化几个目标的折衷解，即Pareto最优解集^[1]。同时，进化算法因一次运行可得到多个解，且能逼近非凸或不连续的Pareto最优前端，从而被认为是更适合求解多目标优化问题的智能方法^[2]。

本文在总结前人研究成果的基础上，针对遗传算法在进化过程中，选择算子、交叉算子和变异算子对选择Pareto最优解的干扰情况，重点研究了农业机器人协同作业最优解保留策略和种群多样性策略，提出了基于Pareto最优解数据库的农业机器人协同作业多目标优化遗传算法。其基本思想是在算法执行过程中建立一个数据库，然后将进化过程中的每一代Pareto最优解都放入数据库中。每一代的所有个体均采用Pareto最优解算法进行运算，剔除掉劣解。然后进行个体间的欧氏距离运算，其中小于指定值的解作为次优解。

2 算法分析

2.1 多目标优化问题的数学模型

在实际应用中，人们经常遇到多准则、多目标的设计与决策问题。为了解决多目标优化问题，需要建立一个通用的数学模型。

首先，定义问题涉及的决策变量。一般来说，决策变量可以看作是n维欧氏空间Eⁿ中的一个点；其次，定义目标函数。一般来说，目标函数是一组与决策变量x相关的函数，由实际问题需要优化的目标来决定；最后，设定约束条件。从实际应用角度来看，多目标优化问题的决策变量取值会受到一些具体条件的约束，从数学的角度来说，这些约束都可以定义为不等式或等式，既m不等式约束和k等式约束。如果所有目标函数都寻求最小值，则多目标优化问题可描述为以下数学模型：

(1)

s.t.： (2)

(3)

(4)

(5)

2.2 遗传算法

遗传算法是一种通过模拟自然选择和生物进化的遗传机制，来解决复杂问题的随机搜索算法。为了使用遗传算法解决多目标优化问题，首先需要对问题涉及的决策变量进行编码，生成遗传算法中的染色体β_i（个体）。遗传算法中有多种染色体编码方式，为了更便于寻找Pareto最优解，不失一般性，可采用染色体二进制编码，既通过编码转换函数f，建立二元字符串βi ={0，1}*和决策变量 之间的映射关系：

(6)

这里，二元字符串β_i ={0，1}^*将分成n个长度为m的子串，总长度为l。每个子串对应 中的一个决策分量。

遗传算法是以群体中所有个体为对象的群体操作。如果第i代的种群为β_i ={0，1}^*，通过遗传操作“^{0,1}_i→{0,1}_i+1”，可以从第i代得到i+1种群，这样经过若干代的遗传，通过进行高适应度个体的搜索，完成优化问题的求解。基本遗传操作“^”有以下三个步骤：

（1）选择算子：从群体中选出优秀个体并剔除劣等个体的操作称为选择算子。个体的适应度计算公式为 (δ为适应度变换函数，g为目标函数，f为染色体编码转换函数)。这里可以根据概率 选择个体并复制给下一代。个体的适应度越大，被选择的可能性就越大。

（2）交叉算子：随机选择两个已经被选择的个体作为交叉基体，然后选择两个交叉位置，两个个体的部分结构将被替换和重组，从而形成两个新的个体。染色体的交叉操作取决于交叉概率P_c。

（3）变异算子：根据较小的概率变异概率P_m，随机改变单个串的每一位。

2.3 基于Pareto最优解数据库的多目标优化遗传算法

本文采用数据库来处理这个问题。通过数据库和及其操作，可以避免遗传过程中的交叉和变异对帕累托最优个体的破坏。具体过程如下。

（1）为了求解帕累托最优解，建立了数据库，并与算法并行存在。

（2）初始种群中的每个个体都设置一个标记flag，flag=0表示此个体是次解，flag=1表示帕累托最优解。初始化为flag=1。

（3）将进化过程产生的每一代帕累托最优解存入数据库。同时，每一代都在数据库中单独执行Pareto最优解算法，即对个体进行欧几里德距离算法，将小于指定数值的个体作为flag=0的次解。

（4）清除数据库中标志为0的个体。

设计方案是：根据Pareto最优个体的概念，将每一代的群体划分为非劣解集和劣解集。在选择操作中，非劣解个体的选择概率远远大于劣解个体。然而，个体是在非劣解集和劣解集中按概率比例选择的。如果群的大小为PopSize，k为非劣解个体的个数， 和 为随机比例， ，则非劣解集A个体的选择概率为： ，非劣解集A的个体选择概率为：

3 分析与讨论

该算法对选择算子进行了改进，采用了数据库保存机制，克服了传统的问题。其基本思想是：为了寻找Pareto最优解的多目标优化遗传算法，建立数据库。将进化过程中每一代的Pareto最优解放入数据库中，每一代首先对数据库中的所有个体进行Pareto最优解计算，剔除劣解。然后在个体之间进行欧氏距离运算，其中一个小于某个值的个体作为次解。该数据库和上述操作可以有效地避免交叉和变异操作对Pareto最优个体的破坏。而本算法最大的优点是能避开人为因素对算法的影响，使算法具有很高的自适应能力。

参考文献：

1[] Pelosi Giuseppe, Selleri Stefano. To Coligny, in the Footprints of Vilfredo Pareto's "Optimum"[J]. IEEE Antennas and Propagation Magazine, 2014, 56(3):249-254.

2[] 胡旺，Gary G. YEN，张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报，2014，25(05)：1025-1050.

作者简介：李作山（1977.08），男，汉，黑龙江绥化人，硕士，讲师，主要研究方向为算法设计、听障生教育。