瞬態搜索金槍魚優化城市物流無人機路徑規劃

謝繼武，席建新

(1.內蒙古師范大學 國際設計學院，內蒙古 呼和浩特 010010；2.內蒙古師范大學 設計與社會創新內蒙古高校人文社科重點研究基地，內蒙古 呼和浩特 010010； 3.內蒙古自治區科技創新發展中心，內蒙古 呼和浩特 010010)

0 引 言

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

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

1 城市物流無人機路徑規劃建模

1.1 飛行環境建模

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

圖1 城市物流無人機飛行環境建模

1.2 飛行約束條件

1.2.1 最大路徑長度約束

令路徑規劃點(即導航點)數量為n，可飛行的最大路徑長度為Lmax，第i段路徑的長度為Li，則無人機路徑規劃總長及需滿足的約束條件為

(1)

1.2.2 飛行高度約束

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

Hi≥Hmin

(2)

1.2.3 爬升/俯沖角約束

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

(3)

式中：(xi，yi，zi)、 (xj，yj，zj) 對應無人機位置的兩個路徑點坐標。

1.2.4 轉彎角約束

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

(4)

圖2 轉彎角

1.3 飛行代價函數

定義飛行代價函數評估物流無人機規劃路徑質量，主要考慮路徑長度、飛行高度以及飛行偏轉角大小3個代價。

1.3.1 路徑長度代價

對于物流無人機而言，配送路徑長度最短，可以得到更少的耗時和節省更多的能耗。將路徑長度代價定義為

(5)

1.3.2 飛行高度代價

對于物流無人機而言，實現穩定高度飛行有助于減小飛行器的系統負載，節省能耗。飛行高度應在滿足高度約束的同時，盡量不發生大幅波動。將飛行高度代價定義為

(6)

1.3.3 飛行偏轉角代價

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

(7)

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

(8)

1.3.4 總代價函數

綜合考慮以上3個代價定義物流無人機總代價函數為

Ccost=w1Clenght+w2Cheight+w3Csmooth

(9)

(10)

其中，w1、w2和w3分別對應路徑長度、飛行高度以及飛行偏轉角大小3個代價的權重因子。

2 自適應瞬態搜索金槍魚優化算法TSTSO

2.1 標準TSO算法

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

(11)

其中，N為種群規模，t為當前迭代次數，Tmax為最大迭代次數，rand∈[0，1]，Xrand(t)、Xbest(t) 為迭代t時選擇的隨機個體和最優個體，Xi(t)、Xi(t+1) 為迭代t時的個體位置和更新位置，α1、α2為個體向隨機個體和最優個體移動的權重

(12)

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

(13)

式中：b∈[0，1] 為隨機量。

拋物線覓食時種群個體的位置更新方式為

(14)

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

2.2 自適應瞬態搜索改進金槍魚優化算法TSTSO設計

2.2.1 Kent混沌種群初始化

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

(15)

式中：a為混沌系數，a=0.5時，混沌系統呈現短周期狀態。結合式(15)生成的Kent混沌序列值，將其映射至搜索空間內生成金槍魚個體的初始位置，映射公式為

x=xmin+y×(xmax-xmin)

(16)

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

令種群規模為50，圖3是隨機初始化和混沌Kent初始化生成的個體分布。隨機初始化容易產生個體重疊和區域空白未搜索的缺點，Kent混沌初始化種群結構均勻性更優，對整個區間可以全面遍歷。

圖3 兩種種群初始化分布

2.2.2 自適應瞬態搜索

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

(17)

式中：r1為[0，1]內隨機值，T、C1為兩個瞬態系數，定義為

(18)

式中：r2、r3均為[0，1]內隨機值，k為自然數常量，z為瞬態系數衰減因子。瞬態搜索以T∈[-2，2] 實現全局搜索與局部開發的線性轉換。T<0時，瞬態搜索振幅更大，能以更廣泛的空間遍歷性搜索最優解，提升全局搜索能力；T>0時，瞬態搜索會逐漸趨于穩態，精細開發逼近最優解。同時，為了全局搜索與局部開發的有效均衡，對瞬態系數衰減進行非線性自適應調整為

(19)

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

2.2.3 透鏡成像對立學習和柯西變異

對于TSO算法，目標位置的更新取決于迭代中種群位置的更新，該過程會選擇每次迭代中適應度最優解替換前代最優個體，但算法沒有考慮目標個體陷入局部最優的情況。為此，TSTSO引入透鏡成像對立學習與柯西變異的混合擾動機制對目標個體位置擾動，降低局部最優的概率。

對立學習可以通過生成候選個體對立點的方式得到適應度更好的種群，通過這種方式擴展種群搜索范圍。

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

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

(20)

(21)

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

(22)

當k=1時，透鏡成像學習模型為標準對立學習模型。通過調整k，透鏡成像對立學習可以動態搜索個體對立點，以此逼近最優目標位置。

圖4 透鏡成像對立學習模型

柯西分布是一種數學期望不存在的連續性概率分布，其概率密度函數為

(23)

柯西分布變異步長比高斯分布范圍更廣。將在目標位置更新中引入柯西算子對位置進行動態調節，能提高算法跳離局部最優解的概率。其變異方式為

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

(24)

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

透鏡成像對立學習與柯西分布有不同能力的擾動幅度，為了提高TSO的搜索性能，TSTSO定義動態選擇變異概率pr更新目標位置，在pr下以隨機量rand與之對比，交替選擇執行透鏡成像對立學習或柯西變異。選擇概率為

(25)

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

2.2.4 越界處理

當個體搜索超過范圍時，TSO以搜索范圍的邊界替換越界位置，這種處理方式具有盲目性，沒有充分利用越界個體的有效信息。引入一種隨機回歸進行個體越界處理，具體為

(26)

式中：γ為[0，1]內隨機值，[lb，ub]為搜索邊界。

2.2.5 TSTSO算法性能驗證

利用5個基準函數對TSO改進前后的性能測試分析，表1給出基準函數特征。選取基準函數Rastrigrin作出三維圖，展示函數特征，如圖5所示。可見，函數是明顯多峰值函數，具有密集的波峰波谷起伏，存在較多局部極值點，極其考驗算法搜索全局最優解的能力。其它4個基準函數也均具備多局部極值點的特征。種群規模N=30，最大迭代次數Tmax=500。

表1 基準函數特征

圖5 Rastrigrin函數三維圖

引入目標函數的最優解、均值和標準方差指標對改進算法的尋優精度、穩定性和魯棒性進行分析。由于智能優化算法的搜索具有一定隨機性，為了降低偶然性，在每個函數獨立搜索10次取均值比較。表2是尋優結果。可見，在5種基準函數上，TSTSO不僅可以找到最優解，而且其均值更接近最優解，且更小的標準方差體現出更好穩定性。在經過相同迭代次數后，TSO的尋優結果與最優解有不同程度偏差，無論均值還是標準方差都不如TSTSO，驗證改進策略在改善TSO的尋優精度和穩定性上都起到決定作用。圖6是為Rastrigrin函數繪制的收斂曲線。可見，相比原始算法TSO，TSTSO收斂速度更快，且初始迭代得到的目標值也更接近最優解，這樣可以提高算法的尋優效率。

3 自適應瞬態搜索金槍魚優化物流無人機路徑規劃方法

結合TSTSO求解物流無人機路徑規劃問題，一條金槍魚個體代表物流無人機路徑規劃的一個候選解，即路徑點位置坐標。TSTSO迭代過程中，將以路徑總代價函數(9)作為適應度函數，評估個體的質量。路徑規劃步驟具體為：

表2 基準函數測試統計結果

圖6 Rastrigrin函數上的收斂曲線

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

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

步驟3 設置初始迭代t=0，利用Kent混沌映射進行種群初始化，生成N條初始路徑規劃解；

步驟4 根據式(9)計算規劃路徑的適應度值，確定種群中的最優解Xbest；

步驟5 根據式(11)更新權重參數α1、α2，并更新p；

步驟6 計算選擇變異概率pr，并利用透鏡成像學習或柯西變異的混合擾動機制對最優解變異，并擇優保留；

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

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

步驟9 更新迭代次數t=t+1；

步驟10 判斷算法終止條件，若達到最大迭代次數，算法結束，并輸出無人機路徑規劃全局最優解；否則，返回步驟4執行。

無人機路徑規劃算法流程如圖7所示。

圖7 TSTSO算法流程

4 實驗分析

4.1 實驗場景及參數配置

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

表3 威脅類型及分布

4.2 實驗結果

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

圖8 簡單場景無人機路徑規劃結果

圖9 復雜場景無人機路徑規劃結果

表4是算法的路徑規劃總代價和路徑長度相關統計結果。在平均路徑長度上，TSTSO分別比ITSO、CLSSA和TSO減小了11.81%、17.36%和29.49%，在路徑規劃的平均總代價上，TSTSO分別比ITSO、CLSSA和TSO降低了17.63、24.92%和36.80%。此外，在代價標準差值上，TSTSO也得到了最小值，表明算法在這種復雜的飛行環境中也能夠為物流無人機穩定地規劃出最優安全路徑。

表4 統計結果

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

圖10 算法收斂性

5 結束語

本文設計了一種瞬態搜索改進金槍魚優化算法求解城市環境物流無人機路徑規劃問題。為了避免路徑規劃收斂于局部最優，設計了Kent混沌初始化、自適應瞬態搜索及透鏡成像對立學習和柯西變異混合擾動防止算法陷入局部最優。結合飛行環境建模與路徑規劃約束條件，利用改進算法對物流無人機路徑規劃多目標代價函數進行求解。結果表明，在復雜的城市物流環境中，改進算法能夠避開所有類型障礙物威脅，并得到最小的路徑規劃代價。