基于視覺修正的改進最大最小螞蟻系統求解TSP

李克文 徐延輝 張震濤 席英杰

(中國石油大學(華東) 山東 青島 266580)

0 引 言

蟻群算法是由Dorigo等[1]提出的一種仿生優化算法,它與粒子群算法[2]、鯨魚優化算法[3]等都屬于群智能優化算法。蟻群算法的靈感來自于對自然界螞蟻群體覓食行為中的路徑探索的模擬。該算法具有典型的系統特性,其分散性、自組織性、正反饋性和并行性等優點為許多學者探索和研究提供了切入點。作為一種元啟發式演化算法[4],在解決許多復雜的組合優化問題上具有明顯的優勢,應用范圍也非常廣泛,如TSP問題、調度問題[5]、圖像特征提取[6]、路徑規劃[7-8]、地震斷層識別[9]和軟件缺陷預測[10]等。然而,蟻群算法也有收斂速度慢、容易陷入局部最優和過早停滯的缺點。

針對這些不足,許多學者提出了改進的方法。文獻[11]提出了一種采用惰性螞蟻概念的自動控制蟻群算法,通過將每個最佳路徑上的螞蟻設置為惰性螞蟻,直到下一次找到該路徑,它才會被激活;文獻[12]提出了一種基于聚度的自適應動態混沌蟻群算法,在迭代前期利用聚度來衡量解的多樣性,并引入混沌算子來增加種群多樣性,提高了算法精度,在迭代后期去掉混沌算子,減少混沌擾動性,提高了算法的收斂速度;文獻[13]提出了改進的蟻群與粒子群混合算法,采用了改進蟻群算法的信息素更新方式和全局最優粒子自適應交叉變異策略;文獻[14]提出了一種基于可變天氣因素的MMAS改進算法,參考天氣變化因素對螞蟻覓食的影響,設置信息素揮發系數和蟻群數量,提高了解的質量;文獻[15]引入了一種稱為單位距離信息素算子的新蟻群,并與ACS和MMAS共同構成了最終的算法,利用皮爾遜相關系數建立自適應頻率的多群體通信;文獻[16]提出了一種梯度下降選擇策略,該策略不僅根據信息素的濃度按概率搜索下一步,而且根據一定概率采用梯度下降方法搜索下一步;文獻[17]參照人類集體行動模型,為蟻群增加一個集體行動,在迭代過程中,每只螞蟻根據自己的閾值決定是否加入到集體行動,避免了算法陷入局部最優;文獻[18]將細菌覓食算法和蟻群算法相結合,在蟻群算法迭代過程中,引入細菌覓食算法的復制操作,以加快算法的收斂速度;引入細菌覓食算法的趨向操作,以增強算法的全局搜索能力。文獻[19]提出了一種改進負反饋機制的偽動態搜索蟻群優化算法,算法在信息素傳遞規則中引入了一個角度,通過角度計算規則,多個角度較小的城市也被包括在下一個候選城市列表中,避免了局部優化;文獻[20]在蟻群陷入局部最優時,利用信息素進行突變,幫助算法跳出局部最優。

MMAS是一種通用性較強,尋優效果較好的經典改進蟻群算法,本文在MMAS算法的基礎上,針對MMAS收斂速度慢、容易陷入局部最優的問題,改進了信息素的初始化,在算法陷入局部最優后提出了局部尋優、新路徑探索和“雙優”策略更新信息素三個策略,增加了解的多樣性,提高了求解精度。

1 相關概念

1.1 基本蟻群算法

蟻群算法(Ant Colony Optimization)的典型應用是TSP問題求解。TSP是一個經典的組合優化問題。n個城市的TSP求解可以描述為：給定一個城市集合V={v1,v2,…,vn},求解遍歷V中所有城市各一次且最后回到出發城市的一個最短旅行哈密爾頓回路g∈G(V,A),其中G(V,A)為滿足上述求解約束條件的哈密爾頓回路集合,A={aij=(vi,vj)|0

給定如下相關參數,蟻群數量m,信息素啟發因子α,期望啟發因子β,信息素揮發系數ρ,各路徑上的信息素τij,算法在初始時刻,每條路徑的信息素濃度為同一個常數,即τij=C(C為較小的常數);在每次迭代過程中,每只螞蟻隨機選擇一個城市作為起始城市,再使用輪盤賭的方法,按照式(1)選擇下一個城市。

(1)

τij(t)=(1-ρ)τij(t-1)+Δτij(t)

(2)

1.2 最大最小螞蟻系統

最大最小螞蟻系統(MMAS)是在ACO基礎上進行改進的,它改進了ACO容易陷入局部最優、收斂速度慢等缺點,其主要改進方向包括以下3個方面：

(1) 將信息素τij限制在τmin與τmax之間,即τmin≤τij≤τmax,該策略避免了最優路徑上的信息素和未訪問路徑的信息素差距過大,導致搜索的停滯。

(2) 將初始信息素設置為τmax,該策略使得算法在初始階段有更多的搜索可能。

(3) 在每次迭代之后,只允許最優路徑更新信息素,可以是當前迭代最優,也可以是歷史最優,其信息素更新方式按照式(3)進行。

(3)

2 基于視覺修正的MMAS算法

自然界中螞蟻認路的本領很強,其認路能力主要依靠兩種路標進行導航,一是大家熟知的氣味路標,是螞蟻一邊走路,一邊分泌的一種信息素;二是天文路標,螞蟻用眼睛憑借太陽來定位,實現導航。螞蟻的眼睛是一雙復眼,由數量不等的單眼組成。復眼越大,螞蟻看得越遠。本文引入天文蟻,即一種主要使用眼睛探索路徑的具有大復眼的螞蟻,在算法陷入局部最優時,由天文蟻檢查當前路徑的情況,并根據不同路徑情況調整搜索方案,使算法及時跳出局部最優。

2.1 基于啟發式信息的信息素初始化

本文在信息素進行初始化時,綜合考慮啟發式信息,依據城市間的歐氏距離初始化信息素,每條路徑上的信息素τij初始化為基礎信息素與期望信息素兩部分,按照式(4)進行初始化,既滿足了算法在初始階段有較多的搜索可能,又避免了算法初期的盲目搜索,提高了算法的收斂速度。

(4)

式中：τ0表示基礎信息素;τ0+(1/dij)的值在τmax附近。

2.2 基于視覺修正的MMAS算法

蟻群算法最大的缺點是容易陷入局部最優,導致算法停滯。在最大最小螞蟻系統中,每次迭代結束,只允許最優路徑有信息素的留下,使得其他路徑的信息素隨著迭代的進行而減少,蟻群的搜索方向極易向歷史最優路徑靠近,一旦長時間陷入局部最優,其他路徑信息素將始終保持為τmin,算法難以找到新解。針對此問題,設置閾值nt并統計歷史最優路徑出現的次數,當該次數達到nt時,算法陷入局部最優的可能性較大。此時,天文蟻檢查歷史最優路徑中是否存在路徑交叉,若存在,則消除交叉路徑;若不存在,則進行新路徑探索。

2.2.1局部路徑優化

蟻群在路徑搜索過程中,極易出現路徑交叉的現象。對于TSP問題,要找的是一條最短的哈密爾頓回路,由三角形的任意兩邊之和大于第三邊,如果存在交叉路徑,此路徑一定不是最短路徑(AE+BE>AB,DE+CE>CD,所以AC+BD>AB+CD),如圖1所示,其中,ABCD為4個城市,E為交叉點。

圖1 路徑交叉圖

當算法陷入局部最優時,若天文蟻檢查到歷史最優路徑存在交叉,根據兩交叉路徑的相對位置,將交叉路徑分以下兩種情況,如圖2所示。其中,ABCDEF為6個城市。

(a) (b)圖2 路徑交叉分類圖

(1) 若交叉路徑相鄰較近,如圖2(a)所示,則選擇交叉路徑臨近的6個城市重新追蹤該段路徑,由于路徑涉及的城市很少,采取組合遍歷的方式找到該段最短路徑,然后更新歷史最優路徑及其距離,同時,用式(5)更新路徑信息素,并揮發交叉路徑信息素。

(5)

(2) 若交叉路徑相鄰較遠,如圖2(b)所示,則重新構建路徑,消除交叉路徑AC和BD,構建新路徑AB和CD,實現路徑的進一步優化,然后更新歷史最優路徑及其距離,同時,用式(6)更新新路徑信息素,并揮發交叉路徑信息素。

(6)

基于數學原理的交叉路徑消除策略,有利于算法及時消除交叉路徑,用最短的時間快速跳出局部最優。

2.2.2新解探索

當第t-1代算法陷入局部最優且天文蟻檢查到歷史最優路徑Tbest不存在交叉時,調整信息素,保持歷史最優路徑信息素不變,增加其他路徑信息素,如式(7)所示。天文蟻在第t代進行新路徑的探索,當所有螞蟻隨機選擇完成起始城市v1后,再采用輪盤賭的方式,按照式(1)選擇第二個城市v2,其中,(v1,v2)?Tbest。之后,每當算法運行nt代,進行一次新解的探索,直到找到更優解。

(7)

在新解探索之前調整信息素,增加了除歷史最優路徑之外的其他路徑信息素,以平均距離為界,采用不同方式增加路徑信息素,減小了路徑間信息素的濃度差距,較大幅度提升較近城市的選中概率,既擴大了新解探索時的搜索范圍,又避免了全局盲目搜索。新解探索策略使算法主動跳出局部最優,尋找新解,避免了算法的停滯。

2.2.3“雙優”策略改善信息素更新方式

當算法陷入局部最優且天文蟻檢查的歷史最優路徑不存在交叉時,用式(8)進行信息素的補充,直至算法找到更優解,跳出當前局部最優。該策略在保持最優路徑信息素不變的前提下,增加了當前迭代最優路徑中新路徑的信息素,增加當前迭代最優路徑的引導能力,在迭代過程中增加了解的可能性,有利于找到新的全局最優解。

(8)

2.3 算法流程

步驟1初始化各參數α、β、Q、τmin、τmax、x、τ0、nt、最大迭代次數T,迭代次數t=0。

步驟2初始化信息素。

步驟3將m只螞蟻隨機放入到n個城市中,并將城市放入禁忌表中。

步驟4每只螞蟻按照概率(見式(1))選擇下一個要訪問的城市,并將該城市放入禁忌表中,直到遍歷完所有城市,計算其路徑長度,并將每只螞蟻的路徑及其長度保存。

步驟5所有螞蟻遍歷完城市之后,保存全局最優路徑best_route以及對應最短路徑長度min_distance。

步驟6按照式(3)將更新全局信息素。

步驟7判斷歷史最優路徑長度出現的次數是否大于nt,如果是,利用天文蟻檢查歷史最優路徑中是否存在路徑交叉的情況,若存在,轉到步驟8,若不存在,轉到步驟11。

步驟8判斷交叉路徑類型,若屬于圖(2)a類,轉到步驟9,若屬于圖(2)b類,轉到步驟10。

步驟9采取組合遍歷的方式找到交叉路徑附近x個城市的最短路徑,并更新歷史最優路徑及其距離,按照式(5)更新該段新路徑信息素,轉到步驟13。

步驟10對交叉線上的四個城市構建新路徑,并更新歷史最優路徑及其距離,按照式(6)更新該段新路徑信息素,轉到步驟13。

步驟11判斷歷史最優路徑長度出現的次數是否等于k×nt(k=0,1,…),如果等于,按照式(7)調整信息素,探索新路徑,否則,轉到步驟12。

步驟12按照式(8)進行更新信息素。

步驟13禁忌表清空,迭代次數t=t+1。如果迭代次數沒有達到最大值,則轉向步驟3,否則輸出最優解并退出循環。

3 實驗與結果分析

為了驗證本文提出的VC-MMAS算法的有效性,本文對TSPLIB數據庫中的TSP問題進行了求解,為了比較VC-MMAS算法的性能,將實驗結果與遺傳算法(GA)、粒子群算法(PSO)、自組織神經網絡(SOM)和最大最小螞蟻系統(MMAS)進行了比較,實驗中所使用的參數均經過試驗確定。各算法實驗參數分別如下：GA中的重要參數取值為：交叉概率為0.9,變異概率為0.2,種群數量為50;PSO中的重要參數取值為：α=0.9,β=0.9,粒子數量為150;SOM中的重要參數為：初始學習率為0.8,神經元數量m=8×n,最大迭代次數為8 000;MMAS中重要參數取值為：α=0.9,β=2,Q=100,τmin=0.001,τmax=1,ρ=0.05,種群數量m=n;VC-MMAS中各參數的取值為：α=0.9,β=2,Q=100,τmin=0.001,τmax=1,ρ=0.05,x=6,τ0=0.9,nt=50。針對10個TSP問題,除SOM外,其他每種算法最大迭代次數T=1 000。不同TSP問題對應算法的實驗結果見表1。

續表1

表1 不同TSP問題對應算法的實驗結果對比

表1展示了對于每一個數據集,每種算法獨立運行十次,求得每種算法的最優路徑長度(Best Length)、最差路徑長度(Worst Length)、平均路徑長度(Average Length)、標準差(Standard Deviation)。其中Best Length、Worst Length體現了算法的有效性,Average Length、Standard Deviation體現了算法的穩定性,標準差越小,表示該算法穩定性越好,反之,標準差越大,表示算法的穩定性越差,尋優結果波動越大。根據實驗的數據,圖3展示了CV-MMAS算法在部分數據集上求解TSP問題時的最優路徑。由表1可知,VC-MMAS在10個數據集上都獲解了最優路徑,MMAS在berlin52、gr96上也獲解了最優路徑,但在這兩個數據集上VC-MMAS獲解的最差路徑優于MMAS;在att48、eil51、berlin52、st70、eil76、gr96、gr202上,VC-MMAS的標準差小于其他4種算法;在eil101、gr666上,VC-MMAS的標準差略大于MMAS。由此可見,VC-MMAS改進效果顯著,相較于其他4種算法,在求解TSP問題上有較高的穩定性,不易陷入局部最優。

(a) att(48) (b) eil(51)

5種算法在att48上的仿真收斂對比情況如圖4所示,其中,SOM算法每8代取一次數據?？梢钥闯?VC-MMAS算法在迭代前20代就得到了較短的路徑;在第400代,GA、SOM算法和MMAS算法就已經陷入了局部最優;直到迭代結束,PSO則經歷了400多代,在算法后期跳出了當前迭代最優;VC-MMAS算法在迭代過程中不斷跳出局部最優,每100多代就能更新歷史最優解,最終找到了最優解。VC-MMAS算法利用啟發式信息初始化信息素,避免了算法初期的盲目搜索;在算法陷入局部最優后引入天文蟻消除局部最優、探索新路徑,并使用“雙優”策略更新信息素,增加了解的多樣性,避免了算法陷入停滯狀態。

圖4 att48的收斂對比圖

上述10個TSP問題的仿真實驗結果表明,本文提出的VC-MMAS算法在解決TSP問題時具有更好的精度,與其他算法相比,提供的最優路徑長度最小且在大多數情況下標準差也最小。

4 結 語

針對蟻群算法在求解TSP問題時表現出的收斂速度慢,易陷入局部最優的現象,本文在MMAS算法的基礎上提出了VC-MMAS算法,該算法引入了以下機制：

(1) 結合啟發式信息進行信息素的初始化,既符合MMAS算法在初始階段有較多的搜索可能,又避免了算法初期的盲目搜索,提高了算法的收斂速度。

(2) 在算法陷入局部最優時,引入依靠太陽而非信息素導航的天文蟻,對歷史最優路徑進行檢查和修正。當存在路徑交叉時,根據交叉路徑的相對位置情況采用不同方式直接消除交叉路徑,以較小的時間代價找到更優的路徑;當不存在路徑交叉時,首先調整信息素,縮小路徑間信息素的差距,其次,天文蟻對路徑尋優進行干預,強制算法進行新路徑的探索,幫助算法找到與歷史最優路徑差別較大的新的最優路徑,避免算法進入停滯狀態;使用“雙優”策略更新信息素,增加解的可能性,幫助算法找到歷史最優路徑或當前迭代最優路徑相似的更優路徑。

在經典TSP問題上的仿真對比實驗表明,VC-MMAS算法較其他4種算法具有更強的尋優能力和更高的穩定性。下一步工作將針對大型的TSP數據集,進一步提升算法性能。