基于改進(jìn)蟻群算法的盤點(diǎn)型機(jī)器人路徑規(guī)劃

馬金科，王 直

(江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引 言

盤點(diǎn)型機(jī)器人是指能夠精確盤點(diǎn)倉庫中的貨品以及可以引導(dǎo)上架新貨品的機(jī)器人。移動機(jī)器人的路徑規(guī)劃是移動機(jī)器人研究的重要分支之一，是機(jī)器人實(shí)現(xiàn)智能化移動的關(guān)鍵[1]。移動機(jī)器人在有障礙物的工作環(huán)境中，按照某一性能指標(biāo)(如工作代價(jià)最小、行走時(shí)間最少、行走路線最短等)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的安全的、無碰的最優(yōu)或次優(yōu)路徑[2]。

目前，常用于移動機(jī)器人路徑規(guī)劃的算法主要有人工勢場法、A*算法、神經(jīng)網(wǎng)絡(luò)法、蟻群法、遺傳算法等[3]。A*算法雖然對比較簡單的地圖搜索速度非?？?，也能找到最優(yōu)路徑，但全局性較差，啟發(fā)函數(shù)選擇不當(dāng)?shù)脑捜菀紫萑胨姥h(huán)。神經(jīng)網(wǎng)絡(luò)法雖然能收斂到最優(yōu)路徑，但環(huán)境改變后必須重新學(xué)習(xí)，在環(huán)境信息不完整或環(huán)境經(jīng)常改變的情況下應(yīng)用起來很困難[4]。模糊推理法雖然避開了其他算法中存在的對環(huán)境信息依賴性強(qiáng)等缺點(diǎn)，但自身的適應(yīng)能力比較差[5]。遺傳算法雖有魯棒性強(qiáng)、全局優(yōu)化等優(yōu)點(diǎn)，但計(jì)算速度不快，容易提前收斂。相對而言，蟻群算法具有分布式計(jì)算、信息正反饋和啟發(fā)式搜索特征，在求解移動機(jī)器人路徑規(guī)劃問題時(shí)更加合適。但基本蟻群算法執(zhí)行過程依賴于大量的迭代和循環(huán)，缺乏實(shí)時(shí)性;運(yùn)行過程中信息素不斷累積，優(yōu)質(zhì)路徑不突出，對于最優(yōu)解的求取有很大影響[6]。對此，文中重點(diǎn)對蟻群算法中的全局初始信息素分配、揮發(fā)系數(shù)隨時(shí)間進(jìn)行相應(yīng)變化，信息素在迭代中更新的方式等方向提出相應(yīng)的改進(jìn)方法。

1 基本蟻群算法

自然界的蟻群在外出覓食時(shí)，會在它們走過的路徑上散發(fā)出一類有特殊氣味的信息素[7]。螞蟻之間依靠這種化學(xué)物質(zhì)實(shí)現(xiàn)信息的交互，并實(shí)時(shí)引導(dǎo)后續(xù)的運(yùn)動方向。每只螞蟻在沒有預(yù)先知道食物所在地的前提下開始搜索食物，并在經(jīng)過的路徑上分泌信息素。而蟻群算法的核心就是：通過若干數(shù)量的螞蟻共同尋路，在各個(gè)途徑帶上分泌信息素來提高食物搜索的效果，最終以最短路徑找到食物。

由上可知，在整個(gè)過程中有兩個(gè)因素會對得出的最優(yōu)路徑造成大的影響：

(1)在選擇下一個(gè)目標(biāo)節(jié)點(diǎn)時(shí)，信息素濃度對螞蟻影響很大，濃度大的螞蟻選擇該路徑的幾率更高。

(2)螞蟻在尋路過程中，節(jié)點(diǎn)路徑上濃度高的路徑，會以較高概率得到保留，相應(yīng)濃度低的路徑會在迭代中被舍棄。

蟻群算法的特點(diǎn)，決定了它在路徑規(guī)劃的范圍較大，且在用戶節(jié)點(diǎn)較多的情況下，能表現(xiàn)出更強(qiáng)的適應(yīng)性和兼容性，同時(shí)在這種應(yīng)用場景下，得到的最優(yōu)路徑結(jié)果也更穩(wěn)定。

旅行商問題(traveling salesman problem，TSP)是在組合型優(yōu)化問題中的一個(gè)典型代表。經(jīng)典的TSP是這樣描述的：一個(gè)推銷員要在所有推銷的城市推銷產(chǎn)品，要求他能夠從一個(gè)起點(diǎn)出發(fā)，最后遍歷所有城市，并回到起點(diǎn)。過程中應(yīng)如何選擇行進(jìn)路線，以使總的行程最短[8]。以TSP(旅行商問題)為背景，蟻群算法中可以將N個(gè)螞蟻比作各個(gè)推銷員，這些螞蟻并不是在同一個(gè)起點(diǎn)出發(fā)，而是分布在各個(gè)節(jié)點(diǎn)出發(fā)。食物所在地則類比為需推銷的城市，蟻穴是集散中心，所有螞蟻對所有食物的地方訪問完后，會回到集散中心。通過多次迭代，所有螞蟻尋出的路徑會收斂出一條最優(yōu)的路徑[9]。為量化闡述蟻群算法，路網(wǎng)中第k只螞蟻選擇下一個(gè)節(jié)點(diǎn)的規(guī)則如下：

(1)

隨著時(shí)間的推移，路途上的信息素會慢慢減弱，每次各個(gè)螞蟻訪問完全部節(jié)點(diǎn)之后，路段上的信息素需要進(jìn)行更新，更新公式為：

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

(3)

Δτij按下列公式更新：

(4)

其中，Q為常量；Lk為第k只螞蟻在本次循環(huán)所經(jīng)過的路徑長度。

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

2.1 揮發(fā)系數(shù)ρ的優(yōu)化

揮發(fā)系數(shù)ρ指信息素濃度逐漸減弱的系數(shù)值，它的設(shè)置決定著螞蟻的搜索效果，也極大影響著算法實(shí)現(xiàn)的性能。若揮發(fā)系數(shù)設(shè)置太小，蟻群對螞蟻的引導(dǎo)作用會過強(qiáng)，導(dǎo)致螞蟻本身搜索的能力降低；若揮發(fā)系數(shù)設(shè)置太大，蟻群對螞蟻引導(dǎo)作用會過小，再次選擇已經(jīng)搜索過的路徑可能性會大大增加，降低了算法的全局搜索能力[10]?；诖耍岢隽俗赃m應(yīng)的揮發(fā)系數(shù)設(shè)置方法，即算法前期設(shè)置較小的揮發(fā)系數(shù)，減小螞蟻間互相吸引，提高搜索效率；算法后期，揮發(fā)系數(shù)設(shè)置較大，提高算法收斂速度。

揮發(fā)系數(shù)ρ自適應(yīng)公式為：

(5)

其中，ρmin為揮發(fā)系數(shù)可以取到的最小值。揮發(fā)系數(shù)隨時(shí)間逐漸減小。

2.2 開始階段信息素分配的優(yōu)化

在傳統(tǒng)算法中，開始階段各個(gè)路徑上的信息素濃度相同，為一個(gè)常數(shù)[11]。這種情況導(dǎo)致的結(jié)果就是算法在初期階段搜索的速度很慢，要經(jīng)過一段時(shí)間的處理，實(shí)現(xiàn)濃度不同對蟻群的影響。所以，文中對各個(gè)路徑上的初始濃度進(jìn)行調(diào)整，加大了起始點(diǎn)和終點(diǎn)連線附近的信息素濃度。這是因?yàn)?，最?yōu)路徑往往分布在起點(diǎn)和終點(diǎn)連線附近。其他區(qū)域出現(xiàn)最優(yōu)路徑的幾率相對較小。這樣在大多數(shù)情況下，改進(jìn)后的算法會更快地找到最優(yōu)路徑，提高了搜索的整體效率。

2.3 信息素更新方式的優(yōu)化

信息素濃度是螞蟻在尋優(yōu)過程中主要參照的依據(jù)[12]，所以，信息素濃度更新的方式直接影響到蟻群算法的準(zhǔn)確性和效率。螞蟻每移動一次稱為一次搜索，經(jīng)過n次搜索后，所有螞蟻就完成了一次迭代。在傳統(tǒng)算法中，信息素的更新只依賴于全局信息素更新，這使得算法容易陷入局部最優(yōu)的陷阱[13]。將信息素濃度的更新分為實(shí)時(shí)更新和全局更新能有效改善這種情況。

螞蟻的實(shí)時(shí)信息素更新公式為：

τij(t+1)=(1-σ)τij(t)+στ0

(6)

其中，σ為實(shí)時(shí)信息素?fù)]發(fā)因子；τ0為信息素初始值。

全局信息素更新時(shí)，每個(gè)螞蟻迭代完成，都會得到這個(gè)螞蟻的路徑[14]。比對這些路徑，按路徑長短排列，在較短路徑上進(jìn)行信息素加強(qiáng)，在較長路徑上進(jìn)行信息素削減。則全局更新的公式為：

τij(t+1)=(1-ρ)τij(t)+ρΔτij

(7)

(8)

其中，Li為本次迭代的最優(yōu)路徑；Lb為當(dāng)前的最優(yōu)路徑；ε為一個(gè)可調(diào)參數(shù)，滿足一次迭代后，加強(qiáng)接近最優(yōu)路徑的路徑上的信息素濃度削減遠(yuǎn)離最優(yōu)路徑上信息素濃度。

通過實(shí)時(shí)和全局信息素更新，螞蟻能夠擺脫求得局部最優(yōu)的陷阱，同時(shí)又能提高尋優(yōu)的效率。

2.4 算法的實(shí)現(xiàn)步驟

改進(jìn)算法的實(shí)現(xiàn)步驟如下：

(1)初始化信息素的分配及其他各種參數(shù)[15]。初始信息素分配時(shí)在起點(diǎn)和終點(diǎn)連線上設(shè)置較大的信息素濃度。對信息素重要程度因子α、能見程度因子β、最大迭代次數(shù)等參數(shù)進(jìn)行初始化。

(2)初始化蟻群，構(gòu)造解空間[16]。

(3)把螞蟻放到起始點(diǎn)進(jìn)行路徑規(guī)劃，按照式5進(jìn)行信息素?fù)]發(fā)因子設(shè)置。

(4)按照式1選擇移動的下一個(gè)節(jié)點(diǎn)。

(5)當(dāng)所有螞蟻完成一次搜索后，按照式6進(jìn)行實(shí)時(shí)信息素更新。

(6)判斷所有螞蟻完成一次迭代與否，完成則轉(zhuǎn)步驟7，未完成轉(zhuǎn)步驟4。

(7)按式7和式8完成全局信息素更新。

(8)判斷是否達(dá)到最大迭代次數(shù)，若未達(dá)到，則開始下一次迭代，達(dá)到后則馬上結(jié)束迭代，得到最優(yōu)的路徑。

算法實(shí)現(xiàn)流程如圖1所示。

圖1 改進(jìn)的蟻群算法實(shí)現(xiàn)流程

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

為了驗(yàn)證改進(jìn)算法的有效性，利用MATLAB平臺對改進(jìn)算法進(jìn)行驗(yàn)證。依據(jù)改進(jìn)算法的實(shí)現(xiàn)步驟，把對應(yīng)參數(shù)初始化為:螞蟻數(shù)目60，迭代數(shù)初始值200，信息素濃度影響因子α=1，能見度影響因子β= 4，揮發(fā)因子按前述自適應(yīng)的方式設(shè)置。分別采用傳統(tǒng)蟻群算法和改進(jìn)蟻群算法在MATLAB環(huán)境下進(jìn)行編程仿真，其仿真結(jié)果對比如圖2和圖3所示。

圖2 基本蟻群算法規(guī)劃出的路徑

圖3 改進(jìn)蟻群算法規(guī)劃出的路徑

從以上對比可知，傳統(tǒng)蟻群算法在搜索初期陷入了局部最優(yōu)，雖然最終也找到了一條最優(yōu)路徑，但路徑質(zhì)量不如改進(jìn)蟻群算法。而改進(jìn)蟻群算法在改進(jìn)了揮發(fā)因子自適應(yīng)，初始濃度分布以及信息素更新方式后，最終規(guī)劃出的最優(yōu)路徑明顯優(yōu)于傳統(tǒng)蟻群算法。

為了更好地驗(yàn)證蟻群算法在收斂速度和最短路徑上的優(yōu)勢，文中給出了傳統(tǒng)蟻群算法和改進(jìn)蟻群算法各次迭代路線的平均距離和最短距離的對比曲線，如圖4和圖5所示。

由圖4和圖5可知，在改進(jìn)算法中，算法的搜索能力有所提升，最優(yōu)路徑得出的收斂速度也更快。對比原始算法，能以不到40次的迭代次數(shù)就得到比原算法更優(yōu)的解，且后續(xù)迭代過程中，最優(yōu)解未出現(xiàn)波動，證明該優(yōu)化算法的可靠性和高效性。

4 結(jié)束語

針對盤點(diǎn)型機(jī)器人路徑規(guī)劃特點(diǎn)，設(shè)計(jì)了改進(jìn)型蟻群算法。改進(jìn)的蟻群算法通過對揮發(fā)因子自適應(yīng)優(yōu)化，初始路徑濃度設(shè)置以及信息素更新方式的優(yōu)化，有效地使傳統(tǒng)算法避免了局部最優(yōu)問題，同時(shí)提高了算法的收斂速度和最優(yōu)解的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法能更快更準(zhǔn)確地找到最優(yōu)解，具有更高的穩(wěn)定性和有效性?；谶@個(gè)改進(jìn)效果，該算法可以應(yīng)用盤點(diǎn)型機(jī)器人，以提高盤點(diǎn)型機(jī)器人盤點(diǎn)物品的能力。