于宏濤 高立群 韓希昌（.東北大學信息科學與工程學院，遼寧沈陽089；.沈陽工程學院自動化學院，遼寧沈陽036）

求解旅行商問題的離散人工螢火蟲算法*

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

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

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

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

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

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

1 人工螢火蟲算法

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

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

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

定義1螢火蟲的熒光亮度

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

定義2螢火蟲的吸引度

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

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

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

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

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

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

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

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

如對于有5個節(jié)點的TSP，其解為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2變鄰域搜索干擾機制對求解性能的影響

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

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

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

3.3與其他方法的比較

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

表3 標準測試問題的計算結(jié)果Table 3Calculation results for benchmark test problems

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

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

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

4 結(jié)論

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

［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問題的離散型螢火蟲群優(yōu)化算法［J］.電子學報，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)化算法求解旅行商問題［J］.吉林大學學報：理學版，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

國家自然科學基金資助項目（61273155）；遼寧省教育廳一般項目（L2014530）

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