王智廣，王興會(huì)，何文俊

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

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

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

1 理論基礎(chǔ)

1.1 蟻群算法

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

(1)

蟻群算法步驟如下：

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

步驟2：對(duì)每只螞蟻根據(jù)公式(2)來(lái)選擇節(jié)點(diǎn)j.

(2)

其中,q是隨機(jī)變量(0

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

(3)

(4)

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

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

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

(5)

(6)

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

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

1.2 遺傳算法

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

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

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

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

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

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

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

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

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

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

2.1 算法收斂及多樣性判斷

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

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

(8)

(9)

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

(10)

(11)

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

(12)

(13)

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

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

(14)

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

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

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

3 實(shí)驗(yàn)測(cè)試

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

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

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

表3 不同算法的收斂時(shí)間比較

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

4 結(jié)語(yǔ)

針對(duì)遺傳算法和蟻群算法容易產(chǎn)生早熟、停滯等現(xiàn)象，分析這兩種算法的運(yùn)行特點(diǎn)：遺傳算法全局搜索能力強(qiáng)；蟻群算法局部搜索能力強(qiáng).在此基礎(chǔ)之上提出基于遺傳算法和蟻群算法的自適應(yīng)協(xié)同演化方法.通過(guò)定義種群多樣性、收斂速度的判斷函數(shù)以及算法運(yùn)行評(píng)估函數(shù)來(lái)對(duì)目前算法運(yùn)行狀態(tài)進(jìn)行評(píng)估，根據(jù)評(píng)估結(jié)果自動(dòng)調(diào)整所要運(yùn)行的算法，從而實(shí)現(xiàn)了遺傳算法和蟻群算法的協(xié)同演化運(yùn)行.從TSP問(wèn)題的實(shí)驗(yàn)數(shù)據(jù)結(jié)果進(jìn)行分析，此協(xié)同演化方法明顯加快了收斂速度，提高了搜索問(wèn)題的結(jié)果，并且比較好地抑制了遺傳算法和蟻群算法容易產(chǎn)生的早熟、停止等阻礙算法繼續(xù)有效率運(yùn)行的現(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問(wèn)題中的應(yīng)用[J]. 電子學(xué)報(bào). 2011, 39(2):336-344.

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