基于改進量子進化算法的變電站選址方法

柳雙林 陳華豐 楊志剛

（1.西南交通大學電氣工程學院，成都 610031；2.浙江省余姚市供電局，浙江 余姚 315400）

近年來，隨著經濟的快速發展，供電負荷不斷增加，迫切地需要在已有變電站的基礎上，增建新的變電站以滿足負荷需求。變電站站址的優化是城市電網優化的一個重要的環節，站址選擇的好與壞直接影響工程投資效益，其結果直接影響未來電力系統的線路走線、網絡結構、電網投資、運行經濟性、供電可靠性及電能質量等[1]。

目前，變電站選址定容的研究領域有很多優化算法，大致可以劃分為啟發式優化方法、數學優化方法和基于隨機優化方法3大類[2-3]。但是，變電站選址屬于大規模復雜優化問題，問題規模一般較大，采用傳統的方法求解速度慢，且解的精度較低。

量子進化算法（QEA）是最近幾年發展起來的新的智能進化算法，該方法具有簡單易實現、搜索精度高、搜索速度快等優點，其在求解復雜組合優化問題方面具有其他隨機優化方法難以比擬的優點[4-6]，本文首次把QEA引入到變電站選址模型中。但傳統的量子進化算法局部搜索能力較弱，本文提出一種改進的量子進化算法（IQEA）并應用到變電所選址優化中。

本文對QEA的修復操作和進化方向進行改進，修復操作采用貪心修復，進化方向以適應度值作為吸引子進行下一代的更新。背包問題測試表明本文的改進措施增強了QEA的尋優質量，把IQEA應用到實際算例中進一步證明了本文所提出算法的有效性。

1 變電站選址模型

變電站選址問題是一個復雜的多目標優化問題，其影響因素多且復雜。一般情況下，變電站的優化配置是保證一定可靠性水平，滿足規劃年負荷要求條件下，以最小的投資費用確定變電站個數和位置。本文不但考慮了線路的網損費用和年投資費用，而且還加入了地理信息因素，將其量化為懲罰因子加入到目標函數中。

在優化選址之前，新建變電站的容量已經確定，新建變電站的運行費用和投資費用固定。變電站選址優化模型可以簡化為只考慮網損費用和線路投資費用的方程[7]，如式（1）所示。

2 改進的量子進化算法

針對上述變電站選址問題，本文給出了 IQEA的變電站選址優化方法。

QEA[8-10]是一種以量子計算和進化算法相結合的概率搜索方法，它有著收斂速度快，全局搜索能力強的特點[11-13]，但其局部搜索能力較弱。本文主要對傳統量子進化算法的修復操作和進化方向進行了修改，來增強其尋優能力。QEA的進化方向是以適應度值作為評價的標準，以適應度值作為吸引子進行下一代的更新，文獻[14-15]采用隨機修復操作，并對QEA的進化方向進行改進，以優秀群體統計分析后構建整個種群的吸引子，使得進化方向更加合理、科學。本文在其基礎上對修復操作進行修改，采用貪心修復，并采用背包問題來測試所提出的算法。

隨機修復全過程：

Step1 給 knapsack-overfilled（背包超重參數）賦值為false；

Step3 while knapsack-overfilled為true時，begin從背包中隨機選擇第i個物品，令xi=0，≤C，then knapsack-overfilled賦值為false，end；

Step4 while knapsack-overfilled為false時，begin從背包中隨機選擇第j個物品，令xj=1，＞C，then knapsack-overfilled賦值為true，end；

Step5xj賦值為0；

End。

貪心修復全過程：

Step1 計算每個物品的價值密度P/W，（P為物品的價值，W為相應物品的重量）；

Step2 根據上面計算的價值密度結果，對物品價值密度進行非遞增排序（如果兩個物品的價值密度相同，則將重量小的排在后面）；

Step3 將排序后的物品按從大到小依次裝入背包中，對于當前物品i，若背包剩余重量大于等于第i個物品的重量，則將物品i裝入背包，繼續考慮下一個物品i+1，重復Step3，直到大于或等于背包容量為止；

End。

IQEA算法流程：

Step1 初始化種群Q(0)、概率ε和學習率λ；

Step2 觀測種群Q(0)得到C(0)；

Step3 修復操作；

Step5 記錄C(0)中最佳個體Cbest(0)；

Step6 令每個個體的b(0)等于C(0)；

Step7 While非結束狀態do；

Step8t=t+1；

Step9 觀測種群Q(t-1)得到C(t)；

Step10 修復操作；

Step12 利用量子旋轉門[18]和A(t-1)更新Q(t)；

Step13 保存C(t)中最佳解到Cbest(t)；

Step14 保存b(t-1)和C(t)中較大者為b(t)；

Step15 利用b(t)和Cbest(t)生成K；

Step16 由ε、λ和K生成A(t)；

End；

End。

表1 量子旋轉角取值

向量K的kj分量計算公式為

式中，N為被選擇種群中優秀個體的統計個數。

本文采用截斷方法對個體進行統計，首先，按照適應度值對所有個體進行非升排序，其次，選取種群前η(t)的個體進行統計。

迭代時按PBIL[16]概率更新K的kj分量

概率向量K初始化為（0.5, 0.5, …, 0.5）。

吸引子A(t)的構造過程如下：

文獻[17]是最新出現的對 QEA進行改進的文章，文中方法是背包問題領域中具有代表性的成果。因此，在本文的背包測試實驗中以該文獻中的方法作為比較方法，以測試本文 IQEA的優越性。文獻[17]中的算法簡稱為 QIEA，文獻[18]中運用隨機修復的改進量子進化算法簡稱IQEA1，本文中運用貪心修復的改進量子進化算法簡稱為IQEA。背包問題數據均來自文獻每次增加 200，各參數設置如表 2所示。三種算法對每個背包問題獨立運行30次，分別記錄最好值，最差值，平均值及方差，實驗結果如表3所示。

表2 參數設置信息表

表3 背包問題實驗結果

（續）

由表3的統計結果可知，IQEA的最好值、平均值和最差值3個參數值要全面優于IQEA1和QIEA。并且IQEA的方差比IQEA1要小，說明IQEA獨立運行30次的結果比較穩定。因此本文IQEA的改進是合理的，具有更強的搜索能力。

3 算例應用

根據電網規劃，計劃建一座規模為 1×50MW的變電站（記為變電站1）和一座規模為2×50MW的變電站（記為變電站 2），用電區域共分為 10個用電單元，根據要求需要確定各個變電站的供電范圍和各個變電站的最優位置，各個參數基本信息如表4所示，用電負荷點的基本信息如表5所示，相關的地理約束的基本信息如表6所示[20]。

表4 參數設置信息表

表5 用電負荷信息表

表6 地理約束信息表

由以上背包問題測試結果表明，IQEA的性能最優，因此根據變電站選址模型，分別應用基本QEA和 IQEA對變電站進行選址操作，對比尋優能力。設種群數量為10，最大迭代次數為300，優化結果如表7所示。

表7 多源變電站選址優化結果

由于，多源變電站選址優化問題是一個多目標、多約束的復雜優化問題，本文針對多源變電站選址中的二源變電站選址進行測試。由表5測試結果可知，IQEA的搜索精度要高于基本QEA，有效避免了陷入局部極值，IQEA方法比基本QEA方法節約資金 30.0377萬元，新建變電站站址基本上都在負荷中心，且滿足了對負荷就近供電的原則，并且IQEA優化得出的變電站1和變電站2的容載比分別為1.66和2.25，比例值滿足電網容載比要求。

4 結論

變電站選址優化是一個復雜的多目標、大規模組合優化問題，本文首次將 QEA引入到變電站選址中，并提出了IQEA。IQEA對QEA的修復操作和進化方向進行改進，背包測試結果表明，IQEA的改進措施提高了搜索的精度，同時應用到具體算例中表明，IQEA是一種科學、合理的變電站選址方法。

[1] EL-FOULY T H M, ZEINELDIN H H, EL-SAADANY E F, et al.A new optimization model for distribution substation sitting, sizing, and timing[J].International Journal of Electrical Power and Energy Systems, 2008,30(5): 308-315.

[2] 劉自發,張建華.基于改進多組織粒子群優化算法的配電網絡變電站選址定容[J].中國電機工程學報,2007, 27(1): 105-111.

[3] 王成山,劉濤,謝瑩華.基于混合遺傳算法的變電站選址定容[J].電力系統自動化, 2006, 30(6): 30-34, 47.

[4] 段剛,余貽鑫.電力系統NP難問題全局優化算法的研究[J].電力系統自動化, 2001, 25(5): 14-18.

[5] 劉建明,李茂軍.基于改進遺傳算法的水電經濟調度[J].電力系統及其自動化學報, 2007, 19(5): 39-44.

[6] 李運華,吳宏昺,盛萬興,劉科研.分布式并行混合遺傳算法在無功優化中的應用[J].電力系統及其自動化學報, 2008, 20(2): 36-41.

[7] 王成山,魏海洋,肖峻,謝瑩華,王凱軍.變電站選址定容兩階段優化規劃方法[J].電力系統自動化, 2005,29(4): 62-66.

[8] HAN K H, KIM J H.Quantum-inspired evolutionary algorithms with a new termination criterion，Hζ gate,and two-phase scheme[J].IEEE Transaction on Evolutionary Computation, 2004, 8(4): 156-169.

[9] LI Y Y, ZHAO J J, JIAO L C.Quantum- Inspired evolutionary multicast algorithm[A].Proceeding of 2009 IEEE International Conference on Systems, Man,and Cybernetics[C].USA: IEEE press, 2009.1496-1501.

[10] JIAO L C, LI Y Y, GONG M G, ZHANG X R.Quantum-inspired immune clonal on Systems, Man,and Cybernetics, Part B, 2008, 38(5): 1234-1253.

[11] 錢潔,鄭建國,張超群,王翔,閻瑞霞.量子進化算法研究現狀綜述[J].控制與決策, 2011, 26(3): 321-326.

[12] 王凌.量子進化算法研究進展[J].控制與決策, 2008,23(12): 1321-1326.

[13] ZHANG G X.Quantum-inspired evolutionary algorithm: a survey and empirical study[J].Journal of Heuristics, 2011, 17(3): 303-351.

[14] DEFOIN P M, STEFAN S, NIKOLA K.Quantuminspired evolutionary algorithm： a multimodel EDA[J].IEEE Transactions on Evolutionary Computation, 2009,13(6)： 1218-1231.

[15] 譚立湘,郭立.基于全面學習的量子分布估計算法[J].模式識別與人工智能, 2010(3)： 314-319.

[16] 周雅蘭,王甲海,印鑒.一種基于分布估計的離散粒子群優化算法[J].電子學報, 2008, 36(6)： 1242-1248.

[17] VLACHOGIANNIS J G, Lee K Y.Quantum-inspired evolutionary Algorithm for real and reactive power dispatch[J].IEEE Trans.Power Syst.2008, 23(4)：1627-1636.

[18] 錢潔,鄭建國.采用群體統計學習的量子進化算法[J].西安交通大學學報, 2012, 46(2)： 51-58.

[19] QIN Y H, ZHANG G X, Li Y Q.A comprehensive learning quantum-inspired evolutionary algorithm[J]//Communications in Computer and Information Science,2011, vol.268： 151-157.

[20] 董永峰,楊彥卿,宋潔,顧軍華,顏威利.基于改進粒子群算法的變電站選址研究[J].繼電器, 2008, 36(5)：32-35.