趙 鑫，楊雄飛，錢育蓉+

(1.新疆大學(xué) 軟件學(xué)院，新疆 烏魯木齊 830046；2.新疆大學(xué) 軟件工程重點(diǎn)實(shí)驗(yàn)室，新疆 烏魯木齊 830046；3.新疆維吾爾自治區(qū) 信號(hào)檢測(cè)與處理重點(diǎn)實(shí)驗(yàn)室，新疆 烏魯木齊 830046)

0 引 言

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

本文研究針對(duì)基本蟻群算法在求解TSP問(wèn)題時(shí)表現(xiàn)的停滯行為和早熟收斂問(wè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)換的時(shí)間成本，最大限度地發(fā)揮了當(dāng)前最優(yōu)解的主導(dǎo)作用，加快了收斂速度，同時(shí)避免局部解的產(chǎn)生。對(duì)TSP的仿真結(jié)果表明，改進(jìn)后的算法通過(guò)變遺忘因子進(jìn)行對(duì)最優(yōu)解的跟蹤，避免了誤差的積累，提高了算法求解的效率。

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

1.1 ACO數(shù)學(xué)模型

TSP問(wèn)題用完全加權(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)一個(gè)正整數(shù)的加權(quán)函數(shù)，TSP的目的是在每個(gè)城市只訪問(wèn)一次時(shí)找到一條最短的路徑。蟻群算法是一種啟發(fā)式算法，用來(lái)模擬真實(shí)蟻群的行為，建立食物源與蟻巢之間的最短路徑[11]。當(dāng)螞蟻尋找食物時(shí)，它會(huì)在自己所經(jīng)過(guò)的路徑上釋放出一種信息素，其它的螞蟻可以被該信息素吸引，而選擇這個(gè)路徑，當(dāng)越來(lái)越多的螞蟻通過(guò)這條路徑時(shí)，會(huì)導(dǎo)致更多的信息素沉積在該路徑上，也會(huì)吸引更多的螞蟻繼續(xù)選擇該路徑。因?yàn)槲浵伕鶕?jù)信息素?cái)?shù)量的多少來(lái)抉擇將要移動(dòng)的路徑，信息素在路徑上的沉積的越多，也就越有可能吸引更多的螞蟻來(lái)選擇該路徑。因此，螞蟻們依據(jù)該原理構(gòu)造出從巢穴到食物來(lái)源并返回的最短路徑，在下面，將提供基本ACO的正式定義。在算法初始階段，隨機(jī)的將每只螞蟻放置在一個(gè)城市位置上，在構(gòu)造可行解的過(guò)程中，每只螞蟻通過(guò)概率決策規(guī)則選擇下一個(gè)將要訪問(wèn)的城市位置，第k只螞蟻由當(dāng)前城市位置，移動(dòng)到下一個(gè)城市位置的概率由式(1)給出，如下所示

(1)

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

(2)

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

(3)

(4)

1.2 ACO算法流程

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

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

(2)螞蟻們根據(jù)式(1)計(jì)算的概率，來(lái)抉擇將要移動(dòng)下一個(gè)節(jié)點(diǎn)的位置，并更新相應(yīng)的tabuk；

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

(4)計(jì)算每條路徑上螞蟻留下的信息素?cái)?shù)量；

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

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

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

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

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

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

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

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

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

A=τ0*ones(N,N)

(5)

(6)

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

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

(7)

(8)

λ=1-Elp

(9)

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

(10)

2.4 改進(jìn)的信息素更新策略

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

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

為了增強(qiáng)每條最優(yōu)路徑對(duì)每個(gè)螞蟻的反饋信息，在傳統(tǒng)螞蟻蟻周模型和精英策略螞蟻系統(tǒng)的基礎(chǔ)上，提出了一種新的全局信息素更新規(guī)則，該規(guī)則能充分利用不同的λ和不同強(qiáng)度的新信息，式(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 實(shí)驗(yàn)環(huán)境及結(jié)果

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

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

3.2 算法參數(shù)配置

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

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

表1 兩城市隨機(jī)交換算子

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

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

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

粒子群優(yōu)化算法的種群規(guī)模為100個(gè)個(gè)體，隨機(jī)初始化粒子的位置，循環(huán)搜索最優(yōu)路徑。通過(guò)計(jì)算種群適應(yīng)度值，更新當(dāng)前最優(yōu)值和歷史最優(yōu)值，結(jié)合交叉變異操作，當(dāng)新路徑長(zhǎng)度小于歷史最優(yōu)值時(shí)，接受更新。在中間種群中每個(gè)個(gè)體交叉和變異的情況下，設(shè)定進(jìn)化的最大數(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問(wèn)題中的城市數(shù)，ρ代表信息素殘留系數(shù)。

3.3 實(shí)驗(yàn)結(jié)果

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

表2 實(shí)驗(yàn)計(jì)算結(jié)果

表3 基準(zhǔn)實(shí)例的最優(yōu)解

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

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

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

3.4 結(jié)果分析

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

圖1 最優(yōu)解進(jìn)化軌跡(實(shí)例Chn31)

圖2 最優(yōu)解進(jìn)化軌跡(實(shí)例Att48)

圖3 最優(yōu)解進(jìn)化軌跡(實(shí)例St70)

圖4 最優(yōu)解進(jìn)化軌跡(實(shí)例Eil76)

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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