基于并行禁忌搜索算法的配電網(wǎng)重構(gòu)

武曉朦，李新橋

(1.西安石油大學(xué) 電子工程學(xué)院/陜西省油氣井測控技術(shù)重點實驗室，陜西 西安 710065；2.國網(wǎng)渭南供電公司，陜西 渭南 714000)

引 言

配電網(wǎng)重構(gòu)是使系統(tǒng)運行方式更優(yōu)的重要舉措，也是配網(wǎng)自動化研究的重要內(nèi)容之一。封閉式設(shè)計、開放式運行是配電網(wǎng)運行最顯著的特點。配電網(wǎng)正常運行時，電力工作人員可以根據(jù)運行情況的差異進(jìn)行開關(guān)通斷操作以調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)，由此可以帶來兩方面的效益：一方面可均衡饋線負(fù)載水平，系統(tǒng)的電壓質(zhì)量能得到較大改善；另一方面網(wǎng)絡(luò)重構(gòu)能降低配網(wǎng)運行過程中的網(wǎng)絡(luò)損耗，有利于改善系統(tǒng)的經(jīng)濟性能。當(dāng)配電網(wǎng)在故障工況運行時，電力工作人員可以通過改變某些開關(guān)的閉合狀態(tài)隔離故障，同時閉合某些聯(lián)絡(luò)開關(guān)從而實現(xiàn)將負(fù)荷從故障線路上轉(zhuǎn)移到未故障的線路上，進(jìn)而達(dá)到縮小停電范圍、減小停電影響并在故障排除后迅速恢復(fù)供電的目的。因此對配電網(wǎng)進(jìn)行網(wǎng)絡(luò)重構(gòu)具有重要的經(jīng)濟效益和實用價值[1]。

配電網(wǎng)重構(gòu)問題屬于一種規(guī)模巨大、多優(yōu)化目標(biāo)且非線性的組合優(yōu)化問題。配電網(wǎng)重構(gòu)的數(shù)學(xué)模型種類繁多，可以是某一個性能指標(biāo)，也可以綜合2個甚至是多個指標(biāo)。比較流行的網(wǎng)絡(luò)重構(gòu)的優(yōu)化模型都是以單一目標(biāo)作為優(yōu)化指標(biāo)；具有多個優(yōu)化指標(biāo)的重構(gòu)模型也是通過數(shù)學(xué)的方法把多目標(biāo)問題轉(zhuǎn)換成單目標(biāo)優(yōu)化問題，繼而運用單目標(biāo)優(yōu)化技術(shù)進(jìn)行重構(gòu)[2]。配電網(wǎng)重構(gòu)問題的另一個研究熱點是應(yīng)用于網(wǎng)絡(luò)重構(gòu)的優(yōu)化算法，配電網(wǎng)重構(gòu)能否尋找到最優(yōu)解很大程度上取決于優(yōu)化算法的性能。國內(nèi)外學(xué)者針對配電網(wǎng)重構(gòu)問題研究出了許多不同的優(yōu)化算法，主要有傳統(tǒng)數(shù)學(xué)法、啟發(fā)式優(yōu)化算法、智能優(yōu)化算法等[3]。目前配電網(wǎng)重構(gòu)研究中最常用的是人工智能算法，主要包括人工神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、禁忌搜索算法、粒子群算法、模擬退火算法等[4]。雖然智能優(yōu)化算法尋求全局最優(yōu)解的效果好，但隨著配電網(wǎng)絡(luò)結(jié)構(gòu)的發(fā)展變化，算法中的某些關(guān)鍵參數(shù)很難確定，且重構(gòu)的時間較長，因此提高優(yōu)化算法的計算效率具有重要的意義[5]。

本文應(yīng)用禁忌搜索算法對配電網(wǎng)進(jìn)行重構(gòu)研究，針對配電網(wǎng)重構(gòu)問題的復(fù)雜性、特殊性和禁忌搜索算法是串行搜索的缺陷，提出并行禁忌搜索算法，通過設(shè)置多個禁忌長度來實現(xiàn)對解空間進(jìn)行并行同時搜索，在擴大搜索范圍的同時，提高禁忌搜索算法的效率，從而進(jìn)一步提高配電網(wǎng)重構(gòu)的效率。

1 配電網(wǎng)重構(gòu)問題的數(shù)學(xué)模型

配電網(wǎng)重構(gòu)通過調(diào)整網(wǎng)絡(luò)中開關(guān)狀態(tài)的組合方式來改變配電網(wǎng)運行結(jié)構(gòu)，從而實現(xiàn)配電網(wǎng)的經(jīng)濟運行。本文對配電網(wǎng)運行過程中的有功損耗進(jìn)行優(yōu)化，即以全網(wǎng)有功網(wǎng)絡(luò)損耗最小作為目標(biāo)函數(shù)，其具體的數(shù)學(xué)表達(dá)公式為：

(1)

式中：Nb代表網(wǎng)絡(luò)中的支路總數(shù)；Ki為開關(guān)i的狀態(tài)，分別用0和1代表開關(guān)的斷開和閉合狀態(tài)；Pi、Qi分別表示流過支路bi的有功功率和無功功率；Ri和Ui分別代表支路bi的支路電阻及其末端節(jié)點電壓。

由于配電網(wǎng)運行必須滿足封閉式設(shè)計、開放式運行的條件，因此重構(gòu)過程需要考慮以下約束條件：

(1)配電網(wǎng)系統(tǒng)的潮流方程約束。

(2)網(wǎng)絡(luò)拓?fù)浼s束，配電網(wǎng)在正常運行時呈輻射狀，網(wǎng)絡(luò)中不存在環(huán)網(wǎng)。

(3) 連通性約束。配電網(wǎng)在正常運行時必須保證對每一負(fù)荷節(jié)點都進(jìn)行供電，即網(wǎng)絡(luò)中不存在供電孤島。

(4)支路電流約束。對支路電流約束也就是對各饋線容量進(jìn)行約束，配網(wǎng)中每條支路上流過的電流不能超過該線路允許的最大電流，即：

Ii

(2)

式中，Ii和Ii,max分別代表流過支路bi的實際電流和其允許流過電流的最大值。

(5)節(jié)點電壓約束。配網(wǎng)中節(jié)點電壓必須保持在額定的范圍內(nèi)。

Ui,min

(3)

式中：Ui為節(jié)點i的實際電壓；Ui,min、Ui,max分別為節(jié)點i上允許的電壓最值。

2 并行禁忌搜索算法在配電網(wǎng)重構(gòu)中的應(yīng)用

2.1 算法簡介

禁忌搜索(Tabu Search,TS)算法的原理最早由F.Glover在20世紀(jì)70年代末提出，經(jīng)過之后近十年的發(fā)展完善，最終形成一套完整的算法。TS算法是一種基于局部鄰域搜索的全局逐步尋優(yōu)算法，它通過引入存儲結(jié)構(gòu)和禁忌準(zhǔn)則模擬人類智力思考的過程，避免迂回重復(fù)搜索，從而增加了有效搜索的次數(shù)，能實現(xiàn)搜索范圍內(nèi)的全局優(yōu)化[6]。

TS算法雖然模擬了人類智力過程，但同樣存在一定缺陷：(1)算法的優(yōu)化性能受初始解的影響較大；(2)在同時注重搜索的集中性與多樣性時，會出現(xiàn)多樣性不足的情況；(3)迭代搜索過程僅是單一狀態(tài)的移動，并非并行搜索，導(dǎo)致搜索效率不是很高。

本文采用并行禁忌搜索(Parallel Tabu Search,PTS)算法來改善TS過程是串行搜索的缺陷，PTS算法設(shè)置不同禁忌長度的禁忌表同時進(jìn)行搜索，進(jìn)一步擴大搜索范圍，提高TS算法的搜索效率[7-8]。

2.2 優(yōu)化變量的設(shè)計

針對配電網(wǎng)重構(gòu)過程中編碼復(fù)雜和計算效率低等問題，本文利用N維坐標(biāo)系的編碼策略對配電網(wǎng)中的開關(guān)進(jìn)行編碼，其中坐標(biāo)系的維數(shù)與配電網(wǎng)絡(luò)中所含環(huán)路的個數(shù)相對應(yīng)，網(wǎng)絡(luò)中環(huán)路的個數(shù)則等于網(wǎng)絡(luò)中聯(lián)絡(luò)開關(guān)的個數(shù)，即網(wǎng)絡(luò)中有幾個聯(lián)絡(luò)開關(guān)，則就有幾個環(huán)路，對應(yīng)的坐標(biāo)系就是幾維。該種編碼方式解決了大規(guī)模開關(guān)編碼復(fù)雜的問題，同時簡化了計算，提高了重構(gòu)效率[9]。

圖1 IEEE16節(jié)點網(wǎng)絡(luò)拓?fù)鋱DFig.1 IEEE 16-node network topology

如圖1所示的配電網(wǎng)絡(luò)中，(5)、(9)、(13)號開關(guān)為聯(lián)絡(luò)開關(guān)，為保證配電網(wǎng)絡(luò)的連通性與輻射性要求，圖中的某些開關(guān)必須閉合，如(1)、(2)、(3)、(16)號開關(guān)，這些開關(guān)不參與編碼。坐標(biāo)的維數(shù)即為網(wǎng)絡(luò)中聯(lián)絡(luò)開關(guān)的個數(shù)，每一維坐標(biāo)都代表一個環(huán)路，坐標(biāo)軸上的點為環(huán)內(nèi)的開關(guān)，即優(yōu)化變量。在解空間進(jìn)行尋優(yōu)時，各單環(huán)中打開的開關(guān)號碼所對應(yīng)的矢量坐標(biāo)即為狀態(tài)量。對圖1中的網(wǎng)絡(luò)進(jìn)行鄰域搜索，搜索空間如圖2所示，x，y，z軸分別代表配電網(wǎng)中的3個環(huán)路，括號外的數(shù)字為坐標(biāo)，括號內(nèi)的數(shù)字代表開關(guān)在網(wǎng)絡(luò)中的編號。圖1此時的優(yōu)化變量狀態(tài)為(5,9,13)，根據(jù)上述編碼規(guī)則，此時的狀態(tài)量為(2,2,3)。

圖2 鄰域搜索空間Fig.2 Neighborhood search space

2.3 鄰域結(jié)構(gòu)的設(shè)計

鄰域結(jié)構(gòu)是解的“移動”途徑或準(zhǔn)則，是影響算法搜索性能的重要因素之一。圖1中有3個環(huán)路，環(huán)路1、2、3的開關(guān)集合為{(4),(5),(6),(7)}，{(8),(9),(10)}，{(11),(12),(13),(14),(15)}，此時優(yōu)化變量的狀態(tài)為(5,9,13)，狀態(tài)量為(2,2,3)。在每維坐標(biāo)中針對每個狀態(tài)量分別進(jìn)行加1和減1操作，以此對應(yīng)在網(wǎng)絡(luò)拓?fù)鋱D中的開關(guān)的移動操作[10]。在環(huán)路1中，此時對應(yīng)x軸的坐標(biāo)為2，對其進(jìn)行加1和減1操作，得到一個鄰域集合為{(1,2,3),(3,2,3)}。然后再分別對環(huán)路2和環(huán)路3中的變量進(jìn)行加1和減1的“移動”操作，得到各自的鄰域集合為{(2,1,3),(2,3,3)}和{(2,2,2),(2,2,4)}，這3個鄰域集合便組成了一個初始的鄰域集合{(1,2,3),(3,2,3),(2,1,3),(2,3,3),(2,2,2),(2,2,4)}。利用N維坐標(biāo)系的編碼策略對配電網(wǎng)中的開關(guān)進(jìn)行編碼，可以大大簡化計算，提高重構(gòu)的效率。

2.4 禁忌長度和候選解集

候選解集通常由鄰域解集中目標(biāo)值或評價值最優(yōu)的鄰居組成，即擇優(yōu)選取，候選解集是當(dāng)前狀態(tài)鄰域解集的一個子集，是影響TS算法性能的關(guān)鍵參數(shù)之一。候選解集可大可小，確定依據(jù)是所求問題的特性和對算法性能的要求。禁忌長度是指在不考慮藐視準(zhǔn)則的情況下，禁忌對象不被選取的最大次數(shù)，也可以將其理解為禁忌對象在禁忌表中所對應(yīng)的任期，只有當(dāng)任期為0時才對該禁忌對象進(jìn)行解禁釋放。在解決實際問題的過程中，對算法的計算量和存儲量都有比較高的要求，為計算簡單起見，候選解集和禁忌表能小則小，即禁忌長度越小，算法的性能越好，但也不宜過小，過小時算法容易陷入局部極小。針對上述問題，本文采用多個禁忌長度同時進(jìn)行并行搜索，多個禁忌長度能控制搜索方向并擴大搜索范圍，最后通過比較使目標(biāo)函數(shù)取得最優(yōu)解。

2.5 藐視準(zhǔn)則和終止準(zhǔn)則

在TS算法的搜索過程中，候選解全部被禁忌的情況時有發(fā)生。此時若被禁對象中存在一個優(yōu)于當(dāng)前最優(yōu)解的候選解，藐視準(zhǔn)則將忽略其禁忌屬性，將該候選解直接作為當(dāng)前解以及當(dāng)前最優(yōu)解，以實現(xiàn)更高效的算法優(yōu)化性能。TS算法需要一個終止準(zhǔn)則來結(jié)束算法的搜索進(jìn)程，本文采用的結(jié)束搜索的判據(jù)是給定最優(yōu)狀態(tài)連續(xù)保持不變的最大持續(xù)迭代步數(shù)ICmax，當(dāng)最優(yōu)狀態(tài)的持續(xù)迭代步數(shù)達(dá)到限定值ICmax，算法終止。ICmax的大小與網(wǎng)絡(luò)的規(guī)模和對算法性能的要求密切相關(guān)[11]。

3 算例分析

本文通過對IEEE16節(jié)點系統(tǒng)和IEEE33節(jié)點系統(tǒng)進(jìn)行網(wǎng)絡(luò)重構(gòu)來驗證所提出方法的可行性和優(yōu)越性。IEEE16節(jié)點系統(tǒng)(算例1)如圖1所示，該系統(tǒng)有16個節(jié)點、16條支路、3個聯(lián)絡(luò)開關(guān)和13個分段開關(guān)，系統(tǒng)的額定電壓為23 kV，總負(fù)荷為28 600 kW+j 7 300 kV·A，初始網(wǎng)絡(luò)的有功網(wǎng)損為521.36 kW，最低節(jié)點電壓為0.970 2 標(biāo)幺值(p.u.)。TS的相關(guān)參數(shù)按下列要求進(jìn)行設(shè)置：根據(jù)鄰域結(jié)構(gòu)的設(shè)計規(guī)則，鄰域解個數(shù)取為6，候選解個數(shù)取3，將解空間進(jìn)行分組，取每組的禁忌長度分別為3、4、5，終止準(zhǔn)則ICmax取為5。

IEEE33節(jié)點系統(tǒng)(算例2)如圖3所示，該系統(tǒng)有33個負(fù)荷節(jié)點、37條支路、網(wǎng)絡(luò)拓?fù)渲泻?個聯(lián)絡(luò)開關(guān)、32個分段開關(guān)。該網(wǎng)絡(luò)系統(tǒng)的額定電壓為12.66 kV，總負(fù)荷為3 715 kW+j 2 300 kV·A，初始網(wǎng)絡(luò)的有功網(wǎng)損為206.68 kW，最低節(jié)點電壓為0.916 9 p.u.。優(yōu)化過程中，根據(jù)鄰域結(jié)構(gòu)的設(shè)計規(guī)則，鄰域解個數(shù)取為10，候選解個數(shù)取5，將解空間進(jìn)行分組，取每組的禁忌長度分別為3、4、5、6、7，終止準(zhǔn)則ICmax取為7。針對上述2個算例運行本文算法程序，得出相應(yīng)的計算結(jié)果，見表1。算例中各節(jié)點的電壓如圖4和圖5所示。

圖3 IEEE33節(jié)點系統(tǒng)網(wǎng)絡(luò)拓?fù)鋱DFig.3 Network topology of IEEE33 node system

圖4 IEEE16節(jié)點系統(tǒng)重構(gòu)前后節(jié)點電壓Fig.4 Node voltage of IEEE16 system before and after reconstruction

圖5 IEEE33節(jié)點系統(tǒng)重構(gòu)前后節(jié)點電壓Fig.5 Node voltage of IEEE33 system before and after reconstruction

表1 重構(gòu)結(jié)果Tab.1 Reconstruction results

由表1的計算結(jié)果可知，通過基于N維坐標(biāo)系的并行禁忌搜索算法的配電網(wǎng)重構(gòu)，IEEE16節(jié)點系統(tǒng)的網(wǎng)損降低為463.73 kW，最低節(jié)點的電壓改善為0.978 3 p.u.；IEEE33節(jié)點系統(tǒng)的網(wǎng)損降低為206.68 kW，最低節(jié)點的電壓改善為0.941 0 p.u.。因此本文算法在實現(xiàn)重構(gòu)的過程中，能有效降低配電網(wǎng)的網(wǎng)絡(luò)損耗，實現(xiàn)配電網(wǎng)的經(jīng)濟運行；同時，也能有效地改善網(wǎng)絡(luò)中節(jié)點的最低電壓，保證網(wǎng)絡(luò)中節(jié)點電壓的質(zhì)量。

針對本文的2個算例，將采用本文所提出方法得到的運算結(jié)果與文獻(xiàn)[10]和文獻(xiàn)[12]所采用方法得到的運算結(jié)果進(jìn)行對比(表2)。

表2 不同算法的重構(gòu)結(jié)果指標(biāo)對比Tab.2 Comparison of reconstruction indicators of different algorithms

由表2的分析對比結(jié)果可以看出，應(yīng)用本文方法進(jìn)行配電網(wǎng)重構(gòu)，IEEE16節(jié)點系統(tǒng)的降損率達(dá)到11.054%，迭代次數(shù)為2次；IEEE33節(jié)點系統(tǒng)的降損率為33.253%，迭代次數(shù)為3次。本文方法在降損率和迭代次數(shù)等方面的優(yōu)化效果均優(yōu)于文獻(xiàn)[10]和文獻(xiàn)[12]所采用的方法。表明其能夠在有效降低網(wǎng)損的同時較快速地尋找到全局最優(yōu)解。

4 結(jié) 論

采用N維坐標(biāo)系的編碼策略對網(wǎng)絡(luò)中開關(guān)進(jìn)行編碼，在每維坐標(biāo)中針對每個狀態(tài)量分別進(jìn)行加1和減1操作，對應(yīng)在網(wǎng)絡(luò)拓?fù)鋱D中的開關(guān)的移動操作，使得程序的編寫和計算過程復(fù)雜度降低；在應(yīng)用禁忌搜索算法時設(shè)置多個禁忌長度同時對解空間進(jìn)行搜索，進(jìn)一步提高計算效率，能夠在有效降低網(wǎng)損的同時較快速地尋找到全局最優(yōu)解，從而實現(xiàn)配電網(wǎng)重構(gòu)的目的。針對一些環(huán)路不容易劃分的復(fù)雜配電網(wǎng)絡(luò)重構(gòu)，還有待于進(jìn)一步分析研究。