莫亞?wèn)|，游曉明+，劉 升

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

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

旅行商問(wèn)題（traveling salesman problem，TSP）是經(jīng)典的組合優(yōu)化問(wèn)題。該問(wèn)題主要描述為：一位旅行商人從任意起始城市出發(fā)，由一個(gè)城市移動(dòng)到另一城市，要求能夠不重復(fù)遍歷整個(gè)國(guó)家的所有城市最終回到起始出發(fā)點(diǎn)，且構(gòu)成的回路之和最小，即構(gòu)成最小哈密頓回路。目前解決TSP問(wèn)題有很多方法[1-3]，研究表明蟻群算法由于其自身正反饋性及分布式運(yùn)行等優(yōu)點(diǎn)是最有效的方法之一。

蟻群算法[4]（ant colony optimization，ACO）是意大利學(xué)者Dorigo等人受自然界中螞蟻覓食的啟發(fā)而提出的群智能算法，主要思想是螞蟻能夠利用自身信息素更新機(jī)制有效地往返食物源與巢穴之間。其算法提出之后引起了人們的很大關(guān)注，并開(kāi)啟了探討蟻群算法的性能應(yīng)用等方面的研究。針對(duì)傳統(tǒng)蟻群算法收斂速度慢，求解精度不高等缺點(diǎn)，Dorigo 等人[5]又提出了蟻群系統(tǒng)（ant colony system，ACS），它通過(guò)每次迭代中對(duì)最優(yōu)螞蟻所生成的路徑上的信息素進(jìn)行更新，加強(qiáng)了最優(yōu)信息的正反饋?zhàn)饔?，進(jìn)一步提高了算法的收斂速度，但由于對(duì)最優(yōu)解的強(qiáng)化，易使算法陷入局部最優(yōu)。Stutzle 等人[6]提出了最大-最小螞蟻系統(tǒng)（max-min ant system，MMAS），該方式將信息素的取值設(shè)定在固定區(qū)間內(nèi)，限制了信息素的累加及揮發(fā)，在一定程度上避免了算法停滯，提高了種群多樣性，但當(dāng)解的分布較為分散時(shí)，算法的收斂速度將會(huì)降低。后來(lái)眾多學(xué)者結(jié)合自身領(lǐng)域需求對(duì)該算法進(jìn)行了更進(jìn)一步的改進(jìn)與研究，例如，在算法應(yīng)用方面，利用蟻群算法求解路徑規(guī)劃[7-10]、密集型網(wǎng)絡(luò)及云計(jì)算虛擬機(jī)布局[11-12]等問(wèn)題；在算法改進(jìn)方面，提出了融合其他智能算法優(yōu)化蟻群算法[13-14]、優(yōu)化算法參數(shù)及改進(jìn)路徑構(gòu)建規(guī)則[15-16]等改進(jìn)方式。文獻(xiàn)[17]在解決TSP 問(wèn)題中提出了一種面向?qū)ο蟮亩嘟巧伻核惴?，使得不同角色的蟻群針?duì)不同的城市執(zhí)行相應(yīng)的搜索策略，實(shí)驗(yàn)表明該方法能夠改善解的精度，但其求解過(guò)程較為復(fù)雜，不易實(shí)現(xiàn)。文獻(xiàn)[18]提出了一種改進(jìn)信息素二次更新局部?jī)?yōu)化的蟻群算法，通過(guò)對(duì)貢獻(xiàn)度較大的路徑進(jìn)行二次信息素更新，加速了算法收斂，但過(guò)快的收斂速度使得算法易陷入局部最優(yōu)。文獻(xiàn)[19]利用自然界中“優(yōu)勝劣汰”的進(jìn)化策略，增加滿足進(jìn)化的路徑上信息素濃度，提高收斂速度，同時(shí)采用隨機(jī)進(jìn)化因子以增強(qiáng)算法跳出局部最優(yōu)能力，但文中只是應(yīng)對(duì)小規(guī)模TSP 問(wèn)題，未能對(duì)大規(guī)模問(wèn)題進(jìn)行測(cè)試，其求解TSP 問(wèn)題規(guī)模有限。文獻(xiàn)[20]結(jié)合狼群算法引入獨(dú)狼視角機(jī)制及獨(dú)狼逃跑策略，使得蟻群具有較好的收斂速度與高效的全局尋優(yōu)能力，存在的問(wèn)題為該改進(jìn)策略在復(fù)雜環(huán)境下求解精度及其穩(wěn)定性有待進(jìn)一步提高。

針對(duì)大規(guī)模TSP問(wèn)題，本文提出融合獎(jiǎng)懲學(xué)習(xí)策略的動(dòng)態(tài)分級(jí)蟻群算法（dynamic hierarchical ant colony system based on reward and punishment learning strategy，DHL-ACS）。首先將蟻群動(dòng)態(tài)劃分為帝國(guó)蟻、殖民蟻及國(guó)王蟻。帝國(guó)蟻與殖民蟻執(zhí)行局部信息素更新，國(guó)王蟻執(zhí)行全局信息素更新，其中帝國(guó)蟻執(zhí)行較大權(quán)重系數(shù)，負(fù)責(zé)對(duì)較優(yōu)解的開(kāi)發(fā)保證算法的收斂速度，殖民蟻執(zhí)行較小權(quán)重系數(shù)，負(fù)責(zé)對(duì)次優(yōu)解的探索提高算法多樣性，并且在每輪迭代對(duì)殖民蟻與帝國(guó)蟻的解進(jìn)行評(píng)判，利用二者交換優(yōu)質(zhì)解的方式提高解的精度。同時(shí)引入改進(jìn)的學(xué)習(xí)策略，將每只帝國(guó)蟻按照自身國(guó)力值分配得到不同的殖民蟻，通過(guò)獎(jiǎng)勵(lì)每只帝國(guó)蟻及其附屬殖民蟻的公共路徑，實(shí)現(xiàn)較優(yōu)解的同化作用，提高算法的收斂速度。進(jìn)一步當(dāng)算法停滯時(shí)，在國(guó)王蟻中引入反饋算子，縮短當(dāng)前路徑與次優(yōu)路徑的信息素的差距，增強(qiáng)算法跳出局部最優(yōu)的能力。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法比傳統(tǒng)蟻群算法在TSP問(wèn)題上取得更好的實(shí)驗(yàn)結(jié)果，有效改善了算法全局搜索能力與收斂速度的矛盾。

1 相關(guān)工作

1.1 蟻群算法（ACS）工作原理

1.1.1 路徑構(gòu)建規(guī)則

ACS 較AS（ant system）的不同之處在于ACS 采用了全局更新與局部更新兩種更新方式，并且在節(jié)點(diǎn)概率選擇過(guò)程中引入偽隨機(jī)概率狀態(tài)轉(zhuǎn)移規(guī)則，其公式如式（1）所示：

式中，τij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j上的信息素；ηij代表了算法的啟發(fā)式信息，其值為ηij=1/dij，其中dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離值，其表達(dá)式為allowed內(nèi)部存儲(chǔ)的是螞蟻在該時(shí)刻未被訪問(wèn)的節(jié)點(diǎn)集合；β為啟發(fā)式因子，其大小代表了啟發(fā)式信息的影響程度；q0是一個(gè)固定的參數(shù)，其值范圍在[0,1]之間，大小由人為設(shè)定；q是一個(gè)均勻分布在[0,1]之間的隨機(jī)數(shù)；Pij為傳統(tǒng)蟻群算法的概率狀態(tài)表達(dá)式，即采用輪盤賭的方式構(gòu)建路徑，其表達(dá)式如式（2）所示：

式中，α為信息啟發(fā)因子，其他因子與式（1）作用相同。

1.1.2 信息素更新規(guī)則

（1）局部更新規(guī)則

當(dāng)每只螞蟻完成一次路徑構(gòu)建時(shí)其走過(guò)的邊上信息素的濃度都要降低，此更新方式讓后來(lái)的螞蟻選擇該條路徑的可能性降低，進(jìn)而增強(qiáng)算法的全局搜索能力，主要更新公式如式（3）所示：

式中，ξ為信息素的揮發(fā)率，其范圍在0～1 之間；τ0為信息素初始濃度，經(jīng)實(shí)驗(yàn)研究發(fā)現(xiàn)τ0=1/(n?ln)時(shí)算法性能較好，其中n為城市數(shù)，ln是由最近鄰域法得到的路徑值。

（2）全局信息素更新

在信息素的累加中，ACS與傳統(tǒng)的AS相比改變了不同路徑上的信息素累加程度，ACS 利用全局信息素更新機(jī)制，使得每次運(yùn)行完后只有至今最優(yōu)的路徑上的信息素會(huì)增加，其更新機(jī)制如式（4）所示：

1.2 3-opt算子

對(duì)蟻群優(yōu)化算法的其中一個(gè)改進(jìn)就是引入局部搜索，其中k-opt 是較為常見(jiàn)的一種局部?jī)?yōu)化方式。例如3-opt 算子就是其中效果較好的一種方法，該方法通過(guò)對(duì)每次螞蟻得到的最優(yōu)路徑進(jìn)行打開(kāi)重組，以此來(lái)提高解的精度，其主要流程為：

（1）首先得到本次算法的最優(yōu)路徑，即構(gòu)成最短的哈密頓回路；

（2）任意選取該條路徑的三個(gè)節(jié)點(diǎn)，依次進(jìn)行打開(kāi)重組，形成閉合回路；

（3）判斷是否有新的更短路徑產(chǎn)生，若有則替代原來(lái)的路徑，若無(wú)則依舊選擇原來(lái)的路徑。

2 改進(jìn)的蟻群算法（DHL-ACS）

2.1 動(dòng)態(tài)分級(jí)機(jī)制

在動(dòng)態(tài)分級(jí)機(jī)制中首先將蟻群劃分為帝國(guó)蟻與殖民蟻，不同的蟻群執(zhí)行不同的信息素更新，并在每次迭代中在帝國(guó)蟻與殖民蟻中選出一個(gè)國(guó)王蟻，并且只有國(guó)王蟻才能執(zhí)行全局路徑更新，如圖1所示。

Fig.1 Dynamic hierarchical mechanism圖1 動(dòng)態(tài)分級(jí)機(jī)制

2.1.1 國(guó)力評(píng)價(jià)算子

在TSP 問(wèn)題中每一只螞蟻所得的路徑長(zhǎng)度即為該螞蟻所得解，在算法運(yùn)行中螞蟻所得的解即為該螞蟻的國(guó)力值，其國(guó)力評(píng)價(jià)算子如下式所示：

式中，lengthi為在每次迭代中每只螞蟻所走的路徑長(zhǎng)度，lengthmin有兩種選擇，一種是至今最優(yōu)路徑的解，一種為迭代最優(yōu)路徑上得到的解。經(jīng)實(shí)驗(yàn)表明在城市數(shù)小于100的情況下兩種結(jié)果所差不多，但當(dāng)城市數(shù)大于100 時(shí)選擇至今最優(yōu)解比迭代最優(yōu)解的效果要好很多。

2.1.2 改進(jìn)信息素更新規(guī)則

在蟻群算法中，最主要的是信息素更新機(jī)制，通過(guò)更新機(jī)制的作用使得每條邊上的信息素差異不同，但傳統(tǒng)蟻群算法中，信息素的差異化不太明顯往往使得算法存在收斂速度慢、全局性能較差等缺點(diǎn)，故本文對(duì)ACS 中的局部更新策略進(jìn)行改進(jìn)，當(dāng)每只螞蟻構(gòu)建完成路徑后，將根據(jù)自身國(guó)力值選擇相應(yīng)的路徑構(gòu)建方式，進(jìn)而實(shí)現(xiàn)不同路徑上的信息素更新，具體如式（7）、式（8）所示：

對(duì)于螞蟻該如何選擇對(duì)應(yīng)的信息素更新機(jī)制，本文設(shè)定好閾值μ，當(dāng)λ≥μ時(shí)蟻群為帝國(guó)蟻，帝國(guó)蟻負(fù)責(zé)提高解的精度，采用式（7）更新信息素；當(dāng)λ<μ時(shí)蟻群為殖民蟻，殖民蟻負(fù)責(zé)對(duì)次優(yōu)解的開(kāi)發(fā)，提高解的多樣性，采用式（8）更新機(jī)制。由此可知，閾值的選取至關(guān)重要，本文通過(guò)多次實(shí)驗(yàn)對(duì)比確定閾值，如圖2所示（以kroA200為例），過(guò)高的閾值（如μ=0.9）會(huì)使得種群中殖民蟻數(shù)目較多，導(dǎo)致大量的無(wú)用搜索，進(jìn)而影響算法收斂速度；若閾值設(shè)定較低（如μ=0.7），此時(shí)帝國(guó)蟻數(shù)目較多，使得算法的搜索路徑過(guò)于集中而陷入局部最優(yōu)，進(jìn)而降低種群多樣性，由實(shí)驗(yàn)結(jié)果可知將閾值設(shè)定為0.8較適宜。

在對(duì)局部信息素的調(diào)整中，將每只螞蟻的自身國(guó)力值引入信息素更新中來(lái)，通過(guò)對(duì)閾值的選取使得在信息素的更新中，將不同螞蟻所得的解作為判斷其選擇信息素更新機(jī)制的依據(jù)，得到較優(yōu)解的螞蟻執(zhí)行較大權(quán)重系數(shù)，得到次優(yōu)解的螞蟻則執(zhí)行較小權(quán)重系數(shù)，這樣突出了優(yōu)質(zhì)解在整個(gè)算法運(yùn)行中的主導(dǎo)作用。當(dāng)算法陷入局部最優(yōu)時(shí)，能夠通過(guò)殖民蟻對(duì)路徑的開(kāi)發(fā)作用保證算法的多樣性。

Fig.2 Comparison of experimental results with different thresholds圖2 不同閾值實(shí)驗(yàn)結(jié)果對(duì)比

2.1.3 優(yōu)質(zhì)解的交換策略

在算法初始時(shí)所有螞蟻完成路徑構(gòu)建后，利用國(guó)力評(píng)價(jià)算子對(duì)每只螞蟻?zhàn)陨砬闆r進(jìn)行分級(jí)，其中優(yōu)良解（國(guó)力值高于閾值）的蟻群為帝國(guó)蟻，較差解（國(guó)力值低于閾值）為殖民蟻。在下一代根據(jù)自身信息素更新機(jī)制進(jìn)行路徑構(gòu)建，在每一代對(duì)所有螞蟻完成求解后，對(duì)兩種群中所得優(yōu)質(zhì)解進(jìn)行交換，國(guó)力值高于閾值的殖民蟻升級(jí)為帝國(guó)蟻，而國(guó)力值低于閾值的帝國(guó)蟻則被降格為殖民蟻，這一行為體現(xiàn)了“優(yōu)勝劣汰”的競(jìng)爭(zhēng)原則，使得優(yōu)質(zhì)解的集合始終保持更新?tīng)顟B(tài)以實(shí)現(xiàn)求解精度更優(yōu)，同時(shí)殖民蟻依據(jù)自身更新機(jī)制能夠繼續(xù)探索當(dāng)前較優(yōu)路徑以外的其他路徑，若探索到更優(yōu)解則幫助算法跳出局部最優(yōu)，增強(qiáng)了算法全局搜索能力。

2.2 學(xué)習(xí)機(jī)制

在學(xué)習(xí)機(jī)制中，如圖3 所示，采用殖民蟻向帝國(guó)螞蟻學(xué)習(xí)模式，在每次迭代劃分種群后，位于帝國(guó)中的螞蟻根據(jù)自身國(guó)力值獲取相應(yīng)的殖民蟻，在殖民蟻中通過(guò)對(duì)比與其所屬帝國(guó)蟻的解路徑得到二者的公共路徑，并相應(yīng)地增加公共路徑上的信息素量，進(jìn)而達(dá)到對(duì)公共路徑獎(jiǎng)勵(lì)的作用。

Fig.3 Learning mechanism圖3 學(xué)習(xí)機(jī)制

2.2.1 分配殖民蟻

通過(guò)上節(jié)劃分得到不同蟻群，并根據(jù)每只螞蟻的國(guó)力值從大到小進(jìn)行排序，設(shè)螞蟻總數(shù)M個(gè)，帝國(guó)蟻數(shù)目為Nim，其余Nco個(gè)螞蟻為殖民蟻，其中Nco=M-Nim，則每個(gè)帝國(guó)蟻依據(jù)下式分配得到殖民蟻：

為更合理地分配蟻群，首先采用式（9）對(duì)帝國(guó)蟻的國(guó)力值進(jìn)行標(biāo)準(zhǔn)化，其中pi為第i個(gè)帝國(guó)蟻的標(biāo)準(zhǔn)國(guó)力值，NCi為第i個(gè)帝國(guó)蟻分配到的殖民蟻數(shù)量，round函數(shù)為四舍五入取整。

2.2.2 種間學(xué)習(xí)

在完成蟻群分配后，在每次迭代中帝國(guó)蟻對(duì)其附屬的殖民蟻進(jìn)行同化操作，設(shè)第k只帝國(guó)蟻所分配得到殖民蟻數(shù)為n個(gè)，則第t次迭代中第k個(gè)帝國(guó)蟻與其所屬殖民蟻的公共解路徑為：

第k只帝國(guó)蟻對(duì)其殖民蟻的同化作用可表示為額外獎(jiǎng)勵(lì)公共路徑上的信息素，如下式所示：

故殖民蟻中公共路徑的信息素更新為：

由上述同化過(guò)程可知，對(duì)于公共路徑的信息素獎(jiǎng)勵(lì)程度不僅取決于帝國(guó)蟻?zhàn)陨韲?guó)力值，同時(shí)也受城市數(shù)目與迭代次數(shù)影響，并且每只帝國(guó)蟻群體中都會(huì)得到相應(yīng)的公共路徑。當(dāng)一條路徑被蟻群共同選擇時(shí)，可以認(rèn)為該路徑為最優(yōu)路徑的一部分或者在其附近存在最優(yōu)路徑。由式（12）可知在算法前期獎(jiǎng)勵(lì)共同路徑的信息素較多，增大螞蟻選擇公共路徑的概率，避免其他無(wú)用搜索，提高收斂速度，后期隨著迭代次數(shù)的增加獎(jiǎng)勵(lì)逐漸減少，保證算法后期的多樣性。

2.3 反饋算子

ACS中全局信息素更新使得算法能夠更快地收斂，但易使算法停滯陷入局部最優(yōu)，故本文中對(duì)國(guó)王蟻的全局信息素更新的改進(jìn)為：

式中，ε與δ為全局更新的反饋系數(shù)，T為當(dāng)前迭代數(shù)，Tc為最大迭代數(shù)，lengthiter為本次迭代中得到的最短路徑，lengthbs為在本次迭代前所得到的全局最短路徑。當(dāng)lengthiterlengthbs，說(shuō)明本次迭代中并未找到更優(yōu)的解，則ε>1，Δτbs減小，懲罰當(dāng)前全局路徑，以縮短當(dāng)前最優(yōu)路徑與其他路徑的信息素差距，增大螞蟻對(duì)其他路徑的開(kāi)發(fā)能力，進(jìn)而提高種群的多樣性。

當(dāng)算法運(yùn)行到中后期時(shí)，信息素的累加會(huì)使得大多數(shù)螞蟻選擇的路徑過(guò)于同質(zhì)化，進(jìn)而易陷入局域最優(yōu)，數(shù)值上表現(xiàn)出來(lái)的情況為長(zhǎng)期的lengthiter=lengthbs，即ε=1。為應(yīng)對(duì)此情況，本文引入反饋系數(shù)δ來(lái)進(jìn)一步懲罰當(dāng)前最優(yōu)路徑，其中設(shè)定δ>1，則Δτbs減小進(jìn)而縮小當(dāng)前最優(yōu)路徑與其他子路徑上的信息素量，增強(qiáng)算法跳出局部最優(yōu)的能力；但若設(shè)置過(guò)大，將會(huì)使得蟻群完全避開(kāi)當(dāng)前最優(yōu)路徑，而通常當(dāng)前最優(yōu)路徑的部分路徑也會(huì)是全局路徑的一部分，此時(shí)將導(dǎo)致算法進(jìn)行大量無(wú)用搜索，出現(xiàn)停滯現(xiàn)象。δ的設(shè)置情況如圖4 所示（kroA100、kroB200 為例），整體來(lái)看，采取懲罰操作（如δ取1.5、2.0）的尋優(yōu)性能較未采取懲罰操作（δ=1.0）的尋優(yōu)能力均有所提升。而δ設(shè)置較高時(shí)（如δ=5.0），算法易出現(xiàn)停滯現(xiàn)象，其中對(duì)于中小規(guī)模的城市（如kroA100），δ取1.5 時(shí)性能較好；但隨著城市規(guī)模增大，每次迭代中未選擇的次優(yōu)路徑數(shù)目也增多，此時(shí)讓周圍路徑以更大的概率被選擇到，則需更快地縮短二者之間的信息素差距，才能讓選擇范圍更廣，故應(yīng)將δ設(shè)置較大些。由圖可知，對(duì)于大規(guī)模城市（如kroB200），取δ=2.0 效果較好。

Fig.4 Comparison of experimental results with different feedback coefficients圖4 不同反饋系數(shù)實(shí)驗(yàn)結(jié)果對(duì)比

2.4 DHL-ACS算法流程

本文改進(jìn)算法（DHL-ACS）的算法流程如下所示：

算法1DHL-ACS算法框架

DHL-ACS Algorithm for TSP

2.5 DHL-ACS算法復(fù)雜度分析

從算法1 可知，在求解過(guò)程中算法可分為兩部分，其中第一代螞蟻依據(jù)ACS進(jìn)行路徑構(gòu)建，故算法復(fù)雜度為O(1 ?m?(n-1))，從第二代開(kāi)始螞蟻進(jìn)行身份劃分，并且兩類蟻群相互獨(dú)立，則此階段的DHLACS 算法復(fù)雜度為O((nc-1)?m1?(n-1)+(nc-1)?m2?(n-1))。式中m1與m2分別為每次迭代中帝國(guó)蟻與殖民蟻的數(shù)量，螞蟻總數(shù)為m，故DHL-ACS 總體復(fù)雜度為O(m?(n-1)+(nc-1)?m1?(n-1)+(nc-1)?m2?(n-1))，即O(nc?m?n)，與傳統(tǒng)ACS 的算法復(fù)雜度相等，故DHL-ACS并沒(méi)有增加整體算法的時(shí)間復(fù)雜度。

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

本文基于Windows10 系統(tǒng)，Matlab2016b 版本的仿真環(huán)境對(duì)算法進(jìn)行性能測(cè)試，選取國(guó)際標(biāo)準(zhǔn)TSP數(shù)據(jù)庫(kù)中多組不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文在ACS[5]的基礎(chǔ)上，通過(guò)多次實(shí)驗(yàn)，測(cè)試了不同參數(shù)對(duì)算法性能的敏感性作用。統(tǒng)計(jì)對(duì)比其結(jié)果發(fā)現(xiàn)，公共參數(shù)設(shè)置如表1 所示效果更好，且對(duì)三種對(duì)比算法實(shí)驗(yàn)結(jié)果分析時(shí)，采用相同的參數(shù)設(shè)置也更為合理，其中m為螞蟻數(shù)，μ為閾值，Tc為最大迭代次數(shù)；表2中δ為反饋系數(shù)，σ1、σ2分別為帝國(guó)蟻與殖民蟻的信息素更新權(quán)重系數(shù)，其作用為調(diào)控路徑上的信息素濃度，增加種群多樣性。為應(yīng)對(duì)算法在求解大規(guī)模TSP問(wèn)題時(shí)多樣性較差等問(wèn)題，本文通過(guò)調(diào)整權(quán)重系數(shù)將不同路徑的信息素差距拉大，以實(shí)現(xiàn)對(duì)不同路徑的區(qū)分作用，進(jìn)而增加算法多樣性。若將其設(shè)為一致，則在大規(guī)模TSP問(wèn)題中算法無(wú)法跳出局部最優(yōu)，故本文根據(jù)城市規(guī)模設(shè)置不同的權(quán)重參數(shù)。表3、表4 中算法誤差率=（算法最優(yōu)解?測(cè)試集最優(yōu)解）/測(cè)試集最優(yōu)解×100%[17]。

Table 1 Common parameters setting of DHL-ACS表1 DHL-ACS的公共參數(shù)設(shè)置

Table 2 Parameters setting in each test set of DHL-ACS表2 DHL-ACS在各個(gè)測(cè)試集中的參數(shù)設(shè)置

3.2 改進(jìn)算法（DHL-ACS）性能分析

3.2.1 DHL-ACS策略性能分析

本小節(jié)主要驗(yàn)證上文所提出的DHL-ACS算法性能，由于學(xué)習(xí)機(jī)制是以動(dòng)態(tài)分級(jí)機(jī)制為前提，故將對(duì)比ACS分別在加入動(dòng)態(tài)分級(jí)機(jī)制、動(dòng)態(tài)分級(jí)+學(xué)習(xí)機(jī)制及原始ACS算法的優(yōu)化結(jié)果，其測(cè)試結(jié)果如表3所示。

表3為ACS加入動(dòng)態(tài)分級(jí)機(jī)制、動(dòng)態(tài)分級(jí)+學(xué)習(xí)機(jī)制的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果（kroB100、kroA200、a280 測(cè)試集，算法運(yùn)行15 次），能夠看出算法加入動(dòng)態(tài)分級(jí)機(jī)制、動(dòng)態(tài)分級(jí)+學(xué)習(xí)機(jī)制的求解質(zhì)量與收斂速度均得到了改善，并且可以明顯看出ACS加入動(dòng)態(tài)分級(jí)+學(xué)習(xí)機(jī)制比單純加入動(dòng)態(tài)分級(jí)機(jī)制更具優(yōu)越性。以kroA200 為例，加入動(dòng)態(tài)分級(jí)+學(xué)習(xí)機(jī)制的算法不僅在收斂速度上優(yōu)于對(duì)比算法，并且在求解過(guò)程中找到了標(biāo)準(zhǔn)最優(yōu)解。其中標(biāo)準(zhǔn)差代表了算法的穩(wěn)定性，通過(guò)其比較也顯示了本文算法有較好的穩(wěn)定性，故改進(jìn)算法能夠較好地平衡算法全局搜索能力和收斂速度之間的關(guān)系。

Table 3 Optimization results of ACS with different models表3 ACS加入不同模型的優(yōu)化結(jié)果

3.2.2 DHL-ACS個(gè)體分布情況分析

為研究DHL-ACS的蟻群分布情況，本文以eil51為例進(jìn)行測(cè)試，結(jié)果如圖5 所示，圖中第一列為帝國(guó)蟻數(shù)量，第二列為殖民蟻數(shù)量，第三、四列分別為DHL-ACS與ACS在不同時(shí)刻的標(biāo)準(zhǔn)差，橫軸為迭代次數(shù)。由圖可得，在200～500 代，帝國(guó)蟻與殖民蟻的數(shù)目差距不明顯，且DHL-ACS 標(biāo)準(zhǔn)差略高于ACS，這是由于算法前期屬于探索階段，所求得的解質(zhì)量都不太高，從而導(dǎo)致兩類蟻群的整體求解結(jié)果差距不明顯；在500～1 000 代時(shí)，DHL-ACS 的標(biāo)準(zhǔn)差開(kāi)始減少并與ACS 持平，而此時(shí)的兩類蟻群數(shù)目差距開(kāi)始拉大，這表明算法在慢慢收斂，不同蟻群的求解結(jié)果逐漸分化，執(zhí)行較大權(quán)重系數(shù)的帝國(guó)蟻在算法中起主導(dǎo)作用，并且由于學(xué)習(xí)機(jī)制的作用使得蟻群較為集中地選擇目前的優(yōu)質(zhì)路徑，加快了算法收斂速度，從而使得種群多樣性有所下降；但在1 000～1 500代，帝國(guó)蟻逐漸減少，殖民蟻越來(lái)越多，此時(shí)學(xué)習(xí)機(jī)制的作用逐漸減弱，殖民蟻執(zhí)行探索功能，使得更多的次優(yōu)路徑能夠被搜索到，進(jìn)而提高了DHL-ACS的多樣性；在1 500～2 000 代，兩類蟻群數(shù)目趨于穩(wěn)定，殖民蟻搜索路徑的同時(shí)反饋算子的引入降低了當(dāng)前最優(yōu)路徑的信息素濃度，進(jìn)一步提升了其找尋新路徑的概率，增強(qiáng)算法跳出局部最優(yōu)的能力，而DHLACS的標(biāo)準(zhǔn)差結(jié)果也說(shuō)明了在后期該算法的多樣性并未下降?？傮w而言，DHL-ACS 在加快收斂速度的同時(shí)能夠保證種群多樣性，進(jìn)而平衡了二者之間的矛盾。

Fig.5 Ants distribution at different time圖5 不同時(shí)期螞蟻分布圖

3.3 與傳統(tǒng)算法對(duì)比分析

本節(jié)將改進(jìn)算法DHL-ACS與ACS及ACS+3opt算法進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比。測(cè)試集中選取15 個(gè)城市集，每個(gè)城市集運(yùn)行15次，每輪進(jìn)行2 000次迭代，實(shí)驗(yàn)結(jié)果如表4所示。

由表4 可知，對(duì)于中小規(guī)模城市如eil51、eil76 及kroA100 城市集，各類算法都能找到標(biāo)準(zhǔn)最優(yōu)解，對(duì)于kroB100 城市集，傳統(tǒng)蟻群算法未能找到最優(yōu)解，而DHL-ACS依舊能找到標(biāo)準(zhǔn)解?？傮w而言，在中小規(guī)模城市中三種算法找尋解的精度相差并不大，但DHL-ACS 算法在收斂速度上明顯快于對(duì)比算法，其中eil51 僅用了30 代便找到了標(biāo)準(zhǔn)最優(yōu)解，eil76 在160代就實(shí)現(xiàn)了最優(yōu)收斂，kroA100、kroB100則在368代及340 代收斂于標(biāo)準(zhǔn)最優(yōu)解，均快于對(duì)比算法，這是由于在學(xué)習(xí)機(jī)制中，殖民蟻的學(xué)習(xí)過(guò)程突顯了較優(yōu)路徑的主導(dǎo)作用，提高了算法的收斂速度。由此可以看出，對(duì)于中小規(guī)模城市DHL-ACS與傳統(tǒng)ACS及ACS+3opt 所得解的精度相差不明顯，但DHL-ACS能夠更快地收斂，其收斂速度均優(yōu)于其他算法。

在中大規(guī)模城市中，本文選取了ch130、kroA150、kroB150、ch150、d198、kroA200 及kroB200 等7 個(gè)城市數(shù)據(jù)集。DHL-ACS 的解均能很好地控制在1%以下，其中在kroA200 城市集上仍舊能找到最優(yōu)解，而kroA150、kroB200的誤差也控制在了0.1%以內(nèi)，并且無(wú)論是平均解還是最差解都要優(yōu)于ACS 及ACS+3opt。

對(duì)于大規(guī)模的城市集，本文選取了tsp225、a280、lin318 以及f417 等4 個(gè)城市集。在應(yīng)對(duì)大規(guī)模城市中傳統(tǒng)蟻群算法已經(jīng)不能很好地實(shí)現(xiàn)解的優(yōu)化，特別是對(duì)于ACS已出現(xiàn)失真現(xiàn)象，DHL-ACS雖然未能找到標(biāo)準(zhǔn)最優(yōu)解，但均能使誤差保持在1%以內(nèi)，并且對(duì)于a280，誤差達(dá)到0.08%，很接近最優(yōu)解，并且其他城市解的質(zhì)量同樣優(yōu)于對(duì)比算法。綜上表明，改進(jìn)的DHL-ACS 算法性能要優(yōu)于傳統(tǒng)的蟻群算法。各個(gè)城市的具體路徑圖如圖6所示，下面將從收斂速度與多樣性上分析DHL-ACS 與ACS、ACS+3opt 的差異情況。

Fig.6 Optimal path/city set(shortest distance)圖6 最優(yōu)路徑/城市集（最短距離）

3.3.1 算法收斂性與多樣性對(duì)比分析

為更加全面地分析改進(jìn)算法（DHL-ACS）的性能，本小節(jié)從收斂速度與多樣性兩方面進(jìn)行研究討論。鑒于小城市的數(shù)據(jù)集中傳統(tǒng)的蟻群算法所得解的質(zhì)量都較好，本文將分析DHL-ACS與ACS、ACS+3opt在中大規(guī)模及大規(guī)模城市集的算法性能。對(duì)于中大規(guī)模城市，本文選取kroA150、d198、kroB200等3個(gè)城市集，大規(guī)模城市集選取a280和f417兩個(gè)數(shù)據(jù)集。

圖7（a）、（b）代表kroA150 的多樣性，在算法前期，DHL-ACS 與ACS 的多樣性波動(dòng)性差距不明顯，但是到了中后期，DHL-ACS的標(biāo)準(zhǔn)差較ACS呈現(xiàn)出上升的態(tài)勢(shì)，這表明DHL-ACS在迭代中不斷優(yōu)化路徑值，同時(shí)DHL-ACS 的多樣性波動(dòng)逐漸加大，而ACS 的多樣性波動(dòng)性漸漸縮小，這也反映出傳統(tǒng)蟻群算法易陷入局部最優(yōu)的不足。圖8（a）、（b）表示d198城市集的多樣性，圖9（a）、（b）代表了kroB200測(cè)試集的多樣性。從圖中可得，DHL-ACS 的多樣性波動(dòng)性均比ACS 的多樣性要大，并且由于殖民蟻的開(kāi)發(fā)作用，使得DHL-ACS在算法后期也能夠保持較好的多樣性。圖7（c）、圖8（c）以及圖9（c）分別代表數(shù)據(jù)集kroA150、d198 和kroB200 對(duì)應(yīng)不同算法的收斂曲線。kroA150 中ACS+3opt 能夠在500 代左右收斂到最優(yōu)解，ACS 的收斂速度也較DHL-ACS 快，但其很快陷入了局域解中，而DHL-ACS的收斂速度雖未快于其他算法，卻能夠提高解的精度。d198、kroB200中DHL-ACS 收斂速度均要優(yōu)于ACS 與ACS+3opt，其中d198 測(cè)試集中在算法的1 800 代后還能跳出局域解，表明了在國(guó)王蟻的更新方式中引入反饋算子的懲罰作用，其更快地縮小了當(dāng)前最優(yōu)路徑與子路徑的信息素差距，使得殖民蟻有更大的概率選擇未被開(kāi)發(fā)的路徑，進(jìn)而增強(qiáng)算法跳出局部最優(yōu)的能力。

Fig.7 Comparative analysis of kroA150 test set圖7 kroA150測(cè)試集對(duì)比分析

Fig.8 Comparative analysis of d198 test set圖8 d198測(cè)試集對(duì)比分析

Fig.9 Comparative analysis of kroB200 test set圖9 kroB200測(cè)試集對(duì)比分析

為進(jìn)一步分析大規(guī)模城市問(wèn)題，本文選取a280（圖10（a）所示）、f417（圖10（b）所示）進(jìn)行對(duì)比。由圖10可以看出，對(duì)于大規(guī)模城市，ACS在收斂速度方面尚需進(jìn)一步優(yōu)化，并且對(duì)于解的質(zhì)量也出現(xiàn)較大誤差；ACS+3opt方面能夠稍微改善解的精度，所得解的質(zhì)量比ACS要高，但提升程度不明顯，同時(shí)收斂速度不如ACS；而綜合表4 DHL-ACS 對(duì)于不同的數(shù)據(jù)集其誤差率均能保證在1%，有效改善了解的精度；在收斂速度方面，由圖10知DHL-ACS的收斂曲線總體上在ACS與ACS+3opt曲線下方，說(shuō)明了收斂速度較對(duì)比算法要好。在f417 測(cè)試集中，DHL-ACS在算法1 800 代后也能進(jìn)一步優(yōu)化解，表明了改進(jìn)算法能夠較好地跳出局部最優(yōu)。綜上所述，DHL-ACS 能夠很好地平衡解的精度與收斂速度。

Fig.10 Comparative analysis of large scale test sets圖10 大規(guī)模測(cè)試集對(duì)比分析

3.3.2 穩(wěn)定性分析

本文利用標(biāo)準(zhǔn)差表示算法穩(wěn)定性，圖11 給出了測(cè)試的15個(gè)城市集的標(biāo)準(zhǔn)差。從圖中可得本文算法的標(biāo)準(zhǔn)差均較對(duì)比算法的要小，并且在中大規(guī)模城市集中更加明顯，這體現(xiàn)了DHL-ACS 比ACS 及ACS+3opt更加穩(wěn)定，故綜合表2表明改進(jìn)算法整體解的精度更高且穩(wěn)定性更好。

Fig.11 Comparison of algorithm stability圖11 算法穩(wěn)定性對(duì)比

3.4 與其他改進(jìn)算法對(duì)比

本文改進(jìn)算法（DHL-ACS）還與其他改進(jìn)算法進(jìn)行比較，結(jié)果如表5 所示。其中，改進(jìn)粒子群算法（IMRGHPSO）數(shù)據(jù)來(lái)自于文獻(xiàn)[2]，一種求解旅行商問(wèn)題的新型帝國(guó)競(jìng)爭(zhēng)算法（ICA）數(shù)據(jù)來(lái)源于文獻(xiàn)[3]，一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP 問(wèn)題求解（OMACO）來(lái)源于文獻(xiàn)[17]。從表5中可以看出，DHLACS算法所得解的質(zhì)量要明顯優(yōu)于對(duì)比算法。

Table 5 Comparison of DHL-ACS with other algorithms on TSP instances表5 DHL-ACS與其他算法在TSP案例上的比較

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

本文提出了融合獎(jiǎng)懲學(xué)習(xí)策略的動(dòng)態(tài)分級(jí)蟻群算法（DHL-ACS），動(dòng)態(tài)調(diào)整帝國(guó)蟻與殖民蟻的數(shù)量，并通過(guò)二者交換優(yōu)質(zhì)解的方式提高解的精度。同時(shí)在學(xué)習(xí)策略中，將帝國(guó)蟻分配得到相應(yīng)的殖民蟻，通過(guò)獎(jiǎng)勵(lì)二者的共同路徑來(lái)實(shí)現(xiàn)雙方的合作作用，進(jìn)而加快了算法的收斂速度。當(dāng)算法出現(xiàn)停滯時(shí)，引入反饋算子，懲罰當(dāng)前較高信息素的國(guó)王蟻，縮短其與次優(yōu)路徑的信息素差距，有效增強(qiáng)了算法跳出局部最優(yōu)的能力。雖然在實(shí)驗(yàn)測(cè)試中對(duì)比其他算法本文解的效果得到了較大的提升，但在大規(guī)模城市集中算法的收斂速度仍待進(jìn)一步改善，故下一步將嘗試改進(jìn)多種群蟻群算法，以提高算法在應(yīng)對(duì)大規(guī)模TSP測(cè)試集上的求解能力。