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

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

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

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

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

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

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

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1 穴孔標(biāo)記和分段編碼

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

圖8 穴孔標(biāo)記示意圖Fig.8 Diagram of tray hole marker

對補(bǔ)苗穴盤的負(fù)標(biāo)記序列分段，以p為分段步長；若m≤p，則保持(-1,-2,…,-m)序列長不變；若m>p，m/p=u，余數(shù)為v,標(biāo)記序列可分段為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個負(fù)標(biāo)記與n個正標(biāo)記隨機(jī)交叉編碼，進(jìn)行該局部分段的遺傳算法路徑優(yōu)化；第2分段負(fù)標(biāo)記則與前次遺傳優(yōu)化后余下的正標(biāo)記進(jìn)行交叉編碼和遺傳優(yōu)化；依此執(zhí)行，直至負(fù)標(biāo)記的第u+1段。若v≠1，仍按遺傳優(yōu)化方法執(zhí)行，若v=1，則按貪心算法直接計算對最后1株補(bǔ)苗移栽的最短路徑。圖7所示模型，假設(shè)取p=4,則第1分段可隨機(jī)交替生成一條含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)化的目標(biāo)是尋找最短移栽路徑值，通過編碼染色體所映射的路徑長度來構(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)進(jìn)行有效搜索。針對補(bǔ)苗移栽路徑的編碼染色體具有正負(fù)交叉、基因不重復(fù)的特點(diǎn)，本文改進(jìn)了交叉操作方法，具體過程如下。

假設(shè)p=4,移栽穴盤的前4個待補(bǔ)苗孔穴和供苗穴盤的43株健康缽苗孔穴編碼可隨機(jī)產(chǎn)生移栽路徑，任選2條作交叉操作示例。A=(32，-3，25，-2，12，-4，9，-1)，B=(28，-1，32，-3，20，-2，16，-4)。隨機(jī)生成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，將其中相同的基因用不在該染色體中的其它基因隨機(jī)替換，可得A2=(32，-1，18，-3，12，-4，9，-2)，B2=(28，-3，25，-2，20，-1，16，-4)。通過以上交叉操作可擴(kuò)大搜索范圍，也保持了補(bǔ)苗路徑染色體的編碼要求。

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

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

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

3.2.4 重插入和算法終止

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

(4)該貪心遺傳算法對稀疏和密集穴盤路徑規(guī)劃運(yùn)算可在1.81 s內(nèi)完成，比全遺傳算法的5.59 s要短，更加有利于自動移栽機(jī)苗盤傳輸單元和移栽單元間的作業(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è)機(jī)械學(xué)報, 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)揮, 任燁, 等. 機(jī)器視覺在幼苗自動移缽作業(yè)中的應(yīng)用[J]. 農(nóng)業(yè)工程學(xué)報, 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 韓綠化, 毛罕平, 胡建平, 等. 穴盤苗自動移栽缽苗力學(xué)特性試驗(yàn)[J]. 農(nóng)業(yè)工程學(xué)報, 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è)大學(xué)學(xué)報, 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 孫國祥, 汪小旵, 何國敏, 等. 穴盤苗移栽機(jī)末端執(zhí)行器設(shè)計與虛擬樣機(jī)分析[J]. 農(nóng)業(yè)機(jī)械學(xué)報, 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 韓綠化, 毛罕平, 嚴(yán)蕾, 等. 穴盤育苗移栽機(jī)兩指四針鉗夾式取苗末端執(zhí)行器[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報, 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 丁文芹, 毛罕平, 胡建平, 等. 穴盤苗自動移栽機(jī)的結(jié)構(gòu)設(shè)計及運(yùn)動仿真分析[J]. 農(nóng)機(jī)化研究, 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 馮青春, 王秀, 姜凱, 等. 花卉幼苗自動移栽機(jī)關(guān)鍵部件設(shè)計與試驗(yàn)[J]. 農(nóng)業(yè)工程學(xué)報, 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 楊揚(yáng), 曹其新, 盛國棟, 等. 基于機(jī)器視覺的育苗穴盤定位與檢測系統(tǒng)[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報, 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 楊振宇, 張文強(qiáng), 李偉，等. 基于單目視覺的移栽缽苗葉片朝向的調(diào)整方法[J]. 農(nóng)業(yè)工程學(xué)報, 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è)工程學(xué)報, 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 韓綠化, 毛罕平, 繆小花, 等. 基于穴盤苗力學(xué)特性的自動取苗末端執(zhí)行器設(shè)計[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報, 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è)大學(xué)學(xué)報, 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 童俊華, 蔣煥煜, 蔣卓華, 等. 缽苗自動移栽機(jī)器人抓取指針夾持苗坨參數(shù)優(yōu)化試驗(yàn)[J]. 農(nóng)業(yè)工程學(xué)報, 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è)計與試驗(yàn)[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報, 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 趙雄, 王川, 楊茂祥, 等. 非圓齒輪行星輪系自動取苗機(jī)構(gòu)逆向設(shè)計分析[J]. 農(nóng)業(yè)工程學(xué)報, 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)式穴盤苗取苗機(jī)構(gòu)的設(shè)計[J]. 機(jī)械工程學(xué)報, 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è)機(jī)械學(xué)報, 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è)機(jī)械學(xué)報, 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

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

賀磊盈(1983—)，男，講師，博士，主要從事農(nóng)業(yè)機(jī)器人技術(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