基于动态自确定并行模糊聚类鸡群优化算法的水稻机器人路径规划

余晓兰，万 云，朱景建，陈靖照

（1.重庆城市职业学院，重庆 永川 402160；2.浙江工业大学，浙江 杭州 310014；3.郑州大学，河南 郑州 450000）

1 引言

水稻机器人的使用为处理农业信息采集等问题提供了高效便利的解决途径，解决了大面积农田信息传输“摆渡”难题，然而如何有效规划水稻机器人的移动路径，已成为当前研究领域热点方向之一。鉴于对外部环境信息的熟知度，路径规划分为全局路径规划和局部路径规划两类[1]。常见的传统全局路径规划算法有栅格法、人工势场方法、随机扩展树法和自由空间法等[2-4]。近年来，随着群智能优化技术的不断发展，智能优化算法为路径规划问题提供了全新的研究视角[5]。

全局路径规划作为机器人路径规划研究基础，学者们开展了系列研究：文献[6]针对路径冗余点问题，提出了一种改进的A＊算法，得到了路径拐点处最小转弯角，但是，复杂环境下算法占用较多内存空间的问题仍没有得到很好解决；文献[2]通过引入目标偏差搜索策略和神经网络处理机制，克服了随机扩展树法实时性差、路径不平滑的缺陷。随着外部环境复杂性不断增加，传统全局路径规划方法面临内存占用加剧、时效性降低、所得路径非最优解等问题，为此，学者们将智能优化计算法应用于路径规划问题，并得到了大量研究成果。文献[3]在烟花算法中引入量子行为，提高了算法样本多样性和收敛速度，并应用于路径规划，仿真结果也证明了该方案的有效性。然而，智能优化算法求解复杂问题时收敛效率低、容易产生早熟等问题[7]，降低了路径规划的时效性和最优性。

鸡群优化（Chicken Swarm Optimization，CSO）算法[8]作为一种全新的群智能优化技术，已被应用于电力工程应用领域。针对CSO算法固有缺陷，设计动态自确定并行模糊聚类鸡群优化算法（DMCSO）：在MPI并行运行架构下，利用动态自确定分类个数的核FCM对鸡群种群进行聚类分析，建立鸡群跟随关系，并证DMCSO算法具有良好的种群多样性。对于水稻机器人全局路径规划问题，构建基于碰撞威胁度、路径长度和路径平滑度等评价指标的极坐标水稻机器人路径规划模型，最后，采用DMCSO算法对模型求解。

2 路径规划模型构建

2.1 路径规划评价指标

对于二维全局路径规划问题，其目的是在路径起点Xstar(xstar，ystar)和终点Xend(xend，yend)之间寻找一条最优或次优路径l(Xstar→Xend)，使得路径规划适应度函数F(l)最优。选取碰撞威胁度Lthr(l)、路径长度Lpɑ(l)和路径平滑度Lsm(l)构建路径规划适应度函数：

式中：ω1、ω2、ω3—权重系数。

碰撞威胁度 对于路径l(Xstar→Xend)，定义碰撞威胁度Lthr(l)为：

式中：ω—安全因子［9］；(x，y)—路径l上的点；(xk，yk)、R(k)—第k个（1≤k≤K）障碍物的坐标和最大几何半径。

路径长度 对于路径l(Xstar→Xend)，定义路径长度Lpɑ(l)为：

路径平滑度 对于路径l(Xstar→Xend)，定义路径平滑度Lsm(l)为：

式中：K(x，y)—路径l在(x，y)处的曲率。

从路径规划适应度函数定义可以看出，选取碰撞威胁度、路径长度和路径平滑度作为评价指标，使得F（l）取最小值时，所得机器人路径在有效避开障碍物的同时，路径长度更短且更加平滑。

2.2 路径空间描述

为降低路径规划复杂度，一般将路径规划问题转化为在Xstar(xstar，ystar)与Xend(xend，yend)之间寻找N-1节点，并按照顺序连接组成l(Xstar→Xend)=[Xstar，X1，…，XN-1，Xend为了进一步降低路径规划求解维度，对路径规划空间进行极坐标处理，如图1（a）所示。

图1 极坐标处理与种群多样性分析Fig.1 Polar Coordinate Processing and Population Diversity Analysis

式中：α—l(Xstar→Xend)与x的轴夹角。从式（7）可以看出，只需要得到θi信息就可以确定Xi坐标，因此，路径l(Xstar→Xend)可以用一个N-1维向量θ=[θ1，…，θN-1]进行描述，从而降低了求解维度。此时，路径规划适应度函数描述为：

3 DMCSO算法实现及在路径规划中的应用

群智能优化技术已被广泛应用于NP-Hard优化问题，并展现出了优秀的寻优能力。在鸡群优化（CSO）算法的基础上，设计动态自确定并行模糊聚类鸡群优化算法（DMCSO），重点分析导致算法收敛精度不高和容易产生早熟的原因，并提出改进策略（CSO算法基本原理见相关文献，不再赘述）。

3.1 动态自确定模糊聚类

FCM算法是目前应用最为广泛的模糊聚类算法之一［10］，但是存在分类数目事先确定、对初始聚类中心敏感等缺陷。为此提出动态自确定模糊聚类算法，并对鸡群种群进行聚类分析。

其中，定义Θ(s，v)=ΦT(s)Φ(v)为核函数内积，选取Θ(s，v)为：

将式（12）～式（13）代入式（11），分别对V、U求偏导：

对式（14）执行迭代操作，直至满足终止条件，从而实现数据聚类分析，使得同一类数据具有更多相似性，不同类数据具有更多差异性。

动态自确定聚类个数 为了克服核FCM实现确定聚类个数的缺陷，根据内核诱导距离，定义“自确定因子Δ(C)”：

式中：|C(i)|—第i个聚类中数据个数。

3.2 基于动态自确定模糊聚类的鸡群迭代更新

CSO算法模拟鸡群觅食行为，通过建立内部社会关系，赋予个体不同进化策略，进而得到全局最优解。随着CSO算法迭代次数不断增加，种群样本多样性逐渐降低，如果个体Pi（如图1（b）所示）选择与自身空间特性相近的个体Pj进行学习更新，则更新后的Pi，new空间位置变化不大；如果选择与自身空间特性相差较大的个体Pk进行学习更新，则更新后的增加了算法搜索空间。特别的，当Pj处于局部极值空间范围内时，很容易导致算法陷入局部最优，导致产生早熟现象。可见，合理科学选取个体学习进化对象，对保持种群样本多样性具有重要意义，为此选取动态自确定模糊聚类方法对种群进行聚类分析，并在此基础上建立鸡群跟随关系，执行迭代进化操作：

（1）聚类分析：对鸡群执行动态自确定模糊聚类操作，得到C个子种群。

（2）角色划定：设定每个子种群内适应度最优的个体为“公鸡”，适应度最差的χ个个体为“小鸡”，其余为“母鸡。

（3）建立跟随关系：在第i个子种群内，选择作为跟随对象，选择适应度最佳的跟随对象。

（4）进化更新：对于第i个子种群分别执行G轮CSO算法进化更新操作。

（5）终止判定：判定是否满足终止条件，若满足则终止算法，否则返回（1）。

结论1 基于动态自确定模糊聚类的CSO算法具有较高的种群多样性

证明：对于具有P个个体的鸡群，每个个体维度为N，即P(p1，…，pN)，t时刻，种群多样性为：

式（20）表明，(t)决定了鸡群的种群多样性，通过对鸡群种群样本多样性分析，基于动态自确定模糊聚类能够提高个体学习对象选取的合理性科学性，从而使得改进后的CSO算法具有更好的样本多样性。

基于动态自确定模糊聚类的CSO算法的计算复杂度 种群初始化复杂度为O(PN)，每次执行动态自确定模糊聚类操作复杂度为tmax(Cmax-1)O(P（)tmax为模糊聚类最大迭代次数），执行个体更新复杂度为G×O(PN)。算法总计算复杂度为（当N≪P）：

3.3 MPI并行运算架构

从式（21）可以看出，基于动态自确定模糊聚类的CSO算法虽然具有较高种群多样性，但是算法计算复杂度较高，主要原因是每次迭代需要执行Cmax次动态自确定模糊聚类操作，为此构建MPI［11］并行运算架构：搭建具有Cmax个节点的局域网，其中一个为中心节点，主要执行种群初始化、模糊聚类初始化、最佳聚类个数判定、鸡群跟随关系建立、算法终止条件判定等操作，其余节点为边缘节点，主要执行核FCM聚类操作、G轮鸡群个体更新等操作。

3.4 基于DMCSO算法的路径规划实现

个体编码 对于路径规划规划问题，DMCSO算法个体编码定义为P(θ1，…，θN-1)。

适应度函数 对于路径规划规划问题，定义DMCSO算法的适应度函数为：

基于DMCSO算法的路径规划实现流程图，如图2所示。

图2 基于DMCSO算法的路径规划实现流程Fig.2 Implementation Flow of Path Planning based on DMCSO Algorithm

4 实验仿真

4.1 DMCSO算法性能验证

为了验证DMCSO算法性能，采用4种经典测试函数f1：Sphere、f2：Ackley、f3：Griewank和f4：Rastrigrin进行测试，并选取基本CSO算法、量子粒子群优化算法（QPSO）和改进灰狼优化算法（IGWO）[7]进行对比试验。DMCSO算法参数设置如下：鸡群规模P=300、χ=20、G=10、算法最大迭代次数Tmax=500。每种算法独立运行50次，评价指标为求解成功率V、均值Av、标准差St和运算时间T。4种经典测试函数收敛曲线，如图3～图6所示。评价指标对比结果，如表1所示。

表1 评价指标对比结果Tab.1 Comparison Results of Evaluation Indexes

图3 f1函数收敛曲线Fig.3 f1 Convergence Curve

图4 f2函数收敛曲线Fig.4 f2 Convergence Curve

图5 f3函数收敛曲线Fig.5 f3 Convergence Curve

图6 f4函数收敛曲线Fig.6 f4 Convergence Curve

4.2 机器人路径规划实例仿真

采用DMCSO算法对水稻机器人路径规划问题进行研究，将农田抽象为二维平面内的方形区域，障碍物等效为圆柱体及长方体，并在MATLAB平台上对不同应用场景进行仿真。

情景1：设定Xstar(15，24)、Xend(46，54)，障碍物为圆柱体。

情景2：设定Xstar(10，35)、Xend(60，55)，障碍物为长方体。

分别采用文献[1]和文献[6]提出的路径规划方法进行对比试验，每种方法独立运行10次，取平均路径距离ˉL、平均规划时间ˉT进行对比分析，对比结果，如表2所示。不同规划方法得到的路径结果，如图7～图8所示。

表2 平均路径距离、平均规划时间对比Tab.2 Comparison of Average Path Distance and Average Planning Time

图7 情景1下仿真比较Fig.7 Simulation Comparison under Scenario 1

图8 情景2下仿真比较Fig.8 Simulation Comparison under Scenario 2

4.3 实例（结果）分析

（1）DMCSO具有较高的收敛精度。从图3～图6和表1可以看出，DMCSO算法无论是求解成功率、最优解平均值，还是标准差都要好于QPSO算法和IGWO算法，而CSO算法表现最差，特别的，对于函数f4，DMCSO算法求解成功率达到了100%，而其他三种算法最好的求解成功率才只有16%。

（2）DMCSO具有较快的运算速度。从图3～图6和表1可以看出，DMCSO算法同样要快于其它3种算法。特别的，对于高维复杂函数f4，相比于CSO、QPSO和IGWO，DMCSO运算速度分别提高了26.9%、13.1%和12.2%。

（3）基于DMCSO算法的路径规划具有更好地路径长度和运算时间。从表2及图3～图6可以看出，不同仿真情景下，得到的路径长度、运算时间要好于其他两种方法，其中路径长度降低了约（15.9～26.5）%，运算时间降低了约（20.3～44.3）%，而且，得到的路径具有更好地平滑度。

（4）之所以DMCSO算法具较好的优化性能，是因为动态自确定模糊聚类的引入，克服了模糊聚类算法不能自动确定聚类个数的缺陷，提高了个体学习对象选取的合理性科学性，进而提升了算法全局深度搜索能力，并且MPI并行架构的构建，将算法迭代过程分布在多个线程中，很大程度降低了算法运行时间。仿真结果有效验证了基于动态自确定并行模糊聚类鸡群优化算法的机器人路径规划的方法可行性。

5 结语

提出了一种基于动态自确定并行模糊聚类鸡群优化算法的水稻机器人路径规划方法。通过构建路径规划模型、设计动态自确定分类个数的核FCM和建立MPI并行架构，有效提高了CSO算法求解高维复杂问题的优化性能，为机器人路径规划问题提供了更有效的解决方法，仿真结果表明，所提路径规划方法更具可行性和合理性，路径长度降低了约（15.9～26.5）%，运算时间降低了约（20.3～44.3）%，具有一定的实际应用价值。