吳俊斌,吳 晟,吳興蛟
(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南 昆明650500;2.華東師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,上海 200062)
旅行商問題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)庫(kù)進(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)行比較。
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)解。
隨機(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部分組成[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)的煙花算法流程示意圖
適應(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)度值。
煙花算法的基本思想如下:煙花為解空間中的部分可行解,煙花爆炸產(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ù)量的最大值和最小值。
當(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)成的集合稱為煙花種群。
變異算子與爆炸算子不同,能夠增加煙花種群的多樣性,一定程度上能夠跳出局部最優(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ù)。
隨著煙花種群數(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ì)參與下一次迭代。
使用隨機(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)。 為檢測(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可以提高算法局部搜索能力。 本文考慮了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問題。5 實(shí)驗(yàn)仿真與結(jié)果分析
6 結(jié)束語