劉 振 王亞蛟

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

1 引言

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

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

2 基本蟻群算法及其存在的問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中

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

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

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

通過(guò)上述的描述，可以總結(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é)點(diǎn)的區(qū)間概率其中概率的計(jì)算可按照式（4）和（5）；

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

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

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

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

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

定義1：

定理1：若滿足：

證明：

證畢。

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

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

表1 TSP問(wèn)題仿真結(jié)果對(duì)比

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

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

圖1 Bays29問(wèn)題仿真對(duì)比結(jié)果

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

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

圖2 Eil101問(wèn)題仿真對(duì)比結(jié)果

表2 Oliver30問(wèn)題對(duì)比表

表3 Eil51問(wèn)題對(duì)比表

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

6 結(jié)語(yǔ)

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