蟻群算法在路徑規(guī)劃中的應(yīng)用研究

肖厚國

（大連理工大學(xué)城市學(xué)院，遼寧大連 116000）

隨著科技的發(fā)展，推動了優(yōu)化理論的進步，使其被廣泛地應(yīng)用于航空航天、自動化等各個領(lǐng)域，同時伴隨著“互聯(lián)網(wǎng)+”技術(shù)的普及應(yīng)用，優(yōu)化理論呈現(xiàn)出更深、更快的發(fā)展趨勢，為解決優(yōu)化算法提供了契機。為此該文通過對蟻群算法的基本原理以及應(yīng)用現(xiàn)狀進行研究，以期為蟻群算法的深入研究奠定基礎(chǔ)。

1 蟻群算法的基本原理

蟻群算法主要通過選擇、更新、協(xié)調(diào)機制來進行路徑規(guī)劃，其算法基本思想是通過模擬螞蟻在尋找食物過程中采用的正反饋原理尋找最短路徑，螞蟻在經(jīng)過的路徑上釋放易揮發(fā)性物質(zhì)信息素(pheromone)，并通過信息素進行相互通信。蟻群算法可分為三步：首先找出初始路徑；其次對路徑剪枝，去掉與實際條件不相關(guān)屬性；最后更新信息素濃度，為后續(xù)螞蟻選擇路徑提供參考依據(jù)。

1.1 初始環(huán)境

設(shè)A點為螞蟻初始行駛的位置，D點為螞蟻最終到達的目的地，ABD和ACD分別為兩條截然不同路徑，其中 ABD=2，ACD=4，ACD=2ABD，初始螞蟻數(shù)量為40只。

1.2 約束條件

該文在進行論述蟻群算法對以下信息進行約束。

（1）兩條路徑的信息濃度為0。

（2）在行駛的過程中始終保持速度不變。

（3）到達點D立即返回。

1.3 螞蟻聚集密度的變化現(xiàn)象

（1）當 t=0 時。

A點共有40只螞蟻，沿ABD路徑的螞蟻數(shù)量為20只，記作N1，沿ACD路徑螞蟻的數(shù)量為20只，記作N2。

（2）當 t=2 時。

因ACD和ABD路徑的長度不同，當t=2時，N1已到終點，而N2剛到達C點。為簡化計算，設(shè)N1、N2到達后立即按原有路程折回，此時DBA上的螞蟻信息濃度由0變成20，而N2還未到達終點D，故DCA上螞蟻的信息濃度為0。

（3）當 t=4 時。

當t=4時，N1回到初始位置，N2剛好到達終點D，因N1已在ABD路徑上留下兩次“痕跡”，而N2在ACD留下一次“痕跡”，所以ABD上的信息度是ACD上的兩倍，因此當螞蟻再次尋找食物時，會根據(jù)路徑上信息度的不同而選擇路徑。隨著越來越多的螞蟻選擇ABD，從而導(dǎo)致ABD的信息度要逐漸大于ACD上的信息度，致使ABD和ACD上信息度的差異越來越大，最終導(dǎo)致螞蟻逐漸趨向于選擇路徑ABD，而非路徑ACD。

1.4 蟻群算法的論述

通過查閱國內(nèi)外研究現(xiàn)狀，蟻群算法應(yīng)用于路徑規(guī)劃，其算法步驟如下。

步驟1：設(shè)初始信息素分布iij=i0，螞蟻初始數(shù)量為m0，最大迭代次數(shù)為Tmax，螞蟻記數(shù)器m=0，迭代計數(shù)器t=0。

步驟2：螞蟻k放置到ɡbegin的位置，并添加至禁忌表tabuk中。

步驟3：在當前可行域Z中選擇預(yù)計運動的節(jié)點，分為兩種情況。

情況1：若|Z|＝0，則所有節(jié)點都走過，即無路可走，跳轉(zhuǎn)至步驟8。

情況2：若|Z|＞0，根據(jù)轉(zhuǎn)移概率，并用輪盤賭的方式選擇下一步要前往的節(jié)點j，并將節(jié)點j加入禁忌表tabuk中。

其中公式（2）中，D為啟發(fā)信息項，一般設(shè)為常數(shù)1；

步驟4：螞蟻運動至節(jié)點J后，判斷是否到達目標位置；

情況1：若節(jié)點J不是目標節(jié)點，跳轉(zhuǎn)到步驟3；

情況2：若節(jié)點J是目標節(jié)點，螞蟻K到達目標位置，跳轉(zhuǎn)至步驟5；

步驟5：該次迭代是否介紹，若不是m=m+1，跳轉(zhuǎn)到步驟2，若是，則m=，并且按照公式（4）對信息素進行及時更新，公式（4）如下所示：

i（t+1）=（1-ρ）i（t）+Δjkij（公式 4）

步驟 8：若 t＜Tmax，則清空 tabuk，迭代次數(shù) t=t+1，并且跳轉(zhuǎn)到步驟2，否則規(guī)劃結(jié)束。

2 蟻群算法的應(yīng)用現(xiàn)狀

通過查詢現(xiàn)有的研究成果，現(xiàn)階段蟻群算法主要根據(jù)選擇、更新、協(xié)調(diào)三種模式進行路徑的部署優(yōu)化。在選擇層面，由于供給的信息量多，所以提供選擇的概率就越大；在更新方面，由于螞蟻多次在路徑上留下“痕跡”，信息濃度就會隨著“痕跡”的增多而增大，從而選擇“痕跡”路徑上多的螞蟻數(shù)量就越來越多；在協(xié)調(diào)層面，由于信息素是螞蟻間有效的“通訊”方式，它們通過“通訊”方式有效地進行傳遞信息，這在一定程度上確保了路徑規(guī)劃選擇蟻群算法的可靠性。即使如此，蟻群算法也難免會存在一定的瑕疵，如在收斂速度、局部優(yōu)化以及停滯等均存在一定的問題。

3 蟻群算法的展望

隨著信息技術(shù)的發(fā)展以及人工智能的涌現(xiàn)，研究學(xué)者針對蟻群算法存在的問題進行也進行了較大的優(yōu)化，但依然存在一定的問題，仍需要繼續(xù)攻破。

（1）螞蟻數(shù)目的確定問題。周邊環(huán)境的狀況與螞蟻的數(shù)量存在一定的關(guān)聯(lián)關(guān)系，而螞蟻數(shù)目的多少在一定程度上回饋蟻群算法搜索的快慢。因此，有必要針對環(huán)境的不同狀況確定螞蟻的數(shù)目進行研究，從而進一步確定環(huán)境因素與螞蟻數(shù)目的選取問題。

（2）收斂速度慢和局部最優(yōu)解問題。由于收斂速度與局部最優(yōu)間相輔相成，雖然研究學(xué)者針對上述問題進行不同程度的探討，且提出較多的優(yōu)化方案，由于其他算法在環(huán)境、外界因素等方面有苛刻的要求，從而導(dǎo)致在收斂速度和局部最優(yōu)方面往往顧己失彼。因此有必要進行探討如何有效的顧及收斂和局部最優(yōu)的情形。

（3）參數(shù)值的設(shè)定。通過查詢現(xiàn)有的研究成果可知：在現(xiàn)階段，針對參數(shù)的設(shè)定方面并沒有明確計算公式，而是通過實驗進行確定參數(shù)值，因此，在參數(shù)值設(shè)定方面有必要研發(fā)出計算公式或程序進行界定。

（4）隨著自動化程度越來越高，移動機器人逐步趨向于市場化，而移動機器對路徑規(guī)劃的要求越來越高，因此有必要針對影響蟻群算法精準度的其他因子進行研究，從而提供路徑規(guī)劃的精準性。

4 結(jié)語

因蟻群算法具備搜索能力、正反饋、魯棒性等特點，而且、能夠友好的融合其他算法，因此蟻群算法普遍在應(yīng)用于路徑規(guī)劃中，該文針對蟻群算法在路徑規(guī)劃中的應(yīng)用進行研究，以期為蟻群算法的深入研究奠定一定的基礎(chǔ)。