基于貪心遺傳算法的穴盤苗補栽路徑優(yōu)化

賀磊盈 楊太瑋 武傳宇 俞亞新 童俊華 陳成錦

(1.浙江理工大學機械與自動控制學院， 杭州 310018； 2.浙江省種植裝備技術(shù)重點實驗室， 杭州 310018; 3.浙江三鋒實業(yè)有限公司， 金華 321300)

基于貪心遺傳算法的穴盤苗補栽路徑優(yōu)化

賀磊盈1,2楊太瑋1武傳宇1,2俞亞新1,2童俊華1,2陳成錦3

(1.浙江理工大學機械與自動控制學院， 杭州 310018； 2.浙江省種植裝備技術(shù)重點實驗室， 杭州 310018; 3.浙江三鋒實業(yè)有限公司， 金華 321300)

溫室育苗需要通過補苗移栽作業(yè)用健康缽苗替換穴盤內(nèi)未發(fā)芽或劣質(zhì)的缽苗，保證缽苗的質(zhì)量。自動補苗移栽機可利用機器視覺獲取穴盤苗健康信息，控制末端執(zhí)行器抓取缽苗進行補苗作業(yè)，移栽效率高。穴盤內(nèi)需補苗孔穴的位置具有隨機性，對補栽路徑進行規(guī)劃，可進一步提高補栽效率。本文綜合貪心算法和遺傳算法的特性提出一種貪心遺傳算法，在分段步長取8，優(yōu)化代數(shù)取100時，可實現(xiàn)稀疏和密集穴盤的補栽路徑優(yōu)化，具有魯棒性。貪心遺傳算法所規(guī)劃補苗路徑長度與全遺傳算法接近，均值差在443 mm以內(nèi)；相比優(yōu)化前的固定順序法，貪心遺傳算法路徑長度可縮短33.8%～41.3%，縮短長度隨空穴數(shù)量增加而加長；貪心遺傳算法與全遺傳算法規(guī)劃補栽路徑耗時分別為1.81 s和5.59 s。對比可知，貪心遺傳算法更有利于自動移栽機輸送單元和移栽單元間的動作銜接，可進一步提高自動移栽機效率。

自動移栽機； 穴盤苗； 溫室； 路徑優(yōu)化； 貪心遺傳算法

引言

溫室穴盤育苗技術(shù)已被廣泛采用，穴盤苗出廠前需將未發(fā)芽或長勢不好的苗剔除，并用健康苗補種。缽苗自動移栽機可以解決傳統(tǒng)人工作業(yè)勞動強度大、效率低的問題，且移栽質(zhì)量好。國外自20世紀80年代末開始研究缽苗移栽機[1-3]，TING等[4-5]研制出2種夾持器安裝于SCARA工業(yè)機器人上，進行600孔至48孔固定順序的稀植移栽作業(yè)。RYU等[6]開發(fā)一種由CCD相機檢測和三維移動平臺構(gòu)建的自動移栽機，其氣缸驅(qū)動的末端執(zhí)行器可實現(xiàn)98%的移栽成功率。國內(nèi)學者近年也開展了適合本土育苗實際的缽苗自動移栽機研究[7-9]，例如，田素博等[10]設(shè)計了穴盤苗輸送、定位及自動控制裝置。孫國祥等[11]基于虛擬樣機技術(shù)對一種電動機驅(qū)動的末端執(zhí)行器進行設(shè)計。TONG等[12]基于改進型分水嶺分割算法對相鄰穴孔缽苗葉片存在重疊的穴盤苗進行健康識別。韓綠化等[13]設(shè)計了一種兩指四針鉗夾式取苗末端執(zhí)行器，并對影響夾缽取苗效果的含水率、入缽角和深度等因素進行統(tǒng)計試驗分析。上述研究主要針對缽苗自動移栽機的系統(tǒng)設(shè)計[14-15]、缽苗健康檢測[16-18]、末端執(zhí)行器開發(fā)[19-21]等方面的關(guān)鍵技術(shù)研究，適用于穴盤苗出廠后大田或花卉盤[22-24]的機械化移栽作業(yè)。

此外，優(yōu)化自動移栽機關(guān)鍵機構(gòu)尺寸和移栽路徑也是研究的熱點。HU等[25]通過建立移栽機運動學和動力學仿真模型，優(yōu)化二自由度五桿并聯(lián)機構(gòu)的幾何尺寸和抓取苗軌跡中的驅(qū)動速度。童俊華等[26]采用全遺傳算法對50孔的穴盤間補苗移栽路徑進行優(yōu)化，相比固定順序路徑長度縮短8.5%以上。但針對目的穴盤為空盤的稀植移栽作業(yè)時，若采用全遺傳算法規(guī)劃，生成的整條路徑編碼長，計算量大，耗時長。為此，童俊華等[27]又采用貪心算法分別對稀疏穴盤(50孔移栽至32孔)和密集穴盤(128孔至72孔)進行稀植移栽路徑優(yōu)化，可使路徑長度縮短10.6%以上。

在對密集穴盤采用全遺傳算法[26]進行補栽路徑規(guī)劃時發(fā)現(xiàn)，穴孔數(shù)量的增加會使單個染色體基因數(shù)增加，使整體路徑取優(yōu)的運算量增大，不能適應(yīng)自動移栽機高效率實時性作業(yè)的要求。為此，本文綜合前期研究，提出一種貪心遺傳算法，對補栽路徑規(guī)劃采用貪心分段式遺傳優(yōu)化再組合的方法，以減少運算時間，縮短補栽路徑，進一步提高移栽機末端執(zhí)行器的工作效率。

1 缽苗補苗移栽路徑規(guī)劃描述

1.1 溫室缽苗自動移栽機補苗作業(yè)原理

溫室缽苗自動移栽機的樣機如圖1所示，其基本尺寸長×寬×高為3 800 mm×1 100 mm×2 300 mm。其中包含視覺檢測、苗盤傳輸、三坐標移栽和控制器4個單元。視覺檢測單元可識別出穴盤各穴孔內(nèi)健康缽苗、未發(fā)芽或長勢不好的劣質(zhì)缽苗，并記錄缽苗在穴盤內(nèi)的位置。苗盤傳輸單元包含前端、中間轉(zhuǎn)換和并行雙末端3段輸送帶，如圖2所示。穴盤苗在前段輸送帶上完成檢測，然后通過中間轉(zhuǎn)換輸送帶送至并行雙末端輸送帶上進行補苗。三坐標移栽單元中的三維移動機械臂驅(qū)動末端執(zhí)行器剔除并行雙末端輸送帶上補苗穴盤劣質(zhì)缽苗穴孔后，將輸送帶上供苗穴盤內(nèi)的健康缽苗逐一進行補種移栽?？刂破鲉卧溆蠭ntel Core i7 CPU的研華701G2工控機和三菱PLC。

圖1 溫室缽苗自動移栽機樣機Fig.1 Prototype automated transplanter in greenhouses1.視覺檢測單元 2.苗盤傳輸單元 3.三坐標移栽單元 4.控制單元

圖2 苗盤傳輸單元示意圖Fig.2 Diagram of tray transfer unit1.前端輸送帶 2.中間轉(zhuǎn)換輸送帶 3.并行雙末端輸送帶

供苗(或補苗)穴盤補種作業(yè)完成后，新穴盤苗從中間轉(zhuǎn)換輸送帶送至三坐標移栽單元的作業(yè)位置距離L2為1 000 mm,假設(shè)輸送帶平穩(wěn)輸送速度為0.5 m/s，則需要2 s時間。補苗路徑控制算法若能在2 s內(nèi)完成規(guī)劃，將不影響自動移栽機苗盤傳輸單元和三坐標移栽單元間作業(yè)節(jié)拍的銜接，滿足實時性要求。

1.2 補苗移栽路徑規(guī)劃分析

溫室育苗穴盤外觀尺寸為250 mm×500 mm，穴孔數(shù)G有32、50、72和128等規(guī)格。圖3為50孔規(guī)格供苗穴盤向補苗穴盤移栽的路徑示意圖：穴盤格內(nèi)小圓圈代表健康缽苗穴孔，空格代表劣質(zhì)缽苗穴孔；末端執(zhí)行器從原點出發(fā)，按照一定順序逐一將供苗穴盤內(nèi)的健康缽苗移栽補種至補苗穴盤中的空穴孔內(nèi)。補苗移栽路徑規(guī)劃的目的是確定往復(fù)移栽的先后順序，在機械臂驅(qū)動速度一定的情況下縮短補栽路徑，提高移栽機工作效率。

圖3 補苗移栽路徑示意圖Fig.3 Diagram of seedlings replugging tour

2 固定順序和貪心算法補苗路徑規(guī)劃方法

2.1 固定順序補苗移栽路徑規(guī)劃方法

補苗移栽固定順序方法(FS)采用文獻[27]中常規(guī)固定順序方案中較穩(wěn)定的方案2作為參照對比方案。具體步驟為：從左至右、從上至下順序掃描供苗穴盤，依次將健康缽苗按從右至左、從上至下的順序補種移栽至補苗穴盤的空穴孔內(nèi)，最終路徑如圖4所示。

圖4 固定順序補苗移栽路徑規(guī)劃方法Fig.4 Fixed sequence method for seedlings replugging tour

2.2 貪心算法補苗移栽路徑規(guī)劃方法

補苗移栽貪心算法(GAS)采用文獻[27]在稀植移栽規(guī)劃試驗中的最優(yōu)方案3。具體為：保持補苗穴盤從上至下、從右至左的掃描移栽順序；比較供苗穴盤內(nèi)健康缽苗所有健康缽苗穴孔與補苗穴盤空穴孔間距離，以最短穴孔的健康缽苗為移栽對象；依照此方法對未完成補苗填充的補苗穴盤空穴按秩序掃描移栽，結(jié)果如圖5所示。

圖5 貪心算法補苗移栽路徑規(guī)劃方法Fig.5 Greedy algorithm for seedlings replugging tour

3 全遺傳算法和貪心遺傳算法補苗路徑規(guī)劃方法

3.1 全遺傳算法補苗移栽路徑規(guī)劃方法

全遺傳算法(GA)補苗移栽路徑規(guī)劃方法與文獻[26]一致，對供苗穴盤內(nèi)的健康缽苗和補苗穴盤內(nèi)的空穴孔進行正負標記和交叉編碼染色體路徑，通過選擇、交叉、變異和重插入操作，優(yōu)選出種群適應(yīng)度最大個體。遺傳算子與前期研究相同，選擇、交叉和變異概率分別取0.9、0.8和0.3，種群規(guī)模取40。遺傳優(yōu)化代數(shù)隨編碼染色體基因加長而增加，對128孔的密集穴盤遺傳規(guī)劃運算取600代時能得到收斂，圖6為重復(fù)運算10次遺傳過程中種群最優(yōu)路徑長度和種群路徑長度均值隨優(yōu)化代數(shù)變化的結(jié)果。確定全遺傳算法各算子參數(shù)后，進一步對圖3所示補苗移栽模型的路徑進行優(yōu)化，結(jié)果如圖7所示。

圖6 128孔穴盤10次運算路徑長度隨遺傳優(yōu)化代數(shù)變化曲線Fig.6 Path changing curves along with hereditary algebra for 128 holes

圖7 全遺傳算法補苗移栽路徑規(guī)劃方法Fig.7 Genetic algorithm for seedlings replugging tour

3.2 貪心遺傳算法補苗移栽路徑規(guī)劃方法

遺傳算法具有全局搜索優(yōu)化的能力，補苗穴盤待補苗空穴孔數(shù)量增加使其搜索的運算量加大；為提高運算效率，引入貪心算法局部取優(yōu)的思想組合成一種貪心遺傳算法(GGA)，用于穴盤苗補苗移栽路徑規(guī)劃。方法可描述為：①將補苗穴盤內(nèi)的待補苗空穴孔按秩序區(qū)域分段。②遺傳算法搜索優(yōu)化的移栽路徑，確定各分段空穴孔對應(yīng)供苗穴盤內(nèi)健康缽苗的移栽秩序。③各分段的優(yōu)化路徑前后拼接，可得到貪心遺傳算法的整體優(yōu)化路徑。結(jié)合圖3中的補苗移栽模型對該算法具體實施步驟加以闡述。

3.2.1 穴孔標記和分段編碼

路徑規(guī)劃前將補苗穴盤內(nèi)待補苗空穴孔和供苗穴盤內(nèi)的健康缽苗按順序標記，并與三坐標移栽單元內(nèi)的坐標值相映射。補苗穴盤內(nèi)m個空穴孔按從上至下、從右至左的掃描順序進行負標記(-1,-2,…,-m)；供苗穴盤內(nèi)n株健康缽苗按從上至下、從左至右的掃描順序進行正標記(1,2,…,n)，如圖8所示。

圖8 穴孔標記示意圖Fig.8 Diagram of tray hole marker

對補苗穴盤的負標記序列分段，以p為分段步長；若m≤p，則保持(-1,-2,…,-m)序列長不變；若m>p，m/p=u，余數(shù)為v,標記序列可分段為u+1段，分別為: (-1,-2,…,-p)，(-p-1,-p-2,…,-2p)，…，(-(u-1)p-1,-(u-1)p-2,…,-up),(-up-1,-up-2,…, -up-v)。按分段順序第1分段p個負標記與n個正標記隨機交叉編碼，進行該局部分段的遺傳算法路徑優(yōu)化；第2分段負標記則與前次遺傳優(yōu)化后余下的正標記進行交叉編碼和遺傳優(yōu)化；依此執(zhí)行，直至負標記的第u+1段。若v≠1，仍按遺傳優(yōu)化方法執(zhí)行，若v=1，則按貪心算法直接計算對最后1株補苗移栽的最短路徑。圖7所示模型，假設(shè)取p=4,則第1分段可隨機交替生成一條含2p=8個基因的局部路徑編碼染色體(32，-3，25，-2，12，-4，9，-1)，相比3.1節(jié)所述的遺傳算法染色體路徑基因可減少10個，采用同樣的方法生成總共N個編碼染色體構(gòu)成該分段遺傳算法的初始種群。

3.2.2 適應(yīng)度函數(shù)和選擇操作

路徑優(yōu)化的目標是尋找最短移栽路徑值，通過編碼染色體所映射的路徑長度來構(gòu)建遺傳算法的適應(yīng)度函數(shù)，從而判別編碼染色體在該種群內(nèi)的適應(yīng)度。假設(shè)R(i)為染色體i的適應(yīng)度，Si表示染色體i對應(yīng)的路徑長度，Smax和Smin表示該種群染色體對應(yīng)路徑最大和最小長度，可定義出介于0～1之間變化的染色體適應(yīng)度函數(shù)為

采用輪盤賭選擇法選擇種群染色體中適應(yīng)度大的作為子代種群，種群選擇比率為f,即有適應(yīng)度大的前Nf個染色體將被選作子代種群。

3.2.3 交叉和變異操作

交叉操作是遺傳算法的主要操作，組合出新個體在串空間內(nèi)進行有效搜索。針對補苗移栽路徑的編碼染色體具有正負交叉、基因不重復(fù)的特點，本文改進了交叉操作方法，具體過程如下。

假設(shè)p=4,移栽穴盤的前4個待補苗孔穴和供苗穴盤的43株健康缽苗孔穴編碼可隨機產(chǎn)生移栽路徑，任選2條作交叉操作示例。A=(32，-3，25，-2，12，-4，9，-1)，B=(28，-1，32，-3，20，-2，16，-4)。隨機生成2個介于1與2p之間的常數(shù)a和b，將A、B染色體的第a位開始至a+b位基因互換。設(shè)a=2，b=3，可得A1=(32，-1，32，-3，12，-4，9，-1)，B1=(28，-3，25，-2，20，-2，16，-4)。若a+b>2p，則令a+b=2p。最后遍歷A1、B1，將其中相同的基因用不在該染色體中的其它基因隨機替換，可得A2=(32，-1，18，-3，12，-4，9，-2)，B2=(28，-3，25，-2，20，-1，16，-4)。通過以上交叉操作可擴大搜索范圍，也保持了補苗路徑染色體的編碼要求。

變異操作可使遺傳算法避免過早收斂于非全局最優(yōu)點，保持種群多樣性。常用的單點基因變異也不適合于補栽路徑染色體正負交叉、基因不重復(fù)的編碼特點。改進后的方法具體如下。

隨機生成1個介于1～2p之間的常數(shù)c，將交叉操作后產(chǎn)生的染色體(設(shè)為A2)的第c位進行變異。首先判別c位基因的正負性，選擇相應(yīng)的其它正負基因隨機替換，并遍歷染色體其它基因位，若出現(xiàn)相同替換基因，則用原變異基因替換。設(shè)c=3，則A2的負基因位變異，可變異得到A3=(32，-1，18，-4，12，-3，9，-2)；設(shè)c=5，則A2的正基因位變異，可變異得到A4=(32，-1，18，-3，6，-4，9，-2)。通過增加判別步驟進行基因點變異，可滿足特有的補苗路徑染色體變異操作的要求。

圖9 貪心遺傳算法補苗移栽路徑規(guī)劃方法Fig.9 Greedy genetic algorithm for seedlings replugging tour

3.2.4 重插入和算法終止

重插入操作使種群個體被不斷篩選和進化時保持規(guī)模不變。初始種群經(jīng)選擇、交叉和變異操作，形成Nf個染色體的新種群；再將初始種群適應(yīng)度大的前N～Nf個染色體合并構(gòu)成子代種群。

該分段遺傳算法的目標是找尋該分段優(yōu)化補苗路徑，經(jīng)過M代種群進化，新產(chǎn)生種群的適應(yīng)度基本保持不變，可判定算法已基本收斂。通過預(yù)設(shè)種群優(yōu)化的代數(shù)作為該分段遺傳算法的終止條件，種群內(nèi)的最優(yōu)個體即為該分段的優(yōu)化路徑。

第1分段補苗路徑遺傳優(yōu)化后，按上述分段編碼方法對第2分段進行初始種群編碼，以及選擇、交叉、變異和重插入等操作，如此循環(huán)，直至最后分段；將各分段的優(yōu)化路徑從原點開始首尾相接，得到該貪心遺傳算法的補苗移栽路徑。本文各分段的先后順序采用前期貪心算法研究中的掃描順序的最優(yōu)方案[27]，即補苗穴盤從上至下、從右至左的分段順序進行規(guī)劃。

貪心遺傳算法的各遺傳算子保持與全遺傳算法一致，各分段遺傳均能有效收斂，圖9a和圖9b分別為圖8所示補苗移栽模型的第1分段和整體的貪心遺傳算法優(yōu)化路徑。

4 試驗與結(jié)果分析

4.1 貪心遺傳算法分段步長選擇

本文所提出的路徑規(guī)劃的貪心遺傳算法的本質(zhì)是將全遺傳算法[26]分拆為多段進行局部遺傳運算。貪心遺傳算法的分段步長對規(guī)劃路徑的影響通過試驗分析得到。

假設(shè)溫室育苗劣質(zhì)苗比例占5%～20%，隨機生成5組空穴孔數(shù)分別為2～6的32孔和8組空穴孔數(shù)分別為3～10的50孔補苗穴盤，另外對應(yīng)隨機生成含最少空穴孔數(shù)的供苗穴盤，各組為20個樣本；同樣，隨機生成11組空穴孔數(shù)分別為4～14的72孔和21組空穴孔數(shù)分別為6～26的128孔補苗穴盤，及相對應(yīng)含最少空穴孔數(shù)的供苗穴盤，各組為20個樣本；采用不同分段步長的貪心遺傳算法分別對上述稀疏和密集穴盤組進行總共6 960次的補苗移栽路徑規(guī)劃，其中分段步長取值介于穴盤空穴孔數(shù)和該規(guī)格穴盤含最少空穴孔數(shù)之間。對各規(guī)格含不同空穴孔數(shù)的穴盤組補苗規(guī)劃路徑長度取平均值進行統(tǒng)計分析，圖10為32孔、50孔、72孔和128孔規(guī)格穴盤補苗路徑長度均值與分段步長的關(guān)系,圖例中的數(shù)字表示空穴孔數(shù)。

圖10 各種穴盤補苗路徑長度均值與分段步長關(guān)系Fig.10 Relationships between average replugging path length and segmentation step value for various seedling trays

由圖10可知不同空穴孔數(shù)的穴盤補苗路徑分層明顯，所規(guī)劃補苗路徑長度隨穴盤的空穴孔數(shù)增加而增加。不同分段步長對相同空穴數(shù)穴盤規(guī)劃路徑的最大最小極差值在733 mm范圍內(nèi)變化，小于補苗總路徑的6.5%。圖11為不同分段步長對應(yīng)各規(guī)格穴盤所有樣本路徑波動均值。進一步通過方差分析，按α=0.05水準，不同分段步長對32、50、72和128孔規(guī)格穴盤路徑波動的顯著性檢驗結(jié)果分別為不顯著(p=0.171)、顯著(p=0.018)、極顯著(p=0.001)和極顯著(p=0.001)。由于前期研究全遺傳算法[26]對稀疏穴盤(50孔以下、空穴孔數(shù)在10以內(nèi))進行補苗規(guī)劃，其運算時間滿足苗盤傳輸單元和移栽單元間的作業(yè)節(jié)拍銜接。為使本文的貪心遺傳算法規(guī)劃密集穴盤的補苗路徑運算時間也滿足上述要求，需將分段步長取值在10以內(nèi)；而分段步長在8～10范圍內(nèi)所對應(yīng)72孔和128孔密集穴盤的路徑波動均值最小。經(jīng)收斂性測試，分段步長取8，優(yōu)化代數(shù)取100時能使128孔密集穴盤的各分段得到圖6所示全遺傳算法優(yōu)化600代的收斂水平，平均運算時間為1.81 s。

圖11 不同分段步長對應(yīng)各規(guī)格穴盤路徑波動均值Fig.11 Average path fluctuation of different segmentation step values for all seedling trays

在21組128孔穴盤樣本中隨機每組選擇1個樣本，采用貪心遺傳算法和全遺傳算法對各樣本重復(fù)運算20次進行路徑規(guī)劃，對應(yīng)各空穴孔數(shù)穴盤的多次規(guī)劃路徑的極差范圍分別為7～511 mm和7～432 mm。通過t檢驗，兩種算法得到的結(jié)果差異不顯著(p>0.281)，說明貪心遺傳算法具有和全遺傳算法一樣的可重復(fù)性，適合補苗路徑規(guī)劃。

4.2 密集穴盤補苗移栽路徑規(guī)劃比較

為檢驗該貪心遺傳算法對密集穴盤補苗移栽路徑規(guī)劃效果，隨機生成的11組空穴孔數(shù)分別為4～14的72孔和21組空穴孔數(shù)分別為6～26的128孔補苗穴盤，及相應(yīng)隨機生成含最少空穴孔數(shù)的供苗穴盤，各組為20個樣本，進行路徑規(guī)劃比較。圖12、13為上述4種方案分別對72孔和128孔穴盤規(guī)劃路徑長度均值與穴盤空穴數(shù)變化的關(guān)系。

圖12 72孔穴盤補苗路徑長度均值與穴盤空穴數(shù)關(guān)系Fig.12 Relationships between average replugging path length and vacancy holes for 72 holes seedling tray

圖13 128孔穴盤補苗路徑長度均值與穴盤空穴數(shù)關(guān)系Fig.13 Relationships between average replugging path length and vacancy holes for 128 holes seedling tray

對比可知，4種方案從規(guī)劃路徑最短目標的優(yōu)劣角度排序，依次為全遺傳算法(GA)、貪心遺傳算法(GGA)、貪心算法(GAS)和固定順序方法(FS)。全遺傳算法和貪心遺傳算法規(guī)劃路徑均值差在0.443 m以內(nèi)，從圖12、13的路徑均值中可看出，兩者非常接近。貪心遺傳算法對72孔和128孔穴盤規(guī)劃補苗路徑，長度均值相比固定順序方法分別縮短1.253～4.024 m和1.903～7.353 m,優(yōu)化幅度分別為33.8%～37.7%和34.5%～41.3%，縮短距離與穴盤空穴數(shù)成正比。圖14為貪心遺傳算法對128孔含空穴穴盤進行補苗移栽路徑規(guī)劃示例。

圖14 貪心遺傳算法補苗移栽路徑規(guī)劃示例Fig.14 Example of replugging path planning by GGA

穴盤空穴孔數(shù)量增加使路徑規(guī)劃算法的運算量加大，同時也延長了算法的運算時間。本文對含最大空穴數(shù)26的128孔規(guī)格穴盤補苗規(guī)劃，從而得到規(guī)劃算法的最大運算時間，全遺傳算法、貪心遺傳算法、貪心算法和固定順序方法的運行平均時間分別為：5.59、1.81、0.000 4、0.000 3 s。綜上可見，全遺傳算法和貪心遺傳算法對補栽路徑的優(yōu)化性能相近，均優(yōu)于貪心算法和固定順序方法，而貪心遺傳算法的運算時間則更加有利于苗盤傳輸單元和移栽單元間的作業(yè)節(jié)拍銜接。這是因為貪心遺傳算法利用貪心算法為框架篩選、快速將補栽空穴孔排序分段，再融合遺傳算法對各分段空穴孔補栽路徑優(yōu)化。此融合縮短了遺傳算法的路徑編碼，減少了運算時間，從而提高算法的綜合性能。

5 結(jié)論

(1)貪心遺傳算法分段步長取8，優(yōu)化代數(shù)取100時，可實現(xiàn)對稀疏和密集穴盤的補苗路徑優(yōu)化，重復(fù)運算的極差小于511 mm，具有魯棒性。

(2)該貪心遺傳算法的構(gòu)建結(jié)合了貪心算法和全遺傳算法的特點，所規(guī)劃補苗路徑要優(yōu)于貪心算法，與全遺傳算法規(guī)劃路徑差值在443 mm以內(nèi)。

(3)該貪心遺傳算法所規(guī)劃補苗路徑比未經(jīng)優(yōu)化的固定順序補苗路徑縮短33.8%～41.3%，其優(yōu)化長度隨穴盤空穴數(shù)增加而加長。

(4)該貪心遺傳算法對稀疏和密集穴盤路徑規(guī)劃運算可在1.81 s內(nèi)完成，比全遺傳算法的5.59 s要短，更加有利于自動移栽機苗盤傳輸單元和移栽單元間的作業(yè)節(jié)拍銜接。

1 KUTZ L J, MILES G E, HAMMER P. Robotic transplanting of bedding plants[J]. Transactions of the ASAE, 1987, 30(3): 586-590.

2 YANG Y, TING K C, GIACOMELLI G A. Factors affecting performance of sliding-needles gripper during robotic transplanting of seedlings[J]. Applied Engineering in Agriculture, 1991, 7(4): 493-498.

3 TAI Y W, LING P P, TING K C. Machine vision assisted robotic seedling transplanting[J]. Transactions of the ASAE, 1994, 37(2): 661-667.

4 TING K C, GIACOMELLI G A, SHEN S J. Robot workcell for transplanting of seedlings. Part Ⅰ: layout and materials flow[J]. Transactions of the ASAE, 1990, 33(3): 1005-1010.

5 TING K C, GIACOMELLI G A, SHEN S J, et al. Robot workcell for transplanting of seedlings. Part Ⅱ: end-effector development[J]. Transactions of the ASAE, 1990, 33(3): 1013-1017.

6 RYU K H, KIM G, HAN J S. Development of a robotic transplanter for bedding plants[J]. Journal of Agricultural Engineering Research, 2001, 78(2): 141-146.

7 繆小花, 毛罕平, 韓綠化, 等. 黃瓜穴盤苗拉拔力及缽體抗壓性能影響因素分析[J/OL]. 農(nóng)業(yè)機械學報, 2013, 44(增刊1): 27-32. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=2013s106&journal_id =jcsam. DOI: 10.6041/j.issn.1000-1298.2013.S1.006. MIAO Xiaohua, MAO Hanping, HAN Lühua, et al. Analysis of influencing factors on force of picking plug seedlings and pressure resistance of plug seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(Supp.1): 27-32. (in Chinese)

8 蔣煥煜, 施經(jīng)揮, 任燁, 等. 機器視覺在幼苗自動移缽作業(yè)中的應(yīng)用[J]. 農(nóng)業(yè)工程學報, 2009,25(5):127-131. JIANG Huanyu, SHI Jinghui, REN Ye, et al. Application of machine vision on automatic seedling transplanting[J].Transactions of the CSAE, 2009,25(5):127-131. (in Chinese)

9 韓綠化, 毛罕平, 胡建平, 等. 穴盤苗自動移栽缽苗力學特性試驗[J]. 農(nóng)業(yè)工程學報, 2013, 29(2): 24-29. HAN Lühua, MAO Hanping, HU Jianping, et al. Experiment on mechanical property of seedling pot for automatic transplanter[J]. Transactions of the CSAE, 2013, 29(2): 24-29. (in Chinese)

10 田素博, 王榮華，邱立春. 溫室穴盤苗自動移栽輸送系統(tǒng)設(shè)計[J]. 沈陽農(nóng)業(yè)大學學報, 2009, 40(4): 620-622. TIAN Subo, WANG Ronghua, QIU Lichun. Design on conveyor system of automatic transplanting for plug seedling in greenhouse[J]. Journal of Shenyang Agricultural University, 2009, 40(4): 620-622. (in Chinese)

11 孫國祥, 汪小旵, 何國敏, 等. 穴盤苗移栽機末端執(zhí)行器設(shè)計與虛擬樣機分析[J]. 農(nóng)業(yè)機械學報, 2010,41(10):48-53. SUN Guoxiang, WANG Xiaochan, HE Guomin, et al. Design of the end-effector for plug seedlings transplanter and analysis on virtual prototype[J]. Transactions of the Chinese Society for Agricultural Machinery, 2010, 41(10): 48-53. (in Chinese)

12 TONG J H, LI J B, JIANG H Y. Machine vision techniques for the evaluation of seedling quality based on leaf area[J]. Biosystems Engineering, 2013, 115(3): 369-379.

13 韓綠化, 毛罕平, 嚴蕾, 等. 穴盤育苗移栽機兩指四針鉗夾式取苗末端執(zhí)行器[J/OL]. 農(nóng)業(yè)機械學報, 2015, 46(7):23-30. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20150704&journal_id=jcsam. DOI:10.6041/j.issn.1000-1298.2015.07.004. HAN Lühua, MAO Hanping, YAN Lei, et al. Pincette-type end-effector using two fingers and four pins for picking up seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(7): 23-30. (in Chinese)

14 丁文芹, 毛罕平, 胡建平, 等. 穴盤苗自動移栽機的結(jié)構(gòu)設(shè)計及運動仿真分析[J]. 農(nóng)機化研究, 2011,33(10):75-77, 137. DING Wenqin, MAO Hanping, HU Jianping, et al. Structure design and simulation analysis on the plug seedlings auto-transplanter[J]. Journal of Agricultural Mechanization Research, 2011, 33(10):75-77, 137.(in Chinese)

15 馮青春, 王秀, 姜凱, 等. 花卉幼苗自動移栽機關(guān)鍵部件設(shè)計與試驗[J]. 農(nóng)業(yè)工程學報, 2013,29(6):21-27. FENG Qingchun, WANG Xiu, JIANG Kai, et al. Design and test of key parts on automatic transplanter for flower seedling[J]. Transactions of the CSAE, 2013, 29(6):21-27.(in Chinese)

16 楊揚, 曹其新, 盛國棟, 等. 基于機器視覺的育苗穴盤定位與檢測系統(tǒng)[J/OL]. 農(nóng)業(yè)機械學報, 2013, 44(6):232-235. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130640&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.06.040. YANG Yang, CAO Qixin, SHENG Guodong, et al. Plug tray localization and detection system based on machine vision[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(6): 232-235. (in Chinese)

17 楊振宇, 張文強, 李偉，等. 基于單目視覺的移栽缽苗葉片朝向的調(diào)整方法[J]. 農(nóng)業(yè)工程學報, 2014, 30(14): 26-33. YANG Zhenyu, ZHANG Wenqiang, LI Wei, et al. Monocular vision-based method for direction adjustment of transplanting potted-seedling leaves[J]. Transactions of the CSAE, 2014, 30(14): 26-33.(in Chinese)

18 孫國祥, 汪小旵, 何國敏. 基于邊緣鏈碼信息的番茄苗重疊葉面分割算法[J]. 農(nóng)業(yè)工程學報, 2010, 26(12): 206-211. SUN Guoxiang, WANG Xiaochan, HE Guomin. Segmentation algorithm of overlapping tomato seedling leaves based on edge chaincode information[J]. Transactions of the CSAE, 2010, 26(12): 206-211.(in Chinese)

19 韓綠化, 毛罕平, 繆小花, 等. 基于穴盤苗力學特性的自動取苗末端執(zhí)行器設(shè)計[J/OL]. 農(nóng)業(yè)機械學報, 2013, 44(11): 260-265. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20131144&journal_id=jcsam. DOI: 10.6041/j.issn.1000-1298.2013.11.044. HAN Lühua, MAO Hanping, MIAO Xiaohua, et al. Experiment on mechanical property of seedling pot for automatic transplanter[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013,44(11):260-265.(in Chinese)

20 張麗華, 邱立春, 田素博, 等. 指針夾緊式穴盤苗移栽爪設(shè)計[J]. 沈陽農(nóng)業(yè)大學學報, 2010, 41(2):235-237. ZHANG Lihua, QIU Lichun, TIAN Subo, et al. Design of a needle clamping claw for plug seedling transplanting[J]. Journal of Shenyang Agricultural University, 2010, 41(2): 235-237.(in Chinese)

21 童俊華, 蔣煥煜, 蔣卓華, 等. 缽苗自動移栽機器人抓取指針夾持苗坨參數(shù)優(yōu)化試驗[J]. 農(nóng)業(yè)工程學報, 2014, 30(16):8-16. TONG Junhua, JIANG Huanyu, JIANG Zhuohua, et al. Experiment on parameter optimization of gripper needles clamping seedling plug for automatic transplanter[J]. Transactions of the CSAE, 2014, 30(16): 8-16. (in Chinese)

22 金鑫, 杜新武, 楊傳華, 等. 蔬菜移栽穴盤苗自動輸送裝置設(shè)計與試驗[J/OL]. 農(nóng)業(yè)機械學報, 2016, 47(7): 103-111. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160715&journal_id=jcsam. DOI: 10.6041/j.issn.1000-1298.2016.07.015. JIN Xin, DU Xinwu, YANG Chuanhua, et al. Design and experiment on automatic transporting mechanism for vegetable potted seedlings[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(7): 103-111. (in Chinese)

23 趙雄, 王川, 楊茂祥, 等. 非圓齒輪行星輪系自動取苗機構(gòu)逆向設(shè)計分析[J]. 農(nóng)業(yè)工程學報, 2015, 31(6): 30-36. ZHAO Xiong, WANG Chuan, YANG Maoxiang, et al. Reverse design and analysis of automatic seedling pick-up mechanism with non-circular gear planetary train[J].Transactions of the CSAE, 2015, 31(6):30-36. (in Chinese)

24 俞高紅, 俞騰飛, 葉秉良, 等. 一種旋轉(zhuǎn)式穴盤苗取苗機構(gòu)的設(shè)計[J]. 機械工程學報, 2015, 51(7): 67-76. YU Gaohong, YU Tengfei, YE Bingliang, et al. Design of a rotary plug seedling pick-up mechanism[J]. Journal of Mechanical Engineering, 2015, 51(7): 67-76.(in Chinese)

25 HU Jianping, YAN Xiaoyue, MA Jun. Dimensional synthesis and kinematics simulation of a high-speed plug seedling transplanting robot[J]. Computers and Electronics in Agriculture, 2014, 107(3): 64-72.

26 童俊華, 蔣煥煜, 周鳴川. 基于遺傳算法的穴盤苗自動移缽路徑優(yōu)化[J/OL]. 農(nóng)業(yè)機械學報, 2013,44(4):45-49. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130408&journal_id=jcsam. DOI:10.6041/j.issn.1000-1298.2013.04.008. TONG Junhua, JIANG Huanyu, ZHOU Mingchuan. Optimization of seedling transplanting path based on genetic algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013,44(4):45-49.(in Chinese)

27 童俊華, 蔣煥煜, 武傳宇. 基于貪心算法的溫室缽苗稀植移栽路徑優(yōu)化[J/OL]. 農(nóng)業(yè)機械學報, 2016, 47(3):8-13. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160302&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2016.03.002. TONG Junhua, JIANG Huanyu, WU Chuanyu. Optimization of seedlings lower density transplanting path based on greedy algorithm[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(3):8-13.(in Chinese)

Optimization of Replugging Tour Planning Based on Greedy Genetic Algorithm

HE Leiying1,2YANG Taiwei1WU Chuanyu1,2YU Yaxin1,2TONG Junhua1,2CHEN Chengjin3
(1.FacultyofMechanicalEngineeringandAutomation,ZhejiangSci-TechUniversity,Hangzhou310018,China2.ZhejiangProvincialKeyLaboratoryofTransplantingEquipmentandTechnology,Hangzhou310018,China3.ZhejiangSanfengIndustrialCo.,Ltd.，Jinhua321300,China)

Replugging tasks make seedling in well consistency in greenhouses. Healthy seedlings are used to replace the ungerminated or poor growth seedlings. This task is labor intensive by traditional manual method. And automated transplanters do the replugging task in high efficiency and good quality. According to the seedlings healthy information which is detected by machine vision, end-effector grasping healthy seedlings does the repetitive replugging task. The position of vacancy holes in plug tray are randomly. Optimizing the seedling grasping sequence can decrease the transplanting path which can improve working efficiency. A greedy genetic algorithm (GGA) was proposed for replugging tour planning which combined the character of greedy algorithm (GAS) and genetic algorithm (GA). The algorithm was robustness. The GGA was suitable for sparse and dense trays’ path optimization when segmentation step value and hereditary algebra were 8 and 100, respectively. The average path deviation of GGA and GA was 443 mm. And their effectiveness was better than that of GAS. Compared with fixed sequence method (FS), the range of optimization amplitude for GGA was 33.8%～41.3%. GA and GGA could finish the optimization operation in 1.81 s and 5.59 s, respectively. The results showed that GGA was more suitable for the action requirement between delivery unit and transplanting unit. The working efficiency of automated transplanter was further improved.

automated transplanter; seedlings; greenhouses; path optimization; greedy genetic algorithm

2016-12-22

2017-02-17

國家自然科學基金項目(51675488)、浙江省自然科學基金項目(LQ16E050006)、浙江省科技廳公益項目(2017C32048)、浙江省重大科技專項重點農(nóng)業(yè)項目(2015C02004)和浙江理工大學科研啟動基金項目(14022211-Y)

賀磊盈(1983—)，男，講師，博士，主要從事農(nóng)業(yè)機器人技術(shù)研究，E-mail: hlying@zstu.edu.cn

武傳宇(1976—)，男，教授，博士生導(dǎo)師，主要從事智能農(nóng)業(yè)裝備研究，E-mail: cywu@zstu.edu.cn

10.6041/j.issn.1000-1298.2017.05.004

S24

A

1000-1298(2017)05-0036-08