自適應(yīng)螢火蟲(chóng)算法改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃

杜力，徐光輝，汪繁榮

（1.湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院，湖北 武漢 430068；2.湖北工業(yè)大學(xué) 太陽(yáng)能高效利用與儲(chǔ)能系統(tǒng)運(yùn)行控制湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430068）

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題一直是機(jī)器人研究領(lǐng)域的熱點(diǎn)。簡(jiǎn)單而言，移動(dòng)機(jī)器人路徑規(guī)劃是指移動(dòng)機(jī)器人在存在障礙物的環(huán)境中運(yùn)動(dòng)時(shí)，無(wú)人為干預(yù)條件下，尋求一條從起始點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞路徑［1］。根據(jù)機(jī)器人對(duì)作業(yè)環(huán)境的感知程度，路徑規(guī)劃問(wèn)題大體上可以分為全局路徑規(guī)劃和局部路徑規(guī)劃兩類(lèi)［2］。其中，全局路徑規(guī)劃是指機(jī)器人在對(duì)作業(yè)環(huán)境全部已知情況下，利用算法得到一條優(yōu)化的全局最優(yōu)或次優(yōu)路徑，常用方法包括自由空間法［3］，柵格法［4］，A*算法（Astar algorithm）［5］等；局部路徑規(guī)劃是指機(jī)器人通過(guò)自身攜帶的傳感器實(shí)時(shí)獲取自身運(yùn)動(dòng)環(huán)境信息，然后選擇一條從當(dāng)前節(jié)點(diǎn)到某一子節(jié)點(diǎn)的最優(yōu)子路徑，通常采取的方法有人工勢(shì)場(chǎng)法［6］，滾動(dòng)窗口法［7］，Dijkstra算法［8］等。上述這些傳統(tǒng)的路徑規(guī)劃方法雖然簡(jiǎn)單且易于實(shí)現(xiàn)，但適用范圍較小，實(shí)時(shí)性較差。

近年來(lái)，隨著群智能算法的發(fā)展和應(yīng)用，移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題有了更多的解決方案［9-10］，如遺傳算法（genetic algorithm，GA）［11］，蟻群算法（ant colony optimization，ACO）［12-13］，粒子群算法（particle swarm optimization，PSO）［14］等，都已在求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題中取得了比較理想的效果。其中，ACO因其魯棒性強(qiáng)、易于實(shí)現(xiàn)和正反饋機(jī)制等優(yōu)點(diǎn)得到了廣泛應(yīng)用。陳勁峰等［15］分析了父節(jié)點(diǎn)和子節(jié)點(diǎn)間的位置關(guān)系，縮小了蟻群的搜索范圍，加快了蟻群的收斂速度；C.C.Hsu等［16］通過(guò)不斷調(diào)整ACO參數(shù)，建立局部和反向信息素更新機(jī)制，提高了ACO路徑規(guī)劃效果；LIU JH等［17］通過(guò)自適應(yīng)調(diào)整啟發(fā)式信息和加入局部最優(yōu)引導(dǎo)機(jī)制，提高了ACO的計(jì)算效率和在二維環(huán)境路徑規(guī)劃中的收斂速度。雖然上述改進(jìn)的ACO在求解路徑規(guī)劃問(wèn)題過(guò)程中都表現(xiàn)出了良好的性能，但是其求解質(zhì)量與參數(shù)的選擇密切相關(guān)，而參數(shù)的選擇往往過(guò)于依賴(lài)個(gè)人經(jīng)驗(yàn)，這種辦法主觀(guān)性強(qiáng)，智能性差，大大限制其優(yōu)越性。為了更好地發(fā)揮ACO的優(yōu)越性能，文獻(xiàn)［13，18-19］將ACO與PSO融合，把ACO的關(guān)鍵參數(shù)賦給PSO的每個(gè)粒子，經(jīng)過(guò)多次迭代自適應(yīng)地尋找到ACO的最優(yōu)參數(shù)組合。雖然PSO優(yōu)化ACO的參數(shù)有著很好的效果，但PSO參數(shù)較多且設(shè)置較復(fù)雜。2008年，劍橋大學(xué)教授Yang提出了一種啟發(fā)式螢火蟲(chóng)算法（firefly algorithm，F(xiàn)A）［20］，該算法通過(guò)對(duì)自然界中螢火蟲(chóng)會(huì)被比自身亮度高的螢火蟲(chóng)吸引而向其運(yùn)動(dòng)的行為進(jìn)行模擬，建立數(shù)學(xué)模型解決優(yōu)化問(wèn)題。FA具有收斂速度快、操作方便、實(shí)現(xiàn)容易、參數(shù)選擇相對(duì)簡(jiǎn)單等特點(diǎn)。

本文首先分析ACO和FA的基本原理，提出一種螢火蟲(chóng)算法改進(jìn)蟻群算法的混合智能算法（firefly algorithm improved ant colony algorithm，F(xiàn)AACA），其核心思想是利用FA對(duì)ACO的核心參數(shù)進(jìn)行優(yōu)化，避免傳統(tǒng)人工經(jīng)驗(yàn)選取參數(shù)對(duì)ACO性能的影響。其次，為減少兩種算法混合后的時(shí)間開(kāi)銷(xiāo)，采取精英策略和承接式結(jié)合的信息素更新方式提高ACO全局搜索速度，并對(duì)FA的步長(zhǎng)因子進(jìn)行自適應(yīng)設(shè)計(jì)，防止螢火蟲(chóng)在最優(yōu)值附近出現(xiàn)震蕩，提高整個(gè)混合算法的求解精度，從而得到一種自適應(yīng)螢火蟲(chóng)算法改進(jìn)蟻群算法的混合智能算法（adaptive firefly algorithm improved ant colony algorithm，AFA-ACA）。最后，在不同柵格環(huán)境下進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn)，仿真結(jié)果表明所提算法比傳統(tǒng)的ACO規(guī)劃得到的路徑更短，得到最短路徑所需迭代次數(shù)更少，運(yùn)行更加平穩(wěn)。

1 算法數(shù)學(xué)模型

1.1 ACO的數(shù)學(xué)模型

ACO是將自然界中蟻群覓食行為抽象化后得 到 的 一 種 啟 發(fā) 式 搜 索 算 法［13，19，21］。螞 蟻k（k=1，2，…，m）在t時(shí)刻運(yùn)動(dòng)方向的選擇由各個(gè)路徑上的信息素濃度決定。在t時(shí)刻螞蟻從位置i選擇下一個(gè)位置j的概率為

式中：τij（t）為t時(shí)刻位置i與位置j之間的路徑上的信息素；ηij（t）為啟發(fā)式函數(shù)，常取ηij（t）=1/dij，dij為位置i與位置j之間的歐式距離；α為信息啟發(fā)式因子；β為期望啟發(fā)式因子；下一個(gè)可移動(dòng)?xùn)鸥窦嫌肨allowed，k表示。每只螞蟻在完成一次遍歷后，對(duì)每條路徑上所留的信息素按照式（2）處理：

式中：ρ為信息素?fù)]發(fā)系數(shù)（0＜ρ＜1）；τij為位置i與位置j之間路徑上的信息素量；為第k只螞蟻在本次循環(huán)中殘留在位置i與位置j之間的信息量。且有，

式中：Q為信息素強(qiáng)度；Lk為路徑總長(zhǎng)度。

1.2 ACO參數(shù)分析

ACO路徑規(guī)劃中，初始化參數(shù)的選擇對(duì)算法性能有著重要影響［21］。

（1）信息啟發(fā)式因子α主要影響螞蟻選擇路徑的隨機(jī)性，該值越大時(shí)，表明啟發(fā)式信息在蟻群搜索過(guò)程中占主導(dǎo)作用，蟻群搜索路徑的隨機(jī)性越低，算法容易陷入局部最優(yōu)；該值越小時(shí)，搜索路徑的隨機(jī)性就會(huì)越高，蟻群收斂速度變慢。

（2）期望啟發(fā)式因子β主要決定環(huán)境因素對(duì)螞蟻路徑選擇概率的影響，該值過(guò)大時(shí)，環(huán)境因素占主導(dǎo)作用，蟻群更趨向于搜索較近的下一節(jié)點(diǎn)，隨機(jī)性降低，算法容易陷入局部最優(yōu)；該值過(guò)小時(shí)，則會(huì)導(dǎo)致隨機(jī)性變大，路徑尋優(yōu)變得更加困難，蟻群收斂速度變慢。

（3）信息素?fù)]發(fā)系數(shù)ρ主要影響算法的收斂速度和全局搜索能力，該值越大，路徑上信息素濃度下降越快，算法全局搜索能力降低，收斂速度變快；該值越小，路徑上信息素濃度下降越慢，算法全局搜索能力提高，收斂速度變慢。

1.3 FA的數(shù)學(xué)模型

FA與PSO原理類(lèi)似，都是基于群體解的隨機(jī)搜索算法［22］。群體中每個(gè)個(gè)體都代表一個(gè)候選解，用亮度代表解的適應(yīng)性，適應(yīng)性越好的個(gè)體亮度越高。群體中的螢火蟲(chóng)沒(méi)有性別之分，若螢火蟲(chóng)在視野范圍內(nèi)發(fā)現(xiàn)亮度高的螢火蟲(chóng)即會(huì)向其移動(dòng)，最終所有螢火蟲(chóng)都聚集于亮度最高的螢火蟲(chóng)，即最優(yōu)解。

假設(shè)Xi=（xi1，xi2，…，xiD）是群體第i只螢火蟲(chóng)（解），其中i=1，2，…，N，N和D分別為群體大小和問(wèn)題維數(shù)。對(duì)于任意兩只螢火蟲(chóng)Xi和Xj（i≠j），它們之間的吸引可表示為

式中：β0為r=0時(shí)的吸引力；γ為光吸收系數(shù)；rij為Xi和Xj之間距離，定義為

對(duì)于Xi和Xj（i≠j），較差的螢火蟲(chóng)將向較好的螢火蟲(chóng)移動(dòng)。假設(shè)Xi優(yōu)于Xj，則Xj向Xi移動(dòng)，其移動(dòng)方式為

式中：d=1，2，…，D；ζ∈ 0，[ ]1為步長(zhǎng)因子；ε為［-0.5，0.5］區(qū)內(nèi)的隨機(jī)數(shù)；t為迭代次數(shù)。

2 算法混合

ACO具有魯棒性強(qiáng)、易于與其他啟發(fā)式算法結(jié)合等優(yōu)點(diǎn)，但是其求解性能過(guò)于依賴(lài)參數(shù)的選擇，而FA在解決許多優(yōu)化問(wèn)題時(shí)表現(xiàn)出了搜索能力強(qiáng)、收斂速度快等良好性能。本文在A(yíng)CO的基礎(chǔ)上引入FA對(duì)ACO核心參數(shù)進(jìn)行優(yōu)化，設(shè)計(jì)一種螢火蟲(chóng)算法改進(jìn)蟻群算法的混合智能算法（FA-ACA）。

FA-ACO核心思想是采用FA對(duì)ACO的關(guān)鍵參數(shù)進(jìn)行優(yōu)化，利用螢火蟲(chóng)算法中每只螢火蟲(chóng)的初始位置代表ACO的一組重要參數(shù)，通過(guò)螢火蟲(chóng)算法自適應(yīng)地選取一組相對(duì)最佳參數(shù)，從而改變傳統(tǒng)的經(jīng)驗(yàn)選參方式，具體運(yùn)行步驟如下。

步驟一初始化螢火蟲(chóng)算法各個(gè)參數(shù)：最大吸引力β0，步長(zhǎng)因子ζ，最大迭代次數(shù)Tmax等。

步驟二設(shè)置每只螢火蟲(chóng)的位置對(duì)應(yīng)一組蟻群算法的重要參數(shù)α，β，ρ，螢火蟲(chóng)在解空間中的位置即為其參數(shù)值。

步驟三利用螢火蟲(chóng)位置信息對(duì)應(yīng)的參數(shù)運(yùn)行蟻群算法，得到當(dāng)前該螢火蟲(chóng)位置信息對(duì)應(yīng)的適應(yīng)度函數(shù)值。

步驟四利用步驟三中適應(yīng)度函數(shù)值，更新對(duì)應(yīng)螢火蟲(chóng)的亮度信息，螢火蟲(chóng)向亮度更高的個(gè)體聚集，并更新位置。

步驟五判斷是否達(dá)到終止條件（螢火蟲(chóng)的亮度和位置不再更新或達(dá)到了最大迭代次數(shù)），若滿(mǎn)足條件，則輸出當(dāng)前螢火蟲(chóng)對(duì)應(yīng)的一組最優(yōu)參數(shù)；否則，利用位置更新后螢火蟲(chóng)對(duì)應(yīng)的參數(shù)信息返回繼續(xù)執(zhí)行步驟三。

步驟六利用步驟五得到的最優(yōu)參數(shù)組合，代入蟻群算法并運(yùn)行。

步驟七輸出最優(yōu)解。

3 自適應(yīng)螢火蟲(chóng)算法改進(jìn)的蟻群算法

由FA-ACA的執(zhí)行步驟可知，螢火蟲(chóng)位置每改變一次，ACO都將被完整地調(diào)用一次，所以該算法雖求解質(zhì)量較高，但時(shí)間成本極大。且傳統(tǒng)的FA步長(zhǎng)固定，搜索過(guò)程會(huì)出現(xiàn)個(gè)體移動(dòng)步長(zhǎng)大于個(gè)體與最優(yōu)值之間距離的情況，導(dǎo)致個(gè)體在更新位置信息時(shí)，在最優(yōu)值附近出現(xiàn)震蕩，從而導(dǎo)致整個(gè)混合算法求解效率和求解精度降低?；诖?，本文對(duì)FA-ACA中ACO的信息素采取精英策略與承接式相結(jié)合的更新方式，并對(duì)FA的步長(zhǎng)因子進(jìn)行重新設(shè)計(jì)，從而得到一種自適應(yīng)螢火蟲(chóng)算法改進(jìn)蟻群算法的混合算法（AFA-ACA）。

3.1 蟻群算法信息素更新方式

在執(zhí)行步驟三時(shí)，采用精英策略對(duì)蟻群的信息素進(jìn)行更新，即蟻群每進(jìn)化一代，對(duì)最優(yōu)路徑上的信息素進(jìn)行強(qiáng)化更新，其他情況下信息素不進(jìn)行更新。參數(shù)切換時(shí)，采用承接式的信息素更新方式，即每次參數(shù)切換，信息素不重新初始化，下一代參數(shù)承接上一代參數(shù)留下的信息素繼續(xù)進(jìn)行迭代更新，避免參數(shù)切換時(shí)初期信息素的積累過(guò)程，極大提高混合算法的收斂速度。信息素更新公式為

式中：τij1（t）為按照全局同步信息素更新方式（即在蟻群算法被調(diào)用的過(guò)程中，蟻群每進(jìn)化一代，信息素隨之更新，切換參數(shù)時(shí)，信息素不重新初始化，繼續(xù)進(jìn)行更新，更新公式見(jiàn)式（2）～（3））進(jìn)行信息素更新時(shí)，持續(xù)到當(dāng)前代次環(huán)境中的信息量；Δτij（t）′為本次循環(huán)中，最優(yōu)螞蟻在路徑［i，j］上釋放的信息量，

式中：ω為常數(shù)；Gk為最短路徑長(zhǎng)度。

3.2 螢火蟲(chóng)算法步長(zhǎng)因子的自適應(yīng)設(shè)計(jì)

在標(biāo)準(zhǔn)的螢火蟲(chóng)算法中，亮度低的螢火蟲(chóng)會(huì)被亮度高的螢火蟲(chóng)吸引并向其移動(dòng)，群體中的個(gè)體會(huì)逐漸聚集，最后收斂于亮度最高的一點(diǎn)。因此，對(duì)群體中任意兩個(gè)個(gè)體Xi和Xj，都有

式中，i，j=1，2，3，…，N。

由式（9）～（10）可以看出，所有的個(gè)體（解）都收斂于一點(diǎn)，且收斂后的解不再發(fā)生變化。根據(jù)式（6）、（9）和（10）可得

由式（11）可以看出，當(dāng)螢火蟲(chóng)算法收斂時(shí)，步長(zhǎng)因子ζ趨近于0。

基于以上分析，本文對(duì)FA的參數(shù)ζ進(jìn)行自適應(yīng)設(shè)計(jì)，更新公式為

式中，Tmax為螢火蟲(chóng)的最大迭代次數(shù)，隨著迭代次數(shù)增加，步長(zhǎng)因子逐漸減小至0。

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文所提算法的有效性和求解質(zhì)量，選擇兩種不同柵格環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，并利用本文所提算法和傳統(tǒng)蟻群算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)選擇MATLAB 2018a，計(jì)算機(jī)CPU型號(hào)為intel i78th，運(yùn)行內(nèi)存為8 GB。

4.1 環(huán)境建模

利用柵格法建立機(jī)器人運(yùn)動(dòng)的環(huán)境模型［13］。為了減少數(shù)據(jù)計(jì)算量，忽略機(jī)器人的大小體積等，將移動(dòng)機(jī)器人作質(zhì)點(diǎn)化處理。如圖1所示，假設(shè)每個(gè)柵格對(duì)應(yīng)二維空間中的坐標(biāo)為（xi，yi），以（0.5，9.5）為中心的網(wǎng)格數(shù)為1，以（1.5，9.5）為中心的網(wǎng)格數(shù)為2，以此類(lèi)推，每個(gè)柵格從左到右，從上到下編號(hào)，各柵格坐標(biāo)與序號(hào)的關(guān)系為

圖1 柵格環(huán)境Fig.1 Grid environment

式中：i為柵格號(hào)；N為柵格地圖的行數(shù)和列數(shù)。假設(shè)每個(gè)柵格邊長(zhǎng)均為1 cm。

4.2 算法的參數(shù)設(shè)置

螢火蟲(chóng)算法參數(shù)取值見(jiàn)表1，設(shè)其適應(yīng)度函數(shù)為Fitk（s）=1/Lk（s）。蟻群算法的參數(shù)α，β和ρ由螢火蟲(chóng)空間位置給出。文獻(xiàn)［21］經(jīng)過(guò)多次仿真實(shí)驗(yàn)，得到了ACO各個(gè)參數(shù)最佳取值范圍，以此作為參考，確定ACO參數(shù)的搜索范圍，具體見(jiàn)表2。

表1 螢火蟲(chóng)算法初始化參數(shù)Tab.1 FA initialization parameters

表2 ACO初始化參數(shù)值范圍Tab.2 ACO initialization parameter value range

4.3 路徑規(guī)劃結(jié)果及比較

文獻(xiàn)［23］在解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題時(shí)，基于經(jīng)驗(yàn)選取參數(shù)α=1，β=0.7和ρ=0.3?，F(xiàn)選取2種不同的柵格環(huán)境，運(yùn)用上述參數(shù)運(yùn)行傳統(tǒng)的ACO，并與本文所提算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)。兩種算法最大迭代次數(shù)為100次，蟻群數(shù)量為50，每種算法運(yùn)行20次。

本文選取其中一組實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，在柵格環(huán)境1和2下，ACO和AFA-ACA規(guī)劃后的最優(yōu)路徑和路徑長(zhǎng)度收斂曲線(xiàn)如圖2～3所示。

圖2 柵格環(huán)境1下ACO和AFA-ACA最優(yōu)路徑和收斂曲線(xiàn)Fig.2 Optimal path and convergence curves of ACO and AFA-ACA in grid environment 1

圖3 柵格環(huán)境2中ACO和AFA-ACA的最優(yōu)路徑和收斂曲線(xiàn)Fig.3 Optimal path and convergence curves of ACO and AFA-ACA in grid environment 2

現(xiàn)將兩種不同柵格環(huán)境下的AFA-ACA和ACO路徑規(guī)劃結(jié)果記錄在表3和表4中。

表3 柵格環(huán)境1中數(shù)據(jù)比較Tab.3 Data comparison in grid environment 1

表4 柵格環(huán)境2中數(shù)據(jù)比較Tab.4 Data comparison in grid environment 2

仿真結(jié)果表明，兩種算法都找到了一條從起點(diǎn)到終點(diǎn)的無(wú)碰撞路徑，驗(yàn)證了AFA-ACA的可行性。由圖2～3可知，隨著迭代次數(shù)增加，AFAACA路徑規(guī)劃得到的路徑長(zhǎng)度不斷變短，說(shuō)明其優(yōu)化能力在不斷增強(qiáng)，與ACO相比，AFA-ACA有著更好的智能性和穩(wěn)定性。柵格環(huán)境1下，AFAACA與ACO得到的最短路徑長(zhǎng)度都為29.21 cm，但ACO的迭代次數(shù)為76次，AFA-ACA的迭代次數(shù)為18次。柵格環(huán)境2下，AFA-ACA與ACO得到的最短路徑長(zhǎng)度分別為30.97 cm和32.73 cm，前者得到的路徑長(zhǎng)度更短，且AFAACA的迭代次數(shù)為5次，ACO的迭代次數(shù)為78次。兩種柵格環(huán)境下的路徑規(guī)劃仿真結(jié)果都表明，與傳統(tǒng)ACO相比，本文所提算法在迭代次數(shù)和算法的平穩(wěn)性上都有明顯提升，滿(mǎn)足移動(dòng)機(jī)器人的路徑規(guī)劃要求。

5 結(jié) 語(yǔ)

AFA-ACA能很好解決ACO求解多變的路徑規(guī)劃問(wèn)題時(shí)過(guò)于依賴(lài)參數(shù)的選擇等問(wèn)題。將AFA-ACA用于移動(dòng)機(jī)器人路徑規(guī)劃中，與傳統(tǒng)的ACO相比，前者找到最優(yōu)路徑所需迭代次數(shù)更少，且算法收斂性和穩(wěn)定性都有很大提升。同時(shí)，本文的研究工作還有許多需要改進(jìn)的地方，比如如何減少算法復(fù)雜度，如何將該算法用于局部路徑規(guī)劃問(wèn)題中，如何提高該算法的其他性能等。