瞬態(tài)搜索金槍魚優(yōu)化城市物流無人機(jī)路徑規(guī)劃

謝繼武，席建新

(1.內(nèi)蒙古師范大學(xué) 國(guó)際設(shè)計(jì)學(xué)院，內(nèi)蒙古 呼和浩特 010010；2.內(nèi)蒙古師范大學(xué) 設(shè)計(jì)與社會(huì)創(chuàng)新內(nèi)蒙古高校人文社科重點(diǎn)研究基地，內(nèi)蒙古 呼和浩特 010010； 3.內(nèi)蒙古自治區(qū)科技創(chuàng)新發(fā)展中心，內(nèi)蒙古 呼和浩特 010010)

0 引 言

物流無人機(jī)路徑規(guī)劃本質(zhì)是在飛行環(huán)境約束及飛行器硬件約束前提下，搜索代價(jià)小且安全的物流配送最優(yōu)路徑[1]。城市環(huán)境中，樓宇分布、天氣影響及禁飛等因素的存在，使得無人機(jī)路徑規(guī)劃成為亟待解決的難題。物流無人機(jī)路徑規(guī)劃方法主要有兩類，一類是傳統(tǒng)算法，如A*[2]、人工勢(shì)場(chǎng)[3]、動(dòng)態(tài)規(guī)劃[4]及Dijkstra[5]等。另一類是智能優(yōu)化算法，如蟻群[6]、粒子群[7]、遺傳[8]及差分進(jìn)化[9]等。智能算法在沒有全局模型情況下，能利用啟發(fā)式機(jī)制解決非線性復(fù)雜路徑規(guī)劃問題。文獻(xiàn)[10]在麻雀算法中引入立方混沌和精英反向?qū)W習(xí)提升算法搜索性能，并對(duì)三維無人機(jī)路徑規(guī)劃求解，但航跡規(guī)劃實(shí)時(shí)性較差。文獻(xiàn)[11]結(jié)合自適應(yīng)搜索蜂群算法求解無人機(jī)路徑規(guī)劃問題。文獻(xiàn)[12]設(shè)計(jì)A*初始化與變異灰狼算法相結(jié)合的無人機(jī)路徑規(guī)劃方法。文獻(xiàn)[13]將黃金正弦引入蝙蝠算法有效提升路徑搜索精度。文獻(xiàn)[14]利用灰狼算法提高路徑全局搜索能力，但模型不夠簡(jiǎn)單高效。

已有算法雖具有一定可行性，但也有一定不足，尤其在搜索精度和穩(wěn)定性上還有一定局限性。金槍魚算法TSO是一種模擬金槍魚覓食行為的新型智能優(yōu)化算法[15]，且體現(xiàn)出比粒子群和遺傳算法更高的搜索精度，已在信號(hào)估算[16]和學(xué)習(xí)模型優(yōu)化[17]等問題上得到應(yīng)用。但TSO在解決高維復(fù)雜問題依然存在搜索精度差的不足。為此，本文將設(shè)計(jì)具有自適應(yīng)瞬態(tài)搜索功能的TSO算法，利用多策略融合改進(jìn)機(jī)制提升算法搜索能力，并將其應(yīng)用于城市物流無人機(jī)三維路徑規(guī)劃問題中，通過金槍魚迭代覓食搜索代價(jià)最優(yōu)規(guī)劃路徑。

1 城市物流無人機(jī)路徑規(guī)劃建模

1.1 飛行環(huán)境建模

面向城市環(huán)境的物流無人機(jī)路徑規(guī)劃問題上，無人機(jī)的飛行路徑主要面臨的障礙物威脅有3類：樓宇建筑物、惡劣天氣以及禁飛區(qū)域。為了確保無人機(jī)具有安全路徑，需要規(guī)劃出與3種威脅避讓的路徑。實(shí)驗(yàn)中，將樓宇建筑物設(shè)置為不可穿越的長(zhǎng)方體，將惡劣天氣設(shè)置為定高圓柱體，禁飛區(qū)域一般是以地面某點(diǎn)為圓心輻射的區(qū)域，可將其設(shè)置為半球體。如圖1所示為城市環(huán)境中物流無人機(jī)飛行環(huán)境建模。

圖1 城市物流無人機(jī)飛行環(huán)境建模

1.2 飛行約束條件

1.2.1 最大路徑長(zhǎng)度約束

令路徑規(guī)劃點(diǎn)(即導(dǎo)航點(diǎn))數(shù)量為n，可飛行的最大路徑長(zhǎng)度為L(zhǎng)max，第i段路徑的長(zhǎng)度為L(zhǎng)i，則無人機(jī)路徑規(guī)劃總長(zhǎng)及需滿足的約束條件為

(1)

1.2.2 飛行高度約束

物流無人機(jī)的飛行高度若與地面距離過近，會(huì)有安全隱患，需對(duì)飛行最低高度約束。令Hi為路徑段i的最低飛行高度，Hmin為最低飛行高度約束，則飛行高度需滿足約束

Hi≥Hmin

(2)

1.2.3 爬升/俯沖角約束

物流無人機(jī)遭遇障礙物威脅時(shí)一般需要進(jìn)行高度爬升或俯沖，但為了確保飛行的穩(wěn)定性，需在爬升角和俯沖角上設(shè)置最大限制，超出限制可能導(dǎo)致物流配送任務(wù)失敗或造成無人機(jī)故障。令φ為無人機(jī)的爬升/俯沖角，需要滿足

(3)

式中：(xi，yi，zi)、 (xj，yj，zj) 對(duì)應(yīng)無人機(jī)位置的兩個(gè)路徑點(diǎn)坐標(biāo)。

1.2.4 轉(zhuǎn)彎角約束

遇到障礙物威脅時(shí)，物流無人機(jī)也可能需要水平轉(zhuǎn)向，生成可行路徑。若轉(zhuǎn)彎角超過最大限制，也可能導(dǎo)致無人機(jī)故障或無法完成配送任務(wù)。令θ為無人機(jī)在水平面上的最大轉(zhuǎn)彎角，Ai=(xi-xi-1，yi-yi-1) 為第i段飛行路徑的水平面投影，且其在第i+1段飛行路徑上的投影為Ai+1=(xi+1-xi，yi+1-yi)， 則物流無人機(jī)最大轉(zhuǎn)彎角約束可由Ai與Ai+1間的夾角表示，最大轉(zhuǎn)彎角約束如圖2所示。轉(zhuǎn)彎角約束為

(4)

圖2 轉(zhuǎn)彎角

1.3 飛行代價(jià)函數(shù)

定義飛行代價(jià)函數(shù)評(píng)估物流無人機(jī)規(guī)劃路徑質(zhì)量，主要考慮路徑長(zhǎng)度、飛行高度以及飛行偏轉(zhuǎn)角大小3個(gè)代價(jià)。

1.3.1 路徑長(zhǎng)度代價(jià)

對(duì)于物流無人機(jī)而言，配送路徑長(zhǎng)度最短，可以得到更少的耗時(shí)和節(jié)省更多的能耗。將路徑長(zhǎng)度代價(jià)定義為

(5)

1.3.2 飛行高度代價(jià)

對(duì)于物流無人機(jī)而言，實(shí)現(xiàn)穩(wěn)定高度飛行有助于減小飛行器的系統(tǒng)負(fù)載，節(jié)省能耗。飛行高度應(yīng)在滿足高度約束的同時(shí)，盡量不發(fā)生大幅波動(dòng)。將飛行高度代價(jià)定義為

(6)

1.3.3 飛行偏轉(zhuǎn)角代價(jià)

由于空氣阻力，無人機(jī)在飛行方向上作出偏移時(shí)，飛行器會(huì)承受壓力并消耗能量。飛行轉(zhuǎn)角越大，承受壓力越大，能耗越大，同時(shí)會(huì)降低飛行效率。飛行轉(zhuǎn)角越小，也表明無人機(jī)飛行平滑性越好。將飛行偏轉(zhuǎn)角代價(jià)定義為

(7)

Φj=(xj+1-xj，yj+1-yj，zj+1-zj)

(8)

1.3.4 總代價(jià)函數(shù)

綜合考慮以上3個(gè)代價(jià)定義物流無人機(jī)總代價(jià)函數(shù)為

Ccost=w1Clenght+w2Cheight+w3Csmooth

(9)

(10)

其中，w1、w2和w3分別對(duì)應(yīng)路徑長(zhǎng)度、飛行高度以及飛行偏轉(zhuǎn)角大小3個(gè)代價(jià)的權(quán)重因子。

2 自適應(yīng)瞬態(tài)搜索金槍魚優(yōu)化算法TSTSO

2.1 標(biāo)準(zhǔn)TSO算法

TSO算法模擬了金槍魚群的兩種合作覓食行為：螺旋覓食和拋物線覓食。螺旋覓食時(shí)種群個(gè)體位置更新方式為

(11)

其中，N為種群規(guī)模，t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)，rand∈[0，1]，Xrand(t)、Xbest(t) 為迭代t時(shí)選擇的隨機(jī)個(gè)體和最優(yōu)個(gè)體，Xi(t)、Xi(t+1) 為迭代t時(shí)的個(gè)體位置和更新位置，α1、α2為個(gè)體向隨機(jī)個(gè)體和最優(yōu)個(gè)體移動(dòng)的權(quán)重

(12)

式中：a為常量，用于確定金槍魚在初始階段跟隨最佳個(gè)體和前一個(gè)體的程度。β為螺旋因子，定義為

(13)

式中：b∈[0，1] 為隨機(jī)量。

拋物線覓食時(shí)種群個(gè)體的位置更新方式為

(14)

式中：TF={-1，1} 為隨機(jī)選擇量，p=(1-t/Tmax)t/Tmax， 用于控制種群的開發(fā)幅度。

2.2 自適應(yīng)瞬態(tài)搜索改進(jìn)金槍魚優(yōu)化算法TSTSO設(shè)計(jì)

2.2.1 Kent混沌種群初始化

TSO為了實(shí)現(xiàn)搜索隨機(jī)性，種群初始化階段在搜索邊界內(nèi)隨機(jī)生成個(gè)體位置，這種方式無法保障位置分布的均勻性，容易降低搜索效率。為此，引入Kent混沌序列進(jìn)行種群初始化。Kent混沌映射同時(shí)具備隨機(jī)性和遍歷性，可在[0，1]內(nèi)生成一定規(guī)律的序列，再以Kent混沌因子改進(jìn)個(gè)體位置初始化，使個(gè)體分布更加合理和均勻。Kent混沌映射公式為

(15)

式中：a為混沌系數(shù)，a=0.5時(shí)，混沌系統(tǒng)呈現(xiàn)短周期狀態(tài)。結(jié)合式(15)生成的Kent混沌序列值，將其映射至搜索空間內(nèi)生成金槍魚個(gè)體的初始位置，映射公式為

x=xmin+y×(xmax-xmin)

(16)

式中：[xmin，xmax] 為個(gè)體搜索范圍，y為Kent混沌因子。

令種群規(guī)模為50，圖3是隨機(jī)初始化和混沌Kent初始化生成的個(gè)體分布。隨機(jī)初始化容易產(chǎn)生個(gè)體重疊和區(qū)域空白未搜索的缺點(diǎn)，Kent混沌初始化種群結(jié)構(gòu)均勻性更優(yōu)，對(duì)整個(gè)區(qū)間可以全面遍歷。

圖3 兩種種群初始化分布

2.2.2 自適應(yīng)瞬態(tài)搜索

螺旋覓食搜索過程中，個(gè)體搜索范圍將逐漸壓縮，造成搜索盲點(diǎn)，一定程度降低了種群多樣性和算法全局搜索力度。為此，TSTSO引入一種基于瞬態(tài)搜索的螺旋覓食機(jī)制改善TSO全局搜索能力。瞬態(tài)搜索策略是一種模擬電路開關(guān)瞬態(tài)行為物理物象的啟發(fā)式搜索機(jī)制，且是全局搜索能力較強(qiáng)的隨機(jī)搜索方法，其狀態(tài)更新方式為

(17)

式中：r1為[0，1]內(nèi)隨機(jī)值，T、C1為兩個(gè)瞬態(tài)系數(shù)，定義為

(18)

式中：r2、r3均為[0，1]內(nèi)隨機(jī)值，k為自然數(shù)常量，z為瞬態(tài)系數(shù)衰減因子。瞬態(tài)搜索以T∈[-2，2] 實(shí)現(xiàn)全局搜索與局部開發(fā)的線性轉(zhuǎn)換。T<0時(shí)，瞬態(tài)搜索振幅更大，能以更廣泛的空間遍歷性搜索最優(yōu)解，提升全局搜索能力；T>0時(shí)，瞬態(tài)搜索會(huì)逐漸趨于穩(wěn)態(tài)，精細(xì)開發(fā)逼近最優(yōu)解。同時(shí)，為了全局搜索與局部開發(fā)的有效均衡，對(duì)瞬態(tài)系數(shù)衰減進(jìn)行非線性自適應(yīng)調(diào)整為

(19)

式中：zini、zfin為衰減因子的初值和終值。

2.2.3 透鏡成像對(duì)立學(xué)習(xí)和柯西變異

對(duì)于TSO算法，目標(biāo)位置的更新取決于迭代中種群位置的更新，該過程會(huì)選擇每次迭代中適應(yīng)度最優(yōu)解替換前代最優(yōu)個(gè)體，但算法沒有考慮目標(biāo)個(gè)體陷入局部最優(yōu)的情況。為此，TSTSO引入透鏡成像對(duì)立學(xué)習(xí)與柯西變異的混合擾動(dòng)機(jī)制對(duì)目標(biāo)個(gè)體位置擾動(dòng)，降低局部最優(yōu)的概率。

對(duì)立學(xué)習(xí)可以通過生成候選個(gè)體對(duì)立點(diǎn)的方式得到適應(yīng)度更好的種群，通過這種方式擴(kuò)展種群搜索范圍。

令X=(x1，x2，…，xD) 為D維空間內(nèi)的個(gè)體，且xj∈[aj，bj]，j=1，2，…，D。 則個(gè)體對(duì)立點(diǎn)為X′=(x′1，x′2，…，x′D)， 且x′j=aj+bj-xi，x′表示x的對(duì)立數(shù)。

對(duì)立學(xué)習(xí)能在迭代初期發(fā)揮作用，但迭代后期會(huì)出現(xiàn)大量個(gè)體聚集的情況，導(dǎo)致個(gè)體陷入局部解的陷阱，削弱了對(duì)立學(xué)習(xí)的作用。進(jìn)一步引入物理學(xué)中透鏡成像思想對(duì)對(duì)立學(xué)習(xí)進(jìn)行優(yōu)化。令搜索目標(biāo)位置對(duì)立點(diǎn)的過程為物體的透鏡成像。令 [a，b] 為個(gè)體搜索范圍，橫軸上最優(yōu)個(gè)體xbest處有一高為h的物體，通過原點(diǎn)為中心，焦距為r的透鏡，投影至對(duì)立面生成高為h′的鏡像個(gè)體，如圖4所示。則鏡像個(gè)體投射至x軸上位置即為xbest的透鏡成像對(duì)立位置點(diǎn)xbest′。根據(jù)透鏡成像原理有

(20)

(21)

定義縮放因子k=h/h′， 可得

(22)

當(dāng)k=1時(shí)，透鏡成像學(xué)習(xí)模型為標(biāo)準(zhǔn)對(duì)立學(xué)習(xí)模型。通過調(diào)整k，透鏡成像對(duì)立學(xué)習(xí)可以動(dòng)態(tài)搜索個(gè)體對(duì)立點(diǎn)，以此逼近最優(yōu)目標(biāo)位置。

圖4 透鏡成像對(duì)立學(xué)習(xí)模型

柯西分布是一種數(shù)學(xué)期望不存在的連續(xù)性概率分布，其概率密度函數(shù)為

(23)

柯西分布變異步長(zhǎng)比高斯分布范圍更廣。將在目標(biāo)位置更新中引入柯西算子對(duì)位置進(jìn)行動(dòng)態(tài)調(diào)節(jié)，能提高算法跳離局部最優(yōu)解的概率。其變異方式為

x(t+1)=cauchy(0，1)⊕xbest(t)+xbest(t)

(24)

式中：cauchy(0，1) 為0、1柯西算子。

透鏡成像對(duì)立學(xué)習(xí)與柯西分布有不同能力的擾動(dòng)幅度，為了提高TSO的搜索性能，TSTSO定義動(dòng)態(tài)選擇變異概率pr更新目標(biāo)位置，在pr下以隨機(jī)量rand與之對(duì)比，交替選擇執(zhí)行透鏡成像對(duì)立學(xué)習(xí)或柯西變異。選擇概率為

(25)

可見，pr是一種基于指數(shù)的自適應(yīng)變化概率。在變化趨勢(shì)上，迭代早期，pr較大，更可能滿足pr>rand，此時(shí)偏向于以柯西變異，避免過早導(dǎo)致種群多樣性缺失，出現(xiàn)早熟收斂；迭代后期，pr較小，更可能滿足pr

2.2.4 越界處理

當(dāng)個(gè)體搜索超過范圍時(shí)，TSO以搜索范圍的邊界替換越界位置，這種處理方式具有盲目性，沒有充分利用越界個(gè)體的有效信息。引入一種隨機(jī)回歸進(jìn)行個(gè)體越界處理，具體為

(26)

式中：γ為[0，1]內(nèi)隨機(jī)值，[lb，ub]為搜索邊界。

2.2.5 TSTSO算法性能驗(yàn)證

利用5個(gè)基準(zhǔn)函數(shù)對(duì)TSO改進(jìn)前后的性能測(cè)試分析，表1給出基準(zhǔn)函數(shù)特征。選取基準(zhǔn)函數(shù)Rastrigrin作出三維圖，展示函數(shù)特征，如圖5所示?？梢?，函數(shù)是明顯多峰值函數(shù)，具有密集的波峰波谷起伏，存在較多局部極值點(diǎn)，極其考驗(yàn)算法搜索全局最優(yōu)解的能力。其它4個(gè)基準(zhǔn)函數(shù)也均具備多局部極值點(diǎn)的特征。種群規(guī)模N=30，最大迭代次數(shù)Tmax=500。

表1 基準(zhǔn)函數(shù)特征

圖5 Rastrigrin函數(shù)三維圖

引入目標(biāo)函數(shù)的最優(yōu)解、均值和標(biāo)準(zhǔn)方差指標(biāo)對(duì)改進(jìn)算法的尋優(yōu)精度、穩(wěn)定性和魯棒性進(jìn)行分析。由于智能優(yōu)化算法的搜索具有一定隨機(jī)性，為了降低偶然性，在每個(gè)函數(shù)獨(dú)立搜索10次取均值比較。表2是尋優(yōu)結(jié)果。可見，在5種基準(zhǔn)函數(shù)上，TSTSO不僅可以找到最優(yōu)解，而且其均值更接近最優(yōu)解，且更小的標(biāo)準(zhǔn)方差體現(xiàn)出更好穩(wěn)定性。在經(jīng)過相同迭代次數(shù)后，TSO的尋優(yōu)結(jié)果與最優(yōu)解有不同程度偏差，無論均值還是標(biāo)準(zhǔn)方差都不如TSTSO，驗(yàn)證改進(jìn)策略在改善TSO的尋優(yōu)精度和穩(wěn)定性上都起到?jīng)Q定作用。圖6是為Rastrigrin函數(shù)繪制的收斂曲線?？梢姡啾仍妓惴═SO，TSTSO收斂速度更快，且初始迭代得到的目標(biāo)值也更接近最優(yōu)解，這樣可以提高算法的尋優(yōu)效率。

3 自適應(yīng)瞬態(tài)搜索金槍魚優(yōu)化物流無人機(jī)路徑規(guī)劃方法

結(jié)合TSTSO求解物流無人機(jī)路徑規(guī)劃問題，一條金槍魚個(gè)體代表物流無人機(jī)路徑規(guī)劃的一個(gè)候選解，即路徑點(diǎn)位置坐標(biāo)。TSTSO迭代過程中，將以路徑總代價(jià)函數(shù)(9)作為適應(yīng)度函數(shù)，評(píng)估個(gè)體的質(zhì)量。路徑規(guī)劃步驟具體為：

表2 基準(zhǔn)函數(shù)測(cè)試統(tǒng)計(jì)結(jié)果

圖6 Rastrigrin函數(shù)上的收斂曲線

步驟1 初始化TSTSO算法參數(shù)，包括種群規(guī)模N、最大迭代次數(shù)Tmax、代價(jià)函數(shù)的權(quán)重因子w1、w2、w3、路徑點(diǎn)數(shù)量n、路徑長(zhǎng)度約束Lmax、飛行高度約束Hmin、爬升/俯沖角約束φ、飛行偏轉(zhuǎn)角約束θ；

步驟2 建立物流無人機(jī)路徑規(guī)劃約束條件及目標(biāo)代價(jià)函數(shù)。以地面坐標(biāo)系建立三維飛行地形圖，即以O(shè)為原點(diǎn)，以確定的x、y、z范圍建立三維空間，作為無人機(jī)的飛行區(qū)域；設(shè)置樓宇建筑物坐標(biāo)、惡劣天氣坐標(biāo)及禁飛區(qū)域坐標(biāo)及威脅范圍，具體地：樓宇建筑物建模為定高長(zhǎng)方體，惡劣天氣建模為定高圓柱體，禁飛區(qū)域建模為地面某點(diǎn)為圓心的半球體區(qū)域，障礙物威脅范圍即為三類立體圖形的覆蓋范圍；

步驟3 設(shè)置初始迭代t=0，利用Kent混沌映射進(jìn)行種群初始化，生成N條初始路徑規(guī)劃解；

步驟4 根據(jù)式(9)計(jì)算規(guī)劃路徑的適應(yīng)度值，確定種群中的最優(yōu)解Xbest；

步驟5 根據(jù)式(11)更新權(quán)重參數(shù)α1、α2，并更新p；

步驟6 計(jì)算選擇變異概率pr，并利用透鏡成像學(xué)習(xí)或柯西變異的混合擾動(dòng)機(jī)制對(duì)最優(yōu)解變異，并擇優(yōu)保留；

步驟7 生成隨機(jī)量rand1∈[0，1]， 若rand1<0.5，進(jìn)入螺旋覓食階段，并在rand

步驟8 判斷個(gè)體是否越界，若越界，利用式(26)的隨機(jī)回歸方式處理越界個(gè)體；

步驟9 更新迭代次數(shù)t=t+1；

步驟10 判斷算法終止條件，若達(dá)到最大迭代次數(shù)，算法結(jié)束，并輸出無人機(jī)路徑規(guī)劃全局最優(yōu)解；否則，返回步驟4執(zhí)行。

無人機(jī)路徑規(guī)劃算法流程如圖7所示。

圖7 TSTSO算法流程

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)場(chǎng)景及參數(shù)配置

建立表3所示兩種場(chǎng)景物流無人機(jī)飛行環(huán)境對(duì)TSTSO的路徑規(guī)劃性能進(jìn)行實(shí)驗(yàn)評(píng)估。無人機(jī)數(shù)值仿真實(shí)驗(yàn)平臺(tái)為Matlab R2017a。具體地，通過對(duì)三維規(guī)劃空間進(jìn)行立方體網(wǎng)格劃分，將三維空間劃分為彼此相鄰且大小相等的立方體，并根據(jù)所設(shè)置的路徑規(guī)劃點(diǎn)個(gè)數(shù)，在規(guī)劃空間內(nèi)利用改進(jìn)算法TSTSO搜索導(dǎo)航點(diǎn)，生成無人機(jī)的最優(yōu)規(guī)劃路徑。建立飛行區(qū)域?yàn)?00 m×300 m×100 m的三維空間范圍，主要威脅來源為樓宇建筑物、惡劣天氣威脅和禁飛區(qū)域，分別建模為不同高度長(zhǎng)方體、圓柱體和半球體，樓宇建筑物數(shù)量為5/8，惡劣天氣數(shù)量為0/2，禁飛區(qū)域數(shù)量為2/3，具體分布及威脅范圍見表3。無人機(jī)出發(fā)點(diǎn)坐標(biāo)為(0，0，0)，目標(biāo)點(diǎn)為(300，300，0)。設(shè)置最大路徑長(zhǎng)度為700 m，爬升/俯沖最大角約束為30°，最大轉(zhuǎn)彎角約束為60°，飛行勻速為10 m/s，最小飛行高度約束為30 m。TSTSO算法中，種群規(guī)模N=30，最大迭代次數(shù)Tmax=500，衰減因子初值z(mì)ini=2，終值z(mì)fin=0，路徑規(guī)劃點(diǎn)數(shù)設(shè)置為n=6，路徑總代價(jià)函數(shù)(適應(yīng)度)的權(quán)重因子w1=0.4，w2=0.3，w3=0.3。選擇標(biāo)準(zhǔn)TSO算法[15]、混沌精英反向?qū)W習(xí)改進(jìn)麻雀搜索算法CLSSA[10]以及改進(jìn)金槍魚算法ITSO[17]進(jìn)行性能縱橫向?qū)Ρ?，?duì)比算法的參數(shù)與原文獻(xiàn)保持一致。同時(shí)，由于智能優(yōu)化算法的搜索過程都具有一定的隨機(jī)性，為了降低偶然隨機(jī)性的干擾，每種算法的搜索過程均進(jìn)行10次，并統(tǒng)計(jì)出路徑規(guī)劃的最優(yōu)解、平均值及標(biāo)準(zhǔn)差指標(biāo)。

表3 威脅類型及分布

4.2 實(shí)驗(yàn)結(jié)果

圖8、圖9是在兩種場(chǎng)景中算法規(guī)劃出的物流無人機(jī)飛行路徑三維圖及二維俯視圖。顯然，簡(jiǎn)單場(chǎng)景中TSTSO規(guī)劃的路徑是最短的。以下重點(diǎn)分析復(fù)雜場(chǎng)景中的路徑規(guī)劃結(jié)果。從圖9(a)可見，在這種威脅分布密集的場(chǎng)景下，算法所規(guī)劃的路徑依然能有效避開建筑物、惡劣天氣和禁飛區(qū)域的威脅，保證物流無人機(jī)配送任務(wù)的順利完成。但各自飛行線路也具有較明顯的差異。TSO的規(guī)劃路徑具有一定程度的方向偏離，飛行線路較長(zhǎng)，且路徑具有明顯的大幅彎折，平滑性不足。ITSO和CLSSA的路徑長(zhǎng)度要短于TSO，從起點(diǎn)出發(fā)后沒有繞行，但在靠近目標(biāo)點(diǎn)處的禁飛區(qū)域時(shí)通過一定程度的爬升避開了禁飛區(qū)，路徑規(guī)劃代價(jià)高于本文算法。TSTSO規(guī)劃出的路徑，從起點(diǎn)出發(fā)后與目標(biāo)點(diǎn)保持了更一致的飛行方向，路徑長(zhǎng)度最短，且沒有明顯的較大轉(zhuǎn)角，路徑平滑性更佳，說明找到的是直接路徑，這證明自適應(yīng)瞬態(tài)搜索機(jī)制能夠防止算法迭代后期因多樣性逐步貧化而陷入局部最優(yōu)，提高了找到全局最優(yōu)解的概率。圖9(b)所示二維俯視路徑規(guī)劃圖中能夠更清晰展示規(guī)劃路徑與三類威脅障礙物之間的關(guān)系，TSTSO能夠避讓前期的所有障礙物，并越過了目標(biāo)點(diǎn)附近的禁飛區(qū)域抵達(dá)終點(diǎn)。

圖8 簡(jiǎn)單場(chǎng)景無人機(jī)路徑規(guī)劃結(jié)果

圖9 復(fù)雜場(chǎng)景無人機(jī)路徑規(guī)劃結(jié)果

表4是算法的路徑規(guī)劃總代價(jià)和路徑長(zhǎng)度相關(guān)統(tǒng)計(jì)結(jié)果。在平均路徑長(zhǎng)度上，TSTSO分別比ITSO、CLSSA和TSO減小了11.81%、17.36%和29.49%，在路徑規(guī)劃的平均總代價(jià)上，TSTSO分別比ITSO、CLSSA和TSO降低了17.63、24.92%和36.80%。此外，在代價(jià)標(biāo)準(zhǔn)差值上，TSTSO也得到了最小值，表明算法在這種復(fù)雜的飛行環(huán)境中也能夠?yàn)槲锪鳠o人機(jī)穩(wěn)定地規(guī)劃出最優(yōu)安全路徑。

表4 統(tǒng)計(jì)結(jié)果

圖10是算法的收斂曲線。在收斂速度上，TSO和CLSSA要略快于ITSO和TSTSO，但是TSO和CLSSA處于收斂處的路徑規(guī)劃總代價(jià)更高，算法陷入階段性局部最優(yōu)，無法拓展搜索空間。ITSO和TSTSO的收斂速度略慢，但其路徑總代價(jià)更小。TSTSO在約76次迭代處于收斂，且路徑總代價(jià)是最小的，驗(yàn)證算法有效性。此外，從迭代初始期的路徑代價(jià)看，TSTSO在迭代初期的規(guī)劃代價(jià)要明顯小于對(duì)比算法，驗(yàn)證其生成的初始種群質(zhì)量更好，向最優(yōu)解進(jìn)化更快，能夠在適應(yīng)度更優(yōu)的個(gè)體間進(jìn)行尋優(yōu)進(jìn)化，在解空間內(nèi)能夠快速逼近全局最優(yōu)解的鄰域，增大全局最優(yōu)解的搜索效率。

圖10 算法收斂性

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

本文設(shè)計(jì)了一種瞬態(tài)搜索改進(jìn)金槍魚優(yōu)化算法求解城市環(huán)境物流無人機(jī)路徑規(guī)劃問題。為了避免路徑規(guī)劃收斂于局部最優(yōu)，設(shè)計(jì)了Kent混沌初始化、自適應(yīng)瞬態(tài)搜索及透鏡成像對(duì)立學(xué)習(xí)和柯西變異混合擾動(dòng)防止算法陷入局部最優(yōu)。結(jié)合飛行環(huán)境建模與路徑規(guī)劃約束條件，利用改進(jìn)算法對(duì)物流無人機(jī)路徑規(guī)劃多目標(biāo)代價(jià)函數(shù)進(jìn)行求解。結(jié)果表明，在復(fù)雜的城市物流環(huán)境中，改進(jìn)算法能夠避開所有類型障礙物威脅，并得到最小的路徑規(guī)劃代價(jià)。