朱鐵欣，董桂菊，顏丙學(xué)，郭凱敏，謝學(xué)剛，郭志強(qiáng)

(東北農(nóng)業(yè)大學(xué)，哈爾濱　150030)

?

基于改進(jìn)蟻群算法的農(nóng)業(yè)機(jī)器人路徑規(guī)劃研究

朱鐵欣，董桂菊，顏丙學(xué)，郭凱敏，謝學(xué)剛，郭志強(qiáng)

(東北農(nóng)業(yè)大學(xué)，哈爾濱150030)

摘要：針對(duì)農(nóng)業(yè)機(jī)器人路徑規(guī)劃實(shí)時(shí)性和穩(wěn)定性差的問題，采用人工勢(shì)場(chǎng)法，并結(jié)合Memetic算法與精英排序法優(yōu)化基本蟻群算法。該算法用勢(shì)場(chǎng)法獲得路徑初始化種群，對(duì)每代路徑進(jìn)行Memetic算法中的交叉組合操作，將每代螞蟻產(chǎn)生的路徑分別進(jìn)行優(yōu)化排序，根據(jù)螞蟻路徑的優(yōu)劣程度，對(duì)信息素進(jìn)行更新；同時(shí)，加入精英小組螞蟻產(chǎn)生的信息素，從而加快了算法的收斂速度，提高了算法的穩(wěn)定性。實(shí)驗(yàn)表明：改進(jìn)后算法的平均最優(yōu)路徑長(zhǎng)度提高了12.56%，收斂代數(shù)提高55.86%，算法用時(shí)提高了65.3%，最優(yōu)解百分比增加了40%。本算法能夠快速有效地規(guī)劃出最優(yōu)路徑，提高了農(nóng)業(yè)機(jī)器人的工作效率。

關(guān)鍵詞：農(nóng)業(yè)機(jī)器人；Memetic算法；路徑規(guī)劃；蟻群算法；精英排序；人工勢(shì)場(chǎng)

0引言

隨著科技的發(fā)展，智能機(jī)器人在農(nóng)業(yè)領(lǐng)域的應(yīng)用日益廣泛，而路徑規(guī)劃是農(nóng)業(yè)機(jī)器人研究領(lǐng)域的重要內(nèi)容之一，是實(shí)現(xiàn)機(jī)器人智能作業(yè)的必要基礎(chǔ)。路徑規(guī)劃一般分為環(huán)境地圖完全已知的靜態(tài)路徑規(guī)劃和環(huán)境地圖部分已知或全部未知的動(dòng)態(tài)路徑規(guī)劃，本文主要對(duì)前者進(jìn)行研究分析。對(duì)于這個(gè)問題，已經(jīng)有大量學(xué)者進(jìn)行研究和探索，并提出了很多解決方法。其中，蟻群算法的應(yīng)用最為突出，該算法具有分布式計(jì)算、信息正反饋和啟發(fā)式搜索的特征，非常適合求解移動(dòng)機(jī)器人的路徑規(guī)劃問題。但基本蟻群算法的執(zhí)行過程依賴于大量的迭代和循環(huán)，缺乏實(shí)時(shí)性；運(yùn)行過程中信息素不斷地累積，優(yōu)質(zhì)路徑不突出，對(duì)于最優(yōu)解的求取有著很大的影響。針對(duì)這些問題，文獻(xiàn)[1]在算法停滯階段，引入交叉操作，并調(diào)整α、β和ρ的值，改善了算法的搜索效率；文獻(xiàn)[2]采用遺傳算法對(duì)蟻群算法的基本參數(shù)進(jìn)行優(yōu)化和配置，增強(qiáng)了算法的穩(wěn)定性；文獻(xiàn)[3]采用人工勢(shì)場(chǎng)法融合蟻群算法，構(gòu)建并加入了權(quán)重可調(diào)的引力概率函數(shù)作為啟發(fā)式因子，提高了算法的運(yùn)行速度。為了減少算法運(yùn)行時(shí)間，提高算法收斂速度和穩(wěn)定性，本文融合了人工勢(shì)場(chǎng)、Memetic算法、精英小組和優(yōu)化排序法以得到問題的更優(yōu)解。

1基本蟻群算法

蟻群算法(Ant colony optimization,ACO)是意大利學(xué)者Dorigo等人，從螞蟻群體的覓食過程中受到啟發(fā)，于1991年提出的一種模擬自然界中蟻群行為的模擬進(jìn)化算法[4]。以下為基本蟻群算法的主要過程。

(1)

螞蟻完成一次循環(huán)，各生成路徑上的信息素按下式進(jìn)行調(diào)整，有

τij(t+1)=ρ·τij(t)+Δτij(t,t+1)

(2)

(3)

按照信息素增量表達(dá)方式的區(qū)別，基本蟻群算法可以分為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)。本文選用使用全局信息素更新策略的蟻周系統(tǒng)。軌跡信息素增量為

(4)

其中，Q為螞蟻k經(jīng)過路徑(i,j)后，每單位長(zhǎng)度釋放的信息素量；Lk為螞蟻k在本次循環(huán)所經(jīng)過的路徑長(zhǎng)度。螞蟻按照這一規(guī)則，循環(huán)往復(fù)進(jìn)行，最終得到從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。

2改進(jìn)算法設(shè)計(jì)

2.1　種群初始化

人工勢(shì)場(chǎng)法是由Khatib提出的一種虛擬力法。該算法應(yīng)用在路徑規(guī)劃問題中時(shí)，將工作環(huán)境抽象為力場(chǎng)，目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人產(chǎn)生“引力”，障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生“斥力”，機(jī)器人距離目標(biāo)位置越近，所受“引力”的影響越大，反之越小。

設(shè)Xd為小車當(dāng)前位置點(diǎn)，Xe為目標(biāo)點(diǎn)，Xz為障礙物，共n個(gè)障礙物，車與障礙物的夾角為

(5)

其中，i=1,2,…,n；dzd為各障礙物與小車當(dāng)前位置間距離。

目標(biāo)對(duì)車的引力為

(6)

其中，y為引力增益系數(shù)；dde為當(dāng)前位置與目標(biāo)位置的距離；θe為當(dāng)前位置與目標(biāo)位置的夾角。

當(dāng)路徑點(diǎn)與障礙物間距離大于預(yù)先設(shè)置的障礙物影響距離P0時(shí)，該障礙物對(duì)小車的斥力為0；否則，障礙物對(duì)車的斥力為

(7)

其中，c為斥力增益系數(shù)。

將位引力與斥力對(duì)應(yīng)求和，則機(jī)器人在該合力的指引下尋找下一路徑點(diǎn)。

2.2　路徑更新

為了擴(kuò)大路徑點(diǎn)的選擇范圍，減少鎖死和早熟現(xiàn)象的發(fā)生，在路徑更新的過程中融入Memetic算法。Memetic算法(也有文獻(xiàn)將其稱為文化基因算法)的概念在1989年由Moscato首次提出，并將其歸為一種基于群體的混合全局啟發(fā)式搜索算法[6]。Memetic算法采用的框架和操作流程與遺傳算法相似，應(yīng)用在路徑規(guī)劃時(shí)，結(jié)合了遺傳算法和局部搜索算法的優(yōu)點(diǎn)，全局尋優(yōu)能力強(qiáng)，收斂性較高，能夠獲得高質(zhì)量解。本文主要應(yīng)用Memetic算法中的交叉操作。

在螞蟻完成一次迭代之后，隨機(jī)打亂一代中全部m只螞蟻的路徑順序，然后取第i條路徑和第m-i條路徑作為父代，將兩父代中所有路徑點(diǎn)合并，取出不重復(fù)的路徑點(diǎn)，且各路徑點(diǎn)首次出現(xiàn)的位置不變，作為子代新生路徑。下面進(jìn)行舉例說明。

設(shè)路徑s1為(1 9 15 18 24 65)，路徑s2為(4 9 18 20 35 43)，合并路徑s1和s2，得到路徑s3為(1 9 15 18 24 65 4 9 18 20 35 43)，剔除重復(fù)路徑點(diǎn)并保持各點(diǎn)相對(duì)位置不變，得到子代路徑sz為(1 9 15 18 24 65 4 20 35 43)。

2.3　信息素更新

2.3.1優(yōu)化排序

在完成算法一次迭代后，將本次循環(huán)中所有螞蟻形成的有效路徑，按照從大到小(L1≥L2≥L3≥…≥Lm)的順序進(jìn)行排列，路徑長(zhǎng)度越長(zhǎng)，排名越靠前，則對(duì)該路徑上的信息素增加較?。环粗?，較短路徑會(huì)對(duì)信息素的更新做出較大貢獻(xiàn)。

本設(shè)計(jì)采用冒泡排序(Bubble Sort)法[7]，是一種穩(wěn)定的排序算法。它重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，若順序與設(shè)置不同，則交換兩個(gè)元素，直到完成最后兩個(gè)元素的比較，排序完成。同時(shí)，在排序過程中加入swap變量，它的作用是如果某次比較路徑長(zhǎng)度Ln=Ln+1，不用將其交換，即可視為排序已完成，就會(huì)直接做結(jié)束處理。如此，便得到從大到小的路徑排序，將此排序翻轉(zhuǎn)，則得到算法所需順序，即從小到大。排序過程流程圖如圖1所示。其中，lengh(Lm)為可行路徑數(shù)量。

2.3.2精英小組

在信息素更新時(shí)，在對(duì)所有可行路徑增加信息素的基礎(chǔ)上，加入精英蟻群小組。精英蟻群小組指在算法執(zhí)行過程中，得到最短路徑的螞蟻小組。使用精英螞蟻小組可以更快、更好地找出最優(yōu)解。然而，如果精英螞蟻的選擇太多，搜索將迅速地集中在其周圍的最佳值附近，這樣將會(huì)導(dǎo)致過早收斂；選用精英螞蟻過少，對(duì)算法的優(yōu)化則難以達(dá)到預(yù)期的效果。經(jīng)大量實(shí)驗(yàn)分析，精英數(shù)量小組數(shù)量jj取3~6時(shí)效果較好。部分實(shí)驗(yàn)數(shù)據(jù)如表1所示。

圖1　冒泡路徑排序流程圖

樣本號(hào)mkjj18035425010063403544505046503537508048406039454031035453

3算法的實(shí)現(xiàn)

應(yīng)用人工勢(shì)場(chǎng)、Memetic算法和精英排序改進(jìn)蟻群算法的算法流程圖如圖2所示。

算法步驟為以下8步。

Step1：算法基本參數(shù)設(shè)置。

Step2：初始化禁忌表、信息素等，人工勢(shì)場(chǎng)法初始化螞蟻爬行路經(jīng)。

Step3：設(shè)置評(píng)價(jià)函數(shù)，本文以起始位置到目標(biāo)位置間直線距離的倒數(shù)作為啟發(fā)式因素。

Step4：按輪賭法尋找螞蟻運(yùn)行路徑點(diǎn)。

Step5 ：Memetic算法更新所得路徑，將所得路徑進(jìn)行交叉組合操作。

Step6：優(yōu)化排序和精英小組信息素更新。

Step7：全局信息素更新。

Step8：判斷是否滿足終止條件，即是否獲得最優(yōu)路徑，或達(dá)到最大迭代次數(shù)，滿足則運(yùn)行結(jié)束，不滿足則返回Step4。

圖2　改進(jìn)蟻群算法流程圖

4實(shí)驗(yàn)研究

4.1　仿真環(huán)境

W.H.Howden提出的柵格法[8]在處理路徑規(guī)劃問題時(shí)，可視地圖簡(jiǎn)單、清晰。并且，柵格法易于實(shí)現(xiàn)計(jì)算機(jī)的建模、存儲(chǔ)、處理、更新與分析。實(shí)驗(yàn)中將圖片進(jìn)行柵格化處理，障礙區(qū)域用1表示，可行區(qū)域用0表示，并將柵格按照從左到右、從上到下的順序進(jìn)行編碼，格柵個(gè)序號(hào)與坐標(biāo)的關(guān)系為

S=(j-1)×20+i

(10)

其中，i，j分別為柵格的橫縱坐標(biāo)。

本實(shí)驗(yàn)采用20×20的障礙柵格模擬實(shí)際農(nóng)田環(huán)境，分別采用復(fù)雜障礙、中等復(fù)雜障礙、簡(jiǎn)單障礙環(huán)境，每種環(huán)境進(jìn)行20次仿真。此仿真過程中，將障礙物尺寸增加機(jī)器人半徑長(zhǎng)度，即視機(jī)器人為質(zhì)點(diǎn)；障礙物不滿一柵格，按一柵格處理。

4.2　仿真結(jié)果分析

取基本蟻群算法參數(shù)迭代次數(shù)K=100，蟻群數(shù)量M=50，信息素激勵(lì)因子α=1.5，啟發(fā)式激勵(lì)因子β=9，信息素強(qiáng)度Q=1，信息素?fù)]發(fā)系數(shù)ρ=0.31；改進(jìn)算法中取K=35，引力增益系數(shù)y=8，斥力增益系數(shù)c=4，障礙影響距離P0=1.8，勢(shì)場(chǎng)步長(zhǎng)b=2.1，并加入精英小組jj=3。表2為各障礙環(huán)境下的仿真數(shù)據(jù)結(jié)果。圖3為算法改進(jìn)前后各數(shù)據(jù)結(jié)果柱狀圖。

表2　算法改進(jìn)后仿真數(shù)據(jù)結(jié)果

圖3　算法改進(jìn)前后結(jié)果對(duì)比圖

圖3中，改進(jìn)前后最優(yōu)路徑長(zhǎng)度、收斂代數(shù)、算法用時(shí)皆為3種環(huán)境規(guī)模平均值，改進(jìn)前分別為32.64、48.33、19.54，最優(yōu)解百分比為48%；改進(jìn)后為28.54、21.33、6.78，最優(yōu)解百分比為88%，這4個(gè)評(píng)價(jià)參數(shù)分別提高了12.56%、55.86%、65.3%、40%，在收斂速度和算法用時(shí)上最為顯著，達(dá)到了本文的目的。圖4為算法改進(jìn)后不同障礙環(huán)境路徑結(jié)果圖。從圖4中可以直觀地看到，對(duì)于不同的環(huán)境模型，該改進(jìn)算法都可以找到最優(yōu)路徑。

復(fù)雜障礙 　　　　　　　　　　　　　　 中等復(fù)雜障礙 　　　　　　　　　　　　　　 簡(jiǎn)單障礙

5結(jié)論

由于基本蟻群算法迭代次數(shù)多、運(yùn)行速度慢，容易產(chǎn)生鎖死現(xiàn)象，本文采用一種基于人工勢(shì)場(chǎng)、冒泡排序和精英小組的改進(jìn)蟻群算法，并融入Memetic算法。該算法在初始時(shí)刻產(chǎn)生優(yōu)質(zhì)初始值，路徑更新過程加入交叉操作，信息素更新時(shí)，突出優(yōu)質(zhì)螞蟻對(duì)算法規(guī)劃的影響，增加優(yōu)質(zhì)路徑搜索范圍，從而使后來螞蟻能夠更快地找到優(yōu)質(zhì)路徑，加快了算法的收斂速度，進(jìn)而可以減少迭代次數(shù)，提高算法效率。

仿真結(jié)果表明：與基本蟻群算法相比，改進(jìn)算法在運(yùn)行用時(shí)和收斂速度上皆有大幅度的提高，具有更高的穩(wěn)定性和有效性，說明本文中的算法改進(jìn)是有效可行的，提高了農(nóng)業(yè)機(jī)器人運(yùn)動(dòng)過程中的穩(wěn)定性和實(shí)時(shí)性?；诖烁倪M(jìn)效果，該算法可以應(yīng)用于自主移動(dòng)農(nóng)業(yè)機(jī)器人，為其智能移動(dòng)進(jìn)行采摘、噴藥等工作的實(shí)施提供了理論依據(jù)。

參考文獻(xiàn)：

[1]張琦,馬家辰,謝瑋，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,34(11):1521.

[2]Wang Zhangqi, Zhu Xiaoguang, Han Qingyao.Mobile robot path planning based on parameter optimization ant colony algorithm[J].Procedia Engineering, 2011,15(8):2738-2741.

[3]孫純哲,桂貴生,韓東，等.基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究與應(yīng)用[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,2006,29(10):1208

[4]李世勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社,2004:29-31.

[5]段海濱.蟻群算法原理及其應(yīng)用[M].北京：北京科學(xué)出版社,2005:36-48.

[6]陳穎頻,王靈芝,吳金峰，等.基于選擇思想和反序標(biāo)識(shí)的改進(jìn)冒泡排序算法[J].泉州師范學(xué)院學(xué)報(bào),2014,32(6):89.

[7]段海濱,張祥銀,徐春芳.仿生智能計(jì)算[M].北京：科學(xué)出版社,2011:130-143.

[8]吳登峰,梅志千,尹立偉，等.一種未知環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃新算法[J].機(jī)電工程,2015,32(3):390.

Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm

Zhu Tiexin， Dong Guiju，Yan Bingxue， Guo Kaimin， Xie Xuegang， Guo Zhiqiang

(Northeast Agricultural University, Harbin 150030, China)

Abstract：In response to the problems of agricultural robot path planning bad real-time and stability,artificial potential field, elite sorting method combined with Memetic algorithm is adopted. This algorithm initialize the path population with potential field method,optimizes the sorting of each generation ants path. And also updates the pheromone according to the superiority of the ants path. At the same time, with the help of the pheromone of the elite ants, and using crossover and mutation operation of the memetic algorithm on each generation path,so as accelerate the convergence speed of the algorithm, improves the stability of it.The simulation results show that the improved algorithm of the optimal path length on average increased by 12.56%,the convergence generation increased by 55.86%, the algorithm time increased by 65.3%,and the optimal solution percentage increased by 40%,this shows that the mentioned algorithm can plan the optimal path in a quick and efficient way, improving the efficiency of agricultural robot.

Key words：agricultural robot; memetic algorithm; path planning; ant colony algorithm; elite sorting; artificial potential field

中圖分類號(hào)：S24

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-188X(2016)09-0048-05

作者簡(jiǎn)介：朱鐵欣(1990-)，女，黑龍江五營(yíng)人，碩士研究生，(E-mail)1254904178@qq.com。通訊作者：董桂菊(1967-)，女，哈爾濱人，副教授，碩士生導(dǎo)師。

基金項(xiàng)目：國(guó)家“863計(jì)劃”項(xiàng)目(810028)

收稿日期：2015-08-26