趙家波，游曉明+，劉 升

1.上海工程技術(shù)大學(xué) 電子電氣學(xué)院，上海 201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620

旅行商問題（traveling salesman problem，TSP）是一類經(jīng)典的組合優(yōu)化問題，可以描述為一位旅行商從某一城市出發(fā)，要求不重復(fù)通過所有規(guī)定的城市，最后回到最初城市的最短路徑問題。

在20 世紀(jì)90 年代，意大利學(xué)者Dorigo、Maniezzo等人受到自然界螞蟻覓食的啟發(fā)，模擬螞蟻覓食的行為，提出了蟻群算法（ant colony optimization，ACO），并應(yīng)用于旅行商的問題與分布式優(yōu)化問題，取得了較好的結(jié)果。之后學(xué)者們根據(jù)自身研究領(lǐng)域?qū)⑾伻核惴☉?yīng)用于配電網(wǎng)故障定位、火力分配問題、網(wǎng)絡(luò)路由問題、車間調(diào)度問題等。

由于信息素的正反饋?zhàn)饔?，螞蟻系統(tǒng)在后期常常因?yàn)閭€(gè)別路徑信息素的快速積累導(dǎo)致螞蟻不會(huì)選擇其他路徑，從而陷入局部最優(yōu)問題。為了避免信息素的過度積累，減少陷入局部最優(yōu)的概率，Dorigo在螞蟻系統(tǒng)（ant system，AS）算法的基礎(chǔ)上提出蟻群系統(tǒng)（ant colony system，ACS）算法，并提出了全局信息素更新方式與局部信息素更新方式，加入局部搜索算法，改善了算法陷入局部最優(yōu)的情況。之后，為了避免信息素過多而導(dǎo)致陷入局部最優(yōu)，Stutzle 等人提出了最大-最小螞蟻系統(tǒng)（max-min ant system，MMAS），通過分別設(shè)置信息素最大最小閾值，將信息素的濃度控制在一定范圍內(nèi)，從而避免信息素的不斷堆積造成局部最優(yōu)。以上是經(jīng)典的蟻群算法，雖然它們具有高效的探索尋優(yōu)能力，但仍存在著容易陷入局部最優(yōu)、收斂速度慢等問題。針對(duì)這些問題，許多學(xué)者提出各自的改進(jìn)策略。

一些學(xué)者在加快蟻群算法的收斂速度上做出一些改進(jìn)，如文獻(xiàn)[9]結(jié)合遺傳算法，提出使用螞蟻的基因控制螞蟻選擇城市，減少算法初期探索全部路徑的時(shí)間成本，加快算法前期收斂速度。文獻(xiàn)[10]通過全局路徑重新設(shè)定初始信息素分布，使得算法前期路徑的探索具有一定導(dǎo)向性，并且通過信息素的二次揮發(fā)，加快算法后期的收斂能力，使算法能夠在較短時(shí)間內(nèi)找到較優(yōu)解。文獻(xiàn)[11]提出一種改進(jìn)的信息素差異化更新策略，在所有螞蟻完成本次路徑構(gòu)建后，對(duì)優(yōu)于平均路徑長(zhǎng)度的路徑進(jìn)行信息素加強(qiáng)，對(duì)劣于平均路徑長(zhǎng)度的路徑進(jìn)行信息素削弱，從而增大較優(yōu)路徑的吸引力，削弱較差路徑對(duì)螞蟻路徑選擇的干擾，加快算法整體的收斂速度。上述學(xué)者較好地解決了蟻群算法收斂速度慢的問題，但算法仍存在易陷入局部最優(yōu)的問題。文獻(xiàn)[12]提出一種具有記憶特征的區(qū)間蟻群優(yōu)化算法，將信息素濃度推廣為一定區(qū)間范圍，不再束縛于信息素為某一定值，并引入長(zhǎng)短時(shí)記憶的信息素更新方式，對(duì)應(yīng)不同的揮發(fā)系數(shù)，使得算法呈現(xiàn)更具層次的多樣性。文獻(xiàn)[13]為了解決算法陷入局部最優(yōu)的問題，使用平滑信息素的方法削弱所有路徑信息素的差異性，并通過自適應(yīng)改變算法的取值,增大算法接受隨機(jī)解的概率，從而實(shí)現(xiàn)跳出局部最優(yōu)。文獻(xiàn)[14]根據(jù)蟻群算法與魚群算法的優(yōu)勢(shì)互補(bǔ)，提出一種先魚群再蟻群的混合算法，通過更新率的調(diào)整，前期借助魚群算法找到更多的解，當(dāng)更新率達(dá)到某一值時(shí)，轉(zhuǎn)為蟻群算法進(jìn)行更好的尋優(yōu)，當(dāng)算法陷入局部最優(yōu)時(shí)，再通過更新率的變化轉(zhuǎn)為魚群算法，從而平衡收斂速度慢、易陷入局部最優(yōu)等問題。雖然以上改進(jìn)的蟻群算法都從加快收斂速度與提高多樣性進(jìn)行改善，但在解決中大規(guī)模的TSP 問題中仍然存在收斂速度慢且容易陷入局部最優(yōu)等問題。

為了在中大規(guī)模TSP 問題中較好地平衡解的多樣性與收斂速度的關(guān)系，本文提出一種結(jié)合價(jià)格波動(dòng)策略與動(dòng)態(tài)回溯的蟻群算法（ant colony algorithm based on price fluctuation strategy and dynamic backtracking mechanism，PBACO）。在價(jià)格波動(dòng)策略中，結(jié)合時(shí)間序列思想將蟻群算法完整迭代周期根據(jù)不同需求分為三類，并根據(jù)價(jià)格波動(dòng)平衡，將影響價(jià)格波動(dòng)的供求關(guān)系進(jìn)行匹配，通過分析算法在各類時(shí)期的不同需求，對(duì)信息素?fù)]發(fā)因子進(jìn)行自適應(yīng)動(dòng)態(tài)供給，來滿足算法各階段的動(dòng)態(tài)需求，較好地改善算法整體性能。當(dāng)價(jià)格波動(dòng)策略的供給關(guān)系無法實(shí)現(xiàn)平衡時(shí)，算法將面臨局部最優(yōu)問題，此時(shí)引入動(dòng)態(tài)回溯機(jī)制，以迭代最優(yōu)螞蟻的個(gè)體相似度作為標(biāo)準(zhǔn)，將路徑信息素回溯至相似度差異顯著的時(shí)期，而非將路徑信息素清零，保證了算法收斂速度的同時(shí)能夠有效跳出局部最優(yōu)。通過MATLAB 對(duì)TSP 中的不同測(cè)試集進(jìn)行仿真，結(jié)果表明該算法在保證收斂速度的基礎(chǔ)上，有效提高了解的質(zhì)量，較好地平衡了多樣性與收斂速度的關(guān)系。本文的主要工作總結(jié)如下：

（1）結(jié)合時(shí)間序列的思想，將蟻群算法完整迭代周期根據(jù)不同內(nèi)在需求分為A、B、C 三類，并采用價(jià)格波動(dòng)策略對(duì)三類不同時(shí)期的不同需求，自適應(yīng)調(diào)整信息素?fù)]發(fā)因子進(jìn)行動(dòng)態(tài)供給，使算法能夠在不同時(shí)期對(duì)多樣性差與收斂速度慢的問題做出相應(yīng)的改善，優(yōu)于傳統(tǒng)算法恒定的信息素?fù)]發(fā)因子。

（2）通過分析三類不同時(shí)期的陷入局部最優(yōu)情況，引入斐波那契數(shù)列抽樣來判定算法是否陷入局部最優(yōu)，而非傳統(tǒng)算法逐個(gè)判斷若干代最短路徑均不變的方法。采用斐波那契數(shù)列抽樣的方式通過抽樣更少樣本數(shù)來判定陷入局部最優(yōu)，節(jié)約時(shí)間成本，同時(shí)對(duì)不同時(shí)期采用不同的最大樣本數(shù)，更為合理地進(jìn)行抽樣樣本數(shù)的調(diào)整，進(jìn)一步加快算法收斂速度。

（3）在算法陷入局部最優(yōu)后，最優(yōu)路徑信息素積累較多，此時(shí)引入動(dòng)態(tài)回溯機(jī)制，以迭代最優(yōu)螞蟻的個(gè)體相似度作為標(biāo)準(zhǔn)，將路徑信息素回溯至相似度差異顯著的時(shí)期，可以將路徑信息素重置為若干代前的路徑信息素，這樣既增加了下代螞蟻選擇路徑的多樣性，同時(shí)未完全重置信息素，節(jié)省了螞蟻重新構(gòu)建路徑信息素的時(shí)間成本，在保證收斂速度的同時(shí)能夠有效跳出局部最優(yōu)。

1 相關(guān)工作

1.1 ACS 蟻群算法1.1.1 路徑構(gòu)建

ACS 中每只螞蟻從城市到城市的選擇公式：

其中，τ()代表著時(shí)刻城市和城市之間的信息素的濃度大小，每條邊上的起始濃度都是相同的，記為。 η代表的是、城市之間距離d的倒數(shù)，即η=1/d。是在區(qū)間[0,1]的常數(shù)值，是在區(qū)間[0,1]的隨機(jī)數(shù)，∈表示城市屬于禁忌表外的可選城市集合。表示當(dāng)≤時(shí)將要被選擇的下一個(gè)城市。是式（2）輪盤賭的選擇方式。、分別表示信息啟發(fā)式因子和期望啟發(fā)式因子，越大，表示對(duì)下一條路徑選擇受啟發(fā)式信息素的影響越大，而值越大，表示對(duì)下一條路徑選擇受城市間距離的影響越大。

式（1）、式（2）表明，當(dāng)≤時(shí)，城市之間信息素高的城市和距離相對(duì)近的城市被選擇的概率更大，當(dāng)不符合上述條件，采用式（2）輪盤賭進(jìn)行路徑構(gòu)建。

ACS 蟻群算法的更新機(jī)制分為局部信息素更新和全局信息素更新兩部分。

全局信息素更新：當(dāng)所有螞蟻都完成一次迭代之后，算法只對(duì)當(dāng)前最優(yōu)路徑上的信息素進(jìn)行更新，通過算法的正反饋?zhàn)饔茫沟米顑?yōu)路徑和非最優(yōu)路徑上的信息素的差距逐漸拉大，為蟻群的路徑選擇增加指向性，加快了算法的收斂速度。公式如下：

其中，是全局信息素的蒸發(fā)率；Δτ是信息素增量；是當(dāng)前最優(yōu)路徑長(zhǎng)度。

局部信息素更新：當(dāng)每只螞蟻完成一次周游后，算法便會(huì)對(duì)其走過的路徑進(jìn)行局部信息素更新。局部信息素更新是對(duì)所有螞蟻都進(jìn)行更新，其作用是為了縮短最優(yōu)路徑和非最優(yōu)路徑之間信息素的差距，增加算法的多樣性，提高算法全局搜索能力，避免陷入局部最優(yōu)。公式如下：

其中，Δτ是信息素增量；為每條邊上的起始濃度；是局部信息素的蒸發(fā)率。

1.2 時(shí)間序列分析法

時(shí)間序列分析法是統(tǒng)計(jì)學(xué)中常用于預(yù)測(cè)未來發(fā)展變化趨勢(shì)的一種方法，能夠以時(shí)間的推移預(yù)測(cè)市場(chǎng)需求趨勢(shì)，通過將經(jīng)濟(jì)跌漲、購(gòu)買力大小、價(jià)格變動(dòng)等同一常數(shù)的觀察值，按照時(shí)間順序進(jìn)行排列，再運(yùn)用數(shù)理統(tǒng)計(jì)方法對(duì)市場(chǎng)未來趨勢(shì)的變化進(jìn)行預(yù)測(cè)，來確定市場(chǎng)的預(yù)測(cè)值。

一個(gè)時(shí)間序列通常由四種要素組成：長(zhǎng)期趨勢(shì)變動(dòng)、季節(jié)變動(dòng)、循環(huán)變動(dòng)和不規(guī)則變動(dòng)。長(zhǎng)期趨勢(shì)變動(dòng)是指時(shí)間序列在長(zhǎng)時(shí)期內(nèi)呈現(xiàn)出來的持續(xù)向上或持續(xù)向下的變動(dòng)；季節(jié)變動(dòng)是指時(shí)間序列在隨季節(jié)而重復(fù)出現(xiàn)的周期性波動(dòng)，受氣候條件、節(jié)假日等各種因素的影響；循環(huán)變動(dòng)是指時(shí)間序列變化為非固定時(shí)長(zhǎng)的周期性波動(dòng)，其循環(huán)周期與趨勢(shì)不同，它并非是單一方向的長(zhǎng)時(shí)變化，而是漲落有序的交替波動(dòng)；不規(guī)則變動(dòng)是指時(shí)間序列中除去以上三種要素所剩余的變動(dòng)，通常隨機(jī)出現(xiàn)在時(shí)間序列中，使時(shí)間序列產(chǎn)生不平穩(wěn)的震蕩波動(dòng)。

時(shí)間序列函數(shù)可由以上四種元素進(jìn)行表示，即=(,,,)，常用所構(gòu)建的模型可分為兩種，加法模型=+++以及乘法模型=***。當(dāng)時(shí)間序列隨時(shí)間等寬推進(jìn)時(shí)，常用加法模型；當(dāng)時(shí)間序列的季節(jié)變動(dòng)與長(zhǎng)期趨勢(shì)變動(dòng)成正比時(shí)，常用乘法模型。

1.3 個(gè)體相似度

在相似度算法的距離度量中，距離越近則兩者差異性較小，證明其相似度越高。但是這類相似度無法直接應(yīng)用于蟻群算法中，因?yàn)楫?dāng)蟻群算法陷入局部最優(yōu)時(shí)，其最優(yōu)路徑基本保持不變，前后兩次路徑的差異性較小，相似度高，但是對(duì)于需要跳出局部最優(yōu)的問題并非一個(gè)好的結(jié)果。

考慮到螞蟻個(gè)體在尋找路徑時(shí)是通過城市節(jié)點(diǎn)的連接來進(jìn)行路徑尋優(yōu)，個(gè)體之間形成的閉環(huán)路徑總會(huì)有一些相同路徑，因此可用個(gè)體間的相同路徑信息來表示個(gè)體之間的相似度，路徑信息相同數(shù)越多，則代表個(gè)體間的相似度越高，而相同數(shù)越少，也表示個(gè)體間差異性較為明顯。個(gè)體相似度的計(jì)算過程如下所示。

個(gè)體相似度的計(jì)算通過相同路徑的多少來進(jìn)行，設(shè)兩個(gè)個(gè)體和，其路徑信息借助連接矩陣表示，如對(duì)應(yīng)連接矩陣，對(duì)應(yīng)連接矩陣，則有：

其中，代表城市數(shù)，在矩陣中，x表示城市至城市的路徑信息，如果個(gè)體的路徑信息中具有城市至城市，則使x=1，否則x=0；因?yàn)?span id="syggg00" class="emphasis_italic">x與x均表示城市至城市的路徑信息，所以x=x，為對(duì)稱矩陣，個(gè)體的連接矩陣同理所示。

個(gè)體相似度借助連接矩陣則可以較為明顯地比較兩個(gè)個(gè)體的路徑信息。在算法運(yùn)行初期，從隨機(jī)城市出發(fā)的兩個(gè)螞蟻個(gè)體可能走過完全不同的路徑，此時(shí)兩者的相似度應(yīng)為0，在算法陷入局部最優(yōu)或算法運(yùn)行末期，因?yàn)樾畔⑺卣答伒淖饔茫瑑蓚€(gè)螞蟻個(gè)體走過的路徑可能大體相同，此時(shí)兩者的相似度為1 或近似為1，所以可構(gòu)建個(gè)體相似度函數(shù)，將兩個(gè)個(gè)體的相同路徑進(jìn)行統(tǒng)計(jì)處理，使個(gè)體間的相似度處于0～1 的范圍。個(gè)體相似度函數(shù)的公式如下所示：

2 改進(jìn)的蟻群算法

2.1 價(jià)格波動(dòng)策略

價(jià)格波動(dòng)策略結(jié)合了價(jià)格理論中商品的供求關(guān)系對(duì)價(jià)格的影響，在不同時(shí)期商品的價(jià)格會(huì)受供給和需求的不同而產(chǎn)生變化，但總體價(jià)格呈現(xiàn)出波動(dòng)平衡的狀態(tài)。而傳統(tǒng)蟻群算法在進(jìn)行路徑探索時(shí)，存在易陷入局部最優(yōu)、收斂速度慢等問題，雖然后續(xù)提出信息素?fù)]發(fā)因子來避免信息素過度積累，改善解的質(zhì)量，但傳統(tǒng)蟻群算法的信息素?fù)]發(fā)因子仍具有一定的局限性，信息素?fù)]發(fā)因子作為蟻群算法的重要參數(shù)，設(shè)置為某一定值無法發(fā)揮其在算法各階段的不同作用，對(duì)算法整體的適應(yīng)性較差，因此提出價(jià)格波動(dòng)策略，使算法不同時(shí)期的供求關(guān)系處于動(dòng)態(tài)平衡狀態(tài)。

時(shí)間序列分析法處理的數(shù)據(jù)通常是根據(jù)時(shí)間排列的數(shù)據(jù)，用來進(jìn)行曲線的預(yù)測(cè)與內(nèi)在發(fā)展趨勢(shì)的變化，本文通過將時(shí)間序列思想引入蟻群算法，對(duì)蟻群算法各時(shí)期的不同狀態(tài)進(jìn)行分析分類，為2.1.2 小節(jié)價(jià)格波動(dòng)策略的供求關(guān)系匹配奠定基礎(chǔ)。

下面將通過分析最短路徑收斂圖來對(duì)蟻群算法各時(shí)期的不同狀態(tài)進(jìn)行分類，為了提高此分類方法的普適性，本文根據(jù)文獻(xiàn)[7]的ACS 算法，對(duì)城市集eil51、eil76、KroA100、KroB100、ch130、ch150、KroA200 和KroB200 進(jìn)行15 次獨(dú)立實(shí)驗(yàn)，獲取各城市集的最短路徑收斂圖。為了增強(qiáng)說服力，選取各城市集15 次實(shí)驗(yàn)中的最優(yōu)路徑收斂圖作為典型進(jìn)行分析。

如圖1 所示，蟻群算法的收斂曲線是以迭代數(shù)為時(shí)間軸，對(duì)本次迭代最優(yōu)螞蟻的最短距離進(jìn)行統(tǒng)計(jì)，從而繪制成的曲線，因此曲線不會(huì)出現(xiàn)往上回升的變化，只存在下降與持平的情況?？紤]到以上原因在蟻群算法的特殊性，蟻群算法最短路徑的變化曲線在結(jié)合時(shí)間序列思想時(shí)會(huì)對(duì)曲線的要素做出相應(yīng)調(diào)整，構(gòu)建符合蟻群算法邏輯的模型。

圖1 最短路徑收斂圖Fig.1 Shortest path convergence graph

圖1 將根據(jù)算法不同時(shí)期的不同變化對(duì)對(duì)應(yīng)時(shí)期的曲線進(jìn)行要素分類。在圖1 中，各城市集的最短路徑曲線都可分為A、B 和C 三個(gè)階段。在A 階段，各城市集曲線呈極速下降趨勢(shì)，階段特征為曲線在較少迭代數(shù)內(nèi)落差明顯，此時(shí)處于算法前期，螞蟻主要受期望啟發(fā)式的影響積極探索路徑，稱之為極速下降變化；在B 階段，各城市集曲線呈階梯下降趨勢(shì)，階段特征為曲線在持平較短迭代數(shù)后發(fā)生下降變化，之后再次持平與下降，循環(huán)進(jìn)行，此時(shí)處于算法前中期，路徑信息素積累至一定程度，螞蟻的路徑選擇受啟發(fā)式與信息素濃度的共同作用，波折探索更短路徑，稱之為階梯下降變化；在C 階段，各城市集曲線呈長(zhǎng)期持平或長(zhǎng)期持平后下降趨勢(shì)，階段特征為曲線在較長(zhǎng)迭代數(shù)內(nèi)持平，或在較長(zhǎng)迭代數(shù)內(nèi)持平后出現(xiàn)下降，此時(shí)處于算法中后期，信息素的正反饋積累使當(dāng)前最優(yōu)路徑的信息素達(dá)到較大值，陷入局部最優(yōu)，算法只能通過輪盤賭的小概率來尋找更短路徑，因此曲線在較長(zhǎng)迭代數(shù)保持持平，若能找出更短路徑，即出現(xiàn)下降現(xiàn)象，稱之為恒定兼隨機(jī)變化。

因?yàn)樽顑?yōu)路徑曲線是以每代進(jìn)行統(tǒng)計(jì)，以上四種分類滿足時(shí)間序列加法模型，所以可以構(gòu)建價(jià)格波動(dòng)策略分類模型，如式（9）所示。

其中，為最短路徑收斂曲線中的極速下降變化，為極速下降的時(shí)長(zhǎng)，該時(shí)段算法多樣性較好，容易找出更優(yōu)解；為最短路徑收斂曲線中的階梯下降變化，為階梯下降的時(shí)長(zhǎng)，該時(shí)段信息啟發(fā)式與期望啟發(fā)式共同作用，算法多樣性逐漸降低，開始陷入局部最優(yōu)，又跳出局部最優(yōu)的階段；為恒定兼隨機(jī)變化，為恒定兼隨機(jī)變化的時(shí)長(zhǎng)，該時(shí)期算法的多樣性較低，已經(jīng)陷入局部最優(yōu)問題，若能跳出局部最優(yōu)，則為隨機(jī)變化，若未能跳出局部最優(yōu)，則為長(zhǎng)期恒定變化；為完整收斂曲線，為各階段時(shí)長(zhǎng)的總和。

上述通過結(jié)合時(shí)間序列的思想，分析了蟻群算法最短路徑的變化曲線，將蟻群算法迭代周期分為三種階段時(shí)期，在不同時(shí)期算法具有不同的需求，而當(dāng)信息素?fù)]發(fā)算子設(shè)置為定值時(shí)，無法動(dòng)態(tài)調(diào)整信息素在各個(gè)階段發(fā)揮不同的作用，對(duì)算法整體的適應(yīng)性較差。因此本文提出一種價(jià)格波動(dòng)策略，將影響價(jià)格波動(dòng)的供求關(guān)系進(jìn)行匹配，對(duì)信息素?fù)]發(fā)因子進(jìn)行動(dòng)態(tài)調(diào)整，用于全局信息素更新公式中，來平衡算法各階段不同時(shí)期的需求。

在算法運(yùn)行前期，即A 階段，最優(yōu)路徑曲線處于極速下降變化階段，此時(shí)路徑信息素積累量較少，此時(shí)若將信息素?fù)]發(fā)因子設(shè)定為較大值，雖然會(huì)削弱正反饋的作用，但此時(shí)算法會(huì)將期望啟發(fā)式因子作為主導(dǎo)地位，從而使螞蟻容易聚集在期望啟發(fā)式因子最強(qiáng)的路徑，變?yōu)轭愗澬乃惴ǎ菀紫萑刖植孔顑?yōu)；而將信息素?fù)]發(fā)算子設(shè)為較小值時(shí)，有助于加快算法前期的收斂速度，因此在算法前期設(shè)置信息素?fù)]發(fā)因子為較小值。在算法運(yùn)行前中期，即B 階段，最優(yōu)路徑曲線呈階梯下降階段，路徑信息素積累較為密集，易陷入局部最優(yōu)，此時(shí)采用較大值的信息素?fù)]發(fā)因子，來平衡最優(yōu)路徑與其他路徑的差異性，使螞蟻選擇其他路徑的可能性增大，從而增加探索更優(yōu)解的概率。在算法運(yùn)行中后期，即C 階段，最優(yōu)路徑曲線呈恒定兼隨機(jī)變化，算法跳出局部最優(yōu)能力較弱，并在當(dāng)前最優(yōu)解上浪費(fèi)了大量時(shí)間成本，因此此時(shí)應(yīng)適當(dāng)增加算法的收斂速度，應(yīng)減小信息素?fù)]發(fā)因子，以實(shí)現(xiàn)算法后期的快速收斂。

綜合上述分析，并結(jié)合MMAS 的范圍限制思想，本文構(gòu)建一種服從高斯分布的自適應(yīng)信息素?fù)]發(fā)因子。

圖2 全局信息素?fù)]發(fā)因子Fig.2 Global pheromone volatilization factor

由圖2 可知，在算法前期的A 階段，服從高斯分布的自適應(yīng)信息素?fù)]發(fā)因子將處于較小值，滿足算法前期信息素?fù)]發(fā)因子較小的需求；當(dāng)算法運(yùn)行至中前期的B 階段，此時(shí)算法路徑信息素積累逐漸密集，且隨迭代數(shù)的增加與解的精度的提高，算法陷入局部最優(yōu)后再跳出局部最優(yōu)的能力逐漸減弱，此時(shí)需要信息素?fù)]發(fā)因子也隨之增加，而服從高斯分布的自適應(yīng)信息素?fù)]發(fā)因子隨迭代數(shù)增加而增加，滿足此階段的需求；在算法中后期的C 階段，最優(yōu)路徑信息素的積累達(dá)到較大值，隨迭代數(shù)的增加與信息素的積累，算法跳出局部最優(yōu)的概率逐漸降低，此時(shí)算法會(huì)在當(dāng)前最優(yōu)解上浪費(fèi)大量的時(shí)間成本，此時(shí)服從高斯分布的信息素?fù)]發(fā)因子隨迭代數(shù)逐步減小，提升算法后期的收斂速度，滿足此階段的需求。

服從高斯分布的自適應(yīng)信息素?fù)]發(fā)因子公式如下所示：

全局信息素更新公式為：

其中，是位置參數(shù)，這里設(shè)定為1 000；＞0 是尺度參數(shù)；是調(diào)整倍數(shù)。通過調(diào)整和的值，使信息素?fù)]發(fā)因子范圍保持在圖中各分布區(qū)間，對(duì)于具體參數(shù)選擇，在后續(xù)實(shí)驗(yàn)中會(huì)進(jìn)行分析對(duì)比，選出一組相對(duì)較好的參數(shù)。

2.2 動(dòng)態(tài)回溯機(jī)制

動(dòng)態(tài)回溯思想受中值法與最優(yōu)化估計(jì)算法啟發(fā)，在進(jìn)行優(yōu)化計(jì)算時(shí)通過取區(qū)間中值來對(duì)最優(yōu)解不斷逼近，當(dāng)一次中值法結(jié)束，對(duì)最優(yōu)解存在區(qū)間再次進(jìn)行中值法，循環(huán)往復(fù)直至逼近最優(yōu)解或得到最優(yōu)解。而在蟻群算法中，常常會(huì)遇到陷入局部最優(yōu)的問題，導(dǎo)致算法在較優(yōu)解而非最優(yōu)解浪費(fèi)大量時(shí)間成本，并且解的精度提升較小，因此提出一種動(dòng)態(tài)回溯機(jī)制來實(shí)現(xiàn)跳出局部最優(yōu)，改善解的質(zhì)量。信息素是蟻群算法的核心因素，螞蟻通過信息素的積累來進(jìn)行下一個(gè)城市的選擇，而動(dòng)態(tài)回溯機(jī)制正是通過將路徑信息素回溯至個(gè)體相似度差異顯著的時(shí)期，此時(shí)在未完全陷入局部最優(yōu)的同時(shí)，保留路徑信息素的完整性，區(qū)別于將信息素初始化的大災(zāi)變，節(jié)省時(shí)間成本，并能有效地跳出局部最優(yōu)。

動(dòng)態(tài)回溯的核心在于將信息素重置為較優(yōu)迭代時(shí)刻，在判斷重置為哪些較優(yōu)迭代時(shí)刻的選擇問題上，本文借助個(gè)體相似度作為標(biāo)準(zhǔn)，來判斷信息素較好的較優(yōu)時(shí)刻，從而進(jìn)行動(dòng)態(tài)回溯。

該機(jī)制首先要對(duì)是否陷入局部最優(yōu)進(jìn)行判斷，傳統(tǒng)判斷局部最優(yōu)方式為若干代的至今最短路徑是否均相等，此類判斷方法需要在每次迭代結(jié)束后將最優(yōu)路徑與若干代前每一代的最優(yōu)路徑進(jìn)行對(duì)比，浪費(fèi)了時(shí)間成本。本文借助斐波那契數(shù)列來對(duì)陷入局部最優(yōu)進(jìn)行判定，通過斐波那契數(shù)列的抽樣方式，結(jié)合價(jià)格波動(dòng)策略不同階段時(shí)期的特殊情況，對(duì)算法是否陷入局部最優(yōu)進(jìn)行判定，在算法前期的A 階段，算法基本不會(huì)出現(xiàn)陷入局部最優(yōu)的情況；在算法前中期的B 階段，算法會(huì)在陷入局部持續(xù)較短迭代數(shù)，再跳出局部，此時(shí)斐波那契數(shù)列抽樣的最大樣本數(shù)會(huì)相應(yīng)減小；在算法中后期的C 階段，算法會(huì)陷入局部最優(yōu)，并持續(xù)較長(zhǎng)迭代數(shù)，此時(shí)斐波那契數(shù)列抽樣的最大樣本數(shù)會(huì)相應(yīng)增加。如圖3 所示，對(duì)比傳統(tǒng)局部最優(yōu)判定方式，假設(shè)樣本迭代數(shù)為50 代，即連續(xù)50 代的最短路徑均相等，最短路徑不發(fā)生變化時(shí)，判定算法陷入局部最優(yōu)；而斐波那契數(shù)列抽樣的方式，在算法前中期設(shè)置最大樣本數(shù)為30，即可通過抽樣第1、2、3、5、8、13 和21 這7 組迭代樣本的最短路徑進(jìn)行比較，從而判定算法是否陷入局部最優(yōu)。在算法中后期適當(dāng)提高最大樣本數(shù)，設(shè)置最大樣本數(shù)為50，抽樣方式同理。隨著斐波那契數(shù)列的遞進(jìn)，樣本抽樣跨度顯著提高，可以省去檢測(cè)大量重復(fù)樣本的時(shí)間。采用斐波那契數(shù)列抽樣進(jìn)行局部最優(yōu)的判定，其優(yōu)點(diǎn)在于能通過抽樣的方式快捷合理地判斷是否陷入局部最優(yōu)，節(jié)約時(shí)間成本，并結(jié)合動(dòng)態(tài)回溯機(jī)制實(shí)現(xiàn)跳出局部最優(yōu)，使算法解的精度得到較好的提升。

圖3 斐波那契數(shù)列抽樣對(duì)比圖Fig.3 Comparison chart of Fibonacci sequence sampling

在算法運(yùn)行時(shí)，若出現(xiàn)下一代最優(yōu)路徑與至今最優(yōu)路徑相等，則調(diào)用斐波那契數(shù)列函數(shù)進(jìn)行判定，設(shè)定當(dāng)前代斐波那契數(shù)為1，下一代斐波那契數(shù)為2，校驗(yàn)后續(xù)滿足斐波那契數(shù)列代數(shù)的最優(yōu)路徑，若經(jīng)過斐波那契數(shù)列抽樣后的最優(yōu)路徑都相等，則判定算法陷入局部最優(yōu)。斐波那契抽樣函數(shù)公式如下：

其中，為抽樣時(shí)刻；=1 為采樣周期；()為斐波那契函數(shù)；為整數(shù)。

若抽樣得到的最短路徑均相等，則判定算法陷入局部最優(yōu)，此時(shí)對(duì)下一代螞蟻的路徑信息素進(jìn)行回溯，通過式（14）相似度判別公式作為判定條件，回溯到滿足此條件且距離當(dāng)前迭代數(shù)最近的較優(yōu)代，根據(jù)式（15）重置其信息素，使其信息素回溯至若干代前個(gè)體相似度差異顯著的時(shí)期，借助此時(shí)跳出局部最優(yōu)能力更強(qiáng)的信息素重新進(jìn)行路徑尋優(yōu)，迭代代，若仍未跳出局部最優(yōu)則再次使用式（14），找出滿足條件的下一個(gè)較優(yōu)代，再次進(jìn)行信息素回溯，以此循環(huán)直至跳出局部最優(yōu)或達(dá)到迭代最大代數(shù)，動(dòng)態(tài)回溯示意圖與動(dòng)態(tài)回溯機(jī)制流程圖如圖4、圖5 所示。

其中，為個(gè)體相似度判定算子，為0 至1 的某一常數(shù)?？紤]到取1 時(shí)，等同于將信息素重置為與至今最優(yōu)路徑相同的路徑信息素，并不一定能實(shí)現(xiàn)跳出局部最優(yōu)。為滿足相似度判別公式時(shí)的迭代數(shù)。為信息素回溯后的迭代數(shù)，與成正比，當(dāng)個(gè)體相似度高時(shí)，回溯的較優(yōu)代與此時(shí)代數(shù)相差步長(zhǎng)較小，陷入局部最優(yōu)嚴(yán)重，需要迭代時(shí)間加長(zhǎng)；反之當(dāng)個(gè)體相似度低時(shí)，回溯的較優(yōu)代與此時(shí)代數(shù)相差較大，信息素差異明顯，此時(shí)迭代時(shí)間適當(dāng)縮小。

圖4 動(dòng)態(tài)回溯示意圖Fig.4 Dynamic backtracking diagram

圖5 動(dòng)態(tài)回溯機(jī)制流程圖Fig.5 Flow chart of dynamic backtracking mechanism

當(dāng)價(jià)格波動(dòng)策略難以通過自適應(yīng)調(diào)整信息素?fù)]發(fā)因子來滿足算法的需求時(shí)，算法陷入局部最優(yōu)問題，此時(shí)將會(huì)啟用動(dòng)態(tài)回溯機(jī)制，使跳出局部最優(yōu)成為算法的首要任務(wù)，通過式（17）強(qiáng)制提升信息素?fù)]發(fā)因子，使其達(dá)到最大值，來更好地解決跳出局部最優(yōu)問題。

其中，為價(jià)格波動(dòng)策略的最大揮發(fā)因子值，當(dāng)(,)≤時(shí)，算法已經(jīng)陷入局部最優(yōu)，強(qiáng)制全局信息素?fù)]發(fā)因子調(diào)整為最大值。

2.3 算法流程

初始化參數(shù)，=0。

將只螞蟻隨機(jī)分配到各個(gè)節(jié)點(diǎn)。

根據(jù)ACS 算法進(jìn)行迭代，根據(jù)式（10）自適應(yīng)調(diào)整信息素?fù)]發(fā)因子，將式（11）作為全局最優(yōu)更新公式進(jìn)行信息素更新。

若發(fā)現(xiàn)相鄰兩代最優(yōu)路徑的距離相同，調(diào)用斐波那契函數(shù)進(jìn)行抽樣，若抽樣后的最優(yōu)路徑距離不全部相同，則跳回步驟3；若抽樣后的最優(yōu)路徑距離完全相同，則跳到步驟5。

當(dāng)算法陷入局部最優(yōu)時(shí)，根據(jù)式（14）進(jìn)行動(dòng)態(tài)回溯，匹配滿足個(gè)體相似度算子的迭代數(shù)，記錄至今最優(yōu)路徑，根據(jù)式（15）將對(duì)應(yīng)的信息素賦予下一代。

以重置后的信息素進(jìn)行次迭代，若迭代數(shù)達(dá)到最大迭代時(shí)，則找到并輸出最優(yōu)解；若未達(dá)到時(shí)，則對(duì)比當(dāng)前最優(yōu)路徑與至今最優(yōu)路徑，若當(dāng)前最優(yōu)路徑小于至今最優(yōu)路徑，則跳出局部最優(yōu)，跳至步驟7；若不小于至今最優(yōu)路徑，則取滿足式（14）的下一個(gè)最近迭代數(shù)時(shí)的信息素回溯，跳回步驟6。

重復(fù)上述步驟2～6，直至迭代次，找到并輸出最優(yōu)解。

2.4 算法復(fù)雜度分析

雖然本文通過回溯信息素濃度的方式實(shí)現(xiàn)跳出局部最優(yōu)，但并未對(duì)迭代總數(shù)進(jìn)行改變。從上述算法流程的分析可以看出，本文算法總的迭代數(shù)為，假設(shè)算法在第1 代陷入局部最優(yōu)，動(dòng)態(tài)回溯機(jī)制會(huì)將若干代前滿足相似度標(biāo)準(zhǔn)的該代信息素賦予1代，并運(yùn)行1 代，若無法跳出局部最優(yōu)則繼續(xù)向前尋找滿足相似度標(biāo)準(zhǔn)的信息素，賦予第(1+1)代。以此循環(huán)，假設(shè)迭代數(shù)達(dá)到代也未能跳出局部最優(yōu)，則運(yùn)行總代數(shù)為(1+1+2+…+)代，其中=1+1+2+…+；若假設(shè)在運(yùn)行代時(shí)實(shí)現(xiàn)跳出局部最優(yōu)，則當(dāng)前運(yùn)行代數(shù)為(1+1+2+…+)，隨后運(yùn)行-(1+1+2+…+)代。綜上所述，算法迭代總數(shù)仍為，螞蟻的數(shù)量是，城市數(shù)為，在每次迭代時(shí)因?yàn)榻杀淼氖褂茫恐晃浵佒荒芩褜こ陨沓跏汲鞘型獾某鞘?，?1 個(gè)城市，因此算法的時(shí)間復(fù)雜度為(××(-1))即(××)，與傳統(tǒng)ACS 算法的時(shí)間復(fù)雜度相同。

3 實(shí)驗(yàn)對(duì)比與結(jié)果分析

為檢驗(yàn)PBACO 的算法性能，本文實(shí)驗(yàn)使用Windows10 系統(tǒng)，MATLAB2016a 版本的仿真環(huán)境，選取國(guó)際標(biāo)準(zhǔn)TSP 數(shù)據(jù)庫的多組數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。

3.1 節(jié)將進(jìn)行公共參數(shù)、價(jià)格波動(dòng)策略與動(dòng)態(tài)回溯機(jī)制的參數(shù)設(shè)置。首先引用文獻(xiàn)[7]的公共參數(shù)，為了檢驗(yàn)后續(xù)參數(shù)的性能，采用控制變量法，后續(xù)全部實(shí)驗(yàn)將在統(tǒng)一的公共參數(shù)上進(jìn)行。在設(shè)置價(jià)格波動(dòng)策略參數(shù)中，以KroA100 作為數(shù)據(jù)集，將圖1 中動(dòng)態(tài)揮發(fā)因子的九組不同區(qū)間參數(shù)，與全局信息素?fù)]發(fā)因子為恒定值0.3 時(shí)的算法作對(duì)比，通過比較30 次獨(dú)立實(shí)驗(yàn)中的最小誤差率、滿足誤差率在0.5%的比例和平均解，來分析揮發(fā)因子的動(dòng)態(tài)調(diào)整所改善的性能；同時(shí)挑出幾組較優(yōu)的區(qū)間參數(shù)，在A200 數(shù)據(jù)集上進(jìn)行30 次獨(dú)立實(shí)驗(yàn)，再次與恒值為0.3 時(shí)的算法作對(duì)比，通過分析對(duì)比更大規(guī)模數(shù)據(jù)集的結(jié)果，再次驗(yàn)證算法的改善，并選出一組最佳參數(shù)。最后分析動(dòng)態(tài)回溯機(jī)制的個(gè)體相似度判定因子對(duì)性能的影響，綜合分析后確定其取值。

3.2 節(jié)將進(jìn)行算法的性能分析，分析不同改進(jìn)方法的作用。在數(shù)據(jù)集eil76、KroA150 與tsp225 進(jìn)行仿真實(shí)驗(yàn)，分別對(duì)ACS、ACS+波動(dòng)平衡策略、ACS+波動(dòng)平衡策略+動(dòng)態(tài)回溯機(jī)制進(jìn)行20 次仿真實(shí)驗(yàn)，通過對(duì)比實(shí)驗(yàn)分析各改進(jìn)方法的作用及優(yōu)勢(shì)。

3.3 節(jié)將在多組數(shù)據(jù)集中對(duì)ACS、ACS+3opt 與PBACO 算法進(jìn)行仿真實(shí)驗(yàn)，證明本文算法性能更優(yōu)，有效改善了蟻群算法解的質(zhì)量，較好地平衡了解的多樣性與收斂速度的關(guān)系。

3.4 節(jié)將會(huì)與其他最新改進(jìn)算法進(jìn)行對(duì)比分析，再次驗(yàn)證本文改進(jìn)算法的性能。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文在ACS的基礎(chǔ)上進(jìn)行多次實(shí)驗(yàn)，測(cè)試了多組參數(shù)對(duì)算法性能的敏感性作用，統(tǒng)計(jì)發(fā)現(xiàn)公共參數(shù)為表1 所示參數(shù)時(shí)效果更好。因此，在本文后續(xù)實(shí)驗(yàn)中，在表1 公共參數(shù)不變的基礎(chǔ)上測(cè)試其他參數(shù)，進(jìn)行敏感性分析。

表1 PBACO 的公共參數(shù)設(shè)置Table 1 Public parameter setting of PBACO

表1 中，為信息啟發(fā)因子，影響信息素在路徑構(gòu)建的作用，越小，螞蟻探索非最優(yōu)路徑的概率增加，解的多樣性變好，但容易使期望啟發(fā)因子作用加強(qiáng)而陷入局部最優(yōu)；為期望啟發(fā)因子，越大，螞蟻選擇距離最短路徑的概率加大，收斂速度加快，但多樣性會(huì)降低；為局部信息素?fù)]發(fā)率，揮發(fā)率過小時(shí)，會(huì)容易陷入局部最優(yōu)，揮發(fā)率過大時(shí)，會(huì)影響最優(yōu)路徑的探索；為螞蟻數(shù)量，螞蟻數(shù)量越大，得到的解越多，算法精度相應(yīng)提升，但會(huì)增加時(shí)間成本，影響收斂速度；為式（1）的判別閾值，越大，算法探索信息素與距離更短的路徑概率越大，收斂速度加快，但多樣性降低；為總迭代數(shù)。

表2 節(jié)點(diǎn)分配組合表Table 2 Node allocation combination table

首先將圖2 中的9 組區(qū)間參數(shù)，與=0.3 在公共參數(shù)相同的基礎(chǔ)上進(jìn)行實(shí)驗(yàn)對(duì)比，在KroA100數(shù)據(jù)集上進(jìn)行獨(dú)立實(shí)驗(yàn)30 次，得到的運(yùn)行結(jié)果如表3 所示。

以=0.3 作對(duì)比，觀察表3 可知，在KroA100 數(shù)據(jù)集上，各組參數(shù)均能找到最優(yōu)解；在0.1～0.3 區(qū)間時(shí)，其滿足誤差率比例與平均解都最優(yōu)，同時(shí)參數(shù)為0.1～0.5、0.1～0.9、0.3～0.7 與0.5～0.9 在平均解上都略優(yōu)于0.3，前三組參數(shù)在滿足誤差率比例上與0.3 持平，雖然0.5～0.9 略低，但在后續(xù)仿真時(shí)也加入實(shí)驗(yàn)，避免遺失潛在優(yōu)質(zhì)參數(shù)。通過表3 數(shù)據(jù)可知，價(jià)格波動(dòng)策略在算法各時(shí)期對(duì)的動(dòng)態(tài)調(diào)整，對(duì)算法性能具有一定改善作用。

表3 不同區(qū)間ρ 在KroA100 對(duì)蟻群算法性能的影響Table 3 Effect of different interval ρ in KroA100 on performance of ant colony algorithm

為了確定最佳參數(shù)，同時(shí)驗(yàn)證算法性能，將以上較優(yōu)的參數(shù)在KroA200 數(shù)據(jù)集上再次進(jìn)行獨(dú)立實(shí)驗(yàn)30 次，得到的運(yùn)行結(jié)果如表4 所示。

表4 不同區(qū)間ρ 在KroA200 對(duì)蟻群算法性能的影響Table 4 Effect of different interval ρ in KroA200 on performance of ant colony algorithm

以=0.3 作對(duì)比，觀察表4 可知，在KroA200 數(shù)據(jù)集上，參數(shù)為0.1～0.3 和0.1～0.5 在最小誤差率上最小，能找到精確解的能力優(yōu)于其余參數(shù)，證明此時(shí)參數(shù)會(huì)使解的質(zhì)量得到提升；在滿足誤差率比例上，參數(shù)為0.1～0.3 和0.1～0.5 均以40%比例高于其他參數(shù)，此時(shí)參數(shù)穩(wěn)定性能優(yōu)于其他參數(shù)；最后通過比較15組實(shí)驗(yàn)最短路徑的平均解，發(fā)現(xiàn)參數(shù)0.1～0.5 的平均解優(yōu)于參數(shù)0.1～0.3，雖然在滿足誤差率比例上兩者持平，但從平均解分析可發(fā)現(xiàn)參數(shù)0.1～0.5 在解的質(zhì)量上會(huì)略優(yōu)，因此確定波動(dòng)平衡策略的參數(shù)區(qū)間為0.1～0.5，根據(jù)式（6），可計(jì)算出=577.4，=698.6。

動(dòng)態(tài)回溯機(jī)制中參數(shù)設(shè)置涉及個(gè)體相似度判定因子，值越大，個(gè)體與最優(yōu)螞蟻的路徑相似度越高，越難跳出局部最優(yōu)，值越小，路徑差異越明顯，但此時(shí)也要花費(fèi)較多的時(shí)間成本。綜合上述分析并在多組數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)在算法陷入局部最優(yōu)后，回溯至前300 代，個(gè)體相似度可降至0.95，回溯至前500 代，個(gè)體相似度可降至0.9，再往前回溯雖然個(gè)體相似度會(huì)較快下降，但其原因是已經(jīng)貼近初始運(yùn)行時(shí)期，類似于大災(zāi)變，因此綜合考慮將值設(shè)定為0.9。

3.2 算法性能分析

為了驗(yàn)證PBACO 算法各個(gè)改進(jìn)策略的作用，本文將不同策略組合為三組優(yōu)化方案，分別在數(shù)據(jù)集eil76、KroA150 與tsp225 進(jìn)行仿真實(shí)驗(yàn)，優(yōu)化方案如表5 所示。每組優(yōu)化方案在各數(shù)據(jù)集進(jìn)行20 次獨(dú)立實(shí)驗(yàn)，并統(tǒng)計(jì)各組方案的最優(yōu)解、最優(yōu)解誤差率、平均解與迭代次數(shù)，并結(jié)合收斂曲線與多樣性曲線來進(jìn)行對(duì)比與分析，統(tǒng)計(jì)結(jié)果如表6 和圖6 所示。

表5 優(yōu)化方案表Table 5 Optimization scheme table

表6 優(yōu)化方案性能對(duì)比表Table 6 Performance comparison table of optimization scheme

從eil76 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，A、B、C 方案都可以找到最優(yōu)解，但是B、C 方案在收斂速度上明顯優(yōu)于ACS 算法，并且更快速地跳出局部最優(yōu)找到最優(yōu)解，能夠較好地平衡算法多樣性與收斂速度，同時(shí)從平均解可以看出，改進(jìn)算法的穩(wěn)定性也優(yōu)于ACS 算法。

圖6 各測(cè)試集收斂情況Fig.6 Convergence of each test set

從KroA150 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，在迭代前期，B 方案通過價(jià)格波動(dòng)策略在短時(shí)間內(nèi)就能夠找到較優(yōu)解，優(yōu)于A 方案，C 方案雖然因?yàn)橄萑刖植孔顑?yōu)，未找到較優(yōu)解，但在300 代左右仍能快速跳出，并找到優(yōu)于A、B 方案的更優(yōu)解。在迭代中后期陷入局部最優(yōu)后，B 方案通過價(jià)格波動(dòng)策略，最先使算法跳出局部最優(yōu)，但解的精度不高；在此基礎(chǔ)上改進(jìn)的C 方案通過動(dòng)態(tài)回溯機(jī)制，進(jìn)一步跳出局部最優(yōu)，使算法整體解的精度得到較好的改善。

從tsp225 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，B、C 方案在前期收斂速度與探索較優(yōu)解的能力明顯優(yōu)于A 方案，在中后期的收斂曲線中，C 方案借助動(dòng)態(tài)回溯策略，在更高精度的解中多次跳出局部最優(yōu)，找到更優(yōu)解，同時(shí)結(jié)合表6 中的最優(yōu)解與平均解可以發(fā)現(xiàn)，C方案在解的精度上得到了有效提升，并且相比A、B方案，解的穩(wěn)定性也得到了明顯改善。

3.3 與傳統(tǒng)蟻群算法對(duì)比分析

為了分析PBACO 算法在不同規(guī)模數(shù)據(jù)集的性能，將ACS、ACS+3opt、PBACO 算法應(yīng)用于不同城市規(guī)模的TSP 實(shí)例中，其中ACS 與ACS+3opt 為傳統(tǒng)判定局部最優(yōu)方式，PBACO 算法中的動(dòng)態(tài)回溯機(jī)制為斐波那契數(shù)列抽樣方式判定是否陷入局部最優(yōu)，結(jié)果如表7、圖7 和圖8 所示。

圖7 PBACO 算法在部分城市集最短路徑Fig.7 Optimal path of PBACO algorithm for part of city sets

圖8 部分城市集收斂情況Fig.8 Convergence for part of city sets

圖7 和圖8 按順序分別展示了改進(jìn)算法在eil76、KroA100、KroB100、ch130、ch150、KroA150、KroB150、KroA200、KroB200、tsp225、a280 和lin318 城市集中的最短路徑和收斂情況。從表7、圖7 和圖8 可以看出，在小規(guī)模城市集中，三種算法均能找到最優(yōu)解，但ACS 與ACS+3opt 的收斂速度明顯慢于PBACO 算法，改進(jìn)算法在前期通過價(jià)格波動(dòng)策略對(duì)算法進(jìn)行改善，能夠較快收斂且找到精度較高的解。城市數(shù)在100 至200 之間的中規(guī)模城市集中，傳統(tǒng)算法無法找到ch130 的最優(yōu)解，而改進(jìn)算法能通過中后期的動(dòng)態(tài)回溯機(jī)制跳出局部最優(yōu)，找到最優(yōu)解；對(duì)于ch150、KroA150 與KroB150，PBACO 算法相比傳統(tǒng)算法均能有效地提高解的精度，并且在KroB150 城市集能精確找到最優(yōu)解，同時(shí)找到最優(yōu)解的迭代數(shù)明顯縮減。在城市數(shù)大于200 的城市集中，從表7 中可以發(fā)現(xiàn)，PBACO 算法在解的精度上得到了較大的改善，并且找到最優(yōu)解的迭代數(shù)也有部分減少，其中KroA200找到貼近最優(yōu)解的較優(yōu)解，KroA200 與a280 在改善解的精度的同時(shí)將收斂速度提升，雖然在tsp225 城市集中PBACO 迭代數(shù)較大，但在動(dòng)態(tài)回溯機(jī)制的作用下，多次跳出局部最優(yōu)，找到更優(yōu)解。在大規(guī)模城市集lin318 中，雖然在迭代前期PBACO 算法陷入短暫的局部最優(yōu)，但在200 代之后算法解的精度明顯提高，在550 代相比傳統(tǒng)算法已經(jīng)找到更優(yōu)解，并在之后陷入局部最優(yōu)后，通過動(dòng)態(tài)回溯機(jī)制多次跳出局部最優(yōu)，將解的質(zhì)量明顯改善。

表7 不同規(guī)模城市數(shù)據(jù)集的性能對(duì)比Table 7 Performance comparison of urban datasets of different sizes

3.4 與至今最新改進(jìn)算法對(duì)比分析

為了進(jìn)一步驗(yàn)證PBACO 算法性能，本文選用至今最新改進(jìn)的融合貓群算法的動(dòng)態(tài)分組蟻群算法（CACS）、考慮動(dòng)態(tài)導(dǎo)向與鄰域交互的雙蟻型算法（TREEACS）和文獻(xiàn)[11]進(jìn)行比對(duì)，如表8 所示。由表8 可以看出，PBACO 算法在小規(guī)模城市中與其他算法都能找到最優(yōu)解，但在中規(guī)模城市與大規(guī)模城市中，PBACO 算法解的精度相比其他算法得到了較好的改善。

表8 PBACO 與其他最新改進(jìn)算法比較Table 8 Comparison of PBACO with other newly improved algorithms

通過實(shí)驗(yàn)分析與結(jié)果對(duì)比可知，本文改進(jìn)后的PBACO 算法與傳統(tǒng)蟻群算法ACS、ACS+3opt和至今最新改進(jìn)的蟻群算法相比，解的精度與收斂性都有明顯的改善。

4 結(jié)束語

針對(duì)傳統(tǒng)蟻群算法存在易陷入局部最優(yōu)、收斂速度較慢等問題，本文提出一種結(jié)合價(jià)格波動(dòng)策略與動(dòng)態(tài)回溯機(jī)制的蟻群優(yōu)化算法（PBACO）。通過價(jià)格波動(dòng)策略，以時(shí)間序列分析的思想將算法不同需求的時(shí)期進(jìn)行分類，以價(jià)格波動(dòng)平衡的供求思想對(duì)信息素?fù)]發(fā)因子進(jìn)行自適應(yīng)動(dòng)態(tài)供給，在保證收斂速度的同時(shí)增大跳出局部最優(yōu)的能力，能夠有效地改善解的質(zhì)量。在算法陷入局部最優(yōu)后，引入動(dòng)態(tài)回溯機(jī)制，以迭代最優(yōu)螞蟻的個(gè)體相似度作為標(biāo)準(zhǔn)，將路徑信息素回溯至相似度差異顯著的時(shí)期，在保證收斂速度的同時(shí)能夠有效地跳出局部最優(yōu)，明顯改善解的精度，并且保證解的穩(wěn)定性。雖然在實(shí)驗(yàn)對(duì)比中相較其他算法解的質(zhì)量得到較好的改善，但在超大規(guī)模城市集中算法解的精度還需要進(jìn)一步提升，因此下一步將進(jìn)行多種群合作競(jìng)爭(zhēng)的算法研究，以提高算法在超大規(guī)模城市集中的求解能力。