基于遺傳—蟻群算法的農田微地形特征土方調配路徑研究

摘要：近年來極端天氣與自然災害頻發，導致農田損毀，造成農田內部出現微地形特征（凸起特征及洼地特征），影響耕作。針對上述問題，基于高精度農田數字地形模型，通過遺傳—蟻群算法提出一種規劃農田微地形特征土方調配路徑的方法。首先，基于航拍圖像獲取高精度農田數字地形模型，根據地形因子綜合隸屬度提取16個凸起特征和9個洼地特征，并分別計算挖填方量為0.885 m3和0.884 m3。其次，以土方量調配成本為決策目標，建立挖、填方區域為路徑搜索節點，利用蟻群算法獲得初始可行解，通過遺傳算法中的適應度函數對解進行初步優化，最后，根據交叉操作和變異操作對解進行二次優化，獲得最優土方調配路徑。結果表明，該方法經232次迭代獲取全局最優解，相較于傳統蟻群算法調配成本下降2.1%。為精準平整農田微地形特征作業提供方法支持。

關鍵詞：農田微地形特征；數字地形模型；土方調配；蟻群算法；遺傳算法

中圖分類號：S237" " " 文獻標識碼：A" " " 文章編號：2095?5553 （2024） 08?0270?06

Study on earthwork reallocation path for micro?topographic features of farmlands based on genetic?ant colony algorithm

Jin Xin1， Li Hanyuan1， Du Mengmeng1， Ji Jiangtao1， Ali Roshanianfard2

（1. School of Agricultural Equipment Engineering， Henan University of Science and Technology， Luoyang， 471003， China;2. Department of Agriculture and Natural Resources， University of Mohaghegh Ardabili， Ardabil， 566199， Iran）

Abstract： In recent years， due to the frequently occurred extreme weather and natural disasters， considerable amount of farmlands have been destructed， resulting in the emergence of micro?topographic features （bump features and concave features） within farmlands， thereby affecting farming. In order to solve the above problems， based on high?precision farmland digital terrain model and genetic ant colony algorithm， a method of soil allocation path planning for farmland micro?terrain features was proposed. Firstly， based on the SfM （Structure from Motion） technology to process aerial images of the test field， a high?precision farmland digital terrain model （FDTM） was obtained， and 16 bump features and 9 concave features were extracted according to the comprehensive membership degree of terrain factors， and the cut volume as well as fill volume was calculated as 0.885 m3 and 0.884 m3， respectively. Secondly， with the cost of earthwork reallocation as the decision target， cutting and filling areas were established as path search nodes， and the ant colony algorithm was used to obtain the initial feasible solutions. Subsequently， these solutions were preliminarily optimized by using the fitness function in the genetic algorithm. Finally， the optimal earthwork reallocation path was obtained by secondary optimization of the solutions according to the crossover and variation operation. The results showed that the global optimal solution was gained after 232 iterations， and the earthwork reallocation cost was reduced by 2.1% compared with the traditional ant colony algorithm. The research results can provide references for precise land leveling with respect to micro?topographic features.

Keywords： micro?topographic features of farmlands; digital terrain model; earthwork deployment; ant colony algorithm; genetic algorithm

0 引言

在生產建設活動或自然災害等外界因素的作用下，農田表層土壤遷移或流失，在地塊內部出現尺寸大小不等的凸起及洼地等微地形特征，不利于進行農田耕作。農田微地形特征在一定程度上反映農田地貌的不規則性。其中，凸起特征在形態上表現為中間高、四周低的封閉地勢，與經典地貌學中的山脊特征相似，指包含單個或多個高程極大值點的局部區域；而洼地特征則為四周高、中間低的封閉地勢，與經典地貌學中的山谷相似，指包含一個或多個高程極小值點的局部區域。為適應現代農業應用發展需要，提高農業生產效率，自主導航的農業車輛已成為不可替代的一部分[1]。微地形特征散亂分布在農田各處，利用具備自動導航的農業機器人根據規劃的路徑，可實現農田凸起及洼地特征的土方量調配，達到平整農田微地形特征的目的。黃琪等[2]基于數字高程模型（DEM，Digital Elevation Model），利用線性規劃方法，根據挖、填土方量與單位土方量成本，規劃土方量調配路徑，但其忽視了農業機器人出現空載或過載的運行情況；Deng等[3]利用遺傳算法將土方工程分配問題簡化為車輛路線問題，然而卻忽視施工次序的問題，導致施工費用增加；王仁超等[4]根據土方量調運的影響因素，提出一種基于結合蟻群算法和粒子群算法的混合算法，解決土石方調配問題，相較線性規劃法，更加貼近工程實際，但不符合農田微地形狀況。

因此，本文以最低調配成本為決策目標，建立農田微地形特征的土方調配模型，利用蟻群算法獲取可行初始解，同時引入遺傳算法中的交叉操作和變異操作對解進行二次優化，確定農田微地形特征土方量調配的最優路徑，以期為規劃農田微地形特征土方調配作業路徑及精準平整地作業提供方法支持。

1 研究材料

研究區域位于陜西省寶雞市（107°9′14.893″E，34°39′182″N），其尺寸（長×寬）約為50 m×100 m。基于SfM（Structure from Motion）技術，從具有時間系列的二維圖像中提取三維信息，對試驗田進行三維重構，獲取空間分辨率為3 cm的農田數字地形模型FDTM。在FDTM環境下，確定農田微地形分析的窗口尺度范圍，選取適用于農田微地形結構的地形因子，并計算農田高程極值點的地形因子綜合隸屬度閾值，定位16個農田凸起特征的頂點，確定農田凸起特征的空間位置，并結合等高線圖識別凸起特征的外形輪廓。類似地，建立反轉數字地形模型RFDTM，將FDTM中的洼地特征轉變為RFDTM中的凸起特征，識別9個農田洼地特征，如圖1所示。

將農田微地形特征的外形輪廓向外偏置50 cm作為緩沖區域，計算微地形特征的高程均值，作為微地形特征的參考基準面高度。基于FDTM法計算農田凸起及洼地特征的挖填土方量，將試驗地塊劃分為若干個柵格，結合參考基準面與高程數據計算研究區域內每個柵格的體積[5]，如表1所示。

由式（1）與式（2）分別確定挖填土方量為1.204 m3和0.884 m3，挖方量遠大于填方量。在各凸起特征參考基準面高度的基礎上，設定高度調整變量x，利用逼近法確定x為0.022 m，由式（1）計算挖方量為0.885 m3。

[Vu挖=i=1n（Zi-Hu）Δσi] （1）

[Vv填=i=1n（Hv-Zi）Δσi] （2）

式中： i——柵格序號，i=1，2，…，n；

n——柵格數量；

Zi——柵格高程，m；

u——凸起特征的特征數量；

v——洼地特征的特征數量；

[Vv填]——第v個洼地特征的填方量，m3；

[Vu挖]——第u個凸起特征的挖方量，m3；

[Hu]——第u個凸起特征的基準面，m；

[Hv]——第v個洼地特征基準面，m；

?σi——柵格底面積，m2。

2 研究方法

2.1 建立數學模型

將農田凸起特征和洼地特征序號依次編號為Fea1，Fea2，…，Fea25，共計25塊。其中，各凸起特征為挖方節點，各洼地特征為填方節點。根據每步運輸的距離、每步運輸的土方量以及每步單位土方量的運輸成本，建立目標函數，如式（3）所示。

[minZ=EtDtFt] （3）

式中： Z——土方調配成本，元；

Et——第t步運輸的土方量，m3；

Ft——第t步單位土方量運輸成本，元/（m×m3）；

Dt——第t步的運輸距離，m。

2.2 約束條件

微地形特征土方調配即對目標特征進行切除和填埋，達到平整的目的。假設平整地機具負載有限，為避免過載應多次訪問挖填方節點，并更新各節點的剩余土方量，如式（4）～式（6）所示。

[Qtm=Sm+Itm-Otm] （4）

[Otm=Et+Ot-1m] （5）

[Itm=Et+It-1m] （6）

式中： m——挖、填方任意節點，m=1，2，…，q；

[Qtm]——經過t步后m節點剩余的土方量，m3；

Sm——m節點調配前達到基準面高度需要的土方量，m3；

[Itm]、[It-1m]——經t和t-1步后m節點運入的土方量總和，m3；

[Otm]、[Ot-1m]——經t和t-1步后m節點運出的土方量總和，m3。

為避免平整地機具出現空載或過載的情況，對每步運輸的土方量進行約束。具體地，設定每步運輸的土方量低于農業機器人的最大載重量，并令每步輸運的土方量大于特定值，以降低空載率，如式（7）所示。

[Et=VminEtVmax] [0lt;Et≤VminVminlt;Etlt;VmaxVmax≤Et] （7）

式中： Vmin——每步運輸的最小土方量，m3；

Vmax——每步運輸的最大土方量，m3。

2.3 確定微地形特征間的運輸距離

微地形特征土方量的運輸路線是土方調配的前提，即確定挖方、填方區域重心之間的距離。通過式（8）和式（9）計算挖方、填方區域重心的橫縱坐標，并利用式（10）確定微地形特征間的運輸距離。

[X=m=1nVmXmm=1nVm] （8）

[Y=m=1nVmYmm=1nVm] （9）

[Dij=（Xi-Xj）2+（Yi-Yj）2] （10）

式中： [X]、[Y]——挖、填方區域重心的橫縱坐標，（°）；

Vm——挖、填方區域重心中第m個格網的土方量/m3；

Xm、Ym——挖、填方區域中第m個格網的橫、縱坐標；

[Xi]、[Xj]——i節點和j節點重心的橫坐標；

[Yi]、[Yj]——i節點和j節點重心的縱坐標；

Dij ——i節點到j節點間的運輸距離，m。

2.4 遺傳—蟻群算法

本文利用蟻群算法產生路徑，通過遺傳算法中的交叉操作和變異操作對路徑進行優化，獲取全局最優土方調配路徑，算法流程如圖2所示。

與旅行商問題TSP類似，本文需要尋找一條滿足目標的最優路徑。TSP問題為在城市個數和各城市間距離已知的情況下，確定一條遍歷所有城市的最短路線[6]。蟻群算法ACA（Ant Colony Algorithm）是通過模擬自然界中螞蟻集體尋徑行為而提出的一種啟發式仿生算法[7]。ACA具有較強的魯棒性和易與其他算法結合等優點，但存在搜索效率低和易陷入局部最優求解循環等缺點。遺傳算法GA（Genetic Algorithm）是模擬生物進化過程的算法，具有全局搜索的優點[8]。

2.5 狀態轉移規則

將螞蟻h（h=1，2，…，m）放置在各挖方節點處，利用動態優先級策略，根據約束條件設置螞蟻訪問優先級。具體地，螞蟻每行走至下一節點柵格時，若負載的土小于填方量，則下一步行走至挖方節點的優先級高于填方節點，反之，則行走至填方節點的優先級高于挖方節點。通過式（11）計算螞蟻h從i節點轉移到j節點的啟發程度，并利用式（12）確定螞蟻從i節點到j節點的概率，輸出遍歷所有挖、填方節點的路徑。

[ηij（t）=1Dij] （11）

[Phij（t）=ταij（t）ηβij（t） s∈Cταis（t）ηβis（t）" " j∈C0" " 其他] （12）

式中： [Phij（t）]——螞蟻h在第t時刻從i節點到j節點處的狀態轉移概率；

C——所有與i節點有邊相連的節點集合；

α——信息素啟發式因子；

β——期望啟發式因子；

[ταij]——螞蟻h從i節點到j節點的信息素；

[ταis（t）]——第t時刻螞蟻h從i節點到s節點的信息素；

[ηis（t）]——螞蟻h在第t時刻從i節點到所有與i節點有邊相連的節點的啟發函數；

[ηij（t）]——螞蟻h在第t時刻從i節點到j節點處的啟發函數。

2.6 染色體編碼

蟻群算法根據每條路徑上信息素濃度的大小確定最優路徑，導致尋優結果易陷入局部循環。局部最優解是所有螞蟻最后均選擇一條路徑，但該條路徑為某一范圍內的最短路徑，在這范圍之外仍存在更短路徑。為了使螞蟻跳出局部最優求解循環，尋找到全局最優解，本文利用蟻群算法輸出所有路徑，將每次迭代輸出的路徑編碼成染色體構成GA的初始種群，即每條路徑代表一個染色體，多條染色體構成一個種群。具體地，編碼方式采用實數方式，農田中挖方區域和填方區域的總數量為25，將挖、填方節點編碼為l，2，3，…，25。每個編碼為一個基因，一條路徑由多個基因構成一條染色體。

2.7 適應度函數

適應度函數是評價種群中優良個體的指標，其函數值隨染色體被遺傳到下一代概率的增大而增加[9]。本文目標為降低微地形特征的土方調配成本，通過調配成本構建立遺傳算法的適應度函數，即確定編碼染色體在種群內的適應度，如式（13）所示。由式（13）可知，調配成本函數與染色體的適應度呈負相關，即調配成本越低，染色體的適應度越高，有更高的幾率遺傳給下一代。

[Fk=1Tkk=11Tk] （13）

式中： Fk——當前迭代次數的第k條染色體的適應度；

Tk——當前迭代次數的第k條染色體的調配成本，元。

2.8 交叉操作和變異操作

本文為了避免交叉后的染色體出現重復基因，提出非對稱的映射交叉操作。交叉操作通過混合遺傳數據，增大種群內部的競爭壓力，產生更為優質的基因，增加種群的多樣性[10]。具體地，隨機選擇兩條父代染色體，對兩條父代染色體進行非對稱截斷，產生4個基因片段，選擇2個父代前半段或者后半段基因片段作為待拼接片段，并對待拼接基因片段的進行互換。通過對子代1和子代2中的待拼接基因片段進行一對一映射，19→12，18→8，6→9和22→24，消除子代1和子代2中的重復基因，獲得子代3和子代4，如圖3所示。

變異操作是增加種群多樣性的一種進化手段，既能保持種群內個體的多樣化，又能提高算法的效率[10]。具體地，染色體在進行交叉操作后，隨機選取一條染色體，互換其任意兩個不相鄰基因的位置，如圖4所示。

2.9 信息素更新策略

蟻群算法收斂到最優解的過程是信息素正反饋的結果，信息素的調整策略對算法的收斂性和求解效率具有很大影響[11]。本文通過編碼、交叉操作和變異操作生成新路徑，并利用式（14）、式（15）更新路徑上的信息素，增大最優解被選擇的概率。被選擇路徑的概率隨著信息素的增加而逐漸上升，而未被選擇路徑的概率隨著信息素揮發逐漸減小。根據額定的迭代次數，尋找到一條信息素濃度最高的路徑，即全局最優微地形特征土方量調配路徑。

[τij（t+1）=（1-ρ）τij（t+1）+h=1mΔτhij] （14）

[Δτhij（t）=QDij" " 第h只螞蟻經過的路徑ij0" " " " 其他] （15）

式中： ρ——信息素揮發系數；

[h=1m?τhij]——信息素的增量總和；

[?τhij]——第h只螞蟻在i節點到j節點間遺留的信息素量；

Q——螞蟻在每次迭代中留下信息素的總量。

3 試驗結果與分析

3.1 算法性能分析

為驗證遺傳—蟻群算法相較于傳統蟻群算法的優越性，本文選擇信息素總量Q為10，信息素啟發式因子α為1，期望啟發式因子β為2，信息素揮發系數ρ為0.5，交叉概率和變異概率分別為0.9和0.006，設置每步單位土方運輸成本為15元/（m×m3）。根據挖方區域最小和最大土方量分別設定Vmin為0.005 m3，Vmax為0.338 m3，并確定迭代次數為300次，對遺傳—蟻群算法與傳統蟻群算法進行性能分析，如圖5所示。

由圖5可知，在第25次迭代之前，螞蟻通過選擇不同的路徑，多條路徑上的信息素濃度增加，兩種算法的搜索效率在初始階段上升。在25～100次迭代中，由于信息素分布不均勻的影響，導致傳統ACA信息素積累在局部最優路徑上。GA-ACA通過引入遺傳算法中交叉操作和變異操作，增加了算法的全局搜索性和路徑的多樣性。本文方法在232次達到全局最優結果，而傳統蟻群算法在79次達到局部最優結果。因此，GA-ACA與傳統ACA相比，具有更優的求解結果。

3.2 微地形特征土方調配分析

本文利用GA-ACA和傳統ACA對農田凸起特征和洼地特征進行土方量調配，如表2和表3所示。由表2和表3可知，傳統ACA土方量調配結果為224.77元，GA-ACA土方量調配結果為215.52元，相較于傳統蟻群算法調配費用下降了2.1%。GA-ACA法對于較大土方量，選擇較近的填方區域進行運輸，對于較小土方量，選擇較遠的填方區域進行運輸，大大降低了土方調配成本。反之，傳統ACA對于較大土方量選擇較遠的填方區域進行調配，導致土方調配成本增加。

4 討論

本文通過蟻群算法獲取農田微地形特征土方調配的可行解，并根據遺傳算法中的適應度函數、交叉操作和變異操作對解進行多次優化，獲取最優的農田微地形特征調配路徑。本文方法相較于傳統蟻群算法達到局部最優解的迭代次數較少，而且傳統蟻群算法經79次迭代后陷入局部最優求解循環。引入遺傳算法后，增加了優化次數，并在迭代232次時獲取全局最優解。未來通過神經網絡優化蟻群算法，以其減少迭代次數，提高工作效率。

試驗結果表明，基于遺傳—蟻群算法的土方調配總成本為215.52元，低于傳統蟻群算法224.77元的調配成本；然而，該方法調配距離為213.15 m，大于傳統蟻群算法的調配路徑191.94 m，仍需進一步通過優化算法降低調配距離。改進的蟻群算法避免了陷入局部最優求解循環，獲取全局最優解，有效降低土方調配費用，但忽視了土方調配總路徑。未來計劃將土方調配路徑作為第二目標函數，進行多目標函數優化，尋找到在路徑和調配總價兩個方面相較于傳統蟻群算法較優的解，進一步提高該方法在微地形特征土方調配中的優越性。

5 結論

基于高精度農田數字地形模型FDTM提取農田微地形特征，設計基準面高度獲取挖、填方量，規劃微地形特征最優土方調配路徑，為精準平整農田微地形特征提供數據支撐。

1） 根據高精度FDTM提取16個凸起特征和9個洼地特征，設置50 cm緩沖區域，確定各微地形特征的基準面高度，并利用逼近法分別確定挖、填方量為0.885 m3和0.884 m3。

2） 根據凸起特征及洼地特征的空間分布與挖填方量，建立土方調配節點，通過蟻群算法獲取可行解，利用遺傳算法中的適應度函數對解進行初步優化，并引入交叉操作和變異操作對解進行二次優化，獲取最優土方調配路徑。通過試驗分析，驗證本文方法與傳統蟻群算法相比，有效降低2.1%的調配成本。

參 考 文 獻

[ 1 ] 劉洋成， 耿端陽， 蘭玉彬， 等. 基于自動導航的農業裝備全覆蓋路徑規劃研究進展[J]. 中國農機化學報， 2020， 41（11）： 185-192.

Liu Yangcheng， Geng Duanyang， Lan Yubin， et al. Research progress of agricultural equipment full coverage path planning based on automatic navigation [J]. Journal of Chinese Agricultural Mechanization， 2020， 41（11）： 185-192.

[ 2 ] 黃琪， 劉友兆， 班春峰， 等. 基于數字高程模型和數學規劃的土地平整工程設計優化[J]. 農業工程學報， 2011， 27（11）： 313-318.

Huang Qi， Liu Youzhao， Ban Chunfeng， et al. Optimal design for land leveling project based on digital elevation model and mathematical programming [J]. Transactions of the Chinese Society of Agricultural Engineering， 2011， 27（11）： 313-318.

[ 3 ] Deng N， Li X， Su Y. Optimization of earthwork allocation path as vehicle route problem based on genetic algorithm [C]. E3S Web of Conferences. EDP Sciences， 2020， 165： 04057.

[ 4 ] 王仁超， 劉金飛， 李仕奇， 等. 基于螞蟻和粒子群算法的土石方調運優化方法研究[J]. 水利學報， 2006（11）： 1393-1397.

Wang Renchao， Liu Jinfei， Li Shiqi， et al. Study on earthwork allocation and transportation method based on ant algorithm and particle swarm optimizer [J]. Journal of Hydraulic Engineering， 2006（11）： 1393-1397.

[ 5 ] Cho S I， Lim J H， Lim S B， et al. A study on DEM?based automatic calculation of earthwork volume for BIM application [J]. Journal of the Korean Society of Surveying， Geodesy， Photogrammetry and Cartography， 2020， 38（2）： 131-140.

[ 6 ] Manthey B. Multi?criteria TSP： Min and max combined [C]. International Workshop on Approximation and Online Algorithms. Berlin， Heidelberg： Springer Berlin Heidelberg， 2009： 205-216.

[ 7 ] 郝琨， 張慧杰， 李志圣， 等. 基于改進避障策略和雙優化蟻群算法的機器人路徑規劃[J]. 農業機械學報， 2022， 53（8）： 303-312， 422.

Hao Kun， Zhang Huijie， Li Zhisheng， et al. Path planning of mobile robot based on improved obstacle avoidance strategy and double optimization ant colony algorithm [J]. Transaction of Chinese Society for Agricultural Machinery， 2022， 53（8）： 303-312， 422.

[ 8 ] Qin Y， Li Z， Ding J， et al. Automatic optimization model of transmission line based on GIS and genetic algorithm [J]. Array， 2022： 100266.

[ 9 ] 林孝騰， Mulowayi Mutombo Arcle， 梅方煒， 等. 基于遺傳算法的全光譜LED植物光源陣列優化研究[J]. 中國農機化學報， 2020， 41（8）： 163-169.

Lin Xiaoteng， Mulowayi Mutombo Arcle， Mei Fangwei， et al. Optimized research of full?spectrum LED plant light source array based on genetic algorithm [J]. Journal of Chinese Agricultural Mechanization， 2020， 41（8）： 163-169.

[10] 任彬， 白東， 謝虎， 等. 基于粗糙遺傳算法在打捆機齒輪箱故障診斷中的應用[J]. 中國農機化學報， 2021， 42（11）： 103-109.

Ren Bin， Bai Dong， Xie Hu， et al. Application of rough genetic algorithm in fault diagnosis of gearbox of bundling machine [J]. Journal of Chinese Agricultural Mechanization， 2021， 42（11）： 103-109.

[11] 吳琦， 詹宇， 于家旋， 等. 基于混合蟻群算法和變論域模糊控制的混肥系統設計[J]. 中國農機化學報， 2019， 40（7）： 146-150.

Wu Qi， Zhan Yu， Yu Jiaxuan， et al. Design of water and fertilizer mixing system based on hybrid ant colony algorithm and variable domain fuzzy control [J]. Journal of Chinese Agricultural Mechanization， 2019， 40（7）： 146-150.