增加方向性信息素的改進(jìn)蟻群路徑規(guī)劃算法

陳繼清，莫榮現(xiàn)，譚成志，劉 旭，王志奎

（1.廣西大學(xué) 機(jī)械工程學(xué)院，廣西 南寧 530004；2.廣西制造系統(tǒng)與先進(jìn)制造技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530004）

0 引言

移動(dòng)機(jī)器人是集監(jiān)測(cè)傳感、動(dòng)態(tài)決策、路徑規(guī)劃、行為控制和執(zhí)行為一體的復(fù)雜智能控制系統(tǒng)。它的“智能”主要體現(xiàn)在機(jī)器人在運(yùn)動(dòng)過(guò)程中是否具有良好的環(huán)境交互能力，這一能力主要指路徑規(guī)劃能力。對(duì)路徑規(guī)劃的研究可以追溯到20 世紀(jì)60年代，經(jīng)過(guò)幾十年的研究和發(fā)展，大量?jī)?yōu)良的算法被提出，如A?star 算法、人工勢(shì)場(chǎng)法、模糊控制算法等傳統(tǒng)算法和蟻群算法、魚(yú)群算法等仿生智能算法。其中，蟻群算法因?yàn)轸敯粜詮?qiáng)、易與其他算法結(jié)合、能并行運(yùn)算等優(yōu)點(diǎn)被廣泛用于解決移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。從20 世紀(jì)90年代提出至今，無(wú)數(shù)專家和學(xué)者對(duì)其進(jìn)行改進(jìn)，使蟻群算法成功應(yīng)用在不同的行業(yè)。如文獻(xiàn)[8]利用蟻群算法來(lái)優(yōu)化生產(chǎn)車間的運(yùn)輸效率，有效地節(jié)約能源和降低生產(chǎn)成本；文獻(xiàn)[9]提出一種作業(yè)路徑生成算法和蟻群算法相結(jié)合的改進(jìn)蟻群算法，并應(yīng)用在無(wú)人機(jī)植保方面，有效縮短了無(wú)人機(jī)的搜索路徑等。

然而，蟻群算法也有易受參數(shù)影響、收斂速度慢、易陷入局部最優(yōu)解和前期路徑有效性差等缺點(diǎn)。根據(jù)文獻(xiàn)[10?11]和蟻群算法程序可知，蟻群算法在找到可行路徑前，每個(gè)柵格的信息素濃度都相等，蟻群算法根據(jù)轉(zhuǎn)移概率公式隨機(jī)地選擇可行柵格，這可能會(huì)出現(xiàn)蟻群算法搜尋遠(yuǎn)離目標(biāo)點(diǎn)的方向，從而增加搜索時(shí)間和加大陷入局部最優(yōu)解的概率。此外，文獻(xiàn)[10]提出的蟻群算法前期的路徑有效性差；文獻(xiàn)[12?13]提及的蟻群算法的收斂速度慢和搜索時(shí)間長(zhǎng)。為了解決這些問(wèn)題，本文提出一種改進(jìn)的蟻群算法。

1 改進(jìn)蟻群算法描述

蟻群算法的改進(jìn)包括兩個(gè)部分：第一個(gè)部分是提出一種方向性信息素，該信息素與目標(biāo)點(diǎn)方向的夾角有關(guān)，越靠近目標(biāo)點(diǎn)方向信息素濃度越大，反之則越小。引入方向性信息素可以減少蟻群算法前期的盲目搜索，縮短搜索時(shí)間、減少轉(zhuǎn)折點(diǎn)數(shù)量和蟻群算法陷入局部最優(yōu)解的概率。第二個(gè)部分是提出一種針對(duì)方向性信息素的蒸發(fā)函數(shù)，該蒸發(fā)函數(shù)能減少前期方向性信息素濃度的蒸發(fā)，使蟻群算法更快速地搜索到可行路徑，進(jìn)而縮短搜索時(shí)間，減少迭代次數(shù)；而后期能加快方向性信息素濃度的蒸發(fā)，減少方向性信息素濃度對(duì)原有信息素濃度的影響。

1.1 方向性信息素

根據(jù)蟻群轉(zhuǎn)移概率公式（1）可知，蟻群算法在沒(méi)有信息素殘留的初期，每個(gè)方向的概率是一樣的，因而每只螞蟻會(huì)隨機(jī)選擇搜索方向，這可能導(dǎo)致螞蟻選擇與目標(biāo)點(diǎn)方向相反的路徑進(jìn)行搜索，增加了前期的搜索時(shí)間，可能使搜尋的路徑長(zhǎng)度陷入局部最優(yōu)解。為了解決這個(gè)問(wèn)題，本文提出一種方向性信息素。方向性信息素與偏離目標(biāo)點(diǎn)方向的夾角有關(guān)，當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在0°～180°時(shí)，夾角越小，方向性信息素的數(shù)值越大；當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在180°～360°時(shí)，夾角越大，方向性信息素的數(shù)值越大。

本文將方向性信息素和蟻群算法原有的轉(zhuǎn)移概率公式結(jié)合起來(lái)，通過(guò)方向性信息素濃度限制蟻群算法前期對(duì)偏離目標(biāo)點(diǎn)方向的搜索，從而避免蟻群算法陷入局部最優(yōu)解和減少搜索時(shí)間。帶有方向性信息素的轉(zhuǎn)移概率公式前期大概率會(huì)選擇靠近目標(biāo)點(diǎn)方向的路徑，減少前期盲目搜索的時(shí)間。

為了設(shè)計(jì)出滿足要求的方向性信息素函數(shù)，本文分兩步：第一步是確定選取基本函數(shù)種類和確定遞增遞減關(guān)系，得出函數(shù)的大概輪廓；第二步是利用實(shí)驗(yàn)的方法將函數(shù)中特殊位置的坐標(biāo)求出，然后利用插值的方法求出最終函數(shù)。

首先確定選取基本函數(shù)種類和遞增、遞減關(guān)系。方向性信息素函數(shù)與偏離目標(biāo)點(diǎn)方向的夾角有關(guān)，因此選取三角函數(shù)cos和sin作為基本函數(shù)。其次，偏離目標(biāo)點(diǎn)方向的夾角為0°～360°，且當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在0°～180°時(shí)，夾角越小，方向性信息素的數(shù)值越大；當(dāng)偏離目標(biāo)點(diǎn)方向的夾角在180°～360°時(shí)，夾角越大，方向性信息素的數(shù)值越大。為了方便函數(shù)擬合，本文規(guī)定當(dāng)偏離目標(biāo)點(diǎn)方向的夾角為180°時(shí)，方向性信息素大小為0。由此可知，方向性信息素函數(shù)在0°～180°遞減，在180°～360°遞增，在夾角為180°時(shí)方向性信息素大小為0。第二步，做如下實(shí)驗(yàn)：分別在偏離目標(biāo)點(diǎn)方向夾角為0°，45°和90°時(shí)加入等梯度的方向性信息素，求出0°，45°和90°的最優(yōu)路徑長(zhǎng)度對(duì)應(yīng)的方向性信息素；然后，利用函數(shù)擬合的方法求出方向性信息素的函數(shù)表達(dá)式。方向性信息素的取值范圍為[0，1.6]，步長(zhǎng)為0.1。蟻群算法的基本參數(shù)為：=1；=8；=1；=0.6；=200；=50。

方向性信息素的大小和算法最優(yōu)路徑的關(guān)系如圖1 所示。

圖1 三種夾角的方向性信息素與最優(yōu)路徑的關(guān)系

從圖1 可以看出：偏離目標(biāo)點(diǎn)方向夾角為0，加入方向性信息素的值為1.4 時(shí)，算法路徑最短；同理，夾角為45°和90°，加入方向性信息素分別是1.2 和0.7 時(shí)，路徑最短。

0°，45°和90°與360°，325°和270°是對(duì)稱的，且當(dāng)夾角為180°時(shí)的方向性信息素濃度為0。因此，可以通過(guò)上述求出的7 個(gè)點(diǎn)擬合出方向性信息素的函數(shù)。擬合結(jié)果如下：

式中為偏離目標(biāo)點(diǎn)方向的夾角。擬合的函數(shù)圖像如圖2 所示。從圖2 可以看出，方向性信息素函數(shù)是連續(xù)的，蟻群算法的搜索方向越靠近目標(biāo)點(diǎn)方向，方向性信息素的數(shù)值越大。而由蟻群轉(zhuǎn)移概率公式可知，蟻群算法在初期階段向每個(gè)方向搜索的概率是一樣的，如果加上方向性信息素，那么靠近目標(biāo)點(diǎn)方向搜索的概率會(huì)變大，避免了前期蟻群算法其他非必要方向的搜索，可大大縮短搜索的時(shí)間；同時(shí)還可以避免路徑長(zhǎng)度陷入局部最優(yōu)解，因?yàn)榉较蛐孕畔⑺氐南拗剖瓜伻核惴ǔ繕?biāo)點(diǎn)方向搜索的概率增大，而朝著目標(biāo)點(diǎn)方向搜索的路徑長(zhǎng)度最優(yōu)。最后，增加方向性信息素的蟻群算法還可以增加前期路徑的有效性，因?yàn)榍捌谙伻核惴ㄊ菦](méi)有目標(biāo)點(diǎn)方向的盲目搜索，所以搜索的方向是隨機(jī)的，只有小部分路徑能“幸運(yùn)”地到達(dá)目標(biāo)點(diǎn)，且路徑長(zhǎng)度不是最優(yōu)。而增加方向性概率的蟻群算法開(kāi)始就有目標(biāo)點(diǎn)方向的指引，能到達(dá)目標(biāo)點(diǎn)的概率增大且路徑長(zhǎng)度比蟻群算法要短，因而前期的路徑有效性增加。

圖2 方向性信息素函數(shù)圖像

方向性信息素在前期可以減少蟻群算法的搜索時(shí)間，提高算法的效率。但方向性信息素不會(huì)隨著迭代次數(shù)改變，而殘留的信息素不斷蒸發(fā)，導(dǎo)致殘留信息素濃度比方向性信息素濃度小，最后使蟻群算法尋路失敗或陷入局部最優(yōu)解。為此，需要引入一種適合的蒸發(fā)函數(shù)。該蒸發(fā)函數(shù)前期需要減少方向性信息素的蒸發(fā)，使改進(jìn)的蟻群算法能快速找到可行路徑，避免局部最優(yōu)解和縮短時(shí)間；而后期則加快方向性信息素的蒸發(fā)，避免方向性信息素的濃度影響新增的信息素濃度，從而影響蟻群算法最優(yōu)路徑的搜索。

1.2 針對(duì)方向性信息素的蒸發(fā)函數(shù)

為了發(fā)揮方向性信息素前期的作用，避免后期方向性信息素對(duì)新增信息素的影響，需要合適的蒸發(fā)函數(shù)來(lái)調(diào)節(jié)每次迭代后的方向性信息素濃度。本文列出蟻群算法的蒸發(fā)函數(shù)，通過(guò)分析該蒸發(fā)函數(shù)來(lái)確定方向性信息素的蒸發(fā)函數(shù)。蟻群算法的蒸發(fā)函數(shù)如下：

式中：是蒸發(fā)系數(shù)；是迭代次數(shù)；τ(0) 表示信息素的初始濃度，一般為8。

原始的蒸發(fā)函數(shù)不能滿足方向性信息素前期減少蒸發(fā)而后期加快蒸發(fā)的要求，因此本文對(duì)原有的蒸發(fā)函數(shù)進(jìn)行改進(jìn)，假設(shè)方向性信息素蒸發(fā)函數(shù)的表達(dá)式如下：

式中：τ(0) 是方向性信息素的初始濃度；是待確定的系數(shù)。因?yàn)榉较蛐孕畔⑺匾谇捌诼窂降倪x擇中占主導(dǎo)作用，所以方向性信息素的初始濃度要比信息素的初始濃度高。其次，為了加快后期方向性信息素的蒸發(fā)，方向性信息素的蒸發(fā)函數(shù)要比蟻群蒸發(fā)函數(shù)更快遞減。根據(jù)上述兩個(gè)條件不難得出，τ( 0 )>τ( 0 )=8 且>1。

為了求出系數(shù)和方向性信息素的初始濃度τ( 0 )，本文設(shè)計(jì)如下實(shí)驗(yàn)：設(shè)置等梯度實(shí)驗(yàn)求出改進(jìn)蟻群算法路徑長(zhǎng)度和迭代次數(shù)最優(yōu)時(shí)的初始方向性信息素濃度τ( 0 )和系數(shù)。初始方向性信息素濃度τ( 0 )的取值范圍為[8，10]，梯度步長(zhǎng)為1；系數(shù)的取值范圍為[1，2.5]，梯度步長(zhǎng)為0.1。初始方向性信息素濃度為8，9，10 時(shí)，系數(shù)與路徑長(zhǎng)度、迭代次數(shù)的關(guān)系如圖3圖5 所示。

圖3 初始濃度為8 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系

由圖3 可知，當(dāng)初始濃度為8、系數(shù)為1.8 時(shí)，算法路徑長(zhǎng)度最短，為42.183 8，迭代次數(shù)為76 次；由圖4 可知，初始濃度為9、系數(shù)為1.9 時(shí)，算法路徑長(zhǎng)度最短且迭代次數(shù)最優(yōu)，分別為42.183 8 和51；由圖5 可知，初始濃度為10、系數(shù)為1.2 時(shí)，算法路徑長(zhǎng)度最短且迭代次數(shù)最優(yōu)，分別為42.183 8 和49。通過(guò)上述實(shí)驗(yàn)可知，當(dāng)初始濃度取10，系數(shù)取1.2 時(shí)改進(jìn)蟻群算法路徑長(zhǎng)度和迭代次數(shù)最優(yōu)，所以方向性信息素的蒸發(fā)函數(shù)表達(dá)式如下：

圖4 初始濃度為9 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系

圖5 初始濃度為10 時(shí)a 與路徑長(zhǎng)度和迭代次數(shù)的關(guān)系

式中，方向性信息素的初始濃度τ( 0 )為10，系數(shù)為1.2。

引入方向性信息素蒸發(fā)函數(shù)可以減少算法初期方向性信息素濃度的蒸發(fā)，使蟻群算法大概率向目標(biāo)點(diǎn)方向搜索，減少非必要方向的搜索，從而減少搜索時(shí)間；而后期則加快方向性信息素濃度的蒸發(fā)，減少對(duì)殘留信息素濃度的影響。

1.3 改進(jìn)的蟻群算法轉(zhuǎn)移概率公式

式中，為當(dāng)前節(jié)點(diǎn)前進(jìn)方向與目標(biāo)節(jié)點(diǎn)的夾角。

由公式（6）可以看出，改進(jìn)蟻群算法的轉(zhuǎn)移概率公式由兩部分組成，前面的部分是原有的轉(zhuǎn)移概率公式，后面的部分是方向性信息素和對(duì)應(yīng)的蒸發(fā)函數(shù)。原有的轉(zhuǎn)移概率公式在開(kāi)始階段由于沒(méi)有殘留信息素，所以向每個(gè)方向搜索的概率相同，而方向性信息素越靠近目標(biāo)點(diǎn)方向數(shù)值越大，所以前期蟻群算法的搜索方向由方向性信息素決定，且大概率向目標(biāo)點(diǎn)方向搜索。而后期方向性信息素比殘留信息素蒸發(fā)快，所以后期方向性信息素對(duì)蟻群算法搜索方向的影響變小，防止蟻群算法受方向性信息素的影響而無(wú)法收斂或陷入局部最優(yōu)解。

圖6 是改進(jìn)蟻群算法的程序流程。首先初始化所有參數(shù)；然后開(kāi)始循環(huán)迭代次數(shù)和螞蟻個(gè)數(shù)，根據(jù)轉(zhuǎn)移概率選擇搜索節(jié)點(diǎn)并修改禁忌表；所有螞蟻搜索完成便更新原始信息素和方向性信息素，再開(kāi)始下一次迭代，直到迭代次數(shù)完成；最后輸出最優(yōu)解并結(jié)束程序。

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

2 仿真分析與對(duì)比

為了驗(yàn)證改進(jìn)蟻群算法的性能，將改進(jìn)蟻群算法、原始蟻群算法和文獻(xiàn)[10]算法進(jìn)行仿真分析，仿真地圖采用30×30 的隨機(jī)柵格地圖，障礙比為0.2，機(jī)器人的起點(diǎn)坐標(biāo)為（0.5，29.5），終點(diǎn)坐標(biāo)為（29.5，0.5）。三種蟻群算法的隨機(jī)地圖對(duì)比結(jié)果如圖7 所示。

圖7 30×30 障礙比為0.2 的隨機(jī)地圖對(duì)比

為了對(duì)比改進(jìn)算法和原始算法、文獻(xiàn)[10]算法的性能，本文列出路徑長(zhǎng)度、搜索時(shí)間、迭代次數(shù)的對(duì)比，如表1 所示。

表1 三種蟻群算法對(duì)比

從表1 可知，相比原始蟻群算法，改進(jìn)算法所需的迭代次數(shù)更少，路徑長(zhǎng)度也更短。迭代次數(shù)變少是因?yàn)榉较蛐孕畔⑺乜梢詼p少前期的盲目搜索，使蟻群算法能更快速地搜索到可行路徑；路徑長(zhǎng)度變短是因?yàn)榉较蛐孕畔⑺乜梢员苊庀伻核惴ㄏ萑刖植孔顑?yōu)解。文獻(xiàn)[10]的算法在路徑長(zhǎng)度、搜索時(shí)間優(yōu)于原始蟻群算法，但路徑長(zhǎng)度和搜索時(shí)間都比本文算法更長(zhǎng)，因?yàn)樵撍惴ㄖ灰?guī)定了核心區(qū)域的信息素減少蒸發(fā)，蟻群算法會(huì)大概率在核心區(qū)域搜索，但沒(méi)有指向目標(biāo)點(diǎn)方向的信息素，無(wú)法保證蟻群算法以最短的路徑向目標(biāo)點(diǎn)方向搜索，所以路徑長(zhǎng)度更長(zhǎng)、搜索時(shí)間也更久。

此外，圖7b）中改進(jìn)算法的收斂曲線比原始蟻群算法更快速地達(dá)到平滑，震蕩幅度更小。由表1 可知，改進(jìn)的蟻群算法性能要比原始的蟻群算法更好，路徑長(zhǎng)度縮短了3.15%，迭代次數(shù)減少了50.74%，搜索時(shí)間縮短了14.19%；相比文獻(xiàn)[10]的算法，本文算法在路徑長(zhǎng)度上縮短了1.87%，在搜索時(shí)間上減少了6.79%，在迭代數(shù)上減少了45%，本文算法在搜索時(shí)間和路徑長(zhǎng)度上優(yōu)于文獻(xiàn)[10]的算法。

3 實(shí)驗(yàn)分析

本文用TurtleBot2 機(jī)器人來(lái)驗(yàn)證改進(jìn)蟻群算法的性能。TurtleBot2 是一種開(kāi)放式的機(jī)器人平臺(tái)，最大的移動(dòng)速度為0.7 m/s，最大的轉(zhuǎn)向速度為180（°）/s。為了提高測(cè)試的精度，設(shè)定TurtleBot2 的線速度為0.2 m/s，角速度為30（°）/s。構(gòu)建環(huán)境地圖的傳感器是RPLIDAR A1 激光雷達(dá)。實(shí)驗(yàn)場(chǎng)地選在實(shí)驗(yàn)樓樓梯口處，場(chǎng)地尺寸為6 m×5.5 m，用Rplidar A1 構(gòu)建樓道2D 地圖。改進(jìn)的蟻群算法尋路結(jié)果和原始的蟻群算法尋路結(jié)果如圖8 和圖9 所示，選用的柵格尺寸為0.3 m×0.3 m。圖8 中的黑色區(qū)域表示障礙物區(qū)域，粉紫色為可行區(qū)域，青藍(lán)色為膨脹區(qū)域。機(jī)器人的起點(diǎn)和終點(diǎn)都相同，從圖8 和圖9 中可以看出，改進(jìn)的蟻群算法路徑更平滑，距離障礙物邊界更遠(yuǎn)，減少發(fā)生碰撞的風(fēng)險(xiǎn)。為了更方便地比較改進(jìn)蟻群算法的性能，本文將兩種算法的尋路時(shí)間和路徑長(zhǎng)度進(jìn)行對(duì)比，對(duì)比結(jié)果如表2 所示。

表2 兩種算法尋路時(shí)間和路徑長(zhǎng)度的對(duì)比

從圖8和圖9可以看出，改進(jìn)的蟻群算法可以用于機(jī)器人的路徑規(guī)劃，且相比傳統(tǒng)的蟻群算法，改進(jìn)的蟻群算法搜尋的路徑更平滑，距離障礙物邊界更遠(yuǎn)。從表2 可以看出，改進(jìn)的蟻群算法在運(yùn)行時(shí)間和路徑長(zhǎng)度上都優(yōu)于原始的蟻群算法，在路徑長(zhǎng)度上縮短了4.27%，在運(yùn)行時(shí)間上減少了4.53%。因此，本文認(rèn)為改進(jìn)的蟻群算法能用于機(jī)器人的路徑規(guī)劃，且比原始的蟻群算法更優(yōu)。

圖8 改進(jìn)的蟻群算法尋路結(jié)果圖

圖9 原始的蟻群算法尋路結(jié)果圖

4 結(jié)語(yǔ)

針對(duì)蟻群算法中存在搜索時(shí)間長(zhǎng)、收斂速度慢和容易陷入局部最優(yōu)解等問(wèn)題，本文提出一種改進(jìn)的蟻群算法。第一個(gè)改進(jìn)的部分是引入方向性信息素，該信息素可以減少蟻群算法前期的盲目搜索，降低蟻群算法的搜索時(shí)間，避免蟻群算法陷入局部最優(yōu)解。第二個(gè)部分是提出針對(duì)方向性信息素的蒸發(fā)函數(shù)，使改進(jìn)的蟻群算法減少前期方向性信息素的蒸發(fā)，加快可行路徑的搜索；而后期能加快方向性信息素的蒸發(fā)，使改進(jìn)的蟻群算法更快收斂，避免方向性信息素對(duì)新增信息素的影響。仿真結(jié)果和機(jī)器人實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法在路徑長(zhǎng)度、迭代次數(shù)和搜索時(shí)間上相比蟻群算法和文獻(xiàn)[10]的算法有明顯的提升。后續(xù)工作是將改進(jìn)的蟻群算法和局部規(guī)劃算法結(jié)合起來(lái)，使機(jī)器人能適應(yīng)動(dòng)態(tài)的實(shí)驗(yàn)環(huán)境。