基于改進(jìn)蟻群算法的柑橘采摘最優(yōu)路徑

陳 鑫，王海寶*，羅 強(qiáng)，王昌洪，錢 偉

(1.重慶三峽學(xué)院 智能山地農(nóng)機(jī)技術(shù)研究中心，重慶 404120；2.中國(guó)科學(xué)院 合肥智能機(jī)械研究所，安徽 合肥 230031)

隨著自動(dòng)控制技術(shù)的推廣，智慧農(nóng)業(yè)[1-2]得到快速發(fā)展.柑橘多數(shù)生長(zhǎng)在山區(qū)，山地地貌使柑橘采摘消耗大量的人力、物力，且采摘效率極其低下.路徑規(guī)劃[3-4]已應(yīng)用于智慧農(nóng)業(yè).文獻(xiàn)[5]對(duì)農(nóng)田環(huán)境下機(jī)器人的運(yùn)行路徑進(jìn)行了優(yōu)化.文獻(xiàn)[6]設(shè)計(jì)及實(shí)現(xiàn)了植保無人機(jī)按規(guī)劃航跡播撒種子的方案.文獻(xiàn)[7]解決了無人機(jī)在噴灑過程中的重噴漏噴問題.文獻(xiàn)[8]解決了切割工藝中路徑規(guī)劃能耗大的問題.

路徑規(guī)劃算法可分為：傳統(tǒng)經(jīng)典算法[9]、現(xiàn)代智能算法[10].傳統(tǒng)經(jīng)典算法有：Dijkstra算法、人工勢(shì)場(chǎng)法及模擬退火法[11].傳統(tǒng)經(jīng)典算法應(yīng)用于3維空間果實(shí)采摘時(shí)，存在計(jì)算量大、收斂速度慢、易陷入局部最優(yōu)解等問題[12].現(xiàn)代智能算法中的蟻群算法具有分布計(jì)算、群體智能、正反饋、魯棒性強(qiáng)等優(yōu)點(diǎn)，解決了不少3維路徑規(guī)劃問題[13-15].然而，蟻群算法受信息素分布及揮發(fā)的影響，前期搜索解空間時(shí)，易陷入局部最優(yōu)解[16-17].基于此，筆者引入信息素濃度的更新機(jī)制，提出一種改進(jìn)蟻群算法，以加快算法收斂速度，避免陷入局部最優(yōu)解，得到柑橘采摘的最優(yōu)路徑.

1 柑橘采摘的數(shù)學(xué)模型

在柑橘采摘過程中，認(rèn)為柑橘相對(duì)于果樹靜止，將柑橘采摘的路徑規(guī)劃抽象為旅行商問題[18]的解集.將柑橘果實(shí)點(diǎn)視為旅行商問題中的城市點(diǎn)，根據(jù)1棵柑橘果樹的平均大小，柑橘采摘的最優(yōu)路徑為1個(gè)約為10 m×10 m×10 m的3維空間中旅行商問題的最優(yōu)解.

設(shè)賦權(quán)圖G=(V,E)，其中V為頂點(diǎn)集，E為路徑的權(quán)值或長(zhǎng)度集合.

定義

(1)

其中：i,j為相鄰果實(shí)點(diǎn).

經(jīng)典的旅行商問題的數(shù)學(xué)模型為

(2)

使得

(3)

其中：dij為相鄰果實(shí)點(diǎn)的距離，S為頂點(diǎn)集V中所有非空子集，|S|為集合S在賦權(quán)圖G中的頂點(diǎn)數(shù).

式(3)～(4)能保證每個(gè)點(diǎn)僅有一條邊進(jìn)和一條邊出，式(5)能保證該模型沒有子回路解.

2 改進(jìn)的蟻群算法

2.1 蟻群算法

蟻群算法是一種仿生啟發(fā)式算法[19-20].自然環(huán)境下，螞蟻尋找食物時(shí)分泌一種獨(dú)特的化學(xué)物質(zhì)，這種物質(zhì)被稱作信息素.在特定范圍內(nèi)，螞蟻能感知信息素的存在，螞蟻就爬向信息素濃度高的地點(diǎn).隨著時(shí)間的累積，螞蟻數(shù)量不斷增多，該路徑上堆積的信息素濃度就增大，使螞蟻選擇該路徑的概率增大.最終，整個(gè)螞蟻群體在信息素濃度的正反饋機(jī)制[21]作用下，尋得最優(yōu)路徑.

設(shè)在3維空間中有n個(gè)柑橘，柑橘i到柑橘j的距離為

(4)

其中：(xi,yi,zi)為柑橘i在3維空間中的坐標(biāo)；(xj,yj,zj)為柑橘j在3維空間中的坐標(biāo).

螞蟻W從柑橘i到柑橘j的狀態(tài)轉(zhuǎn)移概率為

(5)

信息素濃度以如下方式更新

τij(t+1)=(1-ρ)τij(t)+Δτij,0<ρ<1，

(6)

信息素釋放機(jī)制模型有以下3種：蟻周模型、蟻量模型及蟻密模型.

(7)

其中：Q為螞蟻k釋放信息素濃度總量，Lk為螞蟻k經(jīng)過的從柑橘i到柑橘j的路徑長(zhǎng)度.

(8)

Δτij=Q.

(9)

2.2 改進(jìn)的蟻群算法

在蟻群算法中，螞蟻每次選擇目標(biāo)點(diǎn)路徑時(shí)，趨向于優(yōu)先選擇最優(yōu)路徑.當(dāng)目標(biāo)點(diǎn)增多的時(shí)候，由于信息素隨時(shí)間揮發(fā)的程度不均勻，某些路徑信息素?fù)]發(fā)過快，導(dǎo)致螞蟻在選擇下一路徑時(shí)不能選擇最優(yōu)路徑，算法會(huì)在局部最優(yōu)解的領(lǐng)域停滯，降低了全局搜索解空間的能力，為此提出一種改進(jìn)的蟻群算法.

為了避免陷入局部最優(yōu)解，引入如下的隨時(shí)間改變的自適應(yīng)信息素濃度更新機(jī)制

(10)

其中：Lmin為柑橘i到柑橘j的路徑長(zhǎng)度最小值，Lmax為柑橘i到柑橘j的路徑長(zhǎng)度最大值，γmax為柑橘i到柑橘j的最大路徑因子，γmin為柑橘i到柑橘j的最小路徑因子.

改進(jìn)的信息素濃度更新機(jī)制，避免了在解空間連續(xù)域出現(xiàn)間斷點(diǎn)，自適應(yīng)改變信息素?fù)]發(fā)的程度，使信息素濃度更均勻，得到更多的解空間，提高了全局搜索解空間的能力.

改進(jìn)的蟻群算法流程如圖1所示.

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

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

為了驗(yàn)證改進(jìn)蟻群算法的有效性與可行性，在window10操作系統(tǒng)下通過IntelliJ IDEA2020.1，JDK1.8進(jìn)行仿真實(shí)驗(yàn).柑橘果實(shí)以質(zhì)點(diǎn)表示，根據(jù)柑橘果實(shí)點(diǎn)的坐標(biāo)，在3維坐標(biāo)系中繪圖.圖2為3維坐標(biāo)系中柑橘果實(shí)點(diǎn).

圖2 3維坐標(biāo)系中柑橘果實(shí)點(diǎn)

3.1 參數(shù)優(yōu)化

參數(shù)設(shè)置如表1所示.只改變1個(gè)參數(shù)而其他參數(shù)不變時(shí)，進(jìn)行比較實(shí)驗(yàn).綜合分析筆者進(jìn)行的大量比較實(shí)驗(yàn)及有關(guān)文獻(xiàn)實(shí)驗(yàn)結(jié)果[22-23]可知，當(dāng)α=3、β=4、ρ=0.2、γmax=10、γmin=0.5、Q=20、螞蟻數(shù)量為柑橘果實(shí)點(diǎn)數(shù)量的1.5倍時(shí)，改進(jìn)蟻群算法可得到最優(yōu)路徑.

表1 參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 2種算法比較

在進(jìn)行對(duì)比試驗(yàn)前，按上述優(yōu)化參數(shù)對(duì)蟻群算法及改進(jìn)蟻群算法進(jìn)行設(shè)置.柑橘果實(shí)數(shù)量為31時(shí)的2種算法的采摘路徑如圖3所示.柑橘果實(shí)數(shù)量為144時(shí)的2種算法的采摘路徑如圖4所示.由圖3可知：改進(jìn)蟻群算法的路徑長(zhǎng)度比蟻群算法的路徑長(zhǎng)度短；在果實(shí)點(diǎn)較密集區(qū)域，蟻群算法已陷入局部最優(yōu)解，改進(jìn)蟻群算法則沒有陷入局部最優(yōu)解.分析圖4可以得到與圖3相同的結(jié)論，可見該結(jié)論與柑橘果實(shí)數(shù)量無關(guān).

圖3 柑橘果實(shí)數(shù)量為31時(shí)的2種算法的采摘路徑

圖4 柑橘果實(shí)數(shù)量為144時(shí)的2種算法的采摘路徑

表2為2種算法的路徑長(zhǎng)度及其對(duì)比.由表2可知，不管柑橘果實(shí)數(shù)量如何變化，改進(jìn)蟻群算法路徑長(zhǎng)度均比蟻群算法路徑長(zhǎng)度短.

表2 2種算法的路徑長(zhǎng)度及其對(duì)比

改進(jìn)蟻群算法的路徑長(zhǎng)度比蟻群算法的路徑長(zhǎng)度短的原因?yàn)椋涸诠麑?shí)繁密的情況下，蟻群算法釋放的信息素濃度不均勻，易陷入局部最優(yōu)解；而改進(jìn)蟻群算法引入了隨時(shí)間改變的自適應(yīng)信息素濃度更新機(jī)制，不會(huì)陷入局部最優(yōu)解.因此，改機(jī)蟻群算法的性能比蟻群算法更優(yōu).

3.2.2 3種模型比較

圖5為改進(jìn)蟻群算法采用3種模型的采摘路徑.由圖5可知，在3種模型中，蟻周模型的路徑長(zhǎng)度最短.

圖5 改進(jìn)蟻群算法采用3種模型的采摘路徑

表3為改進(jìn)蟻群算法采用3種模型的路徑長(zhǎng)度及其對(duì)比.由表3可知，不管柑橘果實(shí)數(shù)量如何變化，蟻周模型的路徑長(zhǎng)度均比蟻量模型和蟻密模型的路徑長(zhǎng)度短.蟻周模型為最優(yōu)模型的原因?yàn)椋合伭磕Ｐ秃拖伱苣Ｐ透滦畔⑺貢r(shí)，選擇的是局部信息素，而蟻周模型選擇的是全局信息素，不易陷入局部最優(yōu)解.因此，改進(jìn)算法應(yīng)該采用蟻周模型.

表3 改進(jìn)蟻群算法采用3種模型的路徑長(zhǎng)度及其對(duì)比

4 結(jié)束語(yǔ)

筆者將柑橘采摘的路徑規(guī)劃抽象為旅行商問題的解集，提出了改進(jìn)蟻群算法，該算法引入了隨時(shí)間改變的自適應(yīng)信息素濃度更新機(jī)制.仿真實(shí)驗(yàn)結(jié)果表明：改進(jìn)蟻群算法的路徑長(zhǎng)度比蟻群算法的路徑長(zhǎng)度短；相對(duì)于蟻量模型和蟻密模型，蟻周模型為最優(yōu)模型，因此改進(jìn)算法應(yīng)該采用蟻周模型進(jìn)行路徑規(guī)劃.