改進(jìn)的麻雀搜索算法及其求解旅行商問題①

張?jiān)聴?莫愿斌

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

2(廣西民族大學(xué) 廣西混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室,南寧 530006)

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

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

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

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

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

1 麻雀搜索算法

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

麻雀種群中的發(fā)現(xiàn)者的位置更新公式為:

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

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

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

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

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

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

步驟1.初始化最大迭代次數(shù),種群數(shù)量N,發(fā)現(xiàn)這比例PD,偵察者比例SD、警戒閾值R2.

步驟2.計(jì)算麻雀種群的適度值并進(jìn)行排序,找出當(dāng)前最差適度個體與最優(yōu)適度值個體.

步驟3.應(yīng)用式(1)對發(fā)現(xiàn)者進(jìn)行位置更新.

步驟4.應(yīng)用式(2)對跟隨者進(jìn)行位置更新.

步驟5.應(yīng)用式(3)對預(yù)警者進(jìn)行位置更新.

步驟6.完成當(dāng)前迭代,得到新的位置.

步驟7.計(jì)算當(dāng)前麻雀種群的適度值,如果優(yōu)于之前位置,更新麻雀種群位置.

步驟8.判斷是否滿足最大迭代次數(shù)或者精度要求,若是,結(jié)束迭代輸出最優(yōu)結(jié)果,否則返回步驟3.

2 改進(jìn)的麻雀搜索算法

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

2.1 改進(jìn)發(fā)現(xiàn)者更新位置

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

其中,Q+1為均差為1,方差為1的正態(tài)隨機(jī)分布數(shù).Q為標(biāo)準(zhǔn)正態(tài)隨機(jī)分布數(shù).

2.2 改進(jìn)預(yù)警者更新位置

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

如果該麻雀處于最優(yōu)位置,則逃離到最優(yōu)位置與最差位置之間的隨機(jī)位置,否則逃離到自己與隨機(jī)位置之間的隨機(jī)位置,β為標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù).

2.3 高斯變異策略

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

2.4 改進(jìn)的麻雀搜索算法步驟

步驟1.初始化最大迭代次數(shù),種群數(shù)量N,發(fā)現(xiàn)者比例PD,偵察者比例SD、警戒閾值R2.

步驟2.計(jì)算麻雀種群的適度值并進(jìn)行排序,找出當(dāng)前最差適度個體與最優(yōu)適度值個體.

步驟3.應(yīng)用改進(jìn)式(4)對發(fā)現(xiàn)者進(jìn)行位置更新.

步驟4.應(yīng)用式(2)對跟隨者進(jìn)行位置更新.

步驟5.應(yīng)用改進(jìn)式(5)對預(yù)警者進(jìn)行位置更新.

步驟6.完成當(dāng)前迭代,得到新的位置.

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

步驟8.判斷是否滿足最大迭代次數(shù)或者精度要求,若是,結(jié)束迭代輸出最優(yōu)結(jié)果,否則返回步驟3.

3 算法性能測試

為驗(yàn)證改進(jìn)的麻雀搜索算法能夠改善原算法的缺點(diǎn),證明其有效性.本文將ISSA 與基本麻雀搜索算法、粒子群優(yōu)化算法、鯨魚優(yōu)化算法、灰狼優(yōu)化算法使用6 個基準(zhǔn)測試函數(shù)進(jìn)行對比實(shí)驗(yàn).

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

3.1 參數(shù)設(shè)置

在相同的實(shí)驗(yàn)環(huán)境下,設(shè)置種群數(shù)量為30,最大迭代次數(shù)為1 000,對每一個測試函數(shù)進(jìn)行獨(dú)立的20 次實(shí)驗(yàn),每一個測試的優(yōu)化算法均用文獻(xiàn)[4,10,11,17]中所給出的原始參數(shù)值如表1.6 個基準(zhǔn)測試函數(shù)分別為表2的單峰基準(zhǔn)測試函數(shù),表3的多峰基準(zhǔn)測試函數(shù),表4的固定尺寸的多峰基準(zhǔn)測試函數(shù).

表1 算法的初始參數(shù)

表2 單峰基準(zhǔn)測試函數(shù)

表3 多峰基準(zhǔn)測試函數(shù)

表4 固定尺寸的多峰基準(zhǔn)測試函數(shù)

3.2 算法性能測試實(shí)驗(yàn)結(jié)果分析

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

圖1 F1的收斂曲線

圖2 F2的收斂曲線

圖3 F3的收斂曲線

圖4 F4的收斂曲線

圖5 F5的收斂曲線

圖6 F6的收斂曲線

表5 5 種算法的20 次實(shí)驗(yàn)結(jié)果

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

4 ISSA 求解旅行商問題

4.1 問題描述

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

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

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

4.2 實(shí)驗(yàn)測試

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

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

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

圖7 Burma14 最優(yōu)路徑圖

圖9 Eil51 最優(yōu)路徑圖

表6 TSP 問題求解實(shí)驗(yàn)結(jié)果

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

5 結(jié)論與展望

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

圖8 A280 最優(yōu)路徑圖

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

相信隨著麻雀搜索算法的不斷發(fā)展與改進(jìn),麻雀搜索算法將在人工智能領(lǐng)域中的組合優(yōu)化、計(jì)算智能、圖像處理、數(shù)據(jù)挖掘領(lǐng)域?qū)l(fā)揮巨大的優(yōu)勢.