基于改進粒子群算法的變電站巡視路徑問題研究

鐘成

（廣西電網有限責任公司北海供電局，廣西 北海 536000）

0 前言

隨著技術的進步，變電站智能機器人巡視受到了重視，巡視路徑的優化對于提高巡視效率有著重要的作用。利用機器人巡視變電站，可以大幅減輕巡維人員工作壓力，解放勞動力，使巡維人員從事更加專業的工作，對于化解電力設備數量不斷增長與巡維人員不足之間的矛盾有重要意義。優化變電站設備巡視路徑是降低智能巡視機器人能耗，提高機器人效率的有效手段。變電站設備巡視路徑優化問題可以描述為：給定l個設備間隔以及各設備間隔的平面位置坐標，求解一條經過各設備間隔的最短路徑。其數學模型為：假設l個設備間隔的集合G={G1,G2,G3...,Gl}，且每兩個設備間隔的距離為d(Gi,Gj)，要求解一條Hamilton回路，使的值最小。這是一個典型的優化問題，隨著問題規模的擴大（設備間隔數目增加），該問題的求解結果會呈現指數級增加，造成求解過程越來越復雜，所需的計算時間也越來越長，因此該問題屬于組合優化NP問題（Non-Deterministic Polynomial Problems ，存在多項式算法能夠解決的非決定性問題）[1]。若采用傳統的算法，例如窮舉搜索法、線性規劃法，是難以實現的，所以需要找到更優化的算法來求解此問題。

粒子群優化算法（Particle Swarm Optimization，PSO）是一種進化計算技術，1995 年由Eberhart 博士和Kennedy 博士提出，源于對鳥群捕食的行為研究[2]。該算法最初是受到飛鳥集群活動的規律性啟發，進而利用群體智能建立的一個簡化模型。粒子群算法是建立在對動物集群行為觀察的基礎上，利用集群中個體對信息的共享，使整個集群的運動規律在求解空間中產生有規則可循的演化過程，進而求出最優解。

1 粒子群算法基本原理

粒子群優化算法對鳥群的捕食行為進行模擬，設想這樣一個場景：一群鳥在某區域內隨機搜索食物，但在該區域里有且僅有一塊食物，所有的鳥都不知道食物具體位置，但他們知道當前的位置離食物還有多遠，因此找到食物的最優策略是搜尋目前離食物最近的鳥的周圍區域，從而獲悉食物位置[3]。PSO算法中每個粒子代表問題的潛在解，并且每個粒子對應于由適應度函數確定的適應度值。粒子的速度決定了粒子移動的方向和距離，速度隨自身及其他粒子的移動經驗進行動態調整，進而實現個體在可解空間中的尋優。

假定在一個m維的空間中，有n個粒子組成粒子群X={X1,X2,X3...,Xn}，其中第i個粒子的位置向量為Xi={Xi1,Xi2,...,Xin}，速度向量為Vi={Vi1,Vi2,...,Vin}，該粒子在m維空間移動過程中歷經的最優位置為Pi={Pi1,Pi2,...,Pin}。將全部粒子經過的最優位置用PG表示，則PG={PG1,PG2,...,PGn}。粒子在每次迭代后的速度與位置評價函數分別用下列式（1）、式（2）表示：

在式中k為迭代次數，w是慣性權重，c1、c2指加速因子，r1、r2為在區間[0,1]內服從均勻分布的隨機數。式（1）中的wVi(k)為動量部分，為粒子提供一個初始動量，使之可根據初速度進行慣性運動；c1r1[Pi－Xi(k)]稱為認知部分，表示粒子自身的記憶行為，激發粒子向自身曾發現的最優位置移動；c2r2[PG－Xi(k)]為社會部分，表示粒子間的相互影響，引導其他粒子向粒子群的最優解移動[4-9]。三部分的平衡約束決定了PSO算法的性能。在迭代計算的過程中，為了防止粒子超速盲目搜索，還要對粒子的速度加以限制，一般將粒子的位置限制在區間[－Ximax,Ximax]內。

2 改進策略

由于傳統的粒子群算法存在早熟收斂于局部最優解和收速度斂較慢的問題[10-13]，本文提出了以下改進：

2.1 進化變異粒子個體

變異操作是增加種群多樣性的重要方法，適當的變異既可以使種群多樣化，又能提高局部區域探索能力。本文引入進化變異算子，當多樣性低時，增加變異因素，使算法探索更廣闊的空間；當多樣性較強時，削弱變異因素，使算法在小范圍內精確求解。

用Sij表示粒子Xi、Xj的相似度：

式中m表示粒子空間維數。

當Xik=Xjk時，表示粒子Xi與Xj在第k個位置的值相等。Sij∈[0,1]，若Sij=1Sij=[0,1]，則表示Xi、Xj完全相同。

定義第i個粒子的多樣性Di：

式（5）中，Pi為第i個粒子的最優解，PG為全部粒子的最優解。

將粒子種群多樣性定義為單個粒子多樣性的平均值：

當D≤0.3時，執行該變異進化，并采用順序交換法將粒子Xi={Xi1,Xi2,...,Xin}中隨機產生的Xij、Xik兩個變異位置進行交換，得到新粒子Xi=(Xi1,Xi2,...,Xij-1,...,Xik-1,Xij,Xik+1,...,XiS)。

2.2 自適應調整慣性權重

在粒子群優化的過程中，按照適應度的大小對當前的粒子群X=(X1,X2,...,Xn)進行降序排序，并相應形成一個排好序的新粒子群Y=(Y1,Y2,...,Yn)，令fi為種群規模為n的粒子群中，第i個粒子的適應度，Yi∈{f1,f2,...,fn}，1≤i≤n。由于新粒子群中排列第一的粒子適應度最強，因此將其稱之為最優粒子，相應的把新粒子群中第i個粒子與最優粒子的距離稱為最優粒子距di。隸屬函數是模糊集合論中的一個基礎概念，是模糊集合理論與方法具體應用的基石。因此如何建立某個模糊概念的較為合適的隸屬函數，是用模糊集合的方法能否較好的解決問題的關鍵。本文通過引入最優粒子距的概念，隸屬函數u(di,x)的表達式如下：

式（7） 中，n為 粒 子 群 規 模，t1、t2為控制參數，α、β為調整系數，并且滿足條件t1≤t2≤1，α≥0，β≥0。

通過上述隸屬函數的映射關系，可以知道個體粒子在粒子群中的隸屬度，根據每個粒子的隸屬度，可以建立如下慣性權重自適應調整函數w(i,x)：

式（8）中T為當前迭代次數，Tmax為最大迭代次數，ws、we分別表示慣性權重w的初始值和結束值。

3 仿真研究

本文應用的實例為某500 kV變電站，根據該站的電氣總平面布置圖構建平面直角坐標系，并列出該站需巡視的52個設備間隔的平面直角坐標值。采用MATLAB R2013a進行仿真測試，本改進粒子群算法的參數設置如下：加速因子c1=1.4，c2=1.6；控制參數t1=0.4，t2=0.6；調整系數α=3，β=2。

表1 改進粒子群算法求解變電站設備巡視路徑問題結果

表1統計了采用本文提出的改進粒子群算法，求解變電站設備巡視路徑優化問題時，分別于10次、50次、100次以及200次迭代后得出的最優解情況。由此可見，隨著迭代次數的增加，最短巡視路徑的路程也逐漸減少，求解結果收斂于最優。

圖1 迭代計算10次變電設備巡視最優路徑

圖2 迭代計算50次變電設備巡視最優路徑

圖3 迭代計算100次變電設備巡視最優路徑

圖4 迭代計算200次變電設備巡視最優路徑

圖1至圖4分別展示了各次迭代進化后，所求解的最優路徑情況，從路徑的形狀可見，早期求得的最優路徑錯綜復雜，存在一定的迂回折返現象，致使總路程較長，而經過一定數量的迭代后，算法逐漸尋求到更優解，路徑也變得更加簡潔，因此總路程也隨之變短。

圖5 改進粒子群算法求變電站設備巡視路徑最優解過程

圖5顯示了改進粒子群算法求解變電站設備巡視路徑問題最優解的演化過程，即迭代次數與最優解之間的關系，說明隨著迭代次數的增加，最優解結果也逐漸趨向于最短。

4 結束語

本文采用了一種改進粒子群算法，研究了變電站設備巡視路徑優化問題，運用引進進化變異粒子個體，并且對慣性權重進行自適應調整，實現了粒子種群的動態更新。使算法既能夠在運算的早期提高算法的探索能力，避免運算停滯，又能在運算的后期找到最優解并迅速收斂，提高求解速度。并通過實例驗證了所提出方法的研究性，對于實際電網有一定參考價值。