高萬(wàn)博，朱俊武，章永龍，章小衛(wèi)

（揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225000）

0 概述

移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人研究領(lǐng)域中的重要分支，無(wú)人車是一種可以遠(yuǎn)程控制與自主導(dǎo)航的移動(dòng)機(jī)器人。無(wú)人車路徑規(guī)劃問(wèn)題［1］是指無(wú)人車在給定環(huán)境下，尋找一條滿足一定約束條件的無(wú)碰撞路徑［2］。目前，群智能算法是解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題的主要方法［3］，通過(guò)迭代生成新的可行解，在搜索空間中不斷探索與改進(jìn)，最終尋找到滿足約束條件的最佳可行解。群智能算法主要包括粒子群算法［4］、蟻群算法［5］、遺傳算法［6］、煙花算法［7］等。

文獻(xiàn)［8］提出一種新型啟發(fā)式算法，稱為煙花算法，其具有隨機(jī)性、局部性、爆發(fā)性、隱式并行性、多樣性、瞬時(shí)性等特點(diǎn)，通過(guò)煙花在空中爆炸產(chǎn)生火花的過(guò)程來(lái)模擬算法在搜索空間中求解問(wèn)題的過(guò)程，具有較優(yōu)的優(yōu)化求解能力。

在路徑規(guī)劃問(wèn)題中，因算法搜索空間較大，規(guī)劃環(huán)境較復(fù)雜，導(dǎo)致煙花算法難以尋找到全局最優(yōu)路徑，甚至尋找到的路徑會(huì)穿越障礙物。針對(duì)上述問(wèn)題，研究人員對(duì)煙花算法進(jìn)行改進(jìn)。文獻(xiàn)［9］結(jié)合煙花算法與蟻群算法提出一種混合算法，用于解決智能移動(dòng)體避障的問(wèn)題，通過(guò)加入先鋒火花操作提高搜索效率，并使用蟻群算法來(lái)實(shí)現(xiàn)避障的目的。文獻(xiàn)［10］在基本煙花算法的基礎(chǔ)上增加量子行為作為新的爆炸策略，使得煙花算法對(duì)全局和局部最優(yōu)解都具有較優(yōu)的搜索能力。文獻(xiàn)［11］通過(guò)可視圖法構(gòu)建士兵視覺(jué)場(chǎng)景，利用插入和刪除節(jié)點(diǎn)操作解決路徑不連續(xù)的問(wèn)題。一些研究人員采用基于深度學(xué)習(xí)的方法來(lái)解決該類問(wèn)題。文獻(xiàn)［12］對(duì)卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，構(gòu)建圖像與動(dòng)作的映射關(guān)系，實(shí)現(xiàn)移動(dòng)機(jī)器人路徑規(guī)劃。文獻(xiàn)［13-15］將圖像作為唯一輸入，訓(xùn)練強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)實(shí)現(xiàn)移動(dòng)機(jī)器人在未知環(huán)境下自主完成避障和區(qū)域覆蓋的任務(wù)。文獻(xiàn)［16］通過(guò)改進(jìn)的深度Q 網(wǎng)絡(luò)（DQN）訓(xùn)練多個(gè)機(jī)器人進(jìn)行路徑規(guī)劃，以完成無(wú)人倉(cāng)庫(kù)調(diào)度任務(wù)。文獻(xiàn)［17］通過(guò)深度強(qiáng)化學(xué)習(xí)模型學(xué)習(xí)改進(jìn)啟發(fā)式方法，從而解決旅行商問(wèn)題。文獻(xiàn)［18-20］通過(guò)改進(jìn)的深度強(qiáng)化學(xué)習(xí)模型解決車輛路徑優(yōu)化及其變體問(wèn)題。

基本煙花算法在三維地形環(huán)境下進(jìn)行路徑規(guī)劃時(shí)，因部分路徑節(jié)點(diǎn)經(jīng)過(guò)爆炸操作會(huì)遠(yuǎn)離原始路徑且種群的路徑片段間缺乏信息交互，導(dǎo)致收斂速度和探索最優(yōu)解的能力降低。針對(duì)上述問(wèn)題，本文提出選擇交叉煙花算法。通過(guò)路徑節(jié)點(diǎn)的輪盤選擇操作，根據(jù)路徑節(jié)點(diǎn)的適應(yīng)度函數(shù)進(jìn)行輪盤賭，以解決部分路徑節(jié)點(diǎn)偏離軌跡的問(wèn)題。借鑒遺傳算法中的交叉變異操作，引入選擇交叉變異操作，將篩選出的路徑片段與其他路徑片段進(jìn)行交換，從而提高煙花之間的信息交互性。

1 問(wèn)題描述

1.1 地形環(huán)境

無(wú)人車根據(jù)全局三維地形環(huán)境［21］建立三維空間直角坐標(biāo)系O-xyz，沿x軸、y軸將空間分割為m×n個(gè)柵格，將柵格地形環(huán)境的最大高度值z(mì)作為該柵格的內(nèi)容值。通過(guò)該方式將地形環(huán)境表示為zi=Map(xi，yi)的柵格矩陣，其中xi、yi表示柵格矩陣的行列坐標(biāo)位置，zi表示柵格值，即此柵格所在區(qū)域的地形高度。在地圖中的威脅區(qū)域主要是指無(wú)人車不能進(jìn)入的區(qū)域，如沼澤、湖泊等，由一個(gè)矩陣G表示，如式（1）所示：

圖1 柵格法構(gòu)建的地形矩陣Fig.1 Terrain matrix constructed by grid method

1.2 適應(yīng)度函數(shù)

本文從燃耗代價(jià)、威脅代價(jià)和平滑代價(jià)3 個(gè)角度衡量路徑優(yōu)劣，適應(yīng)度函數(shù)如式（2）所示：

其中：w1、w2、w3為平衡各指標(biāo)的權(quán)重系數(shù)，且1；Cf為無(wú)人車行駛時(shí)產(chǎn)生的路程燃耗代價(jià)；Cd為無(wú)人車經(jīng)過(guò)威脅區(qū)域時(shí)產(chǎn)生的威脅代價(jià)；Cs為無(wú)人車轉(zhuǎn)彎行駛時(shí)產(chǎn)生的轉(zhuǎn)角平滑代價(jià)。

1.2.1 燃耗代價(jià)

其中：kl＜1 ＜kh；Xi＝(xi，yj，zi，j)表示xi列yj行，值 為zi，j的柵格塊。

路徑的燃耗代價(jià)為各路徑節(jié)點(diǎn)燃耗代價(jià)之和，如式（5）所示：

1.2.2 威脅代價(jià)

無(wú)人車規(guī)劃的路徑需遠(yuǎn)離威脅區(qū)域，保證路徑的安全性。路徑點(diǎn)的威脅代價(jià)通過(guò)路徑點(diǎn)與威脅區(qū)域的圓心距離來(lái)描述，距離越遠(yuǎn)則路徑點(diǎn)越安全。路徑點(diǎn)Xi的威脅代價(jià)如式（6）所示：

其中：R為威脅區(qū)域的半徑；為威脅區(qū)域中心點(diǎn)的坐標(biāo)和高度值。當(dāng)路徑節(jié)點(diǎn)的距離小于最小威脅區(qū)域半徑時(shí)，Cplot_d大于1，則該點(diǎn)不符合構(gòu)成路徑的要求。

威脅區(qū)域信息表示如圖2 所示。

圖2 威脅區(qū)域坐標(biāo)圖Fig.2 Coordinate diagram of the threat region

路徑節(jié)點(diǎn)A、B、C距圓心的長(zhǎng)度分別為d1、d2、d3，其 中d1＜R＜d2＜d3，因 此Cplot_d(A) ＜1 ＜Cplot_d(B) ＜Cplot_d(C)。路徑節(jié)點(diǎn)A不符合路徑構(gòu)成要求將被舍棄，節(jié)點(diǎn)C的威脅代價(jià)比節(jié)點(diǎn)B更低。

路徑的威脅代價(jià)為各路徑節(jié)點(diǎn)威脅代價(jià)之和，如式（7）所示：

1.2.3 平滑代價(jià)

無(wú)人車需滿足自身的動(dòng)力學(xué)要求，避免轉(zhuǎn)彎時(shí)角度太小。路徑點(diǎn)平滑代價(jià)用路徑點(diǎn)與其前后節(jié)點(diǎn)形成的夾角來(lái)描述。夾角越小，無(wú)人車的轉(zhuǎn)角越大，路徑越不平滑。路徑節(jié)點(diǎn)Xi的平滑代價(jià)如式（8）所示：

其中：α為無(wú)人車的最小轉(zhuǎn)角；θi為行駛過(guò)程中路徑節(jié)點(diǎn)Xi的夾角。當(dāng)θi小于無(wú)人車的最小轉(zhuǎn)角α?xí)r，Cplot_s大于1，則該路徑節(jié)點(diǎn)不符合路徑構(gòu)成要求，應(yīng)當(dāng)舍去。平滑代價(jià)信息表示如圖3所示，無(wú)人車沿著∠OAB方向進(jìn)行轉(zhuǎn)角，最小轉(zhuǎn)角角度為∠OAA'即α。路徑節(jié)點(diǎn)A的夾角θ大于最小轉(zhuǎn)角α，則保留該節(jié)點(diǎn)。

圖3 平滑代價(jià)坐標(biāo)圖Fig.3 Coordinate diagram of the smooth cost

路徑的平滑代價(jià)為各路徑節(jié)點(diǎn)的平滑代價(jià)之和，如式（9）所示：

2 基本煙花算法

基本煙花算法將煙花看作空間中的一個(gè)解，通過(guò)對(duì)煙花進(jìn)行爆炸操作，選擇不同的火花對(duì)鄰域進(jìn)行搜索。其基本原理是煙花對(duì)應(yīng)的適應(yīng)度值越小，則該煙花爆炸產(chǎn)生的火花數(shù)量越多，爆炸幅度越??；相反，若煙花對(duì)應(yīng)的適應(yīng)度值越大，則該煙花爆炸產(chǎn)生的火花數(shù)量越少，且爆炸幅度越大。

在基本煙花算法中，第i個(gè)煙花的爆炸強(qiáng)度如式（10）所示：

第i個(gè)煙花的爆炸幅度如式（11）所示：

其中：fmin為當(dāng)前種群中的最小適應(yīng)度值為控制煙花爆炸幅度的常數(shù)。

為了增加種群中煙花的多樣性，基本煙花算法隨機(jī)選擇j個(gè)維度對(duì)煙花進(jìn)行高斯變異，如式（12）所示：

其中：g表示均值為1、方差為1且滿足高斯分布的隨機(jī)數(shù)。

在煙花爆炸后產(chǎn)生的變異火花和爆炸火花可能會(huì)超出可行域范圍，根據(jù)映射規(guī)則重新映射回可行域內(nèi)，如式（13）所示：

其中：為三維地形環(huán)境中第k維的上邊界；為三維地形環(huán)境中第k維的下邊界；為 第i號(hào)煙花的第m個(gè)路徑節(jié)點(diǎn)在第k維的位置。

煙花算法通過(guò)選擇操作對(duì)產(chǎn)生的新火花進(jìn)行篩選，并選擇部分火花作為下一代煙花，如式（14）和式（15）所示：

其中：R(pi)為火花pi與其他火花之間的距離求和；K為當(dāng)前種群中所有火花的個(gè)數(shù)；Pr(pi)為煙花pi被選中的概率。

3 本文算法

3.1 輪盤選擇操作

本文通過(guò)分析基本煙花算法迭代生成的路徑，發(fā)現(xiàn)路徑中可能存在部分路徑節(jié)點(diǎn)偏離軌跡的問(wèn)題。煙花算法的爆炸操作示意圖如圖4 所示。

圖4 煙花算法爆炸操作示意圖Fig.4 Schematic diagram of explosion operation of fireworks algotithm

路徑節(jié)點(diǎn)Xi、Xj的適應(yīng)度值遠(yuǎn)大于路徑中的其他節(jié)點(diǎn)。因此，本文提出針對(duì)路徑節(jié)點(diǎn)的輪盤選擇操作，提升具有高適應(yīng)度值的路徑節(jié)點(diǎn)被選擇并進(jìn)行變異的概率。圖4 中為經(jīng)過(guò)輪盤選擇后再變異操作得到的新路徑節(jié)點(diǎn)。本文輪盤選擇操作分為以下3 個(gè)步驟：

1）計(jì)算路徑節(jié)點(diǎn)Xi的適應(yīng)度值，如式（16）所示：

2）通過(guò)輪盤賭［22］的方法對(duì)需要爆炸的節(jié)點(diǎn)進(jìn)行選擇，路徑節(jié)點(diǎn)Xi被選擇進(jìn)行爆炸的概率如式（17）所示：

其中：Q(i)為P(i)的累計(jì)概率；select(k)為用于保存k個(gè)被選中的路徑維度；rand 為生成均勻分布的0～1隨機(jī)數(shù)，若rand 在[Q(i)，Q(i+1)]區(qū)間內(nèi)，則將i存入select 中。

3）對(duì)被選擇的路徑節(jié)點(diǎn)進(jìn)行位移操作，如式（18）所示：

因此，本文通過(guò)爆炸位移使路徑節(jié)點(diǎn)在爆炸幅度內(nèi)進(jìn)行一次位置變化。

3.2 選擇交叉變異

基本煙花算法通過(guò)高斯變異和爆炸操作對(duì)煙花的節(jié)點(diǎn)進(jìn)行單點(diǎn)變異，并未考慮煙花之間路徑片段的交互變異。例如，在一次迭代過(guò)程中，一個(gè)煙花Pi=，會(huì)在某一段路徑片段中出現(xiàn)較高的適應(yīng)度值，假設(shè)為P'=，而單一路徑節(jié)點(diǎn)的變異方式并不能顯著提高煙花適應(yīng)度值。

本文借鑒遺傳算法中的交叉變異因子［23］思想，提出選擇交叉變異，并將其作為新的火花變異方式，通過(guò)3.1 節(jié)輪盤選擇的方式選擇其中兩個(gè)節(jié)點(diǎn)作為路徑片段，并將其與另一個(gè)煙花之間的路徑片段進(jìn)行交換，通過(guò)該方式增大最優(yōu)解出現(xiàn)的概率［24］，以加強(qiáng)種群中煙花之間的信息交互。隨機(jī)選擇的兩個(gè)父代煙花par1、par2通過(guò)輪盤選擇操作產(chǎn)生路徑節(jié)點(diǎn)，對(duì)選中的路徑節(jié)點(diǎn)進(jìn)行路徑片段交叉，以得到選擇交叉火花child1、child2，如式（19）所示：

圖5 選擇交叉火花的產(chǎn)生流程Fig.5 Generation procedure of selection crossover spark

3.3 算法流程

選擇交叉煙花算法的具體流程如算法1 所示。

算法1選擇交叉煙花算法（SC-FWA）

輸入地形Map，威脅區(qū)域矩陣G，最大迭代次數(shù)maxgen

輸出最優(yōu)路徑pb

1.隨機(jī)初始煙花種群路徑P={p1，p2，…，pN}

2.for i=1，i ≤maxgen，i++

3.通過(guò)式（2）計(jì)算種群中每個(gè)煙花適應(yīng)度值fcost

4.通過(guò)式（10）和式（11）計(jì)算煙花的爆炸幅度和火花個(gè)數(shù)

5.通過(guò)輪盤選擇操作式（17）篩選出需要位移的路徑節(jié)點(diǎn)Xselect

6.依據(jù)式（18）在爆炸幅度內(nèi)對(duì)Xselect進(jìn)行爆炸位移

7.隨機(jī)選取路徑節(jié)點(diǎn)Xj依據(jù)式（12）進(jìn)行高斯變異

8.通過(guò)式（19）將被選擇的路徑par1、par2進(jìn)行交叉變換，產(chǎn)生選擇交叉火花

9.通過(guò)式（13）對(duì)變異后超出可行域的路徑節(jié)點(diǎn)映射回可行域內(nèi)

10.保留最優(yōu)煙花，將其余爆炸火花、高斯變異火花、選擇交叉火花通過(guò)式（14）選擇下一代煙花。

步驟1 在搜索空間中通過(guò)隨機(jī)選擇符合適應(yīng)度值要求的n個(gè)路徑節(jié)點(diǎn)作為初始路徑，并構(gòu)建N條初始路徑以構(gòu)成煙花種群。步驟2～步驟10 在給定的最大迭代次數(shù)內(nèi)循環(huán)使用選擇交叉煙花算法，其中步驟3 和步驟4 計(jì)算適應(yīng)度函數(shù)，得到爆炸幅度與爆炸強(qiáng)度，步驟5～步驟8 產(chǎn)生爆炸火花、高斯變異火花和選擇交叉火花，步驟9 對(duì)超出可行域的路徑節(jié)點(diǎn)進(jìn)行映射，步驟10 通過(guò)選擇操作對(duì)火花進(jìn)行篩選，形成下一代煙花。當(dāng)達(dá)到最大迭代次數(shù)后，算法輸出最優(yōu)煙花，并作為無(wú)人車的規(guī)劃路徑。

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

4.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

本文在MATLAB 2018b 上進(jìn)行仿真實(shí)驗(yàn)，計(jì)算機(jī)配置為2.60 GHz CPU，16 GB RAM、64 位操作系統(tǒng)。

本文將蟻群算法（ACO）［25］、基本煙花算法（FWA）、改進(jìn)煙花算法（IFWA）［11］、選擇尋優(yōu)煙花算法（SC-FWA）進(jìn)行對(duì)比實(shí)驗(yàn)。SC-FWA 的實(shí)驗(yàn)參數(shù)：最大迭代次數(shù)max_gen=300，初始煙花個(gè)數(shù)N=10，最小轉(zhuǎn)角α=π/2，最大爆炸幅度=10，最大爆炸強(qiáng)度=10，威脅代價(jià)C1=0.2，平滑代價(jià)C2=0.2，燃耗代價(jià)C3=0.6，上坡燃耗系數(shù)kh=0.2，下坡燃耗系數(shù)kl=0.5，搜索空間上界=100，搜索空間下界=1，簡(jiǎn)單地形環(huán)境適應(yīng)度函數(shù)閾值Fs=270，復(fù)雜地形環(huán)境適應(yīng)度函數(shù)閾值Fc=750。

4.2 結(jié)果分析

為驗(yàn)證選擇交叉煙花算法的收斂性和高效性，本文將選擇交叉煙花算法的兩類改進(jìn)操作分開(kāi)進(jìn)行對(duì)比分析。其中加入輪盤選擇操作的煙花算法（S-FWA）是在基本煙花算法的基礎(chǔ)上對(duì)不同適應(yīng)度值的路徑節(jié)點(diǎn)進(jìn)行輪盤賭操作；加入選擇交叉變異的煙花算法（C-FWA）是在基本煙花算法的基礎(chǔ)上隨機(jī)選擇不同的路徑片段進(jìn)行交換。本文將ACO、FWA、IFWA、S-FWA、C-FWA、SC-FWA 在簡(jiǎn)單地形和復(fù)雜地形下進(jìn)行實(shí)驗(yàn)對(duì)比。當(dāng)執(zhí)行完給定的最大迭代次數(shù)后，不同算法在簡(jiǎn)單地形和復(fù)雜地形下的路徑適應(yīng)度值如表1 所示。

表1 不同算法的路徑適應(yīng)度值對(duì)比Table 1 Path fitness values comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 均找到了低于ACO 適應(yīng)度值的路徑，說(shuō)明煙花算法具有較優(yōu)的空間探索能力，其中C-FWA 相較于IFWA、S-FWA、FWA 適應(yīng)度值更低。因此，C-FWA 通過(guò)選擇交叉變異進(jìn)行煙花間的片段交換，以增強(qiáng)煙花算法中煙花間的交互性，從而有效提升探索最優(yōu)解的能力，但其不足是加入了新的交叉操作會(huì)導(dǎo)致運(yùn)行時(shí)間較高于其他基本煙花算法。

在簡(jiǎn)單地形和復(fù)雜地形中，若算法探索到低于適應(yīng)度函數(shù)閾值的路徑時(shí)，則終止程序并記錄運(yùn)行時(shí)間，不同算法在簡(jiǎn)單地形和復(fù)雜地形下的運(yùn)行時(shí)間如表2 所示。

表2 不同算法的運(yùn)行時(shí)間對(duì)比Table 2 Running time comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 運(yùn)行時(shí)間均低于ACO，說(shuō)明煙花算法具有高效性。其中S-FWA 相較于IFWA、C-FWA、FWA 運(yùn)行時(shí)間更短，由此可見(jiàn)，通過(guò)輪盤選擇操作提高偏離路徑節(jié)點(diǎn)的變異概率，從而加快煙花算法的收斂速度。但由于S-FWA 減弱了煙花種群中煙花的多樣性，因此探索最優(yōu)解的能力降低，當(dāng)完成所有迭代次數(shù)后，路徑適應(yīng)度值較高。

SC-FWA 通過(guò)輪盤選擇操作和選擇交叉變異操作，結(jié)合S-FWA 中收斂速度快和C-FWA 中搜索全局最優(yōu)解能力強(qiáng)的特點(diǎn)，在簡(jiǎn)單和復(fù)雜地形中，運(yùn)行時(shí)間和路徑適應(yīng)度值均優(yōu)于IFWA、FWA、ACO。因此，SC-FWA 具有一定的收斂性和高效性，規(guī)劃的路徑適應(yīng)度值更低，運(yùn)行時(shí)間更短。

在100 km×100 km的仿真簡(jiǎn)單和復(fù)雜地形環(huán)境下，ACO、FWA、IFWA、SC-FWA算法的路徑對(duì)比分別如圖6和圖7所示（彩色效果見(jiàn)《計(jì)算機(jī)工程》官網(wǎng)HTML版）。其中，（0，0）為起始點(diǎn)，（100，100）為目標(biāo)點(diǎn)。不同顏色代表區(qū)塊的高度值（如山丘、山峰等），藍(lán)色區(qū)域?yàn)槠皆瓍^(qū)，黃色區(qū)域?yàn)樯椒?，圓圈標(biāo)識(shí)的圓形區(qū)域?yàn)橥{區(qū)域。

圖6 在簡(jiǎn)單地形下不同算法的路徑規(guī)劃對(duì)比Fig.6 Path planning comparison among different algorithms in simple terrain

圖7 在復(fù)雜地形下不同算法的路徑規(guī)劃對(duì)比Fig.7 Path planning comparison among different algorithms in complex terrain

簡(jiǎn)單地形較為單一，大部分為平原地區(qū)。從圖6可以看出，4 種算法均找到了近似全局最優(yōu)解，威脅代價(jià)與轉(zhuǎn)角代價(jià)均相近。但SC-FWA 路徑長(zhǎng)度更短，燃耗更低。而ACO 經(jīng)過(guò)部分山地區(qū)域，導(dǎo)致燃耗增加。從圖7 可以看出，在復(fù)雜地形下，由于加入了燃耗代價(jià)，將轉(zhuǎn)角代價(jià)和威脅代價(jià)作為適應(yīng)度函數(shù)，SC-FWA 規(guī)劃的路徑遠(yuǎn)離了威脅區(qū)域，并且路徑更加平滑，無(wú)人車選擇行駛的路徑地形更加平坦，減少了上坡下坡的燃耗，因此規(guī)劃的路徑適應(yīng)度值更低。IFWA 找到了與SC-FWA 相近的路徑，但是生成的路徑經(jīng)過(guò)山地地形，增加了燃耗消耗。而FWA 和ACO 陷入了局部最優(yōu)解，沒(méi)有找到最合理的路徑。FWA 相對(duì)ACO 產(chǎn)生的路徑更加平滑，但是規(guī)劃的路徑經(jīng)過(guò)了山地，導(dǎo)致燃耗代價(jià)升高。相對(duì)于SC-FWA和IFWA，F(xiàn)WA 規(guī)劃的路徑距離威脅區(qū)域更近，ACO雖然繞過(guò)了山地地形，但是規(guī)劃的路徑不平滑，轉(zhuǎn)角過(guò)多，距離威脅區(qū)域較近。

在簡(jiǎn)單地形和復(fù)雜地形下FWA、IFWA、ACO 和SC-FWA 算法的收斂曲線分別如圖8 和圖9 所示。

圖8 在簡(jiǎn)單地形下不同算法的收斂曲線對(duì)比Fig.8 Convergence curves comparison among different algorithms in simple terrain

圖9 在復(fù)雜地形下不同算法的收斂曲線對(duì)比Fig.9 Convergence curves comparison among different algorithms in complex terrain

煙花適應(yīng)度值越低則表示生成的路徑代價(jià)越小、產(chǎn)生的路徑更加遠(yuǎn)離威脅區(qū)域、路徑更加平滑且燃耗更低。在簡(jiǎn)單地形下，SC-FWA 各個(gè)時(shí)期的適應(yīng)度值均優(yōu)于FWA、ACO、IFWA，并且在迭代第65 次時(shí)，SC-FWA 算法已基本收斂。FWA、ACO、IFWA 算法適應(yīng)度函數(shù)變化不大，說(shuō)明產(chǎn)生的解均靠近全局最優(yōu)解。在復(fù)雜地形下，SC-FWA 的適應(yīng)度值在前期下降更快，當(dāng)?shù)螖?shù)為150～200 時(shí)，陷入了與IFWA 同樣的局部最優(yōu)解，通過(guò)選擇交叉操作，在迭代200 次后跳出局部最優(yōu)解，以搜尋到適應(yīng)度值更小的路徑。在迭代后期，SC-FWA 找到了相比于FWA、ACO、IFWA更優(yōu)的路徑。

實(shí)驗(yàn)結(jié)果表明，通過(guò)構(gòu)建適應(yīng)度函數(shù)，使得SC-FWA 規(guī)劃的路徑更加平滑且遠(yuǎn)離威脅區(qū)域。在FWA 的基礎(chǔ)上加入了輪盤選擇操作和選擇交叉變異，提高了低適應(yīng)度節(jié)點(diǎn)被選擇進(jìn)行變異的概率，并使得煙花之間可以進(jìn)行信息交互。因此，SC-FWA在保證煙花多樣性的同時(shí)提高了算法的搜索效率，使算法在不同的地形環(huán)境下都具有良好的適應(yīng)性，不易陷入局部最優(yōu)解，使其具有更快的收斂速度，規(guī)劃出更安全、高效的路徑。

5 結(jié)束語(yǔ)

本文將三維地形環(huán)境下無(wú)人車路徑規(guī)劃問(wèn)題轉(zhuǎn)化為多約束條件的優(yōu)化問(wèn)題［26］，提出選擇交叉煙花算法。為了更真實(shí)地模擬無(wú)人車在三維地形環(huán)境下的行駛過(guò)程，引入燃耗代價(jià)、威脅代價(jià)和平滑代價(jià)作為適應(yīng)度函數(shù)對(duì)路徑進(jìn)行評(píng)價(jià)，使產(chǎn)生的路徑更加平滑且遠(yuǎn)離威脅區(qū)域。仿真實(shí)驗(yàn)結(jié)果表明，相比ACO、FWA、IFWA等算法，本文算法具有較優(yōu)的求解性能和較快的收斂速度，使無(wú)人車在較短的時(shí)間內(nèi)規(guī)劃出更優(yōu)的路徑。下一步將考慮在三維地形環(huán)境下融合改進(jìn)的煙花算法與強(qiáng)化學(xué)習(xí)模型，使多個(gè)無(wú)人車可以學(xué)習(xí)合作避障策略，以有效規(guī)避動(dòng)態(tài)障礙物。