孫新宇， 王 淳， 吳龍杰， 張 弛， 張 敏

（南昌大學(xué)信息工程學(xué)院，南昌 330031）

0 引 言

配電網(wǎng)重構(gòu)是通過(guò)改變支路開關(guān)狀態(tài)來(lái)改變網(wǎng)絡(luò)拓?fù)鋸亩鴥?yōu)化系統(tǒng)運(yùn)行性能的重要優(yōu)化手段。因其無(wú)需增加額外投資，利用已有供電設(shè)施提高系統(tǒng)運(yùn)行性能，故一直備受研究人員關(guān)注［1］。

配電網(wǎng)重構(gòu)是一個(gè)離散、非線性的大規(guī)模組合優(yōu)化問(wèn)題，屬于NP 難問(wèn)題。隨著配電網(wǎng)規(guī)模增大和網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性增加，重構(gòu)優(yōu)化過(guò)程中產(chǎn)生組合爆炸現(xiàn)象，導(dǎo)致問(wèn)題難以求解。大規(guī)模的配電網(wǎng)重構(gòu)涉及到大量的拓?fù)浞治龊统绷饔?jì)算，消耗大量時(shí)間，給實(shí)際應(yīng)用帶來(lái)困難。當(dāng)前配電網(wǎng)重構(gòu)算法［2-5］大多適用于中小規(guī)模配電網(wǎng)，少有方法在大規(guī)模配電網(wǎng)中仍具有可用性。為尋找適合求解大規(guī)模配電網(wǎng)重構(gòu)的方法，一些學(xué)者展開了研究工作。文獻(xiàn)［6］中提出了一種基于基本環(huán)矩陣的無(wú)不可行解編碼方法，縮小了解空間的范圍。文獻(xiàn)［7］在文獻(xiàn)［6］的基礎(chǔ)上，提出了一種基于自適應(yīng)負(fù)荷調(diào)整網(wǎng)絡(luò)矩陣的配電網(wǎng)重構(gòu)方法，不僅去除了解空間中的不可行解，還去除了可行解中的大量劣解，進(jìn)一步精簡(jiǎn)了解空間。文獻(xiàn)［8］中提出了一種基于圖論的配電網(wǎng)重構(gòu)方法，將配電網(wǎng)重構(gòu)看作是在網(wǎng)絡(luò)拓?fù)鋱D中尋找最小生成樹問(wèn)題，利用Prim算法進(jìn)行求解。文獻(xiàn)［9］中提出了一種三段式的開關(guān)斷開與交換算法，結(jié)合了支路交換法和逐次打開開關(guān)法，原理簡(jiǎn)單、性能穩(wěn)定。上述方法雖然具備求解大規(guī)模配電網(wǎng)重構(gòu)的能力，但普遍存在求解精度不高、求解時(shí)間過(guò)長(zhǎng)的問(wèn)題。文獻(xiàn)［10］中將配電網(wǎng)重構(gòu)模型轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問(wèn)題，應(yīng)用CPLEX 規(guī)劃軟件進(jìn)行求解，在求解精度上有良好的效果，但是會(huì)消耗大量的求解時(shí)間，缺乏實(shí)際應(yīng)用價(jià)值。

變種群模因算法（Variable Population Memetic Algorithm，VPMA）［11］在傳統(tǒng)模因算法的基礎(chǔ)上，增加了種群規(guī)模改變策略，為求解大規(guī)模組合優(yōu)化問(wèn)題提供了一個(gè)通用的解決框架。本文嘗試將VPMA 應(yīng)用于求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題。針對(duì)配電網(wǎng)重構(gòu)問(wèn)題的特點(diǎn)，在VPMA框架中引入啟發(fā)式算法中的開關(guān)組思想，應(yīng)用改進(jìn)開關(guān)組法確定兩個(gè)初始個(gè)體及其鄰域搜索空間，進(jìn)而在種群交叉環(huán)節(jié)引入雙主干交叉算子，從而使得個(gè)體的優(yōu)良特征得以保留，應(yīng)用禁忌搜索法在鄰域空間內(nèi)進(jìn)行局部搜索，采用動(dòng)態(tài)變更種群規(guī)模的方式提高全局搜索能力。最后，在IEEE33、Taipower84、Bus119、Bus136、Bus417 五個(gè)不同規(guī)模的系統(tǒng)中進(jìn)行配電網(wǎng)重構(gòu)仿真，并與多個(gè)算法進(jìn)行比較，驗(yàn)證算法性能。

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

本文研究的重點(diǎn)在于提出一種算法解決大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題。因此，數(shù)學(xué)模型以常用的系統(tǒng)有功網(wǎng)損最小為優(yōu)化目標(biāo)。配電網(wǎng)重構(gòu)的數(shù)學(xué)模型如下：

式中：NE為閉合支路的集合；Pk，loss為支路k的有功功率損耗；rk為支路k的電阻；Pk、Qk、Uk為支路k的首端有功、無(wú)功功率和電壓幅值；A 為節(jié)點(diǎn)-支路關(guān)聯(lián)矩陣；P為饋線潮流向量；D 為負(fù)荷需求向量；Sk為流過(guò)支路k的功率；Sk，max為支路k的線路容量；m為節(jié)點(diǎn)總數(shù)；Ui、Ui，max、Ui，min分別為節(jié)點(diǎn)i的電壓及上下限；l為閉合支路總數(shù)；d（i，isubstation）為節(jié)點(diǎn)i到電源節(jié)點(diǎn)isubstation距離。式（1）為目標(biāo)函數(shù)；式（2）為潮流約束；式（3）為支路容量約束；式（4）為節(jié)點(diǎn)電壓約束；式（5）是保證網(wǎng)絡(luò)為輻射網(wǎng)的必要條件；式（6）表示節(jié)點(diǎn)i與電源節(jié)點(diǎn)間的距離是一個(gè)有限值，即網(wǎng)絡(luò)無(wú)孤立節(jié)點(diǎn)。式（5）、（6）共同組成了的網(wǎng)絡(luò)的輻射狀約束以及連通性約束。

2 VPMA的基本框架

VPMA從僅包含兩個(gè)個(gè)體的初始種群出發(fā)，利用種群交叉和局部尋優(yōu)策略增強(qiáng)算法的局部探索能力，利用種群規(guī)模改變策略增強(qiáng)全局搜索能力。VPMA基本框架的流程如圖1 所示，其中包含種群初始化、種群交叉、局部尋優(yōu)、種群更新和種群規(guī)模改變5 個(gè)步驟。首先在種群初始化環(huán)節(jié)產(chǎn)生兩個(gè)個(gè)體作為初始種群；隨后在種群交叉環(huán)節(jié)中，種群中的個(gè)體兩兩交叉得到子代集合；選取最優(yōu)子代進(jìn)入局部尋優(yōu)環(huán)節(jié)進(jìn)行進(jìn)一步優(yōu)化；局部尋優(yōu)后獲得的個(gè)體替換種群中的較劣個(gè)體從而完成種群更新；當(dāng)算法陷入搜索停滯，即最優(yōu)個(gè)體經(jīng)歷預(yù)設(shè)次數(shù)的迭代后仍未更新時(shí)，VPMA 根據(jù)當(dāng)前種群大小動(dòng)態(tài)調(diào)整種群規(guī)模，重新執(zhí)行種群交叉、局部尋優(yōu)等操作，直到滿足收斂條件后輸出最終結(jié)果。

圖1 變種群模因算法基本框架流程圖

3 VPMA的配電網(wǎng)重構(gòu)

3.1 配電網(wǎng)重構(gòu)編碼策略

本文采用基于基本環(huán)路的編碼策略［12］，種群中的個(gè)體X 以n維向量的形式表達(dá)，即X =［x1，x2，…，xn］T，其中n為個(gè)體的維度。策略中個(gè)體的維度等于配電網(wǎng)中的基本環(huán)路數(shù)，大幅降低了變量維度，提高了計(jì)算效率。

文獻(xiàn)［13］中提出的環(huán)路搜索算法能夠通過(guò)逐步加入余枝的方法，高效地搜索到網(wǎng)絡(luò)的基本環(huán)路。利用貪婪思想優(yōu)先加入能構(gòu)成包含最小支路數(shù)的基本環(huán)路的余枝，使搜索到的環(huán)路包含的邊數(shù)量最少。圖2所示是以IEEE16 節(jié)點(diǎn)系統(tǒng)為例的搜索及編碼過(guò)程。具體步驟如下：

（1）從一個(gè)完全閉合的網(wǎng)絡(luò)出發(fā)，如圖2（a）所示，以電源節(jié)點(diǎn)（節(jié)點(diǎn)1）為根節(jié)點(diǎn)，應(yīng)用廣度優(yōu)先搜索生成廣度優(yōu)先樹，該樹的任意節(jié)點(diǎn)到根節(jié)點(diǎn)距離最短，如圖2（b）所示。

（2）利用貪婪思想，優(yōu)先加入能構(gòu)成包含最小支路數(shù)的基本環(huán)路的余枝，并記錄余枝與基本環(huán)路的對(duì)應(yīng)關(guān)系，直至所有余枝都加入網(wǎng)絡(luò)，完成對(duì)基本環(huán)路的搜索。如圖2（c）～（e）所示，加入余枝的順序?yàn)椋? ～12、7 ～9、5 ～14。分別構(gòu)成包含支路數(shù)5、6、7 的基本環(huán)路。

圖2 基本環(huán)路搜索過(guò)程

（3）在示例系統(tǒng)中，基本環(huán)路數(shù)為3，則個(gè)體X可表示X=［x1，x2，x3］T，x1的取值集合為整數(shù)［1 5］，分別對(duì)應(yīng)環(huán)路1 中開關(guān)1 ～6、6 ～8、8 ～12、12 ～11、11～1 的編號(hào)（編號(hào)可以是任意的）。同理，x2的取值集合為整數(shù)［1 6］，x3的取值集合為整數(shù)［1 7］，當(dāng)xn取值為p時(shí)，表示環(huán)路n中編號(hào)為p的開關(guān)斷開。

3.2 改進(jìn)開關(guān)組法的種群初始化策略

VPMA應(yīng)用種群初始化環(huán)節(jié)生成僅包含兩個(gè)個(gè)體的初始種群P=｛X1，X2｝。初始種群理論上既可以隨機(jī)生成，也可以通過(guò)快速的尋優(yōu)算法搜索得到。將較優(yōu)的精英個(gè)體作為初始種群更符合VPMA的思想，原因是此時(shí)搜索剛剛開始，需要在完整的搜索空間中迅速定位到解質(zhì)量較高、比較有希望出現(xiàn)最優(yōu)解的搜索區(qū)域，再利用局部尋優(yōu)策略對(duì)該區(qū)域進(jìn)行探索，而僅通過(guò)局部尋優(yōu)策略確定搜索方向是非常耗時(shí)的。因此能迅速確定搜索區(qū)域成為了對(duì)種群初始化環(huán)節(jié)的要求。

開關(guān)組法是一種用于求解配電網(wǎng)重構(gòu)的啟發(fā)式方法［14］，此方法原理簡(jiǎn)單、速度快并有較好的尋優(yōu)性能，但是僅適用于基本環(huán)路數(shù)少的小規(guī)模系統(tǒng)。本文保留原方法中開關(guān)組的思想，改變其搜索方式來(lái)適應(yīng)VPMA的基本框架，作為種群初始化環(huán)節(jié)中生成初始種群的方法。

開關(guān)組法將每個(gè)聯(lián)絡(luò)開關(guān)和其左右相鄰的2 個(gè)分段開關(guān)同時(shí)考慮。這3 個(gè)開關(guān)中必須斷開一個(gè)，閉合另外兩個(gè)以保持輻射狀結(jié)構(gòu)。因此共有3 種可能的開關(guān)狀態(tài)組合，這3 種狀態(tài)構(gòu)成了一個(gè)開關(guān)組。若系統(tǒng)中有k個(gè)聯(lián)絡(luò)開關(guān)，則共有k個(gè)開關(guān)組形成3k個(gè)開關(guān)組合。然而，當(dāng)k增大時(shí)，開關(guān)組合的數(shù)量呈指數(shù)型增加，會(huì)導(dǎo)致計(jì)算負(fù)擔(dān)過(guò)重甚至無(wú)法計(jì)算，這顯然不符合快速產(chǎn)生高質(zhì)量初始種群的要求。因此本文針對(duì)大規(guī)模配電系統(tǒng)對(duì)開關(guān)組法進(jìn)行改進(jìn)，整體思想為將所有開關(guān)組分組處理、隨機(jī)重組生成初始種群，具體步驟如下：

（1）確定開關(guān)組。對(duì)一個(gè)所有開關(guān)都閉合的網(wǎng)絡(luò)進(jìn)行環(huán)路搜索后，確定其基本環(huán)路和對(duì)應(yīng)的余枝。將搜索到的所有余枝看作網(wǎng)絡(luò)初始的聯(lián)絡(luò)開關(guān)，根據(jù)聯(lián)絡(luò)開關(guān)在基本環(huán)路中的編號(hào)可以形成初始解，結(jié)合左右相鄰分段開關(guān)即可確定開關(guān)組。

（2）分組。設(shè)系統(tǒng)中有k個(gè)開關(guān)組，k1個(gè)為一組，隨機(jī)分為k2=［k/k1］+1 組，其中［］為向下取整符號(hào)。前k2-1 組中每組包含k1個(gè)開關(guān)組，第k2組中包含k3=Kmodk1（k3≤k1）個(gè)開關(guān)組，其中mod為取余符號(hào)。

（3）抽取。前k2-1 組每組中均會(huì)形成3k1個(gè)開關(guān)組合，第k2組會(huì)形成3k3個(gè)開關(guān)組合，將這（k2-1）×3k3+3k3組合以組為單位，前k2-1 組每組中不重復(fù)的抽取一個(gè)開關(guān)組合，第k2組按同樣的方式抽取，但由于第k2組包含的開關(guān)組合數(shù)較少，抽取完畢后可重復(fù)抽取，不影響算法性能。

（4）組合。抽取出的k2個(gè)開關(guān)組合按照其在模因序列中對(duì)應(yīng)的位置可組合成一個(gè)完成的個(gè)體。

（5）反復(fù)執(zhí)行步驟（3）共3k1次，即可獲得包含3k1個(gè)個(gè)體的候選初始種群，對(duì)所有開關(guān)組合進(jìn)行評(píng)價(jià)，從中選取兩個(gè)精英個(gè)體（目標(biāo)函數(shù)值最小）即可完成種群初始化。

此方法通過(guò)對(duì)參數(shù)k1的設(shè)置，可以將生成的候選種群數(shù)限制在3k1個(gè)，避免了指數(shù)爆炸的問(wèn)題，同時(shí)保證了生成種群的多樣性，實(shí)現(xiàn)了計(jì)算負(fù)擔(dān)和全局搜索能力的平衡，在算例測(cè)試中具有良好的效果。

3.3 雙主干交叉算子的種群交叉策略

種群交叉通過(guò)對(duì)現(xiàn)有個(gè)體的交叉重組，構(gòu)建新個(gè)體，常用的方法有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等。但是這些通用的交叉算子往往沒(méi)有考慮研究問(wèn)題的特性，搜索效率不高。為特定的研究問(wèn)題設(shè)計(jì)專用的交叉算子通常會(huì)更加有利于問(wèn)題的求解，通過(guò)交叉方式的設(shè)計(jì)，子代可以更容易從父代繼承優(yōu)良特征，避免低劣特征，從而提高搜索性能。

本文將雙主干交叉算子［15］引入到種群交叉環(huán)節(jié)，用于解決配電網(wǎng)重構(gòu)問(wèn)題，具體方法如下。

令X1、X2為兩個(gè)父代個(gè)體，比較兩個(gè)體對(duì)應(yīng)位置上的元素，可以將組成個(gè)體的所有元素分為共有元素、獨(dú)有元素和其余元素，其定義如下：

（1）令XA=｛xA1，xA2，…，xAn｝為X1、X2共有元素的集合，xAi=x1i∩x2i（i=1，2，…，n），即X1、X2對(duì)應(yīng)位置上相同的元素，式中n為個(gè)體的維數(shù)，i為元素在個(gè)體中的位置編號(hào)（下同）。

（2）令XB=｛xB1，xB2，…，xBn｝為X1、X2獨(dú)有元素的集合，xBi=（x1i∪x2i）/（x1i∩x2i）（i=1，2，…，n），即X1、X2對(duì)應(yīng)位置上不同的元素，式中/為差集符號(hào)，即第一個(gè)集合減去第二個(gè)集合包含的元素（下同）。

（3）令XC=｛xC1，xC2，…，xCn｝為X1、X2其余元素的集合，xCi= Xi/（x1i∪x2i）（i=1，2，…，n），即未在X1、X2中出現(xiàn)，但在取值集合中的元素，其中Xi是位置i處元素的取值集合。

根據(jù)給定的父代個(gè)體，子代個(gè)體經(jīng)由以下3 步形成：

（1）子代繼承父代所有的共有元素，形成子代的第1 個(gè)主干。

（2）將不同位置上的獨(dú)有元素相互結(jié)合，形成子代的第2 個(gè)主干，第1 主干和第2 主干按照對(duì)應(yīng)位置組合即可得到完整的子代個(gè)體。其中，第2 主干的個(gè)數(shù)決定子代集合中的個(gè)體數(shù)，即若XB中包含j個(gè)不為?的集合，則共會(huì)生成2j個(gè)子代個(gè)體。

（3）在兩個(gè)主干組合時(shí)，第2 主干中的獨(dú)有元素會(huì)有sp的概率變異成新的元素，隨機(jī)抽取XC中的其余元素作為新元素，本文中sp取值為0.2。

3.4 禁忌搜索的局部尋優(yōu)策略

局部尋優(yōu)環(huán)節(jié)關(guān)系到算法的局部探索能力，是VPMA中重要的組成部分。局部尋優(yōu)策略的好壞決定了算法對(duì)某一特定區(qū)域的搜索是否充分。局部尋優(yōu)環(huán)節(jié)可以采用多種搜索策略，例如爬山法、模擬退火法、禁忌搜索法等，由于禁忌搜索具有搜索范圍廣、收斂速度快、能夠避免陷入局部最優(yōu)解等特點(diǎn)，本文在局部尋優(yōu)環(huán)節(jié)中采用禁忌搜索策略。

禁忌搜索是一種基于局部鄰域搜索的逐步尋優(yōu)策略，其本質(zhì)上是不斷向目標(biāo)函數(shù)數(shù)值下降方向進(jìn)行搜索，優(yōu)勢(shì)在于引入了禁忌表和禁忌準(zhǔn)則，以此避免陷入局部最優(yōu)，搜索更多區(qū)域。其關(guān)鍵參數(shù)有：鄰域結(jié)構(gòu)、禁忌表、禁忌長(zhǎng)度、藐視準(zhǔn)則和終止判據(jù)。本小節(jié)將給出局部尋優(yōu)環(huán)節(jié)關(guān)鍵參數(shù)的設(shè)置及具體流程。

3.4.1 鄰域結(jié)構(gòu)

種群交叉環(huán)節(jié)完成后，對(duì)子代集合中的最優(yōu)個(gè)體進(jìn)行局部尋優(yōu)。本文通過(guò)對(duì)個(gè)體每維坐標(biāo)中的元素執(zhí)行加1 和減1 的操作來(lái)形成鄰域結(jié)構(gòu)，對(duì)應(yīng)在網(wǎng)絡(luò)拓?fù)渲袆t表現(xiàn)為聯(lián)絡(luò)開關(guān)在其所在的基本環(huán)路中向左右相鄰開關(guān)的移動(dòng)操作。設(shè)個(gè)體為［2，3，4］T，則對(duì)應(yīng)的鄰域集合為｛［1，3，4］T，［3，3，4］T，［2，2，4］T，［2，4，4］T，［2，3，3］T，［2，3，5］T｝，取鄰域集合中的最優(yōu)個(gè)體作為候選解，進(jìn)行下一次搜索。

3.4.2 禁忌表與禁忌長(zhǎng)度

禁忌表和禁忌長(zhǎng)度的設(shè)置是禁忌搜索策略的核心所在。本文將禁忌對(duì)象設(shè)置為歷次迭代過(guò)程中搜索到的最優(yōu)個(gè)體，禁忌長(zhǎng)度TL=20，每搜索一次禁忌對(duì)象的禁忌長(zhǎng)度減1，當(dāng)禁忌長(zhǎng)度為0 時(shí)從禁忌表中解禁。

3.4.3 禁忌搜索的藐視準(zhǔn)則和終止判據(jù)

為應(yīng)對(duì)搜索過(guò)程中出現(xiàn)的所有候選解均被禁忌的情況，設(shè)置了藐視準(zhǔn)則，即當(dāng)候選解集中出現(xiàn)優(yōu)于當(dāng)前最優(yōu)個(gè)體的候選解時(shí)，忽略其禁忌屬性，直接設(shè)為新的當(dāng)前最優(yōu)個(gè)體并將其禁忌長(zhǎng)度調(diào)整為最大。規(guī)定終止判據(jù)為當(dāng)前最優(yōu)個(gè)體持續(xù)迭代次數(shù)Ic大于最大持續(xù)次數(shù)Icmax。

3.4.4 局部尋優(yōu)搜索流程

局部尋優(yōu)環(huán)節(jié)具體搜索流程如下：

（1）令種群交叉后產(chǎn)生的子代集合中的最優(yōu)個(gè)體為禁忌搜索的當(dāng)前最優(yōu)個(gè)體，設(shè)置關(guān)鍵參數(shù)Icmax=3，TL=20，Ic=0，禁忌表為?。

（2）以當(dāng)前最優(yōu)個(gè)體為中心，生成鄰域集合，并選取鄰域集合內(nèi)的最優(yōu)個(gè)體作為候選解。

（3）判斷候選解是否滿足藐視準(zhǔn)則，若滿足，則直接將候選解取為當(dāng)前最優(yōu)個(gè)體并將其禁忌長(zhǎng)度調(diào)整為最大；若不滿足則判斷其是否在禁忌表中，若在禁忌表中則將鄰域解集內(nèi)非禁忌對(duì)象中的最優(yōu)個(gè)體取為當(dāng)前最優(yōu)個(gè)體，若不在則將候選解取為當(dāng)前最優(yōu)個(gè)體并加入禁忌表，迭代次數(shù)Ic=Ic+1。

（4）判斷是否滿足終止判據(jù)，若滿足，則結(jié)束禁忌搜索，對(duì)當(dāng)前最優(yōu)個(gè)體進(jìn)行種群更新操作；若不滿足，則返回步驟（2），同時(shí)禁忌表內(nèi)所有對(duì)象的禁忌長(zhǎng)度減1。

3.5 種群更新策略

局部尋優(yōu)環(huán)節(jié)優(yōu)化后的個(gè)體將經(jīng)過(guò)種群更新環(huán)節(jié)決定是否重新插入原種群，本文采用的策略為：若子代個(gè)體不與原種群中的任意個(gè)體相同且優(yōu)于其中最劣個(gè)體，則替換最劣個(gè)體。同時(shí)引入變量g記錄種群更新停滯次數(shù)，當(dāng)種群未得到更新，即子代個(gè)體未重插入種群時(shí)，g=g+1；當(dāng)種群得到更新時(shí)g=0。當(dāng)g達(dá)到最大停滯次數(shù)gmax時(shí)（本文設(shè)置為5），算法陷入了搜索停滯，此時(shí)進(jìn)入種群規(guī)模改變環(huán)節(jié)。

3.6 種群規(guī)模改變策略

3.6.1 種群規(guī)模擴(kuò)張策略

當(dāng)搜索陷入停滯時(shí)，算法通過(guò)引入新個(gè)體的方式增大種群規(guī)模，達(dá)到增加種群的多樣性，跳出搜索停滯。本文設(shè)定每進(jìn)入一次種群規(guī)模擴(kuò)張環(huán)節(jié)，在種群中增加一個(gè)新的精英個(gè)體。每個(gè)新個(gè)體都遵循3.2 ～

3.4 小節(jié)的方法產(chǎn)生，但只有當(dāng)新個(gè)體不與原種群中任意個(gè)體相同時(shí)才會(huì)加入種群。

3.6.2 種群規(guī)模收縮策略

種群規(guī)模過(guò)大有利于增加種群多樣性的同時(shí)也意味著更重的計(jì)算負(fù)擔(dān)，因此引入最大種群規(guī)模pmax，當(dāng)種群規(guī)模擴(kuò)張到最大時(shí)，將執(zhí)行種群規(guī)模收縮策略，縮小種群規(guī)模。種群規(guī)模收縮的意義在于：①種群規(guī)模過(guò)大會(huì)消耗大量計(jì)算資源，形成巨大的計(jì)算負(fù)擔(dān)，降低搜索效率；②當(dāng)種群規(guī)模過(guò)大但搜索仍陷入停滯時(shí)，意味著算法在當(dāng)前搜索區(qū)域內(nèi)已搜索殆盡，無(wú)法搜索到更優(yōu)解，需要開拓新的搜索區(qū)域。

將種群收縮為只包含兩個(gè)精英個(gè)體的小種群，保留原種群中的最優(yōu)個(gè)體作為其中一個(gè)精英個(gè)體，另一個(gè)精英個(gè)體遵循3.2 ～3.4 小節(jié)的方法產(chǎn)生。通過(guò)混合歷史最優(yōu)個(gè)體和高質(zhì)量的新個(gè)體，新種群將會(huì)繼承過(guò)往的搜索成果并開拓新的搜索區(qū)域。pmax是算法中十分重要的參數(shù)，它能平衡計(jì)算負(fù)擔(dān)與種群多樣性，并決定搜索軌跡和算法性能，pmax在不同規(guī)模的系統(tǒng)中宜取不同的值。

3.7 終止判據(jù)

本文采用的終止判據(jù)為算法搜索到的最優(yōu)個(gè)體連續(xù)保持不變的迭代次數(shù)t達(dá)到最大迭代次數(shù)tmax，tmax的取值與網(wǎng)絡(luò)規(guī)模和算法性能要求有密切的關(guān)系，其值過(guò)小時(shí)，會(huì)導(dǎo)致無(wú)法充分遍歷搜索空間，陷入局部最優(yōu)；其值過(guò)大時(shí)，會(huì)導(dǎo)致搜索到最優(yōu)解后難以跳出循環(huán)，降低搜索效率。

4 算例分析

選用IEEE33、Taipower84、Bus119、Bus 136 和Bus 417 節(jié)點(diǎn)系統(tǒng)驗(yàn)證算法性能［16］，基本數(shù)據(jù)如下：

（1）IEEE33 節(jié)點(diǎn)系統(tǒng)額定電壓12.66 kV，共33個(gè)節(jié)點(diǎn)，37 條支路，5 個(gè)基本環(huán)路，總負(fù)荷3 715 kW+j2 300 kvar。（2）Taipower84 節(jié)點(diǎn)系統(tǒng)額定電壓11.4 kV，共84 個(gè)節(jié)點(diǎn)，96 條支路，13 個(gè)基本環(huán)路，總負(fù)荷28 351 kW+j20 700 kvar。（3）Bus119 節(jié)點(diǎn)系統(tǒng)額定電壓11 kV，共119 個(gè)節(jié)點(diǎn)，133 條支路，15 個(gè)基本環(huán)路，總負(fù)荷22 710 kW+j17 041 kvar。

（4）Bus136 節(jié)點(diǎn)系統(tǒng)額定電壓13.8 kV，共136個(gè)節(jié)點(diǎn)，156 條支路，21 個(gè)基本環(huán)路，總負(fù)荷18 314 kW+j7 932.5 kvar。（5）Bus417 節(jié)點(diǎn)系統(tǒng)額定電壓10 kV，共415 個(gè)節(jié)點(diǎn)，473 條支路，59 個(gè)基本環(huán)路，總負(fù)荷27 958 kW+j13 237 kvar。

4.1 VPMA法與其他算法性能比較

算法在各系統(tǒng)中的參數(shù)設(shè)置如表1 所示。

表1 不同系統(tǒng)中參數(shù)設(shè)置

表2展示了VPMA的運(yùn)行結(jié)果以及與開關(guān)斷開與交換法（Switch Opening and Exchange Method，SOE）、最小生成樹法（Minimum Spanning Tree，MST）、局部搜索算法（Local Search，LS）和混合整數(shù)非線性規(guī)劃法（Mixed-integer Nonlinear Programming，MINLP）的比較。表3 展示了由VPMA求得的各網(wǎng)絡(luò)最優(yōu)重構(gòu)結(jié)果。

表2最優(yōu)網(wǎng)損一行中IEEE33、Taipower84、Bus119和Bus136 系統(tǒng)的最優(yōu)網(wǎng)損為公認(rèn)全局最優(yōu)網(wǎng)損［17］，Bus417 系統(tǒng)的最優(yōu)網(wǎng)損為文獻(xiàn)［10］應(yīng)用混合整數(shù)線性規(guī)劃法求出的最小網(wǎng)損。Bus119 系統(tǒng)［18］由于原數(shù)據(jù)中出現(xiàn)多處網(wǎng)絡(luò)圖與數(shù)據(jù)表不吻合的情況，故許多文獻(xiàn)中的計(jì)算結(jié)果不一致。本文算法以及與之比較的其他算法均采用的是文獻(xiàn)［16］中的數(shù)據(jù)以及網(wǎng)絡(luò)拓?fù)?。? 括號(hào)中的值為所得網(wǎng)損的相對(duì)誤差，計(jì)算方法為

表2 不同算法結(jié)果比較

表3 VPMA法求得各網(wǎng)絡(luò)最優(yōu)重構(gòu)結(jié)果

其中：f（S*）為算法計(jì)算出的網(wǎng)損；f（S*min）為最優(yōu)網(wǎng)損。

由表2 可以看出，VPMA在求解不同系統(tǒng)時(shí)，相對(duì)誤差在0% ～0.27%，說(shuō)明了其在不同規(guī)模的系統(tǒng)中均有較高的精確度。在求解IEEE33、Taipower84、Bus119 系統(tǒng)時(shí)，VPMA 與MINLP 均能獲得最優(yōu)解，而MST、LS、SOE 獲得的解有不同程度的相對(duì)誤差。在Bus 136 和Bus 417 系統(tǒng)中，VPMA 分別有0.01%和0.27%的相對(duì)誤差，均低于MST 和LS；MINLP 在Bus136 系統(tǒng)的相對(duì)誤差比VPMA低0.01%，但在Bus 417 系統(tǒng)中比VPMA 高17. 63%，說(shuō)明VPMA 較MINLP有更好的求解大規(guī)模系統(tǒng)的能力。SOE 在Bus136 系統(tǒng)的相對(duì)誤差比VPMA 高0. 28%，在Bus 417 系統(tǒng)中比VPMA 低0.05%。SOE 代碼可在文獻(xiàn)［9］中獲得，本文將SOE 和VPMA 代碼運(yùn)行在帶有Intel（R）Core（TM）i7-5500U CPU@2.4 GHz 處理器，12.0GRAM的計(jì)算機(jī)系統(tǒng)MATLAB 軟件中，分別運(yùn)行100 次，運(yùn)行結(jié)果如表4 所示。

表4 VPMA法與SOE法結(jié)果比較

對(duì)VPMA與SOE在平均網(wǎng)損、最優(yōu)解比例和平均耗時(shí)三方面的性能進(jìn)行比較。在表4 平均網(wǎng)損一欄中，VPMA與SOE 在IEEE33 和Bus119 系統(tǒng)中的結(jié)果相同且與最優(yōu)解相等。在Taipower84 和Bus136 系統(tǒng)中VPMA結(jié)果比SOE低0.04%和0.28%。在Bus417系統(tǒng)中兩者相差0.05%，說(shuō)明兩者均具備求解大規(guī)模配電網(wǎng)重構(gòu)的能力，且在節(jié)點(diǎn)數(shù)少于417 的系統(tǒng)中VPMA優(yōu)于SOE，在Bus417 節(jié)點(diǎn)系統(tǒng)中SOE求得的解略優(yōu)于VPMA。在最優(yōu)解比例一欄，SOE 僅在IEEE33和Bus119 系統(tǒng)中可求得最優(yōu)解，其余系統(tǒng)均無(wú)法獲得最優(yōu)解。VPMA在IEEE33、Taipower84 和Bus119 系統(tǒng)中最優(yōu)解比例均為100%，在Bus136 系統(tǒng)中比例為40%，在Bus417 系統(tǒng)兩種方法均獲得了與最優(yōu)解近似的次優(yōu)解?？梢妼?duì)于大型復(fù)雜網(wǎng)絡(luò)，VPMA 獲得的最優(yōu)解比例明顯高于SOE。在平均耗時(shí)一欄，VPMA 在除Bus136 系統(tǒng)外的不同規(guī)模系統(tǒng)中耗時(shí)均明顯少于SOE，平均耗時(shí)縮短了21.6% ～80.4%；在Bus136 系統(tǒng)中，VPMA雖耗時(shí)較長(zhǎng)，但其平均網(wǎng)損降低，最優(yōu)解比例明顯提高，SOE 在求解Bus136 系統(tǒng)重構(gòu)問(wèn)題時(shí)，快速收斂到誤差較大的次優(yōu)解，說(shuō)明其沒(méi)有對(duì)搜索空間進(jìn)行充分探索。可見在求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題時(shí)，VPMA較SOE效率更高。綜上所述，VPMA 較其他同類算法速度快、精度高，在求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題中有明顯的優(yōu)勢(shì)。

4.2 VPMA中不同步驟的影響

VPMA的基本思想為應(yīng)用種群初始化環(huán)節(jié)快速搜索出較好的精英個(gè)體，進(jìn)而應(yīng)用局部尋優(yōu)環(huán)節(jié)進(jìn)一步優(yōu)化個(gè)體，隨后通過(guò)種群規(guī)模擴(kuò)張和種群規(guī)模收縮環(huán)節(jié)增加種群多樣性，最終確定最優(yōu)個(gè)體。

為分析以上4 個(gè)步驟對(duì)算法性能的影響和在搜索最優(yōu)解過(guò)程中的貢獻(xiàn)，本節(jié)將分析執(zhí)行以上各步驟后的時(shí)間消耗和系統(tǒng)網(wǎng)損。定義VPMA Ⅰ為算法執(zhí)行種群初始化環(huán)節(jié)之后的結(jié)果；VPMA Ⅱ?yàn)閳?zhí)行種群初始化和局部尋優(yōu)環(huán)節(jié)后的結(jié)果；VPMA Ⅲ為執(zhí)行種群初始化、局部尋優(yōu)和種群規(guī)模擴(kuò)張環(huán)節(jié)后的結(jié)果；VPMA Ⅳ為執(zhí)行種群初始化、局部尋優(yōu)、種群規(guī)模擴(kuò)張和種群規(guī)模收縮，即完整算法后的結(jié)果，如表5 所示。

表5 5 個(gè)系統(tǒng)由VPMA法不同步驟獲得的網(wǎng)絡(luò)重構(gòu)結(jié)果

在表5 的第3、4 列，即在IEEE33 和Taipower84 系統(tǒng)中，VPMA Ⅲ與VPMA Ⅳ的值相同。這是因?yàn)樵谶@兩個(gè)系統(tǒng)中僅經(jīng)過(guò)種群初始化環(huán)節(jié)和局部尋優(yōu)環(huán)節(jié)后，算法即可得到最優(yōu)解，在種群規(guī)模改變環(huán)節(jié)中僅經(jīng)歷了種群規(guī)模擴(kuò)張環(huán)節(jié)，沒(méi)有進(jìn)行種群規(guī)模收縮環(huán)節(jié)，實(shí)際上，種群規(guī)模擴(kuò)張環(huán)節(jié)中是為了滿足收斂條件而在對(duì)最優(yōu)解重復(fù)搜索，使得運(yùn)行耗時(shí)增加。對(duì)比表5的7、8、9 行，VPMA Ⅱ運(yùn)行后IEEE33、Taipower84 已求得最優(yōu)解，Bus119、Bus136 系統(tǒng)最優(yōu)解比例較低，平均網(wǎng)損較高，Bus417 系統(tǒng)網(wǎng)損誤差較大。這說(shuō)明小系統(tǒng)不能充分挖掘變種群模因算法的求解潛力，僅運(yùn)行VPMA Ⅱ，即不加入變種群策略的傳統(tǒng)模因算法已經(jīng)有了較好的求解小規(guī)模配電網(wǎng)重構(gòu)問(wèn)題的能力，但還不足以求解大規(guī)模配電網(wǎng)。

對(duì)表5 中的5、6、7 列，即對(duì)3 個(gè)大規(guī)模配電網(wǎng)進(jìn)行分析可知，VPMA Ⅱ運(yùn)行后將Bus119、Bus136、Bus417 系統(tǒng)網(wǎng)損誤差分別從6.6%、32.3%和34.2%降低到了0.3%、0.7%和4.98%，Bus119 和Bus136 最優(yōu)解比例由0%提高到了76%和9%。VPMA Ⅲ運(yùn)行后將以上3 個(gè)系統(tǒng)網(wǎng)損誤差分別降低到了0%、0.01%和0.71%，前兩系統(tǒng)最優(yōu)解比例提高到100%和19%。VPMA Ⅳ運(yùn)行后將以上系統(tǒng)網(wǎng)損誤差分別降低到了0%、0.01%和0.27%，前兩系統(tǒng)最優(yōu)解比例提高到了100%和40%。由此可知，對(duì)于Bus119 系統(tǒng)執(zhí)行VPMA Ⅲ即可搜索到全局最優(yōu)解而無(wú)需經(jīng)過(guò)種群規(guī)模收縮策略，而Bus136 和Bus417 系統(tǒng)在VPMAⅢ運(yùn)行后的平均網(wǎng)損和最優(yōu)解比例仍有提高的空間，在完整算法運(yùn)行后進(jìn)一步降低了平均網(wǎng)損并提高了最優(yōu)解比例。

對(duì)表5 中各步驟的平均耗時(shí)進(jìn)行分析可知，VPMA Ⅰ耗時(shí)占總時(shí)耗時(shí)0.4% ～15%，生成的解平均誤差1.2% ～34.2%，且系統(tǒng)規(guī)模小時(shí)，耗時(shí)比例較大、解誤差較小，系統(tǒng)規(guī)模大時(shí)，耗時(shí)比例小、解誤差較大。說(shuō)明其能在不同規(guī)模系統(tǒng)中平衡求解速度和個(gè)體質(zhì)量，滿足3.2 小節(jié)中所述對(duì)種群初始化環(huán)節(jié)迅速定位到解質(zhì)量較高的搜索區(qū)域的要求。在大規(guī)模系統(tǒng)中，VPMA Ⅲ和VPMA Ⅳ耗時(shí)占總耗時(shí)的80.4% ～97.2%，說(shuō)明種群規(guī)模擴(kuò)張和種群規(guī)模收縮策略占據(jù)了算法大部分的搜索時(shí)間，是算法最耗時(shí)的部分，同時(shí)也是求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題最關(guān)鍵的步驟，算法通過(guò)對(duì)種群規(guī)模的不斷調(diào)整從而增加種群多樣性、充分探索搜索空間，得到最優(yōu)搜索結(jié)果。

5 結(jié) 語(yǔ)

引入變種群模因算法的框架，構(gòu)建了求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題的方法。該方法根據(jù)配電網(wǎng)重構(gòu)問(wèn)題的特點(diǎn)，引入啟發(fā)式算法中的開關(guān)組思想生成初始種群并確定其鄰域，應(yīng)用智能算法中的雙主干交叉算子和禁忌搜索算法作為種群交叉及局部尋優(yōu)策略，采用動(dòng)態(tài)改變種群規(guī)模策略。所提方法在一個(gè)基本框架中將啟發(fā)式算法的思想與人工智能算法相結(jié)合，使得其兼具了啟發(fā)式規(guī)則原理簡(jiǎn)單、求解速度快的優(yōu)勢(shì)和人工智能算法搜索能力強(qiáng)的特性。最后，在IEEE33、Taipower84、Bus119、Bus136、Bus417 五個(gè)不同規(guī)模的系統(tǒng)中進(jìn)行配電網(wǎng)重構(gòu)仿真，并與多個(gè)算法進(jìn)行比較，驗(yàn)證了算法性能。同時(shí)分析了算法各個(gè)步驟對(duì)搜索過(guò)程的影響，證明了所提出的方法求解速度快、結(jié)果質(zhì)量好，適合求解大規(guī)模配電網(wǎng)重構(gòu)問(wèn)題。