配電網(wǎng)重構(gòu)遺傳算法的個(gè)體編碼綜述

劉延華 李永飛 李 林 郝 歡

1(國網(wǎng)山東省電力公司 山東 濟(jì)南 250001)2(國網(wǎng)電力科學(xué)研究院武漢南瑞有限責(zé)任公司 湖北 武漢 438400)

0 引 言

配電網(wǎng)重構(gòu)是通過變換配電網(wǎng)開關(guān)的狀態(tài)，修改配電網(wǎng)拓?fù)涞倪^程。其目的包括：1) 能量損耗最小化;2) 保證電壓;3) 降低負(fù)載;4) 維護(hù)負(fù)載平衡。值得注意的是，配電網(wǎng)重構(gòu)是一個(gè)實(shí)際的生產(chǎn)生活中的復(fù)雜問題，被方方面面的現(xiàn)實(shí)條件所制約。所以，上述目標(biāo)往往需要和一些次要目標(biāo)以及約束條件一起考慮，問題就變得復(fù)雜很多。例如，如果同時(shí)考慮到設(shè)備使用損耗，能量損耗最小化的目標(biāo)需要伴隨另一個(gè)次要的目標(biāo)——開關(guān)操作次數(shù)最小化。此外，有一些約束條件必須要滿足，比如拓?fù)涞妮椛湫院瓦B通性，支路的限制，總線的電壓以及變電站的功率。這些約束有的是連續(xù)的，有的是離散的[1]。

從數(shù)學(xué)角度而言，配電網(wǎng)重構(gòu)問題十分復(fù)雜。因此，這一問題引起了廣泛關(guān)注。從文獻(xiàn)[2]開始起，出現(xiàn)了很多基于貪婪算法求解該問題的研究。其中最主要的兩大類是開關(guān)交換方法[3-6]和順序開模類方法[7-9]。不管是開關(guān)交換還是順序開模，最大的優(yōu)點(diǎn)就是概念簡單。然而，這兩類方法的本質(zhì)依然是貪婪算法，局限性在于過于注重局部，難以獲取全局最優(yōu)。

為了獲得全局最優(yōu)解，演化計(jì)算被引入配電網(wǎng)重構(gòu)這一研究領(lǐng)域。演化計(jì)算是模擬大自然生物演化過程的，基于群體的，具有自組織、自適應(yīng)和自學(xué)習(xí)能力的，求解問題的方法?？梢栽谡麄€(gè)解空間內(nèi)搜索解，具有獲取全局最優(yōu)的可能性。其原理簡單、易于操作、通用性強(qiáng)，而且特別適合大規(guī)模并行處理，因此應(yīng)用極為廣泛。演化計(jì)算包括很多分支，如遺傳算法、演化策略、演化規(guī)劃、模擬退火、禁忌搜索、粒子群優(yōu)化以及差分演化等。其中，遺傳算法是歷史最為悠久，研究程度最高的分支，一直以來都最受關(guān)注，最近的一些應(yīng)用見文獻(xiàn)[10-17]。

演化計(jì)算的多個(gè)分支已經(jīng)被引入配電網(wǎng)重構(gòu)這一領(lǐng)域，其中配電網(wǎng)重構(gòu)的遺傳算法為數(shù)眾多，研究開展得比較充分。

絕大多數(shù)演化計(jì)算都由雜交、變異和選擇三種主要算子所控制。和其他演化計(jì)算的類別相比，遺傳算法的個(gè)體編碼以二進(jìn)制或十進(jìn)制編碼為主，雜交變異十分簡便。通常來講，雜交主要以交換拼接為主，同時(shí)，變異也有通用的方法。此外，選擇算子是演化計(jì)算中通用性最強(qiáng)的，大多數(shù)選擇算子都可以廣泛使用。眾多配電網(wǎng)重構(gòu)的遺傳算法之間最大的區(qū)別在于個(gè)體編碼的不同。而編碼直接決定了解空間的大小，也就是可行解的數(shù)量，從而很大程度上影響著算法的求解效率?；谏鲜龅谋尘翱芍?，針對各種配電網(wǎng)重構(gòu)遺傳算法的個(gè)體編碼方式進(jìn)行總結(jié)和分析，對于繼續(xù)研究配電網(wǎng)重構(gòu)遺傳算法具有重要的意義。

本文對現(xiàn)有的配電網(wǎng)重構(gòu)遺傳算法的個(gè)體編碼進(jìn)行綜述，從而為配電網(wǎng)重構(gòu)遺傳算法研究的深入提供支持。

1 配電網(wǎng)重構(gòu)

根據(jù)圖論，配電網(wǎng)重構(gòu)問題定義如下[18]。圖G包含一系列頂點(diǎn)X和一系列邊A，其數(shù)學(xué)表達(dá)為G(X,A)。G中的每一條邊ai,j表示一個(gè)集合X中兩個(gè)非源頭的元素之間的連接，此處用n(X)和n(A)表達(dá)X和A的元素個(gè)數(shù)。扇區(qū)是一個(gè)由子基站、總線和無開關(guān)支路組成的單元。扇區(qū)的邊界由具有開關(guān)的支路形成，可以利用扇區(qū)圖來表達(dá)一個(gè)分布網(wǎng)絡(luò)——GS(XS,AS)，集合XS組成了網(wǎng)絡(luò)扇區(qū)，AS表示所有的有開關(guān)的支路。如果整個(gè)系統(tǒng)只有一個(gè)子基站，GS就是一棵具有輻射性拓?fù)涞臉?。如果子基站的?shù)量更多一些，GS則由樹集合TS(XST,AST)組成。XST=XS=XF∪XL，XF是由連通邊也就是開關(guān)閉合的邊構(gòu)成的不相交集，而XL是不連通邊構(gòu)成的不相交集，任何屬于TS的邊都是連通邊。由于XST=XS，每條不連通邊都位于TS的兩個(gè)節(jié)點(diǎn)之間，每條不連通邊在GS中建立了一個(gè)基本的環(huán)路。無論GS中存在何樣的樹集合，不連通邊的數(shù)量是恒定的。所以，支路的數(shù)量和基本的環(huán)路也是恒定的。配電網(wǎng)重構(gòu)就是為了滿足能量損耗最小化，或者保證電壓，或者降低負(fù)載，或者維護(hù)負(fù)載平衡的目的，對GS進(jìn)行修改。此外，必須考慮一些實(shí)際的電氣限制。例如，每個(gè)節(jié)點(diǎn)必須考慮支路電流熱量限制和最小電壓，源節(jié)點(diǎn)必須考慮子基站功率限制等。

圖1是一個(gè)配電網(wǎng)的例子。圖中：大矩形框表示的是一個(gè)單獨(dú)的子基站，圓形則表示負(fù)載總線，小矩形框用來強(qiáng)調(diào)有開關(guān)的邊。

圖1 配電網(wǎng)例子

圖2展示了根據(jù)圖1產(chǎn)生的扇區(qū)圖。扇區(qū)圖中的節(jié)點(diǎn)只有12個(gè)，大大低于原分布網(wǎng)絡(luò)中的33個(gè)。所以說，扇區(qū)圖是對實(shí)際分布網(wǎng)絡(luò)的一種化簡表達(dá)法。

圖2 配電網(wǎng)所對應(yīng)的扇區(qū)圖

2 遺傳算法

演化計(jì)算是模擬自然界中生物的演化過程產(chǎn)生的一種群體導(dǎo)向的隨機(jī)搜索技術(shù)和方法，反映了自然界“物競天擇，適者生存”的思想。遺傳算法是演化計(jì)算的最大的一個(gè)分支，已經(jīng)在很多領(lǐng)域成功地開展了應(yīng)用。和其他演化計(jì)算方法一樣，在遺傳算法中始終維持著一個(gè)由個(gè)體組成的種群，每個(gè)個(gè)體代表了一個(gè)可行解。按照嚴(yán)格的定義，遺傳算法的個(gè)體是二進(jìn)制編碼的。為了滿足各種復(fù)雜的應(yīng)用，可以采用格雷碼編碼、整數(shù)編碼、實(shí)數(shù)編碼以及符號編碼等。個(gè)體代表的解對于當(dāng)前求解的問題的適應(yīng)程度即為該個(gè)體的適應(yīng)值。種群中的個(gè)體相互之間會(huì)發(fā)生雜交。在遺傳算法中，雜交是通過簡單易行的交換來實(shí)現(xiàn)的。這也就是遺傳算法和其他演化計(jì)算的分支相比最大的特點(diǎn)。此外，個(gè)體自身會(huì)發(fā)生變異。同樣地，遺傳算法的變異也是簡單易行的。雜交和變異都產(chǎn)生后代個(gè)體，后代個(gè)體將和父代個(gè)體進(jìn)行基于適應(yīng)值的競爭。選擇算子負(fù)責(zé)選出競爭中的勝利者組成下一代種群。上述步驟將循環(huán)進(jìn)行下去，直到滿足停止條件為止。

遺傳算法具有很多的優(yōu)點(diǎn)，列舉如下[19]。

1) 不需要很多附加的條件，比如可導(dǎo)性等。

2) 具有良好的并行特性。

3) 可用于求解連續(xù)、離散或者多目標(biāo)問題。

4) 能夠提供一系列解，而不是僅僅一個(gè)。

5) 總是能求出可行解。

6) 當(dāng)解空間非常大，涉及參數(shù)非常多時(shí)，十分有效。

遺傳算法最大的缺點(diǎn)是：雖然具有尋找全局最優(yōu)的可能性，但是實(shí)際的運(yùn)行結(jié)果可能與全局最優(yōu)相差甚遠(yuǎn)。所以，針對一個(gè)問題提出遺傳算法之后，還需要不斷改進(jìn)，提高算法的性能。個(gè)體編碼是完成遺傳算法的首要問題，必須先于雜交、變異或選擇算子進(jìn)行考慮。

3 配電網(wǎng)重構(gòu)遺傳算法的個(gè)體編碼

配電網(wǎng)重構(gòu)遺傳算法的個(gè)體編碼方式多種多樣，所決定的解空間大小也截然不同。本節(jié)將對現(xiàn)有的多種編碼進(jìn)行詳細(xì)分析。

3.1 編碼方式

為了便于說明，將圖2中的扇區(qū)圖利用各種編碼方式進(jìn)行表達(dá)，從而對比不同的編碼方式。由圖2可見，XS={N0,N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}，而AS={S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14,S15,S16}。N0是單獨(dú)的源節(jié)點(diǎn)，其他都是負(fù)載節(jié)點(diǎn)。由此可知，n(XS)=12，n(XF)=1，n(XL)=11，n(AS)=16，n(AST)=11，n(ANA)=5。

3.1.1 節(jié)點(diǎn)編碼

各種節(jié)點(diǎn)編碼方式中，每一位基因表示一個(gè)節(jié)點(diǎn)。文獻(xiàn)[20]中提出的前導(dǎo)法采用了n(XL)位整數(shù)基因。每位基因的值均小于n(XS)。圖3給出了用前導(dǎo)法表示的個(gè)體。圖3頂端的一行數(shù)字表達(dá)的是每位基因的上限，第二行給出了每位基因前導(dǎo)節(jié)點(diǎn)的編號，第三行標(biāo)出每個(gè)基因位的序號。

12121212121212121212120123111378141234567891011

圖3 前導(dǎo)法表示的個(gè)體

如果在前導(dǎo)法的基礎(chǔ)上，根據(jù)鄰居節(jié)點(diǎn)的信息對每個(gè)基因位進(jìn)行限制，可以進(jìn)一步對編碼方法進(jìn)行改進(jìn)?；谏鲜鏊枷?，文獻(xiàn)[21]中提出了改進(jìn)的前導(dǎo)法。圖4中給出了用改進(jìn)的前導(dǎo)法表示的個(gè)體。在這個(gè)圖中，頂端一行和第三行的意義和圖3中的相同，中間一行的值為0表示該基因位的1號鄰居節(jié)點(diǎn)是它的源，1表示2號是源，…，P表示P+1號是源。圖2中，7號基因位有3個(gè)可能相連的節(jié)點(diǎn)，分別是N3、N6和N8。按照節(jié)點(diǎn)編號決定的順序，1號鄰居是N3，2號鄰居是N6，3號則是N8。圖4中，7號基因位填的值是0，表示源是N3。

42343232233000020001001234567891011

圖4 改進(jìn)的前導(dǎo)法表示的個(gè)體

3.1.2 支路編碼

Prufer數(shù)法[22]是一種支路編碼方式。如果n(XF)=1，則需要從S1到Sn(Xs)-2共n(XS)-2位整數(shù)基因。如果n(XF)>1，必須對每棵樹都進(jìn)行上述規(guī)則的編碼。具體而言，每棵樹的支路被從左至右地填入基因位。首先，選擇樹上具有最小標(biāo)識(shí)符編號的葉子。把與之直接相連的節(jié)點(diǎn)的編號填入上述葉子的基因位，這兩點(diǎn)就可以確定一條支路。然后，刪除前一步涉及的葉子節(jié)點(diǎn)及其相關(guān)的連接，繼續(xù)在現(xiàn)存的葉子中選擇標(biāo)識(shí)符編號最小的，重復(fù)上述步驟。整個(gè)循環(huán)直到節(jié)點(diǎn)數(shù)只剩一個(gè)為止。根據(jù)圖2，一開始可選的葉子節(jié)點(diǎn)有{0，5，6，9，10}，所以0被選。由于0通向1，所以第一個(gè)基因位上填入1；0從葉子節(jié)點(diǎn)中被刪掉，5被選。由于5通向11，所以第二個(gè)基因位上填入11。根據(jù)這種方法，可以得到的編碼如圖5所示。圖5中的第一行和前面的圖相同，第二行為支路起始端的節(jié)點(diǎn)，第三行是按順序排列的節(jié)點(diǎn)號，說明了支路末端的節(jié)點(diǎn)。

121212121212121212121111873123412345678910

圖5 Prufer數(shù)法表示的個(gè)體

3.1.3 路徑編碼

路徑編碼由文獻(xiàn)[23]率先提出。文獻(xiàn)[23]中的路徑編碼需要先進(jìn)行預(yù)處理，找到幾條從源節(jié)點(diǎn)通向負(fù)載節(jié)點(diǎn)的路徑。其思想是為每一個(gè)負(fù)載節(jié)點(diǎn)開啟一個(gè)單程反饋路徑，從而保證輻射以及連接的限制。由于上述思想的時(shí)間復(fù)雜度過高，所以需要和一個(gè)路徑刪除算法與之配合。此外，路徑還要服從某些規(guī)律，所以可行性檢驗(yàn)無法避免，拉低了執(zhí)行速度。由于以上的局限性，這種方法應(yīng)用不多，在此沒有給出示意圖。

在文獻(xiàn)[23]的基礎(chǔ)之上，文獻(xiàn)[24]中提出了主鏈法。主鏈法表達(dá)的一個(gè)個(gè)體包含了從源節(jié)點(diǎn)到TS中的每個(gè)葉子節(jié)點(diǎn)的所有路徑。當(dāng)然，路徑的數(shù)量與葉子的數(shù)量相等。圖6是根據(jù)圖2得到的基于主鏈法的個(gè)體表達(dá)。圖6中，每一行各是一條路徑，用節(jié)點(diǎn)表示，這種表達(dá)方式使得個(gè)體的長度不確定。

0160110012341150123789

圖6 主鏈法表示的個(gè)體

3.1.4 邊編碼

特征向量法[25-26]屬于邊編碼方式。一共有AS位二進(jìn)制基因位，每一個(gè)基因位表示GS的一條邊。取值1表示開關(guān)閉合，0表示開關(guān)斷開。所以，個(gè)體表示如圖7所示。第一行依然是上限，第二行是基因本身，第三行是基因所對應(yīng)的邊的編號。

2222222222222222110110110111110012345678910111213141516

圖7 向量特征法表示的個(gè)體

3.1.5 斷開開關(guān)編碼

斷開開關(guān)法[27-28]，采用n(ANA)個(gè)整數(shù)位基因，每位的上限都是AS。每位表達(dá)了一個(gè)斷開的開關(guān)。如果用i來表達(dá)開關(guān)Si+1的話，圖2的個(gè)體可以表示如圖8所示。

1616161616151425812345

圖8 斷開開關(guān)法表示的個(gè)體

3.1.6 環(huán)路編碼

實(shí)際上，GS的一個(gè)基本環(huán)路只會(huì)有一個(gè)斷開的開關(guān)?；谏鲜鍪聦?shí)，產(chǎn)生了兩種環(huán)路編碼，不重復(fù)環(huán)路法[29]和重復(fù)環(huán)路法[30-31]見圖9和圖10。這兩種方法都需要預(yù)先建立一個(gè)查找表。在這個(gè)表中，每一個(gè)回路的各條邊按照順序在同一行給出。表1展示了圖2的兩種環(huán)路編碼的查找表。由表1可見，越是編號靠前的回路，其首條邊的編號越小。

561211201001234

圖9 不重復(fù)環(huán)路法表示的個(gè)體

573561224501234

圖10 重復(fù)環(huán)路法表示的個(gè)體

表1 基于圖2的不重復(fù)環(huán)路法以及重復(fù)環(huán)路法查找表

由表1可見，統(tǒng)計(jì)邊數(shù)時(shí)，不重復(fù)環(huán)路法不會(huì)重新將上一個(gè)回路出現(xiàn)過的邊再次列出。也就是說，若某條邊在前面某個(gè)回路中列出過，后面的回路即便又用到了這條邊，也要在列表中跳過。相反，重復(fù)環(huán)路法中，重復(fù)被利用的邊將不限次數(shù)的重新列出。由表1可以得到不重復(fù)環(huán)路法與重復(fù)環(huán)路法最終的個(gè)體編碼，如圖9和圖10所示。在圖9中，第一行表示環(huán)路中邊的數(shù)量。第二行表示斷開的開關(guān)的編號。具體而言，用i代表第i+1號開關(guān)。如：由表1可知，M0的第1號開關(guān)是S2，用0表示；第5號開關(guān)是S13，用4表示。第三行表示環(huán)路的編號。圖10中雖然有些環(huán)路用了更多的邊來表示，這是因?yàn)橹貜?fù)過的邊依然要列出，但是編碼的方式是類似的。

3.2 編碼的解空間大小

不同編碼方式的解空間大小是比較編碼方式優(yōu)劣的重要依據(jù)。如果編碼方式能夠涵蓋所有的可行解，那么解空間越小，表示當(dāng)前編碼方式越好。一般而言，解空間的大小可以根據(jù)以下公式計(jì)算：

(1)

式中：σ是解的個(gè)數(shù)，也就是解空間的大小。γ是編碼的長度，αi是第i位基因的上限。由式(1)可以計(jì)算出上述各種編碼方法的解空間大小。具體的計(jì)算結(jié)果見表2。

表2 解空間大小

由表2可見，屬于環(huán)路編碼的不重復(fù)環(huán)路法是解空間最小的編碼方法，該方法找出最優(yōu)解的難度相對最小。

4 結(jié) 語

配電網(wǎng)重構(gòu)是一個(gè)復(fù)雜的問題。傳統(tǒng)的解決方法包括各種貪婪算法。這些貪婪算法的最大缺點(diǎn)是無法找到全局最優(yōu)解。所以，利用遺傳算法求解配電網(wǎng)重構(gòu)成為研究的熱點(diǎn)。然而，配電網(wǎng)重構(gòu)遺傳算法種類繁多，性能還有待提高。

事實(shí)上，對于配電網(wǎng)重構(gòu)問題而言，實(shí)施遺傳算法的第一個(gè)步驟——個(gè)體編碼是非常關(guān)鍵的，直接決定了算法的性能。本文對現(xiàn)有的各種編碼進(jìn)行綜述，并比較了它們所決定的解空間大小。經(jīng)過比較可見，利用隸屬環(huán)路編碼的不重復(fù)環(huán)路法表達(dá)個(gè)體，可以將解空間規(guī)模壓縮到極致。所以，為了得到更好的配電網(wǎng)重構(gòu)遺傳算法，這種個(gè)體表達(dá)方式是很好的選擇。當(dāng)然，配合這種個(gè)體表達(dá)方式的遺傳算子也需要進(jìn)一步改進(jìn)。