基于改進多父輩遺傳算法的農機調度優化方法

張 帆，羅錫文，張智剛，何 杰，張聞宇

（華南農業大學工程學院，南方農業機械與裝備關鍵技術省部共建教育部重點實驗室，廣州 510642）

0 引言

傳統農機跨區作業存在組織效率低、勞動生產率不高等問題，造成資源浪費[1]。農機作業時效強，特別是在農忙時節，要求農機在規定時間內完成作業任務，以確保糧食歸倉和及時播種，提高農機作業效率已經成為農業生產的首要問題。農機導航技術與物聯網技術的興起，為農機規模化調度和農場規模化作業的實現提供了技術支撐，加速了傳統農機作業邁向智能農機作業的進程[2]，也為無人農場的建設運營提供理論依據[3-4]。

在農業生產過程中，隨著對自動導航作業需求的不斷增加，實現多臺同種或異種作業農機之間協同作業已成為農機導航研究的重點[5]。對于單作業任務而言，國內外對農機的協同作業的研究重點主要集中收獲農機與運輸車輛之間的配合作業上[6]，如Lida等[7]和Noguchi等[8]分別研究了農機車輛自動跟隨作業與協同導航作業操作的問題。Zhang等[9]開發了一套跟隨式農機主從導航作業系統，實現了從機對主機的輔助運輸和加油等作業。針對多作業任務的需求，通常要根據機器、人員以及作業任務等信息，設計優化算法與決策策略，科學地對機器和人員進行運營調配，在保證所有作業任務及時完成的前提下，實現作業時間最短或作業成本最小[10-11]。

國內外許多學者對多農機執行多種作業任務的資源配置問題進行了研究。Jena等[12]利用混合整數規劃的方法確定甘蔗收獲機的作業路徑；Sethanan等[13]以甘蔗收獲機作業距離最小化和甘蔗收獲產量最大化為目標，提出了改進粒子群優化算法（MO-GLNPSO）解決甘蔗收獲機路徑規劃問題；Pitakaso等[14]提出了一種基于時間窗的聯合收獲機分配與路由問題的領域搜索方法，在聯合收獲機在任務共享的情況下，最大限度地提高收獲機的服務面積；Cerdeira等[15]研究了一個具有附加集群約束、時間窗和城市處理時間約束的旅行商問題（Traveling Salesman Problem，TSP）的變換模型[16]，并采用禁忌搜索和模擬退火思想相結合的算法對一個農機合作社幾個聯合收獲機的作業路徑進行了優化。國內方面，曹如月等和張小花等類比旅行商問題[17-18]，采用蟻群算法求解多機協同作業任務規劃問題，但未將農機在田間作業的約束進行綜合考慮；He等[19]提出了一種基于禁忌搜索和遺傳算法算子的混合算法以確定小麥的最優收獲時間，達到減少收獲時間的目的；王雪陽等[20]采用改進遺傳算法對跨區域作業的農機調度問題進行了研究；Zhou等[21]采用粒子群算法和遺傳算法相結合的方法求解了農機調度服務問題。部分研究采用啟發式算法，如吳才聰等[22]針對單一農機的作業問題建立了時空調度模型，并以動態規劃的方式進行基于時間窗的分步求解，最終完成整個模型的調度；Zhang等[23-24]針對農機跨區緊急作業調度問題進行了模型設計，并采用基于距離最近優先的多機多任務緊急調配和基于貢獻度最大優先的多機多任務緊急調配的啟發算法進行了求解，完成了農機的調度任務。

上述研究對多農機在特定時間內完成同一種作業任務提供了很好的解決方案，但是對農機作業過程中多種任務連續作業的問題，如需連續進行耕整、播種和施肥等作業，無法提供科學合理的決策服務。本文主要研究多農機多任務的連續調度問題，綜合考慮了調度損耗與作業損耗，通過采集的任務與農機的作業參數，建立農機調度模型，以作業時間最短為優化目標，利用改進的多父輩遺傳算法進行農機作業任務序列規劃，為解決多任務多農機的調度問題提供理論依據，也為開發基于無人農場智能農機管控平臺提供決策參考。

1 多農機多任務作業調度問題

1.1 問題描述

隨著3S技術[25]與農機自動駕駛技術[26]的不斷發展，智能農機可通過移動互聯網與云平臺進行實時通訊，將農機的實時位置、速度、作業等信息上傳至云端，這為農機的精準調度提供了數據參考與技術支撐[27-28]。農機作業具有很強的時效性，特別是在農忙時節，需要在較短的時間內完成農田的耕整、播種、施肥等作業操作，而進行每種作業的農機具也各不相同，這就要求在有限的作業期限內做出科學的農機作業調度決策，在保證作業任務及時完成的前提下，實現作業成本最小化[29-30]。

在農機調度中，單機單任務的農機作業序列規劃問題可類比成TSP問題進行分析，對農田空間分布和農機作業時間進行綜合考慮；而對于多機多任務的農機作業序列規劃問題，可描述為：m臺能執行不同作業任務的農機需要在n塊農田上進行特定作業，指定每塊農田特定的作業任務及順序、每塊農田作業參數及每臺農機的參數，安排每臺處于不同位置的農機在不同田塊的作業任務和作業順序，使整個農場的生產作業耗時達到最短。此外，本研究還綜合考慮了農機從當前位置到目標田塊的遷移時間，以及農機在達到目的地后作業準備時間。

1.2 數學規劃模型

根據多機多任務調度問題的描述，對該問題的抽象模型定義如下：

1）農田集合F={F1,F2,…,Fm}，以Fi代表第i塊農田，其屬性描述為Fi={LocFi,SFi}，其中LocFi和SFi分別表示農田Fi的入口位置和面積，

2）農機集合M={M1,M2,…,Mr}，以Mj代表第j臺農機，其屬性描述為Mj={LocMj, RSj, WSj，ReadyTj}，其中，LocMj表示農機Mj的當前位置，RSj表示農機Mj地塊轉移過程中的平均行駛速度，WSj表示農機Mj的平均作業速度,ReadyTj表示農機作業前準備時間，且有 [1,]jr∈ ；

3）農機集群MT={MT1,MT2,…,MTn}，以MTk代表第k種類型農機，表示為MTk={Mk1,Mk2,…,Mka}，a為第k種類型的農機總數，且有

4）作業任務序列的集合Task={Task1,Task2, …,Taskm}，Taski代表農田Fi的作業序列，并表示為Taski={Taski1,Taski2,…,Taskin}，Taskik代表在農田Fi上進行第k種作業，且對應作業的農機類型為MTk，[1,]kn∈ 。

此外，農機調度還需滿足下述條件：

1）每臺機器只能同時在某一塊地上進行作業；

2）在農機數量充足的條件且農田面積大于0.3 hm2時，每塊地可安排多臺同種作業任務的農機進行作業；

3）為避免不同類型農機因作業任務不同而產生干擾，單塊農田只進行同一種作業類型的作業，而需要多機協同完成同一作業任務的情況（如收獲機與運糧車的協同收獲作業），將其處理成同一類型作業任務；

4）每塊農田不同任務的作業順序固定，須滿足專門的作業規程，且每塊農田的任務必須被執行。

上述調度問題在考慮農田作業任務要求的同時，還考慮農田與農機的相對位置關系，以最近距離農機優先作業為原則，求出每塊農田上農機的作業順序集Si={Si1,Si2,…,Sir}，并以Sij表示農機Mj到農田Fi的調配方案，選取總調度時間最小為優化目標，調度模型表示如下：

調度目標：

約束條件：

式中T為任務總時間，h；TiF為第i塊農田的作業總時間，h，其中i=1, 2,…,m；transTik為農機集群MTk到農田Fi的轉移時間，h，其取值為農機集群MTk中每臺農機出發去農田Fi的轉移過程中所耗時間的最大值；readyTik為農機群MTk中每臺農機到達農田Fi作業前的準備時間，h；workTik為農機集群MTk在農田Fi的作業總時間，h；SiF為農田Fi的面積大小，hm2；Dij為農機Mj當前位置到農田Fi的距離，km，文中采用農機Mj到農田Fi兩點之間的距離進行簡要計算；Ek為第k種類型農機的工作效率，即每小時的作業面積，hm2/h；zik表示農機群MTk是否在田塊Fi進行作業，其中k與任務Taskik相對應，當農田中Fi中有任務需要被執行的任務k時，zik取值為1，否則為0；tij表示農機Mj是否到農田Fi進行作業，若該農機的田間轉移時間大于當前已經到達農田Fi的農機集群MTk完成農田任務總時間，則當前農機不參與該地塊的作業，此時tij置于0，否則為1；Yi為農田Fi的的任務數量。式（5）表示農田Fi的每個任務都允許有多臺農機參與，且每個任務必須被執行。

2 IMPGA算法原理

基于上述數學模型，本文提出了基于時間窗的改進多父輩遺傳算法求解多任務多農機調度問題，算法流程如圖1所示。

具體算法步驟如下：

1）初始化問題參數集。錄入農機、農田、作業任務等基礎信息，同時設置種群規模數PopulationNumber和迭代次數Iteration；

2）編碼。基于農田序號的編碼并初始化種群。

對于m塊農田有r種作業任務情況下的作業調度問題，每條染色體的基因數量為個（Ni表示農田Fi的任務個數），使用農田編號進行編碼，農田編號在染色體中出現的頻次代表農田作業任務號，第x次出現的作業序號代表該農田的第x個作業任務。如在一個2×2的調度問題中，農田集合F={F1,F2}，對應的任務集合Task={(1,2)，(2,3)}，則隨機分布的編碼共有6種類型，如[1 2 1 2]或[1 1 2 2]等。

3）適應度函數計算。以作業時間最短為優化目標，則遺傳算法的適應度函數為

式中f為染色體適應度，依據公式（1）～（5）對每個染色體的適應度值進行計算。

4）個體選擇。由于種群中優秀的父代個體中的基因質量更好，為了保證優秀個體基因的遺傳，加速尋優結果的收斂速度，按適應度值將種群劃分成優秀和良好2種種群，其中優秀種群占總群體規模的1/3，良好種群占2/3，從優秀群體里隨機選取個體Parent1，從良好群體隨機選取個體Parent2和Parent3。

5）變異。算法設計可調整的變異概率，當在進行多次迭代之后，如果種群中最優染色體的適應度沒有發生變化，則調整變異概率，若發生進化，則截至當前未進化的代數index置為0并重新開始累積，調整的變異概率用函數表示為：

式中pm為當前變異概率，%；pm0為初始變異概率，%；index為截至當前未進化的代數。

6）多父輩POX交叉。本文采用黃明等[31]提出的多父輩POX交叉方式，用優秀個體Parent1分別與良好個體Parent2和Parent3進行交叉，產生后代Child1和Child2，以3×3的調度問題為例來說明交叉過程，如圖2所示。首先假定有3個選擇的染色體序列Parent1、Parent2和Parent3，且有2個非空互余的基因子集Gene1 {1，2}和Jene2{3}；分別將Parent1中Gene1和Gene2進行分離，并將分離的基因原位置于O，O表示該位置暫時為空，再將Parent2和Parent3進行處理，分別保留Gene2和Gene1；最后分別將Parent1中保留的Gene1和Parent2中保留的Gene2進行交叉，即按從前到后的順序將Parent1中屬于Gene1的基因依次放入Parent2中，生成Child1，同理將Parent1中屬于Gene2的基因依次放入Parent3中，生成Child2。至此，多父輩的POX交叉的過程結束。

7）迭代進化。判斷是否滿足算法結束條件，若不滿足，則返回至步驟3）迭代；若滿足終止條件，則算法終止，輸出最優結果，并將最優結果進行解碼。

解碼是步驟2）的編碼逆變換過程，用實例來描述解碼過程如下：在一個2×2的調度問題中，農田集合F={F1,F2}，對應的任務集合Task={(1,2)，(2,3)}，農機集合為MT={MT1,MT2,MT3}，其中Task中的1代表平地作業，使用農機群MT1進行作業，同理，2和3分別代表播種作業和施肥作業，相應地使用MT2和MT3進行作業，當染色體編號為[1 2 1 2]時，表示的農田作業次序為F1-F2-F1-F2，則農機調度流程為MT1-MT2-MT2-MT3。在確定農機集群的調度流程后，還需對MTk進行解碼。對于任意序列MTk的解碼可描述如下：考慮農機數量充足的情況，對處于不同位置的農機，當選擇農機集群MTk去同一目標農田Fi進行作業任務Tk時，本文以基于最短路徑的貪婪算法選擇作業的農機臺數，具體過程為：①在農機集合M中篩選農機類型為k的農機集合MTk，分別計算農機Mki到農田Fi之間距離，并按增序進行排列；②以農田Fi的面積SFi為調度約束，依據公式（3）～（5）選擇可作業農機，判斷某臺農機能否加入該農田作業的準則是：若該農機的田間轉移時間大于當前已加入集群作業農機完成農田任務總時間，則當前農機不參與該地塊的作業。

3 IMPGA算法驗證

3.1 試驗數據

本文的農田數據采自新疆塔城地區，依據實際作業環境設置仿真作業任務，以驗證算法的性能和穩定性。算法的運行環境為：處理器Inter(R)i5-7500 3.4GHz，內存8G，操作系統Windows10，編程語言Java。表1為部分作業農田的基本信息，主要包括農田面積、農田入口經緯度與作業類型。表2為可用農機裝備的基本信息，如農機作業效率和路面行駛速度，此外包括每臺農機的初始位置經緯度及準備時間，準備時間即農機達到農田后需要進行作業準備的時間，如作業人員就位、裝料、加油、機器作業參數調整等作業前準備所需消耗的時間。

表1 部分作業農田的基本信息 Table 1 Basic information of part of farmland

表2 可用農機的基本信息 Table 2 Basic information of available agricultural machine

3.2 結果與分析

對上述農田的作業任務采用改進的遺傳算法進行仿真調度試驗，選取種群規模為300，進化500代，初始變異概率0.05。完成每種作業農機只有1臺時，選取農田數量為6，此時作業任務數量為20個，使用改進遺傳算法進行運算得出最優調度方案，再通過Matlab生成甘特圖，如圖3a所示，其中甘特圖白色部分代表農機在田塊之間的轉移時間與準備時間之和，其他顏色代表了農機在不同農田的作業時間，該調度方案的總完工時間為85.42 h。同理，當執行每種作業任務的農機數量為多臺時，調度結果如圖3b所示，該調度方案的總完工時間為38.45 h。

為了驗證改進遺傳算法的有效性和穩定性，首先考慮執行每種作業任務的只有1臺時（以下簡稱單農機作業），選取農田數量為5、10、15和20塊的作業任務，分別使用IMPGA和GA進行調配運算10次，調度結果如表3所示。由表3可知，當執行每種任務的農機數量為1臺時，改進的遺傳算法的最優解、平均解均優于標準遺傳算法，其調度時間的最優解和平均解分別縮短2.24%和3.16%，且改進遺傳算法的平均標準偏差小，證明了改進遺傳算法的魯棒性好于標準遺傳算法；為驗證IMPGA的收斂性，對比最優解出現的迭代次數可以發現，除農田數量為15時IMPGA出現的次數大于IG之外，其余農田數量相同的條件下IMPGA均能更早找到最優解，而對比平均值發現，GA最優解平均出現的迭代次數為298.5，而IMPGA為255.8，IMPGA比GA收斂更快。此外，通過對比算法運行時間可知，2種算法的運行時間均隨著任務數量的增加而增加，改進遺傳算法的平均運行時間比標準遺傳算法的平均運行時間長2.36 s。

表3 單農機作業下IMPGA與GA的調度結果對比 Table 3 Comparison of results between IMPGA and GA under single number machinery

由表4可知，當執行每種作業任務的農機多于1臺時，作業任務完工總時間小于農機數量為1臺的結果。在農機數量相同時，改進遺傳算法的調配結果仍優于標準遺傳算法的結果：在農田數量為5時，2種算法均能求得最優解；在農田數量為10時，使用改進遺傳算法求取調度的最優時間和平均時間分別縮短3.77%和3.56%；農田數量為15時，最優時間和平均時間分別縮短1.63%和3.76%；農田數量為20時，最優時間和平均時間分別縮短4.46%和3.47%。此外，隨著農田數量增多時，算法運行時間增加，且改進遺傳算法的平均運行時間比標準遺傳算法的運行時間長8.92 s。

表4 多農機作業的IMPGA與GA調度結果對比 Table 4 Comparison of results between IMPGA and GA under multi-type machinery

總之，本文改進的遺傳算法在總體上優于標準遺傳算法，其調度的最優時間和平均時間分別能平均縮短2.47%和2.70%，能滿足農機作業調度的任務需求。

4 結 論

考慮實際農田作業情況，本文分析了針對連續作業任務的農機作業任務規劃問題，在農機隨機分布的情況下，以作業時間最短為優化目標，建立了基于農業生產中多機執行多任務的調度模型。在考慮農機田間轉移時間和作業準備時間的前提下，采用改進遺傳優化算法對多機多任務的農田作業問題進行調配，通過與標準遺傳算法相對比，結果表明：改進的多父輩遺傳算法能有效解決多任務農機的作業分配問題，在迭代次數相同的情況下，盡管IMPGA比GA運行時間長8.92 s，但IMPGA求解調度方案的最優時間和平均時間分別能縮短2.47%和2.70%，節約了時間成本，滿足農機運維和無人農場生產運營實際作業的調度需求。

后續研究將考慮多臺農機同時作業，某臺農機發生故障時如何對農機重新進行作業分配的問題；此外，隨著農機自動駕駛技術和物聯網技術的不斷發展，研究內容還將與智能無人農機管控平臺集成，逐步實現無人農場農機的智能化任務調度、自動化路徑規劃以及生產作業的全程管控。