焦宗浩，高紹姝，李克文

(中國石油大學(xué) 計算機(jī)與通信工程學(xué)院，山東 青島 266580)

0 引 言

隨著人工智能[1]的飛速發(fā)展，專家學(xué)者逐漸從生活中尋求更先進(jìn)的思想，如從自然界中模擬生物群體解決生存問題的行為，其中蟻群算法[2]是模擬螞蟻覓食、粒子群算法[3]是模擬鳥群覓食。蟻群算法(ant colony optimization，ACO)是在20世紀(jì)90年代由意大利學(xué)者M(jìn). Dorigo根據(jù)蟻群覓食活動提出的，后經(jīng)德國學(xué)者Stützle提出一種改進(jìn)的蟻群算法——最大最小螞蟻系統(tǒng)(MAX-MIN ant system，MMAS)，該方法廣泛應(yīng)用于各種領(lǐng)域[4-8]，其工作原理是在每次循環(huán)過程中僅選擇一只最優(yōu)螞蟻進(jìn)行信息素的更新，該更新方式加快了收斂速度，但同時容易陷入局部最優(yōu)。針對MMAS存在的問題，現(xiàn)有的文獻(xiàn)一般是通過改進(jìn)信息素的更新方式[9,10]、調(diào)整螞蟻的轉(zhuǎn)移規(guī)則[11]、采用自適應(yīng)方法[12,13]等，或者是將MMAS與其它算法結(jié)合，如鄰域搜索[14]、模擬退火策略[15]，甚至是蟻群算法[16]等。這些算法在一定的程度上提升了螞蟻的全局搜索能力，但精度有待提高。本文通過可變天氣因素對蟻群影響，提出一種基于可變天氣因素的最大最小螞蟻系統(tǒng)(VW-MMAS)，通過隨機(jī)的信息素?fù)]發(fā)機(jī)制，改變信息素的殘留程度，增強(qiáng)其搜索的能力，提高解的精度。

1 相關(guān)概念

1.1 基本蟻群算法

我們以求解平面上n城市的旅行商問題(TSP)為例，來說明傳蟻群算法原理。TSP問題是指，給定一組城市坐標(biāo)，城市數(shù)量為n，求得一條遍歷所有城市的最短回路的問題，其中除了出發(fā)的城市以外其它城市僅允許走一次。首先初始化蟻群數(shù)量m，信息啟發(fā)因子α，期望啟發(fā)因子β，信息素?fù)]發(fā)系數(shù)ρ，各路徑上的信息素τij，其中在初始時刻每條路徑的信息素濃度設(shè)為相等，即τij=C(C為較小的常數(shù))；然后在每次迭代過程中，每只螞蟻隨機(jī)選擇一個城市作為起始城市，再使用輪盤賭的方法，按照式(1)選擇下一個城市

(1)

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

(2)

1.2 最大最小螞蟻系統(tǒng)

最大最小螞蟻系統(tǒng)(MMAS)是在ACO上改進(jìn)，克服ACO容易陷入局部最優(yōu)、收斂速度慢、花費(fèi)時間長等缺點(diǎn)，其主要改進(jìn)方向是以下3個方面：

(1)將信息素τij限制在τmin與τmax之間，即τmin≤τij≤τmax， 該策略避免最優(yōu)路徑上的信息素和未訪問路徑的信息素差距過大，導(dǎo)致搜索的停滯；

(2)將初始信息素設(shè)置為τmax， 該策略使得算法在初始階段有更多的搜索可能；

(3)在每次迭代之后，只允許路徑最優(yōu)螞蟻更新信息素，可以是當(dāng)前迭代最優(yōu)，也可以是歷史最優(yōu)。其信息素更新方式按照式(3)進(jìn)行

(3)

2 改進(jìn)的最大最小螞蟻系統(tǒng)

雖然群體螞蟻有著明確的分工行為模式，但是其覓食行為仍受著外界環(huán)境的影響，如地形、天氣等外在因素。根據(jù)螞蟻的生活習(xí)性發(fā)現(xiàn)，在不同的天氣之后螞蟻的覓食行為有所不同，主要原因是在不同天氣信息素的殘留程度不同，如在雨天之后，雨水沖刷了信息素，導(dǎo)致信息素的整體減少，信息素之間的差距減少，使得螞蟻在雨天過后覓食范圍明顯擴(kuò)大。因此本文提出的可變天氣因素最大最小螞蟻系統(tǒng)(VW-MMAS)是針對不同天氣情況下，設(shè)置不同的信息素?fù)]發(fā)系數(shù)，從而改進(jìn)最大最小螞蟻系統(tǒng)，更新全局信息素的殘留程度，擴(kuò)大其螞蟻的搜索范圍，避免快速陷入局部最優(yōu)，停止迭代。

2.1 基于可變天氣因素改進(jìn)MMAS算法

由于實(shí)際的天氣是復(fù)雜多樣的，為了說明本文所提出的改進(jìn)方法的有效性，實(shí)驗(yàn)以3種天氣情況為例，分別是雨天、陰天、晴天。通過在不同的天氣情況下設(shè)置不同的信息素?fù)]發(fā)系數(shù)，根據(jù)實(shí)際情況將信息素?fù)]發(fā)系數(shù)按照可變天氣因素排序；同時考慮到在不同天氣情況下，外出覓食的螞蟻數(shù)量有所不同，本文假設(shè)在雨天揮發(fā)系數(shù)最大且螞蟻不覓食，在陰天揮發(fā)系數(shù)最小且隨機(jī)選擇一定數(shù)量螞蟻覓食，在晴天揮發(fā)系數(shù)中等且全部螞蟻外出覓食。采用上述的改進(jìn)方式能夠有效增加全局的搜索能力，避免快速陷入局部最優(yōu)。

在不同的天氣下，設(shè)置不同的信息素?fù)]發(fā)系數(shù)以及蟻群數(shù)量。首先設(shè)置信息素?fù)]發(fā)ρr、ρc、ρs， 其中ρr表示雨天時揮發(fā)系數(shù)，ρc表示陰天時揮發(fā)系數(shù)，ρs表示晴天時揮發(fā)系數(shù)，信息素?fù)]發(fā)系數(shù)從大到小排序?yàn)椋害裷>ρc>ρs； 然后設(shè)置蟻群數(shù)量，晴天時螞蟻數(shù)量ms， 陰天時螞蟻數(shù)量mc(

2.2 信息素更新的改進(jìn)

在最大最小螞蟻系統(tǒng)中，只允許最優(yōu)的螞蟻留下信息素，導(dǎo)致其它路徑的信息素隨著迭代次數(shù)的增加而減少，這種方式雖然增強(qiáng)了最優(yōu)路徑的尋找，但同時增加了螞蟻陷入局部最優(yōu)的可能性。針對此問題，通過設(shè)置閾值，統(tǒng)計最優(yōu)路徑出現(xiàn)的次數(shù)，當(dāng)時出現(xiàn)的次數(shù)大于閾值時，在式(3)更新的基礎(chǔ)上，用式(4)再進(jìn)行信息素的更新，該方式保持最優(yōu)路徑上的信息素不變，但增加其它路徑上信息素，使得路徑上信息素濃度差減小

(4)

2.3 VW-MMAS算法流程

步驟1 初始化各參數(shù)k,α,β,Q,Iternation，初始信息素設(shè)置為τmax， 迭代次數(shù)NC=0；

步驟2 按照2.1所述，設(shè)置3個隨機(jī)揮發(fā)系數(shù)ρr,ρc,ρs及對應(yīng)的蟻群數(shù)量mr,mc,ms, 在每次循環(huán)結(jié)束后隨機(jī)選擇一個揮發(fā)系數(shù)及對應(yīng)的螞蟻數(shù)量，作為當(dāng)前迭代下的揮發(fā)系數(shù)及螞蟻數(shù)量；

步驟3 統(tǒng)計信息素?fù)]發(fā)系數(shù)ρr連續(xù)出現(xiàn)的次數(shù)是否大于閾值，若是轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟4；

步驟4 將m只螞蟻隨機(jī)放入到n座城市中，并將城市放入禁忌表tabu中；

步驟5 每只螞蟻按照概率(式(1))選擇下一次要訪問的城市，并將該城市放入禁忌表中，直到遍歷完所有城市，計算其路徑長度，并將每只螞蟻的路徑長度保存在distance_list中；

步驟6 當(dāng)每只螞蟻均遍歷完城市之后，保存當(dāng)前迭代最優(yōu)路徑bestRoute以及對應(yīng)最短路徑長度minDistance；

步驟7 按照式(3)將從步驟5中選出來的最優(yōu)螞蟻更新信息素；

步驟8 判斷最優(yōu)路徑長度出現(xiàn)的次數(shù)是否已經(jīng)超過設(shè)置的閾值，如果已經(jīng)超出，按照式(4)進(jìn)行更新信息素；

步驟9 禁忌表tabu清空，迭代次數(shù)NC=NC+1。 如果迭代次數(shù)沒有達(dá)到最大值，則轉(zhuǎn)向步驟2；否則輸出最優(yōu)解并退出循環(huán)。

流程如圖1所示。

圖1 改進(jìn)算法VW-MMAS流程

3 仿真實(shí)驗(yàn)結(jié)果及討論

為了評估VW-MMAS解決TSP問題的性能，實(shí)驗(yàn)分別使用遺傳算法(GA)、粒子群算法(PSO)、蟻群算法(ACO)、最大最小螞蟻系統(tǒng)(MMAS)以及本文提出的VW-MMAS對TSPLIB數(shù)據(jù)庫中的TSP問題進(jìn)行求解比較。其中GA中重要參數(shù)取值為：交叉概率pc=0.7， 變異概率pm=0.02， 種群數(shù)量m=100； PSO中重要參數(shù)取值為：α=1，β=0.9， 種群數(shù)量m=1000； ACO中重要參數(shù)取值為：α=0.8，β=2，Q=100，ρ=0.05， 種群數(shù)量m=2/3*n； MMAS中重要參數(shù)取值為：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρ=0.05， 種群數(shù)量m=2/3*n； VW-MMAS中各參數(shù)的取值為：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρr=0.3，ρc=0.2，ρs=0.15， 種群數(shù)量mr=0，mc=1/3*n，ms=2/3*n。 針對8個TSP問題，每種算法最大迭代次數(shù)MaxIter=1000， 并記錄算法的最優(yōu)解，結(jié)果見表1。

根據(jù)表1中的結(jié)果可以看到，本文所提出的VW-MMAS算法與GA、PSO、ACO、MMAS算法相比，在大部分的TSP問題上所得解的質(zhì)量更好，甚至在大規(guī)模的TSP問題也有一個很好的解，證明了VW-MMAS算法在求解TSP問題上，所得解的精度有所提升或者保持良好。圖2 展示了VW-MMAS算法在求解每個TSP問題時，最優(yōu)的解決方案。

表2展示了對于每一個數(shù)據(jù)集，每種算法獨(dú)立運(yùn)行十次，求得的每個算法的最優(yōu)解、最差解、平均解以及標(biāo)準(zhǔn)差，其中最優(yōu)解表示每個算法對TSP問題最好的解決方案，最差解表示每個算法對TSP問題最差的解決方案，平均解以及標(biāo)準(zhǔn)差表示算法的可靠性以及穩(wěn)定性，而標(biāo)準(zhǔn)差越小，表示該算法越穩(wěn)定更能找到最優(yōu)解，反之標(biāo)準(zhǔn)差越大，算法的穩(wěn)定性越差。

從表2中，可以看出VW-MMAS算法在所有TSP問題上最優(yōu)解、最差解、標(biāo)準(zhǔn)差上取得了一個較好的性能。同時VW-MMAS算法的標(biāo)準(zhǔn)差小于MMAS算法的標(biāo)準(zhǔn)差，表明其穩(wěn)定性和可靠性優(yōu)于MMAS；而相比較GA、PSO、ACO這3種算法，雖然VW-MMAS在少數(shù)TSP問題上的標(biāo)準(zhǔn)差偏大，但是在整體上由于其最優(yōu)解好于其它算法，并且最差解及平均解的精度均有所提高，這意味著VW-MMAS算法在尋找最優(yōu)解時更穩(wěn)定可靠，而其它算法更容易陷入局部最優(yōu)。

表1 不同TSP問題對應(yīng)算法的實(shí)驗(yàn)結(jié)果

圖2 VW-MMAS求解TSP問題最優(yōu)路徑

上述仿真實(shí)驗(yàn)結(jié)果表明，本文提出的VW-MMAS算法在解決TSP問題具有更好的精度，與其它算法相比，提供的最優(yōu)解最小且標(biāo)準(zhǔn)差較小。

4 結(jié)束語

本文提出VW-MMAS算法是在MMAS算法的基礎(chǔ)上，引入以下機(jī)制：

(1)結(jié)合可變天氣因素，提出隨機(jī)信息素?fù)]發(fā)系數(shù)和蟻群數(shù)量機(jī)制，使用多個信息素?fù)]發(fā)系數(shù)和蟻群數(shù)量代替原本僅使用單參數(shù)求解TSP問題，增加了信息素的變化情況，增強(qiáng)螞蟻的搜索能力；

(2)由于在算法運(yùn)行后期容易陷入局部最優(yōu)，通過考慮城市之間的距離對螞蟻路徑搜索的影響，將其作為在陷入局部最優(yōu)時信息素更新方式，增加了不是最優(yōu)路徑上信息素的濃度，縮小了信息素之間的差距，從而擴(kuò)大蟻群的搜索范圍。

通過仿真實(shí)驗(yàn)驗(yàn)證了VW-MMAS算法的有效性，與其它算法相比，解的精度更好而且標(biāo)準(zhǔn)差最小，表明算法的穩(wěn)定性和可靠性。

表2 不同TSP問題對應(yīng)算法比較