云澤暉，邵仕泉，買童寧

(西南民族大學(xué)電子信息工程國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，成都 610041)

0 引 言

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

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

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

圖1 土壤濕度地圖

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

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

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

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

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

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

(1)

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

(2)

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

第三類，兩個(gè)“斑塊”位置分屬于第一行和第二行且不屬于同一塊的區(qū)域，如圖4中3、5“斑塊”位置，因?yàn)槠鋵儆凇耙簧弦幌隆眱尚械那闆r，走中間田埂距離最短，則兩點(diǎn)最短距離公式為：

(3)

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

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

當(dāng)q≤q0時(shí)：

(4)

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

(5)

(6)

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

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

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

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

(7)

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

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

(2)全局動(dòng)態(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)路徑長(zhǎng)度；Lg為當(dāng)前最優(yōu)路徑長(zhǎng)度。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

3.1 參數(shù)選擇

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

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

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

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

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

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

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

仿真實(shí)驗(yàn)中的有關(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ù)取實(shí)驗(yàn)10次的平均值，結(jié)果見(jiàn)表4。

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

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

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

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

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

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

3.2 仿真結(jié)果

與運(yùn)行結(jié)果對(duì)應(yīng)的路徑如圖4所示，從圖4中可以清晰地看到，自一個(gè)“斑塊”出發(fā)，每個(gè)“斑塊”訪問(wèn)一次，遍歷所有“斑塊”后，返回起點(diǎn)，尋找到了最短路徑。圖中行間距和作物間距依據(jù)茄子實(shí)際種植的行間距和作物間距；灰色區(qū)域?yàn)樽魑飬^(qū)間(機(jī)器不可通過(guò))，白色空白區(qū)域?yàn)樘锕^(qū)域(機(jī)器可通過(guò))。

圖4 TSP路線圖

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

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

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

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

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

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

4 結(jié) 論

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

□