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

劉陽陽　莊恒國　張亞楠

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

關鍵詞關鍵詞：蟻群算法；組合優化問題；相鄰節點

DOIDOI：10.11907/rjdk.171001

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）005003103

0引言

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

1蟻群算法

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

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

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

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

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

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

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

2算法策略

2.1信息素自適應更新策略

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

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

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

2.2路徑變異思想

2.2.1蟻群尋徑軌跡

本文通過城市間的相對距離分析路徑特征，取Eil51和KroA100兩個實例的中間解和最優解，統計路徑中相鄰節點間的關系。

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

2.2.2路徑變異

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

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

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

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

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

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

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

2.3算法步驟

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

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

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

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

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

步驟5 求解當次迭代最優解，如果小于當前最優解，更新最優和次優解，轉步驟7；否則，轉步驟6。

步驟6 當次迭代最優解小于當前次優解，更新次優解。

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

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

步驟9 輸出最優路徑及其長度。

3實驗結果與分析

初始各參數值，螞蟻數量N_ant=城市規模/1.5，參數α=β=2.0，q0=0.5，信息素揮發因子初始值ρ=0.95，ρmin設為0.3。

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

4結語

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

參考文獻參考文獻：

[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].計算機研究與發展，2009，46（6）：968978.

[8]孟祥萍，片兆宇，沈中玉，等.基于方向信息素協調的蟻群算法[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]馬穎，田維堅，樊養余.量子擴展蟻群連續優化改進算法[J].計算機工程與設計，2015，36（9）：24492554.

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

[12]劉全，陳浩，張永剛，等.一種動態揮發率和啟發式修正的蟻群優化算法[J].計算機研究與發展，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.

責任編輯（責任編輯：黃健）