云澤暉,邵仕泉,買童寧
(西南民族大學(xué)電子信息工程國家民委重點(diǎn)實(shí)驗(yàn)室,成都 610041)
精準(zhǔn)農(nóng)業(yè)是以信息技術(shù)為支撐,根據(jù)空間變異,定位、定時、定量地實(shí)施一整套現(xiàn)代化農(nóng)事操作與管理的系統(tǒng)[1],被認(rèn)為是農(nóng)業(yè)生產(chǎn)和環(huán)境友好實(shí)踐的貢獻(xiàn)者。也就是說,在適當(dāng)?shù)臅r間、地點(diǎn)應(yīng)用現(xiàn)代機(jī)器,以提高經(jīng)濟(jì)效益,并減少農(nóng)藥和化肥的投放,降低對環(huán)境的影響。但是要實(shí)現(xiàn)精準(zhǔn)控制,就必須知道每個位置的具體情況,才能因地制宜。實(shí)際上,由于土壤的時空變異性,比如:土壤類型、養(yǎng)分可利用性和作物害蟲等因素,會出現(xiàn)多個斑塊(與相鄰?fù)寥佬再|(zhì)不同)。因此需要對整塊土地進(jìn)行測量,但是除去這些“斑塊”位置,其他位置的情況均能根據(jù)附近的點(diǎn)測算出來,那么只需測量這些“斑塊”即可?,F(xiàn)有的農(nóng)業(yè)土壤測量方法大多將便攜式土壤測量儀安裝在農(nóng)業(yè)器具上,每隔一段距離對附近的土壤采用梭行法(即農(nóng)機(jī)逐行逐列行進(jìn))進(jìn)行測量,大大地增加的燃料的損耗,并且比較耗時。如果有一些先驗(yàn)信息可用(提前知道這些斑塊位置),那么機(jī)器可以選擇關(guān)鍵的信息位置來獲取測量結(jié)果。如果附近的土壤具有相關(guān)性,則機(jī)器不需要精確地訪問每個位置,而是訪問其領(lǐng)域中的某個點(diǎn),這樣就可以將精準(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中驗(yàn)證其方法有效性;ZHOU[13]等學(xué)者開發(fā)了一種田間規(guī)劃方法,將田地中多個障礙區(qū)域的優(yōu)化問題,轉(zhuǎn)化為TSP問題,并通過實(shí)際試驗(yàn),驗(yàn)證其方法的有效性;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問題中,實(shí)現(xiàn)機(jī)器最優(yōu)路徑規(guī)劃。該方法首先根據(jù)不同的土壤結(jié)構(gòu)以及土壤時空變異性,得到斑塊的位置,根據(jù)這些斑塊位置,以及斑塊的差異性進(jìn)行數(shù)學(xué)建模,將該問題轉(zhuǎn)化為新型TSP問題。之后,采用蟻群算法對該TSP問題進(jìn)行求解,得出最優(yōu)解。
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)田
設(shè)有m只螞蟻,每只螞蟻根據(jù)以“斑塊”距離和鏈接邊上信息素的數(shù)量為變量的概率函數(shù)選擇下一個“斑塊”[設(shè)τij(t)為t時刻e(i,j)上信息素的強(qiáng)度]?!鞍邏K”距離是根據(jù)田地實(shí)際情況如圖3(白色空白區(qū)域?yàn)樘锕^(qū)域允許機(jī)器通過,綠色區(qū)域?yàn)樽魑飬^(qū)域不允許機(jī)器通過)可分為三類。
第一類,兩個“斑塊”位置處于同一塊區(qū)域,如圖3中1、2“斑塊”位置,則兩點(diǎn)最短距離公式為:
(1)
第二類,兩個“斑塊”位置同屬于第一行或者是第二行的區(qū)域,如圖4中1、4和2、3“斑塊”位置, 在求解這種情況下的最短距離時,需要比較走最上邊田埂和中間田埂的最短距離,選擇最短距離的走法,則兩點(diǎn)最短距離公式為:
(2)
式中:h1為最上邊田埂的坐標(biāo)值;h2中間田埂的縱坐標(biāo)值。
第三類,兩個“斑塊”位置分屬于第一行和第二行且不屬于同一塊的區(qū)域,如圖4中3、5“斑塊”位置,因?yàn)槠鋵儆凇耙簧弦幌隆眱尚械那闆r,走中間田埂距離最短,則兩點(diǎn)最短距離公式為:
(3)
式中:hz為中間田埂的縱坐標(biāo)值。
初始時刻,各條路徑的信息素相等,設(shè)τij(t)=C(C為常數(shù))。在運(yùn)動過程中,根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向,第k只螞蟻由“斑塊”i選擇到下一個“斑塊”j的規(guī)則是:
當(dāng)q≤q0時:
(4)
當(dāng)q>q0時,螞蟻根據(jù)轉(zhuǎn)移概率公式(2)選擇下一個點(diǎn):
(5)
(6)
式中:q0和q是一個給定位于(0,1)之間的常數(shù);τiu(t)表示“斑塊”i和“斑塊”u之間路徑上的信息素濃度;dij為兩個“斑塊”之間的距離;α代表信息素啟發(fā)因子,反映兩個螞蟻在運(yùn)動過程中所積累的信息量(即殘留信息量τiu(t))在指導(dǎo)蟻群搜索中的相對重要程度;β代表期望值啟發(fā)因子,反映螞蟻在運(yùn)動過程中啟發(fā)信息(即期望值ηij)在指導(dǎo)蟻群搜索中的相對重要程度;allowedk表示第k只螞蟻當(dāng)前的可行進(jìn)點(diǎ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ù)初始化。令迭代計(jì)數(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)計(jì)當(dāng)前最優(yōu)路徑,將Lk與S進(jìn)行比較。若Lk
步驟6:迭代循環(huán)。若NC≤T,則返回步驟2,開始新一次迭代,否則算法結(jié)束,輸出最優(yōu)路徑長度S和最優(yōu)路徑。
基于上述算法,使用軟件MATLAB對求解精準(zhǔn)農(nóng)業(yè)TSP問題的改進(jìn)型蟻群算法進(jìn)行仿真驗(yàn)證,以單行種植茄子田地即株距為40 cm,行距為60 cm為參考,并對其進(jìn)行坐標(biāo)標(biāo)準(zhǔn)化處理,得到圖5所示田地模型。仿真算例中的“斑塊”坐標(biāo)由系統(tǒng)隨機(jī)生成,共計(jì)22個,對于一些出現(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)行。
蟻群算法中,螞蟻數(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越大,其螞蟻?zhàn)哌^路徑上的信息素的累積加快,有助于算法的快速收斂。這些參數(shù)均需要選擇一個恰當(dāng)?shù)臄?shù)值,才能提高算法的穩(wěn)定性以及全局搜索能力。但是,由于理論不夠成熟沒有確切的公式計(jì)算出各參數(shù)值,只能通過實(shí)驗(yàn)驗(yàn)證的方法,確定參數(shù)的取值。
選取上述問題作為例子,仿真實(shí)驗(yàn)中的有關(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ù)取實(shí)驗(yàn)10次的平均值,所得的實(shí)驗(yàn)結(jié)果見表1。
表1 螞蟻數(shù)量m對算法性能的影響
根據(jù)該問題的需要,首先考慮算法的穩(wěn)定性和所求得最優(yōu)解的全局性,其次才是收斂速度。因此,在該問題下,螞蟻數(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é)果見表2,3。
從以上仿真實(shí)驗(yàn)不難發(fā)現(xiàn),蟻群算法中啟發(fā)因子α和β的不同取值對算法的搜索性能會產(chǎn)生很大的影響。適當(dāng)?shù)倪x擇α和β的范圍,蟻群算法會獲得較好的搜索結(jié)果,并且算法的收斂速度也較為接近。由全面的實(shí)驗(yàn)可以看出:在本文的問題中,α的最優(yōu)值在1.5左右,而β在4~7之間最優(yōu)。
表3 蟻群算法中期望值啟發(fā)因子對算法性能的影響
仿真實(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é)果見表4。
表4 信息素?fù)]發(fā)因子對算法性能的影響
仿真實(shí)驗(yàn)結(jié)果表明,在螞蟻數(shù)m一定的情況下,信息素?fù)]發(fā)度1-ρ的大小對蟻群算法的收斂性能影響較大。1-ρ較大時,收斂速度快,但容易陷入局部最優(yōu)解。反之,收斂速度慢,搜索的全局性好。當(dāng)ρ值取0.1時最優(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é)果見表5。
通過以上仿真實(shí)驗(yàn)看出,信息素釋放總量Q對蟻群算法的性能影響較小,因此在參數(shù)的選擇上不做特別考慮,在本文中選取Q=100。
綜上所述,本文參數(shù)選擇為:m=35,NCmax=100,α=1.5,β=5,ρ=0.1,Q=100。
表5 信息素釋放總量對算法性能的影響
與運(yùn)行結(jié)果對應(yīng)的路徑如圖4所示,從圖4中可以清晰地看到,自一個“斑塊”出發(fā),每個“斑塊”訪問一次,遍歷所有“斑塊”后,返回起點(diǎn),尋找到了最短路徑。圖中行間距和作物間距依據(jù)茄子實(shí)際種植的行間距和作物間距;灰色區(qū)域?yàn)樽魑飬^(qū)間(機(jī)器不可通過),白色空白區(qū)域?yàn)樘锕^(qū)域(機(jī)器可通過)。
圖4 TSP路線圖
圖5表示迭代次數(shù)和最短距離的關(guān)系,隨著迭代次數(shù)的增加,最短距離呈現(xiàn)不斷下降趨勢。當(dāng)?shù)螖?shù)大于41后,最短距離已不再變化,表明已經(jīng)尋找到最佳路徑。
圖5 算法得到最優(yōu)解歷程曲線
為驗(yàn)證仿真的可靠性,針對農(nóng)田中可能在某一區(qū)域出現(xiàn)多個“斑塊”的情況進(jìn)行仿真實(shí)驗(yàn)。為保證實(shí)驗(yàn)的可靠性,依然選取22個點(diǎn),并保證在某一區(qū)域有不少于5~6個“斑塊”點(diǎn)下,其他各點(diǎn)仍為隨機(jī)生成。每組數(shù)據(jù)取實(shí)驗(yàn)10次的平均值,實(shí)驗(yàn)結(jié)果如表6所示。本文還計(jì)算了在相同模型下,采用傳統(tǒng)土壤測量(即梭行法逐行逐列進(jìn)行數(shù)據(jù)測量)所走路線距離為965.64。通過使用蟻群算法和傳統(tǒng)土壤測量方法的比較,驗(yàn)證算法的可行性。
表6 蟻群算法結(jié)果對比
通過上述仿真實(shí)驗(yàn)不難看出,該算法不僅適用于“斑塊”隨機(jī)均勻分布的情況,還適用于“斑塊”聚集的情況。而且面對“斑塊”聚集的情況,算法收斂更快。同傳統(tǒng)梭行法測量方法相比最短距離至少縮短了1/3。
仿真結(jié)果驗(yàn)證了精準(zhǔn)農(nóng)業(yè)土壤測量TSP問題數(shù)學(xué)模型,以及算法的有效性,仿真表明,將改進(jìn)型蟻群算法應(yīng)用在精準(zhǔn)農(nóng)業(yè)土壤測量TSP問題能夠迅速找到最優(yōu)路徑,可以有效的減少燃料,節(jié)約運(yùn)行時間,在處理某一區(qū)域多“斑塊”的情況具有更好效果。
這篇文章針對精準(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)行仿真驗(yàn)證,實(shí)驗(yà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è)面臨的問題提供一種解決方案。
□