趙 鑫，楊雄飛，錢育蓉+

(1.新疆大學 軟件學院，新疆 烏魯木齊 830046；2.新疆大學 軟件工程重點實驗室，新疆 烏魯木齊 830046；3.新疆維吾爾自治區(qū) 信號檢測與處理重點實驗室，新疆 烏魯木齊 830046)

0 引 言

旅行商問題(traveling salesman problem，TSP)是一個典型的組合優(yōu)化問題[1]，國內(nèi)外學者對這一問題的研究已有很多[2]。蟻群優(yōu)化算法(ant colony optimization，ACO)是一種群體智能算法[3]，蟻群算法具有基于分散自組織系統(tǒng)集體行為的人工智能，蟻群算法早期被應用于求解TSP問題[4]，對最優(yōu)路徑尋優(yōu)具有良好的優(yōu)越性，但也存在收斂速度慢、容易陷入局部最優(yōu)等缺點。對于蟻群算法的改進，比較著名的改進算法還有精英策略螞蟻系統(tǒng)[5]、優(yōu)化排序螞蟻系統(tǒng)[6]等；也有學者對蟻群算法應用于解決多目標優(yōu)化問題而設(shè)計多目標進化算法，改善其計算效率不高的問題[7]，在網(wǎng)格環(huán)境下改善均衡作業(yè)調(diào)度[8]，用于配水系統(tǒng)優(yōu)化[9]，解決武器-目標分配問題[10]。

本文研究針對基本蟻群算法在求解TSP問題時表現(xiàn)的停滯行為和早熟收斂問題，提出了一種帶有遺忘因子的蟻群優(yōu)化算法，命名為遺忘因子蟻群優(yōu)化算法(forgetting factor ant colony optimization，F(xiàn)FACO)算法。FFACO算法在基本蟻群算法基礎(chǔ)上，優(yōu)化轉(zhuǎn)態(tài)轉(zhuǎn)移公式和信息素更新規(guī)則，縮短了城市轉(zhuǎn)換的時間成本，最大限度地發(fā)揮了當前最優(yōu)解的主導作用，加快了收斂速度，同時避免局部解的產(chǎn)生。對TSP的仿真結(jié)果表明，改進后的算法通過變遺忘因子進行對最優(yōu)解的跟蹤，避免了誤差的積累，提高了算法求解的效率。

1 蟻群優(yōu)化算法

1.1 ACO數(shù)學模型

TSP問題用完全加權(quán)有向圖表示G=(V,A,d)，變量V={1,2,…,n} 為城市集，其中n為城市數(shù)，A={(i,j)|(i,j)∈V*V} 為弧集，d是與每條弧arc(i,j)關(guān)聯(lián)一個正整數(shù)的加權(quán)函數(shù)，TSP的目的是在每個城市只訪問一次時找到一條最短的路徑。蟻群算法是一種啟發(fā)式算法，用來模擬真實蟻群的行為，建立食物源與蟻巢之間的最短路徑[11]。當螞蟻尋找食物時，它會在自己所經(jīng)過的路徑上釋放出一種信息素，其它的螞蟻可以被該信息素吸引，而選擇這個路徑，當越來越多的螞蟻通過這條路徑時，會導致更多的信息素沉積在該路徑上，也會吸引更多的螞蟻繼續(xù)選擇該路徑。因為螞蟻根據(jù)信息素數(shù)量的多少來抉擇將要移動的路徑，信息素在路徑上的沉積的越多，也就越有可能吸引更多的螞蟻來選擇該路徑。因此，螞蟻們依據(jù)該原理構(gòu)造出從巢穴到食物來源并返回的最短路徑，在下面，將提供基本ACO的正式定義。在算法初始階段，隨機的將每只螞蟻放置在一個城市位置上，在構(gòu)造可行解的過程中，每只螞蟻通過概率決策規(guī)則選擇下一個將要訪問的城市位置，第k只螞蟻由當前城市位置，移動到下一個城市位置的概率由式(1)給出，如下所示

(1)

τij(t+s)=(1-ρ)τij(t)+Δτij,ρ∈(0,1)

(2)

α是一個信息啟發(fā)式因子，它決定了信息素的相對影響，β是期望啟發(fā)因子，表示期望值的相對重要性，反映了螞蟻在運動過程中路徑長度的影響，ρ是一個信息素殘留系數(shù)。其中τij(t)是信息素在arc(i,j)上時刻t的蹤跡量。路徑上的信息素將一步一步蒸發(fā)掉。經(jīng)過時間s后，根據(jù)式(2)更新軌跡強度

(3)

(4)

1.2 ACO算法流程

ACO算法的具體實現(xiàn)步驟如下：

(1)初始化階段，生成算法所需基本參數(shù)α,β,ρ，螞蟻數(shù)m、算法迭代次數(shù)NC、節(jié)點間代價值arc(i,j)、初始路徑信息素濃度τij(0)=A；

(2)螞蟻們根據(jù)式(1)計算的概率，來抉擇將要移動下一個節(jié)點的位置，并更新相應的tabuk；

(3)當螞蟻們完成一次周游后，記錄它經(jīng)過的路徑所需的最低成本值，若該值比當前最優(yōu)解更優(yōu)，則更新最優(yōu)解，m只螞蟻根據(jù)概率函數(shù)選擇下一個城市，完成本次周游；

(4)計算每條路徑上螞蟻留下的信息素數(shù)量；

(5)重復步驟(3)～步驟(4)，直到所有螞蟻完成整個周游；

(6)當所有螞蟻完成一個周期后，按式(2)～式(4)更新路徑上沉積的信息素濃度值；

(7)當算法達到指定的終止次數(shù)或達到設(shè)定的最優(yōu)值誤差率時，算法結(jié)束運行并輸出最優(yōu)解。

2 改進的蟻群優(yōu)化算法

2.1 遺忘因子調(diào)節(jié)策略

為了解決TSP傳統(tǒng)蟻群算法的局部最優(yōu)、搜索停滯和初始收斂慢的問題，在改進算法中，通過調(diào)整局部信息素更新策略和全局信息素更新策略，在傳統(tǒng)信息素更新策略中引入遺忘因子，螞蟻在搜索和強化的過程中達到了更好的平衡，在已有的已知數(shù)據(jù)上對該算法的性能進行了測試。當解算誤差較大時，自動選擇較小的遺忘因子以提高跟蹤靈敏度；當解算誤差較小時，自動選擇較大的遺忘因子，以增加記憶長度，提高辨識精度。

2.2 初始信息素設(shè)置

加權(quán)初始信息素分布基于最近鄰法，最近鄰法是數(shù)據(jù)挖掘中最簡單的分類算法之一[12]，由于該方法本身具有直觀、求解速度快的特點，因此本文采用最近鄰法來快速建立原始行程的初始信息素分布矩陣，TSP問題的基本概念是最近鄰法求解TSP問題，其實質(zhì)是貪心策略在解決實際問題中的實際應用，可以簡單地描述如下：首先，以一個源點城市為出發(fā)點，然后找到最近的城市，從源點城市找到連接下一城市的方式，并作為下一個源點；最后，依次重復，直到所有的城市標點添加到構(gòu)建的路徑中，并且將起始城市添加到周游路線的末尾，構(gòu)建完整的周游路線。

在螞蟻系統(tǒng)(ant system，AS)算法中，初始信息素濃度均等分布，在算法初期階段的螞蟻進行大量盲目搜索，生成諸多無效路徑，導致路徑上信息素濃度更新不準確，削弱信息素指示路徑的啟發(fā)式意義。該問題不僅使算法的初始搜索時間較長，而且由于信息素濃度更新的誤差，導致搜索路徑陷入局部最優(yōu)，影響了算法的性能。受遺忘算法的啟發(fā)，本文在前期降低了遺忘因子的值，首先用蟻群算法尋找次優(yōu)路徑信息，然后增加遺忘因子的值，搜索路徑信息，A是式(5)中的初始測試信息素矩陣

A=τ0*ones(N,N)

(5)

(6)

由式(6)生成初始信息素τij(0)，可實現(xiàn)在算法初期階段對初始信息素濃度的合理控制，有利于蟻群算法在求解TSP問題時避免選擇路徑信息素濃度較高，使算法易于陷入局部最優(yōu)解的能力。避免了蟻群系統(tǒng)中由于信息素過多而在非最優(yōu)路徑上的搜索，以及信息素濃度過低而無法長期搜索的現(xiàn)象。

2.3 改進的狀態(tài)轉(zhuǎn)換策略

(7)

(8)

λ=1-Elp

(9)

式(8)中，Elp表示lp第二次周游得到的最優(yōu)值誤差，相對誤差Elp表示結(jié)果與算法理想值的差異，Elp越小，算法的性能越好。cb表示算法的最佳值，以及c*是理想值。λ∈(0,1]，它來自于式(9)，如果理想的最優(yōu)值一開始是未知的，可以用lN代替c*，如式(10)所示

(10)

2.4 改進的信息素更新策略

由于蟻群算法中的全局更新策略，只更新單周期最優(yōu)路徑上的信息素釋放的濃度，AS算法的全局更新策略只更新螞蟻經(jīng)過的所有路徑，導致路徑上的信息素濃度變化不大，應該合理利用每次迭代產(chǎn)生的最優(yōu)路徑的優(yōu)化效應，將單次迭代產(chǎn)生的最優(yōu)路徑與全局最優(yōu)路徑密切聯(lián)系起來。因此，在FFACO算法中，對信息素更新規(guī)則的改進主要從兩個方面進行：信息素更新和單個螞蟻整個路徑上的全局信息素更新，在全局更新規(guī)則中引入了λ作為遺忘因子，F(xiàn)FACO算法能有效跟蹤不同最優(yōu)解的信息素加成，避免信息素在單個較短路徑上過度沉積，從而導致局部最優(yōu)。

每個螞蟻路徑信息素的更新規(guī)則見式(11)，用最近鄰法構(gòu)造初始路徑并計算τ0，τij即城市i與城市j之間的信息素濃度，為了避免基本蟻群算法中全局信息素更新策略對螞蟻行為的誤導性影響，及時修改了λ的值，以提高現(xiàn)有新信息的有效利用率。

為了增強每條最優(yōu)路徑對每個螞蟻的反饋信息，在傳統(tǒng)螞蟻蟻周模型和精英策略螞蟻系統(tǒng)的基礎(chǔ)上，提出了一種新的全局信息素更新規(guī)則，該規(guī)則能充分利用不同的λ和不同強度的新信息，式(12)是在全局最優(yōu)路徑上增加信息素

τij(t+1)=(1-ρ)·τij(t)+(1-λ)·τ0,λ∈(0,1)

(11)

τij(t+n)=ρ·τij(t)+(1-λ)Δτij(t)+λ(1./Lbest(n+1))

(12)

3 實驗環(huán)境及結(jié)果

3.1 實驗環(huán)境設(shè)置

為分析改進算法的性能，分別將其與模擬退火(simulated annealing，SA)、遺傳算法(genetic algorithm，GA)、粒子群優(yōu)化算法(particle swarm optimization，PSO)和ACO算法對4個不同的TSP實例進行測試：Chn31測試實例和Att48測試實例數(shù)據(jù)集記錄了重要城市的地理坐標信息，St70和Eil76測試實例分別記錄了城市的位置坐標信息。將SA、GA、PSO、ACO和FFACO算法應用到這4個測試實例中，測試實例全部來自TSPLIB庫中，用仿真軟件Matlab7.0進行仿真實驗，運行計算機配置為Intel(R)core(TM)i7-4710 mq CPU@2.50 Ghz 8核，12 G運行內(nèi)存，下面將詳細介紹算法的實現(xiàn)。

3.2 算法參數(shù)配置

(1)模擬退火算法參數(shù)配置

在模擬退火算法的基本版本中，SA的初始溫度為120，終止溫度為1，冷卻系數(shù)為0.99，城市隨機交換應用的算子見表1，所交換的數(shù)字已用粗體顯示，最大迭代次數(shù)為200次。

表1 兩城市隨機交換算子

(2)遺傳算法參數(shù)配置

遺傳算法的種群規(guī)模為100個個體。從每個個體隨機選擇的城市開始，使用最近鄰啟發(fā)式算法生成初始人口。從群體中隨機選擇兩個個體作為親本世代，在突變(pmut=0.80)的情況下，從群體中隨機選擇一個個體，并按相關(guān)概率進行突變操作，重組情況下(prec=0.80)，最大代數(shù)為200。

(3)粒子群優(yōu)化算法參數(shù)配置

粒子群優(yōu)化算法的種群規(guī)模為100個個體，隨機初始化粒子的位置，循環(huán)搜索最優(yōu)路徑。通過計算種群適應度值，更新當前最優(yōu)值和歷史最優(yōu)值，結(jié)合交叉變異操作，當新路徑長度小于歷史最優(yōu)值時，接受更新。在中間種群中每個個體交叉和變異的情況下，設(shè)定進化的最大數(shù)目是200。

(4)ACO算法參數(shù)配置

ACO算法的參數(shù)初始化為α=1,β=2,Q=10,ρ=0.2,m=10和NC=200。最大迭代次數(shù)為200次，m為螞蟻數(shù)，n為本算法中的城市數(shù)，α表示信息素的重要性因子，β表示啟發(fā)式函數(shù)的重要因子，ρ表示信息素殘留系數(shù)。

(5)FFACO算法參數(shù)配置

FFACO算法的參數(shù)初始化為：α=1,β=2,m=10,λ=0.1,ρ=0.1和NC=200。NC是最大迭代次數(shù)為200，α代表信息素的重要因子，β代表啟發(fā)式函數(shù)的重要因子，m是螞蟻數(shù)，λ是遺忘因子，n是TSP問題中的城市數(shù)，ρ代表信息素殘留系數(shù)。

3.3 實驗結(jié)果

通過對TSPLIB的4個數(shù)據(jù)集的時間消耗和全局最優(yōu)解的測試，充分展示了FFACO算法的優(yōu)越性，為了使結(jié)果更具可讀性和更易于比較，對所描述的5種算法(SA、GA、PSO、PSO和FFACO)的研究設(shè)計如下：每種算法對4個公開測試實例分別進行測試，取30次實驗運行結(jié)果記錄其平均解、最優(yōu)解、最差解及其與已知最優(yōu)解的偏差率，4個TSP數(shù)據(jù)集的模擬計算結(jié)果見表2，表3是每個測試實例的已知最佳解決方案(best known solution, BKS)。

表2 實驗計算結(jié)果

表3 基準實例的最優(yōu)解

表2統(tǒng)計各算法的計算結(jié)果，第一列表示各種測試實例，它們按問題規(guī)模的大小按遞增順序列出；第二列表示算法的名稱，其余主列是指平均解、最優(yōu)解、最差解及其偏差率，其中平均解是使用該方法在運行30次后取平均解，最佳和最差解是在使用該方法運行30次結(jié)果中取到的，每次運行只取該算法的前200個進化結(jié)果，對每個算法的計算結(jié)果顯示其真實值和與最優(yōu)值的偏差，表中每個數(shù)據(jù)集的最優(yōu)值結(jié)果以粗體顯示。

對于Chn31測試實例，F(xiàn)FACO的計算結(jié)果非常好，SA、GA、PSO和ACO的平均解偏差和最差偏差都較大，但GA和PSO的最優(yōu)解與FFACO相同(偏差為0.023%)。對于48個城市的TSP實例，F(xiàn)FACO仍然可以找到最接近的最優(yōu)解(dev.0.234%)，而SA、GA、PSO和ACO的最優(yōu)解偏差率遠遠高于FFACO，平均解偏差和最差解偏差也遠高于FFACO。對于70個和76個城市的TSP問題，最優(yōu)解的最佳性能仍然是FFACO(偏差1.001%，偏差0.929%)，比較平均解偏差時，SA、GA、PSO和ACO的平均解偏差高于FFACO。

總體來說，在200次最優(yōu)解進化過程中，F(xiàn)FACO在以上所有測試實例中表現(xiàn)最好。在上表中的12個優(yōu)化結(jié)果中，有11個是FFACO，改進后的算法大大提高了蟻群算法的性能。針對不同問題規(guī)模的TSP實例，SA、GA和PSO都需要大量的迭代來優(yōu)化最優(yōu)路徑，這也是它們性能不如FFACO的主要原因。對于小問題，ACO和FFACO在平均解偏差、最優(yōu)解偏差和最差解偏差上存在顯著差異，隨著問題規(guī)模的增大，ACO和FFACO的結(jié)果變得比其它程序好，ACO的優(yōu)點是每次迭代都能得到更好的結(jié)果，根據(jù)學習到的數(shù)據(jù)生成一個新的解，但FFACO在訓練最優(yōu)值和平均值方面比蟻群算法有更好的性能，計算結(jié)果表明所提出的改進對TSP問題是有效的，并與SA、GA、PSO和ACO進行了比較。

3.4 結(jié)果分析

為增強最優(yōu)解求解能力的對比性，分析本文算法的有效性，對SA、GA、PSO、ACO算法與本文提出的算法進行最優(yōu)解進化軌跡的對比，實驗結(jié)果如圖1～圖4所示。圖1 為5種算法對Chn31測試實例求最優(yōu)解時，最優(yōu)解的進化曲線，圖2為5種算法對Att48測試實例求最優(yōu)解時的最優(yōu)解進化曲線。從以上可知，改進后的算法和ACO算法都能在迭代的初始階段快速逼近最優(yōu)解，而SA、GA、PSO算法明顯落后于二者，且改進后算法在ACO處于停滯狀態(tài)時，依然能對最優(yōu)解實現(xiàn)進一步優(yōu)化，體現(xiàn)其對最優(yōu)解良好的跟蹤能力。圖3為5種算法對St70測試實例求最優(yōu)解時，最優(yōu)解的進化曲線,圖4為5種算法對Eil76測試實例求最優(yōu)解時的進化曲線。其中，由圖4可知，改進后的算法在對Eil76測試實例求解時，能夠快速逼近最優(yōu)解，其它算法最優(yōu)解進化曲線與其差異明顯。

圖1 最優(yōu)解進化軌跡(實例Chn31)

圖2 最優(yōu)解進化軌跡(實例Att48)

圖3 最優(yōu)解進化軌跡(實例St70)

圖4 最優(yōu)解進化軌跡(實例Eil76)

從問題規(guī)模的角度分析，Chn31、Att48、St70、Eil76這4個測試實例問題規(guī)模依次遞增，在有限次的迭代求解中，F(xiàn)FACO和ACO算法有較好的求解能力，但與ACO算法相比，F(xiàn)FACO對不同問題規(guī)模的TSP問題求解有更好的適應性。從解的質(zhì)量來看，所提出的FFACO算法將在每次迭代中更新最優(yōu)解，而不必過多考慮待解問題的大小，整個求解過程相對穩(wěn)定，有效地提高了蟻群算法的性能。

從表4可知，5種算法求解不同測試實例時的最優(yōu)解時間消耗，加粗字體為最優(yōu)值。對不同算法而言，本文提出的FFACO算法求解最優(yōu)解的時間消耗最短，與SA、GA、PSO算法相比，F(xiàn)FACO算法在有限次迭代計算中具有明顯優(yōu)勢，與ACO算法相比，F(xiàn)FACO算法有較好的跳出局部最優(yōu)解的能力，實現(xiàn)對最優(yōu)解的良好跟蹤，進而縮短時間消耗。對于不同的測試實例而言，所需求解的問題規(guī)模依次遞增，各算法求最優(yōu)解的時間也有所增加，但FFACO算法仍然是求最優(yōu)解時最省時間的。

表4 算法求最優(yōu)解的時間消耗

圖5～圖8是本文所提FFACO算法對Chn31、Att48、St70、Eil76測試實例的全局最優(yōu)解路徑規(guī)劃圖，圖中所示的橫坐標、縱坐標均為城市位置坐標的描述。

圖5 全局最優(yōu)解路線(實例Chn31)

圖6 全局最優(yōu)解路線(實例Att48)

圖7 全局最優(yōu)解路線(實例St70)

圖8 全局最優(yōu)解路線(實例Eil76)

綜上所述，本文所提FFACO算法與ACO算法相比有更好的求解能力，對不同問題規(guī)模的TSP問題求解有更好的適應性，與SA、GA、PSO算法相比，顯著節(jié)約了求最優(yōu)解的時間成本。本文所提算法有效改善基本蟻群收斂過程中早熟停滯現(xiàn)象，整個求解過程相對穩(wěn)定且有效地提高蟻群算法的求解質(zhì)量，使改進算法具有較好的魯棒性和收斂性。

4 結(jié)束語

本文提出了一種帶遺忘因子的蟻群算法，提出改進的信息素更新模型，其主要思想是在基本蟻群算法的螞蟻中引入遺忘因子，遺忘因子能及時修正局部信息素的權(quán)重和全局信息素的更新，遺忘因子的調(diào)整能實現(xiàn)對信息素的良好跟蹤效果，改善了基本蟻群算法的停滯行為和收斂性。最后的實驗結(jié)果表明，該算法具有很好的最優(yōu)解尋優(yōu)能力，且時間成本更低。未來的工作將集中在從理論上評估路徑評估模型的有效性。