基于鄰域搜索的穴盤苗移缽路徑優(yōu)化蛙跳算法

徐守江，羅竹青

(江蘇食品藥品職業(yè)技術(shù)學(xué)院 a.信息工程學(xué)院;b.校企合作辦公室，江蘇 淮安 223003)

0 引言

在穴盤苗培育過程中，常出現(xiàn)穴盤內(nèi)育苗不成功的情況，主要是由于漏栽和缽苗發(fā)育不正常引起，成苗率在90%左右[1]。機(jī)械化批量移栽近年來被廣泛應(yīng)用于補(bǔ)苗環(huán)節(jié)，農(nóng)業(yè)缽苗移栽機(jī)器人通過視覺檢測出不健康缽苗，將不健康缽苗剔除后通過機(jī)械臂帶動(dòng)末端執(zhí)行器完成補(bǔ)種作業(yè)[2]。補(bǔ)種作業(yè)是將移栽穴盤中的部分健康缽苗逐一依次補(bǔ)種到目的穴盤中，移缽距離的長短由補(bǔ)種順序直接決定；而目的穴盤中待補(bǔ)種穴盤位置與移栽穴盤可移栽缽苗位置均存在不確定性與多選擇性，可選擇的移缽路徑隨待補(bǔ)種穴盤數(shù)和可移栽缽苗數(shù)呈指數(shù)級增長。兩穴盤中的孔穴位置距離固定，移栽路徑越短，工作效率越高。遍歷算法的排列組合式解法由于計(jì)算機(jī)的運(yùn)行速度和存儲容量限制無法在實(shí)際應(yīng)用中得到推廣。目前，工程上采用的移缽方法主要是固定順序法，該方法按照固定順序的方式進(jìn)行移栽，移缽路徑未經(jīng)過優(yōu)化。自動(dòng)移缽問題類似于旅行商問題，但移缽問題需要交叉選擇移栽穴盤與目點(diǎn)穴盤的孔穴且移栽穴盤無需遍歷。近年來，諸多學(xué)者將遺傳算法、蟻群算法和貪心算法成功應(yīng)用于移缽路徑的優(yōu)化[3-5]，有效縮短移缽路徑，提高了移缽效率。文獻(xiàn)[3-4]中的算法均存在搜索空間大以及收斂速度慢等問題，增加了搜索時(shí)間。文獻(xiàn)[5]的貪心算法實(shí)時(shí)性能好，能在有效時(shí)間內(nèi)規(guī)劃出優(yōu)化路徑，但優(yōu)化的路徑仍有待于進(jìn)一步提升。

2003年，Muzaffar Eusuff 和Kevin Lansey提出了混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)，并成功應(yīng)用于水資源網(wǎng)絡(luò)優(yōu)化問題[6]。蛙跳算法作為一種新的仿生算法逐步應(yīng)用于機(jī)器人路徑規(guī)劃[7-8]、旅行商問題[9-10]及函數(shù)優(yōu)化[11]等，主要用于解決組合優(yōu)化問題，具有算法簡單、調(diào)整參數(shù)少及尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)。本文基于混合蛙跳算法，針對穴盤苗自動(dòng)移缽問題提出了局部分塊搜索策略，融入交換因子、交換序和交叉操作等思想。同時(shí)，由于自動(dòng)移缽問題的特殊性，在選擇移栽穴盤時(shí)引入鄰域搜索策略，有效限制搜索空間，較好地解決了本文路徑規(guī)劃問題。仿真實(shí)驗(yàn)表明，本文算法能有效規(guī)劃出較優(yōu)化移缽路徑。

1 混合蛙跳算法基本模型

混合蛙跳算法是模擬青蛙覓食過程的一種基于群體的智能協(xié)同仿生算法。青蛙群體在尋找食物過程中通過局部搜索和全局信息交換來進(jìn)行信息傳遞。在信息交流初期將初始青蛙種群劃分為若干個(gè)族群，在每個(gè)族群內(nèi)部執(zhí)行局部搜索策略，實(shí)現(xiàn)族群內(nèi)青蛙個(gè)體之間文化的交流。局部搜索每執(zhí)行一段時(shí)間后，混合所有青蛙個(gè)體實(shí)現(xiàn)全局信息交換，并對青蛙群體重新劃分族群再次進(jìn)行局部搜索。重復(fù)上述過程，直至收斂的條件滿足為止。

1.1 基本概念

1.2 局部搜索

局部搜索的目的是使得各族群內(nèi)個(gè)體在不同的方向上搜索局部最優(yōu)，同時(shí)使得局部最優(yōu)個(gè)體逐步向全局最優(yōu)個(gè)體搜索。將青蛙群體劃分為m個(gè)族群后，為了避免局部搜索過早陷入局部最優(yōu)，在每個(gè)族群內(nèi)按照一定的選擇方法選取若干青蛙個(gè)體組成子族群進(jìn)行局部搜索。假設(shè)全局最優(yōu)青蛙個(gè)體為Xg，子族群內(nèi)的最優(yōu)青蛙個(gè)體為Xb,最差個(gè)體為Xw。子族群內(nèi)的最差個(gè)體Xw更新策略為

D=rand( )×(Xb-Xw),rand( )∈(0,1),
D∈[Dmin,Dmax]

(1)

Xnew=Xw+D

(2)

新產(chǎn)生的青蛙個(gè)體Xnew，其適應(yīng)度值若優(yōu)于Xw，則用Xnew替換Xw；否則利用Xg代替Xb重復(fù)執(zhí)行式(1)、式(2)一次，若新產(chǎn)生的青蛙個(gè)體Xnew仍不優(yōu)于Xw，則隨機(jī)產(chǎn)生一個(gè)新青蛙個(gè)體替換Xw。

1.3 全局信息交換

當(dāng)所有子族群經(jīng)過一定次數(shù)的局部搜索后，混合所有青蛙個(gè)體按照適應(yīng)度值重新排序，根據(jù)族群劃分規(guī)則重新生成族群，再次執(zhí)行局部搜索操作，重復(fù)上述的局部搜索與全局信息交換直至滿足收斂條件。全局信息交換便于各個(gè)族群內(nèi)的信息交流，青蛙個(gè)體間的信息得到充分傳遞，便于青蛙個(gè)體尋找新的全局最優(yōu)解搜索方向。

2 基于鄰域搜索策略的移缽路徑優(yōu)化蛙跳算法

2.1 移缽路徑規(guī)劃問題描述

工程上農(nóng)業(yè)缽苗自動(dòng)化移缽樣機(jī)由4部分組成，分別為識別系統(tǒng)、控制系統(tǒng)、輸送系統(tǒng)和移缽系統(tǒng)，通過4個(gè)子系統(tǒng)間的協(xié)作有效完成目的穴盤不健康缽苗識別與剔除及移栽穴盤中健康穴苗的移缽與補(bǔ)種作業(yè)。圖1為移栽穴盤和目的穴盤外圍尺寸均為250mm×500mm、規(guī)格大小均為50的移缽工作示意圖。圖1中：白色小圓圈表示空的穴孔，即在目的穴盤中表示待移栽穴孔，移栽穴盤中表示當(dāng)前穴孔不存在可移栽缽苗；灰色和黑色小圓圈均表示目的穴盤或移栽穴盤中的當(dāng)前穴孔存在健康缽苗。

建立直角坐標(biāo)系XOY，移栽缽苗主要是指機(jī)械臂帶動(dòng)末端執(zhí)行器從原點(diǎn)O出發(fā)，逐一選取移栽穴盤中的健康缽苗并補(bǔ)種到目的穴盤中的待補(bǔ)種穴孔，如此反復(fù)不斷執(zhí)行補(bǔ)種作業(yè)直至目的穴盤中無空穴存在，最終返回原點(diǎn)O，圖1中的路徑即為一次移栽路徑。為了便于表示移栽路徑信息，將目的穴盤中的M個(gè)待補(bǔ)種穴孔依次編號為(-1，-2，-3，…，-M)，移栽穴盤中的含可移栽健康缽苗的N個(gè)穴孔編碼依次為(1，2，3,…，N)，編號順序均為從上往下、從左到右。圖1中，移缽路徑序列則可線性表示為{0，11，-4，3，-3，4，-2，9，-1，0}。

圖1 健康缽苗補(bǔ)種移缽作業(yè)示意圖Fig.1 Healthy seedling plant transplanting diagram

由于移缽路徑選擇的多樣性，本文基于混合蛙跳算法創(chuàng)新自動(dòng)移缽路徑優(yōu)化新方法，將蛙跳算法的思想有效融入該問題的解決，針對移缽問題提出初始族群的產(chǎn)生、子族群的構(gòu)建和局部搜索等改進(jìn)措施。

2.2 基于鄰域搜索策略初始化青蛙個(gè)體

初始化青蛙個(gè)體時(shí)，從原點(diǎn)O出發(fā)交叉選擇移栽穴盤和目的穴盤，直到遍歷所有目的穴盤，最終回到原點(diǎn)O。由于移缽問題的特殊性，在選擇移栽穴盤序號時(shí)采用鄰域搜索策略，僅從目的穴盤中待補(bǔ)種穴盤位置的移栽穴盤Neighbor域中進(jìn)行選擇。其中，移栽穴盤Neighbor域包含了移栽穴盤中的各可選擇穴盤到目的穴盤中所有待補(bǔ)種的穴盤距離之和最小的前Q個(gè)點(diǎn)(M≤Q≤N)。,在圖1中，Q=8，填充為黑色的穴孔表示當(dāng)前目的穴盤的可移栽穴盤Neighbor域，即可選擇的移栽穴盤序號限定在集合{1，2，3，4，9，10，11，12}中。圖1中的路徑即為初始化過程中產(chǎn)生的一條移缽路徑。

2.3 子族群構(gòu)建方法

青蛙群體按照1.1節(jié)中的規(guī)則劃分為若干族群后，為了避免過早陷入局部最優(yōu)，需在族群內(nèi)生成一個(gè)子族群來進(jìn)行局部搜索。每個(gè)族群中的青蛙個(gè)體按照概率Pi被選擇生成子族群，則有

(3)

2.4 基于交換序與交叉策略的局部搜索

在子族群中Xb表示局部最優(yōu)解，Xw表示局部最差解，一個(gè)青蛙個(gè)體由目的穴盤中的穴孔序號與移栽穴盤中的穴孔序號交叉排列。其中，目的穴盤中的穴孔序號包括了所有的待補(bǔ)種的穴孔位置，而青蛙個(gè)體中的移栽穴孔序號僅為部分可移栽穴孔序號。根據(jù)青蛙個(gè)體的特殊性，將一個(gè)青蛙個(gè)體分塊向局部最優(yōu)解方向進(jìn)行搜索。

現(xiàn)針對圖1環(huán)境來描述局部搜索，待補(bǔ)種穴孔數(shù)目M為4，可移栽穴苗數(shù)N為36。假設(shè)某子族群內(nèi)Xb={0,1，-1，9，-2，2，-4，4，-3，0},Xw={0，11，-4，3，-3，4，-2，9，-1，0}，Xw如圖1中路徑所示。將Xb分割為移栽穴孔集合Xbmove={1，9，2，4}和目的穴孔集合Xbgoal={-1，-2，-4，-3}，而Xw分割為Xwmove={11，3，4，9}和Xwgoal={-4,-3,-2,-1}。針對Xb與Xw的目的穴孔集合執(zhí)行交換操作，移栽穴孔集合執(zhí)行交叉操作。

2.4.1 交換序

將某個(gè)目的穴孔集合的穴孔序號i與穴孔序號j交換的操作定義為一個(gè)交換因子，記為CH(i,j)，如，{-1，-2，-4，-3}+CH(-1,-4)={-4,-2,-1,-3}。交換序是由一個(gè)或多個(gè)交換因子組成的序列?，F(xiàn)有{-1，-2，-4，-3}+CH(-1,-4)+CH(-2,-3)+CH(-1,-2)={-4，-3，-2，-1}，則Xwgoal向Xbgoal轉(zhuǎn)換時(shí)的交換序?yàn)閧CH(-1,-4),CH(-2,-3),CH(-1,-2)},記為CS(XwgoalΘXbgoal)，其中交換序的長度為3。

2.4.2 交換操作

將Xwgoal向Xbgoal轉(zhuǎn)換時(shí)的交換序CS(XwgoalΘXbgoal)的長度記為Length(CS(XwgoalΘXbgoal))，則Xwgoal向Xbgoal變換時(shí)的交換操作可定義為

C= {CHi|CHi∈CS(XwgoalΘXbgoal),i=1,2,…,l}

(4)

Xqgoal=Xwgoal+C

(5)

其中，l為[0,length(CS(XwgoalΘXbgoal))]間的隨機(jī)整數(shù)，C為更新Xwgoal的交換序。若l=0則不執(zhí)行交換操作，青蛙個(gè)體目的穴盤序號不變，即Xqgoal直接等于Xwgoal；否則按照式(4)、式(5)進(jìn)行交換操作產(chǎn)生新的Xqgoal。

2.4.3 交叉策略

針對可移栽穴孔集合Xbmove與Xwmove在[0，4]之間隨機(jī)產(chǎn)生一個(gè)整數(shù)j作為交叉點(diǎn)，若j等于0時(shí)不作交叉，若j等于4則兩集合互換，否則交叉操作如圖2所示。其中，j=2。交叉過程中若新個(gè)體出現(xiàn)重復(fù)的穴盤序號，則在Neighbor域可選范圍內(nèi)重新隨機(jī)生成一個(gè)新的穴盤序號替換其中一個(gè)重復(fù)的穴盤序號。

圖2 交叉操作Fig.2 Crossover operation

2.4.4 局部搜索

將Xqgoal分別與Xq1move、Xq2move合并后產(chǎn)生兩個(gè)新青蛙個(gè)體，取其中適應(yīng)度值較大的一個(gè)Xnew與Xw比較，若適應(yīng)度值f(Xnew)大于f(Xw)則更新青蛙個(gè)體，否則利用全局最優(yōu)個(gè)體Xg代替Xb重復(fù)執(zhí)行上述交換與交叉操作；若產(chǎn)生的青蛙個(gè)體Xnew仍不優(yōu)于Xw，則根據(jù)初始化要求隨機(jī)產(chǎn)生一個(gè)新青蛙個(gè)體替換Xw。

2.5 算法流程

基于以上思想，本文算法流程如下：

1)初始化算法參數(shù)。設(shè)置青蛙個(gè)體的種群大小為F，各族群內(nèi)青蛙個(gè)數(shù)為n，族群個(gè)數(shù)為m，子族群內(nèi)青蛙個(gè)數(shù)為k，局部更新迭代次數(shù)Count，全局搜索迭代次數(shù)為Gcount。

2)基于鄰域搜索策略初始化各青蛙個(gè)體，生成F個(gè)可行解，計(jì)算其適應(yīng)度值。

3)按照適應(yīng)度值降序排列各青蛙個(gè)體，并構(gòu)造m個(gè)族群。

4)按照3.3節(jié)方法產(chǎn)生子族群，在每個(gè)子族群內(nèi)按照3.4節(jié)的方法進(jìn)行局部搜索。

5)當(dāng)局部搜索到達(dá)一定迭代次數(shù)Count，則混合全部族群，根據(jù)適應(yīng)度值更新全局最優(yōu)個(gè)體，Gcount值自動(dòng)增1。

6)根據(jù)Gcount值判斷算法是否終止，若否則轉(zhuǎn)3)。最終，全局最優(yōu)青蛙個(gè)體所表示的解即為規(guī)劃出的移缽優(yōu)化路徑。

3 仿真實(shí)驗(yàn)

為了便于比較，采用文獻(xiàn)[3-4]中的實(shí)例進(jìn)行一組實(shí)驗(yàn)。由于本文算法在青蛙個(gè)體生成過程中，針對移缽問題的特殊性采取了鄰域搜索策略，搜索空間大大減少，算法性能顯著提升。圖3的實(shí)例中設(shè)定Neighbor搜索域大小為8，Neighbor域中的穴孔在圖中用填充為黑色的圓圈表示。圖3中顯示的路徑為本文算法獲得的最優(yōu)化路徑，路徑長度為2 913.892。連續(xù)運(yùn)行10次中9次獲得全局最優(yōu)解，平均路徑長度為2 915.6，路徑優(yōu)化結(jié)果優(yōu)于文獻(xiàn) [3-4] 中的結(jié)果。

圖3 4個(gè)待補(bǔ)種穴盤自動(dòng)移缽路徑Fig.3 Path planned with 4 vacancy cells

假設(shè)目的穴盤中待補(bǔ)種穴盤個(gè)數(shù)為10，移栽穴盤與圖3中的移栽穴盤一樣，如圖4所示。在目的穴盤中分10次隨機(jī)生成10個(gè)待補(bǔ)種穴盤，使用本文算法規(guī)劃出的自動(dòng)移缽路徑長度如表1所示。其中，Neighbor域中的可移栽穴盤數(shù)量設(shè)置為20。與文獻(xiàn)[4]中的固定順序法和蟻群算法進(jìn)行比較，可以看出：本文算法較固定順序法優(yōu)化比例在8%以上，表1中最后一列優(yōu)化比例指的是本文算法較固定順序法優(yōu)化的比例；同時(shí)，本文算法性能比蟻群算法更優(yōu)(迭代次數(shù)均設(shè)定為500)。其中，序號為1的蛙跳算法自動(dòng)移缽路徑規(guī)劃結(jié)果如圖4所示，收斂曲線如圖5所示。從收斂曲線上看，本文算法初始化時(shí)產(chǎn)生的全局最優(yōu)路徑為7 780.316，比固定順序法產(chǎn)生的路徑8 189.573已經(jīng)更加優(yōu)化。

圖4 10個(gè)待補(bǔ)種穴盤自動(dòng)移缽路徑Fig.4 Path planned with 10 vacancy cells表1 不同算法移缽路徑優(yōu)化長度對比Table 1 Comparison of optimized length of different algorithms

序號固定順序法/mm蟻群算法/mm本文算法/mm優(yōu)化比例/%18189.5737167.9207136.26912.8627390.9686677.5796642.19410.1338129.7356953.7686940.73414.6347809.2546943.0356928.52411.2858645.9307726.7507620.55811.8667728.3906755.0956692.33913.4178092.6676868.1876841.08515.4787579.0437007.3506954.7818.2498416.6056771.1396679.70320.64108150.8417269.6007233.41211.26

圖5 蛙跳算法自動(dòng)移缽路徑規(guī)劃收斂曲線Fig.5 Frog leaping algorithm automatic path planning convergence curve

4 結(jié)論

針對穴盤苗自動(dòng)移缽路徑規(guī)劃問題，基于混合蛙跳算法提出了融入交換序和交叉操作的局部搜索方法，較好地解決了移缽問題的路徑優(yōu)化問題。本文算法具有魯棒性好、實(shí)時(shí)性能強(qiáng)、易實(shí)現(xiàn)等特點(diǎn)。本文算法在解的生成過程中引入鄰域搜索策略，在一定的鄰域內(nèi)選擇移栽穴盤，大大縮小了解的搜索空間，提高了算法性能，與固定順序法、遺傳算法和蟻群算法等相比能較好地獲得更優(yōu)化路徑，算法收斂性能好。