張?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)問題.旅行商問題的表述比較容易,但對(duì)于路徑的優(yōu)化求解比較困難.對(duì)于TSP 問題求解的傳統(tǒng)方法有蠻力法、動(dòng)態(tài)規(guī)劃法、分枝限界法等[2],但當(dāng)TSP 問題的規(guī)模較大時(shí),傳統(tǒng)算法往往不能解決.針對(duì)大規(guī)模的TSP 問題,近年來興起的群體智能優(yōu)化算法在該問題的求解中得到了很好的應(yīng)用.

群體智能優(yōu)化算法是一種基于概率而進(jìn)行隨機(jī)搜索的進(jìn)化算法,通過模擬昆蟲、魚群、鳥群、獸群等生物的覓食方式,對(duì)群體之間信息的交流進(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 個(gè)方面:1)單純動(dòng)物個(gè)體的覓食行為;2)單純動(dòng)物個(gè)體的社會(huì)行為;3)生物群體的覓食行為與社會(huì)行為.專家學(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]等.

對(duì)于群體智能優(yōu)化算法在優(yōu)化問題上的應(yīng)用也得到了進(jìn)一步的研究與發(fā)展[12],針對(duì)旅行商問題的求解,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],相對(duì)于其他的群體智能優(yōu)化算法在收斂速度、搜索精度、穩(wěn)定性方面有明顯的優(yōu)勢(shì).但是,在搜索接近全局最優(yōu)時(shí),存在種群的多樣性減少,容易陷入局部最優(yōu)等問題.本文通過對(duì)其改進(jìn),并應(yīng)用在旅行商問題的求解中,獲得了較好的結(jié)果.

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

1 麻雀搜索算法

麻雀搜索算法是受麻雀群體的捕食與反捕食行為啟發(fā)得來.麻雀的覓食過程遵循發(fā)現(xiàn)者-跟隨者模型,同時(shí)引入麻雀對(duì)于捕食者的預(yù)警機(jī)制.麻雀群體種有發(fā)現(xiàn)者、跟隨者、預(yù)警者3 種角色.種群中適度值較高的麻雀作為發(fā)現(xiàn)者,負(fù)責(zé)找到食物并且為其他麻雀提供食物的方位.除去作為發(fā)現(xiàn)者的麻雀,其他個(gè)體則為跟隨者,跟隨發(fā)現(xiàn)者進(jìn)行覓食.同時(shí),跟隨者會(huì)監(jiān)視發(fā)現(xiàn)者,并對(duì)其進(jìn)行食物的掠奪提高自己的適應(yīng)度,從而成為發(fā)現(xiàn)者.在麻雀群體中,存在一定數(shù)量的預(yù)警者,當(dāng)預(yù)警值大于安全值時(shí),預(yù)警者會(huì)發(fā)出叫聲為其他麻雀提供信號(hào),逃離危險(xiǎn)區(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的矩陣,其中每個(gè)內(nèi)部元素都為1.

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

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

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

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

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

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

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

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

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

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

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

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

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

為了使SSA 算法能夠避開向原點(diǎn)收斂的弊端,將算法向最優(yōu)位置跳躍的操作轉(zhuǎn)換為向最優(yōu)位置的移動(dòng),將式(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)危險(xiǎn)后能夠逃離到最優(yōu)的安全位置,提高算法的全局搜索能力,將式(3)進(jìn)行如下修改:

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

2.3 高斯變異策略

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

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

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

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

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

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

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

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

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

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

3 算法性能測(cè)試

為驗(yàn)證改進(jìn)的麻雀搜索算法能夠改善原算法的缺點(diǎn),證明其有效性.本文將ISSA 與基本麻雀搜索算法、粒子群優(yōu)化算法、鯨魚優(yōu)化算法、灰狼優(yōu)化算法使用6 個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行對(duì)比實(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,對(duì)每一個(gè)測(cè)試函數(shù)進(jìn)行獨(dú)立的20 次實(shí)驗(yàn),每一個(gè)測(cè)試的優(yōu)化算法均用文獻(xiàn)[4,10,11,17]中所給出的原始參數(shù)值如表1.6 個(gè)基準(zhǔn)測(cè)試函數(shù)分別為表2的單峰基準(zhǔn)測(cè)試函數(shù),表3的多峰基準(zhǔn)測(cè)試函數(shù),表4的固定尺寸的多峰基準(zhǔn)測(cè)試函數(shù).

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

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

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

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

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

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

圖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ī)則對(duì)全局最優(yōu)解進(jìn)行擾動(dòng),能夠明顯改善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].

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

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

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

本實(shí)驗(yàn)采用tsplib 中的burma14、A280和Eil51的TSP 數(shù)據(jù)對(duì)本文提出的改進(jìn)的麻雀搜索算法與基本麻雀搜索算法、進(jìn)行仿真實(shí)驗(yàn)結(jié)果與文獻(xiàn)[21,22]給出的數(shù)據(jù)進(jìn)行對(duì)比.每個(gè)算法對(duì)TSP 數(shù)據(jù)進(jìn)行20 次獨(dú)立實(shí)驗(yàn).設(shè)置的初始參數(shù)為:種群麻雀的個(gè)數(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í),與其他群體算法相比能在更少的迭代次數(shù)與時(shí)間內(nèi)求得最優(yōu)路徑,并且最優(yōu)解相對(duì)更好.體現(xiàn)出求TSP 問題時(shí)的優(yōu)越性,并且改進(jìn)后的麻雀搜索算法相對(duì)于基本麻雀搜索算法的求解速度更快,路徑更短.

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

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

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

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

5 結(jié)論與展望

本文對(duì)2020年最新提出的麻雀搜索優(yōu)化算法[16]的原理、種群位置更新策略、算法流程進(jìn)行了分析,針對(duì)麻雀搜索算法在接近全局最優(yōu)時(shí),會(huì)出現(xiàn)種群多樣性減少,容易陷入局部最優(yōu),出現(xiàn)早熟現(xiàn)象的缺點(diǎn),改進(jìn)發(fā)現(xiàn)者與偵察者的位置更新公式,引入高斯變異策略對(duì)全局最優(yōu)解進(jìn)行擾動(dòng).通過對(duì)比實(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)麻雀搜索算法對(duì)于最優(yōu)路徑算法與其他群體智能優(yōu)化算法相比更有具優(yōu)越性.

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