配電網(wǎng)重構(gòu)中遺傳算法編碼策略的研究

三峽大學(xué)電氣與新能源學(xué)院 葉 婧 趙辛欣

1.引言

配電系統(tǒng)具有閉環(huán)結(jié)構(gòu)、開(kāi)環(huán)運(yùn)行的特點(diǎn)，包含了大量的常合分段開(kāi)關(guān)及少量常開(kāi)的聯(lián)絡(luò)開(kāi)關(guān)。在正常的運(yùn)行條件下，配電調(diào)度員根據(jù)運(yùn)行情況進(jìn)行開(kāi)關(guān)操作以調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)。通過(guò)配電網(wǎng)網(wǎng)絡(luò)重構(gòu)，一方面平衡負(fù)荷，消除過(guò)載，提高供電電壓質(zhì)量；另一方面降低網(wǎng)損，提高系統(tǒng)的經(jīng)濟(jì)性。配電網(wǎng)絡(luò)重構(gòu)是提高配電系統(tǒng)安全性和經(jīng)濟(jì)性的重要手段。理論上，在滿足各種運(yùn)行約束條件下，以網(wǎng)損最小為目標(biāo)的配電網(wǎng)絡(luò)重構(gòu)問(wèn)題是一個(gè)非線性組合優(yōu)化問(wèn)題。其中作為優(yōu)化變量的開(kāi)關(guān)數(shù)量巨大，窮舉搜索將面臨“組合爆炸”問(wèn)題。

遺傳算法(genetic algorithm，縮寫(xiě)為GA)是模擬生物進(jìn)化過(guò)程的計(jì)算模型，由于GA的整體搜索策略和優(yōu)化時(shí)不依賴梯度信息的特點(diǎn)，使其在自適應(yīng)控制、組合優(yōu)化和模式識(shí)別等方面得到了廣泛應(yīng)用。近幾年來(lái)，不少學(xué)者將GA應(yīng)用于以網(wǎng)損最低為目標(biāo)的配電網(wǎng)重構(gòu)中。由于GA并不直接作用于待求變量本身，而是先將待求變量進(jìn)行編碼，然后GA對(duì)這些編碼進(jìn)行交叉、變異等操作，從而找到最優(yōu)解，所以在使用GA前必須先選擇一種編碼方法。一般說(shuō)來(lái)，由于GA的魯棒性，它對(duì)編碼的要求并不苛刻。但是，GA中編碼的策略或方法對(duì)遺傳操作，尤其是對(duì)于交叉操作的功能有很大的影響，在很多情況下，編碼形式也就決定了交叉操作。本文將針對(duì)現(xiàn)有的遺傳算法編碼方式的計(jì)算效率進(jìn)行分析。

2.傳統(tǒng)的2進(jìn)制編碼

用2進(jìn)制表示時(shí)，一般將網(wǎng)絡(luò)中的開(kāi)關(guān)狀態(tài)用0和1表示，每個(gè)開(kāi)關(guān)占染色體的1位，0代表分閘狀態(tài)，1代表合閘狀態(tài)，各支路狀態(tài)組合在一起就形成了一條染色體，染色體的長(zhǎng)度為網(wǎng)絡(luò)中開(kāi)關(guān)的數(shù)目。如圖1所示的饋線系統(tǒng)的開(kāi)關(guān)狀態(tài)可用二進(jìn)制表示為：[1110111110111110]。種方案簡(jiǎn)潔明了，但在GA的運(yùn)行過(guò)程中會(huì)產(chǎn)生大量的不可行解，嚴(yán)重影響了GA的計(jì)算效率。

對(duì)于圖1所示的配電系統(tǒng)，一共有16條支路，一般認(rèn)為每條支路上均有開(kāi)關(guān)，按上述編碼方法，染色體長(zhǎng)度為16，該配電系統(tǒng)GA空間將有216＝32758個(gè)染色體。通過(guò)組合數(shù)學(xué)可以得出圖1中的配電系統(tǒng)GA表現(xiàn)型個(gè)體為190個(gè)[1]。有效候選解只占 1 90 / 32768= 0 .5798%。這表明：按照傳統(tǒng)的二進(jìn)制編碼方式進(jìn)行編碼，在GA運(yùn)行過(guò)程中，只能產(chǎn)生非常少的可行解，因此按這種編碼方式，搜索效率是非常低的。

圖1 IEEE典型三饋線系統(tǒng)

3.基于環(huán)路的2進(jìn)制編碼

配電網(wǎng)在正常運(yùn)行時(shí)呈放射形，并且每個(gè)節(jié)點(diǎn)的負(fù)荷都必須有電能的供給，因此配網(wǎng)中開(kāi)關(guān)的開(kāi)合并不是任意組合的。為了提高有效侯選解比例，很多文章提出了基于環(huán)路的2進(jìn)制編碼策略[1，3，4]，對(duì)于環(huán)路，不同的文章定義不同，由此也產(chǎn)生了不同的編碼方式。

3.1 一個(gè)聯(lián)絡(luò)開(kāi)關(guān)對(duì)應(yīng)一個(gè)環(huán)路的編碼策略

文獻(xiàn)[1，4]提出采用構(gòu)成同一環(huán)路的開(kāi)關(guān)在同一基因塊內(nèi)、相鄰開(kāi)關(guān)在染色體中相鄰的染色體編碼策略。文獻(xiàn)[1，4]中一個(gè)環(huán)路對(duì)應(yīng)著一個(gè)聯(lián)絡(luò)開(kāi)關(guān)。如果一個(gè)聯(lián)絡(luò)開(kāi)關(guān)合上，則會(huì)構(gòu)成一個(gè)小環(huán)，必須在此環(huán)中打開(kāi)一個(gè)分段開(kāi)關(guān)，使配網(wǎng)保持輻射型。采用這種編碼策略，不可行解數(shù)目大大降低。文獻(xiàn)[1]對(duì)圖1的配電系統(tǒng)編碼如表1所示。

表1 圖1的編碼結(jié)果

文獻(xiàn)[1，4]采用交叉操作只進(jìn)行對(duì)應(yīng)基因塊的交換，而變異操作限制在基因塊內(nèi)的遺傳操作策略。在同一個(gè)環(huán)內(nèi)即同一個(gè)基因塊內(nèi)，選擇一個(gè)開(kāi)關(guān)斷開(kāi)，以此形成初始解。變異操作時(shí)，首先選定一基因塊，然后在確定的基因塊中隨機(jī)選定一位基因?qū)⑵渲等》?，產(chǎn)生不可行解后，再按一定的方式將不可行解消除。

采用這種編碼方式，相對(duì)于傳統(tǒng)的二進(jìn)制編碼方式而言，產(chǎn)生初始解以及經(jīng)過(guò)交叉變異產(chǎn)生的候選解中不可行解的比例大大降低。但是復(fù)雜的配電系統(tǒng)環(huán)路間存在公共開(kāi)關(guān)的可能，故各環(huán)路對(duì)應(yīng)基因塊可能重疊。因此，這種一個(gè)聯(lián)絡(luò)開(kāi)關(guān)對(duì)應(yīng)一個(gè)環(huán)網(wǎng)，一個(gè)環(huán)網(wǎng)內(nèi)只允許有一個(gè)斷開(kāi)開(kāi)關(guān)的編碼方式，在存在公共開(kāi)關(guān)的系統(tǒng)中，仍然會(huì)產(chǎn)生一些不可行解。

3.2 一個(gè)回路對(duì)應(yīng)一個(gè)環(huán)路的編碼策略

文獻(xiàn)[3]提出一種新的環(huán)路的概念，即環(huán)路指的是配電網(wǎng)的開(kāi)關(guān)全部閉合時(shí)，在網(wǎng)絡(luò)中形成的閉環(huán)回路，有2種形式：（1）從配電網(wǎng)的一個(gè)電源節(jié)點(diǎn)出發(fā)，每個(gè)節(jié)點(diǎn)只經(jīng)過(guò)一次，到達(dá)另一個(gè)電源節(jié)點(diǎn)的環(huán)為第一類(lèi)環(huán)；（2）從配電網(wǎng)的某一個(gè)節(jié)點(diǎn)出發(fā)，每個(gè)節(jié)點(diǎn)只經(jīng)過(guò)一次，又回到這個(gè)節(jié)點(diǎn)的環(huán)稱為第二類(lèi)環(huán)。

對(duì)圖1所示的網(wǎng)絡(luò)，按照文獻(xiàn)[1]中環(huán)路的定義，對(duì)應(yīng)的三個(gè)環(huán)路為[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]。而按照文獻(xiàn)[3]環(huán)路的定義，則圖1中含有五個(gè)環(huán)路，分別是[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]；[1 5 10 9 7 11 16 10 12]；[2 3 4 14 13 15 16 11 7 9 10 5]。其中前4個(gè)環(huán)路為第一類(lèi)環(huán)，第5個(gè)環(huán)為第二類(lèi)環(huán)。

文獻(xiàn)[3]產(chǎn)生初始解的方法為：(1)令所有基因值均為1；(2)按順序判斷各環(huán)路中是否有斷開(kāi)的開(kāi)關(guān)，如果沒(méi)有，則隨機(jī)斷開(kāi)該環(huán)路中任一個(gè)開(kāi)關(guān)，這樣可以保證不形成閉環(huán)；如果已經(jīng)存在，不論幾個(gè)，都不再操作，因?yàn)楫?dāng)一個(gè)環(huán)路與其它環(huán)路有公共開(kāi)關(guān)時(shí)，可能出現(xiàn)一個(gè)環(huán)路中斷開(kāi)多個(gè)開(kāi)關(guān)的情況，但不會(huì)行成孤島。

按這種方法產(chǎn)生的初始解都為可行解。這種方法避免了文獻(xiàn)[1]中的初始解出現(xiàn)不可行解情況，但是在交叉和變異過(guò)程中，含有公共開(kāi)關(guān)時(shí)，仍然可能產(chǎn)生不可行解。

4.十進(jìn)制編碼策略

4.1 基于環(huán)路的編碼策略

采用二進(jìn)制編碼染色體的長(zhǎng)度很長(zhǎng)，采取開(kāi)關(guān)狀態(tài)為控制變量，用0或1表示，并且不采用任何縮短染色體長(zhǎng)度策略時(shí)，染色體的長(zhǎng)度為網(wǎng)絡(luò)開(kāi)關(guān)數(shù)總和?；谏鲜鲈蛭墨I(xiàn)[2]提出了十進(jìn)制編碼規(guī)則。

首先將全網(wǎng)的聯(lián)絡(luò)開(kāi)關(guān)以自然數(shù)編號(hào)，并在每個(gè)聯(lián)絡(luò)開(kāi)關(guān)所確定的環(huán)網(wǎng)內(nèi)將開(kāi)關(guān)單獨(dú)編號(hào)（從1到小環(huán)里的開(kāi)關(guān)總數(shù)）。遺傳編碼以聯(lián)絡(luò)開(kāi)關(guān)確定的小環(huán)網(wǎng)為基因位，該位上的值是該環(huán)網(wǎng)里打開(kāi)的開(kāi)關(guān)編號(hào)，基因位上的取值是受限制的，必須是正整數(shù)，并且從1到小環(huán)里的開(kāi)關(guān)總數(shù)。染色體長(zhǎng)度等于聯(lián)絡(luò)開(kāi)關(guān)數(shù)（環(huán)網(wǎng)數(shù)）。

文獻(xiàn)[2]中環(huán)路的定義同文獻(xiàn)[1]中相同，即一個(gè)聯(lián)絡(luò)開(kāi)關(guān)對(duì)應(yīng)著一個(gè)環(huán)路，一個(gè)環(huán)路只能存在一個(gè)斷開(kāi)的開(kāi)關(guān)。采取這種編碼方式，有效地縮短了染色體的長(zhǎng)度，但對(duì)于環(huán)路間含有公共開(kāi)關(guān)的復(fù)雜配電網(wǎng)，由于公共開(kāi)關(guān)，與文獻(xiàn)[1]中的方法存在著同樣的問(wèn)題，在初始解的形成和基因操作過(guò)程中會(huì)產(chǎn)生不可行解。并且文獻(xiàn)[2]中所提方法需要對(duì)聯(lián)絡(luò)開(kāi)關(guān)進(jìn)行編號(hào)，并且在每個(gè)環(huán)網(wǎng)中需要對(duì)每個(gè)開(kāi)關(guān)進(jìn)行重新編號(hào)，與二進(jìn)制編碼相比更為復(fù)雜。

4.2 基于隨機(jī)生成樹(shù)策略的編碼方法

常規(guī)的編碼策略容易產(chǎn)生不可行解，文獻(xiàn)[7]利用圖論的避圈策略生成樹(shù)，保證重構(gòu)后的結(jié)果為放射形，避免了不可行解的產(chǎn)生。

對(duì)配網(wǎng)中所有的開(kāi)關(guān)支路進(jìn)行十進(jìn)制編碼，將不在環(huán)路中的開(kāi)關(guān)始終保持閉合狀態(tài)，將環(huán)路中的所有支路按順序組成一個(gè)支路序列。如圖1所示網(wǎng)絡(luò)，可形成染色體:[5 10 9 7 11 16 15 2 3 4 14 13]，改變基因座的順序可以得到其它的染色體。任一染色體對(duì)應(yīng)著可以生成一棵樹(shù)，通過(guò)圖論“避圈法”文獻(xiàn)[7]保證了所生成的樹(shù)都為連通的放射型。

文獻(xiàn)[7]所提方法，在配電網(wǎng)重構(gòu)過(guò)程中可以避免不可行解的產(chǎn)生，提高了計(jì)算效率。但在染色體解碼過(guò)程中不如其它方式簡(jiǎn)單直觀。

5.總結(jié)

由于GA適用于解決大規(guī)模非線性組合優(yōu)化問(wèn)題，許多學(xué)者對(duì)其在配電網(wǎng)重構(gòu)中的應(yīng)用進(jìn)行了嘗試。本文較全面地分析比較了編碼策略對(duì)重構(gòu)計(jì)算效率的影響。隨著編碼策略不斷地改進(jìn)，侯選解的有效比例已經(jīng)大幅度地提高甚至可以完全避免不可行解的產(chǎn)生。但如何辯識(shí)和修復(fù)不可行解以及提高解碼效率是遺傳算法需要研究的問(wèn)題。

[1]畢鵬翔,劉健,劉春新.配電網(wǎng)絡(luò)重構(gòu)的改進(jìn)遺傳算法[J].電力系統(tǒng)自動(dòng)化,2002,26(2):57-61.

[2]麻秀范,張粒子.基于十進(jìn)制編碼的配網(wǎng)重構(gòu)遺傳算法[J].電工技術(shù)學(xué)報(bào),2004,19(10):65-69.

[3]楊建軍,戰(zhàn)紅,陳憲國(guó).基于遺傳算法并避免不可行解的配電網(wǎng)絡(luò)重構(gòu)優(yōu)化[J].電力系統(tǒng)保護(hù)與控制,2008,36(17):43-46.

[4]唐斌,羅安,王擊.改進(jìn)遺傳算法的編碼策略及其在配電網(wǎng)重鉤中的應(yīng)用[J].繼電器,2004,32(13):35-39.

[5]文勁宇,劉沛,程時(shí)杰.遺傳算法及其在電力系統(tǒng)中的應(yīng)用[J].電力系統(tǒng)自動(dòng)化,1996,20(10):57-60.

[6]李曉明,黃彥浩,尹項(xiàng)根.基于改良策略的配電網(wǎng)重構(gòu)遺傳算法[J].中國(guó)電機(jī)工程學(xué)報(bào),2004,24(2):49-54.

[7]歐陽(yáng)武,程浩忠,張秀斌等.基于隨機(jī)生成樹(shù)策略的配網(wǎng)重構(gòu)遺傳算法[J].高電壓技術(shù),2008,34(8):1726-1730.