謝忠紅，王 培，顧寶興，姬長(zhǎng)英，田光兆

(1 南京農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南京 210095； 2 江蘇省智能化農(nóng)業(yè)裝備重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210031)

基于分組和精英策略的遺傳算法在機(jī)器人導(dǎo)航上的應(yīng)用

謝忠紅1，王 培1，顧寶興2，姬長(zhǎng)英2，田光兆2

(1 南京農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南京 210095； 2 江蘇省智能化農(nóng)業(yè)裝備重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210031)

【目的】針對(duì)種植園復(fù)雜環(huán)境下采摘機(jī)器人進(jìn)行路徑規(guī)劃時(shí)找出多路徑效率低、速度慢等問(wèn)題，提出一種基于分組和精英策略的遺傳算法(GGABE)?！痉椒ā渴紫壬?個(gè)初始群體，使用Sigmoid函數(shù)分組；然后在每組中分別進(jìn)行選擇、交叉、變異操作，進(jìn)行n代迭代后，每組產(chǎn)生該組內(nèi)的k條等長(zhǎng)的最優(yōu)路徑；比較各組最優(yōu)路徑，選擇最短的路徑作為最優(yōu)路徑。在種群的各項(xiàng)參數(shù)均相同的情況下，簡(jiǎn)單遺傳算法(SGA)、未分組的精英遺傳算法(EGA)以及GGABE分別作用于15×15和25×25的地圖，各進(jìn)行 50 次試驗(yàn)。進(jìn)行樣機(jī)驗(yàn)證試驗(yàn)?！窘Y(jié)果】第 1 幅地圖，GGABE算法找到了 8 條最短路徑，路徑均值為 20.970 6，其他 2 種方法只能找出 1 條最短路徑；第 2 幅地圖，GGABE算法找到了 8 條最短路徑，路徑均值為 38.041 6。50次驗(yàn)證試驗(yàn)均找出 3 條最佳路徑，平均路徑規(guī)劃時(shí)間為 15.543 319 s?！窘Y(jié)論】本研究提出的基于分組和精英策略的遺傳算法收斂速度快，可快速準(zhǔn)確地在地圖中搜索出所有能夠遍歷整個(gè)果園的最佳路徑。

分組；精英策略；采摘機(jī)器人；遺傳算法；優(yōu)勢(shì)個(gè)體；路徑規(guī)劃；導(dǎo)航

導(dǎo)航技術(shù)是采摘機(jī)器人研究領(lǐng)域中的關(guān)鍵技術(shù)，而路徑規(guī)劃則是導(dǎo)航研究課題中的重中之重，路徑規(guī)劃是指采摘機(jī)器人基于已給出的種植園地圖，滿(mǎn)足不碰撞障礙物的前提下，計(jì)算出一條從起點(diǎn)到終點(diǎn)的最短路徑或耗時(shí)最少的路徑[1-2]。張毅等[1]在遺傳算法中新增了插入算子將間斷路徑轉(zhuǎn)化為連續(xù)路徑，刪除算子用于刪除路徑中的冗余序號(hào)；盧月品等[2]使用Dijkstra算法找出1條可行、最短但不保證精度和安全性的路徑，然后采用改進(jìn)的遺傳算法提高路徑精度；張超等[3]結(jié)合混沌粒子群算法和遺傳算法，提出了基于粒子群-遺傳算法切換策略的路徑規(guī)劃方法；Kala[4]提出了在1張地圖中使用多個(gè)機(jī)器人共同尋找最佳路徑，由其中的某個(gè)主機(jī)器人協(xié)調(diào)它們之間的合作關(guān)系；Masoud等[5]提出了六邊形環(huán)境建模法，可以在較短的時(shí)間內(nèi)找出全局最佳路徑；Yun等[6]為了提高搜索效率，在產(chǎn)生初始種群時(shí)，引入了障礙物避免算法(OAA)和區(qū)分算法(DA)；Mohanta等[7]在Petri網(wǎng)中引入了遺傳算法，該算法基于一種迭代的、非線(xiàn)性搜索操作，能夠充分利用環(huán)境的幾何信息，產(chǎn)生適宜的航線(xiàn)角度。

已有的算法改進(jìn)主要研究如何提高收斂速度，較少涉及從地圖中獲取多條最佳路徑的問(wèn)題；當(dāng)搜索空間很大時(shí)，如何快速收斂到全局最優(yōu)路徑附近也是一個(gè)難題。針對(duì)這些問(wèn)題，本文提出了一種基于分組和精英策略的遺傳算法，以期快速、有效地獲取地圖中的所有最佳路徑。

1 基于分組的改進(jìn)遺傳算法

基于Sigmoid函數(shù)對(duì)搜索空間分組后，在每組獨(dú)立進(jìn)行遺傳操作，每一代適應(yīng)度值最高的個(gè)體即為精英個(gè)體，將其完整保留到下一代中，并參與到每個(gè)個(gè)體的交叉和變異。

1.1 地圖生成及編碼

為了便于采摘機(jī)器人的移動(dòng)，種植園中果樹(shù)要求分布規(guī)則且間距較大(＞5 m)，而移動(dòng)中的機(jī)器人機(jī)械手處于收攏狀態(tài)，所占區(qū)域長(zhǎng)寬在[1.0 m, 1.5 m]內(nèi)，因此可將機(jī)器人視為質(zhì)點(diǎn)。柵格法生成的種植園地圖如圖1所示，圖1中的帶箭頭的線(xiàn)段表示1條路徑。初始化群體可采用2種編碼方式：坐標(biāo)法和序號(hào)法。坐標(biāo)法和序號(hào)法的轉(zhuǎn)換關(guān)系分別如下，其中x為橫坐標(biāo)，y為縱坐標(biāo)，z為序號(hào)。

圖1 坐標(biāo)法和序號(hào)法表示的地圖Fig. 1 Map indicated by coordinate and order

1.2 分組

對(duì)地圖空間進(jìn)行分組，使得種群在每組中分別進(jìn)行遺傳操作，其中分組數(shù)(k)是關(guān)鍵。k太大，適應(yīng)度高的個(gè)體及其后代會(huì)很容易替代其他個(gè)體，導(dǎo)致陷入局部收斂；k太小，無(wú)法體現(xiàn)分組的優(yōu)勢(shì)[8-9]。

人為指定法分組：根據(jù)經(jīng)驗(yàn)給出1個(gè)可行的分組數(shù)，缺點(diǎn)是主觀差異大。動(dòng)態(tài)分組法：分組數(shù)隨著種群的進(jìn)化不斷動(dòng)態(tài)變化。初始時(shí)種群中的個(gè)體呈隨機(jī)分布，差異大，k取較大值；隨著種群的進(jìn)化，個(gè)體差異變小，逐漸收斂于n條最佳路徑(n≥1)，此時(shí)k隨之變小。研究中k遵循Sigmoid函數(shù)[10]，并結(jié)合了粗粒度并行遺傳算法[11-12]。

式中，g為初始分組數(shù)(5～8)，t為進(jìn)化代數(shù)，μ是調(diào)整參數(shù)，一般取值為2。

首先初始化隨機(jī)種群，設(shè)種群規(guī)模大小為n，即共有n條路徑，po={pa1, pa2, …, pai…, pan}，po表示種群空間，pai表示第i個(gè)個(gè)體。初始設(shè)進(jìn)化代數(shù)t=0，g=8，根據(jù)公式計(jì)算出分組數(shù)k=6。將種群空間po依次平均分為k組子種群，前k–1組子種群中，每個(gè)子種群有av=■n/k」個(gè)個(gè)體，最后1個(gè)子種群有[n?(k?1)av]個(gè)個(gè)體，分組后的種群空間po={{pa1,在每組中依次進(jìn)行遺傳操作，可以避免早熟收斂。

每進(jìn)化1代執(zhí)行遺傳操作之前，在空間po中按■照一■定概率pswap，每2組之間隨機(jī)交換個(gè)個(gè)體，即第1組和第2組，···，第k組隨機(jī)交換個(gè)體，若k為奇數(shù)，則最后一組保持不變。通過(guò)引入新的個(gè)體，增加了每個(gè)子種群的多樣性，避免了局部收斂；同時(shí)，每個(gè)子種群在搜索空間的不同部分分別進(jìn)化，加強(qiáng)了全局搜索能力。

經(jīng)過(guò)觀察發(fā)現(xiàn)，當(dāng)t∈[0, 5]時(shí)，分組數(shù)k均為6；當(dāng)t∈[6, 10]時(shí)，k為5；當(dāng) t∈[11, 19]時(shí)，k為4；當(dāng)t∈[20, 66]時(shí)，k為3；隨著種群的進(jìn)化，最后分組數(shù)k穩(wěn)定為2。也就是說(shuō)，種群在第6、11、20、67代時(shí)會(huì)按照上述方法重新進(jìn)行分組，而在其他代數(shù)時(shí)，采用上一代的分組結(jié)果。

1.3 適應(yīng)度函數(shù)

根據(jù)給定的目標(biāo)函數(shù)，計(jì)算適應(yīng)度值。最優(yōu)路徑滿(mǎn)足以下準(zhǔn)則：無(wú)碰撞；路徑長(zhǎng)度最短。碰撞函數(shù)f(ro)的公式為：

式中，ro指序號(hào)法表示的路徑。

路徑長(zhǎng)度函數(shù)l(rc)的公式為：

式中，rc指坐標(biāo)法表示的路徑；為路徑上相鄰的方格；n為路徑上的方格數(shù)。

移動(dòng)路徑的評(píng)價(jià)函數(shù)g(r)公式為：

式中，C是放大系數(shù)；τ 是1個(gè)極小值。

顯然當(dāng)碰到障礙物時(shí)，適應(yīng)度值低，繁殖后代的概率小。

1.4 遺傳算子

精英個(gè)體指的是當(dāng)前種群中適應(yīng)度值最高的個(gè)體[13]，可能不止一個(gè)。種群中精英個(gè)體和全局最優(yōu)解之間的“血緣關(guān)系”要大于其他個(gè)體和全局最優(yōu)解的“血緣關(guān)系”，所以要充分利用精英個(gè)體中的遺傳信息。本文結(jié)合精英保留策略和輪賭盤(pán)操作選擇個(gè)體，將每組中的精英個(gè)體不加改變地保留到下一代，并參與每個(gè)交叉和變異操作。根據(jù)交叉概率Pc，在選擇后的個(gè)體中進(jìn)行交叉操作。采用單點(diǎn)交叉，在2個(gè)父本中相同點(diǎn)(起點(diǎn)和終點(diǎn)除外)前后交換。如2條路徑分別為(0, 11, 12, 23, 34, 44)和(0, 10, 11, 22, 33, 44)，都經(jīng)過(guò)方格11，在該點(diǎn)前后交叉，交叉后為(0, 10, 11, 12, 23, 34, 44)和(0, 11, 22, 33, 44)。若2條路徑(除起點(diǎn)和終點(diǎn)外)沒(méi)有相同點(diǎn)，則不交叉；有多個(gè)相同點(diǎn)，隨機(jī)選取一個(gè)作為基準(zhǔn)點(diǎn)，進(jìn)行交叉。交叉的父本之一必須是上一代的最優(yōu)值，這樣能保護(hù)種群的精英個(gè)體，加快收斂速度。隨機(jī)產(chǎn)生1個(gè)0～1之間的數(shù)w，若w小于變異概率pm，則進(jìn)行變異操作，采用偏移節(jié)點(diǎn)方法[4]。首先，在待變異個(gè)體上任選一點(diǎn)(xi, yi)，其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)分別為(xi-1, yi-1)和(xi+1, yi+1)；然后，設(shè)置1個(gè)半徑常數(shù)r，并在0～360之間取隨機(jī)數(shù)θ，變異后的節(jié)點(diǎn)為(xi′, yi′)，公式為：

連接(xi-1, yi-1)和(xi′, yi′)、(xi′, yi′)和(xi+1, yi+1)，判斷其是否經(jīng)過(guò)障礙物，若經(jīng)過(guò)，則舍棄該節(jié)點(diǎn)，重新生成一個(gè)節(jié)點(diǎn)并判斷，直到滿(mǎn)足條件為止；否則，用新節(jié)點(diǎn)替換舊節(jié)點(diǎn)。

2 算法收斂性分析

已知定理1：若隨機(jī)過(guò)程或系統(tǒng)在t0時(shí)刻所處的狀態(tài)已知，在t＞t0時(shí)刻所處的條件分布與t0之前所處的狀態(tài)無(wú)關(guān)，則該過(guò)程或系統(tǒng)稱(chēng)為馬爾科夫鏈[14]。

根據(jù)定理1得出結(jié)論 1：GGABE算法的種群序列{Xt,t≥0}是齊次馬爾科夫鏈，其中t表示進(jìn)化代數(shù)。證明如下：GGABE遺傳算法中的選擇、交叉、變異操作都是獨(dú)立進(jìn)行的，且每個(gè)子代都是由父代通過(guò)遺傳操作得到的，與父代之前的個(gè)體無(wú)關(guān)。所以GGABE算法是齊次馬爾科夫鏈。

結(jié)論 2：GGABE算法具有全局收斂性。證明如下：設(shè)S為種群狀態(tài)空間，sk表示第k代最優(yōu)解對(duì)應(yīng)的適應(yīng)度值，pk為得到最優(yōu)值sk的概率，pk＞0，很顯然，隨著進(jìn)

化過(guò)程的推進(jìn)，第k+1代最優(yōu)解的適應(yīng)度值一定大于等于第k代最優(yōu)解的適應(yīng)度值，因此S空間是一個(gè)單調(diào)非遞減的有序空間。pi,j表示由狀態(tài)si遷移到狀態(tài)sj的概率，由于GGABE遺傳算法中每一代的最優(yōu)個(gè)體都會(huì)復(fù)制到下一代中，除非下一代出現(xiàn)了適應(yīng)度值更高的個(gè)體，否則這個(gè)最優(yōu)個(gè)體會(huì)一直被保留，也就是說(shuō)種群會(huì)一直向接近全局最優(yōu)解的方向進(jìn)化，而不會(huì)出現(xiàn)退化現(xiàn)象。因此，根據(jù)定理1，該算法的狀態(tài)轉(zhuǎn)移概率矩陣為：

(趨于無(wú)窮大)時(shí)，可以收斂到最優(yōu)解，因而GGABE算法具有全局收斂性。

3 測(cè)試函數(shù)及結(jié)果

3.1 測(cè)試函數(shù)

選擇了2個(gè)代表性的測(cè)試函數(shù)f1(x)和f2(x), 驗(yàn)證簡(jiǎn)單遺傳算法(SGA)，未分組的精英遺傳算法(EGA)和基于分組和精英策略的遺傳算法(GGABE)的收斂率及收斂速度。f1(x)和f2(x)公式如下：

3.2 測(cè)試結(jié)果及分析

3種遺傳算法分別執(zhí)行200次，種群大小為20，最大遺傳代數(shù)T為100，pc為0.99，pm為0.1，ηc和b均為2，pswap為0.6。根據(jù)函數(shù)圖像中極值的分布對(duì)搜索空間進(jìn)行人工分組，函數(shù)f1(x)分為4組；函數(shù)f2(x)不分組。以收斂率(sr)、平均收斂代數(shù) (ast) 來(lái)評(píng)估算法性能[15]，結(jié)果如表1所示。

式中，n為執(zhí)行次數(shù)，valk表示第k次試驗(yàn)計(jì)算的最優(yōu)值，F(xiàn)(valk)表示valk是否收斂，收斂為1，否則為0，tk表示第k次試驗(yàn)結(jié)束時(shí)種群進(jìn)化次數(shù)。

根據(jù)表1分析對(duì)于同一函數(shù)：SGA收斂率最低，收斂速度最慢，平均迭代數(shù)最大，計(jì)算出的最優(yōu)值誤差最大；GGABE收斂率最高，收斂速度最快，平均收斂代數(shù)最小，計(jì)算的最優(yōu)值誤差最小，f1(x)與實(shí)際最優(yōu)值之差為 0.012，而f2(x)與實(shí)際最優(yōu)值之差為0。GGABE能夠找出多極值函數(shù)的所有最優(yōu)解而SGA和EGA只能找出1個(gè)。函數(shù)f1(x)在[0, 20]內(nèi)有4個(gè)最優(yōu)解，200次試驗(yàn)中，GGABE算法有199次找出了4個(gè)最優(yōu)值，而SGA和EGA算法每次均找出了1個(gè)最優(yōu)值。

表1 3種遺傳算法尋找函數(shù)f1(x)、f2(x)最優(yōu)值的性能比較Tab. 1 Peformance comparision of three genetic algorithms searching optimal function f1(x) and f2(x)

4 尋找最優(yōu)路徑

4.1 試驗(yàn)設(shè)計(jì)

試驗(yàn)設(shè)備為一臺(tái)華碩筆記本，基本配置: i7Intel處理器, 主頻2.39 GHz，試驗(yàn)軟件為Matlab2012A。設(shè)計(jì)了2幅不同規(guī)模的地圖，第1幅為15×15(圖2a、2b、2c)，第2幅為25×25(圖2d、2e、2f), 地圖中黑色區(qū)域?yàn)檎系K物，左下角為起點(diǎn)，右上角為終點(diǎn)，實(shí)線(xiàn)為尋找到的最優(yōu)路徑(圖2)。

圖2 3種算法在不同規(guī)模地圖上的搜索結(jié)果Fig. 2 Searching results of three algorithms on maps with different scales

4.2 結(jié)果分析

基于15×15和25×25的2幅地圖進(jìn)行路徑搜索，3種算法的參數(shù)設(shè)置相同，種群規(guī)模30，循環(huán)100代，pm為0.10，pc為0.99，pswap為0.60，3種算法均執(zhí)行50次。結(jié)果如表2所示。

由表2可知，在15×15規(guī)模的地圖上進(jìn)行路徑搜索時(shí)，GGABE算法收斂代數(shù)最少，收斂率最高，達(dá)94%，在滿(mǎn)足無(wú)碰撞條件下尋找到的最優(yōu)路徑長(zhǎng)度最短，僅為20.970 6。由于試驗(yàn)中使用的地圖中存在8條最優(yōu)路徑，GGABE算法正確地找出了8條路徑，而其他2種算法只能找到1條路徑，且不是最短路徑，說(shuō)明本研究算法性能卓越。

由表2可知，在25×25規(guī)模的地圖上進(jìn)行路徑搜索時(shí)，SGA和EGA的收斂速度和收斂率大幅下降，SGA算法的收斂率降為0.14，EGA的收斂率也降為0.56，而GGABE的性能變化不大，收斂率僅下降了0.04，最大收斂代數(shù)僅增加了4代，找到的最佳路徑數(shù)是全部的8條。由此可見(jiàn)，即使在搜索空間增大的情況下，GGABE依然能夠正確地找出所有的最佳路徑，且有良好的收斂率和收斂速度。

表2 3種遺傳算法在不同大小規(guī)模的地圖中搜索路徑時(shí)性能比較Tab. 2 Performance comparision of three genetic algorithms searching paths on maps with different scales

4.3 驗(yàn)證試驗(yàn)

為了測(cè)試GGABE的性能，2017年在江蘇省徐州市豐縣宋鎮(zhèn)樓的蘋(píng)果園進(jìn)行了樣機(jī)測(cè)試。果樹(shù)行距為4.0 m，株距為3.7 m，以安裝了機(jī)械臂和掃描儀的履帶驅(qū)動(dòng)農(nóng)業(yè)機(jī)器人為研究平臺(tái)，在蘋(píng)果園中規(guī)劃路徑。機(jī)器人的移動(dòng)速度為0.68 m·s–1，行走路徑為果樹(shù)行中心線(xiàn)。為防止破壞果樹(shù)，機(jī)器人移動(dòng)過(guò)程中收起機(jī)械臂，可看成一個(gè)質(zhì)點(diǎn)。果園最佳路徑必須滿(mǎn)足2個(gè)條件：無(wú)碰撞(即不經(jīng)過(guò)障礙物)；滿(mǎn)足前面條件的前提下，保證路徑長(zhǎng)度最短。

為實(shí)現(xiàn)自動(dòng)導(dǎo)航，需要確定果樹(shù)位置信息。以?huà)呙鑳x中心為坐標(biāo)原點(diǎn)，機(jī)器人前進(jìn)方向?yàn)閤軸，建立直角坐標(biāo)系。掃描儀射出的激光會(huì)在樹(shù)干上形成1個(gè)交點(diǎn)，作為此樹(shù)的標(biāo)識(shí)，提取該點(diǎn)在坐標(biāo)系中的坐標(biāo)，就獲得了果樹(shù)位置。獲得的位置坐標(biāo)信息傳入后臺(tái)計(jì)算機(jī)，機(jī)器人可在GPS的幫助下移動(dòng)。將果園柵格化為30×30地圖(圖3a)，黑色區(qū)域?yàn)楣麡?shù)，淺色網(wǎng)格為人為添加的障礙物，由起點(diǎn)至終點(diǎn)，由控制計(jì)算機(jī)基于GGABE算法找出1條或若干條遍歷果園內(nèi)所有果樹(shù)的最佳路徑，并發(fā)送控制指令驅(qū)動(dòng)機(jī)器人前進(jìn)。進(jìn)行50次試驗(yàn)，計(jì)算機(jī)每次均找出3條最佳路徑(圖3b、3c、3d)，人為選中1條路徑供機(jī)器人行走，前10次和后10次試驗(yàn)路徑規(guī)劃花費(fèi)的平均時(shí)間分別為15.700 817 s和15.608 967 s；50次試驗(yàn)中最長(zhǎng)規(guī)劃時(shí)間為15.724 909 s，最短規(guī)劃時(shí)間為15.184 906 s，平均時(shí)間為15.543 319 s。

圖3 驗(yàn)證試驗(yàn)Fig. 3 Verification experiment

5 結(jié)論

本文針對(duì)傳統(tǒng)遺傳算法效率低、收斂速度慢且無(wú)法處理多極值的問(wèn)題，提出了一種基于分組和精英策略的遺傳算法，并將其應(yīng)用在采摘機(jī)器人路徑規(guī)劃研究中。研究中設(shè)計(jì)了15×15和25×25的2幅仿真地圖，GGABE算法能以最快的速度，最高的收斂率找出所有正確的最短路徑，而另外2種算法只能各找出1條路徑，且不是最優(yōu)。當(dāng)搜索空間規(guī)模增大時(shí)，本文提出的算法依然能夠快速收斂，找到多條最優(yōu)路徑?？梢?jiàn)GGABE算法具有良好的魯棒性和收斂速度。實(shí)地試驗(yàn)表明在龐大而復(fù)雜的果園中，GGABE算法依然能躲避障礙物，快速準(zhǔn)確地找出所有遍歷整個(gè)果園的最佳路徑，本研究為后期機(jī)器人實(shí)現(xiàn)采摘任務(wù)提供了基礎(chǔ)。

由于初始種群的優(yōu)劣對(duì)路徑規(guī)劃有一定的影響，本文中初始種群為隨機(jī)產(chǎn)生，今后將重點(diǎn)研究如何獲得優(yōu)質(zhì)的初始種群，從而進(jìn)一步提高算法的收斂率和收斂速度。

[1]張毅, 代恩燦, 羅元. 基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)測(cè)量與控制, 2016, 24(1): 313-316.

[2]盧月品, 趙陽(yáng), 孟躍強(qiáng), 等. 基于改進(jìn)遺傳算法的狹窄空間路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(2): 413-418.

[3]張超, 李擎, 董冀媛, 等. 基于混沌粒子群—專(zhuān)用遺傳算法切換策略的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 北京科技大學(xué)學(xué)報(bào), 2013, 35(6): 826-830.

[4]KALA R. Multi-robot path planning using co-evolutionary genetic programming[J]. Expert Syst Appl, 2012, 39(3): 3817-3831.

[5]MASOUD S, MOHD F O. Global path planning for autonomous mobile robot using genetic algorithm[C]//Signal-Image Technology and Internet-Based Systems, 2013 International Conference. USA: IEEE, 2013: 726-730.

[6]YUN S C, GANAPATHY V, CHONG L O. Improved genetic algorithms based optimum path planning for mobile robot[C]//Control Automation Robotics and Vision, 2010 11th International Conference. USA: IEEE, 2010: 1565-1570.

[7]MOHANTA J C, PARHI D R, PATEL S K. Path planning strategy for autonomous mobile robot navigation using petri-GA optimisation[J]. Comput Electr Eng, 2011, 37(6): 1058-1070.

[8]童俊華, 蔣煥煜, 周鳴川. 基于遺傳算法的穴盤(pán)苗自動(dòng)移缽路徑優(yōu)化[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2013, 44(4): 45-49.

[9]BERCLAZ J, FLEURET F, TURETKEN E, et al. Multiple object tracking using k-shortest paths optimization[J]. IEEE T Pattern, 2011, 33(9): 1806-1819.

[10]CHEN D Z, HERSHBERGER J, WANG H. Computing shortest paths amid convex pseudodisks[J]. SIAM J Comput, 2013, 42(3): 1158-1184.

[11]王峰, 曼媛, 段俊潔. 一種改進(jìn)的求解前N條最短路徑問(wèn)題的多種標(biāo)號(hào)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(7): 1482-1487.

[12]岳欽, 馮珊. 粗粒度并行遺傳算法的計(jì)算性能分析[J].武漢理工大學(xué)學(xué)報(bào), 2008, 30(7): 107-110.

[13]TSAI C C, HUANG H C, CHAN C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J]. IEEE Trans Ind Electron, 2011, 58(10): 4813-4821.

[14]莊嘉祥. 精英策略遺傳算法改進(jìn)及在作物模型參數(shù)優(yōu)化的應(yīng)用[D]. 南京: 南京農(nóng)業(yè)大學(xué), 2013.

[15]羅熊, 樊曉平, 易晟, 等. 具有大量不規(guī)則障礙物的環(huán)境下機(jī)器人路徑規(guī)劃的一種新型遺傳算法[J]. 機(jī)器人, 2004, 26(1): 11-16.

【責(zé)任編輯 霍 歡】

Application of genetic algorithm based on group and elite strategy for robot navigation

XIE Zhonghong1, WANG Pei1, GU Baoxing2, JI Changying2, TIAN Guangzhao2
(1 College of Information Technology, Nanjing Agricultural University, Nanjing 210095, China; 2 Intelligent Agriculture Equipment Key Laboratory in Jiangsu Province, Nanjing 210031, China)

【Objective】To solve the problems that picking robot could not find the multipath quickly and accurately in planning route in complex plantation environment, a genetic algorithm based on group and elite strategy (GGABE) was proposed.【Method】Firstly, an initial population was generated and was divided into several groups using the Sigmoid function. After n times of operations of selections, crossovers and mutations in each group separately, k optimal paths with equal length were then acquired in each group. Comparing the optimal paths among different groups, the shortest paths were chosen as the final optimal paths. With all population parameters being the same, three types of algorithms, including simple genetic algorithm(SGA), ungrouped elite genetic algorithm (EGA) and GGABE, were tested 50 times respectively on 15×15 and 25×25 maps. The prototype verification experiments were carried out in the plantation.【Result】Eight shortest paths with the average length of 20.970 6 were found in map 1 by GGABE. Only one shortest path was found in map 1 with the other two algorithms. Eight shortest paths with the average length of 38.041 6 were found in map 2 by GGABE. Three optimal paths were found in each of the 50 verificationexperiments, and the average consumption time for route planning was 15.543 319 s.【Conclusion】GGABE has fast convergence speed and can quickly and accurately find out all optimal paths, which are able to traverse the entire plantation, from the map.

group; elite strategy; picking robot; genetic algorithm; advantageous individual; route planning; navigation

TP242; S233

A

1001-411X(2017)05-0110-07

謝忠紅, 王培, 顧寶興, 等. 基于分組和精英策略的遺傳算法在機(jī)器人導(dǎo)航上的應(yīng)用[J]. 華南農(nóng)業(yè)大學(xué)學(xué)報(bào), 2017, 38(5): 110-116.

2016-12-30 優(yōu)先出版時(shí)間：2017-07-14

優(yōu)先出版網(wǎng)址：http://kns.cnki.net/kcms/detail/44.1110.s.20170714.0859.038.html

謝忠紅(1977—)，女，副教授，博士，E-mail: xiezh@njau.edu.cn

國(guó)家自然科學(xué)基金(31401291)；江蘇省自然科學(xué)基金(BK20140720)；中央高?；緲I(yè)務(wù)費(fèi)(KYZ201670)