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

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

0 引 言

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

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

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

1 相關(guān)概念

1.1 基本蟻群算法

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

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

(1)

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

(2)

1.2 最大最小螞蟻系統(tǒng)

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

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

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

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

(3)

2 基于視覺修正的MMAS算法

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

2.1 基于啟發(fā)式信息的信息素初始化

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

(4)

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

2.2 基于視覺修正的MMAS算法

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

2.2.1局部路徑優(yōu)化

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

圖1 路徑交叉圖

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

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

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

(5)

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

(6)

基于數(shù)學(xué)原理的交叉路徑消除策略,有利于算法及時消除交叉路徑,用最短的時間快速跳出局部最優(yōu)。

2.2.2新解探索

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

(7)

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

2.2.3“雙優(yōu)”策略改善信息素更新方式

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

(8)

2.3 算法流程

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

步驟2初始化信息素。

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

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

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

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

步驟7判斷歷史最優(yōu)路徑長度出現(xiàn)的次數(shù)是否大于nt,如果是,利用天文蟻檢查歷史最優(yōu)路徑中是否存在路徑交叉的情況,若存在,轉(zhuǎn)到步驟8,若不存在,轉(zhuǎn)到步驟11。

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

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

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

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

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

步驟13禁忌表清空,迭代次數(shù)t=t+1。如果迭代次數(shù)沒有達(dá)到最大值,則轉(zhuǎn)向步驟3,否則輸出最優(yōu)解并退出循環(huán)。

3 實驗與結(jié)果分析

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

續(xù)表1

表1 不同TSP問題對應(yīng)算法的實驗結(jié)果對比

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

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

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

圖4 att48的收斂對比圖

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

4 結(jié) 語

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

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

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

在經(jīng)典TSP問題上的仿真對比實驗表明,VC-MMAS算法較其他4種算法具有更強(qiáng)的尋優(yōu)能力和更高的穩(wěn)定性。下一步工作將針對大型的TSP數(shù)據(jù)集,進(jìn)一步提升算法性能。