改進粒子群優化算法的果園割草機作業路徑規劃

謝金燕 劉麗星 楊 欣 王 旭 王瀟灑 陳 諾

(河北農業大學 機電工程學院,河北 保定 071000)

我國是水果種植大國,果園種植面積逐年增加,趨向規?；?、現代化發展[1-2]。果園雜草過多影響果樹生長,機械除草是當前經濟效益較高的一種除草方式[3]。規范化種植的果園,果樹排列整齊,行間留有較大間距,使得機械除草容易實現。與傳統人力駕駛割草機在果樹行間逐行往復除草的方法相比,采用農業機械自動導航技術對具有自主導航功能的割草機進行全覆蓋作業路徑規劃,可顯著提高割草機的作業效率,降低其作業成本,對果園生產管理更有益[4-5]

全覆蓋路徑規劃是基于環境信息已知前提下,對覆蓋固定區域的路徑做出合理規劃的路徑規劃方法[5]。Bochtis等[6]提出了一種B-patterns模型,將農機作業時對農田的全覆蓋表示為加權圖的遍歷,尋找最優作業路線等效于尋找使總非工作距離最小的遍歷序列。Hameed等[7]則在B-patterns模型的基礎上,考慮使農機作業重疊區域最小化問題,提出了基于遺傳算法的三階段路徑規劃方法。Amalia等[8]以農機全覆蓋作業時的工作距離最短為目標,提出了一種進化混合鄰域搜索算法來求解不同作業場景下的路徑優化問題。國內,孟志軍等[9]提出了一種全區域覆蓋路徑優化方法,通過選擇不同優化目標計算出農機最佳作業方向,以此生成沿該方向逐行覆蓋地塊的作業路徑。黃小毛等[10]則考慮了跨行作業的情況,以轉彎路徑總長度最小為目標,將覆蓋矩形農田的各個作業行的調度排序問題轉化為經典的旅行商問題。羅承銘等[11]提出了針對四邊形田塊全覆蓋的混合路徑,同樣對混合路徑中的方向平行路徑進行調度排優以減少非工作路徑長度?，F有的全覆蓋路徑規劃研究常將路徑規劃問題轉化為離散的組合優化問題,且主要應用在農田作業中,而對果園環境下的全覆蓋路徑規劃還研究尚少。

不同于大田作業,果園由于果樹行的存在而形成了固定的作業結構。果園割草機工作時只需沿著果樹行方向從果園的一端到另一端、一行到另一行便可以完成整個果園的割草任務。割草機如何遍歷各果樹行完成割草任務,并使最終的工作路徑最短,是典型的全覆蓋路徑規劃問題[12]。目前,常使用元啟發式算法解決此類問題[13]。PSO(Particle swarm optimization)算法是一種基于一群在N維空間的粒子,通過自身與群體的適應度值評價來更新其位置和速度從而探索空間內全局最優解的啟發式群體智能算法,具有簡單易實現,收斂速度快,搜索范圍廣等特點,但易陷入局部最優[14]。本研究擬構建割草機作業模型,將果園環境下的割草機作業路徑規劃問題轉化為組合優化問題,并改進PSO算法進行求解,以期為果園環境下的農業裝備全覆蓋路徑規劃問題提供理論依據。

1 割草機作業路徑特點分析

現代蘋果果樹更多地采用矮化密植技術種植,為有效發揮該技術優勢,對果園建設提出了要求。園區選擇較為平緩的坡地,果樹株距為1.5～2.0 m,行距3～4 m,同時果樹行前后留有地頭便于機械化調頭[15]。果園割草機正常作業時,每個果樹行一般來回收割2次即可完成行間除草任務。大部分果園為了保墑、提溫、抑制雜草生長,會選擇順著樹行覆黑色地布。鋪設地布處無雜草,割草機工作時無需考慮這部分。

規范化布局的蘋果園,雜草多生長于果樹行間,使得割草機的作業方向與果樹行排列方向平行。割草機沿果樹行方向行駛的路徑可稱為方向平行路徑;當割草機割完一行雜草,在果園地頭處轉彎進入下一行,轉彎時行駛的路徑可稱為銜接路徑[16]。割草機工作時,方向平行路徑與銜接路徑交替出現,完成對果園的全覆蓋。因此,割草機的工作路徑由方向平行路徑與銜接路徑構成。果園環境確定時,方向平行路徑長度一般是固定值。優化割草機工作路徑時,不考慮方向平行路徑,采用減少銜接路徑長度的方式使割草機最終的總路徑最短。

2 割草機作業模型構建

2.1 割草機作業行

除草時,割草機沿著果樹行來回工作2次,每個果樹行由此被割草機重新劃分為2個作業行(圖1)。

1.矩形果園;2.U型轉彎;3.地頭;4.地布;5.作業軌跡;6.作業行;7.T型轉彎;8.作業行編號;9.Ω型轉彎

對方向平行路徑的調度優化可顯著減少銜接路徑的總長度,即地頭總轉彎距離[11]。當割草機工作參數及果園環境參數確定時,可對作業行進行調度排優來減少總轉彎距離,即通過對各作業行間的合理排序完成對割草機作業路徑的規劃。不同的轉彎策略產生的轉彎路徑不同,要計算總轉彎距離,需對割草機作業時選擇的轉彎策略進行分析。

2.2 地頭轉彎距離

割草機完成一行割草作業后,需要在果園地頭處轉彎進入下一行。當具有自主導航功能的輪式果園割草機轉彎時,通常使用阿克曼轉向。根據割草機作業間距Lw與最小轉彎半徑r的大小關系,常用的轉彎策略有Ω型、U型和T型[17](圖2)。

O1和O2為輔助圓圓心;A、B、C和D為轉彎路徑與圓O1、圓O2的切點;Lw為割草機的作業間距;r為最小轉彎半徑。

割草機在同一果樹行內轉彎時轉彎路徑中不包含地布,而在不同果樹行間轉彎時則需考慮包含的地布數,以便計算轉彎距離。根據該特點,本研究改進Ω型、U型和T型轉彎距離計算公式如下:

(1)

dU=(π-2)r+d(i,j)w+mLd

(2)

dT=(π+2)r-d(i,j)w-mLd

(3)

式中:dΩ表示Ω型轉彎距離;dU表示U型轉彎距離;dT表示T型轉彎距離;r為割草機的最小轉彎半徑;i為當前作業行的編號;j為割草機轉入的下一行的編號;d(i,j)為轉彎時兩作業行間的跨度,d(i,j)=|i-j|,i≠j;w為割草機的作業幅寬;m為轉彎時所跨地布數;Ld為地布寬度。

設V={1,2,…,n}為割草機作業行編號的集合,n為總行數;dij為割草機從i行轉入j行的轉彎距離(?i,j∈V),且dij=dji,dnn=0。割草機采用T型轉彎時需要沿直線倒車,為簡化割草機作業,只考慮Ω型轉彎和U型轉彎,轉彎類型的判斷方法如下:

(4)

根據作業行間的轉彎距離dij構建距離矩陣D如下:

(5)

實際割草機轉彎時并非嚴格按照上述轉彎方式進行轉彎,為方便計算,不考慮割草機實際轉彎路徑與理論轉彎路徑不重合所帶來的轉彎距離偏差。

2.3 數學模型

以割草機的作業行序列為變量,總轉彎距離最小為目標函數,構建割草機作業路徑優化模型如下:

1)定義變量:

(6)

式中:xij為割草機是否從i行轉入j行的決策變量。

2)目標函數:

(7)

式中:dij為作業行i與j之間的轉彎距離。

3)約束條件:

(8)

(9)

式中:a為割草機工作起始行編號;b為割草機工作結束行編號。

(10)

式中:|S|為集合S元素的個數。

式(8)～(10)表示每個作業行僅被割草機遍歷1次,且割草機完成作業后不會回到起始行。

3 PSO算法改進

3.1 PSO算法求解離散問題分析

經典PSO算法[18]的核心是通過粒子間相互分享信息使粒子群體由無序轉為有目標地向空間內的最優解方向移動,最終獲得問題的解。N維搜索空間內,粒子i的位置為Xi=(xi1,xi2,…,xiN),速度為Vi=(vi1,vi2,…,viN),粒子i自身訪問過的最佳位置為Pi=(pi1,pi2,…,piN),整個粒子群體訪問過的最佳位置為Pg=(pg1,pg2,…,pgN)。粒子速度與位置的更新公式如下:

(11)

(12)

經典的PSO算法常用于在連續定義域上查找數值函數的最小值,割草機作業行的調度排優是離散的組合優化問題,求解時需對算法各部分重新定義[19-20]。

2)粒子的適應度值定義為割草機工作時的總轉彎距離,適應度值越小代表粒子找到的作業路徑越好。

4)針對離散問題,粒子位置的更新逐步進行,步驟如下:

①記錄使粒子i由當前位置轉變為最佳位置Pi、Pg的交換序列,在(0,1)范圍內隨機選取學習因子的值,按c1、c2的概率分別對能轉換為Pi、Pg的交換序列進行保留;

②按慣性權重ω值的概率對當前調整序列進行保留;

③將保留的交換序列與調整序列融合,以此作為新的調整序列;

④利用更新后的調整序列對粒子i當前位置進行調整,得到下一次迭代的粒子位置。

3.2 PSO算法改進策略

3.2.1改進慣性權重

慣性權重ω的大小反映當前粒子i的速度受上一代粒子的影響程度,是PSO算法的重要參數?，F有的慣性權重模型有3種:常數、時變慣性權重及自適應慣性權重。為找到全局最優解,與靜態值相比,動態變化的ω尋優效果更好[21]。本研究基于線性遞減慣性權重[22]提出一種非線性遞減慣性權重,表達式為:

(13)

式中:Tmax為算法的最大迭代次數;k為當前迭代次數。

圖3示出線性與非線性遞減慣性權重隨搜索進程的變化?？梢?相比于線性遞減慣性權重,提出的非線性遞減慣性權重使ω值在搜索前期較大,加強粒子的全局搜索能力;在搜索后期較小,加強粒子的尋優能力,以便獲得更好的最優解。

圖3 線性與非線性遞減慣性權重隨搜索進程的變化

3.2.2改進學習因子

學習因子(c1、c2)決定了粒子向自身及群體訪問過的最佳位置靠近的概率,設計得當,將大大提高尋優效率。文獻[23]提出了一種時變學習因子:在搜索初期,使控制粒子向自我學習的因子c1值較大,向群體學習的因子c2值較小,便于粒子全局探索;在搜索后期則相反,便于粒子專注尋優。因此,本研究設置學習因子為所提出的非線性遞減慣性權重的三角函數,使c1隨搜索進程遞減,c2隨搜索進程遞增,同時使PSO算法的3個參數整合為一體,提高算法優化過程的均勻性,具體表達式如下:

c1=sinω

(14)

c2=1-sinω

(15)

學習因子c1、c2隨搜索進程的變化見圖4。

圖4 學習因子c1與c2隨搜索進程的變化

3.2.3粒子擾動

隨著迭代次數的增加,粒子群體逐漸向同一目標區域靠近,容易陷入局部最優,失去多樣性。為此,本研究使用交換操作對處于最佳位置處的粒子進行輕微擾動,增加粒子跳出當前局部最優的可能性,以便粒子尋找更好的作業路徑。

交換過程為:假設粒子i經過迭代更新后獲得的最佳作業行序列為2→5→8→10→7→4→1→3→6→9,隨機選取兩個作業行進行位置交換,如作業行3和5,則交換后的作業序列為2→3→8→10→7→4→1→5→6→9。作業行序列完成交換后將產生新的作業路徑,計算當前新路徑的適應度值,并與交換前的適應度值進行對比。若新路徑較優,則保留新路徑,否則維持原有路徑不變。

3.3 IPSO算法實現

本研究提出的IPSO(Improved particle swarm optimization)算法求解果園割草機作業路徑規劃問題的具體步驟如下:

1)輸入果園環境參數及割草機工作參數,構建距離矩陣D。

2)設置算法參數,隨機產生粒子群初始位置和速度,計算初始位置的適應度值,將初始位置作為各粒子的最佳位置并挑選出群體中的最佳位置。

3)更新慣性權重、學習因子、粒子位置及適應度值。

4)將更新后各粒子位置的適應度值與其訪問過的最佳位置的適應度值進行比較,若當前位置的適應度值更小,則保留其為最佳位置。

5)使用交換操作對處于最佳位置的粒子進行擾動,以便粒子跳出局部最優。

6)更新整個粒子群體的最佳位置,并記錄路徑。

7)判斷當前迭代次數是否達到最大迭代次數。若是,算法終止運行,輸出最優作業路徑,否則轉至步驟3)。

4 仿真試驗分析

為驗證不同作業行數和割草機工作參數條件下,IPSO算法解決割草機作業路徑優化問題時的優化性能,以總轉彎距離最小為優化目標,使用Matlab R2020b軟件進行仿真試驗。試驗評價指標為總轉彎距離減少率(IPSO算法與PSO算法求解出的最優路徑的總轉彎距離差值的百分比)、算法收斂速度(尋優迭代次數)和算法耗時。

4.1 不同作業行數下作業路徑優化結果分析

使用PSO算法、IPSO算法分別對作業行數為20、40、50、70、80和100行的6類果園進行作業路徑優化試驗。結合常見果園與割草機特點,設置割草機工作參數:作業幅寬w=0.9 m,最小轉彎半徑r=2 m;設置果園地布寬度Ld=2 m。設置粒子規模為500,迭代次數500;IPSO算法中,ωmax=1,ωmin=0;PSO算法中,ω=0.5,c1=0.7,c2=0.2。PSO算法屬于概率尋優,每次尋優結果不同。因此,每類果園取20次運行結果的平均值作為最終優化結果(表1)?？梢?針對選取的6種不同作業行數的果園,相同試驗條件下,與PSO算法相比,IPSO算法耗時平均增加約1.0～2.5 s,但均能找到總轉彎距離更少的作業路徑,總轉彎距離減少率為7.52%～32.72%。

表1 不同作業行數下PSO與IPSO算法尋優結果

選取作業行數為40、70和100行的3類果園,進行算法尋優對比(多次運行取平均值),結果見圖5:PSO算法與IPSO算法運行過程穩定,經過多次迭代計算后最終均能找到最優路徑且結果趨于穩定;迭代過程中,IPSO算法的收斂速度較慢,但最終的尋優結果均優于PSO算法,且增加作業行數,IPSO算法減少的總轉彎距離增大。

圖5 不同作業行數(n)下PSO與IPSO算法尋優過程對比

隨著作業行數的增加,尋找最優作業路徑的難度呈指數增長。IPSO算法采用改進的慣性權重和學習因子,并對處于最佳位置處的粒子進行輕微擾動,使粒子群能更廣泛地搜索解空間,避免了因過早陷入局部最優而停止搜索。與PSO算法相比,IPSO算法雖收斂速度較慢,但能夠在大規模搜索的問題中找到更好的最優解。

4.2 不同割草機工作參數下作業路徑優化結果分析

保持果園環境參數及算法參數不變,選擇不同作業幅寬w、最小轉彎半徑r的割草機進行作業路徑優化試驗,并取20次運行結果的平均值作為最終優化結果,見表2?？芍?對于不同工作參數的割草機,相同試驗條件下,與PSO算法相比,IPSO算法均能找到總轉彎距離更少的割草機作業路徑。對比不同作業幅寬或最小轉彎半徑下的總轉彎距離,結果顯示:當作業幅寬或最小轉彎半徑減小時,總轉彎距離減少。

表2 不同割草機工作參數下PSO與IPSO算法尋優結果

通過以上仿真試驗,表明了IPSO算法在求解割草機作業路優化問題時的有效性及普適性。

5 田間試驗驗證

為驗證提出的IPSO算法解決割草機作業路徑優化問題時的實用性,在標準蘋果園內進行田間試驗。

1)試驗場地:河北省保定市順平縣順農果品現代農業園區的某一矩形果園。經實地多次測量取平均值,獲得果園環境參數為:作業行數30行、行間距4 m、地布寬度Ld=2 m。

2)試驗設備:由強視(上海)科技有限公司生產的G33遙控割草機,割草機在試驗園內的工作場景見圖6。

1.地布;2.作業行編號;3.G33遙控割草機;4.作業行

3)試驗評價指標:試驗過程中受設備性能、果園路況及人工操作等多方面因素影響,割草機實際行走軌跡與理論計算偏差較大,故使用作業過程中的油耗率g作為評價指標,表達式如下:

(16)

式中:H1為試驗前割草機油箱的油量高度;H2為試驗后割草機油箱的油量高度;H3為割草機加滿油時油箱的油量高度,測得為32 cm。

4)試驗過程:①對H1進行測量并記錄;②人工遙控G33割草機按照傳統逐行割草的方式進行試驗;③對H2進行測量并記錄;④重復步驟①、②和③,依次對PSO算法、IPSO算法生成的作業路徑進行試驗。

試驗結果見表3?？芍?割草機采用算法求解的作業路徑比采用傳統路徑節省油耗,采用IPSO算法求解的作業路徑時油耗最小,比傳統方法節約 22.51%,比PSO算法節約1.57%。由此,表明了IPSO算法的實用性。

表3 不同作業路徑下割草機的油耗結果

6 結 論

本研究針對果園割草機作業路徑規劃問題,構建了以總轉彎距離最小為優化目標的割草機作業模型,并提出一種IPSO算法求解該模型,主要結論如下:

1)提出的隨搜索進程非線性動態變化的算法參數及對處于最佳位置的粒子進行輕微擾動的策略能夠有效增強PSO算法的尋優能力。不管作業行數或割草機工作參數如何變化,相比于PSO算法,IPSO算法總能找到總轉彎距離更少的作業路徑。

2)作業行數增加時,與PSO算法相比,IPSO算法減少的總轉彎距離增大;保持作業行數不變,減小割草機的作業幅寬或最小轉彎半徑可減少總轉彎距離。

3)割草機實際作業情況下,采用算法規劃的作業路徑比采用傳統路徑節省油耗。

此外,IPSO算法求解組合優化問題時的效率相對較低,下一步可以改進其他群體智能算法求解該類問題,以獲得更優的割草機作業路徑。果園實際生產中離不開機械化操作,果園智能裝備路徑規劃問題還需進一步研究。