歐陽玲,宋 克

(1.中原工學(xué)院,鄭州450007;2.國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,鄭州450005)

改進(jìn)的遺傳算法在配電網(wǎng)檢修計(jì)劃中的應(yīng)用

歐陽玲1,宋 克2

(1.中原工學(xué)院,鄭州450007;2.國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,鄭州450005)

為了減少供電企業(yè)停電損失費(fèi)用和檢修費(fèi)用,同時(shí)滿足多種約束條件,本文在借鑒目前配電網(wǎng)檢修計(jì)劃編制工作經(jīng)驗(yàn)的基礎(chǔ)上,建立了配電網(wǎng)檢修計(jì)劃優(yōu)化模型.針對(duì)該模型的特點(diǎn),采用改進(jìn)的遺傳算法求解配電網(wǎng)檢修計(jì)劃優(yōu)化問題.并通過具體優(yōu)化算例計(jì)算和分析,驗(yàn)證了本文所提出的模型和改進(jìn)算法的有效性.

配電網(wǎng);檢修計(jì)劃;優(yōu)化模型;遺傳算法

配電網(wǎng)設(shè)備檢修是電力系統(tǒng)中一項(xiàng)十分重要的內(nèi)容,設(shè)備檢修計(jì)劃安排的好壞,直接關(guān)系到電網(wǎng)企業(yè)和用戶的利益,對(duì)電力系統(tǒng)乃至整個(gè)社會(huì)的安全性和經(jīng)濟(jì)性都有著很大的影響.因此,根據(jù)供電企業(yè)的實(shí)際需要,建立一個(gè)兼顧電網(wǎng)安全性和經(jīng)濟(jì)性的檢修計(jì)劃數(shù)學(xué)模型,并設(shè)計(jì)求解該模型的算法,有著重要的理論價(jià)值和現(xiàn)實(shí)意義.目前,配電網(wǎng)設(shè)備檢修計(jì)劃基本上還是依靠檢修人員的經(jīng)驗(yàn)人工編制而成,在人工編制計(jì)劃中,存在著可靠性差、工作效率低、經(jīng)濟(jì)性得不到保證等問題[1].本文首先建立合適的配電網(wǎng)檢修計(jì)劃優(yōu)化模型,然后提出適合于該模型的優(yōu)化算法,最后通過算例驗(yàn)證模型和算法的有效性.

1 配電網(wǎng)檢修計(jì)劃的優(yōu)化模型

1.1 檢修計(jì)劃優(yōu)化目標(biāo)

從供電公司角度出發(fā),配電網(wǎng)檢修計(jì)劃優(yōu)化目標(biāo)應(yīng)包括以下兩個(gè)方面:一是在保證配電網(wǎng)安全運(yùn)行的前提下,最大限度地提高供電可靠性,降低供電企業(yè)因設(shè)備檢修而造成的停電損失;二是最大限度地降低因設(shè)備檢修而帶來的檢修成本.

對(duì)檢修而言,受檢修技術(shù)和檢修力量的限制,檢修工作的持續(xù)時(shí)間我們可以認(rèn)為是固定的,也就是說每臺(tái)設(shè)備每次檢修停電持續(xù)時(shí)間是固定的.因此,配電網(wǎng)供電可靠性的提高主要是通過減少因檢修而造成的停電負(fù)荷量和停電次數(shù)來實(shí)現(xiàn),而這兩種因素直接反映了企業(yè)的停電損失.若將導(dǎo)致負(fù)荷停電的設(shè)備檢修時(shí)間安排在負(fù)荷低谷期,即通過優(yōu)化設(shè)備的檢修時(shí)間就可以降低停電負(fù)荷量,也就相應(yīng)地降低了停電損失.同時(shí),保證一次停電可以解決的問題要全面解決,不允許因考慮不周而發(fā)生重復(fù)停電的問題.

檢修成本主要是支付給檢修工人的工資.一般情況下,節(jié)假日所支付的工資遠(yuǎn)遠(yuǎn)高于正常工作日.因此,要盡量避免將檢修工作安排在節(jié)假日,以降低檢修費(fèi)用.

1.2 檢修計(jì)劃目標(biāo)函數(shù)

基于此,本文建立了以降低供電企業(yè)停電損失費(fèi)用和檢修費(fèi)用的優(yōu)化目標(biāo):在保證系統(tǒng)安全可靠運(yùn)行的同時(shí),盡量減少停電損失費(fèi)用和檢修費(fèi)用[2-3].其數(shù)學(xué)描述為:

式中:f1—停電損失費(fèi)用,元;

f2—檢修費(fèi)用,元;

p—平均電價(jià),元/kW h;

N—待檢修設(shè)備總數(shù),臺(tái);

T—檢修時(shí)段總數(shù),d;

pit—第t時(shí)段第i個(gè)設(shè)備檢修所影響負(fù)荷,

MW;

uit—第t時(shí)段第i個(gè)設(shè)備的狀況,取 0時(shí),表示設(shè)備正常運(yùn)行;取1時(shí),表示設(shè)備停機(jī)檢修;

cit—第t時(shí)段第i個(gè)設(shè)備的檢修費(fèi)用,元.

顯然,這是一個(gè)多目標(biāo)優(yōu)化問題,并且兩個(gè)目標(biāo)函數(shù)求的都是最小化問題.對(duì)于求解這類多目標(biāo)優(yōu)化問題,本文采用權(quán)重系數(shù)法,分別給停電損失費(fèi)用f1和檢修費(fèi)用f2賦予不同的權(quán)重,其中w1和w2的大小代表f1和f2的重要程度,它們的線性加權(quán)和即為總的目標(biāo)函數(shù).這樣一來,多目標(biāo)優(yōu)化問題也就轉(zhuǎn)化為單目標(biāo)優(yōu)化問題:

式中:w1—停電損失費(fèi)用權(quán)重;

w2—檢修費(fèi)用權(quán)重.

把式(1)和(2)帶入式(3),即得到總的目標(biāo)函數(shù)式:

1.3 檢修計(jì)劃約束條件

本文的檢修計(jì)劃必須滿足以下約束條件:

(1)同時(shí)檢修約束.在一個(gè)系統(tǒng)中,一次停電可以解決的問題要全面解決,不允許因考慮不周而發(fā)生重復(fù)停電的問題.因此,有些設(shè)備必須同時(shí)檢修.當(dāng)月所有檢修中,凡是使同一條線路、相同節(jié)點(diǎn)停電的檢修,都認(rèn)為是重復(fù)停電檢修.在進(jìn)行檢修計(jì)劃時(shí)間編排時(shí),要將重復(fù)停電檢修安排在相同的時(shí)間段內(nèi),即在此檢修計(jì)劃執(zhí)行過程中只允許停電一次.

(2)互斥檢修約束.為了避免負(fù)荷點(diǎn)在檢修時(shí)停電,有些設(shè)備如互為備用的設(shè)備不能同時(shí)檢修.因此不能將它們安排在相同的時(shí)間段內(nèi)檢修,即它們的檢修時(shí)間不能有重疊.

(3)檢修資源約束.檢修資源是指檢修人員數(shù)量及技術(shù)能力、設(shè)備能力等.由于資源有限,使得能同時(shí)進(jìn)行檢修的設(shè)備數(shù)量有限.

(4)檢修開始時(shí)間約束.計(jì)劃?rùn)z修時(shí),按主管部門頒發(fā)的全國(guó)統(tǒng)一的規(guī)程所規(guī)定的項(xiàng)目、周期進(jìn)行檢修安排.因此設(shè)備的檢修日期有著一定的時(shí)間限制.

(5)檢修持續(xù)進(jìn)行.檢修工作應(yīng)貫徹“應(yīng)修必修,修必修好”的原則,所以要保證檢修工作持續(xù)進(jìn)行.

(6)不可變更的檢修約束.不可變更的檢修包括:上級(jí)調(diào)度部門制定的檢修計(jì)劃;上月延續(xù)至本月的檢修;事故檢修等.這類檢修的起始時(shí)間可認(rèn)為是確定的,與之存在同時(shí)檢修關(guān)系的設(shè)備檢修時(shí)間也不能變更,不參加檢修計(jì)劃時(shí)間的編排.

(7)時(shí)間調(diào)整約束.滿足下式:

式中:xoi—第i個(gè)設(shè)備申報(bào)開始檢修時(shí)間,d;Ai—第i個(gè)設(shè)備調(diào)整時(shí)間限值,d.

2 改進(jìn)的遺傳算法

2.1 基本遺傳算法的特點(diǎn)及缺陷

遺傳算法(GA)是從自然遺傳及自然選擇抽象出來的尋優(yōu)方法[4].與傳統(tǒng)的優(yōu)化算法如 SA、TS等相比,GA主要有全局優(yōu)化、通用性強(qiáng)、隱含并行性、計(jì)算量大等特點(diǎn).

GA的這些特點(diǎn)決定了它具有全局搜索能力、魯棒性強(qiáng)等優(yōu)點(diǎn),適合解決復(fù)雜的非線性問題.因此,本文選用GA求解配電網(wǎng)檢修計(jì)劃優(yōu)化問題,從理論上講是完全可行的.

基本遺傳算法(SGA)采用二進(jìn)制編碼、輪盤賭選擇方法,交叉、變異概率取固定值.特別要注意的是:①選擇采用輪盤賭方法,當(dāng)群體適應(yīng)度差異非常大時(shí),最佳個(gè)體的生存機(jī)會(huì)顯著增高,較差個(gè)體的生存機(jī)會(huì)被剝奪,使得最佳個(gè)體很快充滿整個(gè)群體,GA較早地喪失了進(jìn)化能力;②SGA中交叉概率P、變異概率Pm在整個(gè)進(jìn)化過程中都取固定值(或形式不變化),這在處理復(fù)雜問題時(shí),很難同時(shí)兼顧搜索范圍廣和搜索速率快的矛盾.

這就使得SGA存在一些亟待克服的缺點(diǎn):①進(jìn)化初期的未成熟收斂;②進(jìn)化中后期由于個(gè)體競(jìng)爭(zhēng)減弱引起的隨機(jī)搜索趨勢(shì).前者導(dǎo)致算法收斂到局部最優(yōu)解,后者導(dǎo)致算法的收斂緩慢.

我們知道,交叉是 GA生成新群體,帶動(dòng)群體進(jìn)化的主要方法,是 GA的核心;變異是維持群體多樣性,突破局部極值的主要手段.兩種算子的操作方式對(duì)整個(gè) GA的影響相當(dāng)大.根據(jù)這一情況,本文針對(duì)具體問題改變SGA中選擇、交叉、變異的操作方式,使其克服SGA固有缺陷.改進(jìn)的重點(diǎn)主要放在:①如何增加種群的多樣性以克服未成熟收斂現(xiàn)象;②如何提高算法的局部搜索能力以提高解的質(zhì)量;③如何進(jìn)行有效的搜索以提高收斂速度.

2.2 雙變異率遺傳算法

為了防止未成熟收斂現(xiàn)象,我們對(duì)基本遺傳算法作出改進(jìn),采用一種雙變異率遺傳算法(DM GA)[5].

我們知道,為了維持種群的多樣性,可以有目的地選擇配對(duì)個(gè)體.一般情況下,在物種的形成過程中要考慮配對(duì)策略,以防止相似個(gè)體之間進(jìn)行配對(duì).SGA中,參與交配的個(gè)體是隨機(jī)配對(duì)的,但在DM GA中,我們規(guī)定,只有當(dāng)參與配對(duì)的兩個(gè)個(gè)體間的廣義海明距離超過一定閾值時(shí),才允許它們進(jìn)行交配.

在進(jìn)化的最初階段,由于個(gè)體間差異較大,種群相似度較小,滿足條件的配對(duì)個(gè)體相對(duì)來說比較多.但隨著算法的進(jìn)行,尤其到了進(jìn)化的中后期,個(gè)體間差異減小,種群相似度較大,這時(shí)滿足條件的配對(duì)個(gè)體會(huì)隨之減少,使得交叉操作產(chǎn)生的個(gè)體數(shù)目很有可能達(dá)不到種群規(guī)模.為此,需要引入新個(gè)體來“補(bǔ)充”種群規(guī)模.若采用直接隨機(jī)生成的方式產(chǎn)生新個(gè)體,適應(yīng)度值都太低,而且對(duì)算法的全局搜索性能增加并不顯著.為此,我們想到在變異操作中引入雙變異率(即局部小變異和全局大變異),當(dāng)由廣義海明距離控制的交叉操作產(chǎn)生的個(gè)體數(shù)不足種群規(guī)模時(shí),說明種群中的個(gè)體有趨于相似的可能,很有可能在未來幾代后陷入局部最優(yōu),此時(shí)局部變異因子發(fā)揮作用,對(duì)原種群進(jìn)行小突變.這種類似于“擾動(dòng)”的作用,一方面增大了搜索空間,增加了種群多樣性;另一方面突變后的個(gè)體很有可能滿足了配對(duì)策略,補(bǔ)充了種群規(guī)模.若種群規(guī)模還不夠,則需反復(fù)對(duì)原種群進(jìn)行局部小變異.隨后的全局大變異保證了整個(gè)變異過程的全局收斂.這種對(duì)交叉、變異方式所做的改變可有效克服SGA易陷入局部最優(yōu)及易發(fā)生未成熟收斂的缺點(diǎn).

假設(shè):種群規(guī)模為Size,二進(jìn)制染色體串的長(zhǎng)度為L(zhǎng).

定義:廣義海明距離GHij是相同長(zhǎng)度的以a為基的2個(gè)字串i和j中對(duì)應(yīng)位不同基因的數(shù)量.

本文為了防止高相似個(gè)體之間的交叉操作,提出了廣義海明距離閾值T.只有當(dāng)種群個(gè)體間的廣義海明距離GHij>T時(shí),才可進(jìn)行交叉操作.由于廣義海明距離計(jì)算的是2個(gè)字串對(duì)應(yīng)位不同基因的數(shù)量,因此,T=(0.1-0.3)＊L時(shí),經(jīng)實(shí)驗(yàn)分析得知,T的取值與種群規(guī)模、染色體長(zhǎng)度有一定關(guān)系:一般種群規(guī)模越大,染色體長(zhǎng)度越長(zhǎng),T的取值可定得略大些;反之,T的取值可定得略小些.

考慮到隨著進(jìn)化的進(jìn)行,種群中個(gè)體間的相似度將會(huì)越來越大,尤其到了算法后期,滿足配對(duì)條件的個(gè)體越來越少,需要進(jìn)行多次小突變.若突變次數(shù)過多,很有可能會(huì)在算法末期將尋到的最優(yōu)解破壞掉.為此,閾值T可隨進(jìn)化代數(shù)逐漸減少.雙變異率遺傳算法操作步驟如下:

步驟1:初始化群體pop,種群大小為Size;

步驟2:計(jì)算pop中個(gè)體的適應(yīng)度,同時(shí)保留最優(yōu)個(gè)體;

步驟3:對(duì)pop進(jìn)行聯(lián)賽選擇操作,選擇操作后的群體為TempE;

步驟4:以較大的交叉概率Pc選出一部分個(gè)體,數(shù)量記為popsize,對(duì)任意兩個(gè)個(gè)體計(jì)算廣義海明距離,只有當(dāng)廣義海明距離大于閾值T時(shí)才可進(jìn)行交叉操作;

步驟5:將交叉操作產(chǎn)生的個(gè)體放入臨時(shí)種群tempop,若tempop>Size,進(jìn)入步驟 6,否則,對(duì)TempE進(jìn)行局部小變異,變異概率Pm1,然后轉(zhuǎn)入步驟4;

步驟6:對(duì)tempop按適應(yīng)度值擇優(yōu)選popsize放回TempE中;

步驟7:對(duì)TempE進(jìn)行全局大變異操作,變異概率Pm2;

步驟8:將步驟2中的最優(yōu)個(gè)體代替TempE中的最差個(gè)體;

步驟9:將TempE賦給pop,作為下一代的初始種群;

步驟10:判斷是否滿足算法終止條件,即判斷是否已達(dá)到最大進(jìn)化代數(shù),是則輸出最終結(jié)果,否則轉(zhuǎn)入步驟2.

其中,步驟5中的臨時(shí)種群tempop是每一代交叉操作后的累積.

3 雙變異率遺傳算法配電網(wǎng)檢修計(jì)劃優(yōu)化實(shí)例

對(duì)于求解配電網(wǎng)檢修計(jì)劃優(yōu)化問題,采用雙變異率遺傳算法,流程如圖1所示.

本文配電網(wǎng)檢修計(jì)劃數(shù)據(jù)選用文獻(xiàn)[5]中某地區(qū)供電局4月份待檢修設(shè)備的數(shù)據(jù)信息,如表2所示.

算例中,只有紅亭1線和紅瑯線檢修會(huì)造成負(fù)荷停電,紅亭1線檢修會(huì)使亭江變電所停電,紅瑯線檢修會(huì)使瑯岐變電所停電,它們所引起的停電負(fù)荷預(yù)測(cè)結(jié)果如表3所示.

分別采用 TSGA、DM GA兩種方法對(duì)配電網(wǎng)檢修計(jì)劃優(yōu)化問題進(jìn)行求解.

圖1 雙變異率遺傳算法檢修優(yōu)化求解流程圖

表2 待檢修設(shè)備信息

表3 停電負(fù)荷 MW

設(shè)平均電價(jià)為0.56元/kWh,本文直接用平均電價(jià)與功率的乘積來反映停電損失費(fèi)用.假定檢修工人在正常工作日對(duì)每臺(tái)設(shè)備檢修的費(fèi)用為1元/d,節(jié)假日對(duì)每臺(tái)設(shè)備檢修的費(fèi)用為3元/d,4月共30 d,其中節(jié)假日(清明節(jié)及周末)是 4、5、6、12、13、19、20、26、27日,共9天,依照這種標(biāo)準(zhǔn)來反映檢修費(fèi)用.

使用二進(jìn)制位串編碼,每一個(gè)決策變量編碼碼長(zhǎng)為5位,采用二進(jìn)制單點(diǎn)交叉,交叉概率Pc=0.8,廣義海明距離閾值T=10,聯(lián)賽規(guī)模為2,最優(yōu)個(gè)體保留1個(gè),局部小變異概率Pm1=0.001,全局大變異概率Pm2=0.05,權(quán)重W1=0.01,權(quán)重W2=1,種群規(guī)模為60,最大進(jìn)化代數(shù)為100.

根據(jù)網(wǎng)絡(luò)拓?fù)浞治龅玫?

(1)旗河 1線、2線,北西 1線、2線,北金 1線、2線,建金1線、2線以及南鰲1線、2線是互為備用的雙回路線路,所以應(yīng)錯(cuò)開檢修時(shí)間,為互斥檢修關(guān)系.

(2)北金2線136開關(guān)與北金2線回路,南鰲1線133保護(hù)與南鰲1線回路同時(shí)檢修.

(3)紅瑯線是紅亭1線的一個(gè)分支,所以應(yīng)在紅亭1線檢修的同時(shí)對(duì)紅瑯線進(jìn)行檢修.

(4)每天最多只能同時(shí)檢修4個(gè)項(xiàng)目.

按照同時(shí)檢修約束進(jìn)行分組后,6號(hào)與12號(hào)可歸為一組,4號(hào)與18號(hào)可歸為一組,16號(hào)與17號(hào)可歸為一組,即形成18組,并且本月檢修計(jì)劃中沒有不可變更的檢修約束,因此可確定這18組即為最終優(yōu)化變量.

TSGA和DM GA兩種算法的優(yōu)化結(jié)果分別如表4和表5所示;表6為這兩種算法的比較結(jié)果.

由表4-表6可以看出,兩種算法都能完全避免違背各種約束條件,并且都能將引起停電損失的設(shè)備安排在最小負(fù)荷日(4月28日-4月29日)檢修,使得兩種算法在減小停電損失費(fèi)用這一方面表現(xiàn)相當(dāng).但在DM GA求得的檢修計(jì)劃中,設(shè)備在周末檢修的天數(shù)為6 d,而在 TSGA算法中,周末檢修的天數(shù)為9 d,顯然,TSGA的檢修費(fèi)用要高于DM GA.由此可以看出,用DM GA求得的檢修計(jì)劃更能滿足實(shí)際的需要.

表4 TSGA優(yōu)化結(jié)果

表5 DM GA優(yōu)化結(jié)果

表6 算法比較結(jié)果

算法收斂過程如圖2所示.由圖2也可以看出,DM GA在收斂速度上也比 TSGA快很多,并且尋得的最優(yōu)解也好于 TSGA,顯示了DM GA收斂速度快、尋優(yōu)能力強(qiáng)的特性.

圖2 算法收斂過程

4 結(jié) 語

本文在分析配電網(wǎng)檢修計(jì)劃編制原則的基礎(chǔ)上,建立了適合當(dāng)前國(guó)情的配電網(wǎng)檢修計(jì)劃優(yōu)化模型.同時(shí),針對(duì)基本遺傳算法存在收斂速度慢、尋優(yōu)能力差、易陷入局部最優(yōu)等缺點(diǎn),采用一種改進(jìn)的遺傳算法應(yīng)用于實(shí)際配電網(wǎng)檢修計(jì)劃優(yōu)化中.對(duì)優(yōu)化實(shí)例的分析表明,本文所提出的配電網(wǎng)檢修計(jì)劃優(yōu)化模型和改進(jìn)遺傳算法正確、有效,具有一定的理論價(jià)值和實(shí)用價(jià)值.

[1]于爾鏗,劉廣一,周京陽,等.能量管理系統(tǒng)(EMS)[M].北京:科學(xué)出版社,1998.

[2]黃弦超,舒雋,張粒子,等.免疫禁忌混合智能優(yōu)化算法在配電網(wǎng)檢修優(yōu)化中的應(yīng)用[J].中國(guó)電機(jī)工程學(xué)報(bào),2004,24(11):96-100.

[3]全宏興,劉俊勇.電力市場(chǎng)下火電廠機(jī)組檢修計(jì)劃的研究[J].電力系統(tǒng)自動(dòng)化,2002,26(14):35-39.

[4]周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社,1999.

[5]王杰,馬雁,王非.一種雙變異率的改進(jìn)遺傳算法及其仿真研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(3):57-60.

[6]黃弦超.配電網(wǎng)檢修計(jì)劃優(yōu)化方法的研究與應(yīng)用[D].北京:華北電力大學(xué),2004.

Application on Distribution Maintenance Scheduling by Improved Genetic Algorithm

OU YAN Y Ling1,SONG Ke2
(1.Zhongyuan University of Technology,Zhengzhou 450052;2.National Digital Sw itching System Engineering&Technological R&D Center,Zhengzhou 450052,China)

This paper summarizes the theo ry and achievement of maintenance scheduling p roblem,and refers the experience of maintenance scheduling work.On the basis of these analyses,a new model for distribution maintenance scheduling(DM S)w hich intends to find the most econom ical maintenance schedule w ithout violating any restrictions is p roposed in this paper.Themodel’s fitness and themethod’s validity are very co rrect by the results of a p racticalmaintenance scheduling.

distribution;maintenance scheduling;op timization model;genetic algorithm

A

10.3969/j.issn.1671-6906.2011.04.013

1671-6906(2011)04-0056-06

2011-07-15

歐陽玲(1978-),女,安徽池州人,講師,碩士.