基于改進蟻群算法的配電網重構問題求解方法

姜 敏，謝東升

（1.國家電網山西省電力公司 電力科學研究院，太原 030000；2.國家電網山西省電力公司 經濟技術研究院，太原 030000）

配電網作為面向用戶的基礎設施，直接向用戶配送電能，其網絡結構一般比較復雜，線路較長，損耗較大。因此，配電網的結構設計除了以保障其可靠性和電能質量為前提，降低輸電過程中的損耗是需要考慮的一個重要問題。配電網重構的目的是提高輸電質量，降低網絡上的功率損耗，解除線路過負荷等。由于其自身特點，配電網重構問題被做為多約束條件的復雜組合優化問題來考慮，求解這一問題的方法大致有優化算法、啟發式方法和人工智能算法。

人工智能算法[1-6]是近幾年發展起來的、用以求解配電網重構問題的一種有效方法，目前主要有粒子群算法、遺傳算法、禁忌搜索算法，還有逐漸取得應用的蟻群算法。然而，其應用實例還較少，主要原因在于傳統蟻群算法在該問題求解過程中，最優解的構造需要大量時間，計算效率過低，對此，諸多學者開始對傳統的蟻群算法加以改進[7-10]。本文以傳統蟻群算法為基礎，針對其求解配電網重構問題時的停滯現象，通過信息素局部更新和全局更新相結合的方法，提出一種基于方向性信息素改進的蟻群算法。

1 配電網重構問題描述

配電網重構問題意味著在滿足電網安全運行的約束條件下，如線路熱容、壓降要求等條件，通過改變各分段開關以及聯絡開關的開合狀態而進行供電電源與線路的選擇。其求解目的是通過適當的選擇最終形成一個輻射狀網絡，使得配電網中的線路損耗、負荷均衡、電壓容量等某一個或者多個指標達到最優狀態。

首先，建立配電網重構問題的數學模型，將網損最小作為目標函數，其數學表達式為

式中：n為配電網中支路數目；ki為0/1離散變量，表示開關i的開合狀態；Ri為第i條支路的電阻；Pi，Qi分別為第i條支路的有功功率、無功功率；Ui為第i條支路末端的節點電壓。

在配電網重構時，需滿足以下約束條件：

網絡拓撲約束配電網重構后的網絡應該呈現出輻射狀。

供電約束重構后的配電網網絡需滿足線路負荷約束條件，同時重構后的配電網網絡中不可以出現獨立節點。

節點電壓約束Uimin≤Ui≤Uimax， 式中：Uimin，Uimax分別為節點i所允許電壓的最小值、最大值。

支路過負荷約束Si≤Simax，Ii≤Iimax， 式中：Si，Simax分別為流經不同支路i的計算功率、最大容許功率；Ii，Iimax分別為流經不同支路i的電流、最大容許電流。

變壓器過負荷約束St≤Stmax，式中：St，Stmax分別為變壓器的供出功率、最大容許功率。

針對上述配電網重構問題所求的解是滿足約束條件的一個輻射網絡，將配電網絡上的負荷、配電變壓器以及饋線段圖中的節點、線路看作圖的邊，則可以用一個無向連通圖G=（V，E）來表示配電網絡，其中V為各個節點的集合，E為各條邊的集合。則配電網重構求解問題，即為滿足約束條件下，尋找一個滿足網損最小條件的最小生成樹。

2 蟻群算法及其改進

2.1 傳統的蟻群算法

電力系統配電網重構問題，本質上屬于組合狀態優化問題，即需要求解一個滿足約束條件的輻射網絡，構建輻射網絡的過程與構建無向圖中最小生成樹的過程類似。借助蟻群算法來解決此問題。

文中，用Sk（t）記為第k只螞蟻在t時刻能夠接入樹的全部節點集合；用Wk（t）記為第k只螞蟻在t時刻未能夠接入樹的其它節點集合；用Ek（t）記為在t時刻的全部可選路徑集合；用Pk（t）記為每1條路徑在t時刻的狀態轉移概率值；用Ak（t）記為t時刻能夠在可選路徑集合E（t）中添加新的可選路徑集合；用s-w記為節點s到節點w的1條路徑。

使用傳統的蟻群算法，構造最小生成樹的具體步驟如下：

步驟1令初始化時間t=0，螞蟻k從起點開始搜索，即令 Sk（0）=｛s0｝；

步驟2在t時刻，螞蟻k根據狀態轉移概率值 Pk（t），從可選路徑集合 Ek（t）中選擇 1 條路徑；

步驟3檢查在可選路徑集合Ek（t）中有無到節點w的路徑，若存在則斷開，返回步驟2，否則執行步驟4；

步驟 4更新 Sk（t）和 Wk（t），把節點 w 從集合Wk（t）移入集合 Sk（t）中，即令 Wk（t+1）=Wk（t）-｛w｝，Sk（t+1）=Sk（t）+｛w｝；

步驟5檢查集合Wk（t）是否為空集，若是空集，則已經把所有節點接入生成樹中，算法結束，否則執行步驟6；

步驟 6更新可選路徑集合 Ek（t），從集合 Ek（t）中剔除路徑j，并將在當前時刻更新后的可選路徑集合 Ak（t）添加到 Ek（t）中，即令 Ek（t+1）=Ek（t）+Ak（t）-｛ j｝。

傳統的蟻群算法，利用不同螞蟻之間不間斷的信息交流，從而能夠朝著全局最優的目標進化，因此蟻群算法在求解過程中具有較強的全局最優搜索能力。但是，在求解復雜問題時該算法存在容易停滯的不足，即在尋優過程中在尚未找到全局最優解之前，各個螞蟻找到的解完全一致。此時，算法認為找到了全局最優解，而停止進一步搜索以找到更優的解。這種情況下僅得到局部最優解，不利于找到全局最優解。

分析傳統蟻群算法更新的原則，發現在傳統算法使用的信息素更新規則中，不被選中路徑上的信息素與選中路徑上的信息素的差異會隨著迭代過程越來越大，而螞蟻始終沿著信息素高的路徑搜索，這就導致了當前不被選中的路徑在以后被螞蟻選中的概率越來越小，進而使得該算法會在局部最優解附近出現停滯現象。

2.2 改進的蟻群算法

為加快算法收斂速度，避免出現停滯現象，在此給出一種改進的蟻群算法。在改進的算法中采用信息素局部更新與信息素全局更新相結合的思想，通過螞蟻間利用局部信息交流來更新普通信息素的同時，在改進的算法中定義一種方向性信息素，并利用全局信息對方向性信息素進行更新。結合2種信息素更新規則，在尋優過程中，除了可以更新最優路徑上的信息素之外，同時也會更新路徑較短的網絡節點間的信息素，這樣既可以對最優路徑上的信息反饋加以增強，從而加快算法的收斂速度，還可以抑制尋優過程中易出現的停滯現象，從而避免出現局部最優解。具體的改進方法如下：

假設初始時刻配電網絡中不同線路上的信息素為αij=d，式中d為常數。螞蟻遍歷完所有節點后，隨之可以生成一個最小生成樹，即形成一個輻射網絡，以本次網絡中得到的數據為基礎進行潮流計算，可得到本次迭代路徑的網損值floi。另外，由于配電網絡中每1條支路是不一樣的，所以需要考慮配電網絡中所有不同支路上的電阻值Rij。

完成1次遍歷后，按照式（2）更新當前配電網絡中不同線路上的普通信息素，即

式（2）中，如果螞蟻經過路徑（i，j），則

式中：N為信息素濃度；flok為螞蟻k在完成遍歷后生成的配電網絡的網損值；ρ為信息素的揮發度；Rij為網絡節點i到網絡節點j線路的電阻。

更新完配電網絡中不同支路上的普通信息素的同時，還需要更新當前生成的輻射配電網絡中不同支路上的方向性信息素。考慮到方向性信息素主要起指引作用且不會揮發，故在更新方向性信息素時，選取本次迭代中網損值最小的路徑。

按照式（3）對方向性信息素進行更新，即

式中：N′為方向信息素濃度；fbestNc為本次迭代中生成的輻射配電網絡的最小網損值；α→ij（t）為更新配電網絡前該支路上的方向信息素的數值；Rij為節點i到節點j線路的電阻值。

在使用蟻群算法尋優過程中，可依據式（4）計算當前可選路徑上的概率，即

式中：dk為允許的閾值。

在改進的算法中，為防止算法得到1個局部最優解，在選擇路徑時加入了路徑探測因子ε，螞蟻每完成1次遍歷，就可以根據式（5）更新ε，即

式中：c為常數。由式（5）可見ε值是遞減的。在初始階段，螞蟻在進行路徑選擇時，隨機性都比較大，從而提高了算法的搜索半徑，降低了算法進入停滯現象的可能。隨著螞蟻遍歷次數的增加，ε最終遞減到0，最優路徑上的信息素會不斷增加，從而提高了該算法的全局尋優能力。

3 改進的蟻群算法的應用

根據配電網重構中的約束條件，重構后的配電網應該把網絡中的所有節點包含在內，同時要求重構后所生成的網絡沒有回路。利用上述改進的蟻群算法對配電網絡中的所有節點進行遍歷，生成配電網絡中的最小生成樹。改進的蟻群算法基本流程如圖1所示，基本步驟如下：

圖1 改進蟻群算法求解配電網重構問題計算流程Fig.1 Calculation flow chart of improved ant colony algorithm for solving distribution network reconfiguration problem

步驟1讀取當前配電網數值，同時對配電網重構問題進行初始化。將配電網絡上所有節點的方向性信息素設為0，令配電網絡中所有支路上的普通信息素值為αij=d，式中d為常數。令ε為固定常數，作為路徑探測因子的初始值；令算法的最大迭代次數為 Dmax；令初始時刻 Δαij（0）=0。 同時，清空所有螞蟻的禁忌表，隨機選擇m個螞蟻并將它們放在n個節點上。

步驟2生成1個0～n的隨機數，并與ε做比較，若數值大于 ε，則根據式（4）計算的概率從 Ek（t）中選擇路徑j，否則從Ek（t）中隨機選擇1條路徑。

步驟3判斷Ek（t）中是否存在到節點w的路徑，若存在則斷開路徑j，返回步驟2，否則執行步驟4。

步驟4更新網絡中螞蟻的禁忌表，同時判斷Wk（t）是否為空集，即是否遍歷完所有節點，若未完成遍歷，則執行步驟5，否則執行步驟6。

步驟 5從 Ek（t）中剔除路徑 j，并將當前的Ak（t）加到 Ek（t）中，即令 Ek（t+1）=Ek（t）+Ak（t）-｛ j｝，跳轉到步驟2。

步驟6進行下一次循環，按照式（5）更新ε，并計算各支路的網損值，根據式（2）更新網絡中節點的普通信息素值，找到1個最小的網損值，同時按照式（3）更新方向信息素。

步驟7若達到最大循環次數Dmax，則算法結束并輸出當前計算結果，反之則清空禁忌表并執行步驟2。

4 仿真分析

采用IEEE33節點配電網絡對所提改進的蟻群算法進行仿真分析。假設配電網重構前的節點結構如圖2所示，其配電網絡中有33個節點，包含5個聯絡開關，37條支路，配電網的額定電壓為12.66 kV，總負荷為 3715 kW+j2300 kV·A，功率基準為 10 MV·A。

圖2 IEEE33節點配電網結構Fig.2 IEEE33-node distribution network structure

選擇m=30個螞蟻，假設配電網絡上各支路的初始信息素 α（0）=0.2， ρ=0.4，ε=40，N=2，N′=10，采用改進的蟻群算法進行仿真，并與傳統的蟻群算法做對比，計算結果見表1。

表1 計算結果的對比Tab.1 Comparison of calculation results

由表可知，與重構前相比較，使用改進的蟻群算法重構后的網絡，網損值明顯降低了30%；與傳統的蟻群算法相比較，使用文中所提出的算法進行重構時的網損值更小。傳統蟻群算法和改進的蟻群算法在重構網絡時的收斂情況如圖3所示，由圖可見，后者的收斂速度更快，且收斂時的網損值更小。

圖3 傳統算法與改進算法收斂速度仿真Fig.3 Traditional algorithm and improved algorithm convergence speed simulation

5 結語

針對配電網重構問題展開研究，考慮到傳統蟻群算法在配電網重構問題求解過程中存在停滯現象，同時計算效率低等問題，文中將基于方向性信息素的改進的蟻群算法應用于配電網問題的求解，并進行仿真實驗。仿真分析結果表明，與傳統蟻群算法相比較，該算法可有效加強收斂和防止早熟，具有較強的最優解尋優能力，在提高運算效率的前提下防止算法陷入局部最優，從而得到全局最優解。本算法實用性較強，可應用于實際配電網重構問題的求解，提高電力系統的自動化水平。

[1]葉婧，汪芳宗.基于改進模擬植物生長算法的配電網重構[J].計算技術與自動化，2009，28（3）：49-52.

[2]李雪，崔穎安，崔杜武，等.改進的知識進化算法在配電網的應用[J].計算機工程與應用，2012，48（21）：9-14.

[3]張濤，史蘇怡，徐雪琴.基于二進制量子粒子群算法的含分布式電源配電網重構[J].電力系統保護與控制，2016，44（4）：22-28.

[4]陳正鵬，黃純，張亞萍，等.基于改進雙種群遺傳算法的含分布式電源配電網重構[J].電力系統及其自動化學報，2017，29（4）：78-83.

[5]高元海，王淳.基于八種智能算法的配電網絡重構計算平臺及其性能[J].中國電力，2015，48（8）：53-60.

[6]王暉，趙亮，劉建樹.改進蟻群算法在配電網重構問題中的應用[J].黑龍江電力，2016，38（2）：100-103，108.

[7]徐延煒，賈嶸.基于人工免疫思想的蟻群算法（AIACS）在配電網重構中的應用[J].電力系統保護與控制，2010，38（18）：89-93.

[8]張明光，趙金亮，王維洲，等.基于自適應遺傳算法和蟻群算法融合的配電網重構[J].電氣自動化，2011，33（6）：57-60.

[9]王大為，樸在林.基于序優化和模糊蟻群算法的多目標配電網重構[J].電網與清潔能源，2016，32（9）：44-49.

[10]史林靂.基于模擬退火改進蟻群算法的配電網重構[J].機電信息，2010，10（36）：104-106.