基于多變異分組遺傳算法的多機協同作業靜態任務分配

王 猛 趙 博 劉陽春 汪鳳珠 偉利國 方憲法

(中國農業機械化科學研究院土壤植物機器系統技術國家重點實驗室， 北京 100083)

0 引言

農業生產一般具有很強的“農時”性和嚴格的作業窗口期。隨著農機自動導航技術的發展和推廣，智能農機及其導航技術已成為智慧農業的重要組成部分，多臺農機或多種農機的協同作業技術可發揮機群作業優勢、提高農機作業效率，已逐漸成為新的研究熱點[1-3]。

多機協同作業技術在機器人、無人機等領域已進行了較多的研究，任務分配是其研究熱點之一，即給定一個機器人(或無人機)集合、一個任務集合及系統性能評價指標，為每個子任務尋找一臺合適的機器人(或無人機)負責執行該子任務，且使機器人(或無人機)系統完成任務集合中的全部任務時所獲得的收益最大[4]。通過對多機作業進行任務分配可以加快機群任務執行速度、降低系統消耗，并提高工作效率[5-15]。多機協同任務分配技術在機器人工業生產、水下機器人搜索、無人機作戰和無人機災難搜索等領域已進行了較深入的試驗研究和應用[16-20]。多機協同任務分配技術在農業領域研究較少，相比于無人機或機器人的任務分配問題，農機作業情況更加復雜，農機需依次到達目的地，并且在目的地完成作業。JENSEN等[21]提出1臺運糧車為多臺收獲機運糧的路徑規劃方法，多臺收獲機在不同的地塊進行收獲作業，運糧車根據自身速度和收獲機的作業位置、作業路徑和作業速度等參數，通過Dijkstar算法規劃運糧車田間和田內路徑，實現了行駛距離和用時的最優，該方法不僅實現了運糧車田間的路徑規劃，也實現了田內的路徑規劃，具有較高的參考價值。以前，農機常常分散在農村多個機主手中，農機數量和性能與需要作業的任務地塊參數未知，不具備任務分配條件。我國農機合作社的發展和農機作業遠程平臺的研發為農機任務分配技術提供了必要性和可行性條件[22-23]。

本文根據我國農機合作社農機實際作業模式，綜合考慮機群的作業時間、作業油耗和路程代價等因素，構建多機協同目標函數，根據多機協同作業特點構建多變異分組遺傳算法，設計兩段式編碼、分組交叉算子和多種變異算子，優化目標函數，降低系統代價，以實現多機協同靜態任務分配。

1 多機協同場景

農機多機協同作業靜態任務分配指農機機群作業前將作業任務和任務順序分配給指定農機的過程。以某個作業季農機合作社中常見作業場景為例，即合作社的多臺同種農機同時從車庫出發，分別完成各自多個指定的任務后又回到車庫。用集合{a1，a2，…，am}表示m臺作業農機；用集合{T1，T2，…，Tn}表示n個作業任務。第i臺農機的性能參數表示為ai={vwi，di，wi，vi，tti，cwi，cvi}(i=1，2，…，m)，其中vwi表示第i臺農機作業的平均速度(km/h)，di表示第i臺農機的作業幅寬(m)，wi表示第i臺農機的平均作業能力(m2/h)，vi表示第i臺農機非作業狀態行駛平均速度(km/h)，tti表示第i臺農機作業中每次調頭的平均時間(h)，cwi表示第i臺農機作業時單位時間的平均油耗(L/h)，cvi表示第i臺農機非作業狀態行駛單位時間的平均油耗(L/h)；第j個任務的參數表示為Tj={x1j，y1j，x2j，y2j，x3j，y3j，x4j，y4j，dTj，lTj，Sj}(j=1，2，…，n)，其中(x1j，y1j)、(x2j，y2j)、(x3j，y3j)和(x4j，y4j)分別表示任務Tj地塊4個頂點的坐標，dTj表示任務Tj垂直作業路徑的寬度，lTj表示任務Tj平行作業路徑的長度，Sj表示任務Tj的作業面積，如圖1所示。

2 多機協同代價數學模型

2.1 多機協同作業基本假設

農機協同作業實際情況復雜，為了簡化問題，方便計算，根據農機合作社的作業特點設定的基本假設如下:①農機性能參數和任務參數已知。②需要作業的任務數量大于農機的數量。③每個任務地塊只能有一臺農機作業，單臺農機可以完成多地塊作業。④每個任務地塊分配給指定農機后，任務地塊路徑規劃結果已知。⑤每個作業任務面積適中。⑥農機同時從車庫出發，完成分配的全部任務后回到車庫。⑦全部農機完成分配的任務回到車庫后認為任務全部完成。

2.2 多機協同代價函數

農機完成作業任務的代價包括農機到達指定任務和回到車庫的路程、總的作業時間和油耗等，并根據每個部分的重要程度定義該部分的權重。

對于m臺農機，n個作業任務的情況，給出以下目標函數

(1)

式中f——多機協同代價

si——第i臺農機完成作業任務時路上的總路程

α、β、γ——權重，α、β、γ∈[0,1]

ci——第i臺農機完成任務的油耗

ti——第i臺農機完成任務的時間

(1)總路程si由3部分組成：農機ai從車庫到其第1個任務Tj的路程s(ai，Tj)；農機ai從其第j個任務Tj到下一個任務Tk的路程s(ai，TjTk)；農機ai從其最后一個任務Tl回到車庫的路程s(ai，Tl)，其中j、k、l∈{1，2，…，n}。

(2)

其中

(3)

(4)

(5)

(2)油耗ci由3部分組成：農機路上油耗、作業過程中調頭油耗和作業油耗。

(6)

其中

(7)

(8)

式中kij——第i臺農機在第j個任務地塊作業行數

「?——向上取整運算符

(3)完成任務時間ti由3部分組成：農機路上時間、農機作業時間和農機田間調頭時間。

(9)

(4)將車庫作為起點，即第1個點，n個任務依次作為第2到n+1個點，任意兩點間實際可行駛的最短距離的矩陣D為

(10)

式中di,j——第i-1個任務點到第j-1個任務點之間可行駛的最短距離(i、j=2,3，…,n+1，i≠j)，km

如果j、k2個任務地頭相鄰且作業過程中農機可從地頭連接處進入地塊，如圖2所示，則該2個任務點之間的最短距離為0。矩陣D是一個對角線為0的對稱矩陣，第1行d1，j(j=2,3，…,n+1)表示農機從車庫到第j-1個任務點的距離。

式(2)中s(ai，Tj)=d1，j+1，s(ai，Tl)=d1，l+1。農機進入任務地塊的方式分為從路上進入和從地頭連接處進入，令x=0表示農機從路上進入任務地塊，x=1表示農機從地頭連接處進入任務地塊；令y=0表示農機在該任務完成后回到路邊，y=1表示農機在該任務完成后回到地頭連接處。農機進入第1個任務地塊時從路上進入，第i臺農機在第j個任務地塊作業完成后的位置

yij=(kij+xij)%2

(11)

式中xij——第i臺農機進入第j個任務地塊的標識

%——求余運算符

當dj+1,k+1≠0時，農機ai從任務j到任務k的距離為

s(ai，TjTk)=dj+1，k+1+yijlTj

(12)

xik=0

(13)

當dj+1，k+1=0時，任務i、j地頭相連，此時農機ai從任務j到任務k的距離為

s(ai，TjTk)=|yij-1|lTj

(14)

xik=1

(15)

3 任務分配方法

遺傳算法通常包括選擇、交叉和變異3個基本步驟，本文提出一種多變異分組遺傳算法，設計了兩段式編碼，采用了輪盤賭選擇染色體的方法，設計了交叉和多種變異算子，有效地解決了多機協同任務分配問題。

3.1 算法設計

3.1.1編碼

根據文獻[24]設計了兩段式編碼，如圖3所示。第1段表示任務的排序，n個任務由1到n，n個數字表示，共n位；第2段表示分組的位置，共m-1位(n=12，m=3)。第i臺農機的任務用集合Ci表示，則某一個父代染色體由集合p={C1，C2，…，Cm}表示。

3.1.2選擇算子

定義適應度函數，適應度越高的染色體表示任務分配效果越好。適應度函數

(16)

(1)交叉算子選擇

采用輪盤賭選擇法選擇種群中進行交叉的個體。

(2)最優個體保留

為提高算法效率采用最優個體保留方法。最優個體保留步驟:①找出當前群體中適應度最高的個體和適應度最低的個體。②若當前群體中最佳個體適應度比迄今為止最佳個體的適應度高，則以當前種群中的最佳個體作為迄今為止最佳個體。③用迄今為止最佳的個體替換當前群體中最差的個體。

3.1.3交叉算子

分組交叉算子設計過程如圖4所示，其實現方式如下：①用輪盤賭方法選擇2個父代，同時產生1到m的隨機序列。②按隨機序列的順序進行分組遺傳，設隨機序列第1個數為k，產生隨機數Rr∈[0,1)，如果Rr<0.5則第1個父代的第k組作為子代的第k組，如果Rr≥0.5則第2個父代的第k組作為子代的第k組。③從2個父代中刪除子代中包含的任務，按照步驟②方式進行序列第2到m位代表的組數進行分組交叉遺傳。④將未參與交叉運算的剩余任務隨機插入到子代中得到最終的子代。

3.1.4變異算子

為了加快進化過程，增加基因多樣性，提高遺傳算法效率，提出幾種變異算子。

3.1.4.1組間轉移變異算子

設計了組間轉移變異算子(ITVO)，過程如圖5所示。①在某條染色體隨機選取2個不同的組作為移出組和移入組Ogroup、Igroup∈{1，2，…，m}。②如果移出組Ogroup中任務數量大于1，則隨機從移出組和移入組選取2個點Opoint、Ipoint作為移出任務位置和移入任務位置。③將移出任務位置Opoint對應的任務移動到移入位置Ipoint對應的任務前完成組間轉移，并相應修改分組間斷點的值。

3.1.4.2組間交換變異算子

為了提高染色體多樣性，加快算法的收斂，設計了一種組間交換算子(IEVO)，交換算子的實現形式如圖6所示。①從染色體的第1到m組分別隨機選擇用做交換任務的點。②移除選中點的任務。③將移除的任務進行排序，并按排列后的順序插入到交換任務點。

3.1.4.32-opt局部優化變異算子

2-opt屬于局部搜索算法，是解決組合優化問題的有效工具，該算法的實現方式：①在染色體的某組內隨機選取2個點i、j。②i前的路徑不變添加到新路徑中，將i到j之間的路徑翻轉其編碼后添加到新路徑，將j之后的路徑不變添加到新路徑。

2-opt算法示意圖如圖7所示，該示意圖中基因分組間斷點為3、9，2-opt優化組在第2組，2-opt變異點為4、8。

3.1.4.4突變算子組合

將3種變異算子組合成多變異算子網絡，如圖8所示，每個節點表示一個算子，有向邊表示上一個算子結束后選擇下一個算子的概率。

3.2 算法流程

本文設計算法的流程如圖9所示，具體為：

(1)根據編碼方式產生數量為N的初始種群作為父代，計算每個父代的適應度，定義分組交叉概率Pc、組間轉移變異概率Pm1、組間交換變異概率Pm2、2-opt局部優化變異概率Pm3和迭代次數K。

(2)基于輪盤賭方法選擇2個父代，產生隨機數Rr∈[0,1)，如果RrPc，適應度較好的父代直接復制到子代，計算子代適應度和種群數量，如果子代種群數量小于N，重復步驟(2)。

(3)從子代第1個個體開始，產生隨機數Rr∈[0,1)，如果Rr

(4)將此時的子代作為當前種群，計算變異后每個個體的適應度，執行最優個體保留方法。

(5)判斷是否達到迭代次數，如果未達到迭代次數，執行步驟(2)；如果達到迭代次數，則選擇當前種群適應度最高的個體作為該任務分配的解。

4 仿真分析

為了確定算法參數并驗證算法的有效性，設計了12個任務地塊和3臺農機的仿真試驗，假設任務分配過程中，任務地塊作業路徑方向與任務地塊現有實際作業路徑方向相同。確定參數過程中取目標函數式(1)中系數α=0、β=0、γ=1，即直接用完成任務時用時最長的農機作業時間作為機群代價優化目標函數，試驗任務電子地圖如圖10所示。圖中1～12表示任務地塊編號。

3臺農機的性能如表1所示，根據平臺得到任務參數如表2所示。

表1 農機性能參數

表2 任務參數

多變異遺傳算法包括Pc、Pm1、Pm2和Pm34個參數，采用正交試驗方法研究每個參數對算法的影響，每個參數取4個水平，根據單個算子優化試驗結果，選擇交叉算子概率Pc取值0.4～1，間隔0.2；組間轉移變異算子概率Pm1取值0.4～1，間隔0.2；組間交換變異算子概率Pm2取值0.4～0.7，間隔0.1；2-opt變異算子概率Pm3取值0.4～1，間隔0.2。

根據參數的水平選擇正交試驗表L16(45)，計算20次每種組合計算結果的平均值作為該種組合的優化結果，迭代次數為1 000次，通過計算極差得到參數對結果的影響從大到小依次是Pm2、Pm3、Pm1和Pc，取使計算結果得到最小值的參數水平：Pm2=0.7、Pm3=1、Pm1=0.6和Pc=0.6。

為驗證算法的有效性，分別采用確定參數后的多變異分組遺傳算法(MGGA)與文獻[23]改進的分組遺傳算法(IGGA-SS)和文獻[24]多染色體遺傳算法(MGA)對試驗任務進行仿真試驗，迭代次數取1 000次，重復20次，每次迭代的值取20次試驗的平均值，得到圖11所示結果。可以看到多變異遺傳算法可以在較小的迭代次數下得到較優的結果。

針對3種算法進行9、12、15個任務的任務分配試驗，分別使用多變異遺傳算法(MGGA)、改進分組遺傳算法(IGGA-SS)和多染色體遺傳算法(MGA)對幾種任務分配問題獨立做250、500、750、1 000次迭代試驗，每個算法每次迭代20次取平均值，得到的平均時間代價和平均用時如表3所示。

表3 3種算法對幾種問題的解

由表3可知：相同迭代次數下，多變異遺傳算法(MGGA)運行時間最長、效果最優，最小代價降低1%～5%；在分組數量和迭代次數相同條件下，隨著任務數量的增加多變異遺傳算法(MGGA)運行時間未出現明顯的增加；在相同運行時間條件下，多變異遺傳算法(MGGA)可以在較低的迭代次數下得到最優結果；對不同數量的任務和分組，多變異遺傳算法(MGGA)具有很好的魯棒性；在得到相同結果的條件下多變異遺傳算法(MGGA)可減少50%以上的迭代次數和減少30%以上的運行時間。

為得到更為全面的仿真結果，選擇12個任務和3臺農機分別以不同的權重進行仿真試驗，試驗結果如表4所示。

表4 不同權重的仿真結果

由表4可知，代價的權重越大任務分配后該代價越小，在不同權重條件下，總油耗代價變化較小，總路程代價和最長作業時間代價變化較大。當γ取值較大、α和β取值較小時可以得到各個代價較均衡的任務分配效果，此時的任務分配結果更加符合實際農機作業情況。

5 實際深松作業驗證試驗

為驗證本文提出的任務分配方法在實際作業中的效果，對實際作業情況進行任務分配試驗。圖12為吉林省公主嶺市一合作社某日深松作業情況，該合作社共3臺深松設備，該日共完成23個任務。設備性能參數和任務參數如表5、6所示，數據來源于“農業機械化精準作業平臺”的實際作業數據。

表5 農機性能參數

3臺深松設備實際作業情況如圖13所示，第1臺深松設備的作業順序14→15→22→20→18→6→8，第2臺深松設備的作業順序10→11→17→12→13→4→3→2→1，第3臺深松設備的作業順序16→23→21→19→5→7→9。機群的理論多機協同作業時間為12.57 h，理論總路程為7.0 km。

表6 任務參數

分別以不同的權重進行靜態任務分配，任務分配結果如表7所示。

表7 不同權重下試驗結果

由試驗結果可知，在不同的權重條件下多機協同代價均有明顯下降，代價的權重越大，任務分配后該代價越小。當總路程代價權重較小、時間代價權重較大時，多機協同任務分配后路程代價和時間代價均有明顯下降，且路程和時間代價較為均衡，各農機分配到的任務較為平均，該種情況符合農業生產實際作業需求；當總路程代價權重較大、時間代價權重較小時，多機協同任務分配后路程代價明顯降低，時間代價降低不明顯甚至增加，此時會出現一些農機執行大量任務其他農機執行極少量任務的情況，該種情況不符合農業生產實際作業需求。由于時間代價包含了一個農機的總路程和總任務面積等信息，因此，時間代價權重取值較大時會得到時間和總路程較均衡的任務分配結果，該結果較符合實際農業生產需求。試驗結果表明，基于多變異分組遺傳算法的多機協同靜態任務分配方法可有效解決多機協同靜態任務分配問題。

6 結論

(1)對同種作業農機多機協同靜態任務分配問題進行了研究，構建了多機協同作業代價函數模型。

(2)設計了分組交叉算子和3種變異算子對遺傳算法進行改進，提出了基于多變異分組遺傳算法的多機協同靜態任務分配方法。

(3)對基于多變異分組遺傳算法的多機協同靜態任務分配方法和參考算法進行對比，結果表明，多變異分組遺傳算法對于不同數量的任務和分組都具有很好的任務分配效果，當迭代次數相同時，可降低1%～5%的代價，計算出相同代價可降低50%以上的迭代次數和30%以上的運行時間。

(4)選取不同的權重分別進行仿真分析和實際作業場景試驗分析，得到不同權重系數下的任務分配結果，實際作業場景試驗任務分配后，多機協同代價比實際作業代價降低了29.48%～55.00%，表明基于多變異分組遺傳算法的多機協同靜態任務分配方法可較好地解決多機協同靜態任務分配問題。