改進SSA在三維路徑規劃中的應用*

宋立業， 胡朋舉

(遼寧工程技術大學 電氣與控制工程學院，遼寧 葫蘆島 125105)

0 引 言

隨著工業自動化技術的不斷發展進步，利用無人機(UAV)對復雜山區電力設備的巡檢技術已經成為電網電力設備巡檢技術的發展趨勢。雖然無人機電力設備巡檢技術能夠節省大量的人力以及物力，但該技術在發展應用過程中還存在不少亟需解決的問題，最優路徑規劃問題便是其中之一。針對路徑規劃問題，國內外研究較多的是采用如蟻群算法、人工勢場算法以及A*搜索算法等智能優化算法對最優路徑進行求解計算[1,2]，這些算法雖然能夠有效對最優路徑進行求解，但普遍存在易早熟、迭代收斂速度低以及求解精度低的問題。

針對上述問題，為了提高算法在對三維路徑規劃中的求解精度以及速度，本文提出了一種基于改進麻雀搜索算法(improved sparrow search algorithm，ISSA)的三維路徑規劃方法，該方法通過采用Tent映射對原始麻雀搜索算法(sparrow search algorithm，SSA)進行不斷全局擾動，減小了算法陷入局部解的可能，同時通過對探索因子進行改進計算，使算法的全局搜索以及局部搜索能力得以提高。本文最后通過實驗計算對基于ISSA的三維路徑規劃方法進行了有效性驗證。

1 三維地形建模

現實中的地形是連續的，而計算機與無人機控制器都只能處理離散化的數據，因而針對現實中的三維地形離散化建模方法，目前應用較多的有切線圖法、可視圖法、單元樹法以及柵格化的方法[3]。本文采用的是將三維地形進行柵格化處理的方法，建立橫縱與高度三維坐標。本文給出現實中采集的某地地形數據，然后建立一個11×11的網格化地形圖具體如圖1所示。

圖1 仿真實驗地形

2 ISSA路徑規劃方法建模

首先對SSA進行建模，SSA是一種模仿麻雀群體覓食行為而提出的一種優化算法，這種算法與傳統群體算法最大的不同是將種群分成了兩個類別，即探索者以及追隨者，同時還存在預警機制。對于SSA的具體建模過程如下：

有N個個體、D維的SSA其個體可初始化為Xi=(xi1…xii…xiD)，那么其群體即可表示為X=(X1…Xi…XN)，由于算法參考了PSO算法的群體機制，因而對于當前個體最優位置可用Pi=(Pi1…Pii…PiD)表示，那么群體當前最優位置便可表示為Pg=(Pg1…Pgi…PgN)。首先對于SSA中探索者的更新方式如式(1)所示

(1)

式中R與α為服從均勻分布的[0,1]區間的數，Tmax為最大迭代次數，Q為服從標準正態分布的數，L為單位向量，具體維數為D，ST為預警值，一般設置為0.5～1之間的某個數字。由式(1)可以看出，當R小于ST時，粒子將繼續對該位置進行搜索，反之，則飛向其他位置進行搜索，這種搜索機制提高了算法的全局與局部搜索能力。對于粒子中追隨者的計算更新方式如式(2)所示

(2)

式中xworse(t)與xbest(t)分別為目前最差與最好的位置，而A+則按式(3)進行計算

A+=AT(AAT)-1

(3)

由式(2)可以看出，當滿足i>n/2時，表示當前位置非常差，因而需要跳出當前位置而飛向其他位置，反之，則繼續跟隨探索者，同時在這一步追隨者有可能成為新的探索者，這種搜索機制有效地提高了算法的迭代速度。

在粒子進行搜索過程中，還存在著預警機制，即設置部分粒子進行預警，具體預警粒子更新方式如式(4)所示

(4)

式中β為粒子步長控制參數，k為服從均勻分布的[-1,1]區間的數，ε為避免分母為零而設置的極小數。由式(4)可以看出，若粒子當前位置劣于全局最優位置時，表明粒子當前處于邊緣，此時粒子將會向最優位置移動，而當粒子當前位置等于全局最優位置時，表明粒子當前位置存在危險，從而向其他位置移動，這種搜索機制表明，即使粒子當前處于最優位置也有可能發生移動，有利于抑制算法陷入局部解。

原始的SSA在計算過程中，其控制探索者所占的比例的探索因數是固定的，這種機制不利于算法的全局搜索，針對這個問題，本文提出了一種所迭代變化的探索因數更新方法，即如式(5)所示

(5)

由式(5)可以看出此時探索因數不在固定，在算法開始迭代時，探索因數較大，此時探索者數目也會較大，利于算法的全局搜索，而隨著迭代的進行，探索者的數目是逐漸減少的，利于算法的局部搜索。

另外為了能夠減小算法陷入局部解的概率，本文提出在算法進行迭代計算過程中利用式(6)所示的Tent映射對當前搜索結果進行不斷擾動的方法[4]

(6)

式中μ為映射控制參數，取值范圍為(0,2]，該值越大，混沌映射效果越好，q(t)為當前映射結果，其初始值取值范圍為[0,1]。選取D個具有微小差異的初值后，最后按式(7)將映射結果映射至算法搜索范圍

xij=lb+(ub-lb)·qj(t)

(7)

式中lb與ub分別為算法搜索的上下限，本文取1與21。

對于ISSA的具體流程圖如圖2所示。

圖2 ISSA流程

對于評價函數本文首先參考無人機下一步飛行路徑長度作為標準，具體計算如式(8)所示，即所求解的函數值越小表示路徑規劃效果越好[5～7]

(8)

對于路徑規劃，另外還需要考慮飛行過程中的障礙物，因而文中考慮在評價函數中加入無人機飛行過程中所遇障礙物危險程度來作為整體路徑規劃評價函數具體如式(9)所示

D=∑[1/fi+abs(hi/Hi)]

(9)

式中fi為無人機與所處地點處的障礙物距離，Hi為當前當前無人機所處高度，hi為所躲避當前障礙上行或下行的高度。綜上，文中所建立的評價函數如式(10)所示

fitness=L+D

(10)

3 方法實驗驗證

為了驗證ISSA在三維路徑規劃中的有效性以及優越性，本文給出了利用PSO算法、SSA以及ISSA分別進行20次計算的三維路徑規劃結果。對于PSO算法，設置其慣性因子w為0.9,c1與c2均為1.2種群個數為50；設置SSA，探索因子為0.2，ST為0.8，預警粒子比例為0.2，種群個數為50；設置ISSA，初始探索因子為0.4，映射控制參數為2，其他參數與SSA相同，上述算法均迭代運行500次。

3.1 地形1運行實驗結果分析

利用上述參數對地形1進行路徑規劃的迭代結果如圖3所示，規劃運行結果的平視圖、三維視圖以及俯視圖如圖4所示。

圖3 地形1運行迭代曲線

圖4 地形1路徑規劃結果

利用PSO算法、SSA以及ISSA計算得到的50次平均路徑規劃距離分別為115.35,99.82,95.17，平均運行時間分別為1.115,0.827,1.017 s。所以由實驗計算結果可以看出,本文所提算法具有在保證求解時間較低的前提下求解精度高的優勢，另外由由圖3所示的迭代結果可清楚的顯示，本文所提算法具有迭代收斂速度快的優勢。通過圖4所示的路徑規劃結果可以顯示ISSA路徑規劃結果的合理性。

3.2 地形2運行實驗結果分析

為了驗證算法的普適性，本文給出了利用上述三種算法在未改變參數設置的前提下對于地形2的路徑規劃結果如圖5以及圖6所示。

圖5 地形2迭代曲線

圖6 地形2路徑規劃結果

由圖5與圖6所示的計算結果結合3.1節的驗證可以得出，本文所提基于ISSA的三維路徑規劃方法能夠適用于各種三維路徑規劃問題，而且該方法收斂速度快，求解精度高，求解結果合理，由此，可以得出文中所提方法對于求解實際的三維路徑規劃問題具有非常深遠的應用前景。

4 結 論

針對我國電力無人機在復雜山地巡檢的路徑規劃問題，本文提出了一種基于ISSA的三維路徑規劃方法。本文利用變探索因子計算提高了算法全局與局部搜索能力；利用Tent映射提高了算法的搜索范圍，改善了傳統優化算法普遍存在的易早熟問題，本文通過利用所提方法對實際數據采集的兩類山地地形進行路徑規劃，驗證了算法的有效性與普適性。