精准农业土壤测量中TSP问题求解

　　摘要:针对精准农业土壤测量中，田地因土壤时空变异性，会出现与附近土壤差异较大的“斑块”，将田地中“斑块”位置信息进行整合并转化为TSP问题(旅行商问题)的变体。使用改进型蚁群算法对该TSP问题进行求解，并通过MATLAB软件对算法进行验证，使机器在田地行驶路径为最优路径，节约了机器燃料和运行时间。

　　关键词:精准农业;TSP;蚁群算法

　　引言

　　精准农业是以信息技术为支撑，根据空间变异，定位、定时、定量地实施一整套现代化农事操作与管理的系统［1］，被认为是农业生产和环境友好实践的贡献者。也就是说，在适当的时间、地点应用现代机器，以提高经济效益，并减少农药和化肥的投放，降低对环境的影响。但是要实现精准控制，就必须知道每个位置的具体情况，才能因地制宜。实际上，由于土壤的时空变异性，比如:土壤类型、养分可利用性和作物害虫等因素，会出现多个斑块(与相邻土壤性质不同)。因此需要对整块土地进行测量，但是除去这些“斑块”位置，其他位置的情况均能根据附近的点测算出来，那么只需测量这些“斑块”即可。现有的农业土壤测量方法大多将便携式土壤测量仪安装在农业器具上，每隔一段距离对附近的土壤采用梭行法(即农机逐行逐列行进)进行测量，大大地增加的燃料的损耗，并且比较耗时。如果有一些先验信息可用(提前知道这些斑块位置)，那么机器可以选择关键的信息位置来获取测量结果。如果附近的土壤具有相关性，则机器不需要精确地访问每个位置，而是访问其领域中的某个点，这样就可以将精准农业中测量土壤情况并进行正确选择的问题表述为经典欧几里得的旅行售货员问题TSP的变体。TSP问题作为数学领域中著名问题之一，有许多国内外学者从不同角度采用不同方法对TSP问题进行求解［2－10］。对于精准农业中的TSP问题:JAWAID和SMITH［11］学者，采用贪婪算法拓展了经典最大权重的哈密顿循环，以解决该问题;PHAM［12］等将遗传算法应用在具有凹陷障碍的农业环境中，获得最短路径，并在Matlab中验证其方法有效性;ZHOU［13］等学者开发了一种田间规划方法，将田地中多个障碍区域的优化问题，转化为TSP问题，并通过实际试验，验证其方法的有效性;HAYEＲ［14］等学者提出机器在进行精准灌溉时如何在有限的电池电量和给定时间内进行有效调整，并对两种贪婪启发式方法在此问题中的应用进行可行性分析。然而，上述文献中都没有考虑垄作农田的最短路径问题。基于此，这篇文章的目的是，在考虑燃料和负载的情况下，如何减少机器在田间行驶距离。这篇文章拟采用蚁群算法应用在精准农业中TSP问题中，实现机器最优路径规划。该方法首先根据不同的土壤结构以及土壤时空变异性，得到斑块的位置，根据这些斑块位置，以及斑块的差异性进行数学建模，将该问题转化为新型TSP问题。之后，采用蚁群算法对该TSP问题进行求解，得出最优解。

　　1精准农业中TSP问题及模型介绍

　　TSP问题其一般描述为:有一旅行商要访问n个城市，每个城市必须访问且只能访问一次，需要寻求到一条包含所有n个城市的最短访问路线。其数学模型如下［15］:对于城市V={v1，v2，…，vn}的一个访问顺序为T=(t1，t2，…，tn)，其中ti=V(i=1，2，…，n)，而且tn+1=t1，则问题为求min∑nT∈Ωi=1dtiti+1，其中Ω为这n个城市不重复排列的所有可能的回路。

　　2求解精准农业TSP问题的蚁群算法

　　设有m只蚂蚁，每只蚂蚁根据以“斑块”距离和链接边上信息素的数量为变量的概率函数选择下一个“斑块”［设τij(t)为t时刻e(i，j)上信息素的强度］。“斑块”距离是根据田地实际情况如图3(白色空白区域为田埂区域允许机器通过，绿色区域为作物区域不允许机器通过)可分为三类。

　　3实验及结果分析

　　基于上述算法，使用软件MATLAB对求解精准农业TSP问题的改进型蚁群算法进行仿真验证，以单行种植茄子田地即株距为40cm，行距为60cm为参考，并对其进行坐标标准化处理，得到图5所示田地模型。仿真算例中的“斑块”坐标由系统随机生成，共计22个，对于一些出现在作物区域的点，进行坐标微调，将这些点从作物区域移出。使用MATLAB2017a编制程序，在i5－44603．2GHZ、10GB内存的计算机运行。

　　3．1参数选择

　　蚁群算法中，蚂蚁数目越多，越能提高蚁群算法的全局搜索能力以及算法的稳定性。但蚂蚁数目增加到一定程度以后，会降低算法的收敛速度。同样的，信息素启发因子α大小反映了在蚁群路径搜索中的随机性因素作用的强度，其值越大，搜索的随机性随之减弱;期望值启发因子β的大小反映了在蚁群路径搜索中的确定性因素作用的强度，其值越大，搜索的收敛速度随之加快，但蚁群在最优路径的搜索随机性减弱;信息素挥发度1－ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。当1－ρ过大时会影响到算法的随机性和全局搜索能力。反之，通过减小信息挥发度1－ρ虽然可以提高算法的随机性能和全局搜索能力，但是会使算法的收敛速度降低;信息素释放总量Q为蚂蚁循环一周在经过路径上所释放的信息素总量，在蚁群算法中为一常量。一般认为:信息素释放总量Q越大，其蚂蚁走过路径上的信息素的累积加快，有助于算法的快速收敛。这些参数均需要选择一个恰当的数值，才能提高算法的稳定性以及全局搜索能力。但是，由于理论不够成熟没有确切的公式计算出各参数值，只能通过实验验证的方法，确定参数的取值。

　　选取上述问题作为例子，仿真实验中的有关参数选取为:NCmax=100，α=1．5，β=5，ρ=0．1，Q=100，分别取m∈{15，20，25，30，35，40}，其中m为蚂蚁个数，NCmax代表最大迭代次数，α代表信息素启发因子，β代表期望值启发因子，ρ代表信息素挥发因子，Q代表信息素释放总量。每组数据取实验10次的平均值，所得的实验结果见表1。

　　根据该问题的需要，首先考虑算法的稳定性和所求得最优解的全局性，其次才是收敛速度。因此，在该问题下，蚂蚁数m选取35为宜。

　　仿真实验中的有关参数选取为:m=35，NCmax=100，ρ=0．1，Q=100，分别取不同启发式因子α和β的组合进行比较，每组数据取实验10次的平均值，结果见表2，3。

　　3．2仿真结果

　　与运行结果对应的路径如图4所示，从图4中可以清晰地看到，自一个“斑块”出发，每个“斑块”访问一次，遍历所有“斑块”后，返回起点，寻找到了最短路径。图中行间距和作物间距依据茄子实际种植的行间距和作物间距;灰色区域为作物区间(机器不可通过)，白色空白区域为田埂区域(机器可通过)。

　　4结论

　　这篇文章针对精准农业的土壤测量中因土壤时空变异性而导致“斑块”的情况，将其转化为TSP问题并进行优化，使用改进型蚁群算法进行求解，此蚁群算法对传统蚁群算法的信息素更新方式进行改进，采用信息素局部、全局更新的方式，提高搜索效率，避免陷入局部最优解，并通过MATLAB软件对算法进行仿真验证，实验结果表明该算法可以减少机器在田间的行驶距离，有效地节约燃料和时间。随着信息技术的发展，精准农业无疑是大势所趋，精准农业目前面临的最大问题无非是农田大规模测量问题以及精准作业问题例如农田精准施肥、精准灌溉等。本文研究内容是田垄农田的路径规划问题，本文研究成果可以应用在农田大规模测量以及精准作业方面上，为解决精准农业面临的问题提供一种解决方案。

　　参考文献:

　　［1］TOKEKAＲP，HOOKJV，MULLAD，etal．SensorplanningforasymbioticUAVandUGVsystemforprecisionagriculture［C］∥IntelligentＲobotsandSystems(IＲOS)，2013IEEE/ＲSJInternationalConferenceon．IEEE，2013．

　　［2］李成兵，郭瑞雪，李敏．改进蚁群算法在旅行商问题中的应用［J］．计算机应用，2014，34(增刊1):131－132，165．

　　［3］王沛栋，唐功友，杨熙鑫，等．一种求解旅行商问题的改进蚁群算法［J］．海洋大学学报(自然科学版)，2013，43(1):93－97．

　　［4］杨学峰．蚁群算法求解TSP问题的研究［D］．长春:吉林大学，2010．

　　［5］许凯波．蚁群算法的改进及其在若干优化问题中的应用［D］．江苏无锡:江南大学，2018

　　云泽晖，邵仕泉，买童宁