朱宇 朱留存 羅俊琦 沙波

（1.揚州大學(xué)信息工程學(xué)院 江蘇省揚州市 225009 2.北部灣大學(xué)先端科學(xué)技術(shù)研究院 廣西壯族自治區(qū)欽州市 535000）

1 引言

路徑規(guī)劃[1]是指移動機器人或者移動主體在有障礙物的環(huán)境中尋找一條從初始地點到達目標地點的無碰撞路徑。自移動機器人在20世紀60年代問世開始，作為移動機器人關(guān)鍵性技術(shù)[2]之一的路徑規(guī)劃也隨之產(chǎn)生。

目前路徑規(guī)劃分為兩大種類，一種是全局路徑規(guī)劃[3]，又稱為靜態(tài)路徑規(guī)劃，另一種是局部路徑規(guī)劃，又稱為實時動態(tài)路徑規(guī)劃。局部路徑規(guī)劃注重的是移動機器人實時避障的性能，根據(jù)自身傳感器采集到的局部環(huán)境進行實時動態(tài)路徑規(guī)劃，有非常好的靈活性，但由于缺乏更多的環(huán)境信息，所得到的路徑一般是局部最優(yōu)而非全局最優(yōu)。全局路徑規(guī)劃則需要知道全局環(huán)境信息，通過建立環(huán)境地圖模型，然后在全局地圖上使用尋優(yōu)搜索算法獲取全局最優(yōu)或者較優(yōu)路徑。局部路徑規(guī)劃的代表人工勢場法[4]，該算法結(jié)構(gòu)簡單，方便實時控制，能節(jié)省大量運算時間，但在狹窄通道中會擺動，且目標點存在障礙物時，無法到達目標點。全局路徑規(guī)劃代表有粒子群算法(Particle swarm optimization)[4]，調(diào)整參數(shù)少，易于實現(xiàn)，收斂速度快，但對于離散優(yōu)化問題，又容易陷入局部最優(yōu)。蟻群算法(Ant colony optimization)[5]。模仿蟻群覓食的行為搜索路徑，具有較強的魯棒性和搜索較好解的能力，但容易陷入局部最優(yōu)解，并且收斂次數(shù)較慢。遺傳算法[6]，能充分發(fā)揮自身優(yōu)勢與其他算法融合，擁有優(yōu)秀的自組織性和自學(xué)習(xí)性，實現(xiàn)簡單，受外界影響小，但運行速度較慢，搜索效率較低，同樣易于陷入最優(yōu)解。煙花算法（Fireworks Algorithm）[7]，收斂速度快，易于實現(xiàn)，且具有爆發(fā)性、多樣性和隨機性等等，但運算量大導(dǎo)致運行時間稍長。

其中煙花算法由譚營教授等人于2010年發(fā)表，是根據(jù)煙花在夜空中爆炸的現(xiàn)象而提出的一種新型群智能優(yōu)化算法，但由于出生較晚，對于求解不同類型的優(yōu)化問題的能力還并不成熟，因此業(yè)界內(nèi)對煙花算法的研究逐步深入和鋪開，針對原始煙花算法的不足，進行了大量的改進，例如張穎[10]通過結(jié)合煙花算法和例子群算法優(yōu)化無線網(wǎng)絡(luò)拓撲結(jié)構(gòu)，馬創(chuàng)濤[11]運用煙花算法改進BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型。而本文則是針對煙花算法在路徑規(guī)劃上的應(yīng)用做出優(yōu)化改進。

2 煙花算法原理

煙花算法[10]模擬煙花在夜空中爆炸的現(xiàn)象，將爆炸的一系列流程轉(zhuǎn)換成數(shù)學(xué)模型。首先開始爆炸，然后依次利用爆炸算子、變異算子探索空間，再利用映射規(guī)則將超出范圍的火花拉入范圍內(nèi)，最后應(yīng)用選擇策略選出下一代爆炸的煙花，直到達到終止條件。

2.1 爆炸強度

煙花種群中的每個煙花都會產(chǎn)生相應(yīng)的爆炸火花種群，適應(yīng)度值越好的煙花爆炸強度越大，爆炸火花的數(shù)量就越多，相反，爆炸強度越小，爆炸火花的數(shù)量就越少[11]，爆炸強度公式如下所示。

式中Si為第i 個煙花產(chǎn)生火花的數(shù)目，m 為限制火花生成的數(shù)目，Ymax為當前適應(yīng)度最大的值，f(xi)為第i 個個體產(chǎn)生的適應(yīng)度值，ε 是一個極小的常數(shù)，其目的是為了避免公式分母出現(xiàn)0 的情況，N 是指煙花的種群數(shù)目。

為了限制煙花產(chǎn)生火花的數(shù)目，防止煙花啞火或者產(chǎn)生預(yù)料之外爆炸，設(shè)置了火花數(shù)量的和爆炸范圍的限制公式分別如式（2）和式（3）所示。

式（2）是火花數(shù)量的限制公式，其中Si是第i 個煙花產(chǎn)生的火花數(shù)量，ceil 是四舍五入向上取整的函數(shù)，a 和b 都是給定的常數(shù)。

式（3）是煙花爆炸范圍的限制公式，其中AI為第i 個煙花的爆炸幅度，Ymin為當前最小的適應(yīng)度值，A 為爆炸最大范圍，其他參數(shù)同式（1）。

火花的移動規(guī)則是在確定的爆炸范圍內(nèi)，進行隨機的位移操作，具體如式(4)所示：

2.2 火花變異

隨機對煙花的若干個維度進行高斯變異，其公式如下：

其中N(1,1)是服從均值為1，方差為1 的高斯分布的隨機數(shù)。

2.3 映射規(guī)則

不論是在火花變異和產(chǎn)生火花的過程中，注定會碰到越過地圖范圍的火花，因此設(shè)立了映射規(guī)則，公式如下：

2.4 下一代種群選擇規(guī)則

通過歐式距離計算任意2 個煙花之間的距離，并將每一個煙花到其他煙花距離的總和計算出來，如式（7）所示：

其中d(xi,xi)是任意2 個煙花xi和xj之間的歐式距離R(xi)是煙花個體xi到其他煙花個體的距離總和，集合k 表示煙花，變異火花和爆炸火花的總和，是煙花初始種群的3 倍。

進行下一代種群選擇時運用的是輪盤賭法的方式，每個個體被選中的概率P(xi)如下：

公式（8）表示的意義是距離其他路徑越遠的個體越容易被選中成為下一代，這種選擇方式是煙花算法種群多樣性的主要原因[12]。

3 煙花算法優(yōu)化

3.1 連接規(guī)則優(yōu)化

最初的煙花算法在連接規(guī)則上和遺傳算法[13]相似，都是直連的，沒有節(jié)點選擇的環(huán)節(jié)。因此，本文為煙花算法添加節(jié)點連接環(huán)節(jié)。煙花通過一次爆炸產(chǎn)生n 個煙花，于是xi=(a1,a2,..aend)，其中xi為第i 次煙花爆炸，a1,a2…及aend為第i 次煙花爆炸的火花個數(shù)及位置，共計N 個火花。

公式（9）的目的是將火花an-1到an之間的節(jié)點通過輪盤賭法連接。其中allow 是火花an-1到an的所有可行節(jié)點，D（j,an）為節(jié)點j 到第n 個火花的歐式距離，nt是最短路徑獎勵機制[14]，它的目的是提高選擇最短節(jié)點的概率，因為火花本身就是隨機產(chǎn)生的，通過加強最短節(jié)點的連接概率能夠大幅度減少火花連接的隨機性，更加利于尋找最優(yōu)路徑。最終火花相互之間連接形成一條能夠到達終點的路徑，如圖1所示。

圖1：火花連接示意圖

3.2 煙花爆炸及變異優(yōu)化

原煙花算法中，從火花，變異火花以及爆炸火花中選擇三分之一進行下一輪迭代，沒有被選中的火花則被丟棄，極大的浪費了運算時間和存儲空間，這也是煙花算法運行時間較長的原因之一。針對這一缺點，將火花變異和煙花爆炸進行結(jié)合：

式中：allow 是第Si個煙花中未進行爆炸的火花的集合，其目是先進行火花爆炸，再對剩下火花選擇若干個進行高斯變異，然后統(tǒng)再一進行位移操作。

3.3 路徑冗余優(yōu)化

煙花算法作為自組織系統(tǒng)，通過爆炸產(chǎn)生若干個火花，然后通過節(jié)點選擇步驟使得每個火花之間相連，由于節(jié)點選擇方法為輪盤賭法，因此每個火花之間都不可避免存在著冗余節(jié)點問題，而冗余節(jié)點可分為3 種情況，分別如圖2，圖3 和圖4所示。

圖2：節(jié)點冗余示意圖

圖3：節(jié)點冗余示意圖

圖4：節(jié)點冗余示意圖

通過預(yù)連接的方式，在一個火花與另一個火花預(yù)連接之后，按照圖2、圖3、圖4 三種冗余情況執(zhí)行冗余優(yōu)化步驟，通過將冗余的節(jié)點加入禁忌表，重新進行一遍節(jié)點選擇，以達到預(yù)期的結(jié)果。但是在前期煙花算法處于探索階段，需要擴大搜索范圍，直到中后期煙花算法才處于收斂迭代狀態(tài)，為了避免算法過早的陷入收斂狀態(tài)，因此給予該冗余優(yōu)化步驟一個激活公式：

式（12）中，K 為總的迭代次數(shù)，m 是激活冗余優(yōu)化方法的迭代次數(shù)，迭代的總次數(shù)越大，激活該冗余優(yōu)化方法的時間就越晚。

3.4 種群選擇優(yōu)化

在所有的火花位移操作完成之后，開始進行下一代種群選擇，原煙花算法會大概率選擇距離其他個體較遠的火花作為下一代種群。此種種群選擇規(guī)則存在以下兩個問題：第一，路徑之間的距離難以用公式進行計算，第二，種群選擇需要先計算每條路徑與其他所有路徑的距離總和然后再比較，算法運行花銷較大?；谏鲜鰞煞N弊端，提出新的種群選擇公式如下所示：

式（13）中f(xi)是一條路徑的適應(yīng)度值，K 是爆炸火花與煙花的合計，其目的是大概率選擇適應(yīng)度值較大的個體作為下一代種群，繼續(xù)保持煙花種群的多樣性。

3.5 優(yōu)化算法的步驟

優(yōu)化煙花算法原理步驟圖如圖5所示。

圖5：優(yōu)化煙花算法原理步驟圖

步驟一：初始化煙花種群N 和各個參數(shù)；

步驟二：通過式（10）和式（11）連接煙花中的火花，并計算其適應(yīng)度；

步驟三：通過式（1）和式（3）進行每一個煙花的爆炸強度和爆炸幅度的計算；

步驟四：通過式（6）進行火花越界處理并通過式（10）和式（11）計算爆炸和變異的火花的適應(yīng)度值；

步驟五：通過式（9）將火花相互連接，形成完整的路徑并根據(jù)式（12）確定是否需要進行1 冗余優(yōu)化。

步驟六：通過式（13）選擇出0.6*N 個數(shù)目的火花以及0.4*N個本次最優(yōu)火花作為下一代種群

步驟七：不斷執(zhí)行步驟二到步驟六，直到滿足終止條件為止。

4 仿真實驗

4.1 實驗環(huán)境建模

本文算法使用柵格地圖法[16]，將障礙物按比例在柵格地圖上建模，其中白色格子為可行區(qū)域，黑色格子代表著障礙物，為非可行區(qū)域，具體環(huán)境和柵格地圖節(jié)點序號分別如圖6 和公式（13）所示。

圖6：20*20 柵格地圖

公式（14）中D 為每個格子的序號，M 為柵格地圖的維度，x和y 分別為柵格地圖的橫縱坐標。

4.2 實驗參數(shù)設(shè)置

原煙花算法與改進的煙花算法共用參數(shù)，其中煙花迭代數(shù)目設(shè)置為50 次，種群數(shù)目為50，變異火花數(shù)目為3。

為了驗證本論文算法的性能，選取了蟻群算法[17]以及遺傳算法[18]作為對比，蟻群算法和遺傳算法參數(shù)分別如下：蟻群迭代次數(shù)為50 次，螞蟻個數(shù)為50，信息素系數(shù)α 為1.5，能見度因子β 為6，信息素揮發(fā)因子ρ 為0.9，信息素強度Q 為1。遺傳算法迭代次數(shù)為50 次，種群數(shù)500，基因數(shù)10，交叉概率0.7，變異概率為0.06。

將原煙花算法，本文改進煙花算法，蟻群算法以及遺傳算法在兩種不同規(guī)模的地圖中分別進行10 次仿真，各選取其中最好的一次仿真作為結(jié)果。

本文所有算法都是在mtlab2019b，windows10 系統(tǒng)，8G 內(nèi)存,i5處理器中進行仿真實驗的。

第一種仿真環(huán)境是在20*20 的柵格地圖中進行的，其路線效果圖和迭代圖分別如圖7，圖8 以及表1所示。

圖7：20*20 柵格地圖路線效果圖

圖8：20*20 迭代曲線圖對比

表1：20*20 路徑規(guī)劃數(shù)據(jù)表

第二種仿真環(huán)境對比是在30*30 的柵格地圖中進行的，其路線效果圖和迭代圖分別如圖9，圖10 以及表2所示。

表2：30*30 路徑規(guī)劃數(shù)據(jù)對比圖

圖9：30*30 柵格地圖路線效果圖

圖10：30*30 迭代曲線圖對比

4.3 實驗數(shù)據(jù)分析

結(jié)合表圖7 和圖8 以及表1 可以看出在20*20 的柵格地圖中，優(yōu)化過的煙花算法能夠取得最優(yōu)路徑，并且優(yōu)化過得煙花算法取得的最短路徑較蟻群算法提升了7.5%，較原煙花算法提升了25%，較遺傳算法提升了15.9%。其次優(yōu)化過得煙花算法收斂次數(shù)為21 次，是四個算法中最早收斂的。

從以及圖9，圖10 以及表2 可以看出，在30*30 的柵格地圖中，優(yōu)化過的煙花算法最短路徑長度為50.533，是四個算法中路徑最短的，其路徑長度較蟻群算法提升了11%，較原煙花算法提升了16.1%，較遺傳算法提升了18%，且優(yōu)化過得煙花算法經(jīng)過9 次迭代即完成收斂，相較于其他3 個算法的收斂次數(shù)，其性能大幅度上升。

從以上兩次對比實驗中，可以發(fā)現(xiàn)原煙花算法雖然沒有陷入局部最優(yōu)解，但其搜索最優(yōu)路徑的性能比蟻群算法略差，其原因有一方面在于原煙花算法最初是尋找數(shù)值最優(yōu)解，而非路徑規(guī)劃方面，所以其路徑規(guī)劃方面的應(yīng)用時還并不是很成熟。因此，通過對煙花算法的優(yōu)化，使得優(yōu)化煙花算法不論是在20*20 的柵格地圖中還是30*30 的柵格地圖中，相比于原煙花算法都能取得更好的規(guī)劃效率，獲得的最終路徑更短。

5 結(jié)語

通過對煙花算法的路徑節(jié)點連接機制的完善，將爆炸火花和高斯變異進行結(jié)合，并對下一代種群選擇的方式進行了修改，改進后煙花算法在不同規(guī)模的環(huán)境中在尋找最短路徑方面了顯著的提高，并且運算時間較原煙花算法也有了縮短。在多次試驗中，也發(fā)現(xiàn)了火花的數(shù)目和地圖復(fù)雜程度有著一定的關(guān)系，所以，下一步還會繼續(xù)完善對煙花算法，尋找煙花算法各個因素之間的相互影響關(guān)系，并探索該算法在真實環(huán)境中的表現(xiàn)。