周克良，龔達(dá)欣，張宇龍

江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州 341000

1 引言

在眾多智能優(yōu)化算法中，蟻群算法是最成功的算法之一[1]。該算法最先由意大利學(xué)者Dorigo于20世紀(jì)90年代初提出，首先用于求解著名的旅行商問(wèn)題（Traveling Salesman Problem，TSP）并取得很好的效果[2]。Dorigo等學(xué)者對(duì)其的通用性和適用性進(jìn)一步優(yōu)化，并對(duì)此類框架的算法稱為蟻群算法（Ant Colony Optimization，ACO）[3]。蟻群算法具有較強(qiáng)的全局搜索能力、潛在的并行性、自學(xué)習(xí)能力、易于實(shí)現(xiàn)和較強(qiáng)的魯棒性等特點(diǎn)，被廣泛應(yīng)用于旅行商[4]、多維背包[5]、車輛調(diào)度[6]、圖像處理[7]和多目標(biāo)組合優(yōu)化[8]等問(wèn)題。但是，基本蟻群算法也存在著缺點(diǎn)，如算法收斂速度慢、收斂精度低等。

針對(duì)基本蟻群算法的不足，國(guó)內(nèi)外學(xué)者主要在信息素的釋放和更新、路徑選擇和優(yōu)化、參數(shù)的選擇和計(jì)算效率等方面進(jìn)行改進(jìn)。文獻(xiàn)[9]提出的方向素協(xié)調(diào)的蟻群算法，在信息素的釋放和更新以及路徑的選擇方面進(jìn)行優(yōu)化，在提升收斂速度的同時(shí)增強(qiáng)了全局搜索能力。文獻(xiàn)[10]提出面向?qū)ο蟮亩嘟巧伻核惴ǎ胟-means聚類和TSP的空間信息將城市分類提高收斂速度，并利用精英策略與2-Opt對(duì)信息素和路徑進(jìn)行更新優(yōu)化，提高了蟻群算法收斂精度和魯棒性。文獻(xiàn)[11]提出啟發(fā)式動(dòng)態(tài)信息素更新策略的蟻群算法，隨迭代次數(shù)動(dòng)態(tài)調(diào)整蟻群算法中的偽隨機(jī)因子參數(shù)并改進(jìn)信息素的更新規(guī)則，增加了解的多樣性因此提高了收斂精度。文獻(xiàn)[12]提出基于蟻群優(yōu)化的并行協(xié)作混合算法，使用3-Opt算子進(jìn)行路徑優(yōu)化以避免算法收斂陷入局部最優(yōu)解從而提高算法收斂精度，并通過(guò)并行協(xié)作的方式對(duì)多個(gè)菌落并行計(jì)算提升收斂速度。文獻(xiàn)[13]提出了一種基于蟻群算法、粒子群算法和k-Opt的求解TSP的混合算法，利用蟻群算法生成初始群粒子群對(duì)群算法進(jìn)行粒子群優(yōu)化，使算法在尋找最優(yōu)路徑在準(zhǔn)確率和運(yùn)行時(shí)間上都有較大提高。文獻(xiàn)[14]提出了一種改進(jìn)的蟻群算法，根據(jù)路徑中信息素堆積的程度，調(diào)節(jié)路徑中允許通過(guò)螞蟻數(shù)量的最大值以避免陷入局部最優(yōu)的情況并在路徑選擇方面應(yīng)用2-Opt算法進(jìn)行優(yōu)化，算法的收斂精度和速度相較于基本蟻群算法有較大提升。文獻(xiàn)[15]提出一種新的強(qiáng)化信息素更新機(jī)制和新穎的信息素平滑機(jī)制，利用動(dòng)態(tài)信息進(jìn)行路徑優(yōu)化并在停滯狀態(tài)時(shí)重新初始化信息素矩陣，增強(qiáng)了信息素邊緣信息和全局搜索能力使算法在解的多樣性和收斂性方面均有較好的提升。文獻(xiàn)[16]提出了一種基于動(dòng)態(tài)局部搜索的蟻群算法，增加每個(gè)蟻群的局部搜索能力并以動(dòng)態(tài)策略更新信息素，提高算法的搜索質(zhì)量和穩(wěn)定性。

上述算法對(duì)蟻群算法本身的參數(shù)、信息素更新規(guī)則、路徑選擇等方面進(jìn)行優(yōu)化或結(jié)合其他啟發(fā)式算法，在某些方面確實(shí)產(chǎn)生很好的效果，但仍存在著問(wèn)題。文獻(xiàn)[10]依賴于k-means聚類和分類的精度，算法提升收斂速度不明顯，且在TSP數(shù)據(jù)過(guò)大時(shí)產(chǎn)生局限性。文獻(xiàn)[11]偽隨機(jī)因子和動(dòng)態(tài)信息素更新策略在收斂速度和收斂精度上都有提升，但其提升效果不明顯且算法魯棒性降低。文獻(xiàn)[13]通過(guò)并行計(jì)算和3-Opt優(yōu)化，在收斂速度上有較大提升，但是僅僅依靠3-Opt算子的優(yōu)化使得算法在收斂精度上提升并不明顯。

針對(duì)在提升收斂速度的同時(shí)提高收斂精度和魯棒性的問(wèn)題，本文提出區(qū)域破壞重建的蟻群優(yōu)化算法，其主要思想是：（1）局部?jī)?yōu)化：選取每次迭代后的精英路徑對(duì)其采用2-Opt算子優(yōu)化，在增加解的多樣性的情況下，提高收斂精度并通過(guò)設(shè)置算法的截止條件加快收斂速度。（2）改進(jìn)信息素的更新規(guī)則：信息素更新路徑的選取采取優(yōu)勝劣汰的方式進(jìn)行以提高收斂速度，同時(shí)利用路徑的收斂情況動(dòng)態(tài)改變信息素保持系數(shù)增加算法的全局搜索能力。（3）區(qū)域破壞重建：對(duì)陷入局部最優(yōu)解的蟻群路徑采取區(qū)域破壞重建方式來(lái)破壞由信息素堆積而引起的局部最優(yōu)解，再以插入法重建路徑達(dá)到少量增加算法時(shí)間復(fù)雜度的代價(jià)，大幅度提高收斂精度和魯棒性。

2 基本蟻群算法

基本蟻群算法是由Dorigo等受真實(shí)螞蟻覓食行為的啟發(fā)，提出的一種智能優(yōu)化方法。原理是利用一群人工螞蟻來(lái)模擬真實(shí)螞蟻進(jìn)行覓食，人工螞蟻改變其經(jīng)過(guò)路徑上存儲(chǔ)的數(shù)字信息，碰到從未經(jīng)過(guò)的路口就隨機(jī)選其后的人工螞蟻根據(jù)殘留在其路徑上的數(shù)字信息選取路徑，導(dǎo)致最優(yōu)路徑上面的數(shù)字信息增大，人工螞蟻增多從而產(chǎn)生最優(yōu)路徑。

路徑的選擇和信息素的更新依照公式（1）～（4），其中τ為信息素，η為啟發(fā)信息，α為信息素啟發(fā)因子，β為期望啟發(fā)因子，N為城市個(gè)數(shù)，m為螞蟻個(gè)數(shù)，Nik為未經(jīng)過(guò)的城市組成的集合，ρ為信息素的保持系數(shù)。

第K只螞蟻當(dāng)前所在的節(jié)點(diǎn)為i，從i到節(jié)點(diǎn) j的概率如式（1）所示：

第K只螞蟻在途(i,j)上所留下的信息素如式（2）所示：

3 求解TSP的RDRACO算法

相對(duì)于基本的ACO，RDRACO主要有3點(diǎn)優(yōu)化：（1）引入?yún)^(qū)域破壞重建。對(duì)于陷入局部最優(yōu)的蟻群路徑進(jìn)行區(qū)域破壞重建，提高收斂精度。（2）局部?jī)?yōu)化。使用2-Opt算子對(duì)每次迭代后的前20%路徑進(jìn)行優(yōu)化，加快收斂速度和提高收斂精度。（3）改進(jìn)信息素更新規(guī)則。選取前六和后三的路徑進(jìn)行信息素的更新，根據(jù)路徑的收斂情況改變信息素保持系數(shù)，充分利用路徑信息。

3.1 區(qū)域破壞重建

破壞重建法（Ruin and Recreate，R&R）是由德國(guó)學(xué)者Schrimpf G等[17]提出的一種全新的啟發(fā)算法，特別適用于不連續(xù)、目標(biāo)復(fù)雜或約束較多等優(yōu)化問(wèn)題。借鑒R&R算法的構(gòu)造思路并結(jié)合蟻群算法的思想，對(duì)R&R算法進(jìn)行改進(jìn)使其更加匹配本文算法。區(qū)域破壞重建算法主要由破壞和重建兩部分組成。

3.1.1 破壞

針對(duì)完整的路徑做空間破壞或者空間消除，采取半徑破壞（Radius Ruin）的方法，對(duì)完整的路徑進(jìn)行破壞：全部N個(gè)節(jié)點(diǎn)中，選擇一個(gè)節(jié)點(diǎn)C作為圓心，根據(jù)公式（5）隨機(jī)生成的距離數(shù)據(jù)R選取距離矩陣D中與節(jié)點(diǎn)C距離小于R的節(jié)點(diǎn)集，并和點(diǎn)C并為點(diǎn)集S_Ruin作為移除的部分。移除的點(diǎn)都處于點(diǎn)C的附近，因此Radius Ruin在策略上屬于局部性破壞，不會(huì)對(duì)算法本身產(chǎn)生影響。

原圓心選取公式：

原破壞半徑公式：

在公式（5）、（6）中I為迭代次數(shù)，N 為城市個(gè)數(shù)，Min_L為距離矩陣中最小值即任意兩個(gè)節(jié)點(diǎn)之間最短距離，Max_L為距離矩陣中的最大值即任意兩個(gè)節(jié)點(diǎn)之間最長(zhǎng)距離。

圓心選取公式（5）在圓心的連續(xù)選取上沒(méi)用充分利用破壞半徑公式（6）所產(chǎn)生的區(qū)域節(jié)點(diǎn)破壞，導(dǎo)致選取同一區(qū)域的節(jié)點(diǎn)為圓心，對(duì)一定區(qū)域的節(jié)點(diǎn)進(jìn)行多次破壞和重建，大幅度增加了區(qū)域破壞算法的運(yùn)行時(shí)間。因此對(duì)圓心的選取公式進(jìn)行改進(jìn)，利用破壞區(qū)域內(nèi)的節(jié)點(diǎn)減少圓心節(jié)點(diǎn)的選取范圍以降低運(yùn)算資源的浪費(fèi)從而提升區(qū)域重建的速度。

改進(jìn)圓心選取公式：

其中，P為最優(yōu)路徑的節(jié)點(diǎn)集合，S_Ruin為被破壞區(qū)域的節(jié)點(diǎn)集合。

原破壞半徑公式（6）在 rand=0時(shí)，產(chǎn)生 Rmin=0.45Min_L的最小半徑，運(yùn)行的區(qū)域破壞只對(duì)圓心點(diǎn)進(jìn)行破壞，沒(méi)有達(dá)到區(qū)域破壞的目的導(dǎo)致浪費(fèi)運(yùn)算資源；半徑公式會(huì)在rand=1時(shí)，產(chǎn)生Rmax=0.45Max_L的最大半徑，運(yùn)行的區(qū)域破壞在節(jié)點(diǎn)區(qū)域上與較小破壞半徑的節(jié)點(diǎn)區(qū)域有較大的重疊部分，同樣區(qū)域多次進(jìn)行破壞重建存在運(yùn)算資源的浪費(fèi)。Rmax過(guò)大導(dǎo)致一次破壞過(guò)多的節(jié)點(diǎn)會(huì)大幅度增加區(qū)域重建的時(shí)間。因此對(duì)破壞半徑公式的選取范圍進(jìn)行改進(jìn)，以降低運(yùn)算資源的浪費(fèi)并提升區(qū)域重建的速度。

改進(jìn)破壞半徑公式：

3.1.2 重建

針對(duì)破壞后所留下的不完整路徑，采用插入法對(duì)被移除的節(jié)點(diǎn)一一插入破壞路徑以使路徑完整：原始路徑經(jīng)過(guò)破壞后產(chǎn)生兩個(gè)節(jié)點(diǎn)的集合S_Ruin（被破壞區(qū)域的節(jié)點(diǎn)集合）和S_Tour（未經(jīng)破壞區(qū)域的節(jié)點(diǎn)集合），在重建時(shí)采用插入法將S_Ruin中的元素通過(guò)整體最短距離的方式一一插入到S_Tour中，直到S_Ruin中元素為0為止。區(qū)域破壞重建算法運(yùn)行過(guò)程如圖1所示。

圖1 破壞重建示意圖

算法詳情：

步驟1按照式（7）選取本次迭代最優(yōu)路徑P中的節(jié)點(diǎn)C作為圓心，依據(jù)式（8）確定破壞半徑。

步驟2根據(jù)破壞半徑和距離矩陣確定破壞區(qū)域的節(jié)點(diǎn)集S_Ruin，并消除與之相連的連接線。

步驟3采用插入法將被移除的節(jié)點(diǎn)集S_Ruin中的元素通過(guò)整體最短距離的方式一一插入到節(jié)點(diǎn)集S_Tour中，直到S_Ruin中元素為0為止。

步驟4在最優(yōu)路徑P中剔除節(jié)點(diǎn)集S_Ruin，并判斷P中的元素個(gè)數(shù)是否為0，若是則結(jié)束；否則執(zhí)行步驟1。

3.2 局部?jī)?yōu)化

算法迭代一定次數(shù)后，較短的路徑上容易產(chǎn)生信息素堆積現(xiàn)象，使后續(xù)的蟻群選擇堆積路徑，減少全局搜索而產(chǎn)生局部最優(yōu)解。局部最優(yōu)解大多伴隨著路徑交叉現(xiàn)象，如圖2中原始路徑所示情況。綜合考慮文獻(xiàn)[18]中2-Opt和3-Opt搜索所用的時(shí)間、收斂效果，本文引用2-Opt算法進(jìn)行路徑優(yōu)化，解決因路徑信息素堆積所產(chǎn)生的點(diǎn)交叉現(xiàn)象，加快收斂的速度并提高收斂精度。

圖2 2-Opt示意圖

可以看出圖2中原始路徑存在路徑交叉現(xiàn)象，節(jié)點(diǎn)序列為a→b→e→d→c→f→g，經(jīng)過(guò)2-Opt算子對(duì)原始路徑進(jìn)行點(diǎn)交換優(yōu)化，優(yōu)化路徑節(jié)點(diǎn)序列為a→b→c→d→e→f→g消除路徑交叉現(xiàn)象，縮短路徑距離。

2-Opt算子時(shí)間復(fù)雜度較高，因此僅采取排序的方式選取蟻群算法每次迭代前20%的路徑進(jìn)行優(yōu)化以減少2-Opt算子對(duì)收斂速度的影響并有效地提高算法的收斂精度。

3.3 改進(jìn)的信息素更新

基本蟻群算法的單位信息素Δτ采用的是所有的人工螞蟻在完成一次迭代后的總和進(jìn)行更新，這樣更新的信息素忽略了太多的路徑信息，導(dǎo)致收斂速度較慢、收斂精度差等情況。

對(duì)此，本文采用優(yōu)勝劣汰的方法進(jìn)行信息素的更新，在每次迭代后對(duì)路徑進(jìn)行排序，選取前六和后三的路徑進(jìn)行信息素的更新如式（10）所示。當(dāng)出現(xiàn)和上次迭代最優(yōu)路徑大小相同時(shí)，改變信息素的揮發(fā)因子如式（9）所示。優(yōu)勝劣汰的信息素處理方式，充分地利用了路徑信息，較好地提高了收斂速度和算法的求解質(zhì)量。具體的更新方式如下：優(yōu)距離，為排序前六的路徑信息素的變化之和

ρ為信息素的保持系數(shù)，L_best(t+1)為后一次迭代的最為排序后面三個(gè)路徑的信息素變化之和。

4 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證RDRACO算法的有效性，實(shí)驗(yàn)采用TSPLIB中的20個(gè)經(jīng)典TSP數(shù)據(jù)集對(duì)RDRACO算法進(jìn)行仿真，實(shí)驗(yàn)環(huán)境為Windows 10 64位系統(tǒng)，CPU i5-8300H 2.3 GHz，Matlab 2016b軟件。算法的流程圖如圖3所示。

4.1 優(yōu)化方案分析

ACS[19]是基于ACO改進(jìn)的一種模型，其在收斂精度和收斂速度上達(dá)到了較好的平衡。本文RDRACO相對(duì)于基本的ACO主要有3點(diǎn)優(yōu)化，按照基本ACO和不同的優(yōu)化相結(jié)合分別生成優(yōu)化方案B和優(yōu)化方案C并與ACS在收斂精度上進(jìn)行對(duì)比，優(yōu)化方案的組合和編號(hào)如表1所示。

表1 優(yōu)化方案編號(hào)表

優(yōu)化方案的仿真實(shí)驗(yàn)從20組數(shù)據(jù)集中選取較為經(jīng)典的數(shù)據(jù)集att48，eil51，kroA100，bier127，kroA200，ts225共6組數(shù)據(jù)集。每組數(shù)據(jù)集都采用三種方案優(yōu)化方案進(jìn)行5次尋優(yōu)實(shí)驗(yàn)，尋優(yōu)實(shí)驗(yàn)的結(jié)束條件為達(dá)到最大迭代次數(shù)或連續(xù)30次迭代最優(yōu)解相同。從5次尋優(yōu)實(shí)驗(yàn)中選取最小值作為每組數(shù)據(jù)和實(shí)驗(yàn)優(yōu)化方案的最優(yōu)解并根據(jù)獲取的實(shí)驗(yàn)數(shù)據(jù)求解5次實(shí)驗(yàn)的平均值，通過(guò)已知的數(shù)據(jù)集最優(yōu)解得出相對(duì)誤差、平均誤差，實(shí)驗(yàn)結(jié)果如表2所示。

圖3 算法流程圖

表2 優(yōu)化方案數(shù)據(jù)對(duì)比表

實(shí)驗(yàn)RDRACO算法的參數(shù)設(shè)定為：城市規(guī)模n從數(shù)據(jù)中讀取，螞蟻個(gè)數(shù)m=round(n/1.5)，信息素重要程度參數(shù)Alpha=1.5，啟發(fā)式因子重要程度參數(shù)Beta=4，信息素增加強(qiáng)度系數(shù)Q=100，最大迭代次數(shù)NC_max=1 000。

從表2可以看出，優(yōu)化方案A求解TSP問(wèn)題不論是收斂精度還是魯棒性上都不是很理想，在較少的數(shù)據(jù)集att48上都存在2.56%的相對(duì)誤差，平均誤差也達(dá)到3.99%。

從優(yōu)化方案B的實(shí)驗(yàn)數(shù)據(jù)可以看出，對(duì)基本ACS的信息素更新規(guī)則和路徑2-Opt進(jìn)行優(yōu)化后，無(wú)論是收斂精度還是魯棒性都得到了極大的提高。在數(shù)據(jù)點(diǎn)小于100的情況下采用優(yōu)化方案B可以得到數(shù)據(jù)集已知的最優(yōu)解，在數(shù)據(jù)較大時(shí)也有較好的優(yōu)化。

從優(yōu)化方案C的實(shí)驗(yàn)數(shù)據(jù)可以看出，在方案B的基礎(chǔ)上加入?yún)^(qū)域破壞重建，明顯地提高了在數(shù)據(jù)集100～200的全局最優(yōu)解的搜索能力，在數(shù)據(jù)集小于200的情況下可以得到數(shù)據(jù)集已知的最優(yōu)解，且魯棒性也進(jìn)一步提升。

4.2 收斂情況分析

為了確定RDRACO算法在TSP問(wèn)題上的收斂精度，選取來(lái)源于TSPLIB[20]標(biāo)準(zhǔn)庫(kù)中的20組TSP實(shí)例數(shù)據(jù)進(jìn)行本次實(shí)驗(yàn)分析。從數(shù)據(jù)庫(kù)中找出20組TSP實(shí)例已知的最優(yōu)解作為標(biāo)準(zhǔn)與本次實(shí)驗(yàn)算法所求數(shù)據(jù)進(jìn)行比較得出相對(duì)誤差。

由以往的文獻(xiàn)總結(jié)可得，ACS算法在尋優(yōu)過(guò)程中，其尋優(yōu)的結(jié)果集精確度在很大程度上都會(huì)受到數(shù)據(jù)類型及數(shù)據(jù)點(diǎn)數(shù)量的影響。由表3分析可得，ACS算法隨著數(shù)據(jù)點(diǎn)數(shù)量的增大，尋優(yōu)的精確度并不是很理想，ACS算法在樣本數(shù)量及類型為berlin52時(shí)，精度可高達(dá)99.36%，在樣本數(shù)量及類型為rat783時(shí)，精度僅有82.1%。而本文所提出的RDRACO算法雖然也會(huì)受到數(shù)據(jù)類型及數(shù)據(jù)點(diǎn)數(shù)量的影響，但是在數(shù)據(jù)點(diǎn)數(shù)量小于等于200時(shí)，其精度可高達(dá)100%，當(dāng)尋優(yōu)數(shù)據(jù)點(diǎn)數(shù)量在200到800范圍內(nèi)，其精度最低可達(dá)97.51%，最高精度仍可維持在100%。在實(shí)驗(yàn)仿真過(guò)程中，RDRACO算法相對(duì)于ACS算法收斂速度較快、收斂精度及魯棒性顯著提高。

為查驗(yàn)RDRACO實(shí)驗(yàn)仿真結(jié)果中是否還存在點(diǎn)交叉或明顯的可交換現(xiàn)象，選取TSP實(shí)例中部分不同類別、數(shù)據(jù)點(diǎn)數(shù)的RDRACO仿真實(shí)驗(yàn)結(jié)果圖進(jìn)行驗(yàn)證，如圖4所示。

結(jié)合表3中RDRACO的收斂數(shù)據(jù)和圖4中的圖形可以證明，本文利用局部?jī)?yōu)化、改進(jìn)的信息素更新規(guī)則和破壞重建所優(yōu)化的ACO算法在精確度方面得到了很大的提高。

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

圖4 RAR最優(yōu)路徑

表3 收斂情況表

針對(duì)傳統(tǒng)蟻群收斂速度慢、易陷入局部最優(yōu)等問(wèn)題，提出區(qū)域破壞重建的蟻群優(yōu)化算法（RDRACO）。RDRACO充分利用每次迭代產(chǎn)生的路徑信息對(duì)信息素更新規(guī)則和全局更新策略進(jìn)行了調(diào)整，極大程度上提升收斂速度。RDRACO引入2-Opt進(jìn)行部分路徑優(yōu)化，在少量增加時(shí)間復(fù)雜度的情況下極大減小迭代次數(shù)明顯提高收斂速度。適時(shí)的插入破壞重建算法有效地提升了算法的收斂精度。實(shí)驗(yàn)結(jié)果表明，RDRACO算法對(duì)收斂精度有顯著影響，在處理數(shù)據(jù)點(diǎn)少于200的TSP可以尋找到其最優(yōu)路徑并在數(shù)據(jù)點(diǎn)增多時(shí)也具有優(yōu)秀的搜索能力，整體來(lái)說(shuō)RDRACO具有較高的精度和魯棒性。