區域破壞重建的蟻群優化算法

周克良，龔達欣，張宇龍

江西理工大學 電氣工程與自動化學院，江西 贛州 341000

1 引言

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

針對基本蟻群算法的不足，國內外學者主要在信息素的釋放和更新、路徑選擇和優化、參數的選擇和計算效率等方面進行改進。文獻[9]提出的方向素協調的蟻群算法，在信息素的釋放和更新以及路徑的選擇方面進行優化，在提升收斂速度的同時增強了全局搜索能力。文獻[10]提出面向對象的多角色蟻群算法，利用k-means聚類和TSP的空間信息將城市分類提高收斂速度，并利用精英策略與2-Opt對信息素和路徑進行更新優化，提高了蟻群算法收斂精度和魯棒性。文獻[11]提出啟發式動態信息素更新策略的蟻群算法，隨迭代次數動態調整蟻群算法中的偽隨機因子參數并改進信息素的更新規則，增加了解的多樣性因此提高了收斂精度。文獻[12]提出基于蟻群優化的并行協作混合算法，使用3-Opt算子進行路徑優化以避免算法收斂陷入局部最優解從而提高算法收斂精度，并通過并行協作的方式對多個菌落并行計算提升收斂速度。文獻[13]提出了一種基于蟻群算法、粒子群算法和k-Opt的求解TSP的混合算法，利用蟻群算法生成初始群粒子群對群算法進行粒子群優化，使算法在尋找最優路徑在準確率和運行時間上都有較大提高。文獻[14]提出了一種改進的蟻群算法，根據路徑中信息素堆積的程度，調節路徑中允許通過螞蟻數量的最大值以避免陷入局部最優的情況并在路徑選擇方面應用2-Opt算法進行優化，算法的收斂精度和速度相較于基本蟻群算法有較大提升。文獻[15]提出一種新的強化信息素更新機制和新穎的信息素平滑機制，利用動態信息進行路徑優化并在停滯狀態時重新初始化信息素矩陣，增強了信息素邊緣信息和全局搜索能力使算法在解的多樣性和收斂性方面均有較好的提升。文獻[16]提出了一種基于動態局部搜索的蟻群算法，增加每個蟻群的局部搜索能力并以動態策略更新信息素，提高算法的搜索質量和穩定性。

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

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

2 基本蟻群算法

基本蟻群算法是由Dorigo等受真實螞蟻覓食行為的啟發，提出的一種智能優化方法。原理是利用一群人工螞蟻來模擬真實螞蟻進行覓食，人工螞蟻改變其經過路徑上存儲的數字信息，碰到從未經過的路口就隨機選其后的人工螞蟻根據殘留在其路徑上的數字信息選取路徑，導致最優路徑上面的數字信息增大，人工螞蟻增多從而產生最優路徑。

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

第K只螞蟻當前所在的節點為i，從i到節點 j的概率如式（1）所示：

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

3 求解TSP的RDRACO算法

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

3.1 區域破壞重建

破壞重建法（Ruin and Recreate，R&R）是由德國學者Schrimpf G等[17]提出的一種全新的啟發算法，特別適用于不連續、目標復雜或約束較多等優化問題。借鑒R&R算法的構造思路并結合蟻群算法的思想，對R&R算法進行改進使其更加匹配本文算法。區域破壞重建算法主要由破壞和重建兩部分組成。

3.1.1 破壞

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

原圓心選取公式：

原破壞半徑公式：

在公式（5）、（6）中I為迭代次數，N 為城市個數，Min_L為距離矩陣中最小值即任意兩個節點之間最短距離，Max_L為距離矩陣中的最大值即任意兩個節點之間最長距離。

圓心選取公式（5）在圓心的連續選取上沒用充分利用破壞半徑公式（6）所產生的區域節點破壞，導致選取同一區域的節點為圓心，對一定區域的節點進行多次破壞和重建，大幅度增加了區域破壞算法的運行時間。因此對圓心的選取公式進行改進，利用破壞區域內的節點減少圓心節點的選取范圍以降低運算資源的浪費從而提升區域重建的速度。

改進圓心選取公式：

其中，P為最優路徑的節點集合，S_Ruin為被破壞區域的節點集合。

原破壞半徑公式（6）在 rand=0時，產生 Rmin=0.45Min_L的最小半徑，運行的區域破壞只對圓心點進行破壞，沒有達到區域破壞的目的導致浪費運算資源；半徑公式會在rand=1時，產生Rmax=0.45Max_L的最大半徑，運行的區域破壞在節點區域上與較小破壞半徑的節點區域有較大的重疊部分，同樣區域多次進行破壞重建存在運算資源的浪費。Rmax過大導致一次破壞過多的節點會大幅度增加區域重建的時間。因此對破壞半徑公式的選取范圍進行改進，以降低運算資源的浪費并提升區域重建的速度。

改進破壞半徑公式：

3.1.2 重建

針對破壞后所留下的不完整路徑，采用插入法對被移除的節點一一插入破壞路徑以使路徑完整：原始路徑經過破壞后產生兩個節點的集合S_Ruin（被破壞區域的節點集合）和S_Tour（未經破壞區域的節點集合），在重建時采用插入法將S_Ruin中的元素通過整體最短距離的方式一一插入到S_Tour中，直到S_Ruin中元素為0為止。區域破壞重建算法運行過程如圖1所示。

圖1 破壞重建示意圖

算法詳情：

步驟1按照式（7）選取本次迭代最優路徑P中的節點C作為圓心，依據式（8）確定破壞半徑。

步驟2根據破壞半徑和距離矩陣確定破壞區域的節點集S_Ruin，并消除與之相連的連接線。

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

步驟4在最優路徑P中剔除節點集S_Ruin，并判斷P中的元素個數是否為0，若是則結束；否則執行步驟1。

3.2 局部優化

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

圖2 2-Opt示意圖

可以看出圖2中原始路徑存在路徑交叉現象，節點序列為a→b→e→d→c→f→g，經過2-Opt算子對原始路徑進行點交換優化，優化路徑節點序列為a→b→c→d→e→f→g消除路徑交叉現象，縮短路徑距離。

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

3.3 改進的信息素更新

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

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

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

4 仿真實驗及結果分析

為了驗證RDRACO算法的有效性，實驗采用TSPLIB中的20個經典TSP數據集對RDRACO算法進行仿真，實驗環境為Windows 10 64位系統，CPU i5-8300H 2.3 GHz，Matlab 2016b軟件。算法的流程圖如圖3所示。

4.1 優化方案分析

ACS[19]是基于ACO改進的一種模型，其在收斂精度和收斂速度上達到了較好的平衡。本文RDRACO相對于基本的ACO主要有3點優化，按照基本ACO和不同的優化相結合分別生成優化方案B和優化方案C并與ACS在收斂精度上進行對比，優化方案的組合和編號如表1所示。

表1 優化方案編號表

優化方案的仿真實驗從20組數據集中選取較為經典的數據集att48，eil51，kroA100，bier127，kroA200，ts225共6組數據集。每組數據集都采用三種方案優化方案進行5次尋優實驗，尋優實驗的結束條件為達到最大迭代次數或連續30次迭代最優解相同。從5次尋優實驗中選取最小值作為每組數據和實驗優化方案的最優解并根據獲取的實驗數據求解5次實驗的平均值，通過已知的數據集最優解得出相對誤差、平均誤差，實驗結果如表2所示。

圖3 算法流程圖

表2 優化方案數據對比表

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

從表2可以看出，優化方案A求解TSP問題不論是收斂精度還是魯棒性上都不是很理想，在較少的數據集att48上都存在2.56%的相對誤差，平均誤差也達到3.99%。

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

從優化方案C的實驗數據可以看出，在方案B的基礎上加入區域破壞重建，明顯地提高了在數據集100～200的全局最優解的搜索能力，在數據集小于200的情況下可以得到數據集已知的最優解，且魯棒性也進一步提升。

4.2 收斂情況分析

為了確定RDRACO算法在TSP問題上的收斂精度，選取來源于TSPLIB[20]標準庫中的20組TSP實例數據進行本次實驗分析。從數據庫中找出20組TSP實例已知的最優解作為標準與本次實驗算法所求數據進行比較得出相對誤差。

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

為查驗RDRACO實驗仿真結果中是否還存在點交叉或明顯的可交換現象，選取TSP實例中部分不同類別、數據點數的RDRACO仿真實驗結果圖進行驗證，如圖4所示。

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

5 結束語

圖4 RAR最優路徑

表3 收斂情況表

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