求解旅行商問(wèn)題的離散人工螢火蟲算法*

于宏濤 高立群 韓希昌（.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)089；.沈陽(yáng)工程學(xué)院自動(dòng)化學(xué)院，遼寧沈陽(yáng)036）

求解旅行商問(wèn)題的離散人工螢火蟲算法*

于宏濤1高立群1韓希昌2
（1.東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110819；2.沈陽(yáng)工程學(xué)院自動(dòng)化學(xué)院，遼寧沈陽(yáng)110136）

針對(duì)旅行商問(wèn)題，提出了一種結(jié)合變鄰域搜索算法思想的離散人工螢火蟲算法.文中通過(guò)引入交換子和交換序的概念對(duì)人工螢火蟲算法中的距離進(jìn)行了重新定義；為了增加螢火蟲群的多樣性，避免算法過(guò)早陷入局部最優(yōu)，采用了基于變鄰域搜索算法的擾動(dòng)機(jī)制.在多個(gè)旅行商問(wèn)題上的測(cè)試結(jié)果表明，與文獻(xiàn)中的算法相比，文中提出的離散人工螢火蟲算法具有較好的求解性能.

人工螢火蟲算法；變鄰域搜索；旅行商問(wèn)題；組合優(yōu)化

旅行商問(wèn)題（TSP）是運(yùn)籌學(xué)以及最優(yōu)化理論等領(lǐng)域中的一個(gè)經(jīng)典問(wèn)題，它廣泛應(yīng)用于各行各業(yè)，如電路板鉆孔、貨物配送路線和車間調(diào)度安排等問(wèn)題均可轉(zhuǎn)化為TSP，因此TSP的求解成為國(guó)內(nèi)外學(xué)者研究的熱點(diǎn).對(duì)于規(guī)模比較小的TSP，可以應(yīng)用分支定界法、貪婪法和割平面法等精確算法求解，但對(duì)于規(guī)模較大的TSP，應(yīng)用以上精確算法求解時(shí)計(jì)算量太大，在目前的條件下很難實(shí)現(xiàn)，而智能優(yōu)化算法的出現(xiàn)為其求解開辟了新的途徑.

人工螢火蟲算法是模擬自然界中螢火蟲的發(fā)光特性而發(fā)展起來(lái)的一種新型的群智能優(yōu)化算法.根據(jù)模擬方式的不同，Krishnanand等［1］和Yang［2］分別提出了不同版本的人工螢火蟲算法.目前，國(guó)內(nèi)外學(xué)者對(duì)這兩個(gè)版本的人工螢火蟲算法都進(jìn)行了一定的研究及應(yīng)用：文獻(xiàn)［3］中應(yīng)用一種混合螢火蟲算法對(duì)帶有約束的工程設(shè)計(jì)問(wèn)題進(jìn)行求解；文獻(xiàn)［4］中采用螢火蟲算法對(duì)無(wú)線傳感器網(wǎng)絡(luò)中的傳感器部署問(wèn)題進(jìn)行優(yōu)化；文獻(xiàn)［5］中采用螢火蟲算法對(duì)超聲圖像分類問(wèn)題進(jìn)行求解；文獻(xiàn)［6］中采用螢火蟲算法對(duì)最小交叉熵的多閾值進(jìn)行選擇；文獻(xiàn)［7］中提出了連續(xù)空間多目標(biāo)的螢火蟲算法；文獻(xiàn)［8］中將混沌思想融入到螢火蟲算法中，以提升螢火蟲算法的尋優(yōu)性能；文獻(xiàn)［9］中提出了具有兩種移動(dòng)策略的螢火蟲算法，以提高收斂速度及求解精度；文獻(xiàn)［10-11］中分別提出了用于解決TSP的離散人工螢火蟲算法.

但以上研究主要集中于求解連續(xù)變量問(wèn)題，雖然文獻(xiàn)［10-11］中提出的改進(jìn)算法可求解TSP，但其改進(jìn)是基于文獻(xiàn)［1］算法的求解步驟，而文獻(xiàn)［1］與文獻(xiàn)［2］中算法盡管都是模擬螢火蟲的行為特性，但它們的具體實(shí)現(xiàn)截然不同，相對(duì)而言文獻(xiàn)［2］中算法的設(shè)置參數(shù)更少，求解步驟及公式更簡(jiǎn)單.為此，文中以文獻(xiàn)［2］為基礎(chǔ)，在遵循文獻(xiàn)［2］人工螢火蟲算法仿生機(jī)理的基礎(chǔ)上，提出了求解TSP的離散人工螢火蟲算法.

1 人工螢火蟲算法

自然界中的螢火蟲會(huì)發(fā)出熒光信號(hào)，從生物學(xué)角度，其作用有時(shí)是為了吸引異性關(guān)注，求得交配機(jī)會(huì)，繁衍后代；有時(shí)是為了捕食；有時(shí)是因處于危險(xiǎn)境地而將其作為警戒信號(hào).人工螢火蟲算法中僅考慮螢火蟲利用發(fā)出熒光信號(hào)在一定范圍內(nèi)吸引同伴，最終使大多數(shù)螢火蟲聚集在一個(gè)或者多個(gè)位置上，即實(shí)現(xiàn)位置優(yōu)化.

螢火蟲吸引同伴主要取決于熒光亮度和吸引度.其中，熒光亮度取決于自身所在位置的目標(biāo)值，目標(biāo)值越佳，亮度越高；吸引度和亮度緊密相關(guān)，越亮的螢火蟲也擁有越高的吸引度，可以在一定范圍內(nèi)吸引亮度比其弱的螢火蟲向自己移動(dòng).另外，在人工螢火蟲算法中，考慮到螢火中發(fā)光的物理特性，亮度和吸引度都與螢火蟲之間的距離成反比，即隨著距離的增大，熒光亮度和吸引度逐漸減小.

螢火蟲在移動(dòng)過(guò)程中主要遵循如下原則：①螢火蟲移動(dòng)方向由熒光亮度決定，總是向比自身熒光亮度高的螢火蟲移動(dòng)；②螢火蟲移動(dòng)距離由吸引度決定.文中對(duì)螢火蟲熒光亮度和吸引度進(jìn)行如下定義.

定義1螢火蟲的熒光亮度

式中：rij為螢火蟲i與j之間的空間距離；γ為光強(qiáng)吸收系數(shù)，表征熒光隨著距離的增加而逐漸減弱的特性，可設(shè)為常數(shù)；I0為r=0時(shí)螢火蟲的熒光亮度，即自身熒光亮度，也是最大的熒光亮度，其值與目標(biāo)函數(shù)值相關(guān)，目標(biāo)函數(shù)值越優(yōu)，最大熒光亮度越高.

定義2螢火蟲的吸引度

式中，β0為r=0時(shí)螢火蟲的吸引度，即最大的吸引度.

基于定義1，每只螢火蟲采用輪盤賭等方法選擇向比自身熒光亮度高的個(gè)體移動(dòng)；基于定義2，每只螢火蟲可確定移動(dòng)的距離.螢火蟲通過(guò)不斷地更新自身的位置（具體位置更新公式見定義3）來(lái)實(shí)現(xiàn)尋優(yōu)的目的.

定義3螢火蟲i被吸引向螢火蟲j移動(dòng)的位置更新公式為

該位置更新由3部分構(gòu)成：第1部分xi表示螢火蟲i當(dāng)前的空間位置；第2部分β（xj-xi）表示螢火蟲i向螢火蟲j移動(dòng)一定的距離；第3部分表示在進(jìn)行位置更新時(shí)伴有擾動(dòng)機(jī)制，以避免螢火蟲過(guò)早陷入局部最優(yōu)解，其中α為步長(zhǎng)因子，通常是［0，1］之間的常數(shù)，rand為［0，1］之間服從均勻分布的隨機(jī)因子.

2 求解TSP的人工螢火蟲算法

在應(yīng)用人工螢火蟲算法求解TSP時(shí)，需要已知距離和光強(qiáng)吸收系數(shù)等參數(shù)，然后按照式（1）-（3）進(jìn)行位置更新，從而實(shí)現(xiàn)尋優(yōu).文中在應(yīng)用人工螢火蟲算法求解TSP時(shí)，采用了序號(hào)排列編碼法.由于所求問(wèn)題是組合優(yōu)化問(wèn)題，故先對(duì)離散變量距離進(jìn)行定義，再提出離散變量位置更新公式及其擾動(dòng)機(jī)制，最后給出基于離散螢火蟲算法求解TSP的步驟.

為了描述方便，文中首先引入以下定義［12］.

定義4設(shè)n個(gè)節(jié)點(diǎn)的TSP的解序列為S=（ai），i=1，2，…，n，交換子SO（i1，i2）為交換解S中的點(diǎn)ai1和ai2，則S′=S+SO（i1，i2）為解S經(jīng)算子SO（i1，i2）操作后的新解.

如對(duì)于有5個(gè)節(jié)點(diǎn)的TSP，其解為

交換子為SO（2，3），則

定義6不同的交換序作用于同一解上可能產(chǎn)生相同的新解，所有相同效果的交換序的集合稱為交換序的等價(jià)集.

定義7在交換序等價(jià)集中，擁有最少交換子的交換序被稱為該等價(jià)集的基本交換序.

求解連續(xù)變量的優(yōu)化問(wèn)題時(shí)，螢火蟲間的空間距離可采用歐式距離進(jìn)行計(jì)算；當(dāng)求解TSP時(shí)，解向量為離散變量，其空間距離不能按歐式距離公式進(jìn)行計(jì)算.文中定義螢火蟲間的空間距離為

式中，A為兩只螢火蟲解向量基本交換序中的交換子個(gè)數(shù)，N為所要拜訪城市的數(shù)量.

求得r后，螢火蟲的熒光亮度即可按式（1）進(jìn)行計(jì)算，從而每只螢火蟲可以基于輪盤賭選擇移向熒光亮度更高的其他個(gè)體.

在求解連續(xù)變量的優(yōu)化問(wèn)題時(shí)，螢火蟲移動(dòng)距離可根據(jù)吸引度進(jìn)行計(jì)算，但當(dāng)求解TSP時(shí)，螢火蟲的移動(dòng)距離不應(yīng)是連續(xù)變量，文中定義螢火蟲i向螢火蟲j移動(dòng)的距離為

式中，randint（0，Aij）表示產(chǎn)生0到Aij的隨機(jī)整數(shù)，Aij為螢火蟲i和j的基本交換序的交換子個(gè)數(shù)，βij為隨機(jī)保留基本交換序中0到Aij個(gè)交換子，即螢火蟲i向螢火蟲j隨機(jī)移動(dòng)一定的距離，進(jìn)而按式（6）實(shí)現(xiàn)位置更新，即

求解連續(xù)變量的優(yōu)化問(wèn)題時(shí)，螢火蟲算法存在連續(xù)變量的擾動(dòng)機(jī)制.當(dāng)求解TSP時(shí)，為了避免螢火蟲算法陷入局部最優(yōu)，文中基于變鄰域搜索（VNS）算法［13］的思想，定義了離散變量的擾動(dòng)機(jī)制.在搜索過(guò)程中采用多種鄰域結(jié)構(gòu)形式進(jìn)行搜索，系統(tǒng)地改變其鄰域，從而拓展搜索范圍，增強(qiáng)算法跳出局部最優(yōu)的能力.

根據(jù)TSP的求解特點(diǎn)，文中應(yīng)用了3種鄰域結(jié)構(gòu)：

（1）Insert鄰域，在解序列中隨機(jī)選擇兩個(gè)不同的位置x和y，把位置x對(duì)應(yīng)的城市插入位置y，記為Insert（x，y）；

（2）Swap鄰域，在解序列中隨機(jī)選擇兩個(gè)不同的位置x和y，互換這兩個(gè)位置對(duì)應(yīng)的城市，記為Swap（x，y）；

（3）2-opt鄰域，將邊（i，i+1）、（j，j+1）用（i，j）、（i+1，j+1）代替，這種交換使得原來(lái)路線中邊（i+1，j）的方向發(fā)生變化.

應(yīng)用離散螢火蟲算法求解TSP的步驟如下：（1）初始化算法基本參數(shù)，包括螢火蟲數(shù)目m、光強(qiáng)吸收系數(shù)γ、最大迭代次數(shù)Tmax.

（2）隨機(jī)初始化每只螢火蟲的解序列，計(jì)算螢火蟲的目標(biāo)函數(shù)值Pi和最大熒光亮度I0，

式中，Pg為目前搜索到的最優(yōu)解.

（3）根據(jù)式（1）、（4）、（5）和（7）計(jì)算群體中螢火蟲的相對(duì)亮度I和吸引度βij，從而確定每只螢火蟲的移動(dòng)方向和移動(dòng)距離.

（4）根據(jù)式（6）更新螢火蟲的位置.

（5）基于一定的概率選擇變鄰域搜索的3種鄰域，重復(fù)執(zhí)行n次，選擇目標(biāo)函數(shù)值最優(yōu)的位置作為螢火蟲的當(dāng)前位置.

（6）根據(jù)更新后螢火蟲的位置，重新計(jì)算螢火蟲的目標(biāo)函數(shù)值Pi，并與當(dāng)前最優(yōu)解Pg進(jìn)行比較，如果更優(yōu)，則更新Pg.

（7）如滿足結(jié)束條件，則循環(huán)結(jié)束并輸出計(jì)算結(jié)果，否則跳轉(zhuǎn)到步驟（3）.

3 仿真結(jié)果與分析

3.1光強(qiáng)吸收系數(shù)γ對(duì)求解性能的影響

光強(qiáng)吸收系數(shù)γ是螢火蟲算法的主要參數(shù)，為了分析該系數(shù)對(duì)算法求解性能的影響，文中在給定其他參數(shù)的條件下，針對(duì)不同γ值進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)中其他參數(shù)的設(shè)置如下：最大迭代Tmax=500，螢火蟲數(shù)目m=50，抗干擾機(jī)制中的3種鄰域選擇幾率相同，均為1/3，變鄰域搜索執(zhí)行次數(shù)n=3，對(duì)Berlin52的TSP獨(dú)立運(yùn)行30次，不同γ值的運(yùn)行結(jié)果如表1所示.

表1 γ對(duì)螢火蟲算法性能的影響Table 1Effect of γ on the performance of firefly algorithm

從表1可以看出，當(dāng)γ逐漸增大時(shí)，算法的求解性能并沒有明顯的變化規(guī)律，在γ為0.01、0.02、0.03、0.04、0.06、0.09和0.11時(shí)，螢火蟲算法所得到的計(jì)算結(jié)果7544.3659為最好，其中γ為0.03時(shí)，算法所得到的平均值8007.7480及標(biāo)準(zhǔn)差207.4464均為最小，此時(shí)算法所得到的最差值雖然不是最佳，但位居次席也比較理想，因此，可以認(rèn)為：對(duì)此問(wèn)題，當(dāng)γ為0.03時(shí)，螢火蟲算法具有較好的求解性能.實(shí)際上，考慮隨機(jī)因素的影響，從表1可以進(jìn)一步看出，參數(shù)γ可以在一個(gè)較大的范圍內(nèi)選取，不同的選取對(duì)尋優(yōu)結(jié)果的影響并不是特別的明顯，這是螢火蟲算法的一大優(yōu)點(diǎn).

3.2變鄰域搜索干擾機(jī)制對(duì)求解性能的影響

為了增加解的多樣性，文中提出了基于變鄰域搜索的干擾機(jī)制，設(shè)置了3種鄰域，選擇Insert鄰域、Swap鄰域、2-opt鄰域的比例為k1：k2：k3，采用不同的鄰域比例求解Berlin52的TSP.實(shí)驗(yàn)中，最大迭代Tmax=500，螢火蟲數(shù)目m=50，光強(qiáng)吸收系數(shù)γ=0.03，變鄰域搜索執(zhí)行次數(shù)n=3，算法獨(dú)立運(yùn)行30次，計(jì)算結(jié)果如表2所示.

從表2可以看出，鄰域比的選取對(duì)尋優(yōu)結(jié)果有較大的影響，但相比之下，較差鄰域比所占比例并不大.除了k1：k2：k3為2：3：5和2：5：3外，采用其他鄰域比均能得到最優(yōu)值7 544.365 9.當(dāng)鄰域比為2：1：2時(shí)，算法所得到的平均值8002.4153及最差值8446.8225均為最小，且所得到的標(biāo)準(zhǔn)差216.8828也和最小標(biāo)準(zhǔn)差207.4464相差不大.因此，在實(shí)際優(yōu)化中，只需簡(jiǎn)單做幾次實(shí)驗(yàn)比較，就能夠?qū)ふ页鲎顑?yōu)的結(jié)果，而無(wú)需大量的盲目試探.

表2 k1：k2：k3對(duì)螢火蟲算法性能的影響Table2Effectofk1：k2：k3ontheperformanceoffireflyalgorithm

3.3與其他方法的比較

為了進(jìn)一步驗(yàn)證文中所提算法的求解性能，選用多個(gè)TSPLIB標(biāo)準(zhǔn)庫(kù)實(shí)例進(jìn)行實(shí)驗(yàn)測(cè)試，并將測(cè)試所得到的結(jié)果與其他文獻(xiàn)所提供的結(jié)果進(jìn)行對(duì)比.為了使文中算法與其他文獻(xiàn)算法具有可比性，綜合考慮各文獻(xiàn)，螢火蟲算法參數(shù)設(shè)置如下：當(dāng)城市數(shù)小于48時(shí)，螢火蟲數(shù)目m=20，否則m=50，光強(qiáng)吸收系數(shù)γ=0.03，鄰域比k1：k2：k3=2：1：2，變鄰域搜索執(zhí)行次數(shù)n=3，算法獨(dú)立運(yùn)行20次，計(jì)算結(jié)果如表3所示.從表中可知：對(duì)于Burma14、Ulysses16、Ulysses22和Berlin52，文中算法與STA算法得到了相同的最優(yōu)值，但文中算法得到的平均值和標(biāo)準(zhǔn)差總體上小于STA算法；對(duì)于Att48和Eil51，文中算法得到了更小的最優(yōu)值，分別為3.370 1×104和429.4841，相應(yīng)的仿真實(shí)驗(yàn)結(jié)果如圖1和2所示.因此，求解TSP時(shí)文中算法的性能優(yōu)于STA.對(duì)于Oliver30、Eil51和St70，與改進(jìn)蟻群算法［15］相比，文中算法找到了更優(yōu)的路徑，迭代次數(shù)減少了75%，只是算術(shù)平均值增加了1.1%.因此，綜合看來(lái)文中算法比改進(jìn)蟻群算法具有更好的尋優(yōu)能力，St70實(shí)例的仿真實(shí)驗(yàn)結(jié)果如圖3所示.對(duì)于Burma14和Oliver30，文中算法與DGSO［10］均得到了相同的最優(yōu)值，但對(duì)于Oliver30，文中算法的算術(shù)平均值增加了3.57%，螢火蟲數(shù)目卻減少了80%；對(duì)于Att48和Eil51，表面上看文中算法的性能比DGSO［10］微差，且迭代次數(shù)更多，但文中算法的螢火蟲數(shù)目減少了50%，且DGSO包含了C2opt算子，該步驟是對(duì)構(gòu)成路徑的所有城市進(jìn)行2-opt優(yōu)化，即使在迭代次數(shù)較少的情況下，該步驟也將花費(fèi)大量的時(shí)間，如對(duì)于實(shí)例Eil51，每次迭代就需要對(duì)新產(chǎn)生的路徑執(zhí)行1128次2-opt操作，計(jì)算量大大增加.對(duì)于Berlin52，文中算法與DGSO［11］得到了相同的最優(yōu)值；對(duì)于Eil51和St70，文中算法的最優(yōu)值相對(duì)于DGSO［11］分別增加了0.14%和0.35%，且迭代次數(shù)看似更多，但DGSO［11］的仿真實(shí)驗(yàn)參數(shù)采用的是基于多次實(shí)驗(yàn)所得的最佳參數(shù)，且不同實(shí)例參數(shù)設(shè)置差異較大，影響了該算法的實(shí)際應(yīng)用價(jià)值.另外，DGSO［11］同樣包含計(jì)算量較大的C2opt算子.因此，綜合尋優(yōu)質(zhì)量和尋優(yōu)時(shí)間來(lái)看，文中算法的性能優(yōu)于文獻(xiàn)［10-11］中的DGSO性能.

表3 標(biāo)準(zhǔn)測(cè)試問(wèn)題的計(jì)算結(jié)果Table 3Calculation results for benchmark test problems

圖1 實(shí)例Att48的仿真實(shí)驗(yàn)結(jié)果Fig.1Simulation results of sample Att48

圖2 實(shí)例Eil51的仿真實(shí)驗(yàn)結(jié)果Fig.2Simulation results of sample Eil51

圖3 實(shí)例St70的仿真實(shí)驗(yàn)結(jié)果Fig.3Simulation results of sample St70

4 結(jié)論

TSP是運(yùn)籌學(xué)、圖論和組合優(yōu)化中的NP難題，在許多行業(yè)具有廣泛的應(yīng)用，文中以求解TSP為例，提出了一種離散人工螢火蟲算法的具體實(shí)現(xiàn)，拓展了人工螢火蟲算法的應(yīng)用領(lǐng)域.該離散人工螢火蟲算法主要依據(jù)交換子和交換序進(jìn)行距離定義；采用了基于變鄰域搜索思想的擾動(dòng)策略，增加了搜索區(qū)域，抑制停滯早熟現(xiàn)象的發(fā)生.仿真實(shí)驗(yàn)結(jié)果表明，離散人工螢火蟲算法在收斂速度、尋優(yōu)度和穩(wěn)定性等方面相比最近文獻(xiàn)中的算法更為理想.該算法通過(guò)適當(dāng)?shù)淖兓?，也可以推廣用于解決其他組合優(yōu)化問(wèn)題.

［1］Krishnanand K N，Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics［C］∥Proceedings of IEEE Swarm Intelligence Symposium.Piscataway：IEEE，2005：84-91.

［2］Yang X S.Nature-inspired metaheuristic algorithms［M］. London：Luniver Press，2008：83-96.

［3］Zhou Y，Zhou G，Zhang J.A hybrid glowworm swarm optimization algorithm for constrained engineering design problems［J］.Appl Math，2013，7（1）：379-388.

［4］Liao W H，Kao Y，Li Y S.A sensor deployment approach usingglowworm swarm optimization algorithm in wireless sensor networks［J］.Expert Systems with Applications，2011，38（10）：12180-12188.

［5］HorngMH.Theglowwormswarmoptimizationfortraining the radial basis function network in ultrasonic supraspinatus image classification［J］.Advanced Science Letters，2013，19（9）：2724-2727.

［6］Horng M H，Liou R J.Multilevel minimum cross entropy threshold selection based on the firefly algorithm［J］.ExpertSystemswithApplications，2011，38（12）：14805-14811.

［7］Yang X S.Multiobjective firefly algorithm for continuous optimization［J］.Engineering with Computers，2013，29（2）：175-184.

［8］Gandomi A H，Yang X S，Talatahari S，et al.Firefly algorithm with chaos［J］.Communications in Nonlinear Science and Numerical Simulation，2013，18（1）：89-98.

［9］Wu B，Qian C，Ni W，et al.The improvement of glowworm swarm optimization for continuous optimization problems［J］.Expert Systems with Applications，2012，39（7）：6335-6342.

［10］周永權(quán)，黃正新，劉洪霞.求解TSP問(wèn)題的離散型螢火蟲群優(yōu)化算法［J］.電子學(xué)報(bào)，2012，40（6）：1164-1170. Zhou Yong-quan，Huang Zheng-xin，Liu Hong-xia.Discrete glowworm swarm optimization algorithm for TSP problem［J］.Acta Electronica Sinica，2012，40（6）：1164-1170.

［11］周永權(quán)，黃正新.求解TSP的人工螢火蟲群優(yōu)化算法［J］.控制與決策，2012，27（12）：1816-1821. Zhou Yong-quan，Huang Zheng-xin.Artificial glowworm swarm optimization algorithm for TSP［J］.Control and Decision，2012，27（12）：1816-1821.

［12］黃嵐，王康平，周春光，等.粒子群優(yōu)化算法求解旅行商問(wèn)題［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，2003，41（4）：477-480. Huang Lan，Wang Kang-ping，Zhou Chun-guang，et al. Particle swarm optimization for traveling salesman problems［J］.JournalofJilin University：Science Edition，2003，41（4）：477-480.

［13］Mladenovic N，Hansen P.Variable neighborhood search［J］.Computers and Operations Research，1997，24（11）：1097-1100.

［14］Yang C H，Tang X L，Zhou X J，et al.A discrete state transition algorithm for traveling salesman problem［J］. Control Theory&Applicaions，2013，30（8）：1040-1046.

［15］孟祥萍，片兆宇，沈中玉，等.基于方向信息素協(xié)調(diào)的蟻群算法［J］.控制與決策，2013，28（5）：782-786. Meng Xiang-ping，Pian Zhao-yu，Shen Zhong-yu，et al. Ant algorithm based on direction-coordinating［J］.Control and Decision，2013，28（5）：782-786.Discrete Artificial Firefly Algorithm for Solving Traveling Salesman Problems

Yu Hong-tao1Gao Li-qun1Han Xi-chang2
（1.School of Information Science and Technology，Northeastern University，Shenyang 110819，Liaoning，China；2.College of Automation，Shenyang Institute of Engineering，Shenyang 110136，Liaoning，China）

Proposed in this paper is a discrete artificial firefly algorithm combined with variable neighborhood search algorithm，which is used to solve traveling salesman problems.First，the distance of artificial firefly algorithm is redefined by introducing the concepts of swap operator and swap sequence.Secondly，in order to increase the diversity of firefly swarms and to avoid quick convergence to local optimal solution，a perturbation mechanism is designed on the basis of variable neighborhood search algorithm.Then，several different traveling salesman problems are solved by using the proposed algorithm，and the results finally show that the proposed algorithm is superior to the typical ones in literatures because it helps obtain good solving results.

artificial firefly algorithm；variable neighborhood search；traveling salesman problem；combinatorial optimization

Supported by the National Natural Science Foundation of China（61273155）

TP18

10.3969/j.issn.1000-565X.2015.01.020

1000-565X（2015）01-0126-06

2014-03-24

國(guó)家自然科學(xué)基金資助項(xiàng)目（61273155）；遼寧省教育廳一般項(xiàng)目（L2014530）

于宏濤（1978-），男，在職博士生，沈陽(yáng)工程學(xué)院講師，主要從事智能優(yōu)化算法研究.E-mail：neu970773@sohu.com