改進(jìn)PSO 算法及其無(wú)人機(jī)電力巡線規(guī)劃應(yīng)用

楊輕，楊忠，許昌亮，徐浩，韓家明

1.南京航空航天大學(xué)自動(dòng)化學(xué)院，江蘇南京211106 2.先進(jìn)飛行器導(dǎo)航、控制與健康管理工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室(南京航空航天大學(xué))，江蘇南京211106

由于我國(guó)國(guó)土遼闊、地形多樣，為滿足供電需求，輸電線路需要延伸到社會(huì)生活的各個(gè)角落。因此，面對(duì)日益復(fù)雜的輸電網(wǎng)絡(luò)，電力巡線工作也面臨著越來越嚴(yán)峻的考驗(yàn)[1]。通常，電力巡線采用固定設(shè)備巡檢、爬線機(jī)器人巡檢以及飛行器（固定翼和直升機(jī)）巡檢，但是上述巡檢方式存在監(jiān)控范圍小、維護(hù)復(fù)雜以及使用成本高等各種缺陷和問題[2]。近年來，隨著多旋翼無(wú)人機(jī)相關(guān)技術(shù)的不斷成熟，其逐漸被應(yīng)用到輸電線路巡檢領(lǐng)域之中[3]。但是，現(xiàn)有的應(yīng)用方式僅限于巡檢人員手動(dòng)遙控方式進(jìn)行巡線，不能使其根據(jù)任務(wù)需求自動(dòng)或者自主執(zhí)行巡檢任務(wù)，這就要求巡檢人員具備操作手技能，并且大大提高了應(yīng)用難度和使用成本。

多旋翼飛行器自動(dòng)或者自主執(zhí)行巡檢任務(wù)的基礎(chǔ)之一在于匹配高效的路徑規(guī)劃算法。當(dāng)前，對(duì)于路徑規(guī)劃算法研究比較有代表性的有：文獻(xiàn)[4]通過設(shè)置評(píng)估函數(shù)，在搜索速度和精度之間保持了相對(duì)平衡，可以獲得時(shí)間最優(yōu)路徑；文獻(xiàn)[5]提出篩選調(diào)點(diǎn)的新型A*算法，其運(yùn)用調(diào)點(diǎn)替換原算法中大量無(wú)用節(jié)點(diǎn)，從而解決了算法中資源消耗大的缺陷；文獻(xiàn)[6]在蟻群算法中引入動(dòng)態(tài)搜索算子策略，并著重設(shè)計(jì)了搜索模型，從而提高了算法精度，加快了收斂速度；文獻(xiàn)[7]提出了一種混合算法，其中蟻群優(yōu)化算法用于尋找最快路徑和跳出局部最小值，遺傳算法用于搜索最重要的路徑；文獻(xiàn)[8]、[9]提出了一種快速的兩階段蟻群算法，其基本思想是將信息素傳播到整個(gè)地圖上，并在此基礎(chǔ)上進(jìn)行螞蟻路徑規(guī)劃；文獻(xiàn)[10]提出了一種混合元啟發(fā)式?粒子群優(yōu)化算法（particle swarm optimization,PSO），以避免過早收斂和時(shí)間復(fù)雜性。為解決路徑規(guī)劃中的多目標(biāo)優(yōu)化問題；文獻(xiàn)[11]引入了局部最優(yōu)準(zhǔn)則和速度擾動(dòng)；文獻(xiàn)[12]通過結(jié)合蟻群算法和粒子群算法可以解決中動(dòng)態(tài)環(huán)境中的路徑規(guī)劃問題；文獻(xiàn)[13]提出了一種改進(jìn)的交叉算子，用遺傳算法求解靜態(tài)環(huán)境下的路徑規(guī)劃問題，并對(duì)路徑長(zhǎng)度、安全性等指標(biāo)進(jìn)行了優(yōu)化；文獻(xiàn)[14]在路徑規(guī)劃過程中，運(yùn)用遺傳算法中的一些概念實(shí)現(xiàn)了狼群搜索算法，并引入遺傳算法中的交叉和變異算子，對(duì)原狼群搜索算法進(jìn)行了改進(jìn)；文獻(xiàn)[15]提出了一種全新的方案，該方案采用基于改進(jìn)概率路標(biāo)法的碰撞避免路徑規(guī)劃與基于改進(jìn)遺傳算法的傳遞序列優(yōu)化相結(jié)合的方法來解決非共面輻射治療中的問題。

1 粒子群算法

粒子群算法依靠不同粒子的相互作用尋找相關(guān)問題的在整個(gè)尋優(yōu)空間中的最優(yōu)位置，也即問題的最優(yōu)解。在粒子群算法中，每個(gè)待解決的優(yōu)化問題的可能解都被視為搜索空間中存在的一個(gè)粒子。粒子群中的所有粒子都被賦予一個(gè)由被優(yōu)化的函數(shù)確定的適應(yīng)度值(fitness value)，每個(gè)粒子具有2個(gè)屬性，即速度與位置。算法運(yùn)行過程中，所有粒子趨向當(dāng)前時(shí)刻的最優(yōu)粒子的位置，并試圖在可能空間中搜索全局最優(yōu)解。

在一個(gè) m維搜索空間中，粒子總數(shù)為n，其中第i個(gè)粒子可以表示為：

在 t+1時(shí)刻，所有粒子均遵循式（1）和（2）更新自身參數(shù)，以在搜索空間內(nèi)尋找該問題的最優(yōu)解。

式中：ω為慣性權(quán)重系數(shù)，描述上一時(shí)刻速度的保留程度，該參數(shù)用于調(diào)整算法局部與全局搜索能力，通常初期選擇較大的值，以增強(qiáng)其全局搜索能力，中后期選擇相對(duì)較小的值，以使得算法能夠快速收斂于全局最優(yōu)；c1、c2均為學(xué)習(xí)因子，分別描述算法的自我學(xué)習(xí)與社會(huì)學(xué)習(xí)能力；vi表示全體粒子的速度，且滿足vi∈[?vmax,vmax]，vmax為設(shè)定的粒子運(yùn)行速度極值；r1、r2為介于[0,1]之間的隨機(jī)數(shù)。

2 改進(jìn)措施

2.1 自適應(yīng)慣性權(quán)重

粒子群算法是一種比較優(yōu)秀的群體優(yōu)化算法，但算法本身的全局搜索能力和局部搜索能力并不平衡，且容易出現(xiàn)陷入局部最優(yōu)的早熟現(xiàn)象。針對(duì)算法本身的固有缺點(diǎn)，將通過引入帶有自適應(yīng)因子的策略的粒子群算法（improved particle swarm optimization with adaptive factor strategy,IPSOAF），對(duì)上述問題和缺陷進(jìn)行改進(jìn)。

在粒子群算法中，學(xué)習(xí)因子 c1和 c2描述各個(gè)粒子自身學(xué)習(xí)和他人學(xué)習(xí)對(duì)粒子運(yùn)動(dòng)方向的影響，其反映各個(gè)粒子之間的信息共享程度。在 c1取值較大時(shí)，會(huì)導(dǎo)致粒子大量聚集在局部?jī)?yōu)勢(shì)區(qū)域；在 c2取值較小時(shí)，則會(huì)致使粒子過早收斂于局部最小值，陷入局部最優(yōu)。因此，引入自適應(yīng)因子，通過選取合適的參數(shù)，可以平衡算法全局搜索和局部搜索的能力，并確保算法本身的收斂性。

通過引入自適應(yīng)因子：

式中： ωs和 ωe分別為初始慣性權(quán)重和結(jié)束慣性權(quán)為最大迭代數(shù)，t為當(dāng)前代數(shù)。

2.2 學(xué)習(xí)因子調(diào)整

同時(shí)，為了在算法初期增強(qiáng)全局搜索能力，并且后期增強(qiáng)局部搜索能力，將加速系數(shù) c1和 c2表示為：

2.3 驅(qū)散策略

根據(jù)粒子群算法的工作原理，所有粒子逐漸趨向于個(gè)體最優(yōu)和全局最優(yōu)共同影響的位置。當(dāng)一個(gè)粒子取得全局最優(yōu)時(shí)，其他的粒子會(huì)很大程度上趨向此位置，如果此位置為全局極值，那么算法終止并可以獲得問題的最優(yōu)解；但如果此位置不是全局極值，且其余粒子也未能發(fā)現(xiàn)更優(yōu)解，那么就可能導(dǎo)致大量的粒子群集在該位置附近，無(wú)法跳出這個(gè)區(qū)域，從而使得算法陷入局部最優(yōu)。假如在粒子群逐漸趨于局部極小的過程中，算法能夠及時(shí)地把這些粒子按一定比例驅(qū)散到更大的范圍內(nèi)，在一定程度上進(jìn)行重新搜索，將可以避免算法的早熟現(xiàn)象，最終趨向全局最優(yōu)。因此，在此引入一個(gè)驅(qū)散策略，在粒子分布過于密集的位置，引入驅(qū)散操作，以增強(qiáng)算法的搜索能力。

式中： xmax、 xmin分別表示分子聚集范圍內(nèi)距當(dāng)前最優(yōu)分子的最大距離和最小距離。

如果某個(gè)粒子與當(dāng)前最優(yōu)位置的距離大于cg，則表明此粒子暫時(shí)沒有趨于局部最優(yōu)的風(fēng)險(xiǎn)，不必進(jìn)行驅(qū)散操作。cg的選擇影響算法的驅(qū)散效果，若取值過大，會(huì)導(dǎo)致算法收斂速度下降；若取值過小，則驅(qū)散效果變差，不利于跳出局部極小。

2.4 改進(jìn)算法步驟

通過以上改進(jìn)，自適應(yīng)收縮因子的混合粒子群算法的基本步驟如下：

1）在隨機(jī)產(chǎn)生預(yù)設(shè)數(shù)量的粒子，并對(duì)全體粒子的參數(shù)進(jìn)行初始化；

3） 更 新 w 、 c1和 c2；

4）判斷算法結(jié)束條件是被否滿足，若滿足，則運(yùn)行結(jié)束；若不滿足，則繼續(xù)運(yùn)行；

5）判斷是否滿足驅(qū)散操作條件，若滿足，則轉(zhuǎn)向步驟5）；若不滿足，則轉(zhuǎn)向步驟6）；

6）根據(jù)公式（1）和（2）更新速度和位置，更新全體粒子的實(shí)時(shí)參數(shù)，然后執(zhí)行步驟2）。

3 算例

為了完整地測(cè)試新算法的性能，選擇5個(gè)典型的智能優(yōu)化算法測(cè)試函數(shù)[16]。

1）Schaffer函數(shù)：

2）Griewank函數(shù)：

式中 xi∈[?600,600]。該函數(shù)包含眾多的極值，且這些極值變化范圍很小，函數(shù)在(x1,x2,···,xn)=(0,0,···,0)處獲得全局最小，智能算法對(duì)其優(yōu)化比較困難。

3）Rosenbrock函數(shù)：

式中 xi∈[?2.048,2.048]。該函數(shù)的全局最優(yōu)處于類似窄長(zhǎng)的拋物線波谷，且函數(shù)本身不能表現(xiàn)出較多的有效信息，使得優(yōu)化算法不容易確定搜索的方向，為尋找最優(yōu)解制造很大障礙。

4）Rastrigrin函數(shù)：

式中， xi∈[?5.12,5.12]。該函數(shù)為一個(gè)多峰值函數(shù)，其在 (x1,x2,···,xn)=(0,0,···,0)處能夠獲得全局最小值，且在 x 的定義域范圍內(nèi)存在約1 0n個(gè)局部極小值點(diǎn)。作為一種多模態(tài)函數(shù)，其峰值沒有規(guī)律可循，且總是跳躍性的呈現(xiàn)，因此搜索函數(shù)的全局最優(yōu)值往往具有較大的難度。

5）Shubert函數(shù)：

式中 ?10?x,y?10。該函數(shù)為一個(gè)復(fù)雜的二維函數(shù)，定義域范圍內(nèi)存在760個(gè)局部極值點(diǎn)，全局最小值為?186.7309，在 (?1.42513,0.80032)取得。通過表1中的測(cè)試數(shù)據(jù)（測(cè)試精度、平均最優(yōu)值、成功次數(shù)）可以得出：1）在平均最優(yōu)值方面，IPSOAF算法明顯優(yōu)于原PSO算法10的負(fù)十幾次方，具有明顯優(yōu)化優(yōu)勢(shì)；2）在運(yùn)行時(shí)間方面，IPSOAF算法耗時(shí)僅為PSO算法耗時(shí)的幾分之一，具有更高的優(yōu)化效率；3）在成功率方面，IPSOAF算法實(shí)現(xiàn)整體接近100%的成功率，更是優(yōu)于原PSO算法。

表1 2種不同類型反應(yīng)算法針對(duì)不同測(cè)試函數(shù)的優(yōu)化測(cè)試結(jié)果

4 仿真

高壓輸電線路的多旋翼無(wú)人機(jī)巡檢需要面對(duì)的環(huán)境非常復(fù)雜和多樣，此處引用文獻(xiàn)[17]中的柱狀空間建模法，同時(shí)對(duì)電力線路運(yùn)行環(huán)境進(jìn)行簡(jiǎn)化。以110kV架空線路為例，采用上字型鐵塔，導(dǎo)線為三角排列布置，采用經(jīng)濟(jì)呼稱高度（呼高）18m，水平檔距取250m（為便于展示仿真細(xì)節(jié)，此處仿真取值40m左右），電氣安全距離為5m，絕緣子為8片。多旋翼無(wú)人機(jī)采用四旋翼無(wú)人機(jī)，主要性能如下：最大巡航速度5m/s，最大續(xù)航時(shí)間30min，滾轉(zhuǎn)角和俯仰角范圍為±45°，偏航角范圍為±180°，滾轉(zhuǎn)角速率和俯仰角速率為0~80°/s，偏航角速率為0~20°/s，有效載荷2.5kg，攝像頭為主要巡檢傳感器。

4.1 預(yù)先劃定興趣點(diǎn)的情況

為了便于分析仿真效果，在此采用俯視的二維地圖進(jìn)行仿真分析。

在預(yù)設(shè)地圖中，設(shè)置4基桿塔，電力線路采用常見的三相排列方式；在電力線路周邊設(shè)置5個(gè)障礙物，其中1個(gè)圓形表示單株樹木，4個(gè)不規(guī)則障礙物表示人工建筑、樹林等；在電力線路上設(shè)置12個(gè)待觀測(cè)興趣點(diǎn)；設(shè)置巡檢的起點(diǎn)和終點(diǎn)分別為P0(95,30)、PE(5,40)，待觀測(cè)興趣點(diǎn)位置如表2所示。將提出的IPSOAF算法和原PSO算法分別應(yīng)用于以上設(shè)置的仿真環(huán)境中，得到仿真結(jié)果如圖1~3所示。在仿真圖中，大黑點(diǎn)代表電力桿塔，小黑點(diǎn)代表電力線路上的預(yù)設(shè)興趣點(diǎn)，空心方框代表電力巡線任務(wù)的起始點(diǎn)和終點(diǎn)（下同）。

表2 預(yù)設(shè)興趣點(diǎn)位置

圖1 固定興趣點(diǎn)條件下2種改進(jìn)型算法的對(duì)比仿真曲線

圖2 固定興趣點(diǎn)條件下無(wú)人機(jī)與線路距離曲線

圖3 固定興趣點(diǎn)條件下攝像頭俯仰角變化曲線

從仿真結(jié)果的圖1、2可以看出，IPSOAF算法和PSO算法都能夠順利按要求完成輸電線路巡檢工作。從仿真曲線的細(xì)節(jié)來看，雖然兩者都保持在安全距離之外，但是IPSOAF算法獲得的路徑與線路之間的距離更加穩(wěn)定，且距離更小，更加有利于精確觀察；而PSO算法獲得路徑與電力線路之間的距離變化較大，穩(wěn)定性相對(duì)偏差，且總體巡檢路徑距離更大。通過圖3中的機(jī)載攝像頭俯仰角變化曲線可以看出IPSOAF算法所需要的攝像頭擺動(dòng)幅度相對(duì)較小，表明其工作狀態(tài)也更穩(wěn)定；PSO算法的攝像頭擺動(dòng)角度在50和160s附近出現(xiàn)較為明顯的擺動(dòng)，說明其工作狀態(tài)穩(wěn)定性存在不足。

4.2 預(yù)先劃定興趣點(diǎn)的情況

任務(wù)前指定常規(guī)待觀察興趣點(diǎn)和可疑興趣點(diǎn)。巡檢人員在巡檢過程中傳回的視頻和圖像資料經(jīng)常會(huì)發(fā)現(xiàn)一些事先未預(yù)料到的情況，可能會(huì)出現(xiàn)需要臨時(shí)增加待觀察興趣點(diǎn)的情況，這就要求算法實(shí)時(shí)調(diào)整巡檢路徑和巡檢任務(wù)規(guī)劃。本次仿真設(shè)定在巡檢到P7時(shí)，隨機(jī)在其前的（37,17）附近加入隨機(jī)興趣點(diǎn)（該興趣點(diǎn)較高，需要機(jī)載攝像頭上下俯仰較大角度，以全面觀測(cè)），且巡線無(wú)人機(jī)不被告知該興趣點(diǎn)的準(zhǔn)確位置數(shù)據(jù)，只能獲得概略指定范圍。仿真圖如圖4~6所示（隨機(jī)興趣點(diǎn)設(shè)置于圖4中空心圓形位置）。

圖4 隨機(jī)興趣點(diǎn)條件下2種改進(jìn)型算法的仿真曲線

圖5 隨機(jī)興趣點(diǎn)條件下無(wú)人機(jī)與線路距離曲線

圖6 隨機(jī)興趣點(diǎn)條件下攝像頭俯仰角變化曲線

從仿真圖4、5可以看出，基于IPSOAF算法和PSO算法的仿真曲線表現(xiàn)出更大的差異。除了類似4.1節(jié)中的差異之外，在100s時(shí)加入臨時(shí)模糊興趣點(diǎn)之后大約20s的時(shí)間，兩者表現(xiàn)出較大不同。IPSOAF算法在應(yīng)對(duì)臨時(shí)興趣點(diǎn)加入的過程中，與輸電線路之間的水平距離變化較小，且用更短時(shí)間迅速趨于穩(wěn)定狀態(tài)，很好地響應(yīng)了任務(wù)中隨機(jī)興趣點(diǎn)的加入。而PSO算法則相反，不但出現(xiàn)與線路水平距離變化幅度較大、耗時(shí)更久的現(xiàn)象，而且較大概率發(fā)生陷入局部極小的情況，從而導(dǎo)致巡檢任務(wù)無(wú)法完成。值得注意的是，在巡檢過程中，由于存在高度較高且比較復(fù)雜的待觀測(cè)興趣點(diǎn)，導(dǎo)致多旋翼無(wú)人機(jī)需要一邊沿線路方向前進(jìn)，一邊俯仰擺動(dòng)攝像頭，才能更加全面地觀測(cè)該類興趣點(diǎn)。同時(shí)通過大幅度減小多旋翼無(wú)人機(jī)在垂直方向上的位置調(diào)整，最終提高巡線效率。通過圖6的對(duì)比曲線可以看出，除4.1節(jié)仿真中展現(xiàn)的2種算法的差異之外，IPSOAF算法可以在面對(duì)高度較高的興趣點(diǎn)時(shí)，使得機(jī)載攝像頭俯仰方面擺動(dòng)幅度更小，全程運(yùn)行狀態(tài)也更加平穩(wěn)，因此其較PSO算法更加優(yōu)越。

5 結(jié)論

從上述分析和測(cè)試結(jié)果，可以得出以下結(jié)論：

1）通過引入非線性自適應(yīng)因子，并選取合適的參數(shù)，較好地平衡算法全局搜索和局部搜索的能力，加速了算法的收斂速度。

2）通過引入自調(diào)整學(xué)習(xí)因子，分別加強(qiáng)了不同運(yùn)行階段的全局搜索能力和局部搜索能力，進(jìn)一步提高了算法的搜索效率。

3）通過引入驅(qū)散策略，能夠引導(dǎo)算法更好地避免陷入局部極小，從而獲得全局最優(yōu)解。

從2種情況的電力巡線仿真可以得出，PSO算法基本上能夠完成設(shè)定的輸電線路路徑規(guī)劃任務(wù)，但偶發(fā)陷入局部極小，導(dǎo)致不能完成巡檢任務(wù)；而IPSOAF算法能夠獲得更好的效果，同時(shí)該算法還具有運(yùn)行時(shí)間較短，不易陷入局部極小等優(yōu)點(diǎn)。因此，提出的IPSOAF算法在電力巡線應(yīng)用中在搜索效率、收斂速度以及成功率方面，較PSO算法均具有優(yōu)勢(shì)。故本研究具有一定的理論研究?jī)r(jià)值和較好的社會(huì)應(yīng)用價(jià)值，進(jìn)一步深入研究興趣點(diǎn)細(xì)節(jié)巡檢將是未來該領(lǐng)域一個(gè)重要的研究方向。