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

徐守江，羅竹青

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

0 引言

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

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

1 混合蛙跳算法基本模型

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

1.1 基本概念

1.2 局部搜索

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

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

(1)

Xnew=Xw+D

(2)

新產生的青蛙個體Xnew，其適應度值若優于Xw，則用Xnew替換Xw；否則利用Xg代替Xb重復執行式(1)、式(2)一次，若新產生的青蛙個體Xnew仍不優于Xw，則隨機產生一個新青蛙個體替換Xw。

1.3 全局信息交換

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

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

2.1 移缽路徑規劃問題描述

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

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

圖1 健康缽苗補種移缽作業示意圖Fig.1 Healthy seedling plant transplanting diagram

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

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

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

2.3 子族群構建方法

青蛙群體按照1.1節中的規則劃分為若干族群后，為了避免過早陷入局部最優，需在族群內生成一個子族群來進行局部搜索。每個族群中的青蛙個體按照概率Pi被選擇生成子族群，則有

(3)

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

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

現針對圖1環境來描述局部搜索，待補種穴孔數目M為4，可移栽穴苗數N為36。假設某子族群內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的目的穴孔集合執行交換操作，移栽穴孔集合執行交叉操作。

2.4.1 交換序

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

2.4.2 交換操作

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

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

(4)

Xqgoal=Xwgoal+C

(5)

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

2.4.3 交叉策略

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

圖2 交叉操作Fig.2 Crossover operation

2.4.4 局部搜索

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

2.5 算法流程

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

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

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

3)按照適應度值降序排列各青蛙個體，并構造m個族群。

4)按照3.3節方法產生子族群，在每個子族群內按照3.4節的方法進行局部搜索。

5)當局部搜索到達一定迭代次數Count，則混合全部族群，根據適應度值更新全局最優個體，Gcount值自動增1。

6)根據Gcount值判斷算法是否終止，若否則轉3)。最終，全局最優青蛙個體所表示的解即為規劃出的移缽優化路徑。

3 仿真實驗

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

圖3 4個待補種穴盤自動移缽路徑Fig.3 Path planned with 4 vacancy cells

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

圖4 10個待補種穴盤自動移缽路徑Fig.4 Path planned with 10 vacancy cells表1 不同算法移缽路徑優化長度對比Table 1 Comparison of optimized length of different algorithms

序號固定順序法/mm蟻群算法/mm本文算法/mm優化比例/%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 蛙跳算法自動移缽路徑規劃收斂曲線Fig.5 Frog leaping algorithm automatic path planning convergence curve

4 結論

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