動態(tài)輸電網(wǎng)絡規(guī)劃的組合編碼遺傳算法

高元海，王 淳

（南昌大學電氣與自動化系，江西 南昌 330031）

0 引言

輸電網(wǎng)絡規(guī)劃分為靜態(tài)規(guī)劃和動態(tài)規(guī)劃，靜態(tài)規(guī)劃只關心某一負荷水平年的線路架設方案，不考慮線路在何時進行架設的問題；動態(tài)規(guī)劃在規(guī)劃期內分為多個水平年，需要考慮何時何地架設多少線路，并且還要考慮到規(guī)劃期內不同水平年之間的過渡問題，這種規(guī)劃一般用于輸電系統(tǒng)的長期規(guī)劃[1]。動態(tài)輸電網(wǎng)絡規(guī)劃問題并不能簡單地看作多個靜態(tài)規(guī)劃問題的組合，因為其存在如下一些問題：1) 前一階段架設的線路必定在后續(xù)階段延續(xù)；2) 不同階段內的投資需要考慮到資金的時間效益。動態(tài)輸電網(wǎng)絡規(guī)劃較靜態(tài)規(guī)劃問題復雜很多。

輸電網(wǎng)絡規(guī)劃研究的對象是網(wǎng)絡的結構，各待選支路都需要作為獨立的決策變量來考慮，特別是 動態(tài)規(guī)劃問題還要考慮各支路在何時架設線路，其解空間的維度和組合空間規(guī)模都十分巨大。并且需要在各個階段都滿足多個約束條件（如線路的容量，支路線路的上限等），具有離散、非線性、多峰、不可微[2]等復雜的數(shù)學特征。人工智能算法在近幾十年內得到了快速發(fā)展，出現(xiàn)了：遺傳算法[3-4]、進化算法[5]、粒子群算法[6]、蜜蜂算法[7]、魚群算法[8]、食物鏈算法[9]、植物生長算法[10]等諸多智能算法。人工智能算法提供了一種通用的計算方法，其不依賴于問題的具體領域[11]，對具有離散、不可微等復雜數(shù)學特征的問題也能夠進行求解。人工智能算法從解空間的全局進行隨機有向搜索，同時從深度和廣度兩個方面進行，理論上能給出問題的全局最優(yōu)解。

自1975年Holland 創(chuàng)立遺傳算法以來，遺傳算法作為強有力且運用廣泛的隨機搜索和優(yōu)化方法，其可能是當今影響最為廣泛的智能算法之一[12]。在求解多階段輸電網(wǎng)絡規(guī)劃問題過程中需要考慮時間決策量，針對此問題文[4，10]采用了相應的編碼方式，但都各自存在一定的缺陷。為此本文提出了組合編碼法。組合編碼將多階段輸電網(wǎng)絡規(guī)劃問題的動態(tài)特征隱含其中，計算過程無需再單獨考慮時間決策量，使得動態(tài)規(guī)劃問題能夠類似靜態(tài)問題一樣使用遺傳算法進行求解。針對多階段輸電網(wǎng)絡規(guī)劃問題，采用了算術交叉、分段變異、減小罰系數(shù)等方法對遺傳算法進行了改進。以19 節(jié)點系統(tǒng)對算法進行驗證，結果表明所提方法能夠在較短的迭代次數(shù)內得到最優(yōu)解。

1 遺傳算法及其改進

遺傳算法是從問題潛在解集的一個隨機種群開始的，而一個種群則由經過基因編碼的一定數(shù)目的染色體組成。每個染色體實際上是帶有特征屬性的一個解。染色體作為遺傳物質的主要載體，即多個基因的集合，其編碼（基因型空間）是某種基因的組合，它決定了染色體所代表的解（表現(xiàn)型空間）。遺傳算法需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作，由于仿照基因編碼的工作很復雜，我們往往進行簡化。隨機生成若干個染色體構成初始種群，之后按照適者生存和優(yōu)勝劣汰的生物學進化原理，通過逐代演化產生越來越好的解。

遺傳算法的基本組成部分由Michalewicz 歸納[12]為：1) 問題的解的遺傳表示，即問題解的表現(xiàn)型空間如何通過合理的編碼映射到染色體的基因型空間；2) 創(chuàng)建解的初始種群，一般采用在基因型空間內按種群染色體數(shù)量隨機生成；3) 構建評價染色體優(yōu)劣的適應度函數(shù)，一般針對最小化或者最大化問題進行相應的函數(shù)變換來構建；4) 由父代染色體遺傳產生子代染色體的遺傳算子，一般包括選擇、交叉和變異；5) 遺傳算法的參數(shù)設定，由于遺傳算法屬于隨機算法，因此參數(shù)的選擇一般只能采用試探的方法。

1.1 組合編碼

如何將問題的解編碼成為染色體是遺傳算法使用中關鍵的一環(huán)。當染色體解碼為相應的解時其基因型空間到表現(xiàn)型空間的映射性質存在1 對1，1對n，n對1 三種情況。我們最希望的是1 對1 映射，因為該映射能夠保證在產生后代時不會存在無價值的操作[12]。染色體基因型空間的距離與表現(xiàn)型空間的距離要盡量一致，若編碼方法不合理，一個在表現(xiàn)型空間相鄰的解編碼為染色體時在基因型空間距離卻是最遠時，那么稱為出現(xiàn)了Hamming 懸崖[12]，此時會嚴重影響遺傳算法的性能。

動態(tài)問題與靜態(tài)問題的區(qū)別在于支路中線路的架設還包含有架設時間這個決策變量，需要考慮各支路在哪個階段架設多少線路。文獻[4]中以每條線路架設的階段作為變量，并且采用二進制數(shù)編碼。該編碼方式存在比較嚴重的冗余問題。冗余的原因在于：1) 同一支路的各條線路之間并沒有區(qū)別，該編碼方式卻將其單獨處理，編碼的結果會導致同一個表現(xiàn)型對應多個基因型；2) 階段的數(shù)量用二進制表示時存在冗余，例如有4 個規(guī)劃階段，那么表示1、2、3、4、5（5 表示在整個階段都不建設）這5個狀態(tài)則需要3 個二進制位，而3 位二進制可以表示8 個狀態(tài)，因此出現(xiàn)了冗余的無效染色體。文獻[10]采用了實數(shù)編碼，染色體的每一位代表一條線路，對應位的數(shù)值表示架設的階段。該編碼方式雖然能避免產生無效的冗余染色體，但是與文獻[4]一樣，多個染色體會對應同一個架設方案，也出現(xiàn)了基因型空間到表現(xiàn)型空間n對1 的缺陷。

為了實現(xiàn)基因型空間到表現(xiàn)型空間1 對1，以及基因型空間中沒有無效染色體的目的，提出了組合編碼法。由于每條支路所增設線路都有一定的上限，且該上限一般較小，因此每條支路在整個規(guī)劃期內各個階段的架設方案的組合數(shù)量較少。增設上限為2 條線路的支路在4 個階段內的組合數(shù)量是15，增設上限為3 條線路的支路在4 個階段內的組合數(shù)量也不過是35，從而可以通過枚舉法將各個支路在給定階段的規(guī)劃方案的組合單獨求出。編碼過程中，首先找出可架設線路的支路，基因的每一位表示一條可增設線路的支路；然后按一定的組合規(guī)律計算出各支路在規(guī)劃期內獨立的組合方案，對應位的值表示該支路的規(guī)劃方案編號。以增設上限為2 條線路的支路為例，表1 中枚舉出該支路的15 種組合方案，那么對應的基因位的取值為[1,15]內的整數(shù)。

這樣的編碼方式能夠保證基因型到表現(xiàn)型的1對1 映射，表1 中的編碼結果也清晰表明表現(xiàn)型空間與基因型空間避免了Hamming 懸崖的問題，在基因型空間相鄰的2 個編碼在表現(xiàn)型空間對應的2 個解也是相鄰的。該編碼方式將多階段的規(guī)劃方案變成了各個支路在整個階段的規(guī)劃方案的組合問題，架設時間的決策變量已經隱含在編碼中不需要另做考慮。完成編碼后，將資金的時間效益考慮進來就可以采用類似于靜態(tài)規(guī)劃問題的方法進行求解。

表1 某支路在4 個階段的方案Table 1 Planning of a branch in four stages

1.2 適應度函數(shù)及懲罰系數(shù)的設定

動態(tài)輸電網(wǎng)絡規(guī)劃問題的組合數(shù)量龐大，為加快遺傳算法的收斂速度，參照文獻[3]中采用的指數(shù)變換法對目標函數(shù)進行構造，其中線路的容量約束采用式(1)所示的罰方法并入目標函數(shù)，將其轉化為無約束問題。

其中：C為線路在多個階段的投資費用的貼現(xiàn)值，計算方法在下文給出；Op為網(wǎng)絡在各個規(guī)劃階段的過負荷量的總和，其采用直流潮流模型進行潮流計算求出；Kpunish為網(wǎng)絡出現(xiàn)過負荷的懲罰系數(shù)；Cav是種群中C*的平均值；β是一個給定的系數(shù)；M為遺傳算法的進化的代數(shù)；U為適應度函數(shù)。

為了準確評估規(guī)劃方案的優(yōu)劣，理論上懲罰系數(shù)應選擇較大的值。但是最優(yōu)解可能依賴某些過負荷的方案通過交叉變異得到，有些接近最優(yōu)解的次優(yōu)解染色體可能在交叉變異過程中導致過負荷，這些染色體攜帶了優(yōu)良的基因信息，為了保留這些染色體，懲罰系數(shù)又不能選的過大，否則很難得到最優(yōu)解而收斂到那些有冗余線路的次優(yōu)解。為了更好地收斂到最優(yōu)解，在迭代的初期選擇適當小一點的罰系數(shù)，隨著迭代的進行再逐漸增加。為此在進化過程中，將種群中不過負荷且投資最小的方案作為最終迭代結束的待選方案，當進化過程中出現(xiàn)不過負荷且投資更小的方案時替換上一次的待選方案，在進化結束時就能得到進化過程中出現(xiàn)過的最好的方案。

1.3 算術交叉

文中使用的組合式的實值(整數(shù))編碼方式，其交叉有離散交叉，算術交叉等方式。動態(tài)輸電網(wǎng)絡規(guī)劃問題的編碼每一位代表的是對應支路在整個規(guī)劃期內的規(guī)劃方案，其每一位的狀態(tài)數(shù)相對于2 進制編碼較多，上述2 條待選線路的支路在4 個階段的規(guī)劃期內的規(guī)劃方案有15 種，因此應采用算術交叉方式。常用的算術交叉方式為：λY+(1-λ)Z。其中Y，Z表示2 個染色體向量，λ為[-d,1+d]上的隨機數(shù)[12]。由于多階段輸電網(wǎng)絡問題的染色體向量維度較多，若對整個向量作一次性的交叉效果不佳，本文對染色體的每一位進行均勻的算術雜交，然后對其取整。（d的取值一般為0～1，本文取0.25）。

舉例如下：

解空間：([1,5];[1,5];[1,5];[1,35];[1,15];[1,35])

染色體Y：5|1|3|9|13|20

染色體Z：3|1|2|20|9|16

λ1：0.12|0.50| 0.68|1.02|0.90|-0.23

λ2：0.72|0.63|-0.15|1.20|0.38|0.27

子代1：3.24|1|2.68|8.78|12.60|15.08 取整后為3|1|3|9|13|15

子代2：4.44|1|1.85|6.80|10.52|17.08 取整后為4|1|2|7|11|17

1.4 分段變異

變異本身具有很強的全局搜索能力，往往通過變異能產生新的基因片段，從而可能產生新的較優(yōu)染色體。變異方式的選擇非常重要，在輸電網(wǎng)絡規(guī)劃中采取的變異方式是每次變異只隨機選擇2 位或者1 位進行變異。

在進化（迭代）的初期，主要是進化那些投資費用大且過負荷也很嚴重的適應度很差的染色體。當某一基因位發(fā)生變異時，表現(xiàn)為該支路在各階段的組合方案發(fā)生變化，此時網(wǎng)絡的結構在該支路發(fā)生變化后可能會出現(xiàn)過負荷或者冗余等問題。若另外一條支路的方案也做相應調整，這樣就可能相互之間彌補。因此初期采取成對變異是合適的。隨著進化的推進，線路投資和過負荷達到較好的狀況時，如果繼續(xù)進行成對變異則會對最優(yōu)解的搜索帶來不良影響，可能難以得到最優(yōu)解。一般來說，次優(yōu)解相對于最優(yōu)解可能存在冗余線路，因此在進化的末期適合采用1 位變異來實現(xiàn)對某些冗余線路的規(guī)劃方案進行改變以獲得最優(yōu)解。簡而言之：在進化的初期采用成對變異，進化的后期采用單獨變異。

2 動態(tài)輸電網(wǎng)絡規(guī)劃模型

以式(4)所示的規(guī)劃期內投資費用的貼現(xiàn)值作為目標函數(shù)；并滿足式(5)、式(6)線路容量約束，式(7) 支路可增設線路數(shù)量約束。

目標函數(shù)為

約束條件為

3 計算流程

步驟1 原始數(shù)據(jù)讀取、編碼預處理：按1.1 節(jié)的方法對各支路可架設線路數(shù)量在給定的規(guī)劃階段內分別枚舉出架設方案得到基因型空間到表現(xiàn)型空間的編碼表。

步驟2 初始化種群：根據(jù)各支路的方案組合數(shù)量隨機生成基因，在滿足網(wǎng)絡結構連通性（各階段都要滿足）的約束下，生成給定種群規(guī)模的染色體初始種群。

步驟3 適應度計算：種群中每個染色體表示一個規(guī)劃方案，通過直流潮流計算，分析各個染色體構成的網(wǎng)絡在各個階段的潮流，從而計算出各支路在不同階段的過負荷總量。然后計算各個染色體對應方案的投資費用，利用適應度函數(shù)計算出種群中各個染色體的適應度值。將適應度值高的10%～15%染色體作為精英放入精英庫。

步驟4 輪盤賭選擇：將種群各個染色體的適應度值形成生存概率表，根據(jù)生存概率表構成輪盤，通過多次輪盤賭，選擇出待交叉變異的染色體。

步驟5 交叉變異：將選擇出來的染色體按1.3節(jié)給出的方式進行交叉，以一定的隨機概率按1.4節(jié)給出的方式進行變異，從而產生新的子代染色體，子代中的糟粕染色體用精英庫中的染色體代替。

步驟6 收斂性判斷：產生的子代代替父代進行迭代進化，進化過程中保留無過負荷且投資費用最小的染色體作為待選的最優(yōu)解。按一定的收斂條件判斷終止迭代，如設定一定的迭代次數(shù)上限。滿足條件時輸出迭代進化過程中最優(yōu)的方案以及對應的投資費用。

4 算例分析

如圖1所示為19 節(jié)點測試系統(tǒng)[13]，其包含有4個規(guī)劃階段，有12 條支路共21 條線路可以增設。對每條支路在規(guī)劃期內各階段的增設方案進行枚舉，圖1所示支路2-3 有3 條線路可以增設，在4個規(guī)劃階段內有35 種規(guī)劃方案，該基因位對應解空間內的一個維度，該維度的取值范圍為[1,35]之間的整數(shù)。該測試系統(tǒng)的解空間為：([1,35];[1,5];[1,15];[1,35];[1,35];[1,5];[1,35];[1,5];[1,5];[1,5];[1,5];[1,5])。算法參數(shù)設定：種群規(guī)模為80；變異率為0.16；交叉系數(shù)d為0.25；懲罰系數(shù)初值設定為69，并隨進化代數(shù)T按69+30ln(T)逐漸增加；精英比例為10%。按照上節(jié)給出的流程計算，迭代進化次數(shù)的上限設定為120 次。圖2所示為經過92 次迭代后搜索到最優(yōu)解的投資費用進化圖，其投資總費用的貼現(xiàn)值為649.921 9 萬元，該方案的基因型為：30|3|7|22|12|1|7|1|1|1|1|1，解碼后如表2所示。按上述參數(shù)重復進行20 次測試，結果如圖3所示。有4次得到最優(yōu)解649.921 9 萬元，其余是與最優(yōu)解非常接近的次優(yōu)解，投資費用的平均值為659.568 3 萬元。表明在較少的迭代進化次數(shù)下能夠得到最優(yōu)解或與最優(yōu)解接近的次優(yōu)解。

圖1 19 節(jié)點系統(tǒng)網(wǎng)絡結構圖Fig.1 Network structure of 19-bus system

圖2 投資費用的進化圖Fig.2 Evolutionary process of investment costs

表2 19 節(jié)點系統(tǒng)最優(yōu)規(guī)劃方案Table 2 The best planning of 19-bus system

圖3 20 次重復測試結果Fig.3 Results of 20 repeating tests

5 結論

本文采用組合編碼法將多階段輸電網(wǎng)絡規(guī)劃問題中需要考慮的時間決策變量包含進來，從而解決了各個階段之間復雜的協(xié)調耦合問題。該編碼方式滿足基因型到表現(xiàn)型的1對1映射，以及基因型空間和表現(xiàn)型空間距離的一致性，從而使得遺傳算法求解過程中不會存在重復和無效的編碼且不存在Hamming懸崖，保證了算法的搜索效率。針對多階段輸電網(wǎng)絡規(guī)劃的具體問題采用了算術交叉、分段變異、減小罰系數(shù)等方法對遺傳算法進行了改進，改進后的算法性能有了進一步的提高。以19節(jié)點系統(tǒng)為例驗證了所提方法的可行性。

[1]王錫凡.電力系統(tǒng)規(guī)劃基礎[M].北京:中國電力出版社,1994.

WANG Xi-fan.Foundation of power system planning[M].Beijing:China Electric Power Press,1994.

[2]李翔碩,王淳,龔姣龍.基于食物鏈生態(tài)進化算法的多階段輸電網(wǎng)絡規(guī)劃[J].南昌大學學報:工科版,2012,34(1):93-97.

LI Xiang-shuo,WANG Chun,GONG Jiao-long.Multistage transmission network planning based on ecology evolutionary algorithm of food chain[J].Journal of Nanchang University:Engineering &Technology,2012,34(1):93-97.

[3]王秀麗,王錫凡.遺傳算法在輸電系統(tǒng)規(guī)劃中的運用[J].西安交通大學學報,1995,29(8):1-9,16.

WANG Xiu-li,WANG Xi-fan.Transmission system planning with genetic algorithm[J].Journal of Xi’an Jiaotong University,1995,29(8):1-9,16.

[4]毛玉賓,王秀麗,王錫凡.多階段輸電網(wǎng)絡最優(yōu)規(guī)劃的遺傳算法[J].電力系統(tǒng)自動化,1998,22(12):13-15,19.

MAO Yu-bin,WANG Xiu-li,WANG Xi-fan.Genetic algorithm for the optimal multistage transmissionnetwork planning[J].Automation of Electric Power Systems,1998,22(12):13-15,19.

[5]王秀麗,李淑慧,陳皓勇,等.基于非支配遺傳算法及協(xié)同進化算法的多目標多區(qū)域電網(wǎng)規(guī)劃[J].中國電機工程學報,2006,26(2):11-15.

WANG Xiu-li,LI Shu-hui,CHEN Hao-yong,et al.Multi-objective and multi-district transmission planning based on NSGA-II and cooperative co-evolutionary algorithm[J].Proceedings of the CSEE,2006,26(12):11-15.

[6]金義雄,程浩忠,嚴健勇,等.改進粒子群算法及其在輸電網(wǎng)規(guī)劃中的應用[J].中國電機工程學報,2005,25(4):46-50,70.

JIN Yi-xiong,CHENG Hao-zhong,YAN Jian-yong,et al.Improved particle swarm optimization method and its application in power transmission network planning[J].Proceedings of the CSEE,2005,25(4):46-50,70.

[7]曾鳴,田廓,薛松,等.基于混沌量子蜜蜂算法的機會約束輸電規(guī)劃[J].電力系統(tǒng)保護與控制,2010,38(22):1-7,14.

ZENG Ming,TIAN Kuo,XUE Song,et al.Chance constrained transmission planning method based on chaos quantum honey bee algorithm[J].Power System Protection and Control,2010,38(22):1-7,14.

[8]李如琦,王宗耀,謝林峰,等.種群優(yōu)化人工魚群算法在輸電網(wǎng)擴展規(guī)劃的應用[J].電力系統(tǒng)保護與控制,2010,38(23):11-15.

LI Ru-qi,WANG Zong-yao,XIE Lin-feng,et al.Population optimization artificial fish school algorithm applied in transmission network planning[J].Power System Protection and Control,2010,38(23):11-15.

[9]龔嬌龍,王淳,程虹,等.食物鏈生態(tài)進化算法的改進及其在輸電網(wǎng)絡規(guī)劃中的應用[J].電力系統(tǒng)保護與控制,2011,39(7):38-49.

GONG Jiao-long,WANG Chun,CHENG Hong,et al.Improved ecology evolutionary algorithm of food chain and its application in power transmission network planning[J].Power System Protection and Control,2011,39(7):38-49.

[10]王淳,萬衛(wèi),程虹,等.多階段輸電網(wǎng)絡最優(yōu)規(guī)劃的模擬植物生長算法[J].高電壓技術,2009,35(4):937-942.

WANG Chun,WAN Wei,CHENG Hong,et al.Plant growth simulation algorithm for the optimal multistage transmission network planning[J].High Voltage Engineering,2009,35(4):937-942.

[11]王小平,曹立明.遺傳算法理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002:1-50.

WANG Xiao-ping,CAO Li-ming.Theory and application of genetic algorithms and its software implementation[M].Xi’an:Xi’an Jiaotong University Press,2002:1-50.

[12]玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學出版社,2004:1-13,21-30.

XUAN Guang-nan,CHENG Run-wei.Genetic algorithms and engineering optimization[M].Beijing:Tsinghua University Press,2004:1-13,21-30.

[13]程浩忠,張焰.電力網(wǎng)絡規(guī)劃的方法與應用[M].上海:上?？茖W技術出版社,2002.

CHENG Hao-zhong,ZHANG Yan.Method and application of power network planning[M].Shanghai:Shanghai Science and Technology Press,2002.