基于遗传算法的小麦收割机路径智能优化控制研究

梁 肖，周湘贞

(1.河北政法职业学院 计算机系，石家庄 050000；2.郑州升达经贸管理学院 信息工程系，郑州 451191)

基于遗传算法的小麦收割机路径智能优化控制研究

梁 肖1，周湘贞2

(1.河北政法职业学院 计算机系，石家庄 050000；2.郑州升达经贸管理学院 信息工程系，郑州 451191)

基于遗传算法，以小麦收割机全局路径优化为研究目标，对小麦收割机从起始点到终点的收割作业问题进行了数学建模，并利用MatLab软件进行了仿真计算。结果表明：采用遗传算法得到的优化路径比驾驶员主观的随机路径缩短路线19km，节省费用和时间各为10.8%和7.8%。这说明，该算法可以对小麦收割机全局路径进行有效优化，能够大大提高小麦收割机的工作效率，实际应用前景广阔。

小麦收割机；路径优化；遗传算法；MatLab

0 引言

人工智能技术和互联网技术的发展和应用，加快了我国从传统农业向现代农业转型的步伐，提高了农业生产的自动化水平和作业效率。在联合收割机作业效率的研究中，全局路径优化是研究的重点问题。目前，往往采用蚁群、遗传、免疫、聚类分割、BP网络神经及多目标粒子群等人工智能算法进行路径的优化。本文引入遗传算法，对小麦收割机作业过程进行全局路径优化，可以大大节省作业时间和成本，提高小麦收割机的工作效率。

1 遗传算法概述

遗传算法是以达尔文进化论为基础提出的一种优胜劣汰算法，其模拟自然选择和遗传生物进化过程中的计算模型，可以进行全局区域搜索最优解。遗传算法采用一串编码组合，将需要解决问题的假设解集看作单个个体，然后将待解决问题看成是一个大环境，每个个体在这个大环境中的适应能力称为适配度，适配度越高存活率越高。因此，将生物进化中的繁殖、杂交、变异、竞争和选择引入算法中，将适配度表达式与优化问题相结合，建立目标函数对应关系。

传统优化算法往往以梯度信息寻找最优点，其缺点是可能因陷入局部最优而无法得到最优解。遗传算法则是一种全局寻优方法，更易找到全局最优解。遗传算法其实是一种计算机模拟方法，具有适用面广、多点搜索、鲁棒性好、自适应强、并行性高的特点，本质来讲是一种有着自适应能力的搜索优化方法。

对于使用遗传算法解决小麦收割机路径智能优化控制问题，首先需要构建待解决问题的假设解集的编码形式，然后通过选择、交叉、变异操作来寻找最优解。遗传算法解决路径智能优化控制问题的流程如图1所示。

图1 遗传算法流程Fig.1 The genetic algorithm flow

遗传算法流程主要包括以下几个步骤：

1)准备。

2)初始化，设定变量和可行解等参数值。

3)产生一个个体数为100的初始种群。

4)输入第一个样本值P1。

5)进行遗传操作。

6)若P≥300，则不满足要求，退出遗传算法；若P<300，则继续执行下一步。

7)将P进行加1操作，并指向下一个样本，且q值也加1。

8)转入步骤5)。

2 建立小麦收割机路径智能优化问题模型

小麦收割机路径优化问题是跨区收割最为重要的问题，紧密联系生产效率。如果不将收割路线进行系统规划，容易造成盲目跨区作业及收割机行走路径过长，增加作业成本。在寻求小麦收割机路径最优化中过程，合理进行数学建模是进行路径优化算法的重要途径。

2.1 车辆路径优化问题的一般描述

本文研究的小麦收割机路径优化是以有限个具体的作业点为服务对象的路径优化VRP问题。对于具体问题，VRP路径优化的数学描述形式较多，但一般可以将此类问题描述为：用作业起点向多个作业区域依次收割，在跨区域作业过程中计算或者规划出一条最优路径的作业路线，使得收割机在整个作业过程中找出一种或者多种优化目标，从而使总的路线长度最短。

VRP路径优化问题中一般需要事先知道收割机起始和各个作业区域的地理位置，实现优化目标需要了解如下3点：

1)使小麦收割机在作业过程中行走路径最短；

2)使作业过程的总成本最小，包括燃油费、人工费和其它费用；

3)使整个作业过程时间最少。

一般在小麦收割机路径优化中，起始点A0与各个作业区域点A1到An的位置均已知，各点之间的距离也已经知道，小麦收割机从A0至A1、An开始收割作业。该路径优化问题是指小麦收割机在行驶路径最短的情况下到达每个作业区域进行作业，其路径优化模型如图2所示。

2.2 建立数学建模

针对小麦收割机从A0至A1—An收割作业问题，建立数学模型，如图3所示。

图2 小麦收割机路径VRP模型Fig.2 The VRP model of wheat harvester path

图3 小麦收割机路径优化数学模型Fig.3 The mathematical model of path optimization of wheat harvester

图3中，A0到Ai的运动路径全部给出，只需确定一条最优路径，使得所有区域小麦收割完毕即可。因此，该问题优化目标是成本最低、所需时间最少或行驶路线最短。本文将行驶路线最短作为优化目标，对小麦收割机作业路径进行优化。首先假设：

1)假设小麦收割机在换区作业中的行走速度为定值；

2)假设小麦收割机在各路线通行状态一致；

3)假设行驶费用、所需时间与路程成正比；

4)假设小麦收割机全程无故障，所有费用均来自行驶费用。

小麦收割机路径优化问题的目标是在满足以下约束条件下，使收割机总行驶成本最小，具体如下：

1)路径的起点和终点都是作业区域点；

2)每个作业区域点收割任务一次完成，不能重复路过两次；

3)所有作业区域点收割任务不能超过收割机预算时间。

小麦收割机路径优化模型可以描述为

(1)

其中，i=0,1,2,…,n；k=0,1,2,…,n。

(2)

根据收割机总行驶成本最小为目标，建立小麦收割机路径优化模型，即

(3)

(4)

(5)

(6)

(7)

(8)

xij∈{0,1} (i,j=0,1,,…,n;k=1,2,…,K)

(9)

yki∈{0,1} (i=0,1,,…,n;k=1,2,…,K)

(10)

其中，作业区域点编号为0,1,2,…，n。式(3)是小麦收割机行驶成本最低的目标函数；式(4)是每个作业区域工作时间的约束条件；式(5)是保证每个作业区域都会到达的约束条件；式(6)是保证收割机从出发点出发最后返回到出发点的约束条件；式(7)～式(10)是收割机行走路径最短的约束条件。

3 小麦收割机路径智能优化问题求解

3.1 遗传算法路径优化基本参数

在采用遗传算法进行路径优化前，首先需要清楚群体规模、编码长度、交叉概率、变异概率、迭代步长和终止条件。具体如下：

1)群体规模。群体规模较小可以提高运算速度，但会降低种群多样性，进而破坏全局最优化；而规模过大亦会降低运算速度，在求优过程中很难收敛。

2)编码长度。编码长度若采用2进制编码，选取时需要考虑求解问题精度；若采用浮点数编码，则编码长度由实际问题决定，与精度没有太大关系。

3)交叉概率Pc。交叉概率与父代间发生交叉概率有关，常常取0.5上下。交叉概率大不利于全局路径的优化，而交叉概率小则会增加计算时间、降低算法效率。

4)变异概率Pm。变异算子是在全局求优的过程中跳出局部求优的一种办法，取值不能太大，一般取0.1～0.3。

5)迭代步长。迭代步长是指多长时间迭代1次，该值过大会降低优化效率，过小会加大计算时间。

6)终止条件。在初始阶段设置一终止条件，使算法在达到要求后结束该操作，并得到全局最优解。

3.2 小麦收割机路径优化遗传算法的设计

针对本文提出的从起始点到8个区域依次作业小麦收割机路径优化问题，遗传算法结合选择、交叉和变异3种算子的优化设计。对于遗传算法而言，交叉概率越大表示种群进化程度越高，而变异可能性较小。小麦收割机路径优化问题中，遗传算法各参数设定如下：种群大小M为30；最大迭代次数G为300；交叉概率Pc为0.7；变异概率Pm为0.2。

参数设定完成后，可以对可行解集进行编码，得到初始种群，设定好配度函数与终止条件；根据数学模型的输入条件，结合适配度计算结果进行种群选择操作。小麦收割机路径优化遗传算法的步骤如图4所示。

图4 小麦收割机路径优化遗传算法的步骤Fig.4 The steps of optimization genetic algorithm for wheat harvester

4 实验与结果分析

根据上述从起始点到8个区域依次作业的小麦收割机路径优化遗传算法设计方案，由美国MathWorks公司的MatLab软件进行计算，经过87次迭代后收敛。优化结果如下：

vx_opt0= [0.14 0.27 0.19 0.43 0.68 0.44 0.63 0.91]

vx_opt1= [0.23 0.56 0.45 0.79]

vx_opt2= [0.55 0.21 0.26 0.68]

结合适配度计算结果进行种群选择操作，将编码解码后得到最优的路径方案为A0→A1→A2→A3→A4→A5→A6→A7→A8→A0。

最优路径方案的有向图如图5所示。

图5 最优路径方案的有向图Fig.5 The directed graph of the optimal path plan

为了分析优化结果和可信度，本文将遗传算法得到的最优路径与驾驶员主观进行的随机路径进行对比分析，如表1所示。

表1 优化路径与随机路径对比分析

从图5和表1可以看出：遗传算法得到的优化路径长度为66km，驾驶员主观的随机路径为85 km，优化路径缩短路线19km，节省费用和时间各为10.8%和7.8%。从路径长度和耗费时间而言，遗传算法路径较短并且大大节省了时间和成本，具有良好的优化效果，其优势较为明显。

5 结论

1)为了实现小麦收割机全局路径规划功能，利用遗传算法对路径规划进行有效优化。对小麦收割机从A0至A1—An收割作业问题，进行数学建模，并设定好配度函数与终止条件进行种群选择操作，简化了计算的复杂性，大大提高了全局优化效率。

2)利用MatLab软件对小麦收割机全局路径规划进行了仿真计算，结果表明：采用遗传算法得到的优化路径长度为66km，驾驶员主观的随机路径为85 km，遗传算法得到优化路径缩短路线19km，节省费用和时间各为10.8%和7.8%。因此，遗传算法路径较短并且大大节省了时间和成本，具有良好的优化效果，大大提高了小麦收割机的工作效率，实际应用前景广阔。

[1] 赵辰.基于遗传算法的车辆路径优化问题研究[D].天津：天津大学,2012.

[2] 晏刚,王力,周俊,等.基于改进型遗传算法的AUV路径规划[J].重庆理工大学学报：自然科学版,2010(5):81-85.

[3] 朱大奇,颜明重.移动机器人路径规划技术综述[J]. 控制与决策,2010(7):961-967.

[4] 朱霞,陈仁文,徐栋霞,等.基于改进粒子群的焊点检测路径规划方法[J].仪器仪表学报,2014(11):2484-2493.

[5] 张培彦,李丹丹.物联网技术在联合收割机跨区作业中的应用研究[J].南方农机,2015(3):58-59,62.

[6] 饶喆,唐双喜,刘国平.基于蚁群粒子群混合算法的K均值聚类优化算法研究[J].数字技术与应用,2015(4):122-123.

[7] 李天旭,陈广大.基于改进遗传算法的室内移动机器人路径规划[J].制造业自动化,2015(20):31-35.

[8] 王银年.遗传算法的研究与应用[D].无锡：江南大学,2009.

[9] 王丽.移动机器人路径规划方法研究[D].西安：西北工业大学,2007.

[10] 蒋卓强.基于遗传模拟退火算法的静态路径规划研究[D].重庆：重庆大学,2007.

[11] 张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉：武汉理工大学,2005.

[12] 李丽.基于遗传算法的舰船航行路径规划技术研究[D].哈尔滨：哈尔滨工程大学,2006.

[13] 张敏辉,赖麟,孙连海.基于遗传算法的研究与Matlab代码的实现[J].四川教育学院学报,2012(1):115- 117.

[14] 徐晓晴,朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报,2012(8):1694-1700.

[15] 林爱兰.浅谈如何提高联合收割机的作业效率[J]. 机电技术,2005(1):21-22,28.

[16] 陈华华,杜歆,顾伟康. 基于遗传算法的静态环境全局路径规划[J].浙江大学学报:理学版,2005(1): 49-53,61.

[17] 赵金辉,硕良勋,曲文斌. 基于遗传L-system植物繁殖与模拟的研究[J].邢台职业技术学院学报,2006(3):30-32.

[18] 崔建军.基于遗传算法的移动机器人路径规划研究[D].西安：西安科技大学,2010.

[19] 陈卫东,朱奇光.基于模糊算法的移动机器人路径规划[J].电子学报,2011(4):971-974,980.

[20] 张银玲,牛小梅.蚁群算法在移动机器人路径规划中的仿真研究[J].计算机仿真,2011(6):231-234.

[21] 朱磊,樊继壮,赵杰,等.基于栅格法的矿难搜索机器人全局路径规划与局部避障[J].中南大学学报：自然科学版,2011(11):3421-3428.

[22] 赵荣齐.基于人工势场法的机器人路径规划研究[D].济南：山东大学,2008.

[23] 于海璁,陆锋.一种基于遗传算法的多模式多标准路径规划方法[J].测绘学报,2014(1):89-96.

[24] 史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报,2014(6):53-57.

[25] 刘传领.基于势场法和遗传算法的机器人路径规划技术研究[D].南京：南京理工大学,2012.

[26] 张宏烈.移动机器人全局路径规划的研究[D].哈尔滨：哈尔滨工程大学,2002.

[27] 黄铝文.苹果采摘机器人视觉识别与路径规划方法研究[D].杨凌：西北农林科技大学,2013.

[28] 赵庆波.果树采摘机器人控制与避障技术研究[D].镇江：江苏大学,2008.

Research on Intelligent Optimization Control of Wheat Harvester Path Based on Genetic Algorithm

Liang Xiao1, Zhou Xiangzhen2

(1.Department of Computer Science，Hebei Professional College of Political Science and Low,Shijiazhuang 050000, China; 2.Department of Information Engineering, Shengda Economics Trade & Management College of Zhengzhou, Zhengzhou 451191, China)

Based on genetic algorithm, it studied the path optimization of wheat harvester global through harvesting wheat harvester from the starting point to the end, the mathematical modeling and simulation by using MATLAB software. The simulation results showed that the random path optimization path obtained by genetic algorithm than the subjective saving route 19km, save cost and time is 10.8% and 7.8%, indicating that the algorithm can effectively optimize the wheat harvester global path, which can greatly improve the wheat harvesting efficiency, application prospect.

wheat harvester; path optimization; genetic algorithm; MatLab

2016-12-11

河南省科技攻关计划项目(142102310362)

梁 肖(1984-),女，河北保定人，讲师，硕士，(E-mail)liangxiaolx123@sina.com。

S225.3

A

1003-188X(2018)02-0056-05