一種用于求解TSP問題的隨機(jī)最佳插入煙花算法 *

吳俊斌，吳 晟，吳興蛟

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明650500；2.華東師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200062)

1 引言

旅行商問題TSP(Traveling Salesman Problem)自1959年提出已經(jīng)過去了半個(gè)多世紀(jì)， TSP問題是一個(gè)NP難問題[1-3]，目前為止都沒有一種高效且精準(zhǔn)地求解方法。高效精準(zhǔn)地求解TSP問題在車輛路徑規(guī)劃、O2O物流配送等很多領(lǐng)域都有著非常重要的意義。TSP問題的目標(biāo)是在一系列點(diǎn)集中尋找一條最短回路，并要求每個(gè)點(diǎn)只訪問一次，目前主要的求解方法為啟發(fā)式智能算法，如遺傳算法、蟻群算法和蝙蝠算法等。近幾年，很多學(xué)者致力于研究現(xiàn)代啟發(fā)式智能算法及其優(yōu)化算法，如張瑾等人[4]提出的離散蝙蝠算法以及袁汪凰等人[5]提出的自適應(yīng)模擬退火蟻群算法。

煙花算法FWA(FireWorks Algorithm)[6]2010年由Tan等人提出，是一種模擬煙花爆炸產(chǎn)生火花以照亮夜空的現(xiàn)象探索鄰域的群體智能優(yōu)化算法。在求解復(fù)雜的優(yōu)化問題時(shí)，該算法不僅具有較強(qiáng)的局部搜索能力，同時(shí)還保留了良好的全局搜索能力。近年來煙花算法受到廣大學(xué)者的關(guān)注，并被成功運(yùn)用到許多領(lǐng)域，如Web服務(wù)組合優(yōu)化[7]、智能診斷齒輪箱故障[8]、多維背包[9]、多無人機(jī)任務(wù)分配[10]和作業(yè)車間調(diào)度[11,12]等，各項(xiàng)研究表明煙花算法具有較好的收斂性和穩(wěn)定性[13]。

本文針對(duì)TSP問題的特點(diǎn)，考慮煙花算法的尋優(yōu)機(jī)制，設(shè)計(jì)了一種基于隨機(jī)最佳插入的煙花算法RBIFWA(Randomized Best Insertion FireWorks Algorithm)。該算法改進(jìn)了傳統(tǒng)煙花算法爆炸資源的分配方式，創(chuàng)新性地提出了2個(gè)全新算子：拋棄節(jié)點(diǎn)重新插入的爆炸算子和拋棄路徑重新插入的變異算子。然后通過精英與輪盤賭相結(jié)合的選擇策略對(duì)煙花進(jìn)行選擇，能夠很好地求解TSP問題。算法基本思想如下：初始生成的煙花為TSP問題的一條完整路徑，煙花爆炸產(chǎn)生的火花為原有煙花在鄰域搜索得到的一條新的路徑，質(zhì)量較優(yōu)的煙花爆炸產(chǎn)生的火花數(shù)量較多，但爆炸半徑較小，即其局部搜索的能力較強(qiáng)；質(zhì)量較差的煙花爆炸半徑較大，但火花數(shù)量較少，即其可提高算法全局搜索能力。煙花質(zhì)量的優(yōu)良由適應(yīng)度值決定，根據(jù)適應(yīng)度分配煙花資源，有效平衡了算法全局和局部的搜索能力[14]。為驗(yàn)證算法的有效性，最后使用TSPLIB標(biāo)準(zhǔn)庫進(jìn)行測(cè)試，并與基本煙花算法、混沌煙花算法CFWA(Chaotic FireWorks Algorithm)[15]、離散蝙蝠算法DBA(Discrete Bat Algorithm)[4]和自適應(yīng)模擬退火蟻群算法SA-MMAS(Simulated Annealing Max-Min Ant System)[5]進(jìn)行比較。

2 TSP問題模型

TSP問題可描述為：由n個(gè)點(diǎn)構(gòu)成的點(diǎn)集V={v1,v2,…,vn}表示n個(gè)城市的集合，一個(gè)商品推銷員需到這n個(gè)城市推銷商品，要求從某一城市出發(fā)，剩余的n-1個(gè)城市必須且僅能經(jīng)過1次，最后回到出發(fā)城市，若已知每對(duì)城市之間的距離，求如何安排各城市的訪問次序才能獲得最短的路徑。

假設(shè)d(vi,vj)表示城市vi到城市vj的距離,i,j∈{1,…,n}，該商品推銷員訪問城市的次序?yàn)閜={v[1],v[2],…,v[n],v[1]}，其中v[i]∈V表示訪問的第i個(gè)城市，則這條路徑的長(zhǎng)度為：

(1)

若D(p)的值最小，則由p構(gòu)成的路徑為該TSP問題的最優(yōu)解。

3 改進(jìn)型隨機(jī)最佳插入算法

隨機(jī)最佳插入RBI(Randomized Best Insertion)是一種隨機(jī)性啟發(fā)式算法，該算法實(shí)現(xiàn)簡(jiǎn)單，并能有效平衡精度和計(jì)算性能，常用于快速構(gòu)建一個(gè)次優(yōu)解。然而實(shí)驗(yàn)發(fā)現(xiàn)，RBI算法在求解TSP問題時(shí)很容易將距離較遠(yuǎn)的點(diǎn)優(yōu)先插入，造成交叉路徑，使解的質(zhì)量降低?？紤]到最優(yōu)TSP路徑的相鄰節(jié)點(diǎn)均是距離較近的幾個(gè)節(jié)點(diǎn)[16]，本文對(duì)RBI算法進(jìn)行了改進(jìn)，描述如下：

假設(shè)p(t)是算法在第t次迭代時(shí)的部分TSP封閉路徑：

p(t)={v[1],v[2],…,v[t],v[1]}

(2)

W(t)=V-p(t)為第t次迭代時(shí)尚未訪問的節(jié)點(diǎn)的集合，其中V={v1,v2,…,vn}為TSP所有節(jié)點(diǎn)的集合，|W(t)|=n-t為第t次迭代尚未訪問的節(jié)點(diǎn)數(shù)量。

定義vc為p(t)的幾何中心，wi(wi∈W(t))與vc的距離可以表示為式(3)所示：

dc(wi)=d(wi,vc)

(3)

定義wi在p(t)中的最佳位置滿足式(4)：

(4)

其中,wi∈W(t),Δd[j](wi)滿足式(5)，表示將wi插入到p(t)第j個(gè)位置所增加的長(zhǎng)度。

Δd[j](wi)=d(v[j-1],wi)+

d(wi,v[j])-d(v[j-1],v[j])

(5)

通過改進(jìn)RBI算法構(gòu)建TSP路徑的算法如算法1所示。

算法1改進(jìn)RBI算法

輸入：V={v1,v2,…,vn}。//TSP所有節(jié)點(diǎn)的集合

輸出：p={v[1],v[2],…,v[n],v[1]}。//一條完整路徑

t←1;

隨機(jī)選擇v[1]∈V;

初始化路徑p(t)={v[1],v[1]};

初始化W(t)←V-p(t);

While|W(t)|≠0Do

計(jì)算p(t)的幾何中心vc;

通過式(3)計(jì)算W(t)中各點(diǎn)wi距幾何中心vc的距離dc(wi);

從W(t)中找出dc(wi)最小的r個(gè)點(diǎn)，構(gòu)成Wr(t)={w[1],w[2],…,w[r]};

隨機(jī)選擇w∈Wr(t);

通過式(4)找到w的最佳插入位置;

將w插入到p(t)的最佳位置;

將w從W(t)中刪除;

t←t-1;

EndWhile

其中,r=min(n-r,R)，R為隨機(jī)因子，R越小越接近貪心策略，使每次插入的節(jié)點(diǎn)都是p(t)附近的幾個(gè)節(jié)點(diǎn)，R越大越能提高解的多樣性。通過與原RBI算法進(jìn)行對(duì)比發(fā)現(xiàn)，當(dāng)R選擇合適數(shù)值時(shí)可以抑制交叉路徑的產(chǎn)生，提高解的質(zhì)量，同時(shí)又能保證解的多樣性。

4 改進(jìn)型煙花算法

煙花算法主要由初始煙花、爆炸算子、變異算子和選擇策略4部分組成[17]。本文針對(duì)TSP問題的離散特性，改進(jìn)了爆炸資源分配的方式，創(chuàng)新性地提出了拋棄節(jié)點(diǎn)重新插入的爆炸算子和拋棄路徑重新插入的變異算子，然后通過精英與輪盤賭相結(jié)合的煙花選擇策略，能夠很好地求解TSP問題。其中，煙花和火花對(duì)應(yīng)TSP中的一條完整路徑，初始煙花由改進(jìn)RBI算法隨機(jī)產(chǎn)生，共計(jì)得到M個(gè)初始煙花；爆炸算子和變異算子用于搜索，并得到新的火花；選擇策略將對(duì)煙花進(jìn)行篩選，以進(jìn)行下一次迭代。改進(jìn)的煙花算法流程如圖1所示。

Figure 1 Flowchart of improved fireworks algorithm圖1 改進(jìn)的煙花算法流程示意圖

4.1 適應(yīng)度評(píng)估函數(shù)

適應(yīng)度評(píng)估函數(shù)用于評(píng)估解的優(yōu)劣程度，適應(yīng)度值[18]越小，則表示適應(yīng)度較優(yōu)，解的質(zhì)量較高；適應(yīng)度值越大，則表示適應(yīng)度較差，解的質(zhì)量較低。

設(shè)一條完整的TSP路徑為一個(gè)有效解，路徑訪問節(jié)點(diǎn)的順序?yàn)閜i={v[1],v[2],…,v[n],v[1]}，則定義這條路徑的適應(yīng)度值如式(6)所示：

f(pi)=D(pi)=

(6)

即TSP路徑的適應(yīng)度值為這條路徑的總長(zhǎng)度，由此可知，最短的TSP路徑有最優(yōu)的適應(yīng)度值。

4.2 爆炸資源分配

煙花算法的基本思想如下：煙花為解空間中的部分可行解，煙花爆炸產(chǎn)生的火花會(huì)照亮周圍的夜空，其中周圍夜空表示鄰域解構(gòu)成的空間，其大小由爆炸半徑來度量，爆炸產(chǎn)生的火花為煙花在鄰域空間中搜索的新解。圖2所示為實(shí)際煙花爆炸與煙花算法的類比。

Figure 2 Analogy of the fireworks explosion and fireworks algorithm圖2 實(shí)際煙花爆炸與煙花算法的類比圖

煙花爆炸的資源分配遵循一個(gè)共同的原則，即適應(yīng)度值較優(yōu)的煙花能夠產(chǎn)生更多的火花，爆炸的半徑較小，適應(yīng)度值較差的煙花能夠產(chǎn)生較少的火花，但爆炸半徑更大[19]。根據(jù)這一原則，在爆炸前需要根據(jù)適應(yīng)度計(jì)算各煙花的爆炸半徑和爆炸產(chǎn)生火花的數(shù)量，選擇m個(gè)煙花作為煙花種群參與爆炸，計(jì)算方法如式(7)和式(8)所示：

(7)

(8)

本文針對(duì)TSP的特征，經(jīng)過多次實(shí)驗(yàn)，設(shè)計(jì)了求解A和S的方法，如式(9)和式(10)所示：

(9)

S=m·k

(10)

其中,m為參與爆炸的煙花數(shù)量，n為TSP的節(jié)點(diǎn)數(shù)，n/l和k為煙花的平均爆炸半徑和平均爆炸數(shù)量。在這個(gè)問題中，l∈[2,3]，k∈[10,20]。當(dāng)n較小時(shí)，適當(dāng)增大l并減小k可以提高算法局部搜索能力，使得算法更快收斂；當(dāng)n較大時(shí)，適當(dāng)減小l并增大k可以提高算法全局搜索能力，有利于跳出局部最優(yōu)解。

由于TSP問題離散的性質(zhì)，一般期望處理結(jié)果是一個(gè)整數(shù)，然而式(7)和式(8)得到的是一個(gè)實(shí)數(shù)。同時(shí)為避免求得的爆炸半徑或產(chǎn)生的火花數(shù)量過大或過小，可以通過式(11)和式(12)將得到的實(shí)數(shù)轉(zhuǎn)換為整數(shù)，并將其控制在一定范圍內(nèi)。

(11)

(12)

其中,Amax,Amin,Smax,Smin皆為預(yù)設(shè)的整數(shù)常數(shù)，代表爆炸半徑的最大值和最小值及爆炸火花數(shù)量的最大值和最小值。

4.3 爆炸算子

當(dāng)煙花獲得爆炸資源A和S后，將在周圍發(fā)生爆炸，產(chǎn)生一組新的火花，用于探索鄰域解。為了更好地探索鄰域解，本文設(shè)計(jì)了一種新穎的爆炸操作算子。

提示:(1)根據(jù)氧化還原反應(yīng)的規(guī)律,次氯酸鈣與濃鹽酸反應(yīng)生成氯化鈣、氯氣與水,反應(yīng)的化學(xué)方程式為Ca(ClO)2+4HCl(濃)==CaCl2+2Cl2↑+2H2O。

當(dāng)產(chǎn)生的火花優(yōu)于原煙花時(shí)，則接收該解，并將該火花加入煙花種群中，以供下次迭代時(shí)選擇；當(dāng)產(chǎn)生的火花與原煙花相同時(shí)，則拋棄該火花；當(dāng)產(chǎn)生的火花劣于原煙花時(shí)，則以一定概率接收較差的解，接收概率如式(13)所示：

(13)

其中,fin為原煙花的適應(yīng)度值，fout為產(chǎn)生的火花的適應(yīng)度值，θ為控制參數(shù)，取[1,2]較為合適。由此可知，適應(yīng)度越接近原煙花的火花，被接收的概率越大。為描述方便，本文將被接收的火花稱為有效火花，被拋棄的火花稱為無效火花。有效煙花構(gòu)成的集合稱為煙花種群。

4.4 變異算子

變異算子與爆炸算子不同，能夠增加煙花種群的多樣性，一定程度上能夠跳出局部最優(yōu)解，探索更優(yōu)解。針對(duì)TSP問題，本文設(shè)計(jì)了一種合適的變異操作算子。

(14)

其中,xmin為允許變異刪除的最小連續(xù)節(jié)點(diǎn)數(shù)，xmax為允許變異刪除的最大連續(xù)節(jié)點(diǎn)數(shù)，C為迭代總次數(shù)，c為當(dāng)前迭代的次數(shù)。

4.5 選擇策略

隨著煙花種群數(shù)量的增加，如何選擇煙花參與下一次爆炸顯得至關(guān)重要。為此本文使用精英選擇與輪盤賭相結(jié)合的選擇策略。假設(shè)要從種群中挑選m個(gè)煙花參與下一次爆炸，那么種群中的最優(yōu)個(gè)體將被確定性地選擇，剩余m-1個(gè)煙花則通過輪盤賭的方式從種群中進(jìn)行選擇。對(duì)于煙花種群中的每一個(gè)煙花pi，其被選擇的概率如式(15)所示：

(15)

其中,M為煙花種群的數(shù)量。通過概率做出的選擇，適應(yīng)度值更優(yōu)的煙花有更大的機(jī)會(huì)參與下一次迭代。

4.6 算法偽代碼

使用隨機(jī)最佳插入的煙花算法求解TSP問題的流程如算法2所示：

算法2基于改進(jìn)RBI的煙花算法

輸入：V={v1,v2,…,vn}。//TSP所有節(jié)點(diǎn)的集合

輸出：p={v[1],v[2],…,v[n],v[1]}。//一條完整路徑

(1)初始化。

初始化最大迭代次數(shù)C，煙花種群數(shù)M，爆炸煙花數(shù)m，爆炸參數(shù)Amax、Amin、Smax、Smin，變異參數(shù)xmin和xmax，常量l和k，控制參數(shù)α和θ，迭代次數(shù)c←1，Explosive集置空，Abandoned集置空。

(2)初始煙花。

改進(jìn)RBI生成M個(gè)不同的初始煙花，并將其加入煙花種群集合Fireworks中。

(3)開始迭代。

Whilec≤CDo

(4)選擇策略。

通過式(6)計(jì)算Fireworks中煙花的適應(yīng)度值；

從Fireworks中選擇最優(yōu)煙花加入Explosive;

通過式(15)計(jì)算Fireworks集中剩余M-1個(gè)候選煙花的選擇概率;

輪盤賭選擇m-1個(gè)煙花加入Explosive集中;

(5)資源分配。

ForpinExplosiveDo

(6)爆炸算子。

pin←p;

用改進(jìn)RBI算法將刪除點(diǎn)重新插入pin中，得到新路徑pout;

通過式(6)計(jì)算pout的適應(yīng)度值;

若fout>fin，則將pout加入Fireworks中;

若fout

EndFor

(7)變異算子。

統(tǒng)計(jì)煙花p產(chǎn)生的有效火花數(shù)s；

pin←p;

通過式(14)計(jì)算x;

隨機(jī)刪除pin中的一段包含x個(gè)節(jié)點(diǎn)的路徑;

用改進(jìn)RBI算法將刪除點(diǎn)重新插入pin中，得到新路徑pout;

將pout加入Fireworks中;

將煙花p從Fireworks集移至Abandoned集中;

EndIf

EndFor

(8)更新變量。

c←c+1，Explosive集置空;

更新M為Fireworks集的煙花個(gè)數(shù);

EndWhile

(9)返回結(jié)果。

返回Fireworks和Abandoned中適應(yīng)度最優(yōu)的解

(10)結(jié)束。

由于算法總迭代次數(shù)是C，每次迭代產(chǎn)生的火花數(shù)為S=m·k，每個(gè)火花平均探索n/l的城市規(guī)模，最多探索n的城市規(guī)模，因此算法的時(shí)間復(fù)雜度為O(kmnC)。

5 實(shí)驗(yàn)仿真與結(jié)果分析

為檢測(cè)本文算法的性能，從TSPLIB數(shù)據(jù)集中選取了Oliver30、Eil51等6個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，并使用本文算法RBIFWA與基本煙花算法FWA[6]、混沌煙花算法CFWA[15]、離散蝙蝠算法DBA[4]、自適應(yīng)模擬退火蟻群算法SA-MMAS[5]進(jìn)行實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)環(huán)境為Python，CPU 3.2 GHz，內(nèi)存8 GB，Windows 10 64位操作系統(tǒng)。本文算法RBIFWA的參數(shù)取值如下：總迭代次數(shù)C=1000，隨機(jī)因子r=10，初始煙花種群數(shù)M=10，爆炸煙花數(shù)m=5，爆炸半徑的最大值A(chǔ)max=0.8n(n為城市的規(guī)模)和最小值A(chǔ)min=3，爆炸火花數(shù)量的最大值Smax=0.8n和最小值Smin=3，允許變異的最大節(jié)點(diǎn)數(shù)xmax=0.6n和最小節(jié)點(diǎn)數(shù)xmin=8，常量l=2，平均爆炸火花數(shù)量k=5，控制參數(shù)α=0.25，θ=2。此時(shí)算法每次迭代都產(chǎn)生mk=25個(gè)左右的煙花種群數(shù)量。其余算法的參數(shù)設(shè)置均參考相應(yīng)論文實(shí)驗(yàn)，時(shí)間復(fù)雜度及主要參數(shù)設(shè)置如表1所示。

Table 1 Comparison of algorithm time complexity and main parameters

其中，C為最大的迭代次數(shù)，M為每次迭代參與的種群數(shù)量，n為城市的規(guī)模。由于算法的時(shí)間復(fù)雜度相同，城市規(guī)模n大于25時(shí)，RBIFWA收斂到最優(yōu)解所用的迭代次數(shù)小于其他算法的，即可表明本文算法優(yōu)秀的求解能力。由于不同算法每次迭代的運(yùn)算量不同，因此結(jié)合迭代次數(shù)及目標(biāo)函數(shù)評(píng)估次數(shù)(FEs)進(jìn)行比較，共計(jì)進(jìn)行30次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。

從表2可以看出，RBIFWA 的求解精度優(yōu)于其他算法的。針對(duì)這6個(gè)數(shù)據(jù)集，DBA的平均誤差為2.87%，SA-MMAS的為0.44%，F(xiàn)WA的為5.34%，CFWA的為0.51%，RBIFWA的為0.16%。從平均迭代次數(shù)和平均目標(biāo)函數(shù)評(píng)估次數(shù)上來看，RBIFWA具有明顯的優(yōu)勢(shì)，可見RBIFWA用更少的目標(biāo)函數(shù)評(píng)估次數(shù)和更少的種群數(shù)量，便可以得到相對(duì)更優(yōu)的結(jié)果。與FWA相比，改進(jìn)的隨機(jī)最佳插入算法能夠構(gòu)造精度更高的解，極大減少了搜索時(shí)的迭代次數(shù)和種群數(shù)量，使煙花算法擁有更強(qiáng)的收斂能力。與DBA和SA-MMAS相比，RBIFWA表現(xiàn)出更出色的求解能力，這主要是因?yàn)檫m應(yīng)度更優(yōu)的煙花能夠產(chǎn)生更多的火花，使其能夠在鄰域中多次探索更優(yōu)解，優(yōu)秀的局部搜索能力使算法更快收斂，在減少迭代次數(shù)的同時(shí)，也提高了算法的精度。在選擇策略上，適應(yīng)度更優(yōu)的煙花更有機(jī)會(huì)加入下一次爆炸，也進(jìn)一步提高了算法局部搜索能力。因此整體來說，RBIFWA擁有更加優(yōu)秀的性能，能夠更快地收斂，且求得的最優(yōu)解更加精確。

Table 2 Results comparison of five algorithms

但是，當(dāng)問題規(guī)模進(jìn)一步擴(kuò)大時(shí)，RBIFWA使用較小的種群數(shù)量極易陷入局部最優(yōu)解，為此適當(dāng)增大種群數(shù)量可以增加種群多樣性，提高算法全局搜索能力。圖3對(duì)比了煙花種群數(shù)量分別設(shè)為L(zhǎng)1:25(m=5,k=5),L2:50(m=5,k=10),L3:50(m=10,k=5)時(shí)求解TSPLIB數(shù)據(jù)集中城市規(guī)模為280的子集a280數(shù)據(jù)集的進(jìn)化趨勢(shì)的結(jié)果，由于每次迭代的種群數(shù)量不同，因此實(shí)驗(yàn)以最大目標(biāo)函數(shù)評(píng)估次數(shù)為20 000次作為迭代終止的條件，并各進(jìn)行了10次實(shí)驗(yàn)，得到如圖3所示的不同種群數(shù)量的進(jìn)化趨勢(shì)圖。其中圖3a和圖3c所示分別為最優(yōu)適應(yīng)度值和種群多樣性的進(jìn)化趨勢(shì)，圖3b和圖3d所示分別為圖3a和圖3c前700次的局部放大圖。

Figure 3 Evolutionary trends of different populations圖3 不同種群數(shù)量的進(jìn)化趨勢(shì)圖

(1)圖3a中，煙花種群數(shù)量為L(zhǎng)1時(shí)RBIFWA算法最終收斂至2 712.22，而煙花種群數(shù)量為L(zhǎng)2和L3時(shí)RBIFWA算法分別收斂至2 689.45和2 651.47，可見隨著種群數(shù)量的增加，算法的尋優(yōu)能力也得到加強(qiáng)，使解的精度得到提升(圖3b和圖3c解釋了其原因)。

(2)圖3b中，煙花種群數(shù)量為L(zhǎng)1時(shí)RBIFWA算法收斂都較煙花種群數(shù)量為L(zhǎng)2和L3時(shí)快，但尋優(yōu)能力較弱，這說明當(dāng)種群數(shù)量較小時(shí)，算法收斂速度較快，極易陷入局部最優(yōu)解。

(3)圖3c中，煙花種群數(shù)量為L(zhǎng)2和L3時(shí)RBIFWA算法種群多樣性較煙花種群數(shù)量為L(zhǎng)1時(shí)有很大的提升，這說明隨著種群數(shù)量的增加，更容易探索到新解，結(jié)合圖3a可見，種群多樣性的提升使算法更容易跳出局部最優(yōu)解，因此有更強(qiáng)的全局搜索能力。

(4)對(duì)比種群數(shù)量相同的L2和L3發(fā)現(xiàn)，煙花種群數(shù)量為L(zhǎng)3時(shí)算法較煙花種群數(shù)量為L(zhǎng)2時(shí)有更高的種群多樣性，但煙花種群數(shù)量為L(zhǎng)2比煙花種群數(shù)量為L(zhǎng)3時(shí)的收斂速度更快，這主要是因?yàn)殡S著m的增大，更多的煙花參與探索，提高了煙花爆炸產(chǎn)生有效火花的能力，即決定了全局搜索能力；而平均爆炸數(shù)量k的增加，使煙花能夠在鄰域中進(jìn)行多次探索，更有機(jī)會(huì)得到更優(yōu)解，即決定了局部搜索能力。圖3d中，煙花種群數(shù)量為L(zhǎng)3時(shí)與煙花種群數(shù)量為L(zhǎng)1時(shí)算法結(jié)果差距明顯，而煙花種群數(shù)量為L(zhǎng)2時(shí)的多樣性與煙花種群數(shù)量為L(zhǎng)1時(shí)相當(dāng)，也進(jìn)一步說明了m對(duì)全局搜索能力的作用。

因此，對(duì)于問題規(guī)模較大的測(cè)試算例，適當(dāng)增加煙花種群的數(shù)量，可以提升解的精度。另外，當(dāng)種群數(shù)量相同時(shí)，增大m減小k可以提高算法全局搜索能力；增大k減小m可以提高算法局部搜索能力。

6 結(jié)束語

本文考慮了TSP離散的特征以及煙花算法的尋優(yōu)機(jī)制，設(shè)計(jì)了一種隨機(jī)最佳插入煙花算法。該算法在減少迭代次數(shù)的同時(shí)也提高了求解精度。這是由于算法改進(jìn)了爆炸資源的分配方式和煙花選擇的策略，使適應(yīng)度更優(yōu)的煙花能夠在爆炸過程中產(chǎn)生更多的火花去探索鄰域最優(yōu)解，從而有效提升算法的收斂速度。通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，本文算法無論在時(shí)間性能上還是求解精度上都有著優(yōu)秀的表現(xiàn)。為了進(jìn)一步改進(jìn)以及拓展算法，未來將探索引入并行操作，并結(jié)合鄰域搜索等算法，進(jìn)一步提高算法性能和求解精度，以期解決更大規(guī)模的TSP問題。