基于遺傳算法的農業機械調配研究

劉 麗，劉 野，王新利

(黑龍江八一農墾大學 工程學院，黑龍江 大慶 163319)

0 引言

農業機械化程度是衡量現代農業發展水平的重要標志。近年來，現代科技對農業的引領作用加速，我國農機裝備水平和農業機械化水平均明顯提升。與發達國家相比，我國農業械機化總體水平仍然偏低，地區間發展不平衡、部分地區農機閑置問題非常突出。2016年，黑龍江省農業機械化水平達95%，黑龍江墾區農業機械化率已近100%，且農業裝備先進，但由于氣候條件限制，這里每年11月至來年的4月近半年的時間大型進口農業機械處于閑置狀態。由于農業生產具有較強的時效性和連貫性，對于大范圍的農業生產作業，需要對農機資源進行合理配置和有效調度，以按時完成農業生產任務，提高農機利用率，避免農作物損失和農機資源浪費，最終提高農戶、機手和農機組織的收益[1]。近年來，黑龍江墾區充分利用農機資源實行跨區作業，大大提高了農機利用率，但如何調配農機以縮短作業時間并降低作業成本，發揮現代大型農機對提高農業生產效率的作用，推進現代農業發展，越來越成為重要的研究課題。

從本質上講，農業機械調配是一種排列組合的問題，在問題確定時，必定會存在問題的最優解。然而，實際生產中的問題規模往往都比較大，排列組合的可能性呈指數化增長，在人類現有的計算能力下，只能精確求解很小規模的問題，遠遠不能滿足實際的生產需求。退而求其次，學術界提出了啟發式算法，這類算法基于直觀或經驗構造，在可接受的計算資源消耗下，給出待解決組合優化問題實例的一個可行解。雖然該可行解與最優解的偏離程度難以預計，卻往往可以在實際的問題中證明可行解的有效性。

作為現代啟發式算法的代表之一，遺傳算法(Genetic Algorithm，簡稱GA)是基于適者生存的一種高度并行、隨機和自適應的優化算法，通過模擬“染色體”的進化，最終得到最適應環境的個體，即問題的滿意解。

1 遺傳算法概述

遺傳算法[2]是由美國Michigan大學的Holland教授于1975年首先提出的，源于達爾文的進化論、孟德爾的群體遺傳學說和魏茨曼的物種選擇學說，是一種基于自然選擇和基因遺傳學原理的隨機并行搜索算法和尋求全局最優解而不需要任何初始化信息的高效優化方法[3]。遺傳算法將目標問題看作進化環境，將目標問題的解集當作環境中的生物個體，通過適當的編碼組合用解來表達個體，解答優劣度代表著個體對生存環境的適應程度，適應度越高，個體存活率越高。算法借此將自然界中的優勝劣汰引入到具體的問題中，采取適當的策略來模擬生物進化中的競爭、繁殖、變異和選擇，以引導問題的解逐步逼近最優解。傳統優化算法通常以梯度信息接近最優點，容易陷入局部最優而停止搜索；遺傳算法則通過全局尋優的方式，提高了找到最優解的可能性。本質上，遺傳算法是一種計算機模擬方法，具有適用面廣、多點搜索、魯棒性好、自適應強及并行性高的特點，是一種有著自適應能力的搜索優化方法，在函數優化、圖像處理、系統辨識、自動控制、經濟預測和工程優化等領域得到了廣泛的應用[4]。

2 建立農業機械調配優化問題模型

2.1 農業機械調配優化問題的描述

在確定數目及位置的農機調配站中，派出確定數目的某項單一功能農業機械，完成指定作業區域內的單一目標作業。農機站適合指定作業需求的機型僅有一種；每塊農田的待作業面積確定且已知，每輛農機可以依次對多塊農田實施作業，且對每塊農田都通過一次作業即可完成；農機隸屬于特定的調配站，作業完成后必須回到出發站。解答問題需要規劃所有農機的作業路線，使得農機在整個作業過程中滿足以下優化目標：每塊農田都得以被實施作業；整個作業的農機運行路線最短；整個作業過程的時間最短。簡而言之，農機調度即是要為所有參與作業的農機選擇適當的作業路徑，從而生成從各農機站到各農田作業點之間的調度方案，以達到使用最少的農機、最短的作業路徑及最短的作業時間來為所有農田實施作業的目標。

2.2 模型假設

1)農機調配站的位置、各農田的位置和面積及農機單日作業能力均確定且已知；

2)一塊農田僅由一臺農機來實施作業；

3)單臺農機的作業能力恰好可以滿足單塊農田要求；

4)有多個農機調配站，各農機調配站中針對特定農機作業需求只配有一種車型；

5)在一個調度方案中，每輛農機僅僅被分配一次作業路線，該農機從其隸屬的農機調配站出發，按指定順序對路徑上的農田依次實施作業之后，返回到其出發的農機調配站；

6)在一個調度方案中，每輛農機至少可以分配到一塊農田實施作業任務，即保證所有農機的有效利用；

7)不考慮天氣，農村道路阻塞等特殊情況。

2.3 建立數學建模

針對農業機械的作業問題(見圖1)，按照如下步驟建立數學模型。

圖1 農業機械調配優化路徑Fig.1 The mathematical model of path optimization of wheat harvest

1)問題的要素。農機調配站：DP1，DP2，…，DPn，共計n座。可使用的農機：Veh1，Veh2，…，Vehm，共計m輛。

每臺農機與調配站的隸屬關系：Sub1，Sub2，…， Subm(任一農機必屬于某調配站，即Subi∈ DP)。

農田：Frm1，Frm2，…，Frmq，共計q塊。為建模及計算方便，農田的劃分按農機單日作業量劃分，即某塊農田Frmi在模型中可由某臺機械Vehj單日作業完成。

調配站DPi與農田Frmj之間的路途長度Disij。

農田Frmi與農田Frmj之間的路途長度Dsij。

農機Vehi的作業序列Frma，Frmb，…，Frmp，共計p個(作業序列中的元素為農田，p≤q)。

農田Frmi在作業序列中的順序[Vehj，Ordk]，其中Vehj意為農田Frmi由車輛Vehj作業，Ordk意為農田Frmi在車輛Vehj路徑上的序號(任一序列必屬于該車輛的作業序列，即Ordk≤p)

2)問題的目標1為所有車輛路徑總和最小，由下式表示，即

其中，DS為DS(Sj)(Sj+1)，即農機作業序列中相連的兩塊農田之間的距離；Dis1為Dis(Ci)(S1)，即農機所屬調配站與農機作業序列中第一塊農田之間的距離；Dis2為Dis(Ci)(Sp)，即農機所屬調配站與農機作業序列中最后一塊農田之間的距離。

3)問題的目標2為完成整個作業所用的時間最少，由下式表示，即

min(Ordk)

其中，Ordk即為任一農田在農機作業路徑中的序號，所有農田的Ord值最大的一個即為作業全部完成的時間。

4)問題的約束條件1為所有農田都被農機作業，且只由一臺農機作業，即

上式表示農田的作業序列中，Vehj為車輛集合V中的任一元素，且該農田在車輛Vehj的作業順序合法。

5)問題的約束條件2為農機某個作業順序上，只允許對一塊農田作業。

3 農業機械調度遺傳算法流程

遺傳算法流程如圖2所示。

本文所使用遺傳算法的計算流程如下：

1)隨機產生一組初始個體，形成起始種群；

2)對種群內的每個個體執行適應度判斷，保留適應度高的個體，形成新的種群；

3)判斷整個算法是否達到了終止條件，如是結束算法，否則進入下一個步驟；

4)對種群執行交叉操作，產生子種群；

5)對子種群進行變異操作，并跳入步驟2)。

4 調度遺傳算法設計

使用遺傳算法首先要選擇合適的染色體編碼方式。在問題的建模中，本文使用[Vehj，Ordk]來表示農田Frmi在整個作業序列中由農機Vehj的第Ordk個順序進行作業。按照這個方式，將所有的農田的作業序列依照農田的順序依次列出，即形成了一種可能的整體作業方案，如圖3所示。

圖2 遺傳算法流程Fig.2 The genetic algorithm flow

圖3 農機作業方案示意Fig.3 The deployment program sketch

圖3中，每塊農田的作業為一個染色體，所有農田的作業串接成整個方案，形成一個個體。

在構建整個方案的時候，需要滿足問題建模時的兩個約束條件。

滿足約束條件1的方式為：依次為所有農田隨機抽取某一臺農機作業。

滿足約束條件2的方式為：每當抽取到某臺農機時，將該農機的作業順序加1。

1)形成起始種群。為每塊農田Frmi隨機抽取一臺農機Vehj，并將Frmi附加到Vehj現有的作業序列之后。記錄Frmi[Vehj，Ordk]為一個染色體。為所有農田抽取農機，形成一個方案，即個體；同時，記錄這個個體每臺農機的作業順序。重復這個過程Par1次(Par1值可由問題的規模決定，此處設定初始值為10 000)，即形成了個體數量為Par1的起始種群。

2)適應度判斷。適應度(Fit)直白地表達了個體的好壞。在問題建模時有兩個目標：總路徑最短(Fitdis)及作業時間最短(Fittim)。將兩個目標按照Par2及1-Par2的比例加權作為適應度來判斷個體的好壞，即

Fit=Par2·Fitdis+(1-Par2)·Fittim

Par2的值初始假定為50%，即認為總路徑最短和作業時間最短的重要性相當。可以調節Par2的值來加強某一目標的權重，如天氣狀況不良，搶收時的作業方案計算，就應當將作業時間最短這個目標的權重加強(如Par2=10%)。

計算總路徑最短的適應度Fitdis，首先要計算每個個體各自的總路徑TtlDs，計算方式為累加每臺農機的行駛總路程，即

因為路徑短的個體適應度應該更高，將每個個體的總路徑TtlDs取倒數，然后按照個體與總體的比例計算路徑適應度，即

計算作業時間最短的適應度Fittim，首先要計算每個個體各自的作業時間，計算方式為選取作業序列最長的農機的最后一個序列號為該個體的作業時間，用Ordmax表示。

因為作業時間段的個體適應度應更高，將每個個體的作業時間Ordmax取倒數，然后按照個體與總體的比例計算作業時間適應度，即

將整個群體中的每個個體的適應度都計算出來后，按照適應度由高到低排序，保留前10%的個體作為新的種群，種群規模變為了0.1Par1。

3)算法終止判斷。算法以固定的迭代次數Par3作為終止條件，迭代次數達到Par3則終止計算，將適應度最高的個體作為解決方案輸出。

4)交叉形成子種群。由2)中形成的0.1Par1規模的種群為父種群，按照輪盤賭的方式執行交叉策略，生成子種群，子種群的規模恢復為Par1大小，如圖4所示。具體的策略如下：首先從父種群中隨機選擇兩個個體，方式為在區間(0, 1]上隨機兩次，得到兩個隨機數；父種群是按照適應度從高到低依次排列的，且所有個體的適應度和為1，兩個隨機數落到哪個個體的區間，則這兩個個體成為雙親。

圖4 雙親選擇示意圖Fig.4 The parents choice sketch

選中雙親以后，由雙親交換多個染色體生成兩個子代，如圖5所示。策略為：隨機選擇多個染色體Frmrdm，進行互換。

圖5 染色體交換示意圖Fig.5 The chromosome exchange sketch

圖5中，雙親交換了染色體2，形成了2個新的子代，交叉完成后，需要對每個子代的新的染色體執行合法化。將原來的染色體[Vehold，Ordold]刪除，將農機Vehold的第Ordold作業序列刪除，并將后續作業序列前提；然后添加新的交換來的染色體[Vehnew，Ordnew]，將農機Vehnew的第Ordnew作業序列之后插入農田Frmrdm，并將后續作業順序后延。在合法化的過程中，非Frmrdm的染色體也會隨之發生更新。

重復選擇雙親生成子代的過程0.5Par1次，子代種群達到Par1規模。

5)子種群的變異。以一個較低的概率Par4(初始設定為0.1%)隨機選擇子種群中的個體，對選中的個體隨機挑選多個染色體Frmrdm，隨機更改該染色體的農機，作業順序則保持不變。個體變異以后也需要執行合法化。方式與4)中相同，不再贅述。

5 農業機械調度遺傳算法的應用與分析

使用MatLab編程本文設計的算法，并以隨機生成的數據(4個站點，40臺農機，400塊農田)為例進行計算，如圖6所示。

圖6 遺傳算法算例Fig.6 The genetic algorithm example

初始種群Par1設定為2 000；兩個目標的比例加權Par2設定為50%；迭代次數Par3設定為10 000次；變異比例Par4設定為0.1%。

計算完成后，可看到各臺機械被分配到的農田數量均勻，作業路徑合理，路徑交叉路線較少。證明算法的設計是合理有效的，結果如圖7所示。

圖7 算法結果Fig.7 The genetic algorithm result

作為對比，假設一種由人工指定作業的方式：所有車輛負責等面積的作業區域，作業路徑按維度依次排列，這種方式與現實世界中的人工調配比較相似。最后的作業結果如圖8所示。

對比使用遺傳算法的結算，路程由2 698.5km增加到3 592.2km，作業天數由10天增加到12天。遺傳算法的運算結果明顯優于簡單的按區域劃分分配作業車輛的方式。

遺傳算法本質上是一種規則約束下的全局搜索，隨著問題的復雜化，解空間的大小對比算法計算量趨向于無窮大。所以，算法難以保證最終解與最優解的接近程度。遺傳算法解的演進方式為：先探索，再驗證，接受或否定本次探索，算法特性決定了它的搜索方向是隨機跳動的。這樣做的益處在于保證了搜索的全局性，但對特定解的局部優化則不是算法的優先考慮項。反映到實際的運算結果中，往往發現可以對結果進行局部微調優化，這種微調既可以人工進行，也可以另設計算法處理。圖9為對遺傳算法運行結果進行人工微調后的示例。

圖8 人工調配結果Fig.8 The manual deployment result

圖9 人工微調結果Fig.9 The manual trimming result

由圖9可以看出：手動微調以后，總路程稍微下降至2 666.6km，作業天數增加到11天。人工微調的作用比較有限，而如果設計算法進行局部微調的話，則可能會有更明顯的優化效果，從而形成遺傳算法搜索全局、微調算法局部優化的結構。因本文重點不在于此，故不展開研究。

為測試遺傳算法計算結果的穩定性，重復執行算法，計算20次，各次結果分布如圖10所示。

由圖10可見：各次結果離散性較小，算法求解效果穩定，具有較高的實用性。

6 結論

對農機調配問題進行建模，使用遺傳算法進行編程及算例運行，證明遺傳算法適用于解答較大規模的農機調配問題。本文所構建的遺傳算法使用比較簡單，運行結果穩定，輸出的調配方案整體優于人工調配方案，可明顯縮短農機調配的作業里程及工期，具有較高的實用性。同時，也應看到因為智能算法固有的特性，算法運行結果并不能保證為問題最優解，對結果進行特定方向的人工再調整在實踐中仍有其必要性。

圖10 結果穩定性Fig.10 The results stability