基于目標(biāo)函數(shù)變化率的混合蟻群遺傳算法

劉雪東，許 峰

1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001

2.安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001

基于目標(biāo)函數(shù)變化率的混合蟻群遺傳算法

劉雪東1，許 峰2

1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001

2.安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001

1 引言

隨著生命科學(xué)的迅猛發(fā)展，社會(huì)性動(dòng)物（如螞蟻、鳥(niǎo)群、魚(yú)群等）的自組織行為引起了人們的廣泛關(guān)注。許多學(xué)者對(duì)這些動(dòng)物的行為進(jìn)行數(shù)學(xué)建模并用計(jì)算機(jī)對(duì)其進(jìn)行仿真，群智能算法應(yīng)運(yùn)而生。

蟻群算法（Ant Colony Optimization，ACO）是近年來(lái)頗受?chē)?guó)內(nèi)外學(xué)者關(guān)注的一種新型模擬進(jìn)化算法，由意大利學(xué)者Dorigo M于1992年首先提出[1]，Nature曾多次對(duì)蟻群算法的研究成果進(jìn)行報(bào)道[2-4]。蟻群算法用蟻群在搜索食物過(guò)程中所體現(xiàn)出的尋優(yōu)能力來(lái)解決優(yōu)化問(wèn)題，其算法的基本思想是模仿螞蟻依賴信息素，通過(guò)螞蟻間正反饋的方法來(lái)引導(dǎo)每個(gè)個(gè)體的行為。

遺傳算法（Genetic Algorithm，GA）于1975年由美國(guó)Michigen大學(xué)的J.Holland教授等人受生物進(jìn)化論的啟發(fā)而提出的[5]。遺傳算法把生物進(jìn)化過(guò)程中的自然選擇、優(yōu)勝劣汰、適者生存和遺傳變異的思想應(yīng)用到優(yōu)化問(wèn)題中，是一種全局隨機(jī)搜索算法。

蟻群算法具有分布式、自組織、正反饋等優(yōu)點(diǎn)，缺陷是收斂速度較慢，易陷于局部最優(yōu)解。遺傳算法的優(yōu)點(diǎn)是自適應(yīng)、并行性、具有較強(qiáng)的全局收斂性，缺陷是局部搜索能力較弱。

將兩種或多種智能優(yōu)化算法按照某種規(guī)則相融合或在某種智能算法中引入其他優(yōu)化思想，形成混合優(yōu)化思想，可以有效地?fù)P長(zhǎng)避短，充分發(fā)揮智能算法的優(yōu)點(diǎn)，大大提高算法的各方面性能[6]。

考慮到蟻群算法和遺傳算法在收斂性上的互補(bǔ)性，有多位學(xué)者陸續(xù)提出了基于蟻群算法和遺傳算法的混合優(yōu)化算法[6]。這些混合算法通常采用固定進(jìn)化代數(shù)來(lái)控制兩種算法的調(diào)用，很有可能造成已經(jīng)早熟的種群還在進(jìn)行無(wú)用的進(jìn)化，影響算法的收斂速度。本文提出了一種基于目標(biāo)函數(shù)變化率的混合蟻群遺傳算法，在進(jìn)化過(guò)程中，根據(jù)目標(biāo)函數(shù)的變化率動(dòng)態(tài)地控制蟻群算法和遺傳算法的調(diào)用次數(shù)，并根據(jù)數(shù)值實(shí)驗(yàn)結(jié)果對(duì)新算法的全局和局部收斂性進(jìn)行了評(píng)測(cè)。

2 蟻群算法和遺傳算法

2.1 蟻群算法

用于優(yōu)化領(lǐng)域的蟻群算法吸收了生物界中螞蟻群體的行為特征，其基本原理是：

（1）螞蟻能感知小范圍區(qū)域內(nèi)的狀況，并判斷出是否有食物或其他同伴的信息素軌跡；

（2）螞蟻能連續(xù)不斷地釋放自己的信息素；

（3）螞蟻釋放的信息素濃度隨時(shí)間逐步減小。

螞蟻有能力在沒(méi)有任何提示下找到從其巢穴到食物的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物時(shí)，能在其走過(guò)的路上釋放信息素，隨著時(shí)間的推移該物質(zhì)會(huì)逐漸揮發(fā)。當(dāng)一定路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，其留下的信息素也越來(lái)越多，后來(lái)的螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度。而強(qiáng)度大的信息素會(huì)吸引更多的螞蟻，從而形成一種正反饋機(jī)制。通過(guò)這種正反饋機(jī)制，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短路徑。特別地，當(dāng)螞蟻巢穴與食物間出現(xiàn)障礙物時(shí)，螞蟻不僅可以繞過(guò)障礙物，而且通過(guò)蟻群信息素在不同路徑上的變化，經(jīng)過(guò)一段時(shí)間的正反饋，最終收斂到最短路徑。

蟻群算法在不同問(wèn)題中有不同的表現(xiàn)形式，但其核心步驟均為信息素軌跡強(qiáng)度的更新方式和螞蟻轉(zhuǎn)移概率的確定。本文采用下列螞蟻圈模型[7]：

若路徑(i，j)在t時(shí)刻信息素軌跡強(qiáng)度為τij，螞蟻k在路徑(i，j)上留下的單位長(zhǎng)度軌跡信息素?cái)?shù)量為，軌跡的持久性為ρ(0≤ρ＜1)，則軌跡強(qiáng)度的更新方程為：

設(shè)Zk為第k只螞蟻在本次循環(huán)中所走的路徑的長(zhǎng)度，則其中Q為一個(gè)常數(shù)。如果設(shè)ηij為路徑(i，j)的能見(jiàn)度，通常取為1/dij，dij為路徑(i，j)的長(zhǎng)度，路徑可見(jiàn)度的相對(duì)重要性為β(β≥0)，路徑軌跡的相對(duì)重要性為α(α≥0)，U為可行頂點(diǎn)集，則螞蟻k在t時(shí)刻的轉(zhuǎn)移概率為：

2.2 遺傳算法

遺傳算法的運(yùn)算對(duì)象是由個(gè)體組成的群體。在遺傳算法的運(yùn)算過(guò)程中，群體按照優(yōu)勝劣汰的法則進(jìn)行遺傳和進(jìn)化，將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，經(jīng)過(guò)若干代進(jìn)化后，在群體中會(huì)得到一個(gè)或一批優(yōu)良的個(gè)體，它們即對(duì)應(yīng)問(wèn)題的最優(yōu)解。

生物的進(jìn)化主要是通過(guò)染色體之間的交叉和染色體的變異來(lái)完成的。遺傳算法模擬這個(gè)進(jìn)化過(guò)程，對(duì)群體使用遺傳算子，從而得出新一代群體。

基本遺傳算法的運(yùn)算過(guò)程如下：

（1）選取適當(dāng)?shù)娜后w規(guī)模Μ、染色體編碼長(zhǎng)度l、進(jìn)化代數(shù)T、交叉概率Pc、變異概率Pm等參數(shù)，隨機(jī)生成規(guī)模為Μ的初始群體P(t)，t=0；

（2）解碼并計(jì)算適應(yīng)度；

（3）進(jìn)行選擇操作；

（4）進(jìn)行交叉操作；

（5）進(jìn)行變異操作，產(chǎn)生新一代種群P(t+1)；

（6）若t＜T，則t=t+1，轉(zhuǎn)（2），否則輸出最優(yōu)解，停機(jī)。

3 混合蟻群遺傳算法

蟻群算法已被證明是一種很有發(fā)展前景的求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）的有效方法。但與其他智能優(yōu)化方法一樣，蟻群算法不可避免地存在著一些缺陷，如初始信息素生成速度較慢，全局收斂性較差，易早熟等。

近年來(lái)，許多學(xué)者將蟻群算法與其他優(yōu)化算法相融合，相繼提出了多種混合蟻群算法，并將其應(yīng)用于不同的領(lǐng)域，取得了較好的效果。劉波將分布估計(jì)思想引入蟻群算法[8]；陳立華和張瀟提出了含有變異算子的混合蟻群算法，并將其應(yīng)用于水庫(kù)群優(yōu)化[9-10]；梁亮將Markov過(guò)程與蟻群算法相結(jié)合[11]；周永務(wù)在蟻群算法中引入2-opt算法，并將其應(yīng)用于多時(shí)間窗車(chē)輛路徑問(wèn)題[12]；杜占瑋提出了基于互信息的混合蟻群算法[13]；稅薇提出了與人工勢(shì)場(chǎng)相結(jié)合的混合蟻群算法[14]；丁建立[15]提出采用遺傳算法生成信息素分布，利用螞蟻算法求精確解，優(yōu)勢(shì)互補(bǔ)；毛寧[16]提出借助遺傳算法中的變異幫助蟻群算法提高跳出局部最優(yōu)解的能力；梁旭[17]提出了一種動(dòng)態(tài)蟻群混合遺傳算法，大大提高了蟻群算法的收斂速度。

本文提出一種基于目標(biāo)函數(shù)變化率的動(dòng)態(tài)混合蟻群遺傳算法（Dynamic Ant Colony Genetic Algorithm，DACGA），其基本思想是：根據(jù)目標(biāo)函數(shù)的變化率交叉地調(diào)用蟻群算法和遺傳算法。用蟻群算法的解作為遺傳操作的種子，每當(dāng)種群進(jìn)化接近停滯時(shí)，調(diào)用蟻群算法。這種方法可動(dòng)態(tài)地控制蟻群算法和遺傳算法的調(diào)用時(shí)機(jī)，再配合相應(yīng)的信息素更新方法，可以提高算法的收斂性。

動(dòng)態(tài)調(diào)用蟻群算法和遺傳算法的具體方法是：

定義：

其中：

(i=1,2,…,m;j=1,2,…,n)表示向量Xi的第j個(gè)分量。

對(duì)于離散優(yōu)化問(wèn)題，f(X)不存在梯度，則

其中，Xp，Xc分別表示父代和子代個(gè)體。

當(dāng)γij小于設(shè)定的閾值ε（通常取為10-2）時(shí)，選擇蟻群算法，否則選擇遺傳算法。

DACGA的流程如下：

（1）取定參數(shù)NGmin，NGmax，NKmax，α，β，ρ。

（2）螞蟻位置初始化。

（3）利用式（1）更新信息素，并轉(zhuǎn)（5），否則轉(zhuǎn)（4）。

（4）根據(jù)式（2）選擇下一節(jié)點(diǎn)。

（5）將螞蟻搜索到的初始解和全局最優(yōu)解作為遺傳算法的初始種群，進(jìn)行選擇、交叉、變異，更新種群。

（6）當(dāng)遺傳算法達(dá)到最小迭代次數(shù)NGmin時(shí)，則根據(jù)前述方法動(dòng)態(tài)選擇蟻群算法或遺傳算法。若選擇調(diào)用蟻群算法，則利用式（1）更新信息素，并轉(zhuǎn)（8）。

（7）當(dāng)遺傳算法達(dá)到最大迭代次數(shù)NGmax時(shí)，則轉(zhuǎn)（8），否則繼續(xù)遺傳操作。

（8）若混合算法的整體迭代次數(shù)達(dá)到NKmax，則輸出最優(yōu)解，算法結(jié)束，否則轉(zhuǎn)（2）。

4 算法的收斂性分析與性能評(píng)測(cè)

4.1 收斂性分析

混合蟻群遺傳算法的收斂性極為復(fù)雜，尚未完全解決。目前公認(rèn)的結(jié)論是[18]：基于螞蟻圈模型的蟻群算法和基本遺傳算法的混合算法是收斂的。

由于本文采用的是基于螞蟻圈模型的蟻群算法和基本遺傳算法，只是對(duì)調(diào)用兩種算法的條件作了改進(jìn)，所以本文提出的算法在理論上是收斂的。

4.2 性能評(píng)測(cè)

鑒于混合優(yōu)化算法已被公認(rèn)為解決車(chē)間調(diào)度問(wèn)題較為有效的方法[19]，下面用基于目標(biāo)函數(shù)變化率的DACGA算法對(duì)車(chē)間調(diào)度問(wèn)題中的兩個(gè)基準(zhǔn)測(cè)試問(wèn)題FT06和FT10[19]進(jìn)行仿真計(jì)算，并將計(jì)算結(jié)果與基本蟻群算法、基本遺傳算法和一種蟻群遺傳混合算法[16]（Ant Colony System Genetic Algorithm，ACSGA）的計(jì)算結(jié)果進(jìn)行比較，從而檢驗(yàn)新算法的收斂性能。

仿真程序采用Matlab編程，遺傳算法中，編碼長(zhǎng)度為10，種群規(guī)模為50，交叉概率為0.85，變異概率為0.1，NGmin=20，NGmax=50；蟻群算法中，α=1，β=1，ρ=0.5，Q=800，NKmax=300；動(dòng)態(tài)調(diào)用閾值ε=0.01。

考慮到計(jì)算結(jié)果的隨機(jī)性，表1和表2中給出的是20次實(shí)驗(yàn)結(jié)果的平均值。

表1 FT06的優(yōu)化指標(biāo)結(jié)果

表2 FT10的優(yōu)化指標(biāo)結(jié)果

表1和表2中分別給出了FT06和FT10的最優(yōu)值、平均值、標(biāo)準(zhǔn)差、20次仿真中求得最優(yōu)值（達(dá)到理論最優(yōu)解的95%即視為最優(yōu)值）的頻率及最小進(jìn)化代數(shù)。FT06和FT10的理論最優(yōu)解分別為55和930。

為了更直觀地反映DACGA在收斂性方面的改進(jìn)，圖1給出了DACGA與ACSGA求解FT10的對(duì)比進(jìn)化曲線。

圖1 FT10的DACGA和ACSGA進(jìn)化曲線

從表1、表2和圖1中可以很清楚地看出：

（1）ACO在最優(yōu)值、平均值和標(biāo)準(zhǔn)差指標(biāo)上優(yōu)于SGA，而SGA在收斂頻率和進(jìn)化代數(shù)指標(biāo)方面優(yōu)于ACO，即ACO局部收斂性較強(qiáng)而全局收斂性較弱，SGA全局收斂性較強(qiáng)而局部收斂性較弱。

（2）ACSGA和DACGA在所有指標(biāo)中均較ACO和SGA為優(yōu)，即混合蟻群遺傳算法的確可以優(yōu)勢(shì)互補(bǔ)，提高收斂性。

（3）相比較而言，DACGA較ACSGA在收斂性和收斂速度方面又有一定程度的提高。這表明，本文提出的ACO和SGA的動(dòng)態(tài)調(diào)用機(jī)制是有效的。

5 結(jié)束語(yǔ)

通過(guò)對(duì)蟻群算法和遺傳算法收斂性特點(diǎn)的分析，設(shè)計(jì)了一種基于目標(biāo)函數(shù)變化率的算法調(diào)用機(jī)制，提出了一種新的混合蟻群遺傳算法。新算法不僅實(shí)現(xiàn)了蟻群算法和遺傳算法的優(yōu)勢(shì)互補(bǔ)，而且通過(guò)動(dòng)態(tài)調(diào)用兩種算法減少了冗余迭代次數(shù)，提高了收斂速度。數(shù)值仿真結(jié)果顯示，新算法與蟻群算法相比有較強(qiáng)的全局收斂性，而與遺傳算法相比則有較強(qiáng)的局部收斂性。

最后要特別指出的是，蟻群算法與粒子群算法、人工免疫系統(tǒng)、分布估計(jì)算法、協(xié)同進(jìn)化算法等均為近年來(lái)出現(xiàn)的新型進(jìn)化范例，理論體系尚不完善，收斂性等關(guān)鍵理論問(wèn)題有待進(jìn)一步研究。

[1]Dorigo M.Optimization，learning and natural algorithms[D]. Dipartimento di Elettronica，Politecnico di Milano，Italy，1992.

[2]Bonabeau E，Dorigo M，Theraulaz G.Inspiration for optimization from social insect behavior[J].Nature，2000，406（6）：39-42.

[3]Michael J B K，Jean-Bernarrd B，Laurent K.Ant-like task and recruitment in cooperation robots[J].Nature，2000，406（31）：992-995.

[4]Jackson D E，Holcombe M，Ratnieks F L W.Trail geometry gives polarity to ant foraging networks[J].Nature，2004，432（7019）：907-909.

[5]Holland J H.Adaptation in natural and artificial system[M]. Ann Arbor：The University of Michigan Press，1975.

[6]梁旭，黃明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2011.

[7]Dorigo M，Bonabeau E，Theraulaz G.Ant algorithms and stigmergy[J].Future Generation Computer System，2000，16（8）：851-871.

[8]劉波，李惠光，吳惕華，等.一種新的混合蟻群算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39（6）：154-161.

[9]陳立華，梅亞?wèn)|，楊娜，等.混合蟻群算法在水庫(kù)群優(yōu)化調(diào)度中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)，2009，42（5）：661-665.

[10]張瀟，王江晴.混合蟻群算法在車(chē)輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程，2011，37（24）：190-192.

[11]梁亮，郭波.基于混合蟻群算法的產(chǎn)品開(kāi)發(fā)過(guò)程優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐，2009，29（10）：118-128.

[12]彭碧濤，周永務(wù).多時(shí)間窗車(chē)輛路徑問(wèn)題的混合蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（31）：28-31.

[13]杜占瑋，楊永健，孫永雄，等.基于互信息的混合蟻群算法及其在旅行商問(wèn)題上的應(yīng)用[J].東南大學(xué)學(xué)報(bào)，2011，41（3）：478-481.

[14]稅薇，葛艷，韓玉，等.基于混合蟻群算法的無(wú)人機(jī)航路規(guī)劃系統(tǒng)[J].仿真學(xué)報(bào)，2011，23（3）：574-577.

[15]丁建立，陳增強(qiáng)，袁著祉.遺傳算法與螞蟻算法的融合[J].計(jì)算機(jī)研究與發(fā)展，2003，40（9）：1351-1356.

[16]毛寧，顧軍華.蟻群遺傳混合算法[J].計(jì)算機(jī)應(yīng)用，2006，26（7）：1692-1694.

[17]梁旭，劉鵬飛，黃明.一種新的螞蟻遺傳混合算法應(yīng)用研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2008，14（8）：1566-1570.

[18]丁建立，陳增強(qiáng)，袁著祉.遺傳算法與螞蟻算法的融合的馬爾可夫收斂性分析[J].自動(dòng)化學(xué)報(bào)，2004，30（4）：629-634.

[19]王凌.車(chē)間調(diào)度及其遺傳算法[M].北京：清華大學(xué)出版社，2003：58-59.

LIU Xuedong1,XU Feng2

1.School of Computer Science and Engineering,Anhui University of Science and Technology,Huainan,Anhui 232001,China
2.School of Science,Anhui University of Science and Technology,Huainan,Anhui 232001,China

According to the complementary on convergence of ant colony algorithm and genetic algorithm,a hybrid ant colony genetic algorithm based on the change rate of objective function is put forward.The basic idea of new algorithm is that the solutions of ant colony algorithm are given as the initial population of genetic algorithm,and the ant colony algorithm and genetic algorithm are dynamically called according to the change rate of objective function.When population evolutionary is close to stagnation, ant colony algorithm is called.This approach can dynamically control the call timing of ant colony algorithm and genetic algorithm. Together with the pheromone update methods,the convergence of hybrid algorithm is improved.The new algorithm is used to solve the Job shop scheduling benchmarks problem,and the simulation results show that the global and local convergence performance of new algorithm has been significantly improved compared with basic hybrid ant colony genetic algorithm.

Ant Colony Optimization（ACO）;Genetic Algorithm（GA）;change rate of objective function;Job shop scheduling benchmarks problem

根據(jù)蟻群算法和遺傳算法收斂性互補(bǔ)的特點(diǎn)，提出了一種基于目標(biāo)函數(shù)變化率的混合蟻群遺傳算法。該算法的基本思想是：用蟻群算法的解作為遺傳算法的初始種群，根據(jù)目標(biāo)函數(shù)的變化率交叉地調(diào)用蟻群算法和遺傳算法。每當(dāng)種群進(jìn)化接近停滯時(shí)，調(diào)用蟻群算法。這種方法可動(dòng)態(tài)地控制蟻群算法和遺傳算法的調(diào)用時(shí)機(jī)，再配合相應(yīng)的信息素更新方法，以提高算法的收斂性。將新算法用于車(chē)間調(diào)度基準(zhǔn)測(cè)試問(wèn)題，仿真結(jié)果表明，與常規(guī)混合蟻群遺傳算法相比，新算法的全局收斂性和局部收斂性有了明顯的提高。

蟻群算法；遺傳算法；目標(biāo)函數(shù)變化率；車(chē)間調(diào)度基準(zhǔn)問(wèn)題

A

TP301.6

10.3778/j.issn.1002-8331.1210-0278

LIU Xuedong,XU Feng.Hybrid ant colony genetic algorithm based on change rate of objective function.Computer Engineering and Applications,2013,49（18）：41-44.

安徽省教育廳自然科學(xué)基金項(xiàng)目（No.2010kb236）。

劉雪東（1986—），男，碩士研究生，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算、群智能計(jì)算；許峰（1963—），男，教授，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算、群智能計(jì)算。E-mail：fxu@aust.edu.cn

2012-10-26

2013-01-30

1002-8331（2013）18-0041-04

CNKI出版日期：2013-03-19 http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.001.html