基于改進螢火蟲算法的TSP問題

胡 楠,徐曉光

(安徽工程大學(xué)電氣工程學(xué)院,安徽蕪湖 241000)

?

基于改進螢火蟲算法的TSP問題

胡 楠,徐曉光?

(安徽工程大學(xué)電氣工程學(xué)院,安徽蕪湖 241000)

摘要:針對旅行商問題,提出了一種改進的螢火蟲算法．首先,重新定義螢火蟲個體距離、位置更新公式．其次,為了增加螢火蟲群的多樣性、避免過早陷入局部最優(yōu)、減少算法運行時間,引入了遺傳算法．最后,通過仿真實驗表明,改進后的算法能在迭代次數(shù)較少的情況下更快收斂到最優(yōu)解,證明了所提方法的可行性和有效性．

關(guān) 鍵 詞:旅行商問題;改進的螢火蟲算法;遺傳算法

旅行商問題(Travel Salesman Problem,TSP)是最基本的路線問題,其探索單一旅行者由起點出發(fā),并通過所有給定點后,再回到起點的最小路徑成本問題[1]．求解TSP一直是組合優(yōu)化領(lǐng)域研究的熱點和難點問題之一[2]．目前,為解決TSP問題引入了各種智能算法,如遺傳算法、PSO算法、蟻群算法等[3-5],然而這些方法存在計算存儲量大、運行時間長、求解城市規(guī)模太小等不足．螢火蟲算法(Firefly Algorithm, FA)是近年來提出的一種新型群智能算法,已經(jīng)在很多領(lǐng)域得到了應(yīng)用[6-8],通過模擬自然界中螢火蟲的發(fā)光特性發(fā)展而來,同蟻群算法、魚群算法一樣,也是一種高級啟發(fā)式算法[9]．針對TSP問題,在標準螢火蟲算法的基礎(chǔ)上,提出了一種改進的螢火蟲算法,對螢火蟲個體距離、位置更新公式進行了重新定義．為了提高螢火蟲算法求解TSP問題時的收斂速度,使其找到全局最優(yōu)解,在標準螢火蟲算法中引入了遺傳算法的交叉、變異、逆轉(zhuǎn)操作．

1 標準螢火蟲算法

1．1 標準螢火蟲算法基本概念

螢火蟲算法通過螢火蟲個體之間的相互吸引達到尋優(yōu)的目的,具體來說,就是由于螢火蟲亮度的不同,在一定范圍內(nèi),亮度小的螢火蟲會被亮度大的螢火蟲吸引,從而逐漸向其移動．螢火蟲的亮度與目標函數(shù)有關(guān),所以在螢火蟲移動的過程結(jié)束后,螢火蟲會聚集在亮度最大的螢火蟲位置,即最優(yōu)解,這就是螢火蟲算法的尋優(yōu)過程[9]．

1．2 標準螢火蟲算法的數(shù)學(xué)描述與分析

螢火蟲根據(jù)亮度不同進行選擇移動．亮度分為絕對亮度和相對亮度[9]．絕對亮度,即螢火蟲i在r＝0處的光強度,記為Ii,絕對亮度由目標函數(shù)直接決定,代表解的優(yōu)劣程度;相對亮度,即螢火蟲i在螢火蟲j處的光強度,記為Iij,表達為[10]:

式中,γ為光吸收系數(shù),設(shè)為常數(shù);rij為螢火蟲i到螢火蟲j的距離．

每個螢火蟲都遵循吸引規(guī)則,即絕對亮度小的螢火蟲被絕對亮度大的螢火蟲吸引,吸引力與亮度成比例,螢火蟲i對螢火蟲j的吸引力βij(rij)為[10]:

式中,β0為最大吸引力,即在光源處(r＝0處)螢火蟲的吸引力．

假設(shè)螢火蟲j被螢火蟲i吸引,向其移動,移動后的新位置可根據(jù)位置更新公式計算,表達為[6-7]:

式中,t為迭代次數(shù);→xi、→xj為螢火蟲的空間位置;α為常數(shù),一般可取α∈[0,1];→εj是由高斯分布、均勻分布或者其他分布得到的隨機數(shù)向量．

2 螢火蟲算法TSP實現(xiàn)

2．1 編碼

根據(jù)螢火蟲算法的思想,每個螢火蟲可代表一組解,假設(shè)城市的編號為:cities＝{1,2,3,…,n},那么每個螢火蟲代表n個城市的任意排列,即Path＝{p1,p2,p3,…,pi,…,pn},pi代表途經(jīng)的第i個城市．

2．2 絕對亮度

即目標函數(shù)的值越小,路線長度越短．絕對亮度由目標函數(shù)直接決定,代表解的優(yōu)劣程度,所以,絕對亮度的公式可設(shè)置為:

即路線長度越短,螢火蟲的絕對亮度值越大．

2．3 螢火蟲個體間距公式

由式(1)可知,相對亮度與絕對亮度Ii、光吸收系數(shù)γ和兩螢火蟲之間的距離rij有關(guān)．然而在TSP問題中,每只螢火蟲代表一組經(jīng)過n個城市的隨機序列,所以,在這重新定義螢火蟲個體間的距離．假設(shè)螢火蟲i的解為Path(i)＝{pi1,pi2,pi3,…,pin},螢火蟲j的解為Path(j)＝{pj1,pj2,pj3,…,pjn},rij則:

相對亮度公式和吸引力公式不變,仍沿用式(1)、式(2)．

2．4 位置更新公式

根據(jù)TSP問題解的特點,每次位置更新并不能像式(3)一樣,即不能采用一只螢火蟲向另一只螢火蟲所在位置逐步移動這種方式,而是在滿足移動時直接移動到另一只螢火蟲的位置,即把另一只螢火蟲的解直接賦值給當(dāng)前的螢火蟲．表示為:

3 改進的螢火蟲算法求解TSP問題

為了提高螢火蟲算法求解TSP問題時的收斂速度,使其找到全局最優(yōu)解,對螢火蟲算法進行改進,即引入遺傳算法中的交叉、變異、逆轉(zhuǎn)操作．

3．1 引入交叉、變異、進化逆轉(zhuǎn)操作

螢火蟲算法容易陷入局部最優(yōu)的情況,針對這一缺點,將遺傳算法中的交叉、變異、進化逆轉(zhuǎn)操作引入到螢火蟲算法,這樣增加了TSP問題解的可能性,可以避免陷入局部最優(yōu)．

(1)交叉操作．交叉操作即將每代的解,兩個分為一組,設(shè)置交叉概率Pc,交叉區(qū)間為[r1,r2],區(qū)間內(nèi)數(shù)據(jù)進行交換,如有重復(fù)數(shù)據(jù),則進行部分映射消除沖突[1]．假設(shè)城市數(shù)為12,r1＝5,r2＝8,{6,2,7,9,3, 10,1,5,11,4,8,12},{7,1,8,11,2,12,4,5,10,3,6,9},交叉后,{6,1,7,9,2,12,4,5,11,3,8,10},{7,2, 8,11,3,10,1,5,4,12,6,9}．

(2)變異操作．變異操作即任意選取兩點,將其對換位置[1]．假設(shè)城市數(shù)為12,r1＝5,r2＝8,變異概率為Pm,如下一組數(shù)據(jù){6,2,7,9,3,10,1,5,11,4,8,12},變異后,{6,2,7,9,5,10,1,3,11,4,8,12}．

(3)進化逆轉(zhuǎn)操作．進化逆轉(zhuǎn)操作與變異操作都是任意選取兩點,將其對換位置,區(qū)別在于進化逆轉(zhuǎn)操作結(jié)束后數(shù)據(jù)優(yōu)于原來的可保留,否則數(shù)據(jù)不變[1]．

交叉概率Pc,變異概率Pm,在這里應(yīng)取很小的值,因為問題的尋優(yōu)主要依靠螢火蟲算法的思想,而加入交叉、變異操作主要為了增加解的隨機性,使得TSP問題的解具有多樣性,這樣可以避免陷入局部最優(yōu),使算法找到全局最優(yōu)解的概率增加．

3．2 算法步驟

用改進的螢火蟲算法求解TSP問題,可按以下步驟執(zhí)行:

(1)設(shè)定算法參數(shù),包括最大迭代次數(shù)G、螢火蟲數(shù)量、光吸收系數(shù)γ等;

(2)初始化螢火蟲位置,即隨機產(chǎn)生N組解;

(3)初始化螢火蟲亮度,螢火蟲絕對亮度由目標函數(shù)直接決定,按照式(5)計算;

(4)判斷是否滿足程序終止條件,即是否進行了G次迭代,若滿足條件,程序終止,執(zhí)行第8步,否則繼續(xù)執(zhí)行下一步;

(5)更新螢火蟲位置,首先按式(6)計算螢火蟲個體間距,由于螢火蟲會向絕對亮度比本身大且個體間距較小的螢火蟲移動,通過輪盤賭法進行位置選擇,并按式(7)進行位置更新;

(6)更新螢火蟲亮度,計算位置更新后的螢火蟲亮度;

(7)當(dāng)螢火蟲算法迭代到一定次數(shù)后,可能已達到最優(yōu)化,如果有最優(yōu)解在G/5次運算后結(jié)果仍保持不變,則提前結(jié)束算法,執(zhí)行第8步,否則回到第4步;

(8)輸出遍歷城市順序,繪出最優(yōu)解路線圖．

4 仿真實驗

仿真實驗通過對標準螢火蟲算法與改進的螢火蟲算法的比較,驗證改進算法的可行性．假設(shè)TSP問題的城市數(shù)為14,螢火蟲個數(shù)為80,最大迭代次數(shù)為200,光吸收系數(shù)γ取1．5,在Matlab中進行仿真實驗,每種算法分別進行50次,來驗證實驗的普遍性,仿真結(jié)果如表1所示．由表1可知,將標準螢火蟲算法與改進螢火蟲算法的50次運行結(jié)果的最優(yōu)值和平均值進行比較發(fā)現(xiàn),雖然標準螢火蟲算法與改進螢火蟲算法所得最優(yōu)值相同,但標準螢火蟲算法的最優(yōu)值出現(xiàn)次數(shù)較少,且有最差值的出現(xiàn),平均值的結(jié)果較大;而改進螢火蟲算法50次運行結(jié)果都為最優(yōu)值,且平均值更優(yōu)．

表1 標準螢火蟲算法與改進螢火蟲算法結(jié)果比較

在參數(shù)相同的情況下,標準螢火蟲算法下得到的仿真結(jié)果如圖1、圖2所示．由圖1、圖2可知,在同樣條件下,標準螢火蟲算法得到的最優(yōu)路線結(jié)果并不穩(wěn)定,每次運行的結(jié)果都可能不同,也表明了標準螢火蟲算法更易陷入局部最優(yōu)解,而錯過最優(yōu)路線．改進螢火蟲算法下得到的路線仿真結(jié)果如圖3所示．由圖3可知,結(jié)果相對較為穩(wěn)定．兩種算法的優(yōu)化過程對比如圖4所示．由圖4可以看出,改進螢火蟲算法最優(yōu)值結(jié)果更好,且時間更少．

圖1 標準螢火蟲算法路線

圖2 標準螢火蟲算法路線

圖3 改進螢火蟲算法路線

5 結(jié)論

提出了一種改進的螢火蟲算法在TSP求解上的具體實現(xiàn)．該算法針對TSP問題,在標準螢火蟲算法基礎(chǔ)上,對螢火蟲個體距離、位置更新公式進行了重新定義,并加入了交叉、變異、逆轉(zhuǎn)操作,避免尋優(yōu)過程出現(xiàn)早熟現(xiàn)象,提高了算法效率．通過仿真實驗表明,改進后的螢火蟲算法在更少代數(shù)內(nèi)能夠找到最優(yōu)解,不僅大大提高了效率,也使優(yōu)化結(jié)果更好、更穩(wěn)定,證明了改進螢火蟲算法的可行性與有效性．

參考文獻:

[1] 史峰,王輝,郁磊,等．MATLAB智能算法30個案例分析[M]．北京:北京航空航天大學(xué)出版社,2011．

[2] 周永權(quán),黃正新．求解TSP的人工螢火蟲群優(yōu)化算法[J]．控制與決策,2012,27(12):1 816-1 821．

[3] 王宇平,李英華．求解TSP的量子遺傳算法[J]．計算機學(xué)報,2007,30(5):748-755．

[4] 范會聯(lián),李獻禮．基于近鄰關(guān)系求解TSP的離散PSO算法[J]．計算機應(yīng)用研究,2011,28(2):511-513,544．

[5] 吳華峰,陳信強,毛奇凰,等．基于自然選擇策略的蟻群算法求解TSP問題[J]．通信學(xué)報,2013,34(4):165-170．

[6] K N Krishnand,D Ghose．Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]．Multiagent and Grid System,2006,2(3):209-222．

[7] R Dutta,R Ganguli,V Mani．Exploring isospectral spring-mass systems with firefly algorithm[J]．Proceedings of the Royal Society of London A,2011(467):1-20．

[8] T Mauder,C Sandera,J Stetina,et al．Optimization of the quality of continuously cast steel slabs using the firefly algorithm[J]．Materials and Technology,2011,45(4):347-350．

[9] 董靜．螢火蟲算法研究及其在水下潛器路徑規(guī)劃中的應(yīng)用[D]．哈爾濱:哈爾濱工程大學(xué),2013．

[10]于宏濤,高立群,韓希昌．求解旅行商問題的離散人工螢火蟲算法[J]．華南理工大學(xué)學(xué)報:自然科學(xué)版,2015,43(1): 126-131,139．

Travel salesman problem based on improved firefly algorithm

HU Nan,XU Xiao-guang?
(College of Electrical Engineering,Anhui Polytechnic University,Wuhu 241000,China)

Abstract:According to the characteristics of travel salesman problem,an improved firefly algorithm is proposed．Firstly,a new distance formula are location update formula is redefined．Secondly,in order to increase the diversity of firefly swarms,avoid quick convergence to local optimal solution and save time, genetic algorithm is introduced．Finally,simulation experiments show that the improved algorithm can find the global optimal solution with less evolving time,and the proposed method is feasible and effective．

Key words:travel salesman problem;improved firefly algorithm;genetic algorithm

中圖分類號:TP391．9

文獻標識碼:A

收稿日期:2015-10-15

基金項目:安徽省高等學(xué)校省級自然科學(xué)研究項目(KJ2014A024)

作者簡介:胡 楠(1991-),女,安徽淮南人,碩士研究生．

通訊作者:徐曉光(1972-),男,安徽明光人,副教授,碩導(dǎo)．