改進的蟻群優化算法求解旅行商問題

趙 鑫，楊雄飛，錢育蓉+

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

0 引 言

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

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

1 蟻群優化算法

1.1 ACO數學模型

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

(1)

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

(2)

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

(3)

(4)

1.2 ACO算法流程

ACO算法的具體實現步驟如下：

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

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

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

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

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

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

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

2 改進的蟻群優化算法

2.1 遺忘因子調節策略

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

2.2 初始信息素設置

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

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

A=τ0*ones(N,N)

(5)

(6)

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

2.3 改進的狀態轉換策略

(7)

(8)

λ=1-Elp

(9)

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

(10)

2.4 改進的信息素更新策略

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

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

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

τ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 實驗環境及結果

3.1 實驗環境設置

為分析改進算法的性能，分別將其與模擬退火(simulated annealing，SA)、遺傳算法(genetic algorithm，GA)、粒子群優化算法(particle swarm optimization，PSO)和ACO算法對4個不同的TSP實例進行測試：Chn31測試實例和Att48測試實例數據集記錄了重要城市的地理坐標信息，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運行內存，下面將詳細介紹算法的實現。

3.2 算法參數配置

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

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

表1 兩城市隨機交換算子

(2)遺傳算法參數配置

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

(3)粒子群優化算法參數配置

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

(4)ACO算法參數配置

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

(5)FFACO算法參數配置

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

3.3 實驗結果

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

表2 實驗計算結果

表3 基準實例的最優解

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

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

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

3.4 結果分析

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

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

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

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

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

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

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

表4 算法求最優解的時間消耗

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

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

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

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

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

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

4 結束語

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