遺傳模擬退火算法

1、改進遺傳模擬退火算法在配電網(wǎng)絡重構(gòu)中的應用岸劉揚，楊建軍，魏立新（大慶石油學院，大慶163318）摘 要:對遺傳模擬退火算法中的交叉、變異操作進行了改進，并實施了最 優(yōu)保留策略，形成了改進遺傳模擬退火算法。以網(wǎng)損最小為目標函數(shù)，以配電網(wǎng) 電壓降的限制、線路電流量的限制等為約束條件，建立了配電網(wǎng)絡重構(gòu)優(yōu)化模型。 在考慮配電網(wǎng)自身特點的基礎上，利用改進遺傳模擬退火算法求解。重構(gòu)算例說 明，該優(yōu)化方法有效、實用。關(guān)鍵詞：配電網(wǎng)絡；網(wǎng)絡重構(gòu)；遺傳算法；模擬退火Application of the Improved Genetic Simulated Annealing Algorithm in Dis

2、tribution Network ReconfigurationLIU Yang, YANG Jianjun, WEI Lixin(Daqing Petroleum Institute, Daqing 163318,China)Abstract:In the paper, the crosser and mutation in the genetic simulated annea ling algorithm were improved, and the optimized reserved strategy was used to form the improved genetic si

3、mulated annealing algorithm. An optimization model of distri bution network reconfiguration is established, in which the minimum network loss is taken as objective function, the restrictions to the decline of voltage and curren t are taken as constraint conditions. Based on the features of distribut

4、ion network, the improved genetic simulated annealing algorithm is used in network reconfigurat ion. Reconfiguration results show that the algorithm is efficient and practical.Key words: distribution network; network reconfiguration; genetic algorithm; s imulated annealing1刖言網(wǎng)絡重構(gòu)作為配電系統(tǒng)經(jīng)濟運行自動控制的一個重要問

5、題已被廣泛關(guān)注。網(wǎng) 絡重構(gòu)的基本原理就是在滿足系統(tǒng)約束條件的前提下，通過調(diào)整網(wǎng)絡中分段開關(guān) 和聯(lián)絡開關(guān)的分合來尋求一種符合某特定運行要求（如使網(wǎng)損最小）的拓撲結(jié)構(gòu)。理論上，在各種約束條件下，配電網(wǎng)絡重構(gòu)問題是一個大規(guī)模非線性組合優(yōu) 化問題。由于配電網(wǎng)中作為優(yōu)化變量的開關(guān)數(shù)目巨大，窮舉搜索將面臨“組合爆 炸”問題。近年來，模擬退火算法和遺傳算法在配電網(wǎng)絡重構(gòu)中得到了應用，但 單一算法的搜索能力和效率不高，而且受初始參數(shù)的影響較大。遺傳算法參數(shù)選 擇不當易陷入“早熟”，模擬退火算法對“退溫”歷程的限制條件很苛亥U，優(yōu)化 時間性能較差。本文將遺傳算法和模擬退火算法有效結(jié)合起來，并對遺傳算法的適應函數(shù)

6、、 交叉率和變異率進行了改進，計算過程考慮了配電網(wǎng)自身的特點，使算法的優(yōu)化 性能得到了大幅度提高。2網(wǎng)絡重構(gòu)數(shù)學模型以網(wǎng)損最小為目標函數(shù)的網(wǎng)絡重構(gòu)數(shù)學模型為 TOC o 1-5 h z mm/ =字.L 寫工H）式中： PLi為第i段線路的有功損耗，kW； N為線路總數(shù)量；Ri為線段i的單 位電阻，。；L為線段i的長度，km； P為第i線路的有功潮流，kW； Q為第i iii線路的無功潮流，kvar； Ui為第i線路的電壓值，kV。不等式約束包括電壓降的約束、線路電流值約束、電源容量約束，即心5式中：Uimin為第i節(jié)點要求的最低工作電壓值，kV； Iimax為第i線路導線型號對 應的載流量值

7、，A； St為第t個變電所的負荷值，kVA； Stmax為第t個變電所的供 電能力，kVA。此外，還應保證每組開關(guān)組合不形成環(huán)網(wǎng)和出現(xiàn)“孤島”的情況，即每次循 環(huán)中遍歷的節(jié)點個數(shù)應等于整個網(wǎng)絡的負荷節(jié)點總數(shù)。3改進遺傳模擬退火算法及其在配電網(wǎng)絡重構(gòu)中的應用3.1編碼在遺傳算法中，問題的解用數(shù)字串來表示，每個數(shù)字串叫做一個染色體，遺 傳算子也是直接對串進行操作。遺傳算法常用的有十進制編碼和二進制編碼。配 電網(wǎng)絡重構(gòu)的實質(zhì)就是通過改變開關(guān)的開合狀態(tài)來改變網(wǎng)絡的拓撲結(jié)構(gòu)，目的是 找到最優(yōu)的網(wǎng)絡結(jié)構(gòu)所對應的開關(guān)狀態(tài)，以使網(wǎng)損降到最小。因此，取開關(guān)狀態(tài) 為控制變量比較合適，將網(wǎng)絡中的開關(guān)狀態(tài)自然地用0或

8、1表示（0表示開，1 表示合），每個開關(guān)占據(jù)染色體的一位，各開關(guān)狀態(tài)組合在一起，就形成了一條 染色體，染色體的長度為網(wǎng)絡中開關(guān)的數(shù)量總和。這種方案簡潔明了，而且無需 二進制與十進制之間的相互轉(zhuǎn)換，節(jié)省了計算時間。3.2產(chǎn)生初始種群隨機產(chǎn)生pop-size個長度為1（1為網(wǎng)絡中開關(guān)數(shù)量的總和）的二進制編碼， 作為初始種群。為了讓初始種群遍及整個解空間，盡量反映搜索空間的性態(tài)，P op-size不能取太小，且隨節(jié)點數(shù)的增多而變大，不過太大會使運算時間增加。 由于配電網(wǎng)具有閉環(huán)設計開環(huán)運行的特點，開關(guān)狀態(tài)的組合應保證網(wǎng)絡處于開環(huán) 運行狀態(tài)，同時保證每個負荷的供電，即不形成孤島。因此在配電網(wǎng)潮流計算程

9、 序中應加入搜索判斷程序，將不符合實際運行條件的個體去掉。3.3初溫的確定及退溫操作初溫選擇t0=K6的形式，其中：K為充分大的數(shù)，可以選K=10，20，100， 等試驗值；6=fsmax-fsmin，fsmax為初始種群中最大的目標函數(shù)值，fsmin為初始種群 中最小的目標函數(shù)值。退溫函數(shù)選用常用的tk+1=a tk形式，其中0Va V1。3.4適應函數(shù)的確定適應函數(shù)值是遺傳算法指導搜索方向的依據(jù)，首先應保證適應函數(shù)值不為負。其次，因為在輪盤賭選擇過程中，適應函數(shù)值大的染色體被選中的概率大， 因此目標函數(shù)的優(yōu)化方向?qū)m應函數(shù)值增加的方向。網(wǎng)絡重構(gòu)的目標函數(shù)是網(wǎng) 損最小，屬于最小值優(yōu)化問題，

10、應加以調(diào)整。其變換方式如下式中：f(i)為染色體對應的目標函數(shù)值；fmin為當前代進化群體中最小的目標 函數(shù)值；t為溫度參數(shù)。這是一個非常好的加速適應函數(shù)，當溫度較高時加速性 不明顯，當溫度較低時加速性非常明顯，這正是我們所需要的。3.5終止規(guī)則因為按上面的適應函數(shù)形式，每代計算出的最大適應函數(shù)值均等于1，不發(fā) 生變化，所以應通過監(jiān)控每代進化群體中最小目標函數(shù)值fmin的變化情況來判斷 算法是否終止。當連續(xù)q代沒有發(fā)生變化時，即可認為算法收斂，此時停止計算。 3.6遺傳算法的選擇復制根據(jù)適應函數(shù)值的大小進行群體選擇，選擇方法采用常用的輪盤賭選擇法， 但為了保證算法能夠收斂到全局最優(yōu)解，實施了最

11、優(yōu)保留策略。即將中間群體中 性能最好的個體無條件地復制到下一代群體中，這樣就會保留中間群體中的最好 解，使算法可以以概率1收斂到全局最優(yōu)解，保證了算法的收斂。3.7基因操作一交叉、變異在優(yōu)化時發(fā)現(xiàn)，即使對于同一個問題，交叉率Pc和變異率Pm取值不同也會 產(chǎn)生不同的結(jié)果。目前，常用方法是P、P依經(jīng)驗取固定值，一般P 0.25, c mc0.95，Pme0.005，0.1，具有一定的盲目性。Srinivas等人提出了 P、P隨適應函數(shù)值自動改變(adaptive )的方法， 主要思想是根據(jù)種群的進化情況來動態(tài)地調(diào)整交叉率Pc和變異率Pm，以達到克 服過早收斂及加快搜索速度的目的。根據(jù)其原理，本文建

12、立的表達式如下虹一 /i.un （虹一 /i.un （/ min.I k-.（7）式中：k、k為常數(shù)，具體值根據(jù)實際情況確定；f為當前代進化群體的平均目12avg標函數(shù)值；f為兩個交叉?zhèn)€體中目標函數(shù)值較小的一個。在操作過程中，適應函數(shù)值小的個體，具有較大的交叉率和變異率，這樣有 利于加快搜索速度。當遺傳算法陷入問題的局部極值時，旺皿一fmin時，根據(jù)式 (6)和(7)，適應函數(shù)值較大的個體對應的七、Pm也將增大，這樣有利于避免 “早熟”。但太大的Pc、廿有可能造成解空間過于分散，甚至可能導致原有的 解被破壞。為此，一旦I f -f 1時，就固定P、P值，以避免原有解空 min avgc m間被

13、完全破壞。同時，在基因操作時，為了不破壞配電網(wǎng)絡的輻射運行狀況以及不形成孤島， 變異需成對進行，設選中了某染色體的某一位進行變異，如0變1，與此同時， 必須將該染色體中與該位相鄰二進制碼為1的位變成0，反之亦然。這樣操作可 以大量避免不可行解的產(chǎn)生，極大地提高了計算效率。3.8基于Metropolis判別準則的復制策略以經(jīng)過遺傳算法選擇復制、交叉、變異操作的群體作為初始群體，運用基于 Metropolis判別準則的復制策略，產(chǎn)生下一代群體。基于Metropolis判別準則 的復制策略可分為兩步：實施最優(yōu)保留策略。實施Metropolis判別準則的復制策略。即在染色體i的鄰域中隨機產(chǎn)生 新個體j

14、，i和j競爭進入下一代群體的準則，采用Metropolis判別準則，令 f=f(x)-f(x)，若 f頸，則把x復制到下一代群體，否則產(chǎn)生0，1之間jij的隨機數(shù)r。如果rE Ihc dhlrjhulkm nrtwirkH i 幅壕虻優(yōu)幃后辮比蠢Tib. Ilahk of sACrm Endilhw bvfckrr and jflrr bplinkiution配電X物手供圍牝kw配電m時bi宰配電阡+冊最大成序耽十的汗性傭為林歸的Jf美ks.Kl.Kii.ki 頑“曲、hl ,K,KW.K部l.K .Kl KJ.KE,K?,Kll,(tit 喘mm1,2L*邱Kr.4算例根據(jù)本文算法，用C+B

15、uilder5.0編制了網(wǎng)絡重構(gòu)程序，并以喇嘛甸油田6k V配電系統(tǒng)中的喇十四變電所、喇三變電所以及喇十二變電所間的部分配電線路 （如圖2）為例進行了試算。此系統(tǒng)共有338條線段，129臺變壓器，26個開關(guān)。計算時染色體長度l等于開關(guān)數(shù)26,群體規(guī)模pop-size取60，算法中各系 數(shù)確定如下：選擇初溫時系數(shù)K=20，退溫時的系數(shù)a =0.8，交叉和變異操作時 的系數(shù)k=0.8，k=0.2，當If -f l0.05f時，交叉率和變異率固定為0.12min avgmin6和0.05,算法終止判斷條件中q=20。優(yōu)化結(jié)果見表1，從優(yōu)化結(jié)果中可以看到， 不但配電網(wǎng)網(wǎng)損率降低了 1.7%，而且配電網(wǎng)

16、末端電壓質(zhì)量得到了明顯改善。5結(jié)論本文探討了如何利用改進遺傳模擬退火算法來進行網(wǎng)絡重構(gòu)優(yōu)化，以減少網(wǎng) 損。改進遺傳模擬退火算法的混合策略是一個兩層并行搜索結(jié)構(gòu)，其優(yōu)化性能， 尤其是避免陷入局部極小的能力，得到了提高。其優(yōu)化過程包含了遺傳算法的 復制、交叉、變異和模擬退火算法的狀態(tài)產(chǎn)生函數(shù)等不同的鄰域搜索結(jié)構(gòu)，從 而增強了算法在解空間中的探索能力和效率。它的搜索行為是可控的。即通過 退溫歷程（即初溫、退溫函數(shù)）加以控制，控制初溫，可控制算法的初始搜索 行為?？刂茰囟鹊母叩停煽刂扑惴ㄍ惶芰Φ膹娙?。高溫下的強突跳性有利于 避免陷入局部極小，低溫下的趨化性尋優(yōu)有利于提高局部搜索能力?？刂茰囟?的下降速率，可控制突跳能力的下降幅度，影響搜索過程的平滑性。由此可見， 在優(yōu)化機制、結(jié)構(gòu)和行為上，改進遺傳模擬退火算法的混合優(yōu)化策略均結(jié)合了 遺傳算法和模擬退火算法的特點，兩種算法的搜索能力得到相互補充，使該算 法在優(yōu)化能力、效率和可靠性方面得到了提高。參考