于紅斌，張志軍，蘇 沛

（1．河南師范大學(xué)計算機(jī)與信息工程學(xué)院，新鄉(xiāng)453007；2．河南省高?！坝嬎阒悄芘c數(shù)據(jù)挖掘”工程技術(shù)研究中心，新鄉(xiāng)453007）

基于趨化行為的改進(jìn)蟻群算法及路徑規(guī)劃應(yīng)用*

于紅斌1，2，張志軍1，蘇 沛1

（1．河南師范大學(xué)計算機(jī)與信息工程學(xué)院，新鄉(xiāng)453007；2．河南省高?！坝嬎阒悄芘c數(shù)據(jù)挖掘”工程技術(shù)研究中心，新鄉(xiāng)453007）

針對蟻群算法個體的薄弱性，提出了一種基于細(xì)菌趨化的集成算法。算法中螞蟻個體借助細(xì)菌的趨向性不僅彌補(bǔ)了自身覓食的盲目性，也使螞蟻個體具備了障礙檢測預(yù)警能力，從而提高了整個蟻群的路徑規(guī)劃效率。另外，通過設(shè)置叛逆螞蟻，保障了蟻群路徑選擇的多樣性，提高了路徑規(guī)劃效果。實(shí)驗(yàn)表明，算法能在多障礙物環(huán)境下有效地解決機(jī)器人路徑規(guī)劃問題。

趨化行為；蟻群算法；路徑規(guī)劃；多障礙物，障礙檢測；叛逆螞蟻

1 引 言

路徑規(guī)劃不僅是移動機(jī)器人研究領(lǐng)域的熱點(diǎn)問題，也是基本問題。在特定環(huán)境下，依據(jù)指定準(zhǔn)則為移動機(jī)器人找到一條安全有效的路徑是解決該問題的關(guān)鍵。近年來，相關(guān)學(xué)者為此進(jìn)行了大量研究［1－8］，其中仿生智能算法由于處理復(fù)雜環(huán)境信息的優(yōu)越性而受到了極大關(guān)注。針對螞蟻算法的特點(diǎn)，提出一種改進(jìn)的蟻群算法，借鑒細(xì)菌在覓食過程中的趨化行為［10］改進(jìn)螞蟻的遷移概率函數(shù)，使其具有自適應(yīng)能力，提高螞蟻群體路徑規(guī)劃的效率；引入叛逆螞蟻策略，增加蟻群路徑選擇多樣性，避免局部最優(yōu)路徑，提高路徑規(guī)劃的效果。

2 相關(guān)概念

2．1 細(xì)菌趨化反應(yīng)及運(yùn)動機(jī)制

動力細(xì)菌會本能的對化學(xué)物質(zhì)的刺激表現(xiàn)出趨向性［2］。在無化學(xué)刺激物或正反刺激物濃度相當(dāng)?shù)臈l件下，細(xì)菌會先直線游動一段距離，然后翻滾一次改變運(yùn)動方向，即以游動、翻滾交替變換的方式體現(xiàn)出其對運(yùn)動方向的隨機(jī)選擇性。而在化學(xué)吸引劑作用下，細(xì)菌不再出現(xiàn)翻滾行為，而是直線游動到高濃度吸引劑的方向，表現(xiàn)出其正趨化性；遇到驅(qū)斥劑時，細(xì)菌立即產(chǎn)生翻滾運(yùn)動并沿其濃度梯度遞減方向游動以避開刺激源，表現(xiàn)負(fù)趨化性［9］。細(xì)菌這種趨利避害的行為與蟻群覓食活動不謀而合，因此可以利用細(xì)菌的這一特點(diǎn)對蟻群僅憑信息素遷移的單一機(jī)制進(jìn)行優(yōu)化，以提高蟻群向目標(biāo)逼近的速度，從而保證算法的收斂性。

其中，F(xiàn)由細(xì)菌g所處環(huán)境中的化學(xué)物質(zhì)決定。

2．2 蟻群信息素優(yōu)化函數(shù)

蟻群算法中，若t時刻螞蟻a位于地圖坐標(biāo)點(diǎn)P（x，y），其信息素由決定，則信息素的更新多數(shù)依據(jù)當(dāng)前迭代中的最優(yōu)路徑，即：

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

改進(jìn)的蟻群算法借鑒細(xì)菌的趨化能力，在保證群體特征前提下，追加螞蟻個體的判斷能力，使得信息素更新更為合理。

3．1 螞蟻遷移點(diǎn)選擇

將細(xì)菌植入螞蟻進(jìn)行基因改良，則有：

此時，細(xì)菌g位于螞蟻a體內(nèi)，F(xiàn)′為螞蟻移動向量，由螞蟻群體的信息素分布和螞蟻?zhàn)陨淼内吇呗怨餐瑳Q定。它與螞蟻當(dāng)前運(yùn)動方向的夾角θ計算如下：

α、β分別表示群體和個體的控制權(quán)重。θτ為由信息素決定的螞蟻移動轉(zhuǎn)向角度。θF由障礙物和目標(biāo)共同構(gòu)成，對隨機(jī)移動概率函數(shù)修正。

當(dāng)蟻群中所有螞蟻到達(dá)目標(biāo)點(diǎn)后，選擇當(dāng)前最優(yōu)路徑，按式（2）更新信息素。這種改進(jìn)不僅體現(xiàn)了螞蟻群體特性，同時增強(qiáng)了螞蟻個體障礙檢測預(yù)警機(jī)制，保證了蟻群路徑規(guī)劃的實(shí)現(xiàn)。

3．2 叛逆螞蟻策略

在信息素的引導(dǎo)下，螞蟻移動的隨機(jī)性被限制，路徑節(jié)點(diǎn)的選擇將更加單一，這種正反饋機(jī)制導(dǎo)致大量螞蟻集中到某條特定路徑上。然而該路徑不一定是最優(yōu)路徑，從而使算法陷入局部最優(yōu)。為了防止這種誤導(dǎo)，引入叛逆螞蟻。算法迭代過程中，根據(jù)蟻群規(guī)模設(shè)定某些螞蟻為叛逆螞蟻，當(dāng)該螞蟻發(fā)現(xiàn)某點(diǎn)某個方向上信息素特別集中時，拋棄該點(diǎn)，隨即選擇其他方向點(diǎn)移動。叛逆螞蟻保證了路徑的多樣性，避免了局部最優(yōu)路徑，實(shí)現(xiàn)了算法收斂。

4 路徑規(guī)劃應(yīng)用

4．1 螞蟻機(jī)器人移動方向選取

變異螞蟻在極小范圍內(nèi)可以感知周圍環(huán)境，其轉(zhuǎn)向具有隨機(jī)性。而機(jī)器人可以通過自身高效傳感器來感知并評價所處環(huán)境，其轉(zhuǎn)向更有方向性，因此轉(zhuǎn)向可以機(jī)器人為中心劃分。假設(shè)機(jī)器人每次轉(zhuǎn)角為π／4的倍數(shù)，逆時針為正方向，則轉(zhuǎn)向示意圖如圖1所示。

圖1 轉(zhuǎn)向示意圖

其中，θ表示螞蟻機(jī)器人的轉(zhuǎn)向角度，其值由式（4）確定。

（1）θτ的確定

因?yàn)槲浵仚C(jī)器人轉(zhuǎn)向有8個，假設(shè)當(dāng)前8個方向上的信息素含量為：

（2）θF的確定

若F為障礙物和目標(biāo)共同決定的勢場：

（6）式中：ω1、ω2表示螞蟻機(jī)器人趨向目標(biāo)和避障的權(quán)重。生物實(shí)驗(yàn)證實(shí)螞蟻危險信號的感知能力很強(qiáng)，路徑選擇的安全性尤為重要，所以ω2會比ω1大很多。θg、θ0i為螞蟻當(dāng)前位置與目標(biāo)點(diǎn)或障礙物點(diǎn)的夾角，（xg，yg）為目標(biāo)點(diǎn)的坐標(biāo)，（x0i，y0i）為第i個障礙物的中心點(diǎn)坐標(biāo)，F(xiàn)g為目標(biāo)點(diǎn)對螞蟻機(jī)器人的吸引力，保障了螞蟻機(jī)器人的趨向性運(yùn)動，F(xiàn)0為所有障礙物對螞蟻機(jī)器人的排斥力之和，體現(xiàn)螞蟻路徑選擇的安全性。δi為第i個障礙物的作用半徑。則F與當(dāng)前螞蟻機(jī)器人的運(yùn)動方向夾角即為θF。

4．2 路徑規(guī)劃實(shí)現(xiàn)步驟

（1）初始化。布置地圖。設(shè)定路徑的起點(diǎn)（xs，ys）和目標(biāo)點(diǎn)（x0，y0），設(shè)置每一個障礙物的中心點(diǎn)（x0i，y0i）和作用半徑δ。假定機(jī)器人的步長stepsize＝1，則障礙物作用半徑可以被簡化為機(jī)器人步長的整數(shù)倍。同時設(shè)定α、β、ω1、ω2的值。

（2）根據(jù)地圖規(guī)模，確定螞蟻種群規(guī)模m。初始時所有螞蟻都位于起點(diǎn)，此時沒有群體信息，各方向攜帶信息素均為初始值Q，于是在隨機(jī)選擇某一移動方向后，根據(jù)螞蟻機(jī)器人的趨化能力對方向進(jìn)行調(diào)整。當(dāng)所有螞蟻都到達(dá)目標(biāo)點(diǎn)后，計算每只螞蟻的路徑長度，根據(jù)式（2）修改相應(yīng)節(jié)點(diǎn)的信息素。

（3）將所有螞蟻重新置于起始點(diǎn)，由式（4）決定下一次的移動方向，（5）式?jīng)Q定螞蟻機(jī)器人的移動位置。另外，為保證路徑的多樣性，避免由于信息素過度集中而導(dǎo)致的算法不收斂，將種群m／5的螞蟻設(shè)定為叛逆螞蟻，這些螞蟻機(jī)器人在選擇下一移動方向時，（4）式中θτ將在去除S最大值的基礎(chǔ)上計算。當(dāng)所有螞蟻都到達(dá)目標(biāo)點(diǎn)后，計算每只螞蟻的路徑長度，根據(jù)最短路徑按式（2）修改相應(yīng)節(jié)點(diǎn)的信息素。若設(shè)定迭代沒有完成，則重復(fù)本步驟。否則轉(zhuǎn)（4）。

（4）算法結(jié)束后，計算當(dāng)前最短路徑，該路徑即為最優(yōu)路徑。

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

5．1 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)用Matlab編程，地圖規(guī)模為100*100，螞蟻機(jī)器人起點(diǎn)位于坐標(biāo)（0，0），終點(diǎn)定為（100，100），初始障礙物如表1所示。設(shè)定α＝0．7、β＝0．3，以保證蟻群的群體優(yōu)勢，同時體現(xiàn)螞蟻個體的趨化能力。為了保證路徑的安全性，給定ω1＝0．2，ω2＝0．8，使得機(jī)器人避障能力高于對目標(biāo)的趨向能力。螞蟻種群規(guī)模m＝10，信息素初始值Q＝1，信息素消逝率初值ρ＝0．3，其值隨著迭代次數(shù)遞增，算法結(jié)束時由于每次實(shí)驗(yàn)迭代次數(shù)的不同略有差異，其平均值為0．6。10次實(shí)驗(yàn)中最優(yōu)路徑長度為151．04cm，圖2為實(shí)驗(yàn)結(jié)果。

圖2 路徑規(guī)劃結(jié)果

表1 障礙物信息

5．2 實(shí)驗(yàn)對比

根據(jù)文獻(xiàn)［10］提供的數(shù)據(jù)，與其中各種算法在同樣實(shí)驗(yàn)環(huán)境下進(jìn)行對比實(shí)驗(yàn)，如表2所示。從表中可以看出，改進(jìn)算法路徑雖然不是最短的，但相對比較合理安全，因此算法還是可以信賴的。

表2 方法對比

6 結(jié)束語

針對蟻群算法特點(diǎn)，將細(xì)菌的趨化能力引入到螞蟻個體中，彌補(bǔ)了以往螞蟻算法只考慮群體特性的不足，不僅避免了螞蟻個體覓食過程中的隨機(jī)性，使得單個螞蟻覓食和避障的能力極大改善，同時也為其他螞蟻提前躲避障礙物給出了指示，使得螞蟻個體具備了障礙檢測預(yù)警能力，從而提高了整個蟻群的路徑規(guī)劃效率。而叛逆螞蟻的加入，保障了蟻群路徑選擇的多樣性，提高了路徑規(guī)劃效果。實(shí)驗(yàn)表明，在多障礙物環(huán)境中，該算法能有效地規(guī)劃出合理路徑。今后，在算法中參數(shù)的選擇上應(yīng)進(jìn)行重點(diǎn)研究分析，避免經(jīng)驗(yàn)選擇的隨機(jī)性。

［1］ Ramekin H E，Smith R L．Simulated Annealing for ConstrainedGlobalOptimization［J］．JofGlobal Optimization，1994，5（2）：101－124．

［2］ Chen L N，Aihara K，Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos［J］．Neural Networks，1995，8（6）：915－930．

［3］ 覃柯，孫茂相，孫昌志．動態(tài)環(huán)境下的基于改進(jìn)人工勢場的機(jī)器人運(yùn)動規(guī)劃［J］．沈陽工業(yè)大學(xué)學(xué)報，2003（5）：568－570．QIN Ke，SUN Mao－xiang，SUN Chang－zhi．Motion robot planning in dynamic environment based on improved artificial potential field method［J］．Journal of Shenyang University of Technology，2003（5）：568－570．

［4］ J Tu，S Yang．Genetic Algorithm Based Path Planning for a Mobile Robot［C］．／／Taiwan：Proceeding of IEEE Intelligent Conference on Robotics and Automation，2003：L1221－1226．

［5］ 張穎，吳成東，原寶龍．機(jī)器人路徑規(guī)劃方法綜述［J］．控制工程，2003（5）：152－155．ZHANG Ying，WU Cheng－dong，YUAN Bao－long．Progress on Path Planning Research for Robot［J］．Control Engineering of China，2003（5）：152－155．

［6］ 杜宗宗，劉國棟．基于遺傳模擬退火算法的移動機(jī)器人路徑規(guī)劃［J］．計算機(jī)仿真，2009，26（2）：118－121．DU Zong－zong，LIU Guo－dong．Path planning of Mobile Robot Based on Genetically Simulated Annealing Algorithm［J］．Computer Simulation，2009，26（2）：118－121．

［7］ 朱大奇，顏明重．移動機(jī)器人路徑規(guī)劃技術(shù)綜述［J］．控制與決策，2010，25（7）：961－967．ZHU Da－qi，YAN Ming－zhong．Survey on technology of mobile robot path planning［J］．Control and Decision，2010，25（7）：961－967．

［8］ 周雅蘭．細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用［J］．計算機(jī)工程與應(yīng)用，2010，46（20）：16－21．ZHOU Ya－lan．Research and application on bacteria foraging optimization algorithm［J］．Computer Engineering and Applications，2010，46（20）：16－21．

［9］ 李燕，牟伯中．細(xì)菌趨化性研究進(jìn)展［J］．應(yīng)用與環(huán)境生物學(xué)報，2006，12（1）：135－139．LI Yan，MU Bo－zhong．Progress chemotaxis of Bacteria［J］．ChineseJournalofApplied＆Environmental Biology，2006，12（1）：135－139．

［10］ 蒲興成，趙紅全，張毅．細(xì)菌趨化行為的移動機(jī)器人路徑規(guī)劃方法［J］．智能系統(tǒng)學(xué)報，2014，9（1）：1－7．PU Xingcheng，ZHAO Hongquan，ZHANG Yi．Mobile robot path planning research based on bacterial chemotaxis［J］．CAAI Transactions on Intelligent Systems，2014，9（1）：1－7．

An Improved Ant Colony Algorithm Based on Chemotaxis and Applications in Path Planning

Yu Hongbin1，2，Zhang Zhijun1，Su Pei1
（1．College of Computer and Information Engineering，Henan Normal University，Xinxiang 453007，China；2．Engineering Technology Research Center for Computing Intelligence＆Data Mining，Henan Province，Xinxiang 453007，China）

In order to solve the individual weakness of ant colony algorithm，an integrated algorithm is proposed based on bacterial chemotaxis．This improvement，combining tendency of bacteria，not only makes up the blindness for foraging itself，also makes the ant individuals possess the ability of obstacle detection warning，so as to improve the efficiency of path planning of the whole ant colony．In addition，by setting the rebellious ants，the diversity of the ant colony routing is guaranteed and the effect of the path planning is improved．The experimental results show that the algorithm can effectively solve the problem of robot path planning in many obstacles environment．

Chemotactic behavior；Ant colony algorithm；Path planning；Many obstacles；Obstacle detection；Rebellious ants

10．3969／j．issn．1002－2279．2015．04．012

TP18

A

1002－2279（2015）04－0045－04

河南省教育廳科學(xué)技術(shù)重點(diǎn)研究項(xiàng)目（14A520005）；河南師范大學(xué)青年科學(xué)基金資助項(xiàng)目（2013QK19）

于紅斌（1979－），女，碩士研究生，講師，主研方向：機(jī)器學(xué)習(xí)、智能算法。

2014－12－25