改進SSA在三維路徑規(guī)劃中的應(yīng)用*

宋立業(yè)， 胡朋舉

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

0 引 言

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

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

1 三維地形建模

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

圖1 仿真實驗地形

2 ISSA路徑規(guī)劃方法建模

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

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

(1)

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

(2)

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

A+=AT(AAT)-1

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

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

(7)

式中l(wèi)b與ub分別為算法搜索的上下限，本文取1與21。

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

圖2 ISSA流程

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

(8)

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

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

(9)

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

fitness=L+D

(10)

3 方法實驗驗證

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

3.1 地形1運行實驗結(jié)果分析

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

圖3 地形1運行迭代曲線

圖4 地形1路徑規(guī)劃結(jié)果

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

3.2 地形2運行實驗結(jié)果分析

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

圖5 地形2迭代曲線

圖6 地形2路徑規(guī)劃結(jié)果

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

4 結(jié) 論

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