改進PSO 算法及其無人機電力巡線規劃應用

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

1.南京航空航天大學自動化學院，江蘇南京211106 2.先進飛行器導航、控制與健康管理工業和信息化部重點實驗室(南京航空航天大學)，江蘇南京211106

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

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

1 粒子群算法

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

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

在 t+1時刻，所有粒子均遵循式（1）和（2）更新自身參數，以在搜索空間內尋找該問題的最優解。

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

2 改進措施

2.1 自適應慣性權重

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

在粒子群算法中，學習因子 c1和 c2描述各個粒子自身學習和他人學習對粒子運動方向的影響，其反映各個粒子之間的信息共享程度。在 c1取值較大時，會導致粒子大量聚集在局部優勢區域；在 c2取值較小時，則會致使粒子過早收斂于局部最小值，陷入局部最優。因此，引入自適應因子，通過選取合適的參數，可以平衡算法全局搜索和局部搜索的能力，并確保算法本身的收斂性。

通過引入自適應因子：

式中： ωs和 ωe分別為初始慣性權重和結束慣性權為最大迭代數，t為當前代數。

2.2 學習因子調整

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

2.3 驅散策略

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

式中： xmax、 xmin分別表示分子聚集范圍內距當前最優分子的最大距離和最小距離。

如果某個粒子與當前最優位置的距離大于cg，則表明此粒子暫時沒有趨于局部最優的風險，不必進行驅散操作。cg的選擇影響算法的驅散效果，若取值過大，會導致算法收斂速度下降；若取值過小，則驅散效果變差，不利于跳出局部極小。

2.4 改進算法步驟

通過以上改進，自適應收縮因子的混合粒子群算法的基本步驟如下：

1）在隨機產生預設數量的粒子，并對全體粒子的參數進行初始化；

3） 更 新 w 、 c1和 c2；

4）判斷算法結束條件是被否滿足，若滿足，則運行結束；若不滿足，則繼續運行；

5）判斷是否滿足驅散操作條件，若滿足，則轉向步驟5）；若不滿足，則轉向步驟6）；

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

3 算例

為了完整地測試新算法的性能，選擇5個典型的智能優化算法測試函數[16]。

1）Schaffer函數：

2）Griewank函數：

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

3）Rosenbrock函數：

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

4）Rastrigrin函數：

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

5）Shubert函數：

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

表1 2種不同類型反應算法針對不同測試函數的優化測試結果

4 仿真

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

4.1 預先劃定興趣點的情況

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

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

表2 預設興趣點位置

圖1 固定興趣點條件下2種改進型算法的對比仿真曲線

圖2 固定興趣點條件下無人機與線路距離曲線

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

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

4.2 預先劃定興趣點的情況

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

圖4 隨機興趣點條件下2種改進型算法的仿真曲線

圖5 隨機興趣點條件下無人機與線路距離曲線

圖6 隨機興趣點條件下攝像頭俯仰角變化曲線

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

5 結論

從上述分析和測試結果，可以得出以下結論：

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

2）通過引入自調整學習因子，分別加強了不同運行階段的全局搜索能力和局部搜索能力，進一步提高了算法的搜索效率。

3）通過引入驅散策略，能夠引導算法更好地避免陷入局部極小，從而獲得全局最優解。

從2種情況的電力巡線仿真可以得出，PSO算法基本上能夠完成設定的輸電線路路徑規劃任務，但偶發陷入局部極小，導致不能完成巡檢任務；而IPSOAF算法能夠獲得更好的效果，同時該算法還具有運行時間較短，不易陷入局部極小等優點。因此，提出的IPSOAF算法在電力巡線應用中在搜索效率、收斂速度以及成功率方面，較PSO算法均具有優勢。故本研究具有一定的理論研究價值和較好的社會應用價值，進一步深入研究興趣點細節巡檢將是未來該領域一個重要的研究方向。