穴盤苗補苗自動移栽路徑規劃優化研究

程方啟

（浙江機電職業技術學院，浙江 杭州 310053）

0 引言

工廠化穴盤育苗技術已廣泛應用于溫室蔬菜種植，能夠為蔬菜種植戶提供健壯的蔬菜苗。在穴盤苗出廠前，需要用健壯苗替換那些缺苗或劣質苗。自動移栽機可提高穴盤苗的移栽效率和移栽品質、降低工人勞動強度和生產成本[1-3]。穴盤苗補苗的自動化移栽可描述為：自動移栽機的執行機構從供苗穴盤將健壯苗逐一取出，然后移栽到目標穴盤的多個待補苗的空穴孔中，在此過程中，自動移栽機末端執行器的總行程會因選擇的取苗或補苗路徑不同而不同。因此，對穴盤苗補苗自動移栽路徑進行規劃優化，可以有效降低末端執行器的行走距離，有利于提高補苗作業效率、補苗均勻一致性，節約運行時間[4-6]。

優化自動移栽機的移栽路徑一直是該領域的研究熱點[7-8]。童俊華等[9-10]采用標準遺傳算法對穴盤苗補苗自動移栽的路徑進行了研究，但其優化的算法設計模型與獲得的結果有待改進。賀磊盈等[11]將貪心算法與遺傳算法相結合對穴盤苗補苗移栽的路徑進行優化研究，并與固定順序法的計算結果相比較，結果表明該算法具有較好的效果。徐守江等[12-13]采用蟻群算法和混合蛙跳算法對穴盤苗移栽補苗路徑進行了規劃優化，研究結果與常規的固定順序路徑相比優化幅度較大，算法具有良好的穩定性。張麗娜[14]構建了免疫遺傳算法與克隆選擇算法2 種移栽路徑的優化模型，并與固定順序法和標準遺傳算法做了比較，結果表明，基于免疫遺傳算法的優化模型效率較高。盡管已有較多文獻對穴盤苗補苗移栽路徑進行了規劃優化研究[15-16]，但路徑規劃的設計采用算法的設計、效率及效果仍待提高。

1 穴盤苗補苗自動移栽問題描述與規劃分析

常用的育苗缽盤尺寸一般為250 mm×500 mm，通常以穴孔數量G來定義其規格（其中G一般為25、50、72、128 等）[9]。穴盤苗補苗自動移栽系統中，補苗穴盤A 和供苗穴盤B 物理空間尺寸為630 mm×530 mm，補苗穴盤A 和供苗穴盤B 之間距離為100 mm，如圖1 所示。穴盤格內小橢圓圈表示缽盤的穴苗位，供苗穴盤B 中黑色小橢圓圈表示不可取苗的穴苗位，其他小橢圓圈表示健壯穴苗；補苗穴盤A 中穴盤格內空白的表示待補苗的空穴位，其他小橢圓圈表示健壯穴苗。具體移苗過程描述如下：穴盤苗補苗自動移栽機的執行器從移栽系統的坐標原點出發，從供苗穴盤B 內取出1 株健壯苗移栽到補苗穴盤A 中的空穴孔內，不斷循環直至補苗穴盤A 中的空穴孔全部完成補苗，之后再返回移栽系統坐標原點。穴盤苗補苗移栽路徑規劃的目的是確定往復移栽補苗的先后順序，在末端執行器驅動速度一定的情況下最小化補栽路徑長度，從而提高自動移栽機的工作效率。

圖1 缽盤補苗自動移栽作業示意圖

假定A 盤需補種穴苗的空穴數量為k個，B 盤為可供移栽的健壯苗l株。在上述環境下，缽苗補苗自動移栽機末端執行器進行移栽作業時可選擇的路徑共有q種，計算公式為

式中：

k—— A 盤需補種穴苗的空穴數量，個，k≥1；

G—— A 盤的穴孔數量，個，l≤G；

l—— B 盤可供移栽的健壯苗，株，k≤l。

從公式（1）可看出，即使是小規模的問題，解空間也是非常大的。穴盤苗補苗自動移栽路徑規劃是一個典型的組合優化問題，也是一個NP（Nondeterministic Polynomial）完全問題，迄今沒有一個多項式時間算法來解決這類問題，若采用遍歷搜索算法來獲得最短路徑，則計算量巨大，難以滿足補苗自動移栽機實時性的作業要求。本文嘗試基于改進的遺傳算法進行問題求解。

2 穴盤苗補苗自動移栽路徑規劃問題建模

2.1 定義穴苗位置與穴苗縱橫方向順序對應關系

以缽盤穴孔數為50 的規格為例，穴苗位置Pij與其坐標的對應關系見圖2，設任一穴苗位置中心點坐標為Pij，其中，P表示穴苗位置，角標ij表示橫坐標方向第i列、縱坐標方向第j行交點處的穴盤。其中，i，j均為自然整數，i=1，2，…，Nx，j=1，2，…，My；Nx為橫坐標方向的缽盤A 與B 穴苗位置總數，My為縱坐標方向的缽盤A 與B 各自穴苗位置總數，圖2中，Nx=My= 10。

圖2 缽盤苗位置與坐標對應關系

2.2 穴盤苗補苗自動移栽路徑規劃模型構建

根據歐式定理，任意兩點P1(x1,y1)與P2(x2,y2)之間的距離可表示為

式中：

x1——穴苗位置P1的橫向坐標值；

x2——穴苗位置P2的橫向坐標值；

y1——穴苗位置P1的縱向坐標值；

y2——穴苗位置P2的縱向坐標值。

設補苗穴盤A 有k個需要補苗的穴位孔，供苗穴盤有l個健壯穴苗可供移栽，則補苗自動移栽機末端執行器從坐標原點O 出發，依次從B 盤上將健壯苗移栽到A 盤的空穴位孔上，逐次完成第k個空穴位孔補苗后，從A 盤返回到坐標原點O。則補苗移栽路徑行程順序圖可表示為

其中，O為坐標原點，Ai表示補苗穴盤A 的第i次補苗，Bi表示供苗穴盤B 的第i次取苗。整個移栽路徑行程總長度可以表示為

式中：

PO—— 缽苗自動移栽機坐標原點位置；

G—— 缽盤穴位孔的數量，個；

k——A 盤空穴數，k≤G。

2.3 穴苗位置與坐標對應關系映射

在進行穴盤補苗自動移栽作業路徑規劃前，需要建立穴苗位置與坐標之間的對應關系，以便后續算法的編碼與編程。采用直角坐標法與序號法相結合的編碼方式，缽盤穴苗位置序號與其相對應的直角坐標互為映射關系[8]，為了區分A、B 盤位置，設A 盤位置號為負數，B 盤位置號為正數，建立的缽盤穴苗位置序號如圖3 所示。

圖3 缽盤苗位置序號圖

以圖3 為例，補苗穴盤A 中待補苗空穴孔為-23、-27、-30、-35；供苗穴盤B 中1～10 號和17～20 號共14 個穴位孔為缺苗或劣質苗（穴盤孔涂黑），其余為健壯苗。由于缽苗穴盤大小規格為250 mm×500 mm，根據補苗自動移栽機的布局與運動要求，A 盤左下角的位置坐標為（30，30），B 盤左下角的位置坐標為（380，30）。根據以上A、B盤的位置坐標信息，建立缽苗位置坐標與缽苗序號的映射。

對于補苗穴盤A，當穴苗位置序號P（i，j）≠-10，-20，-30，-40，-50時，穴苗位置坐標與穴苗序號的映射關系可表示為公式（4）；當穴苗位置序號P（i，j）＝-10，-20，-30，-40，-50時，穴苗位置坐標與穴苗序號的映射關系可表示為公式（5）。

對于供苗穴盤B，當穴苗位置序號P（i，j）≠10，20，30，40，50時，穴苗位置坐標與穴苗序號的映射關系可表示為公式（6）；當缽苗位置序號P（i，j）＝10，20，30，40，50時，穴苗位置坐標與穴苗序號的映射關系可表示為公式（7）。

式（4）—（7）中：

X（i，j）——（i，j）位置處的橫向坐標值；

Y（i，j）——（i，j）位置處的縱向坐標值；

P（i，j）——（i，j）位置處的穴苗位置序號；

i和j均為介于1～10 之間的整數，mod 為求余運算；floor 為向下取整運算。

3 穴盤苗補苗移栽路徑優化的遺傳算法設計

3.1 遺傳算法的編碼機制

前述已將缽盤穴苗位置映射為序號，A 盤符號為負數，B 盤序號為正數。根據補苗移栽路徑行程順序圖可知，可將染色體定義為由坐標原點與穴苗位置序號構成的線性數字序列，如表1 所示。設k=4，l=36，則隨機列出一條染色體編碼（0，32，-27，16，-35，23，-30，24，-23，0）。由表1 可見，染色體長度為2k+2，即取決于待補苗的空穴數量。染色體對應的路徑行程長度S由2k+1 段兩點間距離的總和。

表1 染色體編碼機制說明

3.2 構造適應度函數

適應度函數值是評價一條染色體好壞的依據，會對計算結果帶來直接的影響。參照公式（3），S表示補苗移栽行程總長度（目標函數），在遺傳算法中適應度值是越大越好。本文令染色體ζ的適應度函數為f（ζ），在任一個種群的所有路徑中，必然存在最大值Smax與最小值Smin，考慮使總長度最短的路徑適應性為1，而最長路徑適應性為0，其他路徑則介于0～1。適應度函數可表示為

式中：

f（ζ）—— 染色體ζ的適應度函數；

Sζ—— 染色體ζ的路徑行程長度值；

Smax—— 所有染色體遍歷后路徑行程中的最大值；

Smin—— 所有染色體遍歷后路徑行程中的最小值。

3.3 遺傳算子的改進機制

選擇、交叉和變異等遺傳算子的操作都會直接影響遺傳算法的效率和收斂速度，而穴苗補苗自動移栽路徑規劃需要在進行算法設計時對遺傳算子進行改進操作。

3.3.1 選擇操作

采用輪盤賭法進行遺傳算子的選擇操作，適應度值越大的個體被選中的概率越大。每個個體的適應度除以總適應度值，以此作為每個個體的被選中的概率。以初始種群數為父代、個體選擇概率為選擇依據，計算適應度值并按照由大到小對相應個體進行排序。

3.3.2 交叉操作

對初始種群選擇操作完后，進行交叉的遺傳算子操作。因自動移栽路徑編碼分別對應于2 個穴盤內缽苗的不同基因位置標記且具有唯一性，因此，要求交叉后各基因位置的元素不能相同?；诖?，以補苗穴盤有4 個待補苗空穴孔，供苗穴盤有36 個健康苗穴孔為例，其補苗移栽路徑的交叉策略描述如下：

1）隨機選擇種群中的偶數條染色體，確保兩兩相互交叉操作。隨機產生2 個2～7 之間的自然數i和j，確保從染色體基因位第3 位才開始交叉操作，若從第2 位開始交叉且步長等于9，則相當于種群中2 條染色體互換位置，起不到使種群多樣化的目的。其中i為染色體基因位，j為交叉步長。如i+j≥9,則令i+j= 9，染色體基因最后1 位為原點，不需要參加交叉操作，既保證交叉不超出染色體長度，又減少了最后1 位的無效交叉，提高運算效率。

2）以i= 3，j= 4 為例，圖4（a）中，染色體Ⅰ和Ⅱ交叉操作，染色體Ⅰ的第4～7 基因位片段（-35，23，-30，24）與染色體Ⅱ對應的第4～7 基因位片段（-30，35，-27，14）片段交換，形成新的染色體，如圖4（b）所示。

3）檢查同一染色體中基因位是否存在相同的序號，如有，則用100 代替。交叉后形成的新染色體Ⅰ不存在重復的序號，而交叉后形成的染色體Ⅱ第2與第8 個基因位元素相同（均為24）、第7 與第9 個基因位元素相同（均為-30），如圖4（c）所示。將交叉后染色體Ⅱ的第2、7、8、9 四個基因位的元素替換為100，如圖4（d）所示。

4）遍歷染色體2～9 基因位，用有效元素代替100。如圖4（e）所示，當100 所在基因位為奇數時，表示這些元素來自補苗穴盤A，即（-23，-27，-30，-35）。經遍歷后發現（-23，-35）兩個元素已使用，則第7 基因位隨機從（-27，-30）中選1 個元素（如-30），剩余的另1 個元素放在第9 基因位（-27）。當100 所在基因位為偶數時，表示這些元素來自供苗穴盤B，即11～16 和21～50 等元素。經遍歷后發現（30，35）兩個元素已使用，則第2 基因位隨機從11～16 與21～50（30，35 除外）中選1 個元素（如45），剩余的另1 個元素放在第8 基因位（-27）。最終得到交叉后新的染色體Ⅰ和Ⅱ，如圖4（f）所示。

圖4 交叉操作機制

3.3.3 變異操作

為了使種群保持多樣性，避免陷入局部最優，采用遺傳算子的變異操作?？紤]到補苗自動移栽路徑的雙盤基因位的相異性，確保變異后個體的有效性，變異操作需要采取單點變異與元素替換相結合的策略，對變異算法描述如下：

1）隨機選擇種群中的數條染色體進行單點變異操作。隨機產生1 個2～9 之間的數i，確定該染色體變異操作的基因位。判斷該基因位的元素為正數或是負數，從而確定是奇數基因位還是偶數基因位。

2）若為奇數基因位，則需從補苗穴盤A 中選擇元素。如圖5（a）所示，隨機數i=5，該基因位現有元素為-35，則可以變異為（-23，-27，-30）中的任一元素。假設該基因位元素-35 隨機變異為-27，則遍歷奇數基因位，將元素-35 替代原-27 元素所處的第9 基因位，從而得到變異以后的新染色體，如圖5（b）所示。

3）若為偶數基因位，則需從供苗穴盤B 中選擇元素。隨機數i=6，該基因位現有元素為21。變異存在2 種情形，當該基因位元素21 變異為11～16 與21～50 的任一元素且不等于19，38 或16，此時得到新染色體I-1，此為變異情形1，如圖5（c）所示。當該基因位元素21 變異為19，38 或16 中的任一元素時，如變異為19，那么該元素與第2 基因位元素值相同。此時，需要將原來變異前的元素21 替換第2 基因位的元素，得到新的染色體I-2，此為變異情形2，如圖5（d）所示。

圖5 變異操作機制

3.4 最優染色體保存與最差染色體替換策略

為有效防止遺傳算法陷入“早熟收斂”，可采用最優染色體保存策略，如圖6 所示：①生成種群后計算適應度值，找出最優染色體（最優個體）并保存。②找出經選擇、交叉、變異操作后新種群中的最優個體。若本代最優個體優于上一代最優個體，則用本代最優個體代替上一代最優個體，同時，用次優個體代替本代的最差個體。若本代最優個體差于上一代最優個體，則保存上一代最優個體，同時，用本代最優個體代替最差個體。③繼續循環迭代至迭代完成。最優的個體不參與交叉、變異操作，可以確保最優的個體可以遺傳到下一代。利用每次迭代中新種群的次優或者最優個體代替最差個體，可以提高種群的多樣化，不陷入局部收斂，提高運算速度。

圖6 最優個體保存策略算法流程

4 仿真試驗與結果分析

根據上述算法模型對穴盤苗補苗自動移栽路徑進行規劃優化，由于穴盤規格和空穴數量的不同對算法設計不會產生影響，分別設計有效性仿真試驗和隨機性對比仿真試驗。仿真環境為MATLAB R2018a，該算法運行平臺為Thinkpad 筆記本電腦，處理器為Intel（R）Core（TM）i7-10510U CPU，RAM 為16.0 GB。

4.1 有效性仿真試驗與結果對比分析

以圖1 補苗移栽作業要求為例進行優化計算[9,12]。交叉概率、變異概率分別取0.8 和0.3，種群規模為20，優化迭代次數為200。

通過改進的遺傳算法求解，以缽苗移栽路徑總長度為目標的函數曲線收斂很快，其中一次計算如圖7 所示，經過72 次迭代，得到路徑總長度最小值為2 913.892 009 983 26 mm，保留到個位數，記為2 914 mm，平均優化算法運行時間0.43 s。圖8中箭頭所示路徑為經優化后的最優移缽路徑解（0，13，-35，15，-30，16，-27，14，-23，0）。本文的算例初始參數設定參考童俊華[9]和徐守江[12]的研究，經算法運行后獲得路徑長度和最優路徑，如表2 所示。本文算法Ⅰ經與童俊華[9]和徐守江[12]的研究對比后可以看出，算法Ⅰ與算法Ⅱ均可獲得最優路徑長度為2 914 mm，算法Ⅲ獲得的最優路徑長度為2 930 mm，說明算法Ⅲ獲得的最優補苗移栽路徑解（0，12，-35，15，-30，16，-27，14，-23，0）不是該問題的最優解，而是該問題的1 個次優解。本文設計的算法Ⅰ比算法Ⅲ獲得的最優路徑長度縮減了165 mm，縮減幅度為5.6%。對比3 種算法獲得最優路徑可以看出，算法Ⅲ路徑中選擇的第2 個基因位的元素為12，而算法Ⅰ與算法選擇的第2 個基因位為13，其余基因位元素均相同。

圖7 路徑長度收斂變化曲線

圖8 經優化計算后獲得的最優路徑（總長度2 914 mm）

表2 不同算法效果對比

4.2 隨機性仿真試驗與結果分析

為了進一步分析本文算法模型的效率，選取規格為50 穴孔缽盤進行移栽路徑規劃仿真試驗。補苗穴孔數量分別設為4、5、6、7、8，補苗穴孔位置隨機確定。供苗穴孔數量對應分別設定為36、42、39、43、41，取苗穴孔的位置隨機確定。每組做5 次試驗，路程長度與運算時間均取5 次試驗的均值。隨機性仿真試驗初始參數如表3 所示。

表3 隨機性仿真試驗

經仿真試驗，按試驗組別獲得的路徑規劃長度均值分別為2 914、3 340、3 824、4 249、4 851 mm，如圖9 所示。路徑長度受補苗穴孔數量、取苗穴孔位置和補苗穴孔位置等因素的影響，整體趨勢上看，隨著補苗穴孔數量的增多，移栽路徑長度均值也逐漸變大。按試驗組別獲得的運算時間分別為0.43、0.45、0.46、0.49 和0.49 s，從整體趨勢上看，隨著補苗穴孔數的增大，染色體基因位也增多，路徑長度也變大，運算時間也逐漸變大，如圖10 所示。

圖9 多組試驗下補苗穴孔數量與路徑長度均值的關系

圖10 多組試驗下補苗穴孔數量與運算時間均值的關系

5 結語

1）構造的穴盤苗位置坐標和穴盤苗序號之間的映射關系公式為染色體的編碼。補苗自動移栽遺傳算法模型采取補苗穴盤與供苗穴盤序號交替布局的編碼機制、最優個體保存與最差個體替換策略來避免算法陷入“局部早熟”。

2）針對規格為50 穴孔缽盤的補苗移栽仿真試驗，補苗自動移栽遺傳算法模型能快速獲得最優的路徑規劃和最短的移栽路徑長度，且對比標準遺傳算法，獲得的最優路徑長度縮減了165 mm，縮減幅度為5.6%。

3）在規格為50 穴孔缽盤的補苗移栽仿真試驗中，在補苗、取苗穴孔位置一定的情況下，補苗自動移栽遺傳算法模型顯示補苗穴孔數量與移栽路徑長度均值、運算時間在趨勢上均呈正比例關系。