滴灌輪灌分組優(yōu)化模型與算法

李 偉，陳偉能，田 敏，鄧紅濤，陳紅莉

·農(nóng)業(yè)水土工程·

滴灌輪灌分組優(yōu)化模型與算法

李 偉1,2，陳偉能1，田 敏3，鄧紅濤3，陳紅莉4

（1. 華南理工大學(xué)計算機科學(xué)與工程學(xué)院，廣州 510000；2. 石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，石河子 832000；3. 石河子大學(xué)機械電氣工程學(xué)院，石河子 832000；4. 新疆天業(yè)集團有限公司，石河子 832000）

傳統(tǒng)的輪灌組劃分計算方式效率較低且難以獲得較好方案。該研究首次采用智能算法來求解輪灌組劃分問題，依據(jù)《微灌工程技術(shù)標準》及輪灌組劃分原則，提出了基于流量均衡的數(shù)學(xué)模型及其約束條件。通過分析支管空間分布，確定了滴灌問題的鄰域特征，在半徑閾值范圍內(nèi)給出了最大限度查找關(guān)鍵路徑的鄰域搜索策略和不可行解修復(fù)算法，并采用傳統(tǒng)遺傳算法（Genetic Algorithm，GA）、貪心遺傳算法（Greedy-GA）、泰森多邊形遺傳算法（Voronoi-GA）和網(wǎng)格遺傳算法（Grid-GA）算法分別求解模型，探索適應(yīng)輪灌分組問題的初始化方法。對標準差、組內(nèi)路程、連通性和運行時間4項指標對比分析，結(jié)果表明：Grid-GA算法表現(xiàn)優(yōu)異，采用的鄰域策略可有效避免支管分布過于分散，有利于日常管理與維護。取半徑閾值280 m條件下，算法在300代左右達到收斂，最小標準差10.9 m3/h，組內(nèi)路程8 105.2 m，連通性指標25，與一種冒泡+貪心的近似算法相比最小標準差小59.1%。該研究對提高滴灌工程設(shè)計效率和促進輪灌工作制度有效運行有著重要研究意義。

模型；算法；網(wǎng)格法；滴灌；輪灌組；遺傳算法；智能優(yōu)化算法

0 引 言

滴灌系統(tǒng)利用專門的灌溉設(shè)備以間斷或連續(xù)的水滴或細流將水灌到部分土壤表面和作物根區(qū)，這種方式節(jié)水、節(jié)肥、增產(chǎn)，在干旱和半干旱地區(qū)被廣泛采用。由于勞動力成本等因素，國外的滴灌技術(shù)研究偏向自動化控制以及降低運營成本。如采用無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）或物聯(lián)網(wǎng)（Internet of Things，IoT）等技術(shù)將傳感器、氣象站和控制中心等互連來實現(xiàn)自動灌溉[1-2]。Roopaei等[3]提出將IoT和信息物理系統(tǒng)（Cyber-Physical Systems，CPS）相結(jié)合來解決灌溉問題。Moreno等[4]通過研究灌溉計劃與能源消耗的關(guān)系表明采用合適的灌溉方案可以減少能源消耗3.5%～24.9%。中國新疆從1996年開始從以色列引進滴灌技術(shù)，為了解決滴灌在大田作物低成本應(yīng)用的問題，新疆結(jié)合自身特點建立了一整套膜下滴灌技術(shù)[5]。截止2019年，全疆應(yīng)用滴灌規(guī)模已超過300萬hm2，占全國比重為60%左右。國內(nèi)學(xué)者從不同的角度對滴灌問題進行了研究，信息技術(shù)角度研究包括灌水器堵塞機理與優(yōu)化[6-7]、管網(wǎng)布置優(yōu)化[8]、精準滴灌系統(tǒng)[9]、滴灌智能控制[10]等；農(nóng)業(yè)角度研究包括精準施肥[11]、水肥一體化[12-13]等。但國內(nèi)外學(xué)者對輪灌分組問題卻鮮有研究，僅有國內(nèi)學(xué)者從使用角度提出了輪灌組劃分存在的問題[14-15]，但沒有提出模型和算法。

輪灌是為了降低工程成本所采用的一種灌溉方式。這種方式水量相對集中，管理簡便，適用于集中連片的規(guī)?；?jīng)營土地，是新疆滴灌工程主要應(yīng)用模式[16]。輪灌組是輪灌灌溉制度的核心，其劃分受作物種類、生長階段、水資源、電力供應(yīng)等因素影響。設(shè)計人員依據(jù)《微灌工程技術(shù)標準》（GB/T50485-2020，以下簡稱“標準”）計算時，大多基于人工經(jīng)驗和EXCEL推算。隨著工程規(guī)模越來越大，傳統(tǒng)設(shè)計方法不僅效率低，且很難得到合理的方案。當(dāng)外部因素變化時又無法及時調(diào)整，導(dǎo)致輪灌工作制度無法有效運行[14,17]，影響了滴灌設(shè)施的用水效率[18]。

在渠系研究中也存在類似輪灌分組問題[19-21]，這類問題多就渠系用水總量和作物生長關(guān)系開展研究[22]。如程帥等[23]選擇總配水與輪灌組之間引水持續(xù)時間差異值最小構(gòu)建渠系優(yōu)化配水模型。高偉增等[24]以渠道的輸水滲漏損失最小作為目標優(yōu)化輪灌組。這些研究表明輪灌分組問題是一個高維離散組合優(yōu)化問題[25-26]，智能算法在渠系輪灌分組問題上取得了較好效果，這些模型和算法雖然具有一定理論參考意義。但渠系輪灌組與滴灌輪灌組在空間分布、水力特性、灌溉模式、計算標準上都有本質(zhì)區(qū)別，渠系模型和算法并不能直接應(yīng)用在滴灌輪灌分組問題中。

綜上所述，滴灌輪灌分組是一個新興問題，具有明顯的地域特色和水力特征，可以在渠系研究的基礎(chǔ)上，開展輪灌組的模型和算法研究。針對傳統(tǒng)輪灌組劃分手工效率低的問題，本文首次引入智能算法求解輪灌組劃分問題，以流量標準差最小為優(yōu)化目標，采用混合遺傳算法優(yōu)化模型，并探索算法最有利的初始化方法和搜索策略。該研究旨在探索智能算法在輪灌組優(yōu)化問題上的可行性，為今后相關(guān)研究提供借鑒和參考，以期提高滴灌工程設(shè)計效率和保障輪灌工作制度有效運行。

1 輪灌分組模型建模

1.1 工程背景分析

本研究以新疆團場滴灌工程為研究案例，該工程地塊總面積約70 hm2，滴灌帶按照一管二行布置，滴頭流量1.8 m3/h，工作壓力0.1 MPa，輪灌組由若干支管組成，如圖1，假設(shè)1-1，1-2，1-3，2-1，2-2為一個輪灌組，其中，“-”前數(shù)字代表分干管，“-”后數(shù)字代表支管，整體構(gòu)成一個輪灌組。每個輪灌組運行時，其內(nèi)部支管上所有毛管全部開啟，一個輪灌組灌水完成后，開啟下一個輪灌組內(nèi)的支管及毛管，然后再關(guān)閉前一個輪灌組內(nèi)的支管。農(nóng)戶按照輪灌組支管順序逐步完成整個地塊灌溉，相比自動化滴灌，這種手工控制支管的輪灌模式勞動強度大，但是投資成本低，維護簡單，普及面積廣。為節(jié)約成本及管理方便，輪灌組劃分需要滿足《標準》中管網(wǎng)水力計算和流量均衡需求，避免因壓力不均衡導(dǎo)致管網(wǎng)水頭損失或破損。此外還須遵循的原則包括：1）輪灌組中各支管閥門要相對集中，有利于減輕農(nóng)戶勞動強度；2）組內(nèi)支管要按順序編組，便于農(nóng)戶管理與維護。

輪灌分組問題可以簡單描述為：將個支管分配到個輪灌組，在滿足約束條件下，尋找組內(nèi)合理的空間分布，從而優(yōu)化1個或多個性能指標。因此，可以將輪灌分組轉(zhuǎn)化為求解矩陣X的問題，即個支管在個輪灌組中的開閉狀態(tài)，分別由0和1表示。如式（1）矩陣中列表示支管編號={1,2,…,}，且每列只能開啟1次。行表示輪灌組編號={1,2,…,}，且每行中應(yīng)至少有1個支管處于開啟狀態(tài)。根據(jù)劃分原則，輪灌分組問題的實質(zhì)就是求解行間流量標準差最小，同時滿足行內(nèi)支管空間分布鄰近且按順序編號的矩陣X。

1.2 輪灌分組模型構(gòu)建

首先根據(jù)水源、土壤、作物等基礎(chǔ)數(shù)據(jù)及灌溉保證率、灌溉水利用系數(shù)、土壤濕潤比、濕潤層深等參數(shù)，分別計算灌水定額、灌水周期和單次灌水延續(xù)時間。式（1）～式（6）、式（15）～式（17）由《標準》規(guī)定。

m=0.1(max-min)/（2）

( m /I)（3）

=mSS/q（4）

式中m為設(shè)計灌水定額，mm；為土壤容重，g/cm3；為計劃濕潤層深度，m；為微灌設(shè)計土壤濕潤比，%；max、min為適宜土壤含水量上下限，占干土質(zhì)量的百分比，%；為灌水周期，d；I為設(shè)計耗水強度，mm/d；為灌溉水利用系數(shù)；為單次灌水延續(xù)時間，h；q為灌水器流量，m3/h；S為灌水器間距，m；S為毛管間距，m。

根據(jù)管網(wǎng)及水力系統(tǒng)壓力等要求，確定實際輪灌組數(shù)N

max=INT[/] （5）

N=n總q/且滿足N≤max（6）

式中max為最大輪灌組數(shù)；N為實際輪灌組數(shù)；為系統(tǒng)日工作時間，一般取18～22 h；為可供流量，m3/h；總為系統(tǒng)滴頭總數(shù)。

根據(jù)流量均衡要求，建立以各輪灌組流量標準差最小為目標的數(shù)學(xué)模型

式中()表示輪灌組流量標準差，m3/h；Q為第個支管設(shè)計流量，m3/h；F為第輪灌組流量和，m3/h；α表示各輪灌組流量平均值，m3/h。

約束條件：

1）0-1約束

V= 0,1 （10）

式中V表示支管在第輪灌組中狀態(tài)，由于支管閥門只有開和關(guān)兩種狀態(tài)，V＝0和1分別表示支管閥門關(guān)和開。

2）流量約束

式中max為輪灌組最大設(shè)計流量，m3/h，即任意輪灌組流量應(yīng)小于最大設(shè)計流量，大于設(shè)計流量80%：

3）流量差約束

Δ= max(F)-min(F)<（12）

式中F表示各輪灌組流量集合，m3/h；Δ為任意兩個輪灌組流量之差，m3/h；為流量差閾值，m3/h。

4）壓力差約束

Δmax()- min() <（13）

毛=1.2fLFQm2毛/D（15）

支=1.1fLFQm2支/D（16）

干=1.1fLFQm2干/D（17）

式中表示各輪灌組壓力集合，Δ表示任意輪灌組壓力之差應(yīng)小于一定閾值。毛、支、干分別代表毛管、支管和分干管揚程，m；為沿程水頭損失系數(shù)；毛、支、干分別代表毛管、支管和分干管管道流量，m3/h；為管長，m；F為多口系數(shù)；為管道內(nèi)徑，mm；2為流量指數(shù)；為管徑指數(shù)，因管材及局部損失等壓力計算結(jié)果相似，不計算在公式（14）內(nèi)。

2 基于鄰域搜索策略的混合遺傳算法

2.1 算法流程

將不同特點的算法混合使用，可以避免使用單一方法早熟和陷入局部最優(yōu)[27]。隨機方式初始化難以保證初始種群的質(zhì)量，容易產(chǎn)生不可行解。因此，分別采用傳統(tǒng)遺傳算法（Genetic Algorithm，GA）、貪心遺傳算法（Greedy-GA）、泰森多邊形遺傳算法（Voronoi-GA）[28]和網(wǎng)格遺傳算法（Grid-GA）求解模型，并探索最優(yōu)初始化方法。由于遺傳算法是一種元啟發(fā)式算法，其核心是隨機概率，理論上遺傳算法求解的結(jié)果是不確定的，不能保證全局最優(yōu)，因此，本文采用貪心策略在遺傳算法求解結(jié)果的基礎(chǔ)上進行二次優(yōu)化，一方面可以從全局角度二次調(diào)優(yōu)，另一方面也可以通過參數(shù)調(diào)整，在滿足流量標準差不變的條件下優(yōu)化其他指標，算法流程如圖2所示。

2.2 模型求解

遺傳算法求解涉及染色體編碼、初始化種群、目標函數(shù)計算、子代種群生成等。

1）染色體編碼：采用實數(shù)編碼的支管編碼方式，假設(shè)有個支管，從1到順序編號，每個支管代表1個遺傳編碼位，每個編碼位中的數(shù)字表示1個輪灌組編號，則染色體編碼表征為支管在第幾輪灌組開啟。如圖3數(shù)字“9”表示編號為4的支管在第9輪灌組中開啟。

2）種群初始化：分別采用隨機法、貪心算法（Greedy）、泰森多邊形（Voronoi）和網(wǎng)格法（Grid）構(gòu)造初始種群。其中前3種都是在全局解空間中隨機生成若干隨機點，不同點在于貪心算法以隨機點為基準，其策略為通過距離鄰近策略遍歷支管來構(gòu)建初始種群，直至遍歷完所有支管為止。泰森多邊形法通過隨機點先分割為泰森多邊形，再將多邊形區(qū)域內(nèi)支管組成初始種群。網(wǎng)格法則是將解空間均分為若干區(qū)域，在區(qū)域內(nèi)生成隨機點，再以鄰近策略遍歷隨機點附近支管來構(gòu)建初始種群。

3）鄰域搜索策略：鄰域結(jié)構(gòu)體現(xiàn)著問題本身特征信息的利用。對輪灌分組問題而言，支管空間分布具有重要的結(jié)構(gòu)特征。如圖1，1-1和1-2具有連通性，是一條關(guān)鍵路徑。而2-4和3-5則不是。搜索策略關(guān)鍵步驟為：

①根據(jù)輪灌組數(shù)，支管數(shù)，建立支管鄰接矩陣[,]。使用Warshall算法[29]生成支管可達矩陣[,]，計算每個支管的關(guān)鍵路徑集{1,2,…,A-1,A}。

②將編碼轉(zhuǎn)換為矩陣X形式，基于可達矩陣[,]生成各支管關(guān)鍵矩陣和非關(guān)鍵矩陣*。

③計算臨時路徑。在半徑閾值范圍內(nèi)，計算任意支管O可選路徑集為Tí{1,2,…,A-1,A}，再分別計算T在第輪灌組的集合，累加并減去得到臨時路徑集合Temp，并依據(jù)可達性排序。

④計算比較集合。依據(jù)標準差指標，依次將非關(guān)鍵矩陣*各輪灌組中支管分別與TempM比較。

⑤更新矩陣。選擇可行解，交換并更新關(guān)鍵矩陣[,]，并與剩余*合并。

4）子代種群的生成：包括交叉、變異和選擇機制。選擇機制采用競標賽和精英保留策略，有利于加快種群整體收斂速度。為增加搜索空間范圍，交叉、變異均采用均勻交叉策略，即從編碼第一位開始以一定概率交叉或變異，直至編碼最后1位。交叉和變異過程產(chǎn)生的不可行解均通過修復(fù)算法修復(fù)。根據(jù)編碼規(guī)則，不可行解主要包括兩種情況，一種是子代生成導(dǎo)致輪灌組為空，即某一輪灌組中沒有支管開啟；另一種是子代生成中支管分布過于分散，從而影響算法性能。針對這兩種情況，修復(fù)算法的核心思想是將變異交叉控制在半徑閾值范圍內(nèi)，首先避免支管分布過于分散，其次通過鄰近搜索的方法，采用輪盤賭策略來選擇輪灌組內(nèi)支管較少的組作為修復(fù)解，以此避免輪灌組為空的問題。修復(fù)算法關(guān)鍵步驟為：

①對子代種群生成的編碼位進行驗證，判斷其是否為不可行解，判斷依據(jù)是編碼位半徑閾值范圍內(nèi)是否有相同輪灌組編號，如果沒有則表示需要修復(fù)。

②計算當(dāng)前編碼位鄰近支管集合，并存入集合MatrixPool={1,2, …,LN }，LN為支管編號，鄰近范圍由半徑閾值參數(shù)設(shè)置。

③計算數(shù)組MatrixPool中支管所在輪灌組編號，并將編號順序存入集合Group={1,2, …,LM }，LM為輪灌組數(shù)量。

④計算數(shù)組Group中每個輪灌組包含的支管數(shù)量，得到集合numberGroup={1,2,…,LS }，LS為支管數(shù)量。

⑤計算集合numberGroup中每個元素的倒數(shù)并歸一化，采用輪盤賭策略選擇數(shù)組中的元素，數(shù)量越少的數(shù)組元素有較大的幾率被選擇為修復(fù)解。如果輪盤賭策略選擇的編碼存在輪灌組為空的情況，則直接將最小的數(shù)組元素作為當(dāng)前編碼位的修復(fù)解。

2.3 二次優(yōu)化

基于可達矩陣[,]設(shè)計連通性指標，計算公式為

式中為連通度，通過各輪灌組內(nèi)支管連通可達數(shù)量的累計和計算得到。連通度越大表示組內(nèi)支管互連度越高，越趨于集中，連通度越小則表示組內(nèi)支管越趨于分散。在上述遺傳算法求解結(jié)果基礎(chǔ)上，采用貪心算法進行二次調(diào)優(yōu)，貪心策略為采用鄰近策略搜索半徑閾值范圍內(nèi)支管，以流量標準差為基準優(yōu)化連通度指標，替換并更新遺傳算法求解的結(jié)果。

3 結(jié)果與分析

3.1 參數(shù)計算與設(shè)置

根據(jù)案例數(shù)據(jù)計算工程參數(shù)及支管數(shù)據(jù)，見表1和表2。以工程左下角第1個支管為原始起點坐標，則表2中支管1-1坐標為（0，0）。由于案例滴灌帶采用一管二行布置，設(shè)同一分干管上的相鄰支管間距為1 m，則支管1-2坐標為（1，0），其余支管坐標按照距離依次計算得出。由于支管數(shù)量多且編碼維數(shù)較高，經(jīng)驗證，設(shè)種群數(shù)p=200，迭代次數(shù)Iter=500，交叉概率0.09，變異概率0.01，半徑閾值280 m。

3.2 算法分析

采用標準差、組內(nèi)路程、連通性和運行時間4項指標對比分析。其中，標準差由公式（7）定義，組內(nèi)路程指輪灌組內(nèi)支管距離和，由于支管是按編號從小到大排列的，這里組內(nèi)路程不是最優(yōu)路徑，是按照支管排列序列的距離和。連通性按照公式（18）定義方法計算。運行時間指算法求解模型一次所花費時間。將基本參數(shù)分別輸入GA、Greedy-GA、Voronoi-GA和Grid-GA算法，每個算法運行50次。

表1 滴灌工程設(shè)計參數(shù)

表3顯示，初始種群的質(zhì)量對算法的求解質(zhì)量具有重要的影響。與傳統(tǒng)GA相比，Greedy-GA、Voronoi-GA和Grid-GA混合算法平均標準差均小于20 m3/h，滿足流量均衡。其中，Grid-GA最小標準差為10.9 m3/h，分別比GA、Greedy-GA和Voronoi-GA小71.6%、13.1%和31.1%，均值標準差為16.3 m3/h，分別比其他算法少68.8%、6.3%和12.3%，最優(yōu)與最差擺動幅度最小。組內(nèi)路程均值為8 105.2 m，分別少于其他算法23.9%、4.1%和12.2%。連通性均值為25，分別比其他算法高177.7%、13.6%和56.2%。Greedy-GA與Grid-GA結(jié)果最接近，Voronoi-GA在混合算法中表現(xiàn)最差，主要原因是當(dāng)隨機點分布均勻時，Greed與Grid初始解分配存在一定相似性，而當(dāng)隨機點不均勻時，Greed方法種群競爭激烈導(dǎo)致支管分布過于離散，影響求解質(zhì)量。Voronoi是一種圖像分割算法，其與分割區(qū)域大小有關(guān)，缺乏支管間邏輯關(guān)系，初始解的隨機性影響了空間區(qū)域穩(wěn)定性，存在大量不可行解，導(dǎo)致算法迭代和求解質(zhì)量。GA算法不需要大量計算鄰近矩陣，所以運行時間最短，而其他3種混合算法搜索策略相似，運行時間接近。綜合顯示：Grid-GA算法表現(xiàn)優(yōu)異，說明種群初始化分布均勻有利于輪灌分組問題尋優(yōu)，而初始解構(gòu)造的隨機性可能導(dǎo)致支管分布過于集中或離散，加劇了種群資源競爭，不利于結(jié)果尋優(yōu)。

圖4中3種混合算法均采用了修復(fù)算法，收斂下降趨勢類似，沒有出現(xiàn)劇烈波動，穩(wěn)定性好。在300代左右均向最優(yōu)解收斂。Grid-GA收斂曲線的起點優(yōu)于其他隨機分布算法，收斂速度更快。Greedy-GA和Voronoi-GA初始點具有較大偶然性，其中，Greedy-GA初始隨機點過于集中或離散會導(dǎo)致各種群競爭過于激烈，制約搜索空間展開，影響初始解質(zhì)量。Voronoi-GA圖像分割會產(chǎn)生不可行解，初始種群具有不確定性，影響了迭代過程搜索效率。GA全局隨機方式會生成大量不可行解，收斂慢，難以找到最優(yōu)解。

表2 支管基礎(chǔ)數(shù)據(jù)

表3 不同輪灌分組算法比較

半徑閾值一定程度上代表算法搜索空間，是鄰域搜索和修復(fù)算法重要參數(shù)。如圖5所示，半徑閾值在100～300 m區(qū)間時，隨著閾值變大增加了搜索空間，標準差呈快速下降趨勢。從半徑閾值450 m左右，標準差反而有一定程度上浮，原因是搜索空間變大增加了不可行解數(shù)量，選擇、交叉的搜索尋優(yōu)功能減弱，影響了求解結(jié)果。圖6中，半徑閾值與連通性指標總體呈下降趨勢，3種混合算法總體偏差為19%～35%之間，偏差幅度大。表明在標準差約束下，空間搜索范圍增大會降低組內(nèi)支管連通性，即組內(nèi)支管空間分布反而變得分散。圖7為半徑閾值與組內(nèi)路程關(guān)系，路程總體偏差為19%～38%之間，幅度較大。表明搜索范圍對組內(nèi)空間分布影響較大，組內(nèi)支管越分散，路程越長。Grid-GA與Greedy-GA均通過鄰近策略構(gòu)建支管邏輯關(guān)系，組內(nèi)路程相對接近，而Voronoi-GA空間分割有較大隨機性導(dǎo)致路程變化幅度大。

半徑閾值參數(shù)的設(shè)定可以避免輪灌組內(nèi)支點過于分散，有利于農(nóng)民日常管理與維護，從圖5、圖6和圖 7可以看出，半徑閾值參數(shù)與算法性能密切相關(guān)，其中半徑閾值與標準差和連通性總體表現(xiàn)為負相關(guān)，與路程呈正相關(guān)。因此，半徑閾值可以作為算法性能和用戶需求的關(guān)鍵指標，也是滴灌工程經(jīng)濟性和便利性的關(guān)鍵參數(shù)。

3.3 輪灌組優(yōu)化結(jié)果

本案例手工計算標準差為17.4 m3/h，雖然滿足標準中的流量約束，但是花費時間較長。表4為采用Grid-GA算法求解模型的結(jié)果，標準差10.9 m3/h，輪灌組流量均值260.06 m3/h，總路程7 342.6 m，平均路程386.4 m，連通性為22。與其他算法相比，Grid-GA表現(xiàn)穩(wěn)定，滿足約束和工程需求，避免了多維問題的維數(shù)災(zāi)問題，對求解輪灌組優(yōu)化問題有很高的性能。

輪灌分組問題是一個組合優(yōu)化問題，其目的是尋找離散數(shù)據(jù)的最優(yōu)分組、編排和次序等。求解這類問題常用算法包括元啟發(fā)式算法和近似算法，其中近似算法的本質(zhì)通常是貪心算法。因此，針對輪灌組問題特征，設(shè)計一種基于冒泡+貪心策略的近似算法，并與Grid-GA進行對比。冒泡+貪心算法步驟：首先采用冒泡法將支管流量從大到小排序，貪心策略為從流量最大的支管開始分配到不同的輪灌組中，然后分別計算待分配的支管分配到某輪灌組中時的流量標準差，以輪灌組標準差最小為最佳劃分方案，直至遍歷計算完所有支管為止。

由表5對比分析可以看出，冒泡+貪心算法最小標準差為26.8 m3/h。Grid-GA最小標準差為10.9 m3/h，Grid-GA比冒泡+貪心算法最小標準差少59.1%，組內(nèi)路程均值小29.9%，連通度則高257.1%，主要原因是輪灌分組問題的組合變量是離散分布的，傳統(tǒng)優(yōu)化方法求解這類問題會帶來所謂的“組合爆炸”。另外，冒泡+貪心算法是基于流量大小來選擇支管，從空間上表現(xiàn)出支管分布過于分散，導(dǎo)致組內(nèi)路程和連通性指標較差，難以獲得最優(yōu)解。冒泡+貪心算法計算較為簡單，運行時間只需要8.3 s，但是計算結(jié)果無法直接使用，需要再次對求解結(jié)果進行手工調(diào)優(yōu)，調(diào)優(yōu)過程需要依據(jù)工程人員設(shè)計經(jīng)驗，可能需要更多的時間。

表4 基于網(wǎng)格-遺傳混合算法的最優(yōu)輪灌組求解結(jié)果

表5 Grid-GA與冒泡+貪心算法比較

為了驗證算法對輪灌分組問題的普適性，選取新疆生產(chǎn)建設(shè)兵團第三師45團的3組工程案例進行驗證，3組案例支管規(guī)模分別為70、50和40個，根據(jù)案例工程區(qū)域大小分別設(shè)置半徑閾值為300、250和220 m，其他參數(shù)如種群數(shù)迭代次數(shù)、交叉概率和變異概率與前述算法設(shè)置相同。

從表6中可以看出，3組案例在工程面積、支管規(guī)模及輪灌組數(shù)均有區(qū)別，案例1、案例2與案例3的工程面積依次從大到小，案例1與案例3輪灌組數(shù)相差1倍，3組案例可以代表不同的滴灌工程應(yīng)用場景，具有一定普適性。試驗結(jié)果中3組案例求解時間均小于80 s，可極大提升工程設(shè)計計算效率，求解的最小標準差分別為13.3、12.1和6.9 m3/h，均滿足流量約束條件，符合工程實際需求，驗證了算法的有效性。研究初步表明支管數(shù)與運行時間指標呈正相關(guān)，而標準差、組內(nèi)路程和連通性指標與各自案例特征有關(guān)，與支管數(shù)、輪灌組數(shù)和面積等并無直接關(guān)聯(lián)，這也表明不同案例的輪灌分組有一定的特殊性。由于驗證過程中采用相同的優(yōu)化參數(shù)，在實際優(yōu)化中還需要根據(jù)案例情況對參數(shù)進行適當(dāng)調(diào)整，包括半徑閾值、種群數(shù)和迭代次數(shù)等。

表6 3組案例的算法普適性驗證

4 討 論

1）傳統(tǒng)輪灌分組主要采用EXCEL推算的方式來劃分，其結(jié)果優(yōu)劣取決于工程規(guī)模和設(shè)計人員經(jīng)驗，也缺乏公開的算法和數(shù)據(jù)集。隨著大規(guī)模滴灌工程的普及，傳統(tǒng)手工方式難以適應(yīng)工程計算的需求，切實需要改進現(xiàn)有的計算方法。而人工智能算法被廣泛用來解決一些工程實際問題，具有廣泛的適用性和應(yīng)用價值，本文的Grid-GA就是智能算法中的一種元啟發(fā)式算法。

2）需要說明的是：本文分別在種群初始化（第2.2節(jié)）、二次優(yōu)化（第2.3節(jié)）和近似算法（第4節(jié)）中采用了貪心算法。貪心算法（又稱貪婪算法）是一種對某些求最優(yōu)解問題的簡單但迅速的優(yōu)化技術(shù)，并沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇，需要根據(jù)先驗知識來決定算法流程和步驟。因此，文中雖然3次提及貪心算法，但是其算法和步驟均有所差別。

3）表3與圖5研究表明初始種群分布特征以及半徑閾值大小對算法性能有較大影響，可以繼續(xù)從種群初始化策略以及研究自適應(yīng)閾值的角度來提高算法性能。同時，雖然支管流量有其固定的水力計算方法，但是可以針對支管流量進行敏感度分析，研究支管流量對算法的影響程度，以便為今后算法改進提供決策支持。另外，雖然遺傳算法具有較好的全局搜索能力，但是局部搜索能力較弱，而半徑閾值參數(shù)更限制了遺傳算法的全局搜索能力，為此，可以重點研究將爬山法、模擬退火、變鄰域等局部搜索方法與遺傳算法結(jié)合，充分發(fā)揮兩者在全局搜索和局部搜索的優(yōu)勢來共同求解輪灌組，這也是算法下一步需要重點研究和探索的方向。

5 結(jié) 論

本文首次將智能算法運用到滴灌輪灌組劃分問題，從流量均衡和劃分原則出發(fā)，建立了流量標準差最小為目標的優(yōu)化模型和約束。分別采用遺傳算法（Genetic Algorithm，GA）、貪心-遺傳算法（Greedy-GA）、泰森-遺傳算法（Voronoi-GA）和網(wǎng)格-遺傳算法（Grid-GA）求解模型。其中Grid-GA相比其他算法表現(xiàn)優(yōu)異，在最小標準差、標準差均值和組內(nèi)路程均值指標上分別比其他算法小13.1%～71.6%、6.3%～68.8%和4.1%～23.9%，連通性均值比其他算法高13.6%～177.7%，表明初始化種群分布均勻，有利于求解輪灌組問題。混合算法中鄰域搜索策略可以提高算法收斂速度，修復(fù)算法則有利于避免支管分布過于離散，便于農(nóng)戶日常管理與維護。Grid-GA與冒泡+貪心的近似算法比較中最小標準差小59.1%，也驗證了元啟發(fā)算法在輪灌組劃分問題上的潛力。最后分別在3組不同支管規(guī)模的案例上進行測試，驗證了模型和算法的有效性，表明該研究具有較好的研究和應(yīng)用價值。

[1] Roy S K, Roy A, Misra S, et al. AID: A prototype for agricultural intrusion detection using wireless sensor network[C]//2015 IEEE International Conference on Communications (ICC). Piscataway: IEEE, 2015.

[2] Kumar A, Surendra A, Mohan H, et al. Internet of things based smart irrigation using regression algorithm[C]//2017 International Conference on Intelligent Computing, Instrumentation and Control Technologies (ICICICT). Amsterdam: Elsevier, 2017.

[3] Roopaei M, Rad P, Choo K. Cloud of things in smart agriculture: Intelligent irrigation monitoring by thermal imaging[J]. IEEE Cloud Computing, 2017, 4(1): 10-15.

[4] 馬富裕，周治國，鄭重，等. 新疆棉花膜下滴灌技術(shù)的發(fā)展與完善[J]. 干旱地區(qū)農(nóng)業(yè)研究，2004，22(3)：202-208.

Ma Fuyu, Zhou Zhiguo, Zheng Zhong, et al. The development and improvement of drip irrigation under plastic film on cotton[J]. Agricultural Research in the Arid Areas, 2004, 22(3): 202-208. (in Chinese with English abstract)

[5] Jiménez-Bello M A, Campos J C A, Manzano-Juárez J, et al. Methodology for flushing pressurised irrigation networks for fertigation and operation maintenance purposes[J]. Irrigation Science, 2021, 39(3): 375-384.

[6] Moreno M A, Córcoles J I, Tarjuelo J M, et al. Energy efficiency of pressurised irrigation networks managed on-demand and under a rotation schedule[J]. Biosystems Engineering, 2010, 107(4): 349-363.

[7] Zhang Z, Li L, Yang P, et al. Effects of water salinity on emitter clogging in surface drip irrigation systems[J]. Irrigation Science, 2021, 39(2): 209-222.

[8] 王新端，白丹，郭霖，等. 改進的滴灌雙向流道結(jié)構(gòu)參數(shù)對水力性能影響[J]. 排灌機械工程學(xué)報，2016，34(12)：1093-1098.

Wang Xinduan, Bai Dan, Guo Lin, et al. Influence of structural parameters of improved bidirectional flow channel on hydraulic performance in drip irrigation[J], Journal of Drainage and Irrigation Machinery Engineering, 2016, 34(12): 1093-1098. (in Chinese with English abstract)

[9] 田敏. 基于物聯(lián)網(wǎng)技術(shù)的作物養(yǎng)分信息快速獲取與精準施肥智能控制系統(tǒng)研究[D]. 石河子：石河子大學(xué)，2018.

Tian Min. Research on Crop Nutrient Information Acquisition and Precision Fertilization Intelligent Control System Based on Internet of Things[D]. Shihezi: Shihezi University, 2018. (in Chinese with English abstract)

[10] Shi J C, Wu X, Zhang M, et al. Numerically scheduling plant water deficit index-based smart irrigation to optimize crop yield and water use efficiency[J]. Agricultural Water Management, 2021, 248: 106774.

[11] 王建陽. 河套灌區(qū)不同灌溉與覆膜方式下土壤水鹽離子動態(tài)變化研究[D]. 呼和浩特：內(nèi)蒙古農(nóng)業(yè)大學(xué)，2019.

Wang Jian Yang. Study on Dynamic Changes of Soil Water and Salt Ions under Different Irrigation and Film Mulching Methods in Hetao Irrigation Area[D]. Hohhot: Inner Mongolia Agricultural University, 2019. (in Chinese with English abstract)

[12] Liu R, Yang Y, Wang Y S, et al. Alternate partial root-zone drip irrigation with nitrogen fertigation promoted tomato growth, water and fertilizer-nitrogen use efficiency[J]. Agricultural Water Management, 2020, 233: 106049.

[13] 顧巍，葉志偉，嚴盟，等. 一種多目標水肥一體化系統(tǒng)輪灌組劃分方法：中國專利，109496520A[P]. 2019-03-22.

[14] 馬章進. 新疆大田滴灌工程運行中存在的問題及解決建議[J]. 水利技術(shù)監(jiān)督，2018, 26(5)：79-80.

Ma Zhangjin. Problems and suggestions in operation of drip irrigation project in xinjiang field[J]. Techenical Supervision in Water Resources, 2018, 26(5): 79-80. (in Chinese with English abstract)

[15] 楊光龍，洪亮. 支管輪灌滴灌模式在大田應(yīng)用中的優(yōu)點淺述[J]. 農(nóng)業(yè)科技與信息，2008, 25(10)：42.

Yang Guanglong, Hong Liang. The advantages of branch-wheel drip irrigation in field application are briefly discussed[J]. Agricultural Science and Technology and Information, 2008，25(10): 42. (in Chinese with English abstract)

[16] 李萌. 南疆膜下滴灌棉花灌溉和施肥調(diào)控效應(yīng)及生長模擬研究[D]. 楊凌：西北農(nóng)林科技大學(xué)，2020.

Li Meng. Study on Effect of Irrigation and Fertilization Regulation and Simulation of Cotton Growth under Film-Mulched Drip Irrigation in Southern Xinjiang[D]. Yangling: Northwest A&F University, 2020. (in Chinese with English abstract)

[17] 程毅強. 關(guān)于優(yōu)化滴灌輪灌運行方式的探討[J]. 中國水運(下半月)，2013，13(9)：232-233.

[18] Blanke A, Rozelle S, Lohmar B, et al. Water saving technology and saving water in China[J]. Agricultural water management, 2007, 87(2): 139-150.

[19] Masseroni D, Castagna A, Gandolfi C. Evaluating the performances of a flexible mechanism of water diversion: Application on a northern italy gravity-driven irrigation channel[J]. Irrigation Science, 2021, 39(3): 363-373.

[20] Pallavan P N I, Abhirame V S, Prabha V S. Characterization of Water Dynamics and Modelling of an Open Channel Irrigation System[C]//IOP Conference Series: Materials Science and Engineering. London: IOP Publishing, 2020.

[21] Ficchì A, Raso L, Dorchies D, et al. Optimal operation of the multireservoir system in the Seine river basin using deterministic and ensemble forecasts[J]. Journal of Water Resources Planning and Management, 2016, 142(1): 05015005.

[22] 馬孝義，于國豐，李安強，等. 渠系配水優(yōu)化編組通用化軟件的研發(fā)與應(yīng)用[J]. 農(nóng)業(yè)工程學(xué)報，2005，21(1)：119-123.

Ma Xiaoyi, Yu Guofeng, Li Anqiang, et al. Development and application of universal software for optimal water distribution of canal system[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2005，21(1): 119-123. (in Chinese with English abstract)

[23] 程帥. 基于智能算法與GIS的灌溉水資源多目標優(yōu)化配置[D]. 長春：中國科學(xué)院研究生院（東北地理與農(nóng)業(yè)生態(tài)研究所），2016.

Cheng Shuai. Multi-objective Optimal Allocation of Irrigation Water Resources Based on Intelligent Algorithm and GIS[D]. Changchun: Chinese Academy of Sciences (Northeast Institute of Geography and Agroecology), 2016. (in Chinese with English abstract)

[24] 高偉增，趙明富，汪志農(nóng)，等. 渠道輪灌配水優(yōu)化模型與復(fù)合智能算法求解[J]. 干旱地區(qū)農(nóng)業(yè)研究，2011，29(6)：38-42.

Gao Weizeng, Zhao Mingfu, Wang Zhinong. Optimization model of canal water distribution with GA and FS in rotation irrigation[J]. Agricultural Research in the Arid Areas, 2011, 29(6): 38-42. (in Chinese with English abstract)

[25] Zhang X, Zhang F, Zhang Y, et al. Water saving irrigation decision-making method based on big data fusion[J]. International Journal of Performability Engineering, 2019, 15(11): 2916-2926.

[26] Ebtehaj I, Bonakdari H, Gharabaghi B. Development of more accurate discharge coefficient prediction equations for rectangular side weirs using adaptive neuro-fuzzy inference system and generalized group method of data handling[J]. Measurement, 2018, 116: 473-482.

[27] Deng W, Xu J J, Song Y J, et al. Differential evolution algorithm with wavelet basis function and optimal mutation strategy for complex optimization problem[J]. Applied Soft Computing, 2021, 100: 106724.

[28] Kim J, Son H I. A voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard[J]. IEEE Access, 2020, 8: 20676-20686.

[29] Hougardy S. The Floyd-Warshall algorithm on graphs with negative cycles[J]. Information Processing Letters, 2010, 110(8): 279-281.

Optimization model and algorithm of rotation irrigation group for drip irrigation

Li Wei1,2, Chen Weineng1, Tian Min3, Deng Hongtao3, Chen Hongli4

(1.,,510000,;2.,,832000,;3.,,832000,;4.,832000,)

A rotation irrigation is normally implemented in water-shortage regions, such as Xinjiang area of western China with widespread drip irrigation. Nevertheless, the conventional rotation irrigation group is generally divided into the fixed districts in the manual calculation. A better solution is thus highly demanding in this inefficient calculation. The rotation irrigation group is also representing the prominent regional and hydraulic characteristics in recent years. Therefore, it is necessary to clarify how to divide the rotation irrigation group in practice. Furthermore, the operation of the irrigation system needs to gradually complete the whole plot irrigation under the turn-on and turn-off valve sequence of several branch pipes in a rotation irrigation group. Correspondingly, there is a relatively high labor intensity in the operational mode, but with low investment cost, simple maintenance, and wide popularization, compared with the automatic operation of drip irrigation. In this study, a hybrid mathematical model was proposed to explore a better solution using the flow balance and structural constraints in the technical standards and division principles. Neighborhood characteristics were determined from the spatial distribution of branch pipes in the rotation irrigation group. The neighborhood search strategy and the repair of infeasible solution were given in the radius threshold range, further to find the critical path of the maximum extent. Four algorithms were selected to solve the model separately, including the Genetic Algorithm (GA), Greedy-GA, Tyson polygon-GA (Voronoi-GA), and Grid GA. The GA adopted the branch pipe model of actual number coding. The chromosome coding indicated that the branch pipe was opened in that group. The initial population was constructed using the Random, Greedy, Voronoi polygon, and Grid. The spatial distribution of branch pipe was applied in the neighborhood search strategy, further to serve as the structural feature in the rotation irrigation group. A uniform crossover strategy was adopted for the crossover and mutation of the offspring population. A competitive and elite retention strategy was adopted for the selection mechanism. Furthermore, the neighborhood structure represented the use of characteristic information. In the case of the rotation irrigation group, the spatial distribution of branch pipes presented critical structural characteristics. The specific search procedure was: first to establish the adjacency matrix of branch pipe, then to generate the reachable matrix using the Warshall, finally to calculate the critical path set for each valve, thereby converting the code. In a matrix form, the fundamental and non-key matrix was generated using a reachable matrix. Then the temporary path set was calculated and sorted to compare the valves in the non-critical matrix row for the standard deviation index. Feasible solutions were selected to update the matrix using four indicators from standard deviation, path length, connectivity, and running time. Furthermore, an optimal combination was achieved, where the mean flow rate in the rotation irrigation group was 260.06 m3/h, the standard deviation was 10.9 m3/h, the path length was 7 342.6 m, the mean path length was 8 105.2m, the mean path length within the group was 386.4 m, and the mean connectivity was 22. The neighborhood search strategy of the critical path was adopted to balance the distribution of branch pipes under the condition of objective function, suitable for daily management and maintenance. The Grid-GA and repair presented an excellent performance on the rotation operating group in a grip irrigation, particularly without the dimensional disaster in the multi-dimensional combination. Consequently, the hybrid optimal model and algorithm here can meet the hydraulic calculation and engineering requirements in modern agriculture.

models; algorithms; grid method; drip irrigation; rotation irrigation group; genetic algorithm; intelligent optimization algorithm

10.11975/j.issn.1002-6819.2021.10.009

S274.1

A

1002-6819(2021)-10-0073-09

李偉，陳偉能，田敏，等. 滴灌輪灌分組優(yōu)化模型與算法[J]. 農(nóng)業(yè)工程學(xué)報，2021，37(10)：73-81.doi：10.11975/j.issn.1002-6819.2021.10.009 http://www.tcsae.org

Li Wei, Chen Weineng, Tian Min, et al. Optimization model and algorithm of rotation irrigation group for drip irrigation[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2021, 37(10): 73-81. (in Chinese with English abstract) doi：10.11975/j.issn.1002-6819.2021.10.009 http://www.tcsae.org

2021-03-21

2021-04-15

國家自然科學(xué)基金資助項目（61962053，61976093）

李偉，博士生，副教授，研究方向為群體智能與進化算法在農(nóng)業(yè)工程中的應(yīng)用。Email：lw200@qq.com

陳偉能，博士，教授，博士生導(dǎo)師，研究方向為群體智能與進化算法。Email：cschenwn@scut.edu.cn