基于相鄰節(jié)點間特征改進的蟻群算法

劉陽陽　莊恒國　張亞楠

摘要摘要：蟻群算法是解決組合優(yōu)化問題比較有效的方法。該方法采用分布式并行計算機制，易于與其它方法結(jié)合，并具有較強的魯棒性，但也存在搜索時間長、易陷入局部最優(yōu)解等問題。在研究多種改進的蟻群算法基礎(chǔ)上，提出一種改進的蟻群算法來求解TSP問題。改進算法根據(jù)相鄰節(jié)點間的相對距離特征，對路徑解進行變異，誘導(dǎo)蟻群快速尋找到更優(yōu)解。同時引入信息素?fù)]發(fā)因子自適應(yīng)調(diào)整機制和公共路徑思想，調(diào)節(jié)算法收斂速度，以保證算法的全局搜索能力。實驗結(jié)果表明，改進算法相比于MMAS、DMPSOACO等算法，求解精度和收斂速度都有所提高，所選取的測試實例中，平均解相對已知最優(yōu)解的偏差百分比平均可達到0.63%。

關(guān)鍵詞關(guān)鍵詞：蟻群算法；組合優(yōu)化問題；相鄰節(jié)點

DOIDOI：10.11907/rjdk.171001

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號文章編號：16727800（2017）005003103

0引言

蟻群算法是一種模擬自然界中螞蟻覓食行為的啟發(fā)式搜索算法，于20世紀(jì)90年代由意大利Dorigo等學(xué)者[13]提出。后續(xù)各國研究者也提出多種優(yōu)秀的蟻群優(yōu)化算法求解組合優(yōu)化問題。例如，文獻[4]提出了蟻群系統(tǒng)（Ant Colony System，ACS），相對于早期的螞蟻系統(tǒng)（Ant System，AS），強調(diào)了對新路徑的開發(fā)程度，以某一既定概率選擇最優(yōu)路徑，不像AS確定性地選擇最優(yōu)路徑；文獻[5]為了克服蟻群算法中存在的停滯問題，提出了一種最大-最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS），將信息素控制在一定范圍內(nèi)，尋徑結(jié)束后僅更新最優(yōu)路徑的螞蟻信息素；文獻[6]在蟻群算法中引入遺傳算法思想，以達到提升ACS算法性能的目的；文獻[7]對信息素模型進行了改進，建立了以城市為端點、城市間路徑為中心軸的能量等勢場模型；文獻[8]為描述尋優(yōu)過程中的全局信息，定義了一種新的方向信息素，較好地克服了算法停滯現(xiàn)象，提高了解的全局性。本文從蟻群算法在旅行商問題中（Travelling Salesman Problem，TSP）的應(yīng)用出發(fā)，提出了一種基于路徑特征改進的蟻群算法。本文算法根據(jù)相鄰城市間的關(guān)系對路徑進行變異，擴大蟻群的種群多樣性，以便在算法停滯前發(fā)現(xiàn)更短路徑，不斷趨向最優(yōu)路徑解。同時引入信息素?fù)]發(fā)因子自適應(yīng)調(diào)整機制和公共路徑思想，調(diào)節(jié)收斂速度，以提升全局搜索能力。

1蟻群算法

在蟻群算法中，第k只螞蟻由城市i選擇到下一個城市j的規(guī)則是：

其中，q0是（0，1）之間的常數(shù)，q是（0，1）之間均勻分布的隨機數(shù)，τij（t）表示城市i和城市j之間路徑上的信息素濃度，dij為兩個城市之間的距離。啟發(fā)式因子α反映螞蟻在運動過程中所積累的信息量在指導(dǎo)蟻群搜索中的相對重要程度；啟發(fā)式因子β反映螞蟻在運動過程中啟發(fā)信息在指導(dǎo)蟻群搜索中的相對重要程度；allowedk表示第k只螞蟻當(dāng)前的可行城市集合。由式（1）、式（2）組成的偽隨機規(guī)則傾向于選擇短且信息素濃度更大的一條路徑移動。每次搜索結(jié)束后，每條路徑的信息素按公式（4）～（6）進行更新：

τij（t+1）=（1-ρ）τij（t）+ρΔτij（4）

Δτij=∑mk=1Δτkij（5）

公式（5）中，Δτkij為：

Δτkij=QLk，若第k只螞蟻在本次循環(huán)經(jīng)過路徑（i，j）0，若第k只螞蟻在本次循環(huán)不經(jīng)過路徑（i，j）（6）

其中，m表示螞蟻總個數(shù)，ρ表示信息揮發(fā)速率，τij表示螞蟻在本次循環(huán)中留在路徑（i，j）上的信息量，Δτij表示本次循環(huán)中所有經(jīng)歷過路徑（i，j）的螞蟻留在該路徑上信息量的增量，Q表示螞蟻循環(huán)一周所釋放的總信息量，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的長度。這種信息的更新規(guī)則可以使算法信息正反饋性能增強，提高系統(tǒng)搜索的收斂速度。

2算法策略

2.1信息素自適應(yīng)更新策略

信息素?fù)]發(fā)因子ρ反應(yīng)了整個蟻群系統(tǒng)的進化狀態(tài)，當(dāng)ρ越大，收斂速度越快，但會影響算法的全局搜索能力。通過減小ρ，增強隨機性，卻可能使算法的收斂速度降低。為了在“探索”和“利用”間保持平衡，文獻[9]、[10]中都采用了不同的自適應(yīng)調(diào)整方案來動態(tài)調(diào)整ρ值。改進算法中選用簡單而有效的自適應(yīng)策略來調(diào)整ρ，公式如下：

ρ（t+1）=ξ·ρ（t） []ξ·ρ（t）≥ρminρmin[]ξ·ρ（t）<ρmin（7）

式中，ρmin為ρ的最小值，以防止ρ過小而降低算法的收斂速度，ξ∈（0，1）為揮發(fā)因子調(diào)節(jié)系數(shù)。算法初期賦予ρ較大的值，以前搜索過的解被選擇的可能性較大，收斂速度快。為防止陷入局部收斂，后期會逐漸降低ρ值，使未被遍歷的路徑信息素增大，提高了全局搜索能力。通過對揮發(fā)系數(shù)進行自適應(yīng)地改變，既可以提高解的全局性，又可以保證收斂速度。

2.2路徑變異思想

2.2.1蟻群尋徑軌跡

本文通過城市間的相對距離分析路徑特征，取Eil51和KroA100兩個實例的中間解和最優(yōu)解，統(tǒng)計路徑中相鄰節(jié)點間的關(guān)系。

從表1、表2可以看到，Eil51和KroA100兩個實例的最優(yōu)解中相鄰兩個城市的相對距離也較近，主要集中在[0，5）的范圍內(nèi)。而在中間解中，城市間距離分布不均，這是因為在算法迭代過程中，螞蟻所釋放的信息素不足以讓螞蟻快速選擇長度較短的路徑，前期還是選擇了離自己相對較遠的城市。本文將那些相對較遠的城市對視為關(guān)鍵點對，將其進行有效變異，誘導(dǎo)蟻群算法快速收斂到更高質(zhì)量的解。

2.2.2路徑變異

依據(jù)上一小節(jié)的分析對關(guān)鍵點進行變異，結(jié)合局部搜索思想，本文提出一種基于路徑特征改進的方法。假設(shè)當(dāng)前路徑為R（X1，X2，X3，…，Xn），相對距離閾值下界為Dis0，相對距離閾值上界為Dis1，當(dāng)前路徑長度為Len，對路徑進行變異的步驟如下：

步驟1 按相對距離遠近將R排序，得到Order數(shù)組。

步驟2 計算i←Order [k]，k>Dis0，記錄城市點R[i+1]。

步驟3 查找與R[i]相對距離小于Dis1的點R[j]。

步驟4 計算將R[i+1]與R[j]間的路徑進行翻轉(zhuǎn)后的路徑長度。如果長度小于Len，Len←Length（R），記錄R[i+1]、R[j]。

步驟5 更新k←k+1，如果k

變異作用于每次迭代過程中所得到的路徑。此外，在迭代過程中會記錄蟻群最優(yōu)及次優(yōu)路徑的公共部分，當(dāng)前最優(yōu)與次優(yōu)路徑得到的公共路徑很有可能是全局最優(yōu)路徑的組成部分。利用公共路徑尋徑，不但能夠減少算法中的大量重復(fù)計算，還可以誘導(dǎo)蟻群向最優(yōu)路徑變化[11]。

2.3算法步驟

綜上所述，算法步驟歸納為如下：

步驟1 初始化參數(shù)：城市數(shù)、螞蟻個數(shù)、蟻群算法迭代計數(shù)器、蟻群算法允許迭代最大次數(shù)、蟻群信息素等。

步驟2 將其中一部分蟻群，第一組按公式（1）、（2）進行城市選擇，生成路徑解，并對每條路徑進行變異。

步驟3 記錄步驟2解集中的最優(yōu)和次優(yōu)解，并計算出它們的公共路徑。

步驟4 取步驟2的剩余蟻群，將步驟2的公共路徑作為必經(jīng)路段，非公共路徑上的城市按公式（1）、（2）進行狀態(tài)轉(zhuǎn)移，與公共路徑連成一條回路，生成路徑解，并對每條路徑進行變異。

步驟5 求解當(dāng)次迭代最優(yōu)解，如果小于當(dāng)前最優(yōu)解，更新最優(yōu)和次優(yōu)解，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟6。

步驟6 當(dāng)次迭代最優(yōu)解小于當(dāng)前次優(yōu)解，更新次優(yōu)解。

步驟7 按公式（4）～（6）更新信息素。

步驟8 蟻群算法迭代計數(shù)器加1，如果達到最大迭代次數(shù)，轉(zhuǎn)步驟9，否則轉(zhuǎn)步驟2。

步驟9 輸出最優(yōu)路徑及其長度。

3實驗結(jié)果與分析

初始各參數(shù)值，螞蟻數(shù)量N_ant=城市規(guī)模/1.5，參數(shù)α=β=2.0，q0=0.5，信息素?fù)]發(fā)因子初始值ρ=0.95，ρmin設(shè)為0.3。

表3比較了在本文算法中采用不同Dis0、Dis1值時，不同實例所得到的平均長度。

4結(jié)語

本文提出的改進算法根據(jù)路徑特征對螞蟻偵查到的路徑進行變異，以豐富種群多樣性，有助于跳出局部最優(yōu)，增強算法的全局尋優(yōu)能力。引入的公共路徑和自適應(yīng)調(diào)整機制可有效調(diào)節(jié)算法收斂速度。實驗結(jié)果表明，在TSP問題上，改進算法相比MMAS、DMPSO-ACO算法不僅能夠得到相對較好的解，收斂速度也有一定提升。平均解相對已知最優(yōu)解的偏差百分比平均可達0.63%，最優(yōu)解相對已知最優(yōu)解的偏差百分比平均可達0.04%。在今后的研究中，會進一步分析不同參數(shù)組合之間的相互制約關(guān)系，并將算法應(yīng)用到實際的組合優(yōu)化問題中，以解決實際工作中的問題。

參考文獻參考文獻：

[1]COLORNI A，DORIGO M，MAIEZZO V.Distributted optimization by ant colonies[C].Proc of the ECAL′91 European Conf of Artificial Life.New York：Elsevier，1991：134144.

[2]DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agents[J].IEEE Transaction on Systems，Man，and Cybernetics，Part B：Cybernetics，1996，26（1）：2941.

[3]DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the travelling salesman problem[J].IEEE Transaction on，Evolutionary Computation，1997（1）：5366.

[4]GAMBARDELLA L M，DORIGO M.Solving symmetric and asymmetric TSPs by ant colonies[C].Proc of the 1996 IEEE Int Conf on Evolutionary Commutation ICEC96.Piscataway，NJ：IEEE，1996：622627.

[5]STUTZLE T，HOOS H H.Maxmin ant system[J].Future Generation Computer Systems，2000（16）：889914.

[6]TSAI C F，TSAI C W.A new approach for solving large travelling salesman problem using evolution ant rules[C].Proc of the 2002 Int Joint Conf on Neural Networks （IJCNN 2002）.Piscataway，NJ：IEEE，2002：15401545.

[7]冀俊忠，黃振，劉椿年.一種快速求解旅行商問題的蟻群算法[J].計算機研究與發(fā)展，2009，46（6）：968978.

[8]孟祥萍，片兆宇，沈中玉，等.基于方向信息素協(xié)調(diào)的蟻群算法[J].控制與決策，2013，28（5）：782786.

[9]DUAN H B，ZHANG X Y，WU J，et al.Maxmin adaptive ant colony optimization approach to multi UAVs coordinated trajectory replanning in dynamic and uncertain environments[J].Journal of Bionic Engineering，2009（6）：161173.

[10]馬穎，田維堅，樊養(yǎng)余.量子擴展蟻群連續(xù)優(yōu)化改進算法[J].計算機工程與設(shè)計，2015，36（9）：24492554.

[11]申鉉京，劉陽陽，黃永平，等.求解TSP問題的快速蟻群算法[J].吉林大學(xué)學(xué)報：工學(xué)版，2013，43（1）：147151.

[12]劉全，陳浩，張永剛，等.一種動態(tài)揮發(fā)率和啟發(fā)式修正的蟻群優(yōu)化算法[J].計算機研究與發(fā)展，2012，49（3）：620627.

[13]ZHENG JIANGUO，WU DAQING，ZHOU LIANG.Traveling salesman problem using an enhanced hybrid swarm optimization algorithm[J].Journal of Donghua University，2014，31（3）：362367.

責(zé)任編輯（責(zé)任編輯：黃?。?