代婷婷

(昭通學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南 昭通 657000)

0 引 言

目前，機(jī)器人在眾多領(lǐng)域發(fā)揮著重要的作用，人們可通過編程設(shè)計(jì)讓機(jī)器人完成很多危險(xiǎn)復(fù)雜的工作.關(guān)于機(jī)器人路徑規(guī)劃問題，科研人員提出了很多解決方案，例如，遺傳算法、粒子群算法、人工勢(shì)場(chǎng)法、蟻群算法等[1-4].雖然相關(guān)的智能算法比較多，但仍存在一些不足[5].其中，蟻群算法雖然在理論上能夠找到最優(yōu)解，在機(jī)器人路徑規(guī)劃方面的性能不錯(cuò)，但其仍存在如何快速有效地在全局范圍內(nèi)搜索出最優(yōu)解的問題，對(duì)此，學(xué)者們對(duì)蟻群算法進(jìn)行了各種改進(jìn).例如，Deng等[6]提出了動(dòng)態(tài)搜索誘導(dǎo)算子，通過閾值p的動(dòng)態(tài)變化極大地提高了算法解的質(zhì)量和收斂速度；Cai等[7]通過人工勢(shì)場(chǎng)法對(duì)蟻群算法信息素的揮發(fā)系數(shù)進(jìn)行改進(jìn)，提高了算法的最優(yōu)解質(zhì)量；趙靜等[8]對(duì)蟻群算法的啟發(fā)函數(shù)表達(dá)式進(jìn)行了改進(jìn)，在啟發(fā)函數(shù)中加入了下一節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的歐氏距離，使得當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的聯(lián)系更加緊密，從而提高了算法的求解效率；顧軍華等[9]對(duì)于蟻群算法的信息素濃度更新提出了新的方案，從相反的方向?qū)γ看蔚械淖顑?yōu)最差路徑上的信息素釋放量進(jìn)行干擾，避免了收斂過快而導(dǎo)致局部最優(yōu)解的出現(xiàn).在此基礎(chǔ)上，本研究將文獻(xiàn)[8]與文獻(xiàn)[9]中相關(guān)的改進(jìn)蟻群算法巧妙地融合而得出一種新的改進(jìn)蟻群算法，并將其用于解決機(jī)器人路徑規(guī)劃問題，取得了較好的效果.

1 路徑規(guī)劃問題的環(huán)境建模方法

針對(duì)機(jī)器人的路徑規(guī)劃問題，通常需要對(duì)機(jī)器人所處的環(huán)境進(jìn)行模擬建模.對(duì)此，本研究選擇最常用的柵格法進(jìn)行環(huán)境建模，此方法具有建立、表示與保存簡(jiǎn)單等優(yōu)點(diǎn).其思路是：將機(jī)器人所處的模擬環(huán)境分割成大小相同的一些正方形柵格，一個(gè)柵格表示一個(gè)單位，而每個(gè)柵格邊長是環(huán)境最小行走單元，柵格內(nèi)的情況可以忽略不計(jì).具體步驟包括：首先，規(guī)定使用中心點(diǎn)來表示機(jī)器人的柵格坐標(biāo)，并對(duì)柵格進(jìn)行標(biāo)記和編號(hào)，其可采用坐標(biāo)法和序號(hào)法;其次，按照柵格所具有的屬性，使用2種顏色將安全區(qū)域和障礙區(qū)域區(qū)別開，即機(jī)器人曾經(jīng)走過的柵格劃掉，其他安全的區(qū)域可以任意行走.圖1為20×20柵格示例.

圖1 20×20柵格示例圖

2 基本蟻群算法

基本蟻群算法的思路是：在尋找食物的過程中，螞蟻會(huì)在自己走過的搜索路徑上釋放信息素，而信

息素會(huì)對(duì)其他螞蟻產(chǎn)生吸引作用.正是有這種相互作用的正反饋，使得螞蟻搜索到的最短路徑的概率和該路徑上的信息素濃度成正比.按照此機(jī)制，就可以達(dá)到尋找到最短路徑的目的.其具體的模型為：設(shè)i為外出覓食螞蟻的出發(fā)點(diǎn)，則其到達(dá)覓食終點(diǎn)j的隨機(jī)行進(jìn)概率可表為，

(1)

式(1)表明:螞蟻覓食過程中最容易被選到的那條路徑具有較高的信息素濃度且距離螞蟻較近；每一次每一只螞蟻經(jīng)過某一條路徑后都會(huì)馬上按照式(2)和式(3)更新該路徑上的信息素[10].

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

(2)

(3)

3 改進(jìn)蟻群算法與流程圖

3.1 改進(jìn)啟發(fā)函數(shù)

基于基本蟻群算法的原理分析以及結(jié)合相關(guān)的文獻(xiàn)，本研究認(rèn)為，不但節(jié)點(diǎn)之間的概率轉(zhuǎn)移能影響最短路徑的計(jì)算結(jié)果，而且行走路徑上的信息素濃度的更新對(duì)最短路徑的影響也較為明顯.一般情況下，可使用相鄰節(jié)點(diǎn)i和j間的歐氏距離的倒數(shù)來表示轉(zhuǎn)移概率中的啟發(fā)函數(shù).但事實(shí)上，開始搜索的最初階段，由于螞蟻數(shù)量不多，釋放的信息素濃度較少使得更多螞蟻偏離正確尋找路徑的概率加大，從而形成局部最優(yōu)解或無效解.對(duì)此，文獻(xiàn)[8]在啟發(fā)函數(shù)中引入了下一節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的歐氏距離，從而加強(qiáng)了當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的聯(lián)系，其數(shù)學(xué)表達(dá)式為，

(4)

式中，dij表示當(dāng)前節(jié)點(diǎn)i與下一個(gè)可行節(jié)點(diǎn)j之間的歐氏距離，djE是下一可行節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)E的歐氏距離.

式(4)表明，由于加強(qiáng)了搜索路徑的方向性，相應(yīng)的運(yùn)算時(shí)間可大為縮短，提高了算法的計(jì)算效率.

3.2 更新信息素濃度

研究表明，蟻群算法的效率受信息素濃度更新的影響極大[10].影響信息素濃度更新的主要因素包括：第一，行走路徑的長度與信息素濃度的更新關(guān)系非常地密切，為了防止其積累過多而使算法過早局部收斂，信息素濃度進(jìn)行更新是必不可少的；第二，由于大自然的固有特性，螞蟻行走路徑上的信息素濃度會(huì)隨著時(shí)間的推移而揮發(fā)掉一部分，即濃度會(huì)不斷降低；第三，經(jīng)過行走路徑的所有螞蟻都會(huì)釋放信息素，即最短路徑上的螞蟻?zhàn)疃?，信息素濃度也最?qiáng)；最后，要在全部路徑中凸顯出最優(yōu)路徑[11].對(duì)此，文獻(xiàn)[9]的主要做法是沿相反的方向?qū)Ξ?dāng)次迭代的最優(yōu)和最差路徑上的信息素進(jìn)行改變，即最優(yōu)的加強(qiáng)，最差的減弱，并將其按照式(5)的方式更新，防止算法收斂過快而陷入局部最優(yōu)，

(5)

3.3 改進(jìn)蟻群算法與計(jì)算流程

本研究根據(jù)以上2種文獻(xiàn)相關(guān)算法改進(jìn)的優(yōu)點(diǎn)，將文獻(xiàn)[8]中的啟發(fā)函數(shù)改進(jìn)和文獻(xiàn)[9]中的信息素濃度更新的方案融合起來構(gòu)成一種新的改進(jìn)蟻群算法，即對(duì)啟發(fā)函數(shù)進(jìn)行改變，把與最終節(jié)點(diǎn)的距離加入其中，同時(shí)，增加或減少在信息素更新時(shí)找到的最優(yōu)和最差解的信息素濃度，從而提高算法的性能.本研究的改進(jìn)蟻群算法的具體計(jì)算流程如圖2所示.

圖2 改進(jìn)蟻群算法的計(jì)算流程示意圖

4 實(shí)證分析

為了驗(yàn)證本改進(jìn)蟻群算法的實(shí)際效果，本研究選用MATLAB分析軟件進(jìn)行仿真實(shí)驗(yàn)，具體做法是分別使用基本的蟻群算法和本改進(jìn)蟻群算法來進(jìn)行測(cè)試.其步驟是，將機(jī)器人處于圖1所示中的柵格障礙環(huán)境中，讓機(jī)器人在該環(huán)境中尋找無碰撞的最短路徑.在實(shí)驗(yàn)的過程中，設(shè)定找到一條從起點(diǎn)到終點(diǎn)的沒有碰撞的最短路徑是機(jī)器人工作的目的，從而比較使用2種算法使機(jī)器人在這個(gè)尋找最短路徑的過程中找到最優(yōu)路徑用時(shí)最短的方法.

在測(cè)試中，對(duì)本改進(jìn)蟻群算法在實(shí)驗(yàn)中的參數(shù)做表1所示的具體設(shè)置.

表1 實(shí)驗(yàn)過程中改進(jìn)蟻群算法的參數(shù)設(shè)置

通過MATLAB分析軟件的仿真試驗(yàn)，2種算法的測(cè)試結(jié)果如圖3、圖4所示.

圖3 20×20柵格最優(yōu)路徑

圖4 20×20柵格環(huán)境下基本蟻群算法與改進(jìn)蟻群算法的收斂曲線

由圖3可知，基本蟻群算法和本改進(jìn)蟻群算法都尋找到了長度為29.21的最優(yōu)路徑，即2種算法找到的最優(yōu)路徑相同.盡管2種算法得到的最優(yōu)路徑是一樣的，但從圖4可以看出，這2種算法所使用的時(shí)間是完全不同的，基本蟻群算法找到最優(yōu)路徑需要18次迭代，而本改進(jìn)的蟻群算法僅迭代到第3次的時(shí)候就已經(jīng)找到了最優(yōu)路徑.此也表明，本研究的改進(jìn)蟻群算法收斂速度很快，其搜索效率與基本蟻群算法相比有較大提升，可以在極短時(shí)間內(nèi)搜索到最優(yōu)解.

為了進(jìn)一步顯示本改進(jìn)蟻群算法的特點(diǎn)，本研究將其與文獻(xiàn)[8]和文獻(xiàn)[9]所提算法的性能進(jìn)行了對(duì)比，結(jié)果如圖5所示.

圖5 20×20柵格環(huán)境下3種算法的收斂曲線

由圖5可知，由于同時(shí)對(duì)啟發(fā)函數(shù)和信息素濃度的更新方式進(jìn)行了改進(jìn)，使得本研究所提算法具有明顯的優(yōu)勢(shì).與其他2種算法相比，本算法在搜索初期所走的路線更短.文獻(xiàn)[8]算法在迭代第12次時(shí)，得到的路徑長度為29.21，但收斂速度較慢.雖然文獻(xiàn)[9]算法在迭代第8次時(shí)就得到長度為30.36的最優(yōu)路徑，擁有較快的收斂速，但得到的卻是局部最優(yōu)解.本算法在迭代第3次時(shí)就獲得了長度為29.21的最短路徑，明顯地在大幅度提升收斂速度的同時(shí)獲得了最短路徑.

為更直觀地展現(xiàn)本文算法與其他2種算法的對(duì)比優(yōu)勢(shì)，在表2中列出了上述3種算法運(yùn)行10次的仿真結(jié)果.

表2 20×20柵格環(huán)境下3種算法仿真結(jié)果對(duì)比

根據(jù)表2的仿真結(jié)果對(duì)比可知:從搜索路徑的長度上看，本文算法在迭代次數(shù)內(nèi)僅有一次陷入了局部最優(yōu)，其余幾次均能快速地找到全局最優(yōu)解，且在距離啟發(fā)函數(shù)和自適應(yīng)揮發(fā)因子的共同作用下?lián)碛袠O強(qiáng)的逃離局部最優(yōu)解的能力;文獻(xiàn)[8]算法有數(shù)次找到了最優(yōu)解，但還是有幾次未能很好地實(shí)現(xiàn)尋優(yōu);文獻(xiàn)[9]算法出現(xiàn)了幾次搜尋路徑較長，其尋優(yōu)能力弱于上述2種算法.在迭代次數(shù)上，本文算法與文獻(xiàn)[9]算法次數(shù)相差不大，與文獻(xiàn)[8]算法相比大幅降低.在運(yùn)算時(shí)間上，本文算法稍優(yōu)于文獻(xiàn)[9]算法，但均優(yōu)于傳統(tǒng)算法.據(jù)此可知，本文的相關(guān)改進(jìn)使蟻群算法的缺點(diǎn)得到了較大改善，避免了算法易陷入局部最優(yōu)的難題,同時(shí)收斂速度提升明顯.

5 結(jié) 語

針對(duì)機(jī)器人路徑規(guī)劃問題，本研究根據(jù)文獻(xiàn)[8]和文獻(xiàn)[9]中的相關(guān)算法，提出了一種新的改進(jìn)蟻群算法，具體改進(jìn)體現(xiàn)為：第一，對(duì)啟發(fā)函數(shù)中的2段距離之和做了平方處理，加強(qiáng)了搜索的方向性，使得搜索時(shí)間有所減少；第二，對(duì)信息素濃度的更新方式做了改變，避免了出現(xiàn)局部最優(yōu)的情況.利用MATLAB分析軟件對(duì)相關(guān)算法進(jìn)行了仿真測(cè)試，結(jié)果表明：本改進(jìn)蟻群算法與基本蟻群算法相比，雖然在相同的柵格環(huán)境中尋找的最優(yōu)路徑完全相同，但所需要的迭代次數(shù)較少；與文獻(xiàn)[8]與文獻(xiàn)[9]的2種算法相比，在尋找最優(yōu)解和收斂速度方面都有比較明顯的提升.