改進的麻雀搜索算法及其求解旅行商問題①

張月棟,莫愿斌

1(廣西民族大學 電子信息學院,南寧 530006)

2(廣西民族大學 廣西混雜計算與集成電路設計分析重點實驗室,南寧 530006)

旅行商(TSP)問題是數學領域組合優化中著名的NP 難題之一,又稱旅行推銷員問題[1].該問題的求解一直是學術界研究的熱點問題.旅行商問題的表述比較容易,但對于路徑的優化求解比較困難.對于TSP 問題求解的傳統方法有蠻力法、動態規劃法、分枝限界法等[2],但當TSP 問題的規模較大時,傳統算法往往不能解決.針對大規模的TSP 問題,近年來興起的群體智能優化算法在該問題的求解中得到了很好的應用.

群體智能優化算法是一種基于概率而進行隨機搜索的進化算法,通過模擬昆蟲、魚群、鳥群、獸群等生物的覓食方式,對群體之間信息的交流進行抽象,從而快速找到問題的最優解[3].“群體智能”的概念最早由Beni和Wang 在文獻[4]中提出.之后群體智能優化算法得到迅速的發展,最具代表性的是1991年Colorni和Dorigo 提出的蟻群算法(ACO)[5]以及1995年Kennedy和Eberhart 提出的粒子群優化算法(PSO)[6].在此之后,群體智能算法的靈感來源主要有3 個方面:1)單純動物個體的覓食行為;2)單純動物個體的社會行為;3)生物群體的覓食行為與社會行為.專家學者因此提出了許多群體智能優化算法,例如2003年Eusuff等提出的混合蛙跳算法(SFLA)[7]、2009年Karaboga等提出的人工蜂群算法(ABC)[8]、2008年Yang提出的螢火蟲優化算法(GSO)[9],2014年Mirjalili等提出的灰狼優化算法(GWO)[10]與2016年提出的鯨魚優化算法(WOA)[11]等.

對于群體智能優化算法在優化問題上的應用也得到了進一步的研究與發展[12],針對旅行商問題的求解,Mahi 等提出了一種求解標準TSP的混合算法PSOACO-3-opt[13],Geng 等提出了一種有效的基于模擬退火(SA)和貪婪搜索技術的局部搜索算法來求解TSP問題[14],Jolai和Ghanbari 提出了一種改進的人工神經網絡(ANN)方法來求解TSP[15]等.

麻雀搜索算法(SSA)是Xue 等[16]2020年新提出的元啟發式群體智能優化算法.研究表明[17],相對于其他的群體智能優化算法在收斂速度、搜索精度、穩定性方面有明顯的優勢.但是,在搜索接近全局最優時,存在種群的多樣性減少,容易陷入局部最優等問題.本文通過對其改進,并應用在旅行商問題的求解中,獲得了較好的結果.

本文對麻雀搜索算法的搜索策略與算法的基本流程進行研究分析,針對SSA 容易陷入局部最優問題,通過改進發現者與偵查者的位置更新公式,引入高斯變異策略,提出一種改進的麻雀搜索算法(ISSA).將ISSA 算法與基本SSA 算法、粒子群優化算法(PSO)、鯨魚優化算法、灰狼優化算法使用6 個基準測試函數進行性能對比測試實驗,驗證ISSA 算法的有效性,最后將其應用在旅行商問題的求解中,驗證ISSA 算法與SSA 算法對于求解TSP 問題的可行性與優越性.

1 麻雀搜索算法

麻雀搜索算法是受麻雀群體的捕食與反捕食行為啟發得來.麻雀的覓食過程遵循發現者-跟隨者模型,同時引入麻雀對于捕食者的預警機制.麻雀群體種有發現者、跟隨者、預警者3 種角色.種群中適度值較高的麻雀作為發現者,負責找到食物并且為其他麻雀提供食物的方位.除去作為發現者的麻雀,其他個體則為跟隨者,跟隨發現者進行覓食.同時,跟隨者會監視發現者,并對其進行食物的掠奪提高自己的適應度,從而成為發現者.在麻雀群體中,存在一定數量的預警者,當預警值大于安全值時,預警者會發出叫聲為其他麻雀提供信號,逃離危險區域,防止被捕食.麻雀搜索算法中麻雀角色具體位置更新公式如下:

麻雀種群中的發現者的位置更新公式為:

其中,麻雀種群中發現者所占的比例為10%–20%,式中t為當前的迭代數,itermax為最大迭代數,α為(0,1]之間均勻的隨機數,R2∈[0,1],S T∈[0.5,1.0]分別表示預警值與安全值.Q為服從正態分布的隨機數,L為1×d的矩陣,其中每個內部元素都為1.

麻雀種群中跟隨者的位置更新公式為:

其中,Xworst,Xtp+1分別為種群中在第t次迭代與第t+1次迭代中,在第j維處于最差位置與局部最優位置的個體,A是一個矩陣內部元素為1 或?1的多維矩陣.

麻雀種群中預警者的位置更新公式如下:

其中,預警者所占的比例為10%–20%,Xbtest為當前麻雀種群的全局最優位置的個體,β為服從正態分布,均值為0,方差為1的控制步長的參數,ε為一個極小的常數,用于避免式中分母出現0的情況,一般設為10E–8.K∈[0,1]用 來控制麻雀的運動方向.fi為當前個體i的適應度值,fg,fw為當前麻雀種群的局部最優適度值與最差適度值.

麻雀搜索算法的基本算法步驟如下:

步驟1.初始化最大迭代次數,種群數量N,發現這比例PD,偵察者比例SD、警戒閾值R2.

步驟2.計算麻雀種群的適度值并進行排序,找出當前最差適度個體與最優適度值個體.

步驟3.應用式(1)對發現者進行位置更新.

步驟4.應用式(2)對跟隨者進行位置更新.

步驟5.應用式(3)對預警者進行位置更新.

步驟6.完成當前迭代,得到新的位置.

步驟7.計算當前麻雀種群的適度值,如果優于之前位置,更新麻雀種群位置.

步驟8.判斷是否滿足最大迭代次數或者精度要求,若是,結束迭代輸出最優結果,否則返回步驟3.

2 改進的麻雀搜索算法

麻雀搜索算法在接近全局最優時,會出現種群多樣性減少,容易陷入局部最優,出現早熟現象的缺點[17].為此,本文對麻雀搜索算法中發現者與偵查者的位置更新進行改進,引入高斯變異策略對全局最優解進行擾動,具體改進策略如下.

2.1 改進發現者更新位置

為了使SSA 算法能夠避開向原點收斂的弊端,將算法向最優位置跳躍的操作轉換為向最優位置的移動,將式(1)進行如下修改:

其中,Q+1為均差為1,方差為1的正態隨機分布數.Q為標準正態隨機分布數.

2.2 改進預警者更新位置

為了讓預警者發現危險后能夠逃離到最優的安全位置,提高算法的全局搜索能力,將式(3)進行如下修改:

如果該麻雀處于最優位置,則逃離到最優位置與最差位置之間的隨機位置,否則逃離到自己與隨機位置之間的隨機位置,β為標準正態分布隨機數.

2.3 高斯變異策略

引入高斯變異算子對每次迭代得到的全局最優解進行擾動,避免算法陷入局部最優,出現早熟現象的缺點,同時也能夠維持種群個體的多樣性[18].高斯變異算子如下:

2.4 改進的麻雀搜索算法步驟

步驟1.初始化最大迭代次數,種群數量N,發現者比例PD,偵察者比例SD、警戒閾值R2.

步驟2.計算麻雀種群的適度值并進行排序,找出當前最差適度個體與最優適度值個體.

步驟3.應用改進式(4)對發現者進行位置更新.

步驟4.應用式(2)對跟隨者進行位置更新.

步驟5.應用改進式(5)對預警者進行位置更新.

步驟6.完成當前迭代,得到新的位置.

步驟7.使用高斯變異算子(6)對全局最優位置進行高斯變異,使用貪婪規則(7)判斷是否更新最優位置.

步驟8.判斷是否滿足最大迭代次數或者精度要求,若是,結束迭代輸出最優結果,否則返回步驟3.

3 算法性能測試

為驗證改進的麻雀搜索算法能夠改善原算法的缺點,證明其有效性.本文將ISSA 與基本麻雀搜索算法、粒子群優化算法、鯨魚優化算法、灰狼優化算法使用6 個基準測試函數進行對比實驗.

本文實驗所使用的操作系統為Windows 10 專業版64 位,實驗軟件為Matlab R2019b,處理器Intel(R)Core(TM)i5-5257U CPU @ 2.70 GHz.

3.1 參數設置

在相同的實驗環境下,設置種群數量為30,最大迭代次數為1 000,對每一個測試函數進行獨立的20 次實驗,每一個測試的優化算法均用文獻[4,10,11,17]中所給出的原始參數值如表1.6 個基準測試函數分別為表2的單峰基準測試函數,表3的多峰基準測試函數,表4的固定尺寸的多峰基準測試函數.

表1 算法的初始參數

表2 單峰基準測試函數

表3 多峰基準測試函數

表4 固定尺寸的多峰基準測試函數

3.2 算法性能測試實驗結果分析

5 種算法優化6 個基準測試函數的最優值、最差值、平均值對比結果如表5所示,最優結果由粗體標出.從收斂曲線圖(圖1、圖2)可以看出,ISSA 在優化單峰函數時的性能是最好的,有很強的全局搜索能力.從收斂曲線圖(圖3、圖4)可以看出在優化多峰函數時,改進后的麻雀搜索算法的收斂速度隨著迭代次數的增多逐漸加快,能夠快速收斂到最優值,沒有出現早熟現象.總體結果由表5可以看出,改進的麻雀搜索算法在處理含有多個局部最優解的問題上,相對于其他3 種優化算法性能更好.從收斂曲線圖(圖5、圖6)可以看出,在處理固定尺寸的多峰測試函數時,5 種算法的收斂速度基本相同,都是在每次迭代的最開始就快速收斂.但在優化測試函數時,改進麻雀搜索算法的收斂速度相對于其他算法更快.

圖1 F1的收斂曲線

圖2 F2的收斂曲線

圖3 F3的收斂曲線

圖4 F4的收斂曲線

圖5 F5的收斂曲線

圖6 F6的收斂曲線

表5 5 種算法的20 次實驗結果

由上述實驗結果可知,通過改進麻雀搜索算法中發現者與偵察者的位置更新公式,有效的提高了SSA的全局搜索能力,加快了尋優與收斂的速度.通過引入高斯策略,通過貪婪規則對全局最優解進行擾動,能夠明顯改善SSA 算法容易陷入局部最優,出現早熟現象的缺點.綜上所述,證明了改進的麻雀搜索算法的有效性.

4 ISSA 求解旅行商問題

4.1 問題描述

旅行商問題是經典的組合優化NP 問題,又稱之為旅行推銷員問題,最早由Flood 在1956年提出,在運籌學和理論計算機科學中具有非常重要的地位[19].

旅行商問題可以描述為一個商品的推銷員要在若干城市之間推銷商品,該推銷員從某一個城市出發,需要經過所有的城市之后回到出發地.問題是如何選擇行進路線才能夠使得總行程最短[20].

設城市的集合為頂點集V=〈v1,v2,···,vn〉其中每對城市之間的距離為d(vi,vi+1),則城市的旅行最短距離問題的目標函數公式為:

4.2 實驗測試

本實驗采用tsplib 中的burma14、A280和Eil51的TSP 數據對本文提出的改進的麻雀搜索算法與基本麻雀搜索算法、進行仿真實驗結果與文獻[21,22]給出的數據進行對比.每個算法對TSP 數據進行20 次獨立實驗.設置的初始參數為:種群麻雀的個數為100,最大迭代次為1 000,各算法的具體參數按表1給出.

4.3 實驗結果分析

各算法20 次獨立實驗的最優值、平均值、迭代次數如表6所示.圖7–圖9為ISSA 求解3 種TSP 問題的最優路徑圖.從表6的實驗結果可以看出,ISSA算法與SSA 算法在求解TSP 問題時,與其他群體算法相比能在更少的迭代次數與時間內求得最優路徑,并且最優解相對更好.體現出求TSP 問題時的優越性,并且改進后的麻雀搜索算法相對于基本麻雀搜索算法的求解速度更快,路徑更短.

圖7 Burma14 最優路徑圖

圖9 Eil51 最優路徑圖

表6 TSP 問題求解實驗結果

綜上所述,麻雀搜索算法在求解TSP 問題時,與其他群體智能算法相比時間更短,收斂次數更少,因此有更好的優越性,并且改進后的麻雀搜索算法相對于基本麻雀搜索算法的收斂速度更快、路徑相對更優,說明了改進的有效性.

5 結論與展望

本文對2020年最新提出的麻雀搜索優化算法[16]的原理、種群位置更新策略、算法流程進行了分析,針對麻雀搜索算法在接近全局最優時,會出現種群多樣性減少,容易陷入局部最優,出現早熟現象的缺點,改進發現者與偵察者的位置更新公式,引入高斯變異策略對全局最優解進行擾動.通過對比實驗結果表明,在全局搜索能力與收斂性方面,改進麻雀搜索算法的性能明顯優于其他算法,驗證了改進的麻雀搜索算法有效性.

圖8 A280 最優路徑圖

在旅行商求解問題中,改進的麻雀搜索算法提供了一種新的優化方法,通過仿真實驗可以看出改進麻雀搜索算法對于最優路徑算法與其他群體智能優化算法相比更有具優越性.

相信隨著麻雀搜索算法的不斷發展與改進,麻雀搜索算法將在人工智能領域中的組合優化、計算智能、圖像處理、數據挖掘領域將發揮巨大的優勢.