呂金秋,游曉明,劉 升

(上海工程技術(shù)大學(xué)a.電子電氣工程學(xué)院;b.管理學(xué)院,上海201620)

基于α-鄰近的改進蟻群算法

呂金秋a,游曉明a,劉 升b

(上海工程技術(shù)大學(xué)a.電子電氣工程學(xué)院;b.管理學(xué)院,上海201620)

為克服傳統(tǒng)蟻群系統(tǒng)(ACS)在較大規(guī)模問題計算中易陷入局部最優(yōu),以及求解精度較低等不足,提出一種新的改進蟻群算法。該算法引入最小1-樹中的α-鄰近概念,能更好地反映給定邊屬于最優(yōu)回路的概率,通過轉(zhuǎn)換鄰接矩陣,計算出最優(yōu)回路的下界,以此提高α值的精度,并給出適應(yīng)性探索策略,加入3-opt領(lǐng)域搜索算子,有效提高優(yōu)化解的精度。實驗結(jié)果表明,該算法具有更好的全局尋優(yōu)能力,與ACS等算法相比能獲得更加優(yōu)化的解。

蟻群系統(tǒng);α-鄰近;最小1-樹;下界;適應(yīng)性策略;旅行商問題

1 概述

旅行商問題(Traveling Salesman Problem, TSP)[1]是組合優(yōu)化問題領(lǐng)域中研究和關(guān)注次數(shù)最多的問題之一,其可以描述成在一張帶權(quán)完全無向圖中,尋找一條具有最小權(quán)值的漢密爾頓回路。蟻群優(yōu)化(Ant Colony Optimization,ACO)算法[2]作為一種新型的智能群體協(xié)作算法,可以直接應(yīng)用到TSP中。盡管第一個ACO算法(螞蟻系統(tǒng)(Ant System,AS))得到的優(yōu)化結(jié)果遜于其他TSP經(jīng)典算法,但它為一系列擴展算法的出現(xiàn)提供了靈感。這些擴展的算法具有分布式計算、自學(xué)習(xí)、魯棒性強和易與其他算法相結(jié)合的優(yōu)點[3],已廣泛應(yīng)用于調(diào)度問題、分配問題、圖像處理等諸多領(lǐng)域。

此外,大量學(xué)者針對蟻群算法及其應(yīng)用展開了研究。比如,文獻[4]提出了多種群的概念,利用不同群落搜索解空間,從而極大程度上避免了算法陷入局部最優(yōu)解;文獻[5]提出了基于超頂點交流策略的并行蟻群算法,通過減少各種群的之間的通信量提高了算法效率;文獻[6]采用雙重最鄰近插入法(dual nearest insertion)初始化信息素,利用最優(yōu)解的下界強化學(xué)習(xí),并結(jié)合了L-K鄰域搜索算法;文獻[7]提出量子蟻群算法,即采用量子比特的概率幅表示螞蟻的當(dāng)前位置,采用量子旋轉(zhuǎn)門更新螞蟻的位置,從而使搜索空間加倍,算法的精確度和魯棒性得以增強;文獻[8]定義一種新的方向信息素來刻畫尋優(yōu)過程中的全局信息,從而可以較好地克服算法停滯現(xiàn)象,并在最優(yōu)路徑的基礎(chǔ)上提高了解的全局性。

本文將α-鄰近的思想引入到啟發(fā)函數(shù)ηij的計算中,得出一種新的啟發(fā)函數(shù)計算公式,該啟發(fā)函數(shù)值更能反映出一條邊屬于最優(yōu)回路的概率。隨后,通過轉(zhuǎn)換鄰接矩陣,計算最優(yōu)回路的下界,從而提高α的精度。此外,還提出了一種新的選擇策略——適應(yīng)性探索策略,即在進化前期通過刺激螞蟻選擇信息素較弱的路徑,擴大蟻群種群多樣性,在進化后期加速種群的收斂。

2 算法描述

2.1 算法框架

本文算法(α-AACS)的框架以偽代碼的形式給出,如下:

輸入TSP測試數(shù)據(jù)

輸出遍歷路徑

2.2 基于最小1-樹的啟發(fā)函數(shù)

在原始的蟻群系統(tǒng)(Ant Colony System,ACS)中,位于城市i的螞蟻個體k根據(jù)偽隨機比例規(guī)則選擇下一個訪問的城市j。具體如下[2]:

其中,q是均勻分布在區(qū)間[0,1]中的一個隨機變量,q0(0≤q0≤1)是一個參數(shù);J是根據(jù)下式給出的概率分布產(chǎn)生出來的一個隨機變量(α=1):

其中,ηij=1/dij為啟發(fā)函數(shù);α為信息啟發(fā)式因子;β為期望啟發(fā)式因子;代表了位于城市i的螞蟻個體k可以繼續(xù)訪問的城市的集合,即所有未被螞蟻k訪問的城市集合。

此轉(zhuǎn)移規(guī)則在一定程度上阻礙算法搜索到最優(yōu)路徑。假設(shè)一條邊不屬于其2個頂點的最近的鄰近邊集,而卻屬于最優(yōu)回路的邊集,這種情況下算法就很難尋得最優(yōu)解。因此,本文引入了α-nearest[9]的概念,它可以更好反映一條邊屬于最優(yōu)回路的概率。

定義1設(shè)圖G=(N,E),則其1-樹是指在圖G′=(N{1},E)(1為圖G的第一個頂點)的生成樹中加入2條與點1相連的邊所生成的圖形。那么,圖G的最小1-樹就是邊長總和最小的1-樹。

定義2設(shè)最小1-樹T的長度為L(T),T+(i,j)為包含邊(i,j)的最小1-樹的長度,則邊(i,j)的α值由下式求得:

設(shè)β(i,j)為在最小1-樹中加入邊(i,j)時去除的邊的長度,則α(i,j)=c(i,j)-β(i,j),其中,c(i,j)表示邊(i,j)的歐式距離。如圖1所示,若(j1,j2)是最小1-樹的一條邊,i是最小1-樹中的一點(i≠j1,j2)。增加邊(i,j2)后會產(chǎn)生一個閉合回路,點j1位于此回路上,那么β(i,j2)即為β(i,j1)和c(j1,j2)中的最大值。

圖1 β(i,j2)計算結(jié)構(gòu)

設(shè)b和mark為2個一位數(shù)組,其中,b[j]=β(i,j),數(shù)組mark用來表示b[j]已針對點i計算并被賦值。數(shù)組b[j]的計算分為2步:首先計算從節(jié)點i到最小1-樹的根節(jié)點的路徑上的所有點的b值,這些點的mark[j]=i;然后再向前計算剩下所有點的b值。隨后,α值的計算將在內(nèi)循環(huán)中進行。本文計算α值的偽代碼如下:

下面給出了新的基于α-鄰近的啟發(fā)函數(shù)的計算步驟。這里,φ為一正常量參數(shù)。

步驟1用Prim算法[10]計算圖G′=(N{1},E)的最小生成樹;

步驟2在最小生成樹中加入2條與點1相連的最短邊,即得圖G的最小1-樹;

步驟3計算每條邊的α(i,j)值;

步驟4ηij=1/[α(i,j)+φ]。

2.3 下界計算

在2.2節(jié)中,α值較理想的估算了一條邊屬于最優(yōu)回路的概率。實驗結(jié)果表明一條邊的α值比其長度更能代表其屬于最優(yōu)回路的可能性。然而,α值的精度可以通過對原始的鄰接矩陣做一個簡單的轉(zhuǎn)換而大大提高。轉(zhuǎn)換公式如下:

其中,向量π=(π1,π2,…,πn)。當(dāng)鄰接矩陣C= (cij)轉(zhuǎn)換到新的矩陣D=(dij)的時,D的最優(yōu)回路同時也是C的最優(yōu)回路,只是長度增加了2∑πi。設(shè)Tπ為D的最小1-樹,那么其長度L(Tπ)即是D的最優(yōu)回路長度的下界,同時,w(π)=L(Tπ-2∑πi也就是C的最優(yōu)回路長度的下界,即要找到一個向量π=(π1,π2,…,πn)使得下界w(π)最大。當(dāng)w(π)＞w(0)時,從D求得的α值比從C求得的α值能更好地反映一條邊屬于最優(yōu)回路的可能性。

本文使用次梯度優(yōu)化(subgradient optimization)迭代法[11]來求w(π)最大值。迭代公式為πk+1=πk+tk(0.7vk+0.3vk-1),其中,vk為次梯度向量(v-1=v0);tk為步長(正數(shù))。次梯度向量計算式為vk=dk-2,其中,向量dk中的元素為當(dāng)前最小1-樹中每個節(jié)點的度。此迭代法使得最小1-樹中節(jié)點的度逐漸變?yōu)?,即形成一回路。下面給出了次梯度優(yōu)化的步驟:

步驟1設(shè)k=0,π0=0,W=-∞。

步驟2求最小一樹Tkπ。

步驟4則W=max(W,w(πk))。

步驟5計算vk=dk-2,其中,向量dk的元素是中節(jié)點的度。

步驟6 如果vk=0(即為最優(yōu)回路),或者滿足終止條件,則算法結(jié)束;否則,進入下一步。

步驟7 更新步長tk+1=2tk,直到W不在增長, (t0=1)。

步驟8計算:

其中,v-1=v0。

步驟9k=k+1返回到步驟2。

文獻[12]已經(jīng)證明,當(dāng)tk→0(k→0),∑tk=∞時,W總會收斂到w(π)的最大值。

2.4 適應(yīng)性探索策略

在式(1)中,參數(shù)q0決定著蟻群是選擇當(dāng)前可能的最優(yōu)移動方式還是探索其他路徑。換言之,通過調(diào)整q0可以調(diào)節(jié)算法對新路徑的探索度,從而決定蟻群是應(yīng)該集中搜索至今最優(yōu)路徑附近的區(qū)域,還是應(yīng)該探索其他區(qū)域。因此,本文的適應(yīng)性探索策略是指在進化前期設(shè)定較小的q0值來增加種群多樣性,在進化后期設(shè)定較大的q0值以加速算法收斂。

2.5 3-opt鄰域搜索

3-opt鄰域搜索是指在原回路的基礎(chǔ)上改變最多3條邊得到的長度更短的新的回路。本文使用α值設(shè)定候選集,即α值越小,則這條邊在候選集的排名越靠前,并且候選集長度設(shè)為5。表1給出了532個城市分別用距離成本c值、α值和改進過后的α值作為候選集設(shè)定標(biāo)準(zhǔn)時,最優(yōu)回路中的邊在各自候選集中的排名比例[9]。3種情況的平均排名分別為2.4%,2.1%,1.7%。顯然,采用改進后的α值,平均排名比例明顯提高。

表1 TSP各最優(yōu)邊在候選集中的排名比例%

在原回路上去掉3條邊得到3個子路徑,有4種方式可以將這3個子路徑重新組合成回路,如圖2所示。

圖2 4種3-opt交換方式

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

由文獻[13]可知,原ACS算法的時間復(fù)雜度為T(n)=O(Nc·n2·m),其中,n為TSP的規(guī)模;m為螞蟻數(shù)目;Nc為最大迭代次數(shù)。本文算法中計算α值算法的時間復(fù)雜度為O(n2),3-opt鄰域搜索的時間復(fù)雜度為O(n3),故本文算法的時間復(fù)雜度為T(n)=O(Nc·n2·m)+O(Nc·n3)。由此可見,在TSP的規(guī)模n和螞蟻數(shù)目m相等的情況下,本文算法時間復(fù)雜度沒有增加。

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

為證明本文算法的有效性,本節(jié)利用標(biāo)準(zhǔn)測試集TSPLIB[14]中的實例進行了大量的實驗,并與其他算法的實驗結(jié)果進行了比較。對每一個測試實例和每一種算法進行10次實驗。

表2針對6種不同的測試實例,比較了本文算法(α-AACS)、ACS+3opt和ACS的實驗結(jié)果。由表2可知,在Eil51和Kroa150問題中,本文算均能獲得最優(yōu)解;在Kroa100、Kroa200和Pr264問題中,本文算法均能獲得與已知最優(yōu)解極其相近的解,誤差可近似為0;在大規(guī)模問題Lin318中,本文算法所求解的誤差為0.37%,比ACS算法縮小了約7%。由此可見,α-AACS的性能勝于其他2種算法,并且能獲得最優(yōu)解或接近最優(yōu)解。

表2 3種算法實驗結(jié)果對比

圖3給出針對Kroa150測試實例[14]3種算法的收斂曲線,其中,路徑長度為虛值無單位。

圖3 3種算法關(guān)于Kroa150測試實例的收斂曲線

表3比較了在本文算法中采用不同q0值,并應(yīng)用到不同的測試實例中得到的回路的平均長度(虛值)?？梢钥闯?本文算法采用第3組q0時在3個測試問題中所獲解的平均長度均優(yōu)于前2組解的平均長度。

表3 本文算法不同條件下回路的平均長度對比

由此可見,當(dāng)q0_1=0.3,q0_2=0.9,算法能夠獲得更好的結(jié)果,并且在尋優(yōu)過程中具有較好的穩(wěn)定性。圖4是針對Kora200測試實例采用3組參數(shù)得到的收斂曲線。由此得,本文算法中參數(shù)q0的值設(shè)定為q0_1=0.3,q0_2=0.9時所獲解最佳。

圖4 本文算法Kroa150測試實例下的收斂曲線

4 結(jié)束語

本文提出一種新的蟻群優(yōu)化算法(α-AACS)。引入最小1-樹的α-nearest用來計算啟發(fā)信息值,給出通過計算最優(yōu)回路的下界提高α值精度的方法。此外,適應(yīng)性探索選擇策略的提出和3-opt鄰域搜索的加入提高了優(yōu)化解的精度。實驗結(jié)果表明,該算法能獲得較大規(guī)模TSP問題的全局最優(yōu)值或接近最優(yōu)值。今后將研究一般性k-opt子交換鄰域搜索,并將其應(yīng)用到蟻群優(yōu)化算法中。

[1] Stutzle T,Hoos H.MAX-MIN Ant System and Local Search for the Traveling Problem[C]//Proceedings of IEEEInternationalConferenceonEvolutionary Computation.Indianapolis,USA:IEEE Press,1997: 309-315.

[2] Dorigo M,Stutzle T.Ant Colony Optimization[M]. Cambridge,USA:MIT Press,2004.

[3] 金 弟,楊 博,劉 杰,等.復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測——基于隨機游走的蟻群算法[J].軟件學(xué)報, 2012,23(3):451-464.

[4] Chen Fa.A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem[J].Information Sciences,2004,166(4):67-81.

[5] 章春芳.基于超頂點交流策略的并行蟻群算法[J].江南大學(xué)學(xué)報:自然科學(xué)版,2007,6(6):895-899.

[6] Zhang Ying,Li Lijie.MST Ant Colony Optimization with Lin-Kerninghan Local Search for the Traveling Salesman Problem[C]//Proceedings of International Symposium on Computational Intelligence and Design. Wuhan,China:[s.n.],2008:344-347.

[7] 李 煜,馬 良.用量子蟻群算法求解大規(guī)模旅行商問題[J].上海理工大學(xué)學(xué)報,2012,34(4):355-358.

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

[9] Helsgaun K.An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic[J].European JournalofOperationalResearch,2000,126(1): 106-130.

[10] Prim R C.Shortest Connection Networks and Some Generalizations[J].Bell System Technical Journal, 1957,36(1):1389-1401.

[11] Held M,Karp R M.The Traveling-salesman Problem and Minimum Spanning Trees:Part II[J].Mathematical Programming,1971,1(1):16-25.

[12] Poljak B T.A General Method of Solving Extremum Problems[J].Soviet Mathematics:Doklady,1967, 8(1):593-597.

[13] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005.

[14] University of Heidelberg.TSPLIB Website[EB/OL]. (2013-11-21).http://www.iwr.Uni-heidelberg.de/ groups/comopt/software/TSPLIB95/tsp.

編輯 劉 冰

Improved Ant Colony Algorithm Based on α-nearest

LV Jinqiua,YOU Xiaominga,LIU Shengb
(a.College of Electronic and Electrical Engineering;b.School of Management, Shanghai University of Engineering Science,Shanghai 201620,China)

In order to overcome the disadvantages that traditional Ant Colony System(ACS)is easy to fall into local optimum and low-precision for large-scale problems,this paper presents an improved ant colony optimization algorithm. The algorithm introduces α-nearest in the minimum1-tree,which better reflects the chances of a given link being a member of an optimal tour.It improves α-nearest precision by transforming the adjacency matrix and computes a lower bound.Besides,it proposes the adaptive exploration strategy and 3-opt local search.Experimental results show that this algorithm has a better global searching ability in finding the best solutions and can obtain better solutions than ACS,etc.

Ant Colony System(ACS);α-nearest;minimum1-tree;lower bound;adaptation strategy;Travelling Salesman Problem(TSP)

呂金秋,游曉明,劉 升.基于α-鄰近的改進蟻群算法[J].計算機工程,2015,41(2):184-188.

英文引用格式:Lv Jinqiu,You Xiaoming,Liu Sheng.Improved Ant Colony Algorithm Based on α-nearest[J].Computer Engineering,2015,41(2):184-188.

1000-3428(2015)02-0184-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.02.035

國家自然科學(xué)基金資助項目(61075115);上海市教委科研創(chuàng)新基金資助重點項目(12ZZ185)。

呂金秋(1991-),男,碩士,主研方向:智能信息處理,嵌入式系統(tǒng);游曉明、劉 升,教授、博士。

2014-03-12

:2014-04-10E-mail:yxm6301@163.com