精準農業(yè)土壤測量中TSP問題求解

云澤暉，邵仕泉，買童寧

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

0 引 言

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

1 精準農業(yè)中TSP問題及模型介紹

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

圖1 土壤濕度地圖

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

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

圖2 “豐”字形農田

2 求解精準農業(yè)TSP問題的蟻群算法

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

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

(1)

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

(2)

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

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

(3)

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

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

當q≤q0時：

(4)

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

(5)

(6)

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

由于環(huán)境的原因隨著時間的變化，信息素逐漸揮發(fā)消失。信息素更新規(guī)則遵從局部更新以及全局動態(tài)更新的方式。

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

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

(7)

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

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

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

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

(8)

(9)

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

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

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

步驟1：參數(shù)初始化。令迭代計數(shù)器NC=0，設置當前最優(yōu)路徑長度S、最大迭代次數(shù)T、“斑塊”之間的距離dij(i,j=1,…,n)、啟發(fā)式信息η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)根據(jù)公式(7)進行信息素局部更新。

步驟5：信息素全局動態(tài)更新。統(tǒng)計當前最優(yōu)路徑，將Lk與S進行比較。若Lk

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

3 實驗及結果分析

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

3.1 參數(shù)選擇

蟻群算法中，螞蟻數(shù)目越多，越能提高蟻群算法的全局搜索能力以及算法的穩(wěn)定性。但螞蟻數(shù)目增加到一定程度以后，會降低算法的收斂速度。同樣的，信息素啟發(fā)因子α大小反映了在蟻群路徑搜索中的隨機性因素作用的強度，其值越大，搜索的隨機性隨之減弱；期望值啟發(fā)因子β的大小反映了在蟻群路徑搜索中的確定性因素作用的強度，其值越大，搜索的收斂速度隨之加快，但蟻群在最優(yōu)路徑的搜索隨機性減弱；信息素揮發(fā)度1-ρ的大小直接關系到蟻群算法的全局搜索能力及其收斂速度。當1-ρ過大時會影響到算法的隨機性和全局搜索能力。反之，通過減小信息揮發(fā)度1-ρ雖然可以提高算法的隨機性能和全局搜索能力，但是會使算法的收斂速度降低；信息素釋放總量Q為螞蟻循環(huán)一周在經過路徑上所釋放的信息素總量，在蟻群算法中為一常量。一般認為：信息素釋放總量Q越大，其螞蟻走過路徑上的信息素的累積加快，有助于算法的快速收斂。這些參數(shù)均需要選擇一個恰當?shù)臄?shù)值，才能提高算法的穩(wěn)定性以及全局搜索能力。但是，由于理論不夠成熟沒有確切的公式計算出各參數(shù)值，只能通過實驗驗證的方法，確定參數(shù)的取值。

選取上述問題作為例子，仿真實驗中的有關參數(shù)選取為：NCmax=100,α=1.5,β=5,ρ=0.1,Q=100，分別取m∈{15,20,25,30,35,40}，其中m為螞蟻個數(shù)，NCmax代表最大迭代次數(shù)，α代表信息素啟發(fā)因子，β代表期望值啟發(fā)因子，ρ代表信息素揮發(fā)因子，Q代表信息素釋放總量。每組數(shù)據(jù)取實驗10次的平均值，所得的實驗結果見表1。

表1 螞蟻數(shù)量m對算法性能的影響

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

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

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

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

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

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

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

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

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

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

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

3.2 仿真結果

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

圖4 TSP路線圖

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

圖5 算法得到最優(yōu)解歷程曲線

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

表6 蟻群算法結果對比

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

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

4 結 論

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

□