改進(jìn)蟻群算法在機(jī)器人中的應(yīng)用概述

廖 錚，楊奇燊，林生杰，鄭曉云，王治坤

（北京理工大學(xué)珠海學(xué)院，廣東 珠海519000）

蟻群算法是一種元啟發(fā)式的智能搜索算法，與另外的一些模擬式的進(jìn)化型算法一樣，具有智能的特性。蟻群算法自被意大利學(xué)者DORⅠGO[1]于1996年提出，引起了許多研究者的關(guān)注。蟻群算法最初是被應(yīng)用于商旅行問(wèn)題，取得的效果尚好，但是因?yàn)槠渚哂幸资諗康娜秉c(diǎn)，仍需改進(jìn)。隨著蟻群算法的發(fā)展和改進(jìn)，因蟻群算法具有易與其他優(yōu)化算法結(jié)合的優(yōu)點(diǎn)，蟻群算法逐漸被應(yīng)用于多個(gè)領(lǐng)域。本文首先從蟻群算法原理出發(fā)，再?gòu)南伻核惴ㄔ跈C(jī)器人中的應(yīng)用及其發(fā)展趨勢(shì)進(jìn)行描述。

1 原始蟻群算法的基本原理

算法最初期的應(yīng)用在TSP類型的問(wèn)題時(shí)，主要由初始、信息素更新2部分組成。以簡(jiǎn)單的兩點(diǎn)間的距離問(wèn)題為例，分別取A、B兩點(diǎn)。蟻群路徑圖如圖1所示。

圖1 蟻群路徑圖

第一步，在初始時(shí)，從A點(diǎn)到B點(diǎn)的3條路徑上并沒(méi)有任何信息素物質(zhì)影響螞蟻的路徑方向，所以初始時(shí)螞蟻路過(guò)3條路徑的概率是相同的，3條路徑路過(guò)的螞蟻初始時(shí)是一樣的。第二步，螞蟻在不斷經(jīng)過(guò)3條道路的過(guò)程中，會(huì)散發(fā)出一種能夠吸引其他螞蟻的物質(zhì)——信息素，可以吸引其他螞蟻過(guò)來(lái)，不斷集中走這一條路。第三步，在初始時(shí)，假設(shè)螞蟻每分鐘經(jīng)過(guò)的路程相同。由于2是3條道路上路程最短的，則在相同的時(shí)間內(nèi)，螞蟻路過(guò)2路上的數(shù)量是最多的，并且因?yàn)閿?shù)量最多，所以可以散發(fā)更多的信息素，可以吸引更多的螞蟻?zhàn)?路上，因此，2路上的信息素變得越來(lái)越濃密。第四步，經(jīng)過(guò)一段時(shí)間的循環(huán)，螞蟻在選擇1、2、3路上的時(shí)候會(huì)更多地選擇第2路，因?yàn)?路上的信息素含量遠(yuǎn)大于1、3路的信息素含量，所以推斷出：經(jīng)過(guò)時(shí)間的推移，1、3路上基本沒(méi)有螞蟻經(jīng)過(guò)，2路上的螞蟻是最多的。

基本的蟻群算法原理核心由下列3條公式組成[2]：

經(jīng)典的蟻群規(guī)劃模型有3種經(jīng)典模型，王穎等[3]詳細(xì)說(shuō)明了蟻群算法的3種模型，3種模型分別為cycle system、quantity system、dentisy system。以下是3種模型：

對(duì)上述3種經(jīng)典模型進(jìn)行了仿真實(shí)驗(yàn)，可得在求解商旅行的問(wèn)題中，ant cycle system性能是最佳的。

2 蟻群算法的改進(jìn)與發(fā)展

蟻群算法到現(xiàn)階段位置有2個(gè)比較需要改進(jìn)的缺點(diǎn)，分別為算法的收斂度太短和局部空間尋優(yōu)快。針對(duì)這2個(gè)缺陷，大部分學(xué)者利用蟻群算法的信息素傳播原理，對(duì)信息素規(guī)則進(jìn)行修改。因?yàn)樾畔⑺氐恼{(diào)整策略對(duì)算法的收斂性和求解效率具有很大影響的。

有很多國(guó)內(nèi)外的學(xué)者利用多種方式對(duì)信息素的傳播和揮發(fā)進(jìn)行修正。如柳長(zhǎng)安等[4]利用柵格法并對(duì)柵格進(jìn)行編號(hào)，再通過(guò)引入自適應(yīng)的函數(shù)對(duì)信息素的含量進(jìn)行修正，最后再通過(guò)研究狼群分配原則再次對(duì)信息素進(jìn)行修正。在螞蟻的前進(jìn)路上，把路上螞蟻留下的信息含量較低的路線去掉，使得螞蟻在每次迭代中都能找到最多信息素含量的路線，得到最優(yōu)解。針對(duì)正反饋過(guò)程易陷入局部最優(yōu)解的情況，對(duì)蟻群算法進(jìn)行改進(jìn)，覃剛力等[5]提出針對(duì)信息素矩陣在每一次蟻群迭代中的改變，提出了一種動(dòng)態(tài)自適應(yīng)調(diào)整信息素的方法改進(jìn)蟻群算法求解商旅行問(wèn)題，通過(guò)信息素矩陣的改變，達(dá)到對(duì)蟻群算法的監(jiān)控，實(shí)時(shí)判斷算法的搜索狀態(tài)，采用強(qiáng)制機(jī)制，減小必要的信息素，達(dá)到更好的效果。針對(duì)螞蟻的易出現(xiàn)停滯現(xiàn)象，鄭松等[6]提出了一種針對(duì)全局動(dòng)態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法，能夠有效抑制蟻群算法的停滯現(xiàn)象，更容易得到局部最優(yōu)解。

3 蟻群算法在機(jī)器人上的應(yīng)用

因?yàn)橄伻旱臄?shù)量龐大、基數(shù)足的特點(diǎn)，可以通過(guò)傳播信息素的方法來(lái)改變蟻群的路徑規(guī)劃趨勢(shì)和移動(dòng)方向的規(guī)劃。國(guó)內(nèi)外許多學(xué)者對(duì)此進(jìn)行進(jìn)一步的改進(jìn)和運(yùn)用。

3.1 蟻群算法在TSP問(wèn)題上的應(yīng)用

因?yàn)橄伻旱臄?shù)量龐大、基數(shù)足的特點(diǎn)，可以通過(guò)傳播信息素的方法來(lái)分配整個(gè)蟻群中的任務(wù)和對(duì)路線進(jìn)行規(guī)劃。蟻群在尋找食物的過(guò)程中，每只螞蟻都會(huì)在途徑的路上釋放一種具有信息的因子——信息素，每個(gè)螞蟻都能感知到這種物質(zhì)的存在，并根據(jù)信息濃度的強(qiáng)度指導(dǎo)自己的移動(dòng)方向。傳統(tǒng)的機(jī)器人路徑規(guī)劃一般是在自然環(huán)境中，機(jī)器人按照給定的參數(shù)指標(biāo)和一定的規(guī)則在給定的全局空間中不斷探索一條從開(kāi)始位置到目標(biāo)位置的無(wú)碰撞路徑。

近年來(lái)，國(guó)內(nèi)外的學(xué)者都對(duì)蟻群算法在路徑規(guī)劃問(wèn)題上的研究提出了不同的創(chuàng)新點(diǎn)。任紅格等[7]提出的采用修改的算法路徑搜索策略以及創(chuàng)新的啟發(fā)函數(shù)進(jìn)行規(guī)劃。結(jié)合信息素?fù)]發(fā)系數(shù)，解決了平時(shí)有時(shí)無(wú)法搜索到最優(yōu)路徑等問(wèn)題，提高了搜索算法的的效率，也得到了較為優(yōu)良的路徑規(guī)劃路線。劉輝等[8]基于改進(jìn)的蟻群算法對(duì)無(wú)人礦車路徑進(jìn)行規(guī)劃研究，將速度-坡度作為一個(gè)影響因子，結(jié)合蟻群算法的狀態(tài)轉(zhuǎn)移概率建立相關(guān)的影響公式。在實(shí)際的場(chǎng)景中，具體是在路徑較短的條件下選擇坡度較小的節(jié)點(diǎn)。將每代螞蟻中的優(yōu)良的螞蟻進(jìn)行局部路徑優(yōu)化，提高搜索路徑的能力。與傳統(tǒng)的蟻群算法進(jìn)行比較該種算法在實(shí)際的采礦類環(huán)境下，改進(jìn)過(guò)后的蟻群算法在采礦的情況下全局尋優(yōu)的能力更為良好，算法的實(shí)際收斂速度更快，實(shí)際用時(shí)較短。鄧向陽(yáng)等[9]在基本的蟻群算法基礎(chǔ)上提出先驗(yàn)優(yōu)勢(shì)方位角的概念，建立了主優(yōu)勢(shì)網(wǎng)格和次優(yōu)網(wǎng)格的模型，在全局的解空間中構(gòu)建了起始點(diǎn)與目標(biāo)點(diǎn)互換的交替雙向引導(dǎo)策略，應(yīng)用在具有復(fù)雜障礙物分布的大規(guī)模地圖，改變了傳統(tǒng)蟻群算法信息素結(jié)構(gòu)。由仿真實(shí)驗(yàn)可得出，該算法大大提升了構(gòu)建初始解及收斂的速度，針對(duì)于大規(guī)模場(chǎng)景下的路徑規(guī)劃，改良的蟻群算法在處理大規(guī)模的地圖環(huán)境中可以具有優(yōu)良的適應(yīng)性，求解的過(guò)程也得到了很大的提升，能夠很好地求解在復(fù)雜的路況下的復(fù)雜路障環(huán)境的問(wèn)題。李文振等[10]針對(duì)在蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中存在的一些穩(wěn)定性不足、收斂速度慢、易陷入局部最優(yōu)等問(wèn)題，優(yōu)化改進(jìn)了傳統(tǒng)的蟻群算法。主要是通過(guò)改進(jìn)轉(zhuǎn)移概率來(lái)改變轉(zhuǎn)移規(guī)則，讓螞蟻可以準(zhǔn)確預(yù)測(cè)搜索到下一個(gè)最佳柵格位置，同時(shí)采用了新的信息素更新規(guī)則可以加快收斂速度，擴(kuò)大搜索空間。仿真結(jié)果表明，該改進(jìn)算法在路徑搜索效率和收斂速度方面明顯優(yōu)于傳統(tǒng)蟻群算法。藍(lán)丹等[11]結(jié)合智能車輛的具體動(dòng)力學(xué)方程約束，對(duì)規(guī)劃路徑進(jìn)行平滑和優(yōu)化處理，對(duì)智能車在車道障礙物的具體建模場(chǎng)景中，均成功規(guī)劃出一條更為便捷且更為平滑的全局安全路徑。實(shí)驗(yàn)結(jié)果表明該方法能夠較好地克服傳統(tǒng)蟻群算法存在的缺陷，能提高算法效率同時(shí)優(yōu)化車輛的具體行駛路徑，實(shí)現(xiàn)了動(dòng)態(tài)避障的目標(biāo)。何雅穎等[12]提出的由起點(diǎn)到終點(diǎn)距離以及地圖參數(shù)來(lái)構(gòu)建全局優(yōu)先區(qū)域，避免算法在龐大的全局空間中進(jìn)行盲目的搜索；在信息素的更新公式中引入信息素增強(qiáng)因子，再提高相應(yīng)的路徑信息素含量。采用反向?qū)W習(xí)來(lái)優(yōu)化路徑上的信息素含量，能夠很好地解決傳統(tǒng)蟻群算法存在陷入局部最優(yōu)、收斂速度慢等一些問(wèn)題。

3.2 蟻群算法的其他應(yīng)用

自蟻群算法被其他的研究者開(kāi)發(fā)以來(lái)，已經(jīng)被運(yùn)用于很多其他的方面，如基于生產(chǎn)的多目標(biāo)分配問(wèn)題、集裝箱經(jīng)典分配問(wèn)題、無(wú)人機(jī)的遠(yuǎn)距離調(diào)度問(wèn)題、甚至還可以用于電力的用戶規(guī)劃，運(yùn)用十分廣泛。

孫新宇等[13]基于經(jīng)典蟻群算法的基本特性和固有特點(diǎn)，對(duì)比了最優(yōu)解算法、試探算法和循環(huán)改進(jìn)算法對(duì)解決裝配線問(wèn)題，不能取得良好的結(jié)果之后，便對(duì)原有的蟻群算法進(jìn)行改進(jìn)和嘗試，在原有的蟻群算法加入局部搜索的機(jī)制，利用了比較新穎的蟻群算法解決了混流裝配線的調(diào)度問(wèn)題。四川大學(xué)徐剛等[14]基于原有的算法模型對(duì)基本特征進(jìn)行改進(jìn)，引入了具有變異特征的蟻群算法，利用蟻群中的相互幫助、相互傳遞信息的機(jī)制尋找水庫(kù)中的水分配的最優(yōu)解，并且本方法較好地解決了動(dòng)態(tài)規(guī)劃中的水庫(kù)群?jiǎn)栴}優(yōu)化調(diào)度中的所特有的“維數(shù)”問(wèn)題。除此之外，蟻群算法的運(yùn)用對(duì)無(wú)人機(jī)的位置功能的規(guī)劃也有幫助，柳長(zhǎng)安[15]在文中利用蟻群算法不受搜索空間的限制約束和不必要求連續(xù)性和導(dǎo)數(shù)存在的假設(shè)的特點(diǎn)，在對(duì)無(wú)人機(jī)的動(dòng)態(tài)航路的規(guī)劃中有良好的路徑規(guī)劃特性，并提出了改進(jìn)的蟻群算法，解決了多架無(wú)人機(jī)的路徑規(guī)劃問(wèn)題。在配電網(wǎng)的調(diào)度規(guī)劃問(wèn)題中，王志剛等[16]以配電網(wǎng)中的綜合使用費(fèi)用和過(guò)負(fù)荷懲罰費(fèi)最小為目的，提出了一種網(wǎng)架規(guī)劃的數(shù)學(xué)模型，把每只螞蟻?zhàn)鳛橐粋€(gè)線路集合，最后形成一個(gè)規(guī)劃方案，有效說(shuō)明了蟻群算法在配電網(wǎng)的調(diào)度規(guī)劃問(wèn)題中的可行性。同時(shí)，東南大學(xué)的陳歆技等[17]將線路中的故障定位問(wèn)題轉(zhuǎn)化為一種新型的TSP問(wèn)題，并且采用電力系統(tǒng)中的分級(jí)保護(hù)的原理對(duì)整個(gè)配電網(wǎng)進(jìn)行區(qū)分，最后借助蟻群算法進(jìn)行局部?jī)?yōu)化，最后較好地解決了配電的故障問(wèn)題。

4 改進(jìn)蟻群算法在機(jī)器人應(yīng)用中的未來(lái)展望

隨著蟻群算法的不斷改進(jìn)與發(fā)展，蟻群算法已經(jīng)能在很多領(lǐng)域進(jìn)行應(yīng)用。在未來(lái)，蟻群算法與其他各種智能算法結(jié)合的改進(jìn)型蟻群算法將被多次利用并且運(yùn)用于解決實(shí)際問(wèn)題。但是與其他智能算法相比，蟻群算法還不成熟，蟻群算法的運(yùn)用還有很長(zhǎng)一段時(shí)間，仍需要更多的研究者去發(fā)掘和運(yùn)用。同時(shí)，蟻群算法的收斂性問(wèn)題雖然被眾多學(xué)者解決，但是如何權(quán)衡收斂速度和收斂次數(shù)的矛盾是最主要的問(wèn)題。