基于改进遗传算法的电力光传输网规划方法

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



基于改进遗传算法的电力光传输网规划方法

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

（北京邮电大学网络与交换技术国家重点实验室，北京 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-），男，山东莱芜人，北京邮电大学教授、硕士生导师，主要研究方向为网络管理体系结构、网络管理系统分析和建模理论、网络管理接口测试理论及技术、电信运营系统和软件等。