一種解決TSP問題的自適應(yīng)協(xié)同演化計算方法

王智廣，王興會，何文俊

(中國石油大學(xué)(北京)信息工程學(xué)院，北京 102249)

演化計算來自于達(dá)爾文的自然進(jìn)化理論，其通過使用種群、進(jìn)化、評估、迭代等方法來體現(xiàn)自然界中“優(yōu)勝劣汰”原則，以獲得問題的最優(yōu)解，常被用于組合優(yōu)化問題求解.演化計算是一種非常重要的算法思想，最初由Fogel在1952年博士論文中提出，由Holland和其學(xué)生提出的遺傳算法將這種思想推廣并進(jìn)行深度應(yīng)用[1]. 目前在演化計算思想上發(fā)展出了許多算法，主要包括兩個方面的內(nèi)容：一種是以遺傳算法、差分進(jìn)化[2]、演化編程為代表的演化算法；另一種是以蟻群算法[3]、粒子群算法[4]、蜂群算法[5]為代表的群智能算法.演化算法主要以自然進(jìn)化為理論依據(jù)，通過種群之間的迭代演化完成問題的求解.而群智能算法通過模擬自然界中的群智能生物(螞蟻、大雁、蜜蜂)行為來完成問題的求解.由于兩種類型的算法關(guān)注點不同，從而導(dǎo)致在解決問題時所產(chǎn)生的效果也是不同的.雖然現(xiàn)在沒有統(tǒng)一的理論來規(guī)定什么樣的問題適用于什么樣的演化算法.但是從解決問題的實踐來看，這兩種類型算法具有互補性.遺傳算法通過種群進(jìn)行目標(biāo)尋優(yōu)，其強調(diào)的是全局搜索能力而對局部的細(xì)致搜索不足，而蟻群算法通過信息素的正反饋來強化局部搜索能力，但其全局搜索能力不強，而全局搜索和局部搜索不足均可能導(dǎo)致早熟和停滯的現(xiàn)象方式.因此如果能夠?qū)煞N算法結(jié)合起來運行，將能夠彌補各自的缺點，最大程度地避免在演化計算中經(jīng)常出現(xiàn)的早熟、停滯現(xiàn)象.因此研究將這兩種算法相結(jié)合的協(xié)同演化算法是目前演化計算領(lǐng)域重要的研究方向.Khakmardan等人[6]利用EO算法與粒子群算法相結(jié)合的方法來降低搜索過程中選入局部最優(yōu)解.吳建輝等人[7]提出了一種基于競爭—合作的分層協(xié)同進(jìn)化免疫算法，通過對若干個子種群進(jìn)行低層免疫操作：局部最優(yōu)免疫優(yōu)勢、克隆擴增及克隆選擇算子、基于改進(jìn)粒子群優(yōu)化算法的抗體多樣性改善和高層遺傳操作：選擇、抗體遷移、變異，增強優(yōu)秀抗體實現(xiàn)親和度成熟的機會，提高抗體群分布的多樣性，以解決TSP問題.

本文提出一種自適應(yīng)的協(xié)同演化方法，通過動態(tài)評估方法將蟻群算法與遺傳算法有機結(jié)合起來，讓兩種算法相互切換運行，充分利用兩種算法的各自解決問題的優(yōu)點來對問題進(jìn)行求解.將在下面首先介紹這兩種算法的基本實現(xiàn)步驟，然后說明蟻群與遺傳算法協(xié)同演化的方法，最后通過對TSP問題的實驗測試來說明本方法在搜索速度、避免停滯、早熟等方面具有優(yōu)勢.

1 理論基礎(chǔ)

1.1 蟻群算法

蟻群算法模擬了螞蟻尋找食物的過程.每只螞蟻在搜素食物是根據(jù)其它螞蟻留下的信息素及自己的判斷來進(jìn)行搜索路徑選擇.每只螞蟻在面臨路徑選擇時，根據(jù)公式(1)來進(jìn)行判斷.

(1)

蟻群算法步驟如下：

步驟1：初始化.將迭代次數(shù)g初始化為1，并初始化Mk和q0(0

步驟2：對每只螞蟻根據(jù)公式(2)來選擇節(jié)點j.

(2)

其中,q是隨機變量(0

步驟3：使用公式(3)和(4)更新局部信息素:

(3)

(4)

步驟4：對每只螞蟻判斷是否已經(jīng)通過所有路徑節(jié)點，如果沒有通過，則返回步驟2繼續(xù)執(zhí)行，否則選擇目前蟻群中目前的最短路徑lmin.

步驟5：按照公式(5)和(6)更新全局信息素:

τij=(1-λ)τij+λΔτij,

(5)

(6)

其中，1-λ表示全局信息素的揮發(fā)速度，Q0是常量表示全局信息素的增長速率.

步驟6：如果迭代次數(shù)超過最大限制或者已經(jīng)得到合理的結(jié)果，則算法退出，否則初始化Mk(k∈m)并設(shè)置g:=g+1，返回步驟2繼續(xù)運行.

1.2 遺傳算法

遺傳算法根據(jù)生物信息學(xué)中的基因編碼及其進(jìn)化原理得到的，其廣泛應(yīng)用于各種優(yōu)化問題，有著很多變化的方法，但是其基本算法步驟主要包括以下幾步.

步驟1：初始化種群.對種群進(jìn)行相關(guān)編碼，并設(shè)置迭代次數(shù)g：=1.

步驟2：根據(jù)適應(yīng)度評估函數(shù)，從當(dāng)前種群選擇較好的m個個體.

步驟3：對此m個個體進(jìn)行交叉操作.

步驟4：對交叉后的后代按照一定概率進(jìn)行變異操作，并根據(jù)評估函數(shù)得到下一代種群.

步驟5：檢查是否滿足算法停止條件.如果滿足則停止，否則返回步驟2繼續(xù)運行.

1.3 遺傳算法和蟻群算法之間的聯(lián)系

在遺傳算法中，如果將一個種群看作為蟻群,則種群下個體為蟻群中一只螞蟻，算法中的交叉、變異來表示螞蟻的路徑選擇動作，基于適應(yīng)度評估函數(shù)的選擇操作能夠保存每一代蟻群之間的聯(lián)系.在蟻群算法中，每只螞蟻根據(jù)其啟發(fā)函數(shù)和信息素濃度選擇路徑，蟻群憑借各自留下的信息素來達(dá)到協(xié)同工作的目的[8]，每只螞蟻可以表示為遺傳算法中的一個個體，每一代蟻群可以表示為遺傳算法中的每代種群.蟻群算法更加強調(diào)個體的搜索過程，通過遺留信息素的正反饋操作來使得蟻群協(xié)同工作.遺傳算法更強調(diào)的是全局搜素能力，而蟻群算法更擅長局部搜索.因此兩個算法具備可結(jié)合性和相互彌補性.

2 自適應(yīng)協(xié)同演化方法

自適應(yīng)協(xié)同演化方法實現(xiàn)的基本思路是：如果在蟻群算法中搜索的路徑集中于某幾條，則將搜索過程轉(zhuǎn)換為遺傳算法來進(jìn)行；如果遺傳算法出現(xiàn)停滯、早熟等現(xiàn)象，則將搜索過程轉(zhuǎn)換為蟻群算法.自適應(yīng)的關(guān)鍵是對蟻群算法和遺傳算法的狀態(tài)評估.

2.1 算法收斂及多樣性判斷

在蟻群和遺傳算法運行中會出現(xiàn)收斂速度變慢、甚至出現(xiàn)停滯的現(xiàn)象.這是由種群的多樣性趨于一致所致.因此在下面的公式分別定義了這兩種算法的收斂速度、多樣性的評估函數(shù).

蟻群算法收斂速度表示為公式(8)，其中D(g)表示蟻群的搜索路徑結(jié)果，dk(g)表示第k個螞蟻的搜索路徑結(jié)果.

(8)

(9)

將蟻群的多樣性使用公式(10)和(11)表示:

(10)

(11)

其中，Oij表示蟻群算法的第i代搜素路徑結(jié)果與第j代搜索路徑結(jié)果之間的差異.P(g)表示第g代蟻群搜素的路徑集合.

(12)

(13)

2.2 基于遺傳算法和蟻群算法的自適應(yīng)協(xié)同模型

自適應(yīng)的選擇遺傳或蟻群算法運行需要對這兩種算法的運行狀態(tài)進(jìn)行評估，根據(jù)上面定義的收斂速度及種群多樣性函數(shù)，定義函數(shù)T(g)表示第g代兩個算法的運行狀態(tài)，如公式(14)所示.

(14)

其中，g表示迭代次數(shù)，C1和C2是常量.T(g)的值為布爾類型，如果得到結(jié)果為false則當(dāng)前算法繼續(xù)運行，否則將選擇另一個算法運行.

為使得兩個算法協(xié)作運行，需要對每種算法的運行結(jié)果進(jìn)行保存，當(dāng)切換到另一種算法運行時，可以從前一個算法運行結(jié)果基礎(chǔ)上繼續(xù)運行.具體的模型如圖1所示，兩個算法的切換通過每次迭代后的評估函數(shù)T(g)來進(jìn)行判斷.在最優(yōu)隊列中保存兩個算法得到的最優(yōu)結(jié)果，其可以作為這兩個算法被切換運行后初始化的種群.在遺傳算法運行結(jié)束后需要根據(jù)結(jié)果更新蟻群的全局信息素，以保障蟻群算法運行時能夠在遺傳算法結(jié)果基礎(chǔ)上繼續(xù)運行.

圖1 基于遺傳算法和蟻群算法的自適應(yīng)協(xié)同模型

3 實驗測試

為了測試此種自適應(yīng)協(xié)同演化方法的有效性，針對TSP問題使用TSPLIB庫進(jìn)行實驗測試.實驗過程中使用C++語言，在CPU3.2G、內(nèi)存4GB機器上實現(xiàn)了上述協(xié)同模型及相關(guān)算法、以及傳統(tǒng)的蟻群算法和遺傳算法，設(shè)置各個參數(shù)數(shù)據(jù)值為m=n/2,α=0.75,β=0.72,q0=0.81,Q=2000,Q0=1800,ρ=0.75,λ=0.85.而參數(shù)C1和C2取值隨TSP問題規(guī)模不同，而取不同數(shù)值，通過實驗測試，通常C1=n×10(n為TSP問題的節(jié)點規(guī)模)， 0.03≤C2≤0.06.在設(shè)置迭代次數(shù)限制為4000代時，將實現(xiàn)的算法運行15次得到的平均結(jié)構(gòu)如表1、表2和表3所示.在表中，TSPLIB表示測試集目前已知最優(yōu)結(jié)構(gòu)，GA表示遺傳算法，ACO表示蟻群算法，GACOEV表示此自適應(yīng)協(xié)同模型算法，eil51、lin105、a280、ftv100等表示測試數(shù)據(jù)類型.

表1 Symmetric TSP問題不同算法的數(shù)據(jù)結(jié)果比較

表2 Asymmetric TSP問題不同算法的數(shù)據(jù)結(jié)果比較

表3 不同算法的收斂時間比較

從表1～3中數(shù)據(jù)結(jié)構(gòu)看，本文提出的協(xié)作演化模型方法與傳統(tǒng)的遺傳算法或蟻群算法相比具有明確的優(yōu)勢，得到的最優(yōu)值明顯好過其它兩個算法，并且收效速度有著較大幅度的提高.針對a280問題，此模型方法的收斂速度約為遺傳算法的9倍，蟻群算法的2倍.

4 結(jié)語

針對遺傳算法和蟻群算法容易產(chǎn)生早熟、停滯等現(xiàn)象，分析這兩種算法的運行特點：遺傳算法全局搜索能力強；蟻群算法局部搜索能力強.在此基礎(chǔ)之上提出基于遺傳算法和蟻群算法的自適應(yīng)協(xié)同演化方法.通過定義種群多樣性、收斂速度的判斷函數(shù)以及算法運行評估函數(shù)來對目前算法運行狀態(tài)進(jìn)行評估，根據(jù)評估結(jié)果自動調(diào)整所要運行的算法，從而實現(xiàn)了遺傳算法和蟻群算法的協(xié)同演化運行.從TSP問題的實驗數(shù)據(jù)結(jié)果進(jìn)行分析，此協(xié)同演化方法明顯加快了收斂速度，提高了搜索問題的結(jié)果，并且比較好地抑制了遺傳算法和蟻群算法容易產(chǎn)生的早熟、停止等阻礙算法繼續(xù)有效率運行的現(xiàn)象.

[1]De Jong K. Evolutionary computation: a unified approach[C]//ACM.Proceeding of the 2007 GECCO Conference Companion on Genetic and Evolutionary Computation Conference(GECCO′07).New York:ACM,2007:3158-3171.

[2] Price K,Storn R M,Lampinen J A.Differential evolution: a practical approach to global optimization[M]. Berlin:Springer, 2005:13-55.

[3] Dorigo M.Optimization,learning and natural algorithms[D]. PhD thesis.Italie: Politecnico di Milano, 1992.

[4] Kennedy J, Eberhart R. Particle swarm optimization[C]//IEEE. Proceedings of IEEE International Conference on Neural Networks. Australia:IEEE, 1995:1942-1948.

[5] Pham DT,Ghanbarzadeh A,Koc E,et al. The bees algorithm, technical note[R].UK:Cardiff University, 2005.

[6] Khakmardan S, Poostchi H, Akbarzadeh M R. Solving traveling salesman problem by a hybrid combination of PSO and extremal optimization[C]//IEEE. The 2011 International Joint Conference on Neural Networks (IJCNN). California:IEEE,2011:1501-1507.

[7] 吳建輝, 章 兢, 張小剛, 等. 分層協(xié)同進(jìn)化免疫算法及其在TSP問題中的應(yīng)用[J]. 電子學(xué)報. 2011, 39(2):336-344.

[8] 朱慶保, 楊志軍. 基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J].軟件學(xué)報, 2004,15(2):185～192.