[發明專利]基于無向圖所有生成樹的網絡重構遺傳算法

有效

• 申請號: 201410108464.4
• 申請日: 2014-03-21
• 公開（公告）號: CN103903055A
• 公開（公告）日: 2014-07-02
• 發明（設計）人: 張劍;袁曉冬
• 申請（專利權）人: 國家電網公司;江蘇省電力公司;江蘇省電力公司電力科學研究院
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林;許婉靜

技術領域

本發明涉及一種基于無向圖所有生成樹的網絡重構遺傳算法，屬于電力系統運行、仿真與控制領域。

背景技術

為了提高供電可靠性，城市配電網一般設計為環網結構，為了減小短路電流與便于繼電保護的整定，一般采用開環運行方式。配電線路中包含大量常閉的分段開關及少量常開的聯絡開關。配電網網絡重構通過調整開關狀態能夠達到降低網損、隔離故障、均衡負荷、提高電壓等目的。目前，配網自動化示范工程在全國各大中城市全面鋪開，配網自動化系統能夠人工、交互或者自動地調整開關狀態，為網絡重構的實際工程應用奠定了良好基礎。

配電網網絡重構是一種大規模、非線性組合優化問題，主要有支路交換法、最優流法、遺傳算法、啟發式方法、混合方法等。由于遺傳算法不依賴于初值、魯棒性好、能得到全局最優解等優點，得到了眾多學者的關注。

在最初的基于遺傳算法的配電網網絡重構中，通常采用二進制編碼方法，每個開關對應染色體中的一個基因位，基因為0表示開關打開，為1表示開關閉合。這種編碼方式容易理解、實現簡單。但是大量不能打開的開關也參與了編碼，導致染色體較長，在交叉、變異過程中會產生大量不可行解，程序搜索效率十分低下。后來提出的基于改良策略網絡重構遺傳算法也或多或少地產生不可行解，從而使得程序搜索效率大打折扣。

發明內容

本發明提供了一種基于無向圖所有生成樹的網絡重構遺傳算法，避免了傳統網絡重構遺傳算法產生大量不可行解，搜索效率低的弊端。

為達到上述目的，本發明采用的技術方案為：

基于無向圖所有生成樹的網絡重構遺傳算法，包括以下步驟：

1）、構建配電網的簡化圖，采用無向圖所有生成樹的搜索算法搜索出簡化圖中所有的生成樹和連支，

所述簡化圖的構建方法為：城市配電網拓撲結構圖是以配變或線路為支路、負荷母線為節點的有環、無向、連通圖，將配電網拓撲結構圖中不在環路中的支路去掉、度為2的相鄰節點所在的支路合并成一條邊，由此構成一個簡化圖；

所述生成樹是指包含簡化圖的所有節點，但不包含簡化圖的所有邊的簡化圖的子圖；

所述連支是指簡化圖減去生成樹剩下的邊組成的集合；

2）、計算所述步驟1）的所有的連支的基向量和連支的候選解個數，

所述連支的基向量是指以連支中每條邊上的開關數量為分量組成的向量；

所述候選解個數的計算方法為將連支基向量的每個分量作乘積運算即為該連支對應的候選解數目；

3）、并行產生初始的子種群，所述子種群與連支一一對應，子種群中染色體的長度等于連支上邊的個數，所述染色體每一位的取值等于對應邊上打開開關的編號，染色體第i位取0，1，2……N_i-1中的某一個值，N_i為連支第i條邊上的開關數目；

4）、并行計算子種群中染色體的適應度值，具體計算方法為：對染色體代表的配電網中打開的開關采用十進制編碼方法進行解碼，采用并行前推回代算法計算網損值，對子種群中每個染色體對應的網損值按照從小到大進行排序并編號，對編號等間隔線性映射為0-2中實數作為每個染色體對應的適應度，并定義網損值最大的染色體對應的適應度值為0，網損值最小的染色體對應的適應度值為2，相鄰的染色體適應度值間隔相等；

5）、并行在子種群中進行基因操作，具體包括如下步驟：

5-1）進行子種群選擇操作

對于每個子種群，根據染色體的適應度值，采用“賭輪盤”法選擇N個染色體，所述N為偶數；

5-2）進行子種群交叉操作

按照指定的概率將雙親染色體對應基因位數值互換；

5-3）進行子種群變異操作

按照指定的變異概率將雙親染色體中一位或多位基因替換為小于基向量對應位的非負整數值；

5-4）進行子種群重插入操作

將每個子種群中選擇的N個染色體完成了交叉、變異操作的染色體重新插入父代，同時計算子種群中染色體的適應度值，淘汰掉子種群父代中適應度值最小的N個染色體；

6）、完成所有子種群的基因操作后，整個種群中網損值最小的染色體即為最優解，即按照該染色體所代表的配電網中打開的開關組合進行配電網網絡重構。

前述的步驟3），步驟4），步驟5）的并行計算采用MATLAB/PARALLEL?COMPUTING工具箱進行。

前述的步驟5-2）進行子種群交叉操作中，指定的概率的范圍為：0.7—0.9。