云澤暉，邵仕泉，買童寧

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

0 引 言

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

1 精準(zhǔn)農(nóng)業(yè)中TSP問題及模型介紹

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

圖1 土壤濕度地圖

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

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

圖2 “豐”字形農(nóng)田

2 求解精準(zhǔn)農(nóng)業(yè)TSP問題的蟻群算法

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

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

(1)

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

(2)

式中：h1為最上邊田埂的坐標(biāo)值；h2中間田埂的縱坐標(biāo)值。

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

(3)

式中：hz為中間田埂的縱坐標(biāo)值。

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

當(dāng)q≤q0時：

(4)

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

(5)

(6)

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

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

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

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

(7)

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

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

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

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

(8)

(9)

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

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

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

步驟1：參數(shù)初始化。令迭代計數(shù)器NC=0，設(shè)置當(dāng)前最優(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)。所有的螞蟻隨機(jī)選擇初始“斑塊”，將所選的“斑塊”添加到禁忌表tk中，并更新Lk的值。

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

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

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

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

3 實驗及結(jié)果分析

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

3.1 參數(shù)選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 仿真結(jié)果

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

圖4 TSP路線圖

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

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

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

表6 蟻群算法結(jié)果對比

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

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

4 結(jié) 論

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

□