一種記憶區(qū)間蟻群算法及其仿真分析*

劉 振 王亞蛟

（1.海軍航空大學(xué)岸防兵學(xué)院 煙臺 264001）（2.92706部隊 寧波 315813）

1 引言

蟻群優(yōu)化算法作為一種經(jīng)典的啟發(fā)式智能優(yōu)化算法，由Dorigo M率先提出［1]，經(jīng)過二十多年的發(fā)展，已經(jīng)廣泛應(yīng)用于故障診斷［2]、路徑規(guī)劃［3]、圖像處理［4]、網(wǎng)址追蹤［5]等問題。由于基本蟻群容易陷入局部極值并且收斂速度慢，國內(nèi)外已經(jīng)有許多學(xué)者提出了很多改進(jìn)的蟻群算法，例如小生境蟻群算法［6]、協(xié)同進(jìn)化蟻群算法［7]等，文獻(xiàn)［8]提出一種改進(jìn)蟻群算法用于網(wǎng)絡(luò)編碼資源最小化問題，基于特定問題設(shè)定啟發(fā)式信息，同時提出一種多維信息素保留體制，文獻(xiàn)［9]將蟻群算法與迭代局部搜索算法相結(jié)合。雖然已經(jīng)有諸多學(xué)者對蟻群算法進(jìn)行了改進(jìn)，并有效提高了蟻群算法的收斂性能，但蟻群算法作為一種仿生智能進(jìn)化算法，由于其迭代尋優(yōu)過程的本質(zhì)特點，導(dǎo)致其收斂速度和收斂性能方面仍然受到一定的限制。

從當(dāng)前諸多改進(jìn)方法可以看出，要想提高蟻群進(jìn)化算法的優(yōu)化性能，在保留螞蟻的尋優(yōu)特點以及整體優(yōu)化流程的基礎(chǔ)上，必須從螞蟻路徑選擇方式和信息素更新方式出發(fā)對算法進(jìn)行相應(yīng)改進(jìn)和推廣。綜合以上的分析和考慮，本文提出了一種轉(zhuǎn)移概率為區(qū)間概率，并且信息素更新方式具有記憶特征的記憶區(qū)間蟻群算法（memory interval ant colony optimization，MIACO），將蟻群算法的信息素濃度推廣為區(qū)間數(shù)，并對螞蟻路徑的概率選擇方式進(jìn)行了有效的改進(jìn)，同時結(jié)合人類記憶特征［10]，對螞蟻信息素的更新方式進(jìn)行了擴展。

2 基本蟻群算法及其存在的問題

對于一個具有n個城市的TSP問題，共有n只螞蟻進(jìn)行迭代尋優(yōu)，當(dāng)?shù)趉只螞蟻處于第i個城市時，其選擇下一個城市的訪問概率可以表示為

在式（1）中，τij為第i個城市和第j個城市之間的信息素濃度，ηij表示路徑長度的啟發(fā)式信息，dij表示城市之間的距離，α和β分別為信息素濃度和啟發(fā)式信息的重要度影響因子，allowed(k)為第k只螞蟻的下一步允許經(jīng)過的路徑集合。螞蟻根據(jù)式（1）進(jìn)行迭代搜索，當(dāng)經(jīng)過一定的迭代次數(shù)以后，完成一次遍歷搜索，更新經(jīng)過的每條邊的信息素濃度，更新方法按式（2）進(jìn)行。

從基本蟻群算法的進(jìn)化過程可以看出，每只螞蟻都以固定概率的選擇下一個節(jié)點，勢必存在一定的缺陷。首先信息素濃度和啟發(fā)式信息都是固定的數(shù)值，選擇方式較為單調(diào)，為提高選擇過程中的多樣性，可考慮采用區(qū)間參數(shù)信息和區(qū)間概率的選擇方式，能夠保證在選擇較優(yōu)路徑的基礎(chǔ)上，增加尋優(yōu)過程中的隨機性。其次螞蟻都傾向于選擇最優(yōu)路徑，因而信息素濃度容易累積在局部路徑上，限制了尋優(yōu)能力較強的螞蟻的全局選優(yōu)能力，不能充分協(xié)同利用蟻群優(yōu)化算法的勘探（exploration）和開采（exploitation）能力，可考慮對路徑的更新范圍推廣到次優(yōu)路徑，并對全局更新和局部更新采用基于人類記憶的更新方式。

3 記憶區(qū)間蟻群算法的提出

3.1 區(qū)間信息素濃度的初始化方法

在以往的蟻群進(jìn)化算法中，在初始時刻，都是采用統(tǒng)一的信息素濃度，沒有體現(xiàn)出啟發(fā)式信息指導(dǎo)作用，因此為了提高算法的收斂性能，在算法初始化的過程中，提出區(qū)間信息素濃度為區(qū)間數(shù)的方法，其設(shè)置方法如式（3）所示：

3.2 區(qū)間概率的轉(zhuǎn)移方法

當(dāng)信息素濃度為區(qū)間數(shù)時，蟻群的轉(zhuǎn)移概率也為區(qū)間概率形式，選擇某一節(jié)點j的概率上限為

選擇某一節(jié)點j的概率下限可以表示為

當(dāng)?shù)玫侥骋还?jié)點概率區(qū)間以后，利用最大熵［11]方法得到精確的點概率。對于概率可按照式（6）求解最優(yōu)化模型，獲得點概率值：

3.3 區(qū)間信息素濃度的更新方法

按照認(rèn)知心理學(xué)的界定，人類記憶的特點分為長時記憶、短時記憶和瞬時記憶［12]。不失一般性，本文只考慮長時記憶和短時記憶對信息素更新的影響。蟻群算法中信息素的更新方式有效地融合人類記憶的特性，對于全局最優(yōu)路徑及其部分次優(yōu)路徑，將其歸入長時記憶的范疇，即記憶較為深刻的信息素，短時記憶在人類記憶方式中對應(yīng)印象并不深刻的事物，在蟻群算法中，對應(yīng)于一次尋優(yōu)后得到的可行路徑。

螞蟻尋優(yōu)過程中的信息素按照不同記憶方式，分為長時記憶更新方式和短時記憶更新方式，分別設(shè)置長時記憶因子系數(shù)和長時記憶揮發(fā)系數(shù)，短時記憶因子系數(shù)和短時記憶揮發(fā)系數(shù)。采用基于長時記憶的更新方式，對一次迭代完成后的最優(yōu)路徑及其次優(yōu)路徑的信息素進(jìn)行全局更新，而在短時記憶方式中，則利用短時記憶因子系數(shù)和短時記憶揮發(fā)系數(shù)對相應(yīng)路徑及其次優(yōu)路徑信息素進(jìn)行局部更新。

3.3.1 信息素的全局記憶更新方式

信息素更新方式對提高蟻群算法的全局收斂性能具有重要的作用，但通過蟻群算法信息素的更新方式可以看出，利用這種正反饋機制，有效增加了全局最優(yōu)解信息素濃度的同時，也使得最優(yōu)解和其它解之間的信息素濃度差距變大。在蟻群尋優(yōu)過程中，次優(yōu)解中的路徑片段往往是潛在最優(yōu)解的部分路徑片段，因此為提高算法的收斂精度和收斂速度，本文提出除了更新當(dāng)前最優(yōu)路徑以外，同時更新適應(yīng)度較優(yōu)的若干次優(yōu)路徑，提高進(jìn)化過程中螞蟻選擇的多樣性。

假定此時的最優(yōu)路徑值為fb，判斷當(dāng)前路徑是否滿足：

當(dāng)路徑滿足式（7）時，則對該路徑進(jìn)行一次全局記憶更新。引入長時記憶因子系數(shù)λL，長時揮發(fā)系數(shù)ρL，此時的信息素濃度選擇使用區(qū)間數(shù)的上限進(jìn)行更新，即按照式（8）進(jìn)行更新：

其中

3.3.2 信息素局部記憶更新方式

當(dāng)螞蟻經(jīng)過的路徑并非最優(yōu)路徑時，將其視為短時記憶路徑?；鞠伻核惴窂礁潞瓦x擇方式的優(yōu)點在于簡單易行，收斂速度較快，但收斂的時間過長并且收斂效果并不優(yōu)越，無法保證取得全局最優(yōu)結(jié)果。因此針對基本蟻群算法存在的問題，將所有的路徑進(jìn)行排序，當(dāng)t時刻處于節(jié)點i的某只螞蟻按照式（1）選擇某個節(jié)點j后，按照式（9）更新信息素濃度：

在式（9）中，Δτis為該段路徑片段長度值的倒數(shù)，為短時記憶因子系數(shù)，ρE為短時記憶揮發(fā)系數(shù)。若路徑Lij為節(jié)點i與相鄰結(jié)點之間的最短路徑，假定此時的次優(yōu)路徑為Lik，則按照式（9）更新信息素τik(t+1)，若路徑Lij并不是節(jié)點i與下一節(jié)點之間的最短路徑，假定此時的最優(yōu)路徑為Lih，則更新路徑τih(t+1)。

通過上述的描述，可以總結(jié)本文提出的記憶區(qū)間蟻群算法（MIACO）的步驟如下。

步驟1初始化算法的參數(shù)信息，包括蟻群的規(guī)模，算法的循環(huán)迭代次數(shù)，按照式（3）初始化信息素濃度，以及α、β、λL、ρL、λE及ρE等參數(shù)；

步驟2判斷是否滿足結(jié)束條件，不滿足則繼續(xù)循環(huán)迭代，即t←t+1；

步驟3依據(jù)區(qū)間概率的方式，獲得螞蟻選擇下一結(jié)點的區(qū)間概率其中概率的計算可按照式（4）和（5）；

步驟4依照式（6）獲得選擇概率的點概率值pij，第k只螞蟻依據(jù)pij選擇下一結(jié)點；

步驟5在完成一步行進(jìn)后，將其標(biāo)記為短時記憶，按照式（9）進(jìn)行局部信息素更新；

步驟6當(dāng)所有螞蟻都完成一次遍歷后，根據(jù)式（7）選擇符合長時記憶更新方式的候選路徑集合，并按照式（8）進(jìn)行更新；

步驟7判斷是否滿足迭代結(jié)束條件，滿足則結(jié)束，輸出最優(yōu)解，否則轉(zhuǎn)步驟2。

4 記憶區(qū)間蟻群算法收斂性分析

定義1：

定理1：若滿足：

證明：

證畢。

5 記憶區(qū)間蟻群算法仿真驗證分析

為了充分驗證算法的有效性，對算法利用TSP問題進(jìn)行仿真分析，設(shè)定α=1，β=1.5，ε=0.95，λL=1.2，ρL=0.90，λE=1.1，ρE=0.80，參數(shù)Q隨問題規(guī)模自適應(yīng)調(diào)整為了驗證算法的有效性，選用五個典型的TSP問題進(jìn)行仿真分析，分別是Fri26、Bays29、Eil76、KroD100及Eil101進(jìn)行仿真分析。算法獨立運行十次，將本文提出的記憶區(qū)間蟻群算法（MIACO）與基本蟻群算法進(jìn)行仿真對比，統(tǒng)計結(jié)果如表1所示。

表1 TSP問題仿真結(jié)果對比

從統(tǒng)計結(jié)果可以看出，本文所提出的MIACO在幾個典型TSP問題中都能取得較好的尋優(yōu)結(jié)果，并且在某些函數(shù)能夠獲得理論最優(yōu)值，而這在很多情況下傳統(tǒng)ACO算法所無法達(dá)到的。但同時也注意到，本文算法的運行時間較之以前有了較為明顯的增加，特別是當(dāng)TSP問題的規(guī)模在不斷擴大的時候。這主要是因為隨著問題規(guī)模的不斷增大，采用區(qū)間數(shù)進(jìn)行路徑更新以及利用區(qū)間概率選擇路徑時，問題的規(guī)模急劇變大，在增加選擇多樣性的同時，也增加了系統(tǒng)的負(fù)擔(dān)，加重了系統(tǒng)的開銷。因此本文提出的MIACO，在優(yōu)化規(guī)模較小的TSP問題時，可以在計算精度和計算效率之間得到較好的平衡，當(dāng)問題規(guī)模較大時，可以適當(dāng)將信息素的更新方式采用傳統(tǒng)的點概率更新方式。

為了進(jìn)一步進(jìn)行對比分析，將Bays29和Eil101進(jìn)行仿真對比分析，收斂迭代結(jié)果分別如圖1和圖2所示。

圖1 Bays29問題仿真對比結(jié)果

從圖1和圖2可以看出，利用本文所提出的MIACO，無論是取得的最優(yōu)解，還是最終解的穩(wěn)定性都較基本ACO有了明顯的進(jìn)步，顯示出本文利用區(qū)間概率選擇路徑和信息素記憶更新方式體現(xiàn)出的優(yōu)越性。

為進(jìn)一步進(jìn)行分析，以O(shè)liver30及Eil51問題為例，將本文算法與相關(guān)文獻(xiàn)比較，MIACO運行的結(jié)果優(yōu)于大部分文獻(xiàn)的方法，只有文獻(xiàn)［15]的方法所尋找到的最優(yōu)值略優(yōu)于本文提出的方法，但算法穩(wěn)定性并不如本文算法。

圖2 Eil101問題仿真對比結(jié)果

表2 Oliver30問題對比表

表3 Eil51問題對比表

由表2和表3的對比結(jié)果可以看到，利用本文提出的MIACO算法，在求解Oliver30以及Eil51上都已經(jīng)具備了良好的性能，其性能較文獻(xiàn)［3]也更為穩(wěn)定，充分顯示出MIACO的優(yōu)越性。

6 結(jié)語

本文提出一種具有記憶特征的區(qū)間蟻群優(yōu)化算法MIACO。算法的最主要的特征在于將信息素濃度推廣到區(qū)間數(shù)，打破了過去信息素濃度都為固定數(shù)值的局限性。在路徑的揮發(fā)和增強過程中，充分考慮人類記憶特征，引入長時記憶和短時記憶更新方式，采用不同的揮發(fā)系數(shù)，從而使得在路徑更新和選擇過程中呈現(xiàn)更具層次的多樣性。在本文對提出的MIACO進(jìn)行了理論分析和仿真驗證分析，充分證明了算法所具有的優(yōu)越性。