基于視覺(jué)修正的改進(jìn)最大最小螞蟻系統(tǒng)求解TSP

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

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

0 引 言

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

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

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

1 相關(guān)概念

1.1 基本蟻群算法

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

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

(1)

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

(2)

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

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

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

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

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

(3)

2 基于視覺(jué)修正的MMAS算法

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

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

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

(4)

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

2.2 基于視覺(jué)修正的MMAS算法

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

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

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

圖1 路徑交叉圖

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

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

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

(5)

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

(6)

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

2.2.2新解探索

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

(7)

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

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

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

(8)

2.3 算法流程

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

步驟2初始化信息素。

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的VC-MMAS算法的有效性,本文對(duì)TSPLIB數(shù)據(jù)庫(kù)中的TSP問(wèn)題進(jìn)行了求解,為了比較VC-MMAS算法的性能,將實(shí)驗(yàn)結(jié)果與遺傳算法(GA)、粒子群算法(PSO)、自組織神經(jīng)網(wǎng)絡(luò)(SOM)和最大最小螞蟻系統(tǒng)(MMAS)進(jìn)行了比較,實(shí)驗(yàn)中所使用的參數(shù)均經(jīng)過(guò)試驗(yàn)確定。各算法實(shí)驗(yàn)參數(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。針對(duì)10個(gè)TSP問(wèn)題,除SOM外,其他每種算法最大迭代次數(shù)T=1 000。不同TSP問(wèn)題對(duì)應(yīng)算法的實(shí)驗(yàn)結(jié)果見(jiàn)表1。

續(xù)表1

表1 不同TSP問(wèn)題對(duì)應(yīng)算法的實(shí)驗(yàn)結(jié)果對(duì)比

表1展示了對(duì)于每一個(gè)數(shù)據(jù)集,每種算法獨(dú)立運(yùn)行十次,求得每種算法的最優(yōu)路徑長(zhǎng)度(Best Length)、最差路徑長(zhǎng)度(Worst Length)、平均路徑長(zhǎng)度(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é)果波動(dòng)越大。根據(jù)實(shí)驗(yàn)的數(shù)據(jù),圖3展示了CV-MMAS算法在部分?jǐn)?shù)據(jù)集上求解TSP問(wèn)題時(shí)的最優(yōu)路徑。由表1可知,VC-MMAS在10個(gè)數(shù)據(jù)集上都獲解了最優(yōu)路徑,MMAS在berlin52、gr96上也獲解了最優(yōu)路徑,但在這兩個(gè)數(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。由此可見(jiàn),VC-MMAS改進(jìn)效果顯著,相較于其他4種算法,在求解TSP問(wèn)題上有較高的穩(wěn)定性,不易陷入局部最優(yōu)。

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

5種算法在att48上的仿真收斂對(duì)比情況如圖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算法在迭代過(guò)程中不斷跳出局部最優(yōu),每100多代就能更新歷史最優(yōu)解,最終找到了最優(yōu)解。VC-MMAS算法利用啟發(fā)式信息初始化信息素,避免了算法初期的盲目搜索;在算法陷入局部最優(yōu)后引入天文蟻消除局部最優(yōu)、探索新路徑,并使用“雙優(yōu)”策略更新信息素,增加了解的多樣性,避免了算法陷入停滯狀態(tài)。

圖4 att48的收斂對(duì)比圖

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

4 結(jié) 語(yǔ)

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

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

(2) 在算法陷入局部最優(yōu)時(shí),引入依靠太陽(yáng)而非信息素導(dǎo)航的天文蟻,對(duì)歷史最優(yōu)路徑進(jìn)行檢查和修正。當(dāng)存在路徑交叉時(shí),根據(jù)交叉路徑的相對(duì)位置情況采用不同方式直接消除交叉路徑,以較小的時(shí)間代價(jià)找到更優(yōu)的路徑;當(dāng)不存在路徑交叉時(shí),首先調(diào)整信息素,縮小路徑間信息素的差距,其次,天文蟻對(duì)路徑尋優(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問(wèn)題上的仿真對(duì)比實(shí)驗(yàn)表明,VC-MMAS算法較其他4種算法具有更強(qiáng)的尋優(yōu)能力和更高的穩(wěn)定性。下一步工作將針對(duì)大型的TSP數(shù)據(jù)集,進(jìn)一步提升算法性能。