基于新型信息素更新策略的蟻群算法

摘 要:深入研究了蟻群優化算法(ACO)的路徑搜索及參數控制策略，分析了其存在的缺陷。為了提高ACO算法的解題能力，提出一種新型信息素更新策略(PACS)，然后將PACS算法與其他蟻群算法分別應用于旅行商問題(TSP)進行仿真實驗。仿真結果表明，PACS算法具有優良的全局優化性能，可抑制算法過早收斂于次優解，有效防止了停滯現象，收斂速度也大大加快。

關鍵詞:蟻群算法; 旅行商銷售問題; 參數控制; 信息素

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2080-04

doi:10.3969/j.issn.1001-3695.2010.06.024

Ant colony algorithm based on new pheromone updated strategy

CEN Yu-sen1， XIONG Fang-min2， ZENG Bi-qing2

(1. School of Computer Science ， Zhaoqing University， Zhaoqing Guangdong 526061， China; 2. Dept. of Computer Engineering ， Nanhai College， South China Normal Univercity， Foshan Guangdong 528225， China)

Abstract:This paper studied the routes searching strategy and the pheromone updating strategy of ant colony optimization algorithm (ACO) and ananlyzed the limitations of these strategies. To increase the performance of ACO， proposed the ant colony system based on improved pheromone updated strategy (PACS). Gave an example of traveling salesman problem， which was simulated by using basic ACO and PACS. The simulation results show that PACS has excellent global optimization properties and faster convergence speed， and it can avoid premature convergence of ACO.

Key words:ant colony optimization; traveling salesman problem; parameters control; pheromone

0 引言

蟻群優化算法(ant colony optimization，ACO)是20世紀90年代由意大利學者Dorigo等人通過模擬自然界螞蟻覓食行為提出的一種全新的模擬進化算法。該算法是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經網絡算法等元啟發式搜索算法以后的又一種應用于組合優化問題的啟發式搜索算法。ACO算法已陸續成功地應用于求解多種復雜的組合最優化問題，如旅行推銷員問題 (TSP)、車輛路線問題、二次指派問題、工作站排班問題和圖形著色問題等[1~3]。

近十多年來，隨著對上述各策略執行細節的設計不同，已有許多種改良式螞蟻算法陸續被提出，較著名的有蟻群系統(ACS)、帶精英策略的螞蟻系統(AS)和最大最小螞蟻系統(MMAS)等。它們之間的差別主要在于信息素更新方式的不同。不同的信息素濃度更新方式可能會導致因為初期產生的可行解品質不佳而累積了偏差的可行解信息，導致無法由累積信息素的方式搜索到更優的解;此外，算法后期也不易跳脫局部最優解的束縛。信息素濃度更新方式是影響求解效率與品質的重要因素之一[2~5]。

旅行商問題(traveling salesman problem，TSP)是一種經典的組合優化問題，此類問題已經被證明是一種NP難問題，即不能在多項式時間內求得問題的最優解。最近幾年，關于此問題的研究吸引了多個學科領域的關注，包括人工智能、生物學、數學等領域。雖然其數學模型很容易被模擬，并且出現了多種優化方法如模擬退火算法、遺傳算法、貪婪算法、蟻群算法、神經網絡算法等，以及多種算法相結合的方法(如蟻群—遺傳算法)，但當涉及到組合優化中如何快速、有效地求出其最優解時，這些方法均或多或少地存在一些缺點和不足[6]。

鑒于此，本文希望針對蟻群算法的信息素控制參數進行深入研究與分析，并對傳統的蟻群系統(ACS)的信息素更新方式進行改良，提出新的信息素更新策略(PACS)，以提升蟻群算法的解題績效。為驗證PACS的解題績效，從TSP 的國際標準題庫中選擇了10個例題進行測試，并將測試結果與目前較為著名的改良蟻群算法進行比較。

1 基本蟻群算法原理

ACO 算法在每一次反復回合開始時，以隨機方式產生每只螞蟻皆不相同的起始節點，搜索路徑時則利用信息素濃度及意念函數組成的公式，求出該螞蟻尚未經過的各個節點的預行走概率值 (P)，再依據概率值決定螞蟻下一個欲前往的節點，然后將該節點加入該螞蟻既有路徑中。依此類推，直到所有節點皆經過一次后回到該螞蟻在該次循環時的起始節點才算是完成路徑，最后進行信息素濃度更新操作。該次路徑信息可視為一種較優解信息，引導后續路徑構建操作并開始搜索更優的解[1～5]。

算法執行前需先設定基本參數，包括節點數 (n)、螞蟻數 (k)、信息素初值 (τ)、回合數 (t)、蒸發系數 (ρ)、意念函數 (η)、信息素權重 (α)、意念函數權重 (β) ，其余變量符號說明見表1。

表1 變量符號定義

符號定義

τij(t)在第t 次反復時，路徑 (i，j) 上的信息素濃度

ηij螞蟻從節點i行走到節點j的意念函數，為節點i與j間距離的倒數

Nki螞蟻k在節點i時，可選擇的尚未經過的節點集合

Pkij(t)螞蟻k在第t次反復時從節點i行走至節點j 的概率值

Lk(t)螞蟻k在第t次反復時所完成路徑的長度

Lb(t)第t次反復中的最優解路徑長度

Lgb(t)執行至第t次反復時所記錄的目前最優解路徑長度

τmax(t)第t次反復開始前，各路段信息素濃度的最大值

τmin(t)第t次反復開始前，各路段信息素濃度的最小值

Q常數參數代表信息素數量

傳統的ACS算法執行步驟如下:

a)設定參數初值。

b)重復b)直到所有螞蟻都完成各自完整的可行路線:

(a)螞蟻k利用式(1)構建一條完整的可行路線P(k):

Pkij(t)=[τij(t)]α[ηij]β∑j∈Nki[τij(t)]α[ηij]β 若j∈Nki(1)

(b)利用式(2)和(3)對可行路線P(k)進行信息素濃度實時更新作業:

τij(t)=(1-ξ)τij(t)+ξτ0 0<ξ<1(2)

τ0 = (n×Lk(t))-1(3)

c)利用式(4)進行信息素濃度全局更新作業:

τij(t+1)=(1-ρ)τij(t)+ρΔτgbij(t)Δτgbij(t)=1/Lgb(4)

d)反復回合數累計一次。若滿足停止條件，則輸出最優解;否則回到步驟b)。

為了提高蟻群算法的求解性能，研究人員相繼提出了一系列改良型蟻群系統。經過分析比較發現各種改良型螞蟻系統的主要區分在兩大部分，即路徑搜索策略和信息素更新策略。兩個策略是各種改良蟻群算法的差異所在。

2 新型信息素更新策略(PACS)

2.1 實時更新策略

傳統的ACS 算法中，當路段pij已被螞蟻k經過后，則立即調整該路段的信息素濃度。由Dorigo等學者的研究可知[1～4]，若設定τ0=0，蒸發掉該路段上固定比例的信息素濃度(降低該路段再被經過的概率)所得的結果較設定τ0=(n ×Lk(t))-1差，因為若包含該路段所組成的路徑較優時，不應下降相同比例的信息素濃度量，應減少下降比例，以避免累積在路網上的信息素信息混亂，反之則多下降些信息素濃度，以避免后續螞蟻行走到該條較差的路段。

下面將分述ACS采用使用式(3)進行信息素實時更新可能出現以下四種信息素濃度調整情形:

a)過去已有許多螞蟻行經的路段(τ值偏大)，且包含該路段所組成的路徑較優(τ0 值偏大)，表示該路段組成最優解概率較高，則下降較少量的信息素濃度，使后續螞蟻行經此路段的概率仍高。

b)過去并未有許多螞蟻行經的路段(τ值偏小)，但包含該路段所組成的路徑卻較優(τ0 值偏大)，表示該路段組成最優解概率較高，則下降較少量的信息素濃度，以保持后續螞蟻行經此路段的概率。

c)過去已有許多螞蟻行經的路段(τ值偏大)，但包含該路段所組成的路徑卻較差(τ0 值偏小)，表示該路段組成最優解概率偏低，則下降較多量的信息素濃度，以降低后續螞蟻行經此路段的概率。

d)過去并未有許多螞蟻行經的路段(τ值偏小)，且包含該路段所組成的路徑也較差 (τ0 值偏小)，表示該路段組成最優解概率應很低，則下降較大量的信息素濃度，持續降低后續螞蟻行經此路段的概率。

(n×Lk(t))-1的值相較于τij為一極小的數值，所以原ACS算法中信息素實時更新的結果都會使原路段信息素濃度下降，僅下降幅度不同;此外由于(n×Lk(t))-1的值相對極小，路段調整結果對于相同回合數或鄰近回合數的螞蟻搜索結果影響并不大。

為了增加搜索解的廣度，同時避免后續的螞蟻行走到較差的路段上，本文提出了一個新的信息素實時更新策略。

PACS算法是將信息素實時更新策略更改如式(5)所示，利用路網中最大與最小值的信息素濃度值，增加信息素實時更新時調整的幅度，即增加對相同回合數或鄰近回合數中螞蟻搜索方向的影響程度。

τij(t)=(1-ξ)τij(t)+ξτmax(t)nLk(t) 當τij(t)≥τ(t)(1-ξ)τij(t)+ξτmin(t)nLk(t) 否則(5)

其中:1<ξ<0;τ(t)=τmin(t)+τmax(t)2。

當路段dij的信息素濃度高于該路徑中信息素濃度的中間值τ(t)時，表示該路段存在于最優解中的可能性偏高，即利用該次反復的路網中最高的信息素濃度值，減少信息素濃度下降量，保持后續螞蟻可能行走該條較優路線的可能性;但由于信息素濃度值已下降，仍可達到信息素實時更新的目的，即在相同回合中，增加其他未被行走過路段被行走的概率，以跳出局部最優解。反之，當路段dij的信息素濃度低于該路徑中信息素濃度的中間值時，表示該路段存在于最優解中的可能性偏低，則利用該次反復的路網中最小的信息素濃度值，提高路徑信息素濃度的下降量，增加后續螞蟻嘗試其他較優路段去搜索最優解的機會。

2.2 全局更新策略

目前各種較著名的ACO算法中，其信息素全局更新方式皆不相同，其中AS使用螞蟻走出的所有路徑進行更新、Elitist AS累積使用數次目前最優解、ACS與AntQ只使用一次目前最優解、最大最小螞蟻系統(MMAS)依設定頻率交替使用目前最優解或是回合最優解，而ASrank則以權重分配的方式同時使用多個回合最優解與目前最優解。各種不同的設計策略，配合其適合的參數設定以及其他搜索與更新策略，使得各個ACO算法在求解組合優化問題時大多有良好的表現[7~9]。

然而，根據過去學者研究結果，本文分析各算法使用的策略，發現下列三項缺陷:

a)每次反復結束時僅利用一條路徑進行更新，或僅利用目前最優解的路徑進行更新，如ACS、Elitist AS和AntQ 等。其路網中所記錄的歷史解信息將過于狹隘，求解過程容易快速收斂;若只利用每次反復所得的最優解，則路網中所記錄的歷史解信息將過于混淆，不易反映出全局最優解信息。

b)最大最小螞蟻系統(MMAS)算法中，最優解與回合最優解交替使用頻率設定策略。目前最優解使用頻率變化的范圍值是以固定值方式設定。當設定不同的反復次數時，就必須重新設定范圍值，非常不具有彈性，且依據不同規模的問題、不同的求解反復次數，以及使用的螞蟻數不同時，MMAS 算法中所適合的全局最優解應用頻率也皆不相同，造成使用該算法時，適合的交替頻率參數值測試非常不容易。

c)ASrank 算法中，信息素全局更新策略以權重方式組合r個回合最優解，并給予目前最優解較高的權重。該策略累積較多的反復可行解確實可以增加搜索廣度。其中較優解給予較高的權重，而較差解則給予較低的權重。在反復過程中雖可逐漸凸顯較優路徑，但亦會減緩近似解收斂的速度，所以較其他算法的策略需要更多的反復次數。而該策略所增加的參數r值亦應隨著不同規模的問題以及使用的螞蟻數改變，又增加了一項需測試的參數。進一步對算法求解效率分析，該策略需將每次反復產生的可行解進行排序，方可擷取出其中較優的r個解進行信息素全局更新，增加了求解時間。

本文采用全局最優解與回合最優解的路徑信息同時使用來改良信息素全局更新策略，既保留了前述各項策略優勢，又避免其缺陷的出現。具體改良策略如式(6)所示。

τij(t+1)=(1-ρ)τij(t)+(ρ-w(t))τb(t)+w(t)τgb(6)

式(6)采用了變化型的權重分配方式，其中ρ-w(t)與w(t)分別代表回合最優解與目前最優解在第t次反復時所使用的權重值。變化型權重分配方式為求解初期給予回合最優解較高權重ρ-w (t)，以增加搜索區域的廣度，隨著反復次數的增加，漸漸給予全局最優解路徑較高的權重值w(t)，同時漸漸降低回合最優解所占的權重ρ-w(t)，以增加搜索解的深度與品質，如此并不會增加新的參數，同時回合最優解與目前最優解所使用的權重設定方式亦較具彈性。

3 仿真實驗

這里利用題庫TSPLIB中10個題目進行測試。使用Microsoft Windows XP操作系統，與AMD Athlon (tm) 64 Processor 3000+1.80 GHz，1GB Ram 環境中進行測試。

新型信息素實時更新策略如式(5)所示，參數n值沿用過去學者設定方式，與節點數相同，而參數ξ值經過參數測試，測試介于0.05～0.95，以0.05 遞增的19項數值，結果顯示參數ξ值等于0.6 時所求得的最優解普遍較優。

新型信息素全局更新策略如式 (6) 所示，同時使用回合最優解與目前最優解進行信息素全局更新。在算法初期由于目前最優解的品質尚未最優，且求解初期也應增加求解范圍的廣度，進行信息素全局更新時，本文給予回合最優解較高的權重。隨著演算過程的推進，算法所搜索到的目前最優解品質漸漸提升，因而進行信息素全局更新時亦漸漸提升目前最優解的權重值，同時漸漸降低回合最優解所占的權重值。

為測試較適合的回合最優解與目前最優解間的權重分配比，本文實驗設計回合最優解與目前最優解的權重分配比會隨權重變化長度而改變。例如，權重變化長度等于5時，權重分配比為 {5∶1、4∶2、3∶3、2∶4、1∶5}，當反復回合數小于t/5時，使用第一個權重分配比 (5∶1)，即回合最優解權重值(ρ-w(t))=5，而目前最優解權重值w(t)=1;當反復回合數介于 t/5 ~ 2t/5 時，使用第二個權重分配比 (4∶2);依此類推，當反復回合數大于4t/5時，使用第五個權重分配比 (1∶5)。若權重的變化長度等于3時，權重分配比則為{3∶1、2∶2、1∶3}，以此規則測試權重變化長度值范圍 10~1所包含的所有整數，其他參數使用的設定值為沿用過去學者針對ACS算法建議使用的參數值。

結果顯示權重變化長度值等于5與9時較優解平均績效普遍較優，而長度值為9時所求得的最優解品質亦明顯較優，與題庫最優解差距也最小。

實驗是從TSP的國際標準題庫中選擇了10個例題進行測試，每次測試運行50次，每次迭代數是1 000。表2對比了PACS算法和傳統ACS算法以及最大最小螞蟻系統(MMAS)求解過程中獲得的最優解，也就是搜索得到的最短路徑長度。表3對比了同樣的TSP問題，求解獲得的平均值。

表2 各種ACO算法求解 TSP的最優解

TSP題目名稱題庫最優解ACSMMASPACS

Ulysses227575.3175.3175.31

Bays299 0749 6149 0749 074

Att4833 52338 49933 52433 523

Eil51426428426426

KroA10021 28221 28221 28221 282

KroC10020 74920 75120 75020 750

KroD10021 29421 29521 29421 294

Oliver30424430427425

Pr12459 03059 03159 03059 030

Pr76108 159108 165108 160108 159

表3 各種ACO算法求解 TSP的平均解

TSP題目名稱題庫最優解ACSMMASPACS

Ulysses227675.875.3575.31

Bays299 07410 0979 0919 083

Att4833 52340 95633 68333 600

Eil51426433428428

KroA10021 28221 42021 29121 285

KroC10020 74920 76020 75820 758

KroD10021 29421 33521 32521 321

Oliver30424445437427

Pr12459 03059 66359 13559 071

Pr76108 159108 284108 272108 224

從表2的數據可以看出，PACS算法求得的最優解要比其他算法求得的最優解更接近題庫已知最優解;從表3的數據可以看出，在同樣的求解次數下，PACS算法的平均值也比其他算法求得的平均值更小，更接近已知最優解。

為了更加直觀地體現 PACS算法的優越性，選擇Bays29 和Att48 題目作為測試對象，將PACS 、ACS、MMAS 的收斂過程體現在圖1~4上。

從圖1和2可以看出，PACS的收斂速度和優化結果都要比ACS和MMAS強。圖3和4比較了ACS和PACS算法求解Att48 問題的收斂速度和穩定性能。圖中記錄了求解50次過程中，每次求得的回合最優解。從圖中可以看出，PACS算法不但擁有較快的收斂速度，而且還具有較好的求解穩定性。

根據以上模擬結果，可以判定采用本文改良策略的蟻群算法的全局搜索能力和優化速度都有較大的改善，能夠高效地求解各種TSP問題。

4 結束語

本文針對現今已提出且較著名的各種 ACS 算法的路徑搜索策略與參數設計方式優缺點進行了詳細分析，并提出了一種新的信息素更新策略(PACS)，同時測試其可否有效提升ACS 算法的求解績效。實驗是從TSP 的國際標準題庫中選擇了10個例題進行測試，并將測試結果與目前較為著名的蟻群算法進行比較，測試結果表明 PACS 算法求得的最優解和平均解均比其他蟻群算法(ACS、MMAS)的結果更優、收斂速度更快、求解過程更穩定。

綜上所述，本文提出的信息素更新策略(PACS)與目前各種著名的ACS算法求解品質相比較有顯著的改善。可見，PACS策略可以作為改良蟻群算法的主要策略。

參考文獻:

[1]DORIGO M， MANIEZZO V， COLORNI A. Ant system:optimization by a colony of cooperating agents[J]. IEEE Trans on Systems， Man and Cybernetics，1996，26(1):29-41.

[2]BEKTAS T. The multiple traveling salesman problem:an overview of formulations and solution procedures[J].Omega，2006，34(33):209-219.

[3]BONABEAU E， DORIGO M， THERAULAZ G. Inspiration for optimization from social insect behaviour[J].NATURE，2000，406(6):39-42.

[4]鄭松，侯迪波，周澤魁.動態調整選擇策略的改進蟻群算法[J].控制與決策，2008，23(2):225-228.

[5]劉立東，蔡淮. 自適應調整α，β參數的蟻群算法[J]. 計算機工程與設計，2007，28(20):4496-4497.

[6]蔡光躍，董恩清.遺傳算法和蟻群算法在求解TSP問題上的對比分析[J]. 計算機工程與應用，2007，43(10):96-98.

[7]HUANG Han，HAO Zhi-feng，WU Chun-guo.The convergence speed of ant colony optimization[J].Chinese Journal of Computers，2007，30(8):1344-1353.

[8]SHANG Yun-wei， QIU Yu-huang. A note on the extended Rosenbrock function[J].Evolutionary Computation，2006，14(1):119-126.

[9]STUTZLE T， HOOS H. MAX-MIN ant system[J].Future Generation Computer Systems，2000，16(8):889-914.

[10]STUTZLE T， DORIGO M. A short convergence proof for a class of ant colony optimization algorithms[J]. IEEE Trans on Evolutionary Computation，2002，6(4):358-365.