基于改進遺傳算法的電力光傳輸網規劃方法

石悅，邱雪松，郭少勇，亓峰

?

基于改進遺傳算法的電力光傳輸網規劃方法

石悅，邱雪松，郭少勇，亓峰

（北京郵電大學網絡與交換技術國家重點實驗室，北京 100876）

為保證建成的電力通信網絡滿足智能電網堅強可靠、經濟高效的需求，提出一種兼顧網絡建設成本和網絡可靠性的電力光傳輸網線路規劃方法，設計出基于站點成環率和電壓等級的可靠性函數，建立了線路規劃問題的多目標優化模型，在此基礎上，用改進的遺傳算法對問題進行求解，仿真結果表明，提出的規劃方法能夠提供有效的線路規劃方案，具備較優的算法性能。

智能電網；光傳輸網；網絡規劃；遺傳算法；可靠性

1 引言

近年來，隨著智能電網的發展，通信、計算機技術在電網中得到了廣泛深入的應用，逐漸形成了分層分級結構的電力專用通信網絡結構，用以支持各類新型智能電網業務。為滿足智能電網堅強可靠、經濟高效的目標[1]，在規劃建設電力通信網絡時應重點考慮網絡建設成本和網絡可靠性兩大指標，即以最小的代價建設最可靠的通信網絡是電力通信網規劃的關鍵問題之一。

目前，電力骨干通信網已經形成以光纖通信為主，微波、載波、衛星等多種傳輸方式并存的局面。其中，依托光纖通信的電力光傳輸網主要用于承載電力調度及生產實時控制業務，對整個電力系統的安穩運行起著至關重要的作用，各級電力光傳輸網要求實現互聯互通[2]。然而，目前電力光傳輸網存在一些問題：一是110 kV以下站點的光纖覆蓋率水平低，部分地區仍采用租用公網通信方式解決35 kV變電站通信接入問題，這勢必會對通信網容災能力、無人值班模式推行、調度數據專網覆蓋等工作形成制約，難以滿足智能電網中堅強可靠的要求；二是部分光纜存在纖芯緊張，運行可靠性低等問題；三是個別光纜承載保護、安控業務過重，光纜檢修或故障將造成多條保護通道中斷，電網安全運行風險較大。

由上述問題可以看出，對電力光傳輸網的改造和擴建亟需進行，為保證網絡建設的經濟性和可靠性，需要進行合理的規劃設計。通信線路規劃是網絡規劃設計的一個重要內容，是指在已知通信站點位置和業務分布的基礎上，根據現有網絡結構，在滿足業務分布和可靠性約束的條件下，確定出經濟性最佳的通信線路部署方案[3]。目前針對電力通信網規劃問題已有一些研究，文獻[4]對電力通信網的整體架構進行規劃優化，通過向網絡中部署分布式測量數據管理系統（D-MDMS, distributed meter data management system），將現有的中心式控制架構轉變為分布式控制架構，目的是減小用戶側數據的傳輸距離，并提前在D-MDMS中過濾一部分無用信息，從而提高了網絡資源的利用率并降低了網絡建設成本。文獻[5]通過向智能電力通信網中部署冗余站點來提高網絡的容災能力，在一定程度上提高了網絡可靠性，但冗余資源會導致網絡成本的提高，沒有對網絡經濟性進行相應的約束。文獻[6]抽象出基于電力線通信（PLC, power line communication）的低壓配電通信網絡模型，構造了網絡建設成本模型，提出了一種電力線通信中的接入節點(AP, access points)選址規劃方法，并給出了路由優化方案，有效降低了網絡的建設成本，但該方法主要面向下層的配電通信網，且規劃的對象是通信節點，無法適用于傳輸層網絡的線路規劃問題。文獻[7]建立的電力通信傳輸網的線路規劃模型，考慮了網絡時延和容量，利用啟發式算法解決了線路部署問題，但該方法沒有考慮站點成環率，難以保證網絡可靠性，且默認網絡中的所有站點電壓等級均相同，未能區分不同電壓等級站點在重要度和成環率方面的差別，與實際情況有所差異。總而言之，雖然目前電力通信網絡規劃問題已有一些研究，但針對光傳輸網線路規劃的研究還相對較少，因此需要重點研究，以解決其在擴建和改造時面臨的經濟性和可靠性問題。

針對電力通信網規劃中存在的問題，本文同時考慮網絡建設的經濟性和可靠性兩大因素，重點解決電力骨干通信網中的光傳輸網線路規劃問題。首先，基于圖的結構抽象出光傳輸網模型，利用節點權值區分不同站點的電壓等級，用以模擬現實網絡環境。隨后，引入網絡成本函數，并基于站點成環率這一電力通信網的重要特性建立網絡可靠性函數，從而建立光傳輸網線路規劃的數學模型。在此基礎上，利用改進的遺傳算法對問題進行求解，并利用Matlab對21節點系統進行仿真，對本文算法和傳統遺傳算法做了仿真實驗，并對比不同約束條件下的規劃結果，結果表明本文算法具有較高靈活性，且算法性能較優。

2 電力光傳輸網線路規劃問題

2.1 問題描述

電力骨干通信網覆蓋35 kV及以上電網，由跨區、區域、省、地市等4級通信網絡組成，如圖1所示，主要承載語音、數據、運動、繼電保護、電力監控等電力通信業務網絡。

本文研究電力骨干通信網中的光傳輸網線路規劃問題，即在進行網絡擴建時，已知通信站位置的基礎上，根據現有的網絡結構和待選光纜線路，在滿足可靠性和業務分布約束的前提下，確定出經濟性最佳的光纜布線方案。利用圖的結構對光傳輸網建模，圖的頂點表示通信站點，邊表示光纜線路，如圖2所示，以圖的結構對問題進行建模，圖中頂點表示通信站點，邊表示光纜線路，如圖2所示，圖中123456和7表示現有網絡站點，89101112131415和16表示新增站點，實線表示已有線路，虛線表示待擴建線路。該問題就是如何從條待選線路中選擇(≤)條線路構成最經濟可靠的網絡結構。

通信網絡可靠性可從2個層面考慮，一是底層物理架構的可靠性，如拓撲結構、設備和鏈路自身可靠性等；二是上層業務的可靠性，如業務最短路徑、冗余路由保護等。底層架構為上層業務提供支撐，是上層業務的基礎和前提，因此需要首先進行規劃設計。本文從拓撲結構層面考慮網絡可靠性，環形拓撲是電力光傳輸網中最常見的拓撲結構，其能夠為業務提供環形保護，如1+1保護、1+保護、1:保護等，使網絡能夠規避或減小由光纖故障造成的損失，因此站點成環率是量化電力光傳輸網可靠性的重要指標之一，在進行線路規劃時需要重點考慮。此外，在選擇線路時還需要考慮站點電壓等級，目前我國電力通信網絡中的站點電壓等級由低到高分別為：3 kV、6 kV、10 kV、35 kV、60 kV、110 kV、220 kV、330 kV、500 kV、750 kV和1 050 kV。電壓等級高的站點管轄區域更廣、所處控制層級更高、承載業務流量更大（如某地區500 kV變電站承載的業務凈流量為92 Mbit/s，而地區35 kV變電站承載的業務凈流量只有19 Mbit/s），因此高電壓等級的站點對可靠性（即站點成環率）的要求也相對更高。目前，我國電力骨干通信網的成環率約為73%，其中220 kV及以上站點成環率為100%[3]。

2.2 數學模型

1) 網絡建設成本函數。指在規劃方案中新加入網絡的光纜線路的建設成本，如式(1)所示。

其中，表示網絡建設成本；表示待選光纜線路數；∈{0,1} ，當第條光纜被選中時，e為1，否則e為0；c表示第條線路e的建設成本。

2) 網絡可靠性約束。由上文可知，網絡可靠性由2部分線性加權組成：一是站點成環率；二是成環站點電壓加權值。在實際網絡中，某區域內的高電壓等級的站點匯聚了本區域內的信息數據，并逐級上報（或下發）至上級（下級）網絡，因此高電壓等級的站點通常位于本區域的邊界，且距離區域中心的距離較遠。為此類站點規劃一條相連光纜需要耗費較高的經濟成本，且對站點成環率的提升較小。為保證在線路規劃時能夠同時兼顧站點成環率和電壓等級，本文將這兩大因素進行整合，如式（2）所示。

由于站點成環率為0至1之間的概率，而站點電壓值與成環率相比屬于大數，在數量級上有很大差別，因此在進行加權時需要先對其進行歸一化處理，具體方法見下文。式（2）中表示站點成環率；表示成環占站點電壓加權歸一化處理后的值；和分別是二者的權重系數，且。

3) 站點成環率。電力光傳輸網中以站點成環率來量化網絡可靠性，其值為網絡中成環站點數和總站點數的比值。

其中，為網絡中站點的總數，s代表成環站點。成環站點的定義有2種：一種是物理成環，即在網絡中由光纜相連而構成環狀結構的站點，如圖3中共有8個站點，成環站點為1234和5，因此該網絡的成環率為0.625；另一種是邏輯上成環，即在物理成環的基礎上，利用相應網管系統進行線路配置，開通相應的業務通路，其涉及到邏輯層面上的通道、復用段等概念，不在本文討論范圍，故本文只考慮物理層面上的站點成環率。

圖3 成環站點示意

4) 成環站點電壓加權值。由上文可知，電力光傳輸網中電壓等級越高的站點成環率要求也相對較高，成環站點電壓加權值是反映高電壓站點成環情況的指標，該值越高，表明越多的高電壓站點形成環狀結構。根據上文所述，站點電壓等級與成環率分屬不同量綱，因此需要進行歸一化處理。設網絡中共有類不同電壓等級的站點，記為集合= {1,2,…,v},v∈為不同電壓值（單位：kV），如500、220、110、35等；本文采用min-max標準化方法對集合中的元素進行歸一化處理，如式（4）所示。

其中，min和max分別為集合中的最小值和最大值，d為v經歸一化處理后的值，設集合，令d∈。

基于此，得到成環站點電壓加權值的表達式

其中，為網絡中站點的總數；z為0-1變量，當第個站點在環狀結構上時，z為1，否則，z為0。

5) 網絡連通性約束。電力光傳輸網要求各級站點之間實現互聯互通，不允許出現“信息孤島”。因此在進行光纜線路規劃時，應確保光纜覆蓋網絡中的所有站點，避免出現網絡解裂。

可以看出，電力光傳輸網線路規劃屬于多目標優化問題，已被證明為NP問題[3]。模擬生物智能的啟發式算法（如遺傳算法、免疫算法、蟻群算法、粒子群算法等）能夠在有限時間內解決此類問題。在眾多啟發式算法中，遺傳算法在全局搜索能力和靈活度方面都表現較優[8]，因此本文選取遺傳算法對光傳輸網線路規劃問題進行求解。

3 基于遺傳算法的線路規劃方法

遺傳算法是從代表問題可能潛在解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的染色體組成。在算法實現過程中，首先需要進行染色體編碼，在產生初代種群之后，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解，在每一次迭代過程中，根據問題域中染色體的適應度大小選擇染色體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼，可以作為問題近似最優解[9]。

1) 染色體編碼

在利用遺傳算法解決光傳輸網線路規劃問題時，每一個染色體代表一個線路規劃方案。本文采用二進制編碼，每個基因位代表一條待選光纜線路，當基因位為1時表示該條線路被選中，否則基因位為0。例如，某網絡有6條待選光纜線路，染色體s的編碼為{100101}，表示該線路規劃方案是將第1、4、6條待選線路加入網絡。

2) 適應度函數

適應度函數由經濟性和可靠性兩方面決定。其中經濟性用式（1）中的成本函數表示，其值越小說明網絡建設成本越低、經濟性越好。可靠性由式（2）中的可靠性函數表示，其值越高可靠性越好。由于目標函數的優化方向對應抗體親和度增加的方向，因此染色體s的適應度函數如式(6)所示。

其中，為一個大數，保證(s)的值為正；1和2分別為經濟性和可靠新的權重系數，且1+2=1，用以調整規劃方案對經濟性或可靠性的偏重程度，本文在仿真實驗部分首先賦予二者一個初始值，隨后逐漸對該值進行調整并進行仿真實驗，最終確定1和2最佳取值，具體內容見后續章節；是調節因子，由于、相對而言是大數，為平衡經濟性和可靠性對(s)的影響程度，需利用將二者取值調節至相同數量級。

3) 染色體濃度

為避免遺傳算法陷入局部最優，本文引入染色體濃度函數，其定義如下。

已知(s)和(s)分別為染色體s和染色體s的適應度，則

為代表染色體s和染色體s的相似度指標。若存在任意整數，使

(8)

成立，則稱染色體s和染色體s相似。記

染色體s的濃度是指種群中與s相似的染色體的數目與種群規模的比值，記作

(10)

其中，N為種群規模。染色體濃度函數用來表征某個染色體與種群中其他染色體的相似程度，通過將其引入選擇算子，用以避免算法重復選擇相似度過高的染色體而陷入局部最優，具體方式如下。

4) 選擇算子

在選擇染色體時，既要保證優秀染色體能以較大的概率被選中，又要保證子代種群的多樣性，避免算法陷入早熟，因此本文采用正比染色體使用度、反比染色體濃度的選擇算子

其中，(s)是染色體s的選擇概率。

5) 變異算子

本文算法采用2點變異，首先判斷染色體是否滿足成環率約束，若不滿足，則從其值為0的基因位中隨機挑選2個設置為1；若滿足，則從其全部基因位中隨機挑選2個取反。

4 實驗分析

為了驗證本文提出的規劃方法對電力光傳輸網線路規劃的有效性，將利用本文方法對國內某地市光傳輸網進行仿真實驗。如圖4所示，該網絡中共有4類站點，分別為500 kV站點、220 kV站點、110 kV站點以及35 kV站點；網絡中共有35條光纜線路，其中實線表示原有線路，虛線表示待擴建線路。出于篇幅原因，本文列出了部分光纜線路的經濟成本，如表1所示。

表1 光纜線路成本

本文算法中，種群規模均取80，交叉概率取0.6，變異概率取0.1，最大進化代數取300。首先通過調整經濟性和可靠性的權重系數，得到網絡建設成本與站點成環率之間的對應關系，如圖5所示。可以看出，隨著成環率的升高，網絡建設成本也逐步增加，這是由于需要建設更多的光纜用以構成環狀網絡。具體實驗數據如表2所示。

表2 詳細仿真數據

由表2可以看出，初始1和2分別為0.9和0.1，這表示規劃方案中的經濟性因素遠大于可靠性因素，即規劃方案主要考慮降低網絡建設成本，對可靠性的要求不高，雖然得到了最低的網絡建設成本435，但站點成環率只有28.75%，難以滿足電力通信網高可靠的需求。通過下調經濟性權重系數，網絡建設成本逐漸升高，相應的站點成環率也隨之增加。經濟性和可靠性逐漸趨于平衡，在1和2分別為0.4和0.6時，站點成環率為76.19%，超出了電力骨干傳輸網的平均水平（即上文所述的73%），同時，220 kV及以上站點和110 kV及以上站點的成環率分別為100%和90%，說明規劃方法能夠將高電壓等級的站點優先組成環狀結構，滿足電力通信網的要求。

選取表2中的第6、第7和第8組數據，觀察3組實驗的算法適應度函數隨進化代數的變化，如圖6所示。可以看出，在面對不同的權重系數時，本文算法的適應度函數在進化初期快速上升，并均能在有限進化代數內達到收斂，說明本文算法在面對不同實驗參數時均能表現出良好的算法性能，具備較高的靈活性。

利用式（2）對以上3組數據的站點成環率和成環站點電壓加權進行擬合，得到網絡可靠性隨進化代數的變化關系，如圖7所示。可以看出，網絡可靠性隨著算法的運行逐漸升高并達到收斂。同時，網絡可靠性與可靠性權重系數2成正比，說明權重系數1和2能夠有效影響仿真結果。

由上文可知，本文算法通過引入染色體濃度函數以避免陷入局部最優，為了驗證這一改進給算法性能帶來的提高，對本文算法與傳統遺傳算法做了對比實驗。設置傳統遺傳算法的種群規模均取80，交叉概率取0.6，變異概率取0.1，最大進化代數取300。設置權重系數1和2的值分別為0.4和0.6，各條光纜線路的成本和建設情況如表1所示。為避免算法執行過程中的偶然性，本文對2種算法各執行10次，取算法各項性能平均值做比較。2種算法的性能曲線如圖8所示。

從圖8可以看出，2種算法的適應度在初期均能快速上升，并逐漸達到收斂，但本文算法收斂后的適應度明顯高于傳統遺傳算法，說明本文算法具備更高的性能。2種算法的方案成本隨進化代數的變化曲線如圖9所示。

從圖9可以看出，隨著進化代數的增加，本文算法的方案成本下降更快，能獲得更低的建設成本。而傳統遺傳算法由于沒有引入染色體濃度函數，在執行過程中容易陷入早熟，無法得到最優的線路部署方案。

圖10所示為本文算法規劃后的實際網絡拓撲，結合表2可知，該規劃方案的成環率為76.19%，其中沒有成環的站點共有5個，分別是站點1、站點2、站點3、站點5和站點6，主要集中在低電壓站點（110 kV及以下），表明本文規劃方法在進行光纜線路規劃時，能夠優先考慮高電壓站點的可靠性，與電力通信網的實際情況相符。

5 結束語

為了建設堅強可靠、經濟高效的智能電網，本文提出了基于遺傳算法的電力光傳輸網線路規劃方法。構造了網絡建設的經濟成本函數和可靠性函數，其中可靠性函數能夠體現出站點成環率和成環站點電壓等級這2個因素，符合現網中的實際情況。實驗結果表明本文提出的規劃方法能夠有效解決光纜線路規劃問題，具有很高的靈活性。下一步工作將橫向比較不同啟發式算法求解線路規劃問題的性能，進一步提高算法的效率。

[1] ZHONG F, PARAG K, SEDAT G, et al. Smart grid communications: overview of reaserch challenges, solutions, and standardization activities [J]. IEEE Communications Surveys & Tutorials, 2013, 15(1): 21-38..

[2] 曹軍威, 等. 智能電網信息系統體系結構研究[J]. 計算機學報, 2013, 36(1):143-167. CAO J W,et al. Information system architecture for smart grid[J]. Chinese Journal of Computers, 2013, 36(1):143-167.

[3] 曹惠彬. 國家電網公司“十二五”通信網規劃綜述[J]. 電力系統通信, 2011, 32(223):1-7. CAO H B. The summary of “12th five-year” telecommunication network plan of SGCC[J]. Telecommunications for Electric Power System, 2011, 32(223):1-7.

[4] ZHOU J Z, HU Q Y, QIAN Y. Scalable distributed communication architectures to support advanced metering infrastructure in smart grid[J]. IEEE Transcations on Parallel and Distributed System, 2012, 23(9): 1632-1642.

[5] DUSIT N Y, WANG P, EKRAM H. Reliability analysis and redundancy design of smart grid wireless communications system for demand side management[J]. IEEE Wireless Communications, 2012, 19(3):38-46.

[6] SILVIA C, et al. Optimal planning and routing in medium voltage power line communications networks[J]. IEEE Transactions on Smart Grid, 2013, 4(2): 711-719.

[7] JAHROMI A E, RAD Z B. Optimal topological design of power communication networks using genetic algorithm[J]. Scientia Iranica, Transactions Engineering, 2013, 20(3): 945-957.

[8] GUO P F, WANG X Z, HAN Y S. The enhanced genetic algorithms for the optimization design[C]//2010 3rd International Conference on Biomedical Engineering and Informatics (BMEI).c2010: 16-18.

[9] MANTAWY A H, ABDEL-MAGID Y L, SELIM S Z. Integrating genetic algorithms, tabu search, and simulated annealing for the unit commitment problem[J]. IEEE Transactions on Power System, 2002, 14(3): 829-835.

Optimal planning of optical transmission network using improved genetic algorithm

SHI Yue, QIU Xue-song, GUO Shao-yong, QI Feng

(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)

To ensure that power communication network to meet the reliable, economic requirements, a network planning method was proposed. Developing a reliability function based on ring rate and voltage class of communication station, then a multi-target programming model was established. An approach based on improved genetic algorithm was developed to solve the problem. Finally, simulation results show that the proposed method can provide efficient network planning solution with high performance.

smart grid, optical transmission network, network planning, genetic algorithm, reliability

TP302

A

10.11959/j.issn.1000-436x.2016013

2014-12-05；

2015-06-16

電力通信管理系統智能化提升與擴展技術研究及應用基金資助項目

Research and Application of Management System Intellectualization and Extension Technology in Electric Power Communication Foundation

石悅（1987-），男，北京人，北京郵電大學博士生，主要研究方向為智能電網通信網絡規劃與優化。

邱雪松（1973-），男，江西上饒人，北京郵電大學教授、博士生導師，主要研究方向為網絡管理與通信軟件、智能電網等。

郭少勇（1985-），男，河北隆堯人，北京郵電大學博士生，主要研究方向為泛在網絡管理、智能電網等。

亓峰（1971-），男，山東萊蕪人，北京郵電大學教授、碩士生導師，主要研究方向為網絡管理體系結構、網絡管理系統分析和建模理論、網絡管理接口測試理論及技術、電信運營系統和軟件等。