基于小世界纵横交叉算法在输电线路巡视路径中的应用

欧郁强，闻建中，王利国，杨玺，梁海蓬，孟安波，李德强，洪俊杰（.广东电网有限责任公司江门供电局，广东江门　59000；.广东工业大学，广东广州　50006）

基于小世界纵横交叉算法在输电线路巡视路径中的应用

欧郁强1，闻建中1，王利国1，杨玺1，梁海蓬1，孟安波2，李德强2，洪俊杰2
（1.广东电网有限责任公司江门供电局，广东江门529000；2.广东工业大学，广东广州510006）

输电线路巡视；小世界纵横交叉算法；贝叶斯网络；杆塔风险运行概率

输电线路是电力系统的重要组成部分［1］，其安全运行是系统整体稳定的重要保障。但是输电线路及其附属设备暴露在野外中，这种运行方式必定会受到环境因素、人为因素和设备自身等因素的影响。传统的输电线路巡视工作没有得到合理的规划，导致其缺乏效率和科学性，这样在一定程度上助长了输电线路的风险运行概率。同时，制定输电线路巡视路径可以有效提升人力资源和节省费用，所以，输电线路巡视路径规划是必要的。

目前输电线路巡视路径规划算法主要有线性规划法、人工智能算法［2-6］等。文献［7］提出对输电线路路径等目标进行规划，所用算法是原始遗传算法。对于多目标路径规划问题，遗传算法的编码方式导致程序运行效率较低和编程难度增加。文献［8］提出改进的遗传算法进行对输电线路无人机巡视路径进行规划，但改进的遗传算法进行路径规划寻优过程中容易陷入局部最优中不能跳出，导致无法寻找全局最优解。文献［9］针对巡检路径中车辆路径问题进行寻优，同时通过分析输电线路工作的内容及特点，制定特定的约束条件和目标函数，所用算法为混合算法，编程部分采用Microsoft Visual C++ 6.0和Matlab混合编程，其结果验证了模型的正确性和算法的有效性。

本文对输电线路巡视路径规划模型进行改进，通过贝叶斯［10-15］模型原理建立杆塔风险运行概率模型，在已知杆塔风险运行影响因素的情况下，求出杆塔的风险概率，在此基础上建立多目标巡视路径规划模型。搜索过程所用算法是SW-CSO （Small World Based Crisscross Optimization Algorithm，SW-CSO）算法，这种算法是在纵横交叉算法的基础上，加入小世界的思想，特点是在粒子寻优过程中增加粒子的搜索记忆，使得相邻邻域之间的粒子可以进行信息交换和共享。仿真部分采用拥有30个杆塔电网的数据，结果验证了模型的正确性和算法的有效性。

1　SW-CSO算法

基于Watts和Strogetz提出的小世界网络［9］模型和纵横交叉算法［16-17］（CSO），本文提出了一种新型的小世界纵横交叉算法（SW-CSO）。SW-CSO算法的主要思想是在原有CSO算法的基础上增加粒子的邻域记忆，通过邻域记忆来记录一定区域内的粒子路径或适应度。

粒子的邻域构造［18-19］过程是将每个粒子与其相邻的t个粒子组成一个邻域i，同时初始的种群拓扑结构是一个k阶规则网络。进化过程中每个区域中的粒子不断自行进化，基于区域划分思想将相邻区域粒子进行替代更新：首先，邻域i中的最佳粒子Xibest以概率p1代替邻域i中的粒子Xk；其次，在邻域j中抽出最佳粒子Xjbest以p2的概率的替代邻域i中的最佳粒子Xibest。这样的交换方式实现了不同邻域中之间的信息交流和同一个邻域中自行更新，使得种群的收敛精度和速度大大增强。

下面分别介绍横向交叉算子、纵向交叉算子和竞争算子的具体操作流程。

1.1横向交叉算子

横向交叉算子的搜索方式是区域t中的2个不同粒子的所有维中进行的一种算数运算。假设区域t中2个粒子的第d维分别为X（t，i，d）和X（t，j，d），则它们的子代为

式中：r1和r2为0～1之间的随机数；c1和c2为-1～1之间的随机数；D为粒子的维度；M为粒子的规模；t为粒子的区域为子代粒子。

1.2纵向交叉算子

纵向交叉算子是一个粒子的不同维度算数运算，这种运算可以使陷入局部最优的种群跳出，并快速收敛到全局最优。假设粒子X（t，i）的第d1维和第d2维进行交叉，可表示为：

式中：r为0～1之间的随机；X（t，i）为区域t中的父代粒子；MSvc（t，i，d）为区域t中的一个粒子的第d1维和第d2维通过交叉运算产生的子代。

与遗传算法不同，SW-CSO算法中的纵向交叉可以以一定概率跳出父代粒子所在的范围［13］。假如父代粒子的范围在（x1，x2）和（y1，y2）之间，则生成的子代粒子的概率如图1所示。

1.3竞争算子

图1 二维空间的概率分布Fig.1　Distribution of probability density of the moderation solutions for 2-D space

传统竞争算子是一种淘汰机制，它的功能是将2个的粒子的适应度进行对比，只有适应度更强的粒子才能参与下一次迭代。其具体流程如图2所示。

将小世界网络的思想与竞争算子结合后，改进的竞争算子如图3所示。

图2　竞争算子的流程Fig.2　Procedure of the competitive operator

图3　竞争算子的流程Fig.3　Procedure of the competitive operator

2　输电杆塔风险运行概率

输电杆塔风险运行概率是输电线路巡视路径目标函数的一项指标，同时也是杆塔运行状态的一项参考数据。风险概率模型的构建步骤：

1）收集杆塔风险运行因素原始数据。

2）对数据进行预处理。

3）建立贝叶斯网络模型并计算相应因素的杆塔风险运行条件概率。

对于每种对杆塔风险运行概率的影响因子，用C1到C9来表示，D表示决策属性，也就是表示杆塔的运行状态，因此生成初始决策表如表1所示。

表1 初始决策表Tab.1　Data error comparison between two methods

C1为输电杆塔所在区域的天气情况；C2为输电杆塔所在区域的地质情况，分为简单、中等和复杂3个等级；C3为输电杆塔的平均温度；C4为输电杆塔的平均巡视周期；C5为输电杆塔的异常频率；C6为输电杆塔的材料等级，分为高级材料、中级材料和低级材料；C9为输电杆塔的电压等级；D为决策属性，表示杆塔的运行状态（正常或者异常）。

表1中的部分数据要经过量化处理，其量化过程是将每种影响因素的特征映射到一定的区间内，并用具体的数值表示其中的不同特征，如天气因素等。在获得量化后的初始决策表后，将所有数据输入到贝叶斯网络模型中进行计算。模型构建过程分为如下5个步骤。

1）计算杆塔风险运行影响因素之间的条件互信息：Ip（Ci；Cj|C），i，j=1，2，…，n（条件互信息是指一个变量包含另一个变量的多少）。

2）生成一个以Ip（Ci；Cj|C）为弧的权重加权无向图，i，j=1，2，…，n。

3）寻找一个最大权重生成树。

4）设置以根节点为起点所有边向外的图。

5）生成以变量节点与属性节点之间的弧。

则生成模型如图4所示。

图4TAN贝叶斯网路结构图Fig.4　The diagram of TAN Bayesian network structure

通过贝叶斯网络模型计算得出初始决策表中每个属性的条件概率。在获得条件概率和贝叶斯网络模型的前提下，通过概率计算即可得出样本的高风险运行概率。设杆塔运行状态变量用B=｛B1、B2｝=｛高风险运行、低风险运行｝，杆塔运行状态的影响因素用｛C1C2C3…C9｝来表示，则杆塔的高风险运行概率为：

9式中：P（B1）和P（B2）分别为杆塔的历史高风险运行和低风险运行概率；P（Ci|B1）为杆塔在不同的影响因素的条件下的高风险运行概率。

同理，该样本的低风险运行概率为：

3　数学模型

3.1巡视路径目标函数

输电线路巡视路径模型就是通过设定目标最优值，使之达到最科学的巡视路径［20-21］。通常，目标函数设为路径最短，即区域中每个杆塔的巡视路径之和为最小。本文在路径之和的基础上引入杆塔高风险运行概率比值作为目标函数。假设某一巡视区域有N个杆塔，根据目标函数求出任意2个杆塔之间的距离以及各杆塔的运行风险概率，同时要求确定每条巡视路径应当满足：

1）要求区域巡视总时间最短。

2）巡视过程中要求每个杆塔只经过1次。

3）优先经过运行异常较高的杆塔或者电压等级高的杆塔。则每个杆塔的距离公式为：

式中：Si，i+1为1条巡检路径中2个相邻杆塔之间的距离；Xi、Yi为第i个杆塔的横坐标和纵坐标。

输电线路巡检路径优化问题中同时考虑杆塔巡检距离和杆塔高运行风险概率，采用的目标函数具体形式为：

式中：Fij为目标函数；D为待巡检杆塔数目；Pi、Pi+1分别为杆塔i和i+1的风险概率；α和β为加权系数。

3.2SW-CSO流程图

SW-CSO算法流程图如图5所示。

图5SW-CSO算法流程图Fig.5　The flow chart of SW-CSO algorithm

4　仿真分析

仿真采用MATLAB R2012b进行程序语言编写，运行环境是：CPU为G3240，3.10 GHz，内存1 GB，操作系统为Windows7旗舰版。经过贝叶斯网络建模和分析，将杆塔的影响因素初始决策表导入模型中，得出每种影响因素的条件概率，通过杆塔风险运行概率模型计算得出杆塔的高风险运行概率。30个杆塔的位置和高风险运行概率如表2所示。

根据表2中提供的输电线路杆塔坐标位置和高风险运行概率，分别用遗传算法（GA）、粒子群算法（PSO）、模拟退火法（SA）和小世界纵横交叉算法（SW-CSO）进行对比，得出巡视路径和目标函数综合值如表3所示。

由表3可知，在考虑输电线路杆塔高风险运行概率的情况下，SW-CSO算法的优化结果好于其他3种算法。

表2　30杆塔系统参数表Tab.2　Data error comparison between two methods

表3　几种算法下的巡视路径比较Tab.3　Comparison of several algorithms on inspection paths

SW-CSO搜索出的最佳巡视路径如图6所示。

图6 最佳巡视路径Fig.6　The diagram of best patrol route

同时用GA、PSO、SA和SW-CSO 4种算法对巡视路径搜索做30组实验，验证其稳定性。其稳定性对比分析如图7所示。

图7SW-CSO算法稳定性分析Fig.7　Stability analysis of SW-CSO algorithm

从图7中可以看出，30次实验中GA算法有10次无法收敛到最佳值，得到最佳值的概率为66.6%。PSO算法有6次没有收敛到最佳值，得到最佳值的概率为80%。而SA和SW-CSO算法仅有3次没有收敛到最佳值，得到的最优结果概率为90%。说明SW-CSO鲁棒性强。

5　结论

本文在SW-CSO算法的环境下，搜索含有30个杆塔的输电线路巡视路径，得出以下结论：

1）在考虑杆塔风险运行概率的条件下，与其他算法相比，SW-CSO算法具有较强的搜索能力和较好的鲁棒性。

2）输电线路巡视路径规划模型为科学地安排线路巡视提供了依据。

［1］吕明，盛戈皞，张卫东，等.无人飞行器巡检输电线路的杆塔和导线跟踪算法［J］.电力系统自动化，2012，36（9）：92-97. LÜ Ming，SHENG Gemu，ZHANG Weidong，et al.A tower and line tracking algorithm for power transmission line inspection based on unmanned aerial vehicles［J］. Automation of Electric Power Systems，2012，36（9）：92-97（in Chinese）.

［2］曾瑛，李伟坚，陈媛媛，等.基于业务优先级的电力调度数据网拥塞规避算法［J］.电力系统保护与控制，2014 （2）：49-55. ZENG Ying，LI Weijian，CHEN Yuanyuan，et al.A congestion avoidance algorithm based on the service priority for electric power dispatching data network［J］.Power System Protection，2014（2）：49-55（in Chinese）.

［3］付锦，王先洪，欧智乐，等.改进类电磁机制算法在多目标动态电网规划中的应用［J］.电力系统保护与控制，2014（3）：94-99. FU Jin，WANG Xianhong，OU Zhile，et al.Application of improvedelectromagnetism-likemechanisminmultiobjective dynamic power network planning［J］.Power System Protection and Control，2014（3）：94-99（in Chinese）.

［4］袁佳歆，赵震，费雯丽，等.基于免疫算法的逆变器多目标Pareto最优控制策略［J］.电工技术学报，2014，29 （12）：33-41. YUAN Jiaxin，ZHAO Zhen，FEI Wenli，et al.Pareto optimum control of inverter based on multi-objective immune algorithm［J］.transactions of China electrotechnical Society，2014，29（12）：33-41（in Chinese）.

［5］肖曦，许青松，王雅婷，等.基于遗传算法的内埋式永磁同步电机参数辨识方法［J］.电工技术学报，2014，29 （3）：21-26. XIAO Xi，XU Qingsong，WANG Yating，et al.Parameter identification of interior permanent magnet synchronous motors based on genetic algorithm［J］.Transactions of China Electrotechnical Society，2014，29（3）：21-26（in Chinese）.

［6］唐磊，曾成碧，苗虹，等.基于蒙特卡洛的光伏多峰最大功率跟踪控制［J］.电工技术学报，2015，30（1）：170-176. TANG Lei，ZENG Chengbi，MIAO Hong，et al.A novel maximum power point tracking scheme for PV systems under partially shaded conditions based on monte carlo algorithm［J］.Transactions of China Electrotechnical Society，2015，30（1）：170-176（in Chinese）.

［7］李士波，孙秀霞，王栋，等.无人机动态环境实时航迹规划［J］.系统工程与电子技术，2007，29（3）：399-401. LI Shibo，SUN Xiuxia，WANG dong，et al.Real-time route planning algorithm for unmanned aerial vehicles in dynamic environment［J］.Systems Engineering and Electronics，2007，29（3）：399-401（in Chinese）.

［8］郝震，张健，蔡满意.自适应遗传算法在飞行器离线航迹规划中的应用［J］.电光与控制，2010，17（1）：65-68. HAO Zhen，ZHANG Jian，CAI Manyi.Application of adaptivegeneticalgorithminaircraftoff-lineroute planning［J］.Electronics Optics&Control，2010，17（1）：65-68（in Chinese）.

［9］石远鹏，姜建军，郑德宇，等.输电线路巡检的路径规划与建模［J］.应用科技，2011，38（11）：18-21. SHI Yuanpeng，JIANG Jianjun，ZHENG Deyu，et al. Route planning and modeling of transmission lines inspection［J］.Applied Science and Technology，2011，38（11）：18-21（in Chinese）.

［10］段其昌，周华鑫，程有富，等.贝叶斯网络在输电线路运行状态预测中的应用［J］.计算机科学，2012，39（3）：83-87. DUAN Qichang，ZHOU Huaxin，CHENG Youfu，et al. Application of bayesian network in transmission lines running state prediction［J］.Computer Science，2012，39 （3）：83-87（in Chinese）.

［11］余文辉，王沾，曾祥君，等.基于贝叶斯网络的多状态变压器可靠性跟踪分析［J］.电力系统保护与控制，2015，43（6）：78-85. YU Wenhui，WANG Zhan，ZENG Xiangjun，et al.Reliability tracing analysis for multi-state power transformers using bayesian network［J］.Power System Protection and Control，2015，43（6）：78-85（in Chinese）.

［12］周忠宝，董豆豆，周经伦.贝叶斯网络在可靠性分析中的应用［J］.系统工程理论与实践，2006，26（6）：95-100. ZHOU Zhongbao，DONG Doudou，ZHOU Jinglun.Application of bayesian networks in reliability analysis［J］. Systems Engineering-Theory&Amp；Practice，2006，26 （6）：95-100（in Chinese）.

［13］霍利民，朱永利，张在玲，等.贝叶斯网络在配电系统可靠性评估中的应用［J］.电工技术学报，2004，19（8）：113-118. HUO Liming，ZHU Yongli，ZHANG Zailing，et al.Bayesian networks application to reliability evaluation of electric distribution systems［J］.Transactions of China Electrotechnical Society，2004，19（8）：113-118（in Chinese）.

［14］杨莉，孙华昕，朱宏超.基于贝叶斯网络的多目标优化算法［J］.华北电力大学学报，2007，34（1）：128-131. YANG Li，SUN Huaxin，ZHANG Hongchao.Multiobjective optimization algorithm based-on bayesian networks［J］.Journal of North China Electric Power University，2007，34（1）：128-131（in Chinese）.

［15］WATTS D J，STROGATZ S H.Collective dynamics of small-world networks［J］.Nature，1998，393（4）：440-442.

［16］MENG A，CHEN Y，YIN H，et al．Crisscross optimization algorithm and its application［J］．Knowledge-Based Systems，2014，67（3）：218-229．

［17］孟安波，卢海明，李海亮，等.纵横交叉算法优化FCM在电力客户分类中的应用［J］.电力系统保护与控制，2015，43（20）：150-154. MENG Anbo，LU Haiming，LI Hailiang，et al.Electricity customer classification based on optimized FCM clusteringby hybrid CSO［J］.Power System Protection and Control，2015，43（20）：150-154（in Chinese）.

［18］王爽心，董旸，刘海瑞.基于T-S模型和小世界优化算法的广义非线性预测控制［J］.控制与决策，2011，26 （5）：673-678. WANG Shuangxin，DONG Yang，LIU Hairui.Generalized nonlinear predictive controller based on T-S fuzzy model and small-world optimization algorithm［J］.Control and Decision，2011，26（5）：673-678（in Chinese）.

［19］杜海峰，庄健，张进华，等.用于函数优化的小世界优化算法［J］.西安交通大学学报，2005，39（9）：1011-1015. DU Haifeng，ZHUANG Jian，ZHANG Jinhua，et al. Small-worldphenomenonforfunctionoptimization［J］. Journal of Xi'；An Jiaotong University，2005，39（9）：1011-1015（in Chinese）.

［20］曾胜林.浅谈输电线路路径的选择［J］.科技与创新，2014（19）：26-27. ZENG Shenglin.On the selection of the transmission line route［J］.Science and Technology&；Innovation，2014（19）：26-27（in Chinese）.

［21］王慧刚，王峰.输电线路巡视存在问题分析及应对措施［J］.现代工业经济和信息化，2014，4（22）：49-52，57. WANG Huigang，WANG Feng.Problems and countermeasuresofpatrollingoftransmissionlines［J］.Modern Industrial Economy and Informationization，2014，4（22）：49-52，57（in Chinese）.

洪俊杰（1981—），博士，讲师，主要研究方向为电力电子与电力传动和电机驱动控制。

（编辑董小兵）

Application of Small World Based Crisscross Optimization Algorithm in Power Transmission Lines Inspection

OU Yuqiang1，WEN Jianzhong1，WANG Liguo1，YANG Xi1，LIANG Haipeng1，
MENG Anbo2，LI Deqiang2，HONG Junjie2
（1.Jiangmen Power Supply Bureau，Guangdong Power Grid Co.，Ltd.，Jiangmen 529000，Guangdong，China；2.Guangdong University of Technology，Guangzhou 510006，Guangdong，China）

Line inspection is a basic job in the operation of the transmission system and the effective inspection is necessary for achieving the maximum safety and reliability of the transmission line.This paper proposes a small world based crisscross optimization algorithm（SW-CSO） for the path planning of transmission line inspection and the risk probabilities of tower poles are derived by applying Bayesian network.The risk probabilities of each tower pole and the distance between tower poles are considered in the objective function of the optimal inspection problem.The proposed method is validated on a transmission network consisting of 30 tower poles.The results show that SW-CSO algorithm has some advantages in convergence accuracy and stability，compared with other heuristic algorithms.

TRAnsmission lines inspection；small world based crisscross optimization algorithm；Bayesian network；risk probability of tower poles摘要：输电线路在电力系统正常运行过程中起到重要作用，其安全运行对整体网络起到保障作用。输电线路巡视是输电系统的一项基础工作，有效的巡视可以使输电线路设备安全性和可靠性达到最大化。基于小世界纵横交叉算法（SWCSO）对输电线路巡视路径进行规划，同时利用贝叶斯及其推理机制对输电线路杆塔风险等级进行分类，在考虑每个杆塔的杆塔距离、风险等级的条件下，制定最优巡视方案。仿真部分是拥有30个杆塔的输电网络，在通过贝叶斯及其推理机制获得杆塔风险运行概率的条件下，对巡视路径搜索用几种不同的算法进行对比。仿真结果证明了SW-CSO算法在收敛精度和算法稳定上都有一定的优势。

1674-3814（2016）06-0046-07

TM732

A

2016-02-21。

欧郁强（1964—），男，硕士，高级工程师，主要研究方向输变电生产管理；

闻建中（1978—），男，硕士，高级工程师，主要研究方向输变电生产管理；

王利国（1982—），男，硕士，高级工程师，主要研究方向输变电生产管理；

杨玺（1986—），男，本科，工程师，主要研究方向生产设备管理；

梁海蓬（1986—），男，大专，助理工程师，主要研究方向输电线路运行与维护；

孟安波（1971—），男，博士，副教授，主要研究方向为电力系统自动化，系统分析与集成；

李德强（1991—），男，硕士研究生，主要研究方向为智能算法在电力系统中的应用；

国家自然科学基金资助项目（51407035）；广东省电网公司科技项目（GDKJ00000009）。

Project Supported by National Natural Science Foundation of China（51407035）；Science and Technology Project of Guangdong Power Grid Corp（GDKJ00000009）.