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

于紅斌，張志軍，蘇 沛

（1．河南師范大學計算機與信息工程學院，新鄉(xiāng)453007；2．河南省高校“計算智能與數(shù)據(jù)挖掘”工程技術(shù)研究中心，新鄉(xiāng)453007）

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

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

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

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

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

1 引 言

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

2 相關(guān)概念

2．1 細菌趨化反應及運動機制

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

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

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

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

3 改進的蟻群算法

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

3．1 螞蟻遷移點選擇

將細菌植入螞蟻進行基因改良，則有：

此時，細菌g位于螞蟻a體內(nèi)，F(xiàn)′為螞蟻移動向量，由螞蟻群體的信息素分布和螞蟻自身的趨化策略共同決定。它與螞蟻當前運動方向的夾角θ計算如下：

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

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

3．2 叛逆螞蟻策略

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

4 路徑規(guī)劃應用

4．1 螞蟻機器人移動方向選取

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

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

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

（1）θτ的確定

因為螞蟻機器人轉(zhuǎn)向有8個，假設(shè)當前8個方向上的信息素含量為：

（2）θF的確定

若F為障礙物和目標共同決定的勢場：

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

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

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

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

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

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

5 仿真實驗

5．1 實驗參數(shù)設(shè)置

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

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

表1 障礙物信息

5．2 實驗對比

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

表2 方法對比

6 結(jié)束語

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

［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)境下的基于改進人工勢場的機器人運動規(guī)劃［J］．沈陽工業(yè)大學學報，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］ 張穎，吳成東，原寶龍．機器人路徑規(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］ 杜宗宗，劉國棟．基于遺傳模擬退火算法的移動機器人路徑規(guī)劃［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］ 朱大奇，顏明重．移動機器人路徑規(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］ 周雅蘭．細菌覓食優(yōu)化算法的研究與應用［J］．計算機工程與應用，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］ 李燕，牟伯中．細菌趨化性研究進展［J］．應用與環(huán)境生物學報，2006，12（1）：135－139．LI Yan，MU Bo－zhong．Progress chemotaxis of Bacteria［J］．ChineseJournalofApplied＆Environmental Biology，2006，12（1）：135－139．

［10］ 蒲興成，趙紅全，張毅．細菌趨化行為的移動機器人路徑規(guī)劃方法［J］．智能系統(tǒng)學報，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

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

于紅斌（1979－），女，碩士研究生，講師，主研方向：機器學習、智能算法。

2014－12－25