精準農業土壤測量中TSP問題求解

云澤暉，邵仕泉，買童寧

(西南民族大學電子信息工程國家民委重點實驗室，成都 610041)

0 引 言

精準農業是以信息技術為支撐，根據空間變異，定位、定時、定量地實施一整套現代化農事操作與管理的系統[1]，被認為是農業生產和環境友好實踐的貢獻者。也就是說，在適當的時間、地點應用現代機器，以提高經濟效益，并減少農藥和化肥的投放，降低對環境的影響。但是要實現精準控制，就必須知道每個位置的具體情況，才能因地制宜。實際上，由于土壤的時空變異性，比如：土壤類型、養分可利用性和作物害蟲等因素，會出現多個斑塊(與相鄰土壤性質不同)。因此需要對整塊土地進行測量，但是除去這些“斑塊”位置，其他位置的情況均能根據附近的點測算出來，那么只需測量這些“斑塊”即可?，F有的農業土壤測量方法大多將便攜式土壤測量儀安裝在農業器具上，每隔一段距離對附近的土壤采用梭行法(即農機逐行逐列行進)進行測量，大大地增加的燃料的損耗，并且比較耗時。如果有一些先驗信息可用(提前知道這些斑塊位置)，那么機器可以選擇關鍵的信息位置來獲取測量結果。如果附近的土壤具有相關性，則機器不需要精確地訪問每個位置，而是訪問其領域中的某個點，這樣就可以將精準農業中測量土壤情況并進行正確選擇的問題表述為經典歐幾里得的旅行售貨員問題TSP的變體。TSP問題作為數學領域中著名問題之一，有許多國內外學者從不同角度采用不同方法對TSP問題進行求解[2-10]。對于精準農業中的TSP問題：JAWAID和SMITH[11]學者，采用貪婪算法拓展了經典最大權重的哈密頓循環，以解決該問題；PHAM[12]等將遺傳算法應用在具有凹陷障礙的農業環境中，獲得最短路徑，并在Matlab中驗證其方法有效性；ZHOU[13]等學者開發了一種田間規劃方法，將田地中多個障礙區域的優化問題，轉化為TSP問題，并通過實際試驗，驗證其方法的有效性；HAYER[14]等學者提出機器在進行精準灌溉時如何在有限的電池電量和給定時間內進行有效調整，并對兩種貪婪啟發式方法在此問題中的應用進行可行性分析。然而，上述文獻中都沒有考慮壟作農田的最短路徑問題?；诖?，這篇文章的目的是，在考慮燃料和負載的情況下，如何減少機器在田間行駛距離。這篇文章擬采用蟻群算法應用在精準農業中TSP問題中，實現機器最優路徑規劃。該方法首先根據不同的土壤結構以及土壤時空變異性，得到斑塊的位置，根據這些斑塊位置，以及斑塊的差異性進行數學建模，將該問題轉化為新型TSP問題。之后，采用蟻群算法對該TSP問題進行求解，得出最優解。

1 精準農業中TSP問題及模型介紹

TSP問題其一般描述為：有一旅行商要訪問n個城市，每個城市必須訪問且只能訪問一次，需要尋求到一條包含所有n個城市的最短訪問路線。其數學模型如下[15]：

圖1 土壤濕度地圖

首先，將田地進行枚舉式測量，并繪制土壤濕度地圖(如圖1)。圖1中x,y代表田地的長和寬坐標，h是土壤濕度坐標，根據峰值高低，區分土壤中濕度情況。

將其簡化后得到二維圖，如圖2所示。圖2中黑色塊狀圖形代表斑塊，黑線代表作物區域。農田多為“豐”字形或是“井”字形，而作物區域一般機器不能通行，這樣就形成了精準農業的TSP問題。

圖2 “豐”字形農田

2 求解精準農業TSP問題的蟻群算法

設有m只螞蟻，每只螞蟻根據以“斑塊”距離和鏈接邊上信息素的數量為變量的概率函數選擇下一個“斑塊”[設τij(t)為t時刻e(i，j)上信息素的強度]。“斑塊”距離是根據田地實際情況如圖3(白色空白區域為田埂區域允許機器通過，綠色區域為作物區域不允許機器通過)可分為三類。

第一類，兩個“斑塊”位置處于同一塊區域，如圖3中1、2“斑塊”位置，則兩點最短距離公式為：

(1)

第二類，兩個“斑塊”位置同屬于第一行或者是第二行的區域，如圖4中1、4和2、3“斑塊”位置, 在求解這種情況下的最短距離時，需要比較走最上邊田埂和中間田埂的最短距離，選擇最短距離的走法，則兩點最短距離公式為：

(2)

式中：h1為最上邊田埂的坐標值；h2中間田埂的縱坐標值。

第三類，兩個“斑塊”位置分屬于第一行和第二行且不屬于同一塊的區域，如圖4中3、5“斑塊”位置，因為其屬于“一上一下”兩行的情況，走中間田埂距離最短，則兩點最短距離公式為：

(3)

式中：hz為中間田埂的縱坐標值。

初始時刻，各條路徑的信息素相等，設τij(t)=C(C為常數)。在運動過程中，根據各條路徑上的信息量決定轉移方向，第k只螞蟻由“斑塊”i選擇到下一個“斑塊”j的規則是：

當q≤q0時：

(4)

當q>q0時，螞蟻根據轉移概率公式(2)選擇下一個點：

(5)

(6)

式中：q0和q是一個給定位于(0,1)之間的常數；τiu(t)表示“斑塊”i和“斑塊”u之間路徑上的信息素濃度；dij為兩個“斑塊”之間的距離；α代表信息素啟發因子，反映兩個螞蟻在運動過程中所積累的信息量(即殘留信息量τiu(t))在指導蟻群搜索中的相對重要程度；β代表期望值啟發因子，反映螞蟻在運動過程中啟發信息(即期望值ηij)在指導蟻群搜索中的相對重要程度；allowedk表示第k只螞蟻當前的可行進點的集合。

由于環境的原因隨著時間的變化，信息素逐漸揮發消失。信息素更新規則遵從局部更新以及全局動態更新的方式。

(1)局部更新。在路徑構建構成中，螞蟻每經過一條邊(i，j)都使用公式(7)來更新該邊上的信息素。

τij(t+1)=(1-ε)τij(t)+ετ0

(7)

式中：ε為局部軌跡持久性；τ0為信息素的初始值。

信息素局部更新的作用在于，螞蟻每經過一條邊，該邊上的信息素將會減少，從而降低其他螞蟻選中該邊的概率，增加了探索其他邊的機會。

(2)全局動態更新。當一次迭代結束后，將當前最優路徑使用公式(8)、(9)進行信息素全局更新。

τij(t+1) =(1-ρ)τij(t)+ρΔτij

(8)

(9)

式中：ρ為信息素揮發因子；1-ρ為信息揮發度；L1為當前迭代最優路徑長度；Lg為當前最優路徑長度。

更新當前最優路徑上的信息素反饋并保留到下一次迭代中，直到有更優路徑取代為止。

根據上述的描述，總結算法步驟如下：

步驟1：參數初始化。令迭代計數器NC=0，設置當前最優路徑長度S、最大迭代次數T、“斑塊”之間的距離dij(i,j=1,…,n)、啟發式信息ηij(i,j=1,…,n)、路徑上的信息素τij(i,j=1,…,n)。

步驟2：螞蟻位置初始化。初始化m只螞蟻的禁忌表tk(k=1,2,…,m)、所走路徑長度Lk(k=1,2,…,m)。所有的螞蟻隨機選擇初始“斑塊”，將所選的“斑塊”添加到禁忌表tk中，并更新Lk的值。

步驟3：路徑構建。每只螞蟻按公式(5)進行路徑選擇，將所選的“斑塊”添加到tk中，并更新Lk的值。

步驟4：信息局部更新。螞蟻每選擇一個“斑塊”，就對剛剛走過的路徑(i，j)根據公式(7)進行信息素局部更新。

步驟5：信息素全局動態更新。統計當前最優路徑，將Lk與S進行比較。若Lk

步驟6：迭代循環。若NC≤T，則返回步驟2，開始新一次迭代，否則算法結束，輸出最優路徑長度S和最優路徑。

3 實驗及結果分析

基于上述算法，使用軟件MATLAB對求解精準農業TSP問題的改進型蟻群算法進行仿真驗證，以單行種植茄子田地即株距為40 cm，行距為60 cm為參考，并對其進行坐標標準化處理，得到圖5所示田地模型。仿真算例中的“斑塊”坐標由系統隨機生成，共計22個，對于一些出現在作物區域的點，進行坐標微調，將這些點從作物區域移出。使用MATLAB 2017a編制程序，在i5-4460 3.2 GHZ、10 GB內存的計算機運行。

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。

表1 螞蟻數量m對算法性能的影響

根據該問題的需要，首先考慮算法的穩定性和所求得最優解的全局性，其次才是收斂速度。因此，在該問題下，螞蟻數m選取35為宜。

仿真實驗中的有關參數選取為：m=35,NCmax=100,ρ=0.1,Q=100，分別取不同啟發式因子α和β的組合進行比較，每組數據取實驗10次的平均值，結果見表2,3。

從以上仿真實驗不難發現，蟻群算法中啟發因子α和β的不同取值對算法的搜索性能會產生很大的影響。適當的選擇α和β的范圍，蟻群算法會獲得較好的搜索結果，并且算法的收斂速度也較為接近。由全面的實驗可以看出：在本文的問題中，α的最優值在1.5左右，而β在4～7之間最優。

表3 蟻群算法中期望值啟發因子對算法性能的影響

仿真實驗中的有關參數選取為：m=35,NCmax=100,α=1.5,β=5,Q=100，分別取ρ∈{0.1,0.2,0.3,0.4,0.5}進行比較，每組數據取實驗10次的平均值，結果見表4。

表4 信息素揮發因子對算法性能的影響

仿真實驗結果表明，在螞蟻數m一定的情況下，信息素揮發度1-ρ的大小對蟻群算法的收斂性能影響較大。1-ρ較大時，收斂速度快，但容易陷入局部最優解。反之，收斂速度慢，搜索的全局性好。當ρ值取0.1時最優。

仿真實驗中的有關參數選取為：m=35,NCmax=100,α=1.5,β=5,ρ=0.1。分別取Q∈{1,10,50,100}進行比較，每組數據取實驗10次的平均值，結果見表5。

通過以上仿真實驗看出，信息素釋放總量Q對蟻群算法的性能影響較小，因此在參數的選擇上不做特別考慮，在本文中選取Q=100。

綜上所述，本文參數選擇為：m=35,NCmax=100,α=1.5,β=5,ρ=0.1,Q=100。

表5 信息素釋放總量對算法性能的影響

3.2 仿真結果

與運行結果對應的路徑如圖4所示，從圖4中可以清晰地看到，自一個“斑塊”出發，每個“斑塊”訪問一次，遍歷所有“斑塊”后，返回起點，尋找到了最短路徑。圖中行間距和作物間距依據茄子實際種植的行間距和作物間距；灰色區域為作物區間(機器不可通過)，白色空白區域為田埂區域(機器可通過)。

圖4 TSP路線圖

圖5表示迭代次數和最短距離的關系，隨著迭代次數的增加，最短距離呈現不斷下降趨勢。當迭代次數大于41后，最短距離已不再變化，表明已經尋找到最佳路徑。

圖5 算法得到最優解歷程曲線

為驗證仿真的可靠性，針對農田中可能在某一區域出現多個“斑塊”的情況進行仿真實驗。為保證實驗的可靠性，依然選取22個點，并保證在某一區域有不少于5～6個“斑塊”點下，其他各點仍為隨機生成。每組數據取實驗10次的平均值，實驗結果如表6所示。本文還計算了在相同模型下，采用傳統土壤測量(即梭行法逐行逐列進行數據測量)所走路線距離為965.64。通過使用蟻群算法和傳統土壤測量方法的比較，驗證算法的可行性。

表6 蟻群算法結果對比

通過上述仿真實驗不難看出，該算法不僅適用于“斑塊”隨機均勻分布的情況，還適用于“斑塊”聚集的情況。而且面對“斑塊”聚集的情況，算法收斂更快。同傳統梭行法測量方法相比最短距離至少縮短了1/3。

仿真結果驗證了精準農業土壤測量TSP問題數學模型，以及算法的有效性，仿真表明，將改進型蟻群算法應用在精準農業土壤測量TSP問題能夠迅速找到最優路徑，可以有效的減少燃料，節約運行時間，在處理某一區域多“斑塊”的情況具有更好效果。

4 結 論

這篇文章針對精準農業的土壤測量中因土壤時空變異性而導致“斑塊”的情況，將其轉化為TSP問題并進行優化，使用改進型蟻群算法進行求解，此蟻群算法對傳統蟻群算法的信息素更新方式進行改進，采用信息素局部、全局更新的方式，提高搜索效率，避免陷入局部最優解，并通過MATLAB軟件對算法進行仿真驗證，實驗結果表明該算法可以減少機器在田間的行駛距離，有效地節約燃料和時間。隨著信息技術的發展，精準農業無疑是大勢所趨，精準農業目前面臨的最大問題無非是農田大規模測量問題以及精準作業問題例如農田精準施肥、精準灌溉等。本文研究內容是田壟農田的路徑規劃問題，本文研究成果可以應用在農田大規模測量以及精準作業方面上，為解決精準農業面臨的問題提供一種解決方案。

□