謝忠紅,王 培,顧寶興,姬長英,田光兆
(1 南京農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南京 210095; 2 江蘇省智能化農(nóng)業(yè)裝備重點實驗室,江蘇 南京 210031)
基于分組和精英策略的遺傳算法在機器人導(dǎo)航上的應(yīng)用
謝忠紅1,王 培1,顧寶興2,姬長英2,田光兆2
(1 南京農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南京 210095; 2 江蘇省智能化農(nóng)業(yè)裝備重點實驗室,江蘇 南京 210031)
【目的】針對種植園復(fù)雜環(huán)境下采摘機器人進行路徑規(guī)劃時找出多路徑效率低、速度慢等問題,提出一種基于分組和精英策略的遺傳算法(GGABE)?!痉椒ā渴紫壬?個初始群體,使用Sigmoid函數(shù)分組;然后在每組中分別進行選擇、交叉、變異操作,進行n代迭代后,每組產(chǎn)生該組內(nèi)的k條等長的最優(yōu)路徑;比較各組最優(yōu)路徑,選擇最短的路徑作為最優(yōu)路徑。在種群的各項參數(shù)均相同的情況下,簡單遺傳算法(SGA)、未分組的精英遺傳算法(EGA)以及GGABE分別作用于15×15和25×25的地圖,各進行 50 次試驗。進行樣機驗證試驗。【結(jié)果】第 1 幅地圖,GGABE算法找到了 8 條最短路徑,路徑均值為 20.970 6,其他 2 種方法只能找出 1 條最短路徑;第 2 幅地圖,GGABE算法找到了 8 條最短路徑,路徑均值為 38.041 6。50次驗證試驗均找出 3 條最佳路徑,平均路徑規(guī)劃時間為 15.543 319 s?!窘Y(jié)論】本研究提出的基于分組和精英策略的遺傳算法收斂速度快,可快速準(zhǔn)確地在地圖中搜索出所有能夠遍歷整個果園的最佳路徑。
分組;精英策略;采摘機器人;遺傳算法;優(yōu)勢個體;路徑規(guī)劃;導(dǎo)航
導(dǎo)航技術(shù)是采摘機器人研究領(lǐng)域中的關(guān)鍵技術(shù),而路徑規(guī)劃則是導(dǎo)航研究課題中的重中之重,路徑規(guī)劃是指采摘機器人基于已給出的種植園地圖,滿足不碰撞障礙物的前提下,計算出一條從起點到終點的最短路徑或耗時最少的路徑[1-2]。張毅等[1]在遺傳算法中新增了插入算子將間斷路徑轉(zhuǎn)化為連續(xù)路徑,刪除算子用于刪除路徑中的冗余序號;盧月品等[2]使用Dijkstra算法找出1條可行、最短但不保證精度和安全性的路徑,然后采用改進的遺傳算法提高路徑精度;張超等[3]結(jié)合混沌粒子群算法和遺傳算法,提出了基于粒子群-遺傳算法切換策略的路徑規(guī)劃方法;Kala[4]提出了在1張地圖中使用多個機器人共同尋找最佳路徑,由其中的某個主機器人協(xié)調(diào)它們之間的合作關(guān)系;Masoud等[5]提出了六邊形環(huán)境建模法,可以在較短的時間內(nèi)找出全局最佳路徑;Yun等[6]為了提高搜索效率,在產(chǎn)生初始種群時,引入了障礙物避免算法(OAA)和區(qū)分算法(DA);Mohanta等[7]在Petri網(wǎng)中引入了遺傳算法,該算法基于一種迭代的、非線性搜索操作,能夠充分利用環(huán)境的幾何信息,產(chǎn)生適宜的航線角度。
已有的算法改進主要研究如何提高收斂速度,較少涉及從地圖中獲取多條最佳路徑的問題;當(dāng)搜索空間很大時,如何快速收斂到全局最優(yōu)路徑附近也是一個難題。針對這些問題,本文提出了一種基于分組和精英策略的遺傳算法,以期快速、有效地獲取地圖中的所有最佳路徑。
基于Sigmoid函數(shù)對搜索空間分組后,在每組獨立進行遺傳操作,每一代適應(yīng)度值最高的個體即為精英個體,將其完整保留到下一代中,并參與到每個個體的交叉和變異。
1.1 地圖生成及編碼
為了便于采摘機器人的移動,種植園中果樹要求分布規(guī)則且間距較大(>5 m),而移動中的機器人機械手處于收攏狀態(tài),所占區(qū)域長寬在[1.0 m, 1.5 m]內(nèi),因此可將機器人視為質(zhì)點。柵格法生成的種植園地圖如圖1所示,圖1中的帶箭頭的線段表示1條路徑。初始化群體可采用2種編碼方式:坐標(biāo)法和序號法。坐標(biāo)法和序號法的轉(zhuǎn)換關(guān)系分別如下,其中x為橫坐標(biāo),y為縱坐標(biāo),z為序號。
圖1 坐標(biāo)法和序號法表示的地圖Fig. 1 Map indicated by coordinate and order
1.2 分組
對地圖空間進行分組,使得種群在每組中分別進行遺傳操作,其中分組數(shù)(k)是關(guān)鍵。k太大,適應(yīng)度高的個體及其后代會很容易替代其他個體,導(dǎo)致陷入局部收斂;k太小,無法體現(xiàn)分組的優(yōu)勢[8-9]。
人為指定法分組:根據(jù)經(jīng)驗給出1個可行的分組數(shù),缺點是主觀差異大。動態(tài)分組法:分組數(shù)隨著種群的進化不斷動態(tài)變化。初始時種群中的個體呈隨機分布,差異大,k取較大值;隨著種群的進化,個體差異變小,逐漸收斂于n條最佳路徑(n≥1),此時k隨之變小。研究中k遵循Sigmoid函數(shù)[10],并結(jié)合了粗粒度并行遺傳算法[11-12]。
式中,g為初始分組數(shù)(5~8),t為進化代數(shù),μ是調(diào)整參數(shù),一般取值為2。
首先初始化隨機種群,設(shè)種群規(guī)模大小為n,即共有n條路徑,po={pa1, pa2, …, pai…, pan},po表示種群空間,pai表示第i個個體。初始設(shè)進化代數(shù)t=0,g=8,根據(jù)公式計算出分組數(shù)k=6。將種群空間po依次平均分為k組子種群,前k–1組子種群中,每個子種群有av=■n/k」個個體,最后1個子種群有[n?(k?1)av]個個體,分組后的種群空間po={{pa1,在每組中依次進行遺傳操作,可以避免早熟收斂。
每進化1代執(zhí)行遺傳操作之前,在空間po中按■照一■定概率pswap,每2組之間隨機交換個個體,即第1組和第2組,···,第k組隨機交換個體,若k為奇數(shù),則最后一組保持不變。通過引入新的個體,增加了每個子種群的多樣性,避免了局部收斂;同時,每個子種群在搜索空間的不同部分分別進化,加強了全局搜索能力。
經(jīng)過觀察發(fā)現(xiàn),當(dāng)t∈[0, 5]時,分組數(shù)k均為6;當(dāng)t∈[6, 10]時,k為5;當(dāng) t∈[11, 19]時,k為4;當(dāng)t∈[20, 66]時,k為3;隨著種群的進化,最后分組數(shù)k穩(wěn)定為2。也就是說,種群在第6、11、20、67代時會按照上述方法重新進行分組,而在其他代數(shù)時,采用上一代的分組結(jié)果。
1.3 適應(yīng)度函數(shù)
根據(jù)給定的目標(biāo)函數(shù),計算適應(yīng)度值。最優(yōu)路徑滿足以下準(zhǔn)則:無碰撞;路徑長度最短。碰撞函數(shù)f(ro)的公式為:
式中,ro指序號法表示的路徑。
路徑長度函數(shù)l(rc)的公式為:
式中,rc指坐標(biāo)法表示的路徑;為路徑上相鄰的方格;n為路徑上的方格數(shù)。
移動路徑的評價函數(shù)g(r)公式為:
式中,C是放大系數(shù);τ 是1個極小值。
顯然當(dāng)碰到障礙物時,適應(yīng)度值低,繁殖后代的概率小。
1.4 遺傳算子
精英個體指的是當(dāng)前種群中適應(yīng)度值最高的個體[13],可能不止一個。種群中精英個體和全局最優(yōu)解之間的“血緣關(guān)系”要大于其他個體和全局最優(yōu)解的“血緣關(guān)系”,所以要充分利用精英個體中的遺傳信息。本文結(jié)合精英保留策略和輪賭盤操作選擇個體,將每組中的精英個體不加改變地保留到下一代,并參與每個交叉和變異操作。根據(jù)交叉概率Pc,在選擇后的個體中進行交叉操作。采用單點交叉,在2個父本中相同點(起點和終點除外)前后交換。如2條路徑分別為(0, 11, 12, 23, 34, 44)和(0, 10, 11, 22, 33, 44),都經(jīng)過方格11,在該點前后交叉,交叉后為(0, 10, 11, 12, 23, 34, 44)和(0, 11, 22, 33, 44)。若2條路徑(除起點和終點外)沒有相同點,則不交叉;有多個相同點,隨機選取一個作為基準(zhǔn)點,進行交叉。交叉的父本之一必須是上一代的最優(yōu)值,這樣能保護種群的精英個體,加快收斂速度。隨機產(chǎn)生1個0~1之間的數(shù)w,若w小于變異概率pm,則進行變異操作,采用偏移節(jié)點方法[4]。首先,在待變異個體上任選一點(xi, yi),其前驅(qū)節(jié)點和后繼節(jié)點分別為(xi-1, yi-1)和(xi+1, yi+1);然后,設(shè)置1個半徑常數(shù)r,并在0~360之間取隨機數(shù)θ,變異后的節(jié)點為(xi′, yi′),公式為:
連接(xi-1, yi-1)和(xi′, yi′)、(xi′, yi′)和(xi+1, yi+1),判斷其是否經(jīng)過障礙物,若經(jīng)過,則舍棄該節(jié)點,重新生成一個節(jié)點并判斷,直到滿足條件為止;否則,用新節(jié)點替換舊節(jié)點。
已知定理1:若隨機過程或系統(tǒng)在t0時刻所處的狀態(tài)已知,在t>t0時刻所處的條件分布與t0之前所處的狀態(tài)無關(guān),則該過程或系統(tǒng)稱為馬爾科夫鏈[14]。
根據(jù)定理1得出結(jié)論 1:GGABE算法的種群序列{Xt,t≥0}是齊次馬爾科夫鏈,其中t表示進化代數(shù)。證明如下:GGABE遺傳算法中的選擇、交叉、變異操作都是獨立進行的,且每個子代都是由父代通過遺傳操作得到的,與父代之前的個體無關(guān)。所以GGABE算法是齊次馬爾科夫鏈。
結(jié)論 2:GGABE算法具有全局收斂性。證明如下:設(shè)S為種群狀態(tài)空間,sk表示第k代最優(yōu)解對應(yīng)的適應(yīng)度值,pk為得到最優(yōu)值sk的概率,pk>0,很顯然,隨著進
化過程的推進,第k+1代最優(yōu)解的適應(yīng)度值一定大于等于第k代最優(yōu)解的適應(yīng)度值,因此S空間是一個單調(diào)非遞減的有序空間。pi,j表示由狀態(tài)si遷移到狀態(tài)sj的概率,由于GGABE遺傳算法中每一代的最優(yōu)個體都會復(fù)制到下一代中,除非下一代出現(xiàn)了適應(yīng)度值更高的個體,否則這個最優(yōu)個體會一直被保留,也就是說種群會一直向接近全局最優(yōu)解的方向進化,而不會出現(xiàn)退化現(xiàn)象。因此,根據(jù)定理1,該算法的狀態(tài)轉(zhuǎn)移概率矩陣為:
(趨于無窮大)時,可以收斂到最優(yōu)解,因而GGABE算法具有全局收斂性。
3.1 測試函數(shù)
選擇了2個代表性的測試函數(shù)f1(x)和f2(x), 驗證簡單遺傳算法(SGA),未分組的精英遺傳算法(EGA)和基于分組和精英策略的遺傳算法(GGABE)的收斂率及收斂速度。f1(x)和f2(x)公式如下:
3.2 測試結(jié)果及分析
3種遺傳算法分別執(zhí)行200次,種群大小為20,最大遺傳代數(shù)T為100,pc為0.99,pm為0.1,ηc和b均為2,pswap為0.6。根據(jù)函數(shù)圖像中極值的分布對搜索空間進行人工分組,函數(shù)f1(x)分為4組;函數(shù)f2(x)不分組。以收斂率(sr)、平均收斂代數(shù) (ast) 來評估算法性能[15],結(jié)果如表1所示。
式中,n為執(zhí)行次數(shù),valk表示第k次試驗計算的最優(yōu)值,F(xiàn)(valk)表示valk是否收斂,收斂為1,否則為0,tk表示第k次試驗結(jié)束時種群進化次數(shù)。
根據(jù)表1分析對于同一函數(shù):SGA收斂率最低,收斂速度最慢,平均迭代數(shù)最大,計算出的最優(yōu)值誤差最大;GGABE收斂率最高,收斂速度最快,平均收斂代數(shù)最小,計算的最優(yōu)值誤差最小,f1(x)與實際最優(yōu)值之差為 0.012,而f2(x)與實際最優(yōu)值之差為0。GGABE能夠找出多極值函數(shù)的所有最優(yōu)解而SGA和EGA只能找出1個。函數(shù)f1(x)在[0, 20]內(nèi)有4個最優(yōu)解,200次試驗中,GGABE算法有199次找出了4個最優(yōu)值,而SGA和EGA算法每次均找出了1個最優(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.1 試驗設(shè)計
試驗設(shè)備為一臺華碩筆記本,基本配置: i7Intel處理器, 主頻2.39 GHz,試驗軟件為Matlab2012A。設(shè)計了2幅不同規(guī)模的地圖,第1幅為15×15(圖2a、2b、2c),第2幅為25×25(圖2d、2e、2f), 地圖中黑色區(qū)域為障礙物,左下角為起點,右上角為終點,實線為尋找到的最優(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幅地圖進行路徑搜索,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ī)模的地圖上進行路徑搜索時,GGABE算法收斂代數(shù)最少,收斂率最高,達94%,在滿足無碰撞條件下尋找到的最優(yōu)路徑長度最短,僅為20.970 6。由于試驗中使用的地圖中存在8條最優(yōu)路徑,GGABE算法正確地找出了8條路徑,而其他2種算法只能找到1條路徑,且不是最短路徑,說明本研究算法性能卓越。
由表2可知,在25×25規(guī)模的地圖上進行路徑搜索時,SGA和EGA的收斂速度和收斂率大幅下降,SGA算法的收斂率降為0.14,EGA的收斂率也降為0.56,而GGABE的性能變化不大,收斂率僅下降了0.04,最大收斂代數(shù)僅增加了4代,找到的最佳路徑數(shù)是全部的8條。由此可見,即使在搜索空間增大的情況下,GGABE依然能夠正確地找出所有的最佳路徑,且有良好的收斂率和收斂速度。
表2 3種遺傳算法在不同大小規(guī)模的地圖中搜索路徑時性能比較Tab. 2 Performance comparision of three genetic algorithms searching paths on maps with different scales
4.3 驗證試驗
為了測試GGABE的性能,2017年在江蘇省徐州市豐縣宋鎮(zhèn)樓的蘋果園進行了樣機測試。果樹行距為4.0 m,株距為3.7 m,以安裝了機械臂和掃描儀的履帶驅(qū)動農(nóng)業(yè)機器人為研究平臺,在蘋果園中規(guī)劃路徑。機器人的移動速度為0.68 m·s–1,行走路徑為果樹行中心線。為防止破壞果樹,機器人移動過程中收起機械臂,可看成一個質(zhì)點。果園最佳路徑必須滿足2個條件:無碰撞(即不經(jīng)過障礙物);滿足前面條件的前提下,保證路徑長度最短。
為實現(xiàn)自動導(dǎo)航,需要確定果樹位置信息。以掃描儀中心為坐標(biāo)原點,機器人前進方向為x軸,建立直角坐標(biāo)系。掃描儀射出的激光會在樹干上形成1個交點,作為此樹的標(biāo)識,提取該點在坐標(biāo)系中的坐標(biāo),就獲得了果樹位置。獲得的位置坐標(biāo)信息傳入后臺計算機,機器人可在GPS的幫助下移動。將果園柵格化為30×30地圖(圖3a),黑色區(qū)域為果樹,淺色網(wǎng)格為人為添加的障礙物,由起點至終點,由控制計算機基于GGABE算法找出1條或若干條遍歷果園內(nèi)所有果樹的最佳路徑,并發(fā)送控制指令驅(qū)動機器人前進。進行50次試驗,計算機每次均找出3條最佳路徑(圖3b、3c、3d),人為選中1條路徑供機器人行走,前10次和后10次試驗路徑規(guī)劃花費的平均時間分別為15.700 817 s和15.608 967 s;50次試驗中最長規(guī)劃時間為15.724 909 s,最短規(guī)劃時間為15.184 906 s,平均時間為15.543 319 s。
圖3 驗證試驗Fig. 3 Verification experiment
本文針對傳統(tǒng)遺傳算法效率低、收斂速度慢且無法處理多極值的問題,提出了一種基于分組和精英策略的遺傳算法,并將其應(yīng)用在采摘機器人路徑規(guī)劃研究中。研究中設(shè)計了15×15和25×25的2幅仿真地圖,GGABE算法能以最快的速度,最高的收斂率找出所有正確的最短路徑,而另外2種算法只能各找出1條路徑,且不是最優(yōu)。當(dāng)搜索空間規(guī)模增大時,本文提出的算法依然能夠快速收斂,找到多條最優(yōu)路徑??梢奊GABE算法具有良好的魯棒性和收斂速度。實地試驗表明在龐大而復(fù)雜的果園中,GGABE算法依然能躲避障礙物,快速準(zhǔn)確地找出所有遍歷整個果園的最佳路徑,本研究為后期機器人實現(xiàn)采摘任務(wù)提供了基礎(chǔ)。
由于初始種群的優(yōu)劣對路徑規(guī)劃有一定的影響,本文中初始種群為隨機產(chǎn)生,今后將重點研究如何獲得優(yōu)質(zhì)的初始種群,從而進一步提高算法的收斂率和收斂速度。
[1]張毅, 代恩燦, 羅元. 基于改進遺傳算法的移動機器人路徑規(guī)劃[J]. 計算機測量與控制, 2016, 24(1): 313-316.
[2]盧月品, 趙陽, 孟躍強, 等. 基于改進遺傳算法的狹窄空間路徑規(guī)劃[J]. 計算機應(yīng)用研究, 2015, 32(2): 413-418.
[3]張超, 李擎, 董冀媛, 等. 基于混沌粒子群—專用遺傳算法切換策略的移動機器人路徑規(guī)劃[J]. 北京科技大學(xué)學(xué)報, 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]童俊華, 蔣煥煜, 周鳴川. 基于遺傳算法的穴盤苗自動移缽路徑優(yōu)化[J]. 農(nóng)業(yè)機械學(xué)報, 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]王峰, 曼媛, 段俊潔. 一種改進的求解前N條最短路徑問題的多種標(biāo)號算法[J]. 小型微型計算機系統(tǒng), 2016, 37(7): 1482-1487.
[12]岳欽, 馮珊. 粗粒度并行遺傳算法的計算性能分析[J].武漢理工大學(xué)學(xué)報, 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]莊嘉祥. 精英策略遺傳算法改進及在作物模型參數(shù)優(yōu)化的應(yīng)用[D]. 南京: 南京農(nóng)業(yè)大學(xué), 2013.
[15]羅熊, 樊曉平, 易晟, 等. 具有大量不規(guī)則障礙物的環(huán)境下機器人路徑規(guī)劃的一種新型遺傳算法[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
謝忠紅, 王培, 顧寶興, 等. 基于分組和精英策略的遺傳算法在機器人導(dǎo)航上的應(yīng)用[J]. 華南農(nóng)業(yè)大學(xué)學(xué)報, 2017, 38(5): 110-116.
2016-12-30 優(yōu)先出版時間: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
國家自然科學(xué)基金(31401291);江蘇省自然科學(xué)基金(BK20140720);中央高校基本業(yè)務(wù)費(KYZ201670)