結(jié)合ABC算法動(dòng)態(tài)分級(jí)的雙蟻態(tài)蟻群算法

李順東，游曉明，劉 升

1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海201620

2.上海工程技術(shù)大學(xué) 管理工程學(xué)院，上海201620

1 引言

旅行商問題[1]（Traveling Salesman Problem，TSP）是經(jīng)典NP-hard組合優(yōu)化問題，它可以簡(jiǎn)單地描述為：旅行商從規(guī)定的城市列表中選擇一個(gè)城市作為起點(diǎn)，不重復(fù)地遍歷完所有城市，最終再返回到初始位置，從而找到一條最短的閉合回路。目前解決TSP問題的算法[2-5]有很多，其中蟻群算法由于良好的并行性、正反饋性以及極強(qiáng)的魯棒性等特點(diǎn)，成為最有效的方法之一。

20世紀(jì)90年代，意大利學(xué)者Dorigo等人受自然界蟻群覓食行為的啟發(fā)創(chuàng)新性地提出了蟻群算法（Ant System，AS）[6]，但算法存在收斂速度慢，易陷于局部最優(yōu)等問題。在此基礎(chǔ)上，1996年Dorigo等[7]結(jié)合Q-learning思想提出了全新機(jī)制的ACS算法。該算法沿用了兩種信息素更新方式，加快了算法收斂速度。同期，Stutzle等人[8]又提出了最大最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS），為每條路徑上信息素濃度設(shè)定了上、下限閾值區(qū)間，避免信息素濃度無(wú)限累加而停滯，提高了算法的多樣性。此后，眾多專家學(xué)者在這兩者算法的基礎(chǔ)上做出了改進(jìn)：文獻(xiàn)[9]提出了一種動(dòng)態(tài)信息素策略的改進(jìn)算法，通過動(dòng)態(tài)改變偽隨機(jī)因子的閾值，來平衡算法的多樣性和收斂速度。文獻(xiàn)[10]通過融合模擬退火算法，提出了一種自適應(yīng)模擬退火蟻群算法，提高了解的質(zhì)量。以上改進(jìn)算法，雖然在一定程度上取得了進(jìn)步，但在蟻群協(xié)同分工機(jī)制方面仍然存在著不足。

針對(duì)不足，Dorigo等人曾提出過精英螞蟻系統(tǒng)（Elitist Ant System，EAS），通過對(duì)螞蟻分級(jí)，分別執(zhí)行不同的信息素更新策略，突出了最優(yōu)路徑螞蟻的精英作用，為蟻群的路徑選擇增加導(dǎo)向性，加快了系統(tǒng)的收斂速度。Bullnheimer等人[11]還提出過RAS形式的螞蟻分級(jí)系統(tǒng)等。實(shí)驗(yàn)證明，在蟻群算法的基礎(chǔ)上實(shí)行分級(jí)機(jī)制，效果良好，改善了群智能優(yōu)化算法本身存在的收斂性和多樣性的矛盾。此后，很多其他分級(jí)機(jī)制的算法應(yīng)運(yùn)而生。其中，人工蜂群算法表現(xiàn)較為突出。

自然界中蜂群采蜜以分工協(xié)作而聞名，不同級(jí)別的蜂種各司其職共同完成采蜜任務(wù)。根據(jù)這一特性，Karaboga等[12]提出了人工蜂群算法（Artificial Bee Colony，ABC），算法通過適應(yīng)度不同將蜂群進(jìn)行分級(jí)、分工協(xié)作，既凸顯了精英蜂群的引領(lǐng)作用，加快找到優(yōu)質(zhì)蜜源速度，又通過偵察蜂群隨機(jī)搜索更多優(yōu)質(zhì)蜜源，提高了算法解的精度。

鑒于此，本文在ACS算法基礎(chǔ)上，融合了人工蜂群算法分級(jí)思想，提出了一種動(dòng)態(tài)分級(jí)的改進(jìn)蟻群算法（ABC-ACS）。通過引入適應(yīng)度分級(jí)算子，將蟻群劃分為兩種蟻態(tài)：尋優(yōu)蟻和偵查蟻。尋優(yōu)蟻的作用是搜索較優(yōu)路徑，經(jīng)過若干次迭代最終找到最優(yōu)解；偵查蟻則負(fù)責(zé)開發(fā)其他路徑，搜索更多優(yōu)化解。兩類螞蟻分別執(zhí)行不同加權(quán)系數(shù)的動(dòng)態(tài)信息素更新策略，使得較優(yōu)路徑和非較優(yōu)路徑之間的信息素產(chǎn)生一定的濃度差，既突出了尋優(yōu)蟻的導(dǎo)向作用，又不會(huì)影響偵查蟻繼續(xù)搜索其他更優(yōu)解的能力，從而不僅增加了算法導(dǎo)向性，加快收斂速度，又保持了算法的多樣性，避免陷入局部最優(yōu)。此外，在每次迭代結(jié)束后兩類螞蟻執(zhí)行優(yōu)良解交換策略，提高了解的質(zhì)量。最后，通過ACS全局最優(yōu)路徑信息素更新策略，使算法收斂速度進(jìn)一步提高。另外，為了使所得解的質(zhì)量更優(yōu)，算法還融合3-opt算子對(duì)其繼續(xù)優(yōu)化。

2 相關(guān)工作

2.1 ACS蟻群算法

2.1.1 路徑構(gòu)建

ACS算法模型中每只螞蟻從城市i到城市j之間轉(zhuǎn)移，是利用偽隨機(jī)概率公式進(jìn)行選擇的，公式如下：

其中，τij為城市i和城市j之間信息素濃度的大?。籥llowedk∈{ }n-tabuk表示螞蟻k下一步可選擇的城市；ηij(t)是啟發(fā)式函數(shù)，表示螞蟻k從城市i轉(zhuǎn)移到城市j的期望度，且表示相鄰城市i和j之間的距離；αβ分別表示信息啟發(fā)式因子和期望啟發(fā)式因子，αβ值越大，對(duì)下一條路徑的選擇影響越大。q是區(qū)間[0，1]上均勻分布的隨機(jī)變量；q0是區(qū)間[0，1]上的可調(diào)參數(shù)；當(dāng)q≤q0時(shí)，螞蟻k根據(jù)偽隨機(jī)比例公式（1）選擇最優(yōu)路徑；當(dāng)q＞q0時(shí)，則按照s即輪盤賭公式進(jìn)行路徑選擇，如式（2）所示：

本文ABC-ACS沿用了ACS的偽隨機(jī)比例規(guī)則，其先進(jìn)之處在于：算法在路徑構(gòu)建時(shí)，螞蟻以q0概率選擇當(dāng)前可能最優(yōu)的移動(dòng)方式，又以1-q0概率有偏向性地探索各條邊。通過合理調(diào)整參數(shù)q0，就可以有效地調(diào)節(jié)算法對(duì)于每條新路徑選擇的優(yōu)先級(jí)和探索度，從而決定算法應(yīng)該集中探索當(dāng)前最優(yōu)區(qū)域還是其他區(qū)域，確保在局部加權(quán)信息素更新時(shí)，對(duì)不同探索度的路徑引入相應(yīng)比例的權(quán)重進(jìn)行更新，即較優(yōu)路徑加權(quán)大，其他路徑加權(quán)小，進(jìn)而保證了局部信息素動(dòng)態(tài)加權(quán)更新規(guī)則的準(zhǔn)確性。

2.1.2 信息素更新

ACS蟻群算法的更新機(jī)制分為局部信息素更新和全局信息素更新兩部分。

局部信息素更新：當(dāng)每只螞蟻完成一次周游后，算法便會(huì)對(duì)其走過的路徑進(jìn)行局部信息素更新。局部信息素更新是對(duì)所有螞蟻都進(jìn)行更新，其作用是為了縮短最優(yōu)路徑和非最優(yōu)路徑之間信息素的差距，增加算法的多樣性，提高算法全局搜索能力，避免陷入局部最優(yōu)。其公式如（3）所示：

式中，τ0為每條路徑上的初始信息素濃度；ρ是局部信息素?fù)]發(fā)率。

全局信息素更新：當(dāng)所有螞蟻都完成一次迭代之后，算法只對(duì)當(dāng)前最優(yōu)路徑上的信息素進(jìn)行更新，通過算法的正反饋?zhàn)饔?，使得最?yōu)路徑和非最優(yōu)路徑上的信息素的差距逐漸拉大，為蟻群的路徑選擇增加指向性，加快了算法的收斂速度，如式（4）所示：

式中：

其中，ρ是全局信息素?fù)]發(fā)率，Δτij是信息素增量，Lgb是當(dāng)前最優(yōu)路徑的長(zhǎng)度。

2.2 3-opt搜索算子

K-opt是TSP問題中廣泛應(yīng)用的啟發(fā)式搜索方法。其中，3-opt[13](K=3)是效率較高的局部?jī)?yōu)化算法。該算法主要通過對(duì)螞蟻構(gòu)建的路徑進(jìn)行局部?jī)?yōu)化，提高解的質(zhì)量，從而得到最優(yōu)解。其流程大致為：

步驟1螞蟻完成路徑構(gòu)建，生成Hamilton回路T。

步驟2在回路T上隨機(jī)選取三個(gè)點(diǎn)切開重組，形成新的閉合回路，如圖1所示。

步驟3將新的回路和舊的回路T進(jìn)行解的比較，保留其中較優(yōu)解。

步驟4重復(fù)執(zhí)行該算法，直到找到最優(yōu)解。

圖1 3-opt路徑重組

3 改進(jìn)蟻群算法

3.1 ABC算法動(dòng)態(tài)分級(jí)策略

3.1.1 ABC算法分級(jí)思想

人工蜂群（ABC）算法是由土耳其學(xué)者Karaboga于2005年提出的，它是受到自然界中蜂群采蜜行為啟發(fā)的群智能優(yōu)化算法，其模型主要是由：蜜源、引領(lǐng)蜂、跟隨蜂和偵查蜂四個(gè)要素組成。在求解TSP[14-17]時(shí)，ABC算法首先根據(jù)蜜源i(i=1,2,…,NP)的質(zhì)量計(jì)算對(duì)應(yīng)的適應(yīng)度f(wàn)iti；然后根據(jù)適應(yīng)度值的大小將蜂群劃分為引領(lǐng)蜂、偵查蜂和跟隨蜂三種類型：引領(lǐng)蜂負(fù)責(zé)搜索蜜源；引領(lǐng)蜂歸巢分享蜜源信息，跟隨蜂按一定比例選擇是否跟隨；偵查蜂負(fù)責(zé)搜索空間內(nèi)其他蜜源。

3.1.2 動(dòng)態(tài)適應(yīng)度分級(jí)算子

蟻群算法自提出以來就存在著收斂速度慢、易陷入局部最優(yōu)、協(xié)同機(jī)制不夠完善等問題，而目前單種群?jiǎn)涡螒B(tài)蟻群算法無(wú)法實(shí)現(xiàn)收斂速度和多樣性之間的平衡，因此本文借鑒了人工蜂群算法分級(jí)的思想，引入動(dòng)態(tài)適應(yīng)度分級(jí)算子，將蟻群劃分為尋優(yōu)蟻和偵查蟻兩種蟻態(tài)并行搜索。其中尋優(yōu)蟻負(fù)責(zé)較優(yōu)路徑的搜索，通過較高加權(quán)系數(shù)的信息素更新規(guī)則，突出較優(yōu)路徑上的信息素強(qiáng)度，增強(qiáng)其導(dǎo)向性，提高算法的收斂速度；而偵查蟻則負(fù)責(zé)開發(fā)較優(yōu)路徑以外的其他路徑，尋找更多優(yōu)質(zhì)解，保證了算法的多樣性，增強(qiáng)其跳出局部最優(yōu)的能力，提高了解的質(zhì)量。因此，通過動(dòng)態(tài)分級(jí)蟻群進(jìn)行并行搜索，實(shí)現(xiàn)了多樣性與收斂速度之間的平衡。

定義動(dòng)態(tài)適應(yīng)度分級(jí)算子如公式（6）、（7）所示：

式中，fiti表示每只螞蟻對(duì)應(yīng)的適應(yīng)度值(0＜fiti≤1)，如公式（6）所示，其值由lengthmin和lengthi的比值所決定，lengthmin表示當(dāng)前迭代中的最短路徑；lengthi表示每只螞蟻迭代一次的路徑長(zhǎng)度；根據(jù)所計(jì)算的適應(yīng)度f(wàn)iti值的不同，將整個(gè)蟻群劃分為兩類，如公式（7）所示，M為偵查蟻與尋優(yōu)蟻的分級(jí)閾值界點(diǎn)(0＜M＜1)：當(dāng)0＜fiti≤M時(shí)，為偵查蟻；當(dāng)M＜fiti≤1時(shí)，則為尋優(yōu)蟻。M值并非任意選取，其大小直接影響算法整體的求解精度。因?yàn)镸值過大時(shí)，偵查蟻的數(shù)量則會(huì)增多，從而導(dǎo)致大量的無(wú)用搜索，影響算法的收斂速度；而當(dāng)M值過小時(shí)，尋優(yōu)蟻的數(shù)量過多又會(huì)導(dǎo)致某些較優(yōu)路徑上的信息素過度累積而陷入局部最優(yōu)，影響算法的多樣性以及解的質(zhì)量。本文通過大量的實(shí)驗(yàn)對(duì)比，驗(yàn)證了當(dāng)M=0.7時(shí)，算法的性能表現(xiàn)最佳，求解精度最優(yōu)。

3.2 改進(jìn)的動(dòng)態(tài)信息素更新策略

為了更好地平衡蟻群算法多樣性和收斂速度之間的矛盾，本文在ACS局部信息素更新策略的基礎(chǔ)上，引入了加權(quán)[18]系數(shù)和適應(yīng)度值，使得不同級(jí)別的螞蟻執(zhí)行不同加權(quán)系數(shù)的動(dòng)態(tài)信息素更新策略，如公式（8）～（10）所示：

式中：

其中，λ1λ2為加權(quán)系數(shù)；fiti為對(duì)應(yīng)螞蟻計(jì)算的適應(yīng)度值。

需要說明的是，原ACS算法的局部信息素更新策略對(duì)于每只螞蟻都是相同的，整個(gè)算法只依靠全局更新策略來增強(qiáng)較優(yōu)路徑上的信息素濃度，不能很好地突出其導(dǎo)向作用，從而在較短的時(shí)間內(nèi)找到最優(yōu)解，因此，本文融合了EAS的精英思想對(duì)局部信息素更新公式進(jìn)行加權(quán)改進(jìn)：

（1）當(dāng)M＜fiti≤1時(shí)，為尋優(yōu)蟻，其局部信息素更新公式為式（8）、（9）。

（2）當(dāng)0＜fiti≤M時(shí)，為偵查蟻，其局部信息素更新公式為式（8）、（10）。

其中，λ1為尋優(yōu)蟻群的局部信息素加權(quán)系數(shù)，λ2為偵查蟻群局部信息素加權(quán)系數(shù)，并定義λ1＞λ2，目的是為了區(qū)分兩類蟻群搜索路徑上的信息素濃度，突出較優(yōu)路徑的精英導(dǎo)向作用，從而縮短算法找到最優(yōu)解的周期。通常λ1只能略大于λ2，因?yàn)棣?與λ2之間相差過大都會(huì)導(dǎo)致算法過早停滯而陷入局部最優(yōu)，影響算法求解的精度。因此，本文在進(jìn)行大量實(shí)驗(yàn)對(duì)比之后，驗(yàn)證了當(dāng)λ1=4、λ2=2時(shí)效果最好，故取之為兩類螞蟻局部信息素更新改進(jìn)策略的加權(quán)系數(shù)。

此外，改進(jìn)的局部信息素更新策略還引入了螞蟻的適應(yīng)度值fiti，目的是為了讓每只螞蟻能夠根據(jù)自身適應(yīng)度值的大小動(dòng)態(tài)地進(jìn)行局部信息素更新，因?yàn)檫m應(yīng)度值大的螞蟻，搜索的路徑相對(duì)較優(yōu)，通過改進(jìn)的局部信息素更新策略便會(huì)獲得更高濃度的信息素更新，導(dǎo)向作用也隨之增強(qiáng)。

整體而言，在原ACS算法的基礎(chǔ)上，動(dòng)態(tài)改進(jìn)局部信息素更新策略，既保持了每條路徑上都有信息素增加的特性，又使其濃度和影響力根據(jù)自身適應(yīng)度的不同動(dòng)態(tài)變化，從而形成路徑間的濃度差，即適應(yīng)度高的較優(yōu)路徑增加的信息素高，適應(yīng)度低的次之。當(dāng)算法陷入局部最優(yōu)時(shí)，偵查蟻依然具備搜索其他更優(yōu)路徑的能力，保證了算法的多樣性，提高全局尋優(yōu)的能力，從而有效地幫助算法跳出局部最優(yōu)；進(jìn)一步，通過較優(yōu)路徑的精英導(dǎo)向作用加快了收斂速度，從而使全局尋優(yōu)能力與局部尋優(yōu)能力之間達(dá)到平衡。此外，算法的全局更新依然沿用ACS算法的更新策略，即在所有螞蟻完成一次迭代之后，只更新當(dāng)前最優(yōu)路徑上的信息素，如式（4）所示，目的是為了進(jìn)一步突出最優(yōu)路徑的導(dǎo)向作用，從而加快收斂速度。

3.3 優(yōu)良解的交換策略

當(dāng)iter=1時(shí)，算法利用ACS的路徑構(gòu)建公式和信息素更新公式完成第一次迭代，并計(jì)算相應(yīng)的適應(yīng)度值來將蟻群進(jìn)行劃分：當(dāng)0＜fiti≤M時(shí)，為偵查蟻；當(dāng)M＜fiti≤1時(shí)，則為尋優(yōu)蟻。

從第二代開始(iters≥2)，算法首先會(huì)對(duì)上一代劃分的兩類螞蟻進(jìn)行路徑構(gòu)建，然后再通過不同加權(quán)系數(shù)的局部信息素公式進(jìn)行信息素更新，且在每一次迭代之后，都要判斷兩類螞蟻是否需要進(jìn)行優(yōu)良解的交換，主要思路為：若偵查蟻構(gòu)建的路徑集合中存在‖ length ‖＜‖ length ‖，則對(duì)兩類螞蟻執(zhí)行優(yōu)良解的交換：

交換后的兩類螞蟻身份職能互換，即原來較優(yōu)的偵查蟻轉(zhuǎn)變?yōu)樾碌膶?yōu)蟻，而被替換掉的尋優(yōu)蟻則淪為偵查蟻，執(zhí)行偵查蟻的職能。在完成優(yōu)良解交換之后，系統(tǒng)開始進(jìn)行下一輪迭代；若一次迭代中不存在偵查蟻優(yōu)于尋優(yōu)蟻的解情況，算法則不進(jìn)行優(yōu)良解交換，直接進(jìn)入下一輪迭代。優(yōu)良解交換策略的大致過程如圖2所示。

圖2 優(yōu)良解交換

通過優(yōu)良解的交換策略，可以使每一代尋優(yōu)蟻解的集合不斷更新，始終保持較優(yōu)路徑集合的質(zhì)量更優(yōu)；偵查蟻不受尋優(yōu)蟻導(dǎo)向作用的影響，繼續(xù)搜索當(dāng)前較優(yōu)路徑以外的其他路徑，保證了算法的多樣性，增強(qiáng)了算法全局尋優(yōu)能力。當(dāng)偵查蟻尋得更優(yōu)解時(shí)，則與當(dāng)前較優(yōu)路徑集合進(jìn)行優(yōu)良解交換，從而幫助算法跳出局部最優(yōu)，提高了解的精度。優(yōu)良解的交換設(shè)定是從第二代開始，直到尋優(yōu)蟻解的集合不再發(fā)生變化或者達(dá)到最大迭代數(shù)為止。

3.4 ABC-ACS算法流程

本文所提出的結(jié)合ABC算法動(dòng)態(tài)分級(jí)的雙蟻態(tài)蟻群算法的算法流程可以簡(jiǎn)單地描述如下。

步驟1參數(shù)初始化。

步驟2 NC=1，將m只螞蟻分別分配n個(gè)城市。

步驟3螞蟻k根據(jù)式（1）和輪盤賭的方式（2）進(jìn)行下一城市的轉(zhuǎn)移。

步驟4所有螞蟻完成第一次迭代，根據(jù)公式（6）、（7）計(jì)算相應(yīng)的適應(yīng)度值，并將蟻群分級(jí)為尋優(yōu)蟻和偵查蟻，NC=NC+1。

步驟5完成第NC次迭代，算法根據(jù)式（1）完成兩類螞蟻路徑的構(gòu)建。

步驟6然后，根據(jù)式（8）～（10）分別對(duì)尋優(yōu)蟻和偵查蟻執(zhí)行局部信息素更新。

步驟7當(dāng)所有螞蟻完成迭代，兩類螞蟻進(jìn)行優(yōu)良解交換，若達(dá)到交換條件，則根據(jù)式（11）進(jìn)行交換；否則，不進(jìn)行交換。

步驟8根據(jù)式（4）進(jìn)行全局信息素更新。

步驟9當(dāng)NC≤NCmax時(shí)，NC=NC+1，跳轉(zhuǎn)到步驟5；否則，轉(zhuǎn)到步驟10。

步驟10輸出最優(yōu)解。

算法的整體框架如圖3所示。

算法流程：

ABC-ACS Algorithm for TSP

1.Procedure ABC-ACS（）

2.Begin：

3.Initialize the pheromone and parameters

4.Calculate the distance between cities

5.#Algorithm：ACS

6.for iter=1 do

7.for i←1 to m do#m as ant'snumber

8.for j←2 to n do#n as cities'number

9.Construct ant solutions

10.Compute fitness&Classify ants

11.end-for

12.end for

13.end-for

14.Update pheromones

15.#Algorithm：ABC-ACS

16.for iter←2 to NC do

17.for i←1 to m do#m as ant'snumber

18.for j←2 to n do#n as cities'number

19.Construct ant solutions

20.Update dynamic local pheromones

21.if(‖ length ‖＜‖ length ‖)do

22.Exchange excellent solutions

23.end if

24.end for

25.end for

26.end for

27.Update pheromones

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

由算法流程分析可知ABC-ACS算法的復(fù)雜度為O(1×m×(n-1)+(NC-1)×m×(n-1))，具體可分為兩個(gè)部分：其中，第一代算法沿用的是ACS算法進(jìn)行路徑構(gòu)建、求解，其復(fù)雜度為O(1×m×(n-1))；而從第二代開始，根據(jù)第一代所產(chǎn)生解的適應(yīng)度將種群分為兩個(gè)蟻態(tài)繼續(xù)進(jìn)行迭代，其算法復(fù)雜度為O((NC-1)×m×(n-1))。所以，改進(jìn)后算法的總體復(fù)雜度為O(NC×m×n)，而ACS算法的復(fù)雜度為O(NC×m×n)，可見本文算法的復(fù)雜度并未發(fā)生改變。

3.6 算法收斂性分析

3.6.1 經(jīng)典ACO算法收斂性分析定理[8]一旦找到最優(yōu)解s*，則公式（12）成立：

對(duì)于經(jīng)典蟻群算法而言，只存在全局信息素更新機(jī)制，其更新公式為τij(t+1)=(1-ρ)τij(t)+Δτij(t)。假設(shè)一次迭代之后任意一條邊(i,j)上的信息素的最大增量為qf(s*)，則根據(jù)更新公式可知，第一次迭代中信息素最大值是(1-ρ)τ0+qf(s*)，第二次迭代中最大值是(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此類推，第θ次迭代中最大值。由于信息素具有揮發(fā)作用，信息素水平只能漸近于最大值水平，故。所以，一旦找到最優(yōu)解，所有邊上的信息素值都會(huì)收斂于τmax。此外，Dorigo等定義過每條邊都存在相同的初始信息素τ0，其值為大于0的極小常數(shù)，因此，τmin＞0。所以，對(duì)于任意一條邊而言，其信息素上下限為[τmin,τmax]。

根據(jù)式（2）蟻群算法的路徑構(gòu)建公式可知，任意一個(gè)可行解都有其選擇概率p，且其下界pmin如公式（13）所示：

其中，Nc為成分集合C的勢(shì)；τmin為信息素值的下界。

需要說明的是，可行選擇概率p取到下界(p=pmin)時(shí)，即出現(xiàn)最優(yōu)可行解增加的信息素濃度最低為τmin，而其他Nc-1個(gè)非最優(yōu)可行解的信息素皆為最大值τmax的最差情況，那么求得任意的一般性解s′，包括任意最優(yōu)解s*∈S*的概率，其中，n＜+∞是序列的最大長(zhǎng)度，這足夠讓一只螞蟻找到一個(gè)最優(yōu)解，P*(θ)有如下下限：

3.6.2 ABC-ACS算法收斂性分析

ABC-ACS算法與經(jīng)典蟻群算法的不同點(diǎn)主要體現(xiàn)在幾個(gè)方面：第一，ABC-ACS沿用了偽隨機(jī)比例規(guī)則，使得算法在路徑選擇和局部信息素加權(quán)更新時(shí)更具偏向性和準(zhǔn)確性；第二，ABC-ACS中并不是所有邊上的信息素都會(huì)蒸發(fā)，只有屬于至今最優(yōu)解的邊才會(huì)蒸發(fā)信息素；第三，ABC-ACS中每只螞蟻在構(gòu)造解時(shí)都會(huì)使用局部信息素更新規(guī)則，在螞蟻經(jīng)過一條邊(i,j)之后立即更新素；第四，對(duì)局部信息素更新規(guī)則進(jìn)行動(dòng)態(tài)加權(quán)改進(jìn)；第五，采用了優(yōu)良解交換策略。

ABC-ACS算法具有局部、全局兩種更新機(jī)制，更新公式可以記為τij(t+1)=(1-ρ)τij(t)+ρb這種形式，在全局更新中，b=qf(sbs)；在局部更新中，b=τ0。當(dāng)算法迭代θ次之后，信息素的最大值為，當(dāng)θ→∞時(shí)，信息素的最大值漸近于。其次，τ0為信息素下限值。

根據(jù)公式（1）偽隨機(jī)比例規(guī)則可知，如果邊(i,j)的信息素值不是最大的，那么選中(i,j)的概率就是算法進(jìn)行隨機(jī)選擇的概率(1-q0)與在隨機(jī)選擇中選擇邊(i,j)的概率的乘積。因?yàn)樾畔⑺厝≈荡嬖谏舷孪?，所以任意一個(gè)可行解選擇都有概率p＞0，且存在下界pmin，其公式如式（13）所示。因此，構(gòu)造任意可行解的概率都大于0，任意一條邊(i,j)選中的概率下界為(1-q0)pmin。根據(jù)公式（14）可得，ABC-ACS的下限公式為(θ)=1-(1-(1-q0))θ，則當(dāng)?shù)螖?shù)θ足夠大時(shí)，

4 實(shí)驗(yàn)對(duì)比與結(jié)果分析

為了檢驗(yàn)ABC-ACS算法的性能，本章選取了標(biāo)準(zhǔn)TSBLIP庫(kù)中19個(gè)經(jīng)典的TSP實(shí)例進(jìn)行仿真，每個(gè)實(shí)例進(jìn)行10次實(shí)驗(yàn)，并將其結(jié)果與傳統(tǒng)算法，最新改進(jìn)算法以及其他算法作對(duì)比。

4.1 與經(jīng)典算法對(duì)比

4.1.1 與經(jīng)典算法性能對(duì)比分析

對(duì)比分析了算法的性能，驗(yàn)證了本文算法求解質(zhì)量更高，對(duì)比結(jié)果及算法搜索到的最優(yōu)路徑迭代圖如表1和圖4所示。從表1可以看出，ABC-ACS在各種規(guī)模的TSP實(shí)例中，無(wú)論是最優(yōu)解、平均解還是誤差率等方面都優(yōu)于ACS和MMAS。其中，在Oliver30～pr107等小規(guī)模的TSP問題中，ABC-ACS都能以最快的速度找到標(biāo)準(zhǔn)最優(yōu)解，算法尋優(yōu)能力和收斂速度較ACS和MMAS均明顯提升；而隨著城市規(guī)模擴(kuò)大，雖然ABC-ACS算法迭代數(shù)較大，但解的質(zhì)量顯著提高：中規(guī)模TSP測(cè)試集的誤差均小于0.1%，其中，在ch130的測(cè)試上，算法所得解為6 113，而標(biāo)準(zhǔn)最優(yōu)解為6 110，誤差率僅為0.05%；在KroB150的測(cè)試中，更是達(dá)到了標(biāo)準(zhǔn)最優(yōu)解。而對(duì)于pr226～rand300等大規(guī)模TSP問題的測(cè)試中，誤差也都小于1%。這是因?yàn)閷?duì)蟻群進(jìn)行動(dòng)態(tài)分級(jí)，并且執(zhí)行優(yōu)良解交換策略的結(jié)果，既保證了算法的多樣性，提高了算法的全局搜索能力，避免了陷入全局最優(yōu)，又優(yōu)化了解的質(zhì)量。因此，同樣規(guī)模的測(cè)試集，ACS、MMAS花較少的迭代數(shù)但卻陷入早熟、停滯狀態(tài)，而ABC-ACS算法依然具有很好的多樣性和全局搜索能力可以繼續(xù)搜尋更優(yōu)的解，充分說明了ABC-ACS算法的性能良好，且求解精度更高。

4.1.2 與經(jīng)典算法收斂速度對(duì)比分析

為了更加充分比較ABC-ACS與經(jīng)典算法的性能，本文又選取了eil51等不同規(guī)模的8個(gè)TSP實(shí)例對(duì)其收斂速度進(jìn)行對(duì)比，結(jié)果如圖5所示。

由圖5所示，ABC-ACS在解決eil51等小規(guī)模TSP問題時(shí)，都能以最快的速度找到最優(yōu)解，這是由于尋優(yōu)蟻精英導(dǎo)向作用的影響，大大縮減了前期蟻群的搜索周期，提高了算法搜索效率；在求解KroA150等中規(guī)模的TSP問題時(shí)，雖然迭代數(shù)有所增大，但整體還是快于ACS、MMAS，且解的質(zhì)量更高，標(biāo)準(zhǔn)最優(yōu)解為26 524，ABC-ACS所得解為26 550，誤差率僅為0.1%。而對(duì)于求解KroA200等大規(guī)模TSP測(cè)試時(shí)，前期收斂速度依然很快，且后期種群多樣性依然好，這是由于ABC-ACS算法融合了人工蜂群分級(jí)的思想，對(duì)蟻群進(jìn)行了動(dòng)態(tài)分級(jí)，增加了算法搜索的多樣性，避免陷入局部最優(yōu)。由于每一代搜索完成之后，算法都會(huì)執(zhí)行優(yōu)良解交換策略，故與ACS、MMAS相比，ABC-ACS算法后期收斂速度稍慢，但求解精度更高。

4.1.3 算法多樣性對(duì)比分析

為了進(jìn)一步驗(yàn)證改進(jìn)算法的多樣性，本文以KroA100測(cè)試集為例，設(shè)置代碼執(zhí)行斷點(diǎn)，統(tǒng)計(jì)算法執(zhí)行到200、500、1 000、1 500以及2 000代時(shí)個(gè)體多樣性的變化情況，并與ACS算法作對(duì)比分析，結(jié)果如圖6所示，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為標(biāo)準(zhǔn)差值（用以衡量算法每次迭代的多樣性）。

通過圖6多樣性圖對(duì)比可以看出：ABC-ACS算法整體多樣性要優(yōu)于ACS算法，且設(shè)置斷點(diǎn)執(zhí)行代碼對(duì)比不同迭代數(shù)時(shí)兩個(gè)算法的個(gè)體多樣性情況，可以發(fā)現(xiàn)ABC-ACS依然更優(yōu)。

其中，500～1 000代ABC-ACS多樣性下降趨勢(shì)明顯，這是由于算法改進(jìn)了局部信息素更新規(guī)則，動(dòng)態(tài)加權(quán)系數(shù)的引入，使得較優(yōu)路徑上信息素增加的濃度要高于非較優(yōu)路徑，從而突出了尋優(yōu)蟻的導(dǎo)向作用，導(dǎo)致選擇較優(yōu)路徑的螞蟻數(shù)大幅增多，加快了算法的收斂速度，因此多樣性下降幅度很大；而1 000～1 500代，多樣性又有所上升，這是因?yàn)閭刹橄伈皇軐?yōu)蟻導(dǎo)向作用的影響，而去搜索非較優(yōu)路徑以發(fā)現(xiàn)更多優(yōu)化解，并且通過優(yōu)良解交換策略將發(fā)現(xiàn)的更優(yōu)解與尋優(yōu)蟻進(jìn)行交流互換，從而幫助算法跳出局部最優(yōu)，故多樣性得以增加；算法執(zhí)行到后期1 500～2 000代，多樣性雖然有所下降，但依然高于ACS算法。所以，總體而言，改進(jìn)后的ABCACS算法較ACS算法保持了良好的多樣性，并且通過動(dòng)態(tài)加權(quán)的局部信息素更新規(guī)則，加快了算法的收斂速度。此外，兩類螞蟻各司其職、優(yōu)良解交換，增強(qiáng)了算法全局尋優(yōu)的能力，提高了解的質(zhì)量（ABC-ACS找到的最優(yōu)解是21 282，為標(biāo)準(zhǔn)最優(yōu)解；ACS找到的最優(yōu)解為21 292，存在誤差）。

表1 ABC-ACS、ACS、MMAS在不同TSP測(cè)試集的性能對(duì)比

圖4 最優(yōu)路徑

4.2 與最新蟻群改進(jìn)算法對(duì)比分析

為了更好地說明ABC-ACS算法求解精度高，本文又選取了劉中強(qiáng)等[9]提出的D-ACS和袁汪凰等[10]提出的SA-MMAS兩種最新的蟻群改進(jìn)算法與eil51等不同規(guī)模的TSP問題進(jìn)行性能對(duì)比，結(jié)果如表2所示。

明顯可以看出：ABC-ACS在求解選取的各個(gè)規(guī)模TSP問題時(shí)幾乎都能尋得最優(yōu)解，其中KroA150和KroA200雖然沒達(dá)到最優(yōu)解，但誤差都控制在很小的范圍之內(nèi)，且各方面表現(xiàn)皆優(yōu)于D-ACS和SA-MMAS。

圖5 收斂速度對(duì)比

表2 ABC-ACS、D-ACS、SA-MMAS性能對(duì)比

4.3 與其他優(yōu)化算法對(duì)比分析

為了進(jìn)一步驗(yàn)證ABC-ACS算法的可行性以及性能的高效，本文還將其與最新粒子群改進(jìn)算法IMRGHPSO[3]、蜂群改進(jìn)算法Proposed ABC[15]進(jìn)行對(duì)比，其結(jié)果如表3所示。

通過結(jié)果對(duì)比可以直觀地看出：ABC-ACS求解旅行商問題精度更高、性能更好，各個(gè)規(guī)模的表現(xiàn)皆優(yōu)于最新的粒子群改進(jìn)算法IMRGHPSO和蜂群改進(jìn)算法Improved ABC，足以說明其可行性以及求解問題的性能高效。

綜合以上所有數(shù)據(jù)對(duì)比及分析表明：ABC-ACS算法既增加了導(dǎo)向性，提高了搜索效率，縮短了收斂周期；又增加了多樣性，提高了全局搜索能力，能夠跳出局部最優(yōu)，發(fā)現(xiàn)更多優(yōu)化解；再加上優(yōu)良解交換策略的影響，使得算法求解精度更高。其中，結(jié)合表1和圖5可以看出，在解決中小規(guī)模TSP問題時(shí)，ABC-ACS均能以最快的速度找到最優(yōu)解；而在解決少數(shù)的大規(guī)模TSP問題時(shí)，在沒有找到標(biāo)準(zhǔn)最優(yōu)解的情況下，由于其良好的多樣性，不會(huì)很快收斂而陷入局部最優(yōu)，與經(jīng)典ACS、MMAS算法相比求解質(zhì)量更好。結(jié)合表2可以看出，ABC-ACS不僅跟傳統(tǒng)的蟻群算法相比有優(yōu)勢(shì)，對(duì)比最新的蟻群改進(jìn)算法其性能優(yōu)勢(shì)仍然明顯。而結(jié)合表3可以進(jìn)一步直觀地看出，ABC-ACS與其他最新的智能優(yōu)化改進(jìn)算法相比其表現(xiàn)還是更優(yōu)。所以整體來看，改進(jìn)后的ABC-ACS算法在解決TSP問題時(shí)既具備較快的收斂速度，又有較好的多樣性。而且，無(wú)論是對(duì)比經(jīng)典的蟻群算法，還是對(duì)比最新的蟻群改進(jìn)算法，又或是其他最新的改進(jìn)優(yōu)化算法，ABC-ACS算法皆表現(xiàn)得更優(yōu)，性能更好，實(shí)用性很強(qiáng)。

表3 ABC-ACS、Improved ABC、IMRGHPSO性能對(duì)比

圖6 多樣性對(duì)比

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

本文提出動(dòng)態(tài)分級(jí)的改良蟻群算法，結(jié)合人工蜂群算法分級(jí)的思想，將蟻群劃分為偵查蟻和尋優(yōu)蟻兩個(gè)蟻態(tài)進(jìn)行分工合作解決TSP問題。其中，尋優(yōu)蟻增加導(dǎo)向性，提高收斂速度；偵查蟻增加多樣性，避免陷入局部最優(yōu)。然后，通過優(yōu)良解的交換，對(duì)所求解的質(zhì)量進(jìn)行優(yōu)化。最后，應(yīng)用ACS全局信息素更新策略，突出全局最優(yōu)路徑的精英導(dǎo)向作用，使算法很快找到最優(yōu)解。經(jīng)過多次不同規(guī)模的TSP實(shí)驗(yàn)，以及與經(jīng)典蟻群算法、最新改進(jìn)算法還有其他最新優(yōu)化算法全方位對(duì)比得出：本文算法是可行有效的，在解決TSP問題時(shí)收斂速度明顯提高，而大規(guī)模TSP問題質(zhì)量更優(yōu)。下一步將深入研究蟻群算法多種群之間的交流，進(jìn)一步優(yōu)化大規(guī)模TSP問題解的質(zhì)量和收斂速度。