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

鐘成

（廣西電網(wǎng)有限責(zé)任公司北海供電局，廣西 北海 536000）

0 前言

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

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

1 粒子群算法基本原理

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

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

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

2 改進(jìn)策略

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

2.1 進(jìn)化變異粒子個(gè)體

變異操作是增加種群多樣性的重要方法，適當(dāng)?shù)淖儺惣瓤梢允狗N群多樣化，又能提高局部區(qū)域探索能力。本文引入進(jìn)化變異算子，當(dāng)多樣性低時(shí)，增加變異因素，使算法探索更廣闊的空間；當(dāng)多樣性較強(qiáng)時(shí)，削弱變異因素，使算法在小范圍內(nèi)精確求解。

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

式中m表示粒子空間維數(shù)。

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

定義第i個(gè)粒子的多樣性Di：

式（5）中，Pi為第i個(gè)粒子的最優(yōu)解，PG為全部粒子的最優(yōu)解。

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

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

2.2 自適應(yīng)調(diào)整慣性權(quán)重

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

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

通過上述隸屬函數(shù)的映射關(guān)系，可以知道個(gè)體粒子在粒子群中的隸屬度，根據(jù)每個(gè)粒子的隸屬度，可以建立如下慣性權(quán)重自適應(yīng)調(diào)整函數(shù)w(i,x)：

式（8）中T為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)，ws、we分別表示慣性權(quán)重w的初始值和結(jié)束值。

3 仿真研究

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

表1 改進(jìn)粒子群算法求解變電站設(shè)備巡視路徑問題結(jié)果

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

圖1 迭代計(jì)算10次變電設(shè)備巡視最優(yōu)路徑

圖2 迭代計(jì)算50次變電設(shè)備巡視最優(yōu)路徑

圖3 迭代計(jì)算100次變電設(shè)備巡視最優(yōu)路徑

圖4 迭代計(jì)算200次變電設(shè)備巡視最優(yōu)路徑

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

圖5 改進(jìn)粒子群算法求變電站設(shè)備巡視路徑最優(yōu)解過程

圖5顯示了改進(jìn)粒子群算法求解變電站設(shè)備巡視路徑問題最優(yōu)解的演化過程，即迭代次數(shù)與最優(yōu)解之間的關(guān)系，說明隨著迭代次數(shù)的增加，最優(yōu)解結(jié)果也逐漸趨向于最短。

4 結(jié)束語

本文采用了一種改進(jìn)粒子群算法，研究了變電站設(shè)備巡視路徑優(yōu)化問題，運(yùn)用引進(jìn)進(jìn)化變異粒子個(gè)體，并且對(duì)慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整，實(shí)現(xiàn)了粒子種群的動(dòng)態(tài)更新。使算法既能夠在運(yùn)算的早期提高算法的探索能力，避免運(yùn)算停滯，又能在運(yùn)算的后期找到最優(yōu)解并迅速收斂，提高求解速度。并通過實(shí)例驗(yàn)證了所提出方法的研究性，對(duì)于實(shí)際電網(wǎng)有一定參考價(jià)值。