董平先 郭放 陈晨 宋晓帆 王辉 白萍萍 齐桓若 钱翌明 张浩杰 韩云昊
摘要针对基于传统手工设计的电缆敷设存在误差大和效率低等问题，将蚁群算法优化的计算机辅助设计应用到电缆敷设路径规划中．利用蚁群算法在复杂线路中多端点的线路计算优势，解决电缆敷设的最短路径问题．同时，本文将电缆敷设路径平面化，进一步利用Gompertz函数从信息素限定和挥发因子自适应调整两方面进行优化，提高了蚁群算法的收斂速度和全局性．仿真实验表明，优化的蚁群算法在变电站数字化三维电缆敷设过程能够快速得出最短电缆敷设路径，节省人力物资成本，提高了设计精度．
关键词蚁群算法;电缆敷设;信息素;挥发因子;收敛速度
中图分类号
TM757;TP18
文献标志码
A
收稿日期
2022-01-04
资助项目
国家自然科学基金（61873159）
作者简介董平先，女，高级工程师，研究方向为电力系统及其自动化．1224231819@qq.com
韩云昊（通信作者），男，博士，副教授，研究方向为电力系统及其自动化．yunhaoh@126.com
0 引言
为了适应我国经济的快速发展和人们对电力日益增长的需求，电力企业需要加大电网建设的规模和速度．其中电缆敷设是电厂工程建设的关键基础环节和最复杂部分之一［1］．以往传统人工设计方案是基于二维设计图纸或者Auto CAD等软件进行电缆敷设以及现场电缆长度计算，但由于人工统计电缆的用量和计算汇总电缆的长度会产生很大的误差和浪费，很难适应现代工程需要．随着电缆敷设数量逐年增多以及电缆敷设方式的多样化需求，如何实现节省成本和高效敷设的统一成为当下需要重点解决的问题［2］．
基于上述问题，考虑将计算机的三维数字化辅助设计技术应用于电缆敷设设计工作［3］．电缆敷设系统的核心是计算电缆路径的算法［4-6］，比较常用的有Dijkstra算法［7］、粒子群算法［8］和动态规划算法等．从传统算法到启发式智能算法在电缆敷设中的应用，有利于精确高效地规划电缆敷设路径．文献［9］提出通道容量限制、减少转弯数量等方面改进的Dijkstra算法，应用于抽水蓄能电站的电缆敷设中，降低了运算耗时．文献［10］将A-Star算法运用于电缆最短路径敷设中，在减轻设计人员工作量的同时提高了经济效益．文献［11］将分层序列法的思想运用于电缆敷设模型中，采用遗传算法和Dijkstra算法相结合求解了电缆敷设最短路径，但该算法只能求解两设备之间的路径，并且不能考虑多设备节点间的电缆敷设．文献［12］采用树状、网状搜索算法，精确地计算了电缆的路径和长度，但是该算法结构简单，不适用于较大规模的复杂电网．
本文针对传统蚁群算法应用于电缆敷设设计存在局部最优和收敛速度慢等问题，对算法进行优化，将其信息素限定在一定范围内，避免算法前期舍弃较差路径．同时将其挥发因子随着Gompertz增长函数自适应调整，提高算法收敛速度．优化后的蚁群算法应用在电缆敷设时，能够以更短的时间得到最短电缆敷设长度，并且提高算法迭代过程中的正确率，减缓算法运行过程中的停顿现象，提高电缆敷设效率和质量．
1 电缆敷设
为适应电网发展和传输容量的需求，越来越多的电缆和高电压电缆投入使用．在电缆敷设过程中，需要将大小不一的电缆按敷设规则放置在支架上，如图1所示，圆圈代表直径不同、类型不同的电缆，支架各层所需的实际电缆情况有所不同．
电缆是信息与电流传输的载体，具有严格的内部结构．如图2所示，电缆由绝缘层、保护层和线芯等组成，线芯是电缆的导电部分，绝缘层将线芯与大地以及不同相的线芯间在电气上彼此隔离．
电缆敷设是沿勘测线路布放、安装电缆以形成电缆线路的过程，事先需要安装好桥架、电缆沟等辅助配套设施，有排管敷设、直埋敷设、垂直敷设等多种敷设方式．电缆有多种类型，比如中压电缆、低压电缆和控制电缆．电气工程设计可能需要多种类型的电缆，但值得注意的是，在一个通道里只能敷设同一种类型的电缆，而且要考虑通道的容积率，保留足够范围的裕度，以便后续的检修工作［13］．电缆敷设的核心要求是电缆敷设路径符合工程设计需求且长度最短，为此需要引入电缆敷设的核心算法．
电缆敷设是一项复杂的工程（图3），敷设开始前需要进行绝缘电阻和耐压等多种试验，敷设过程中要考虑周围环境及电缆长度等因数，敷设完成以后要挂标识牌并完成其他检查验收任务．
2 蚁群算法
2.1 蚁群算法原理
蚁群算法（Ant Colony Algorithm，ACA）是一种仿生智能算法，具有分布式计算、信息正反馈和鲁棒性强等特征，并且能与其他算法相融合［14］．研究发现，蚂蚁在路径上会释放一种叫作信息素的生物荷尔蒙，而且会保留一段时间并不断挥发，蚂蚁能够感知到这种荷尔蒙，并且会有更高的概率选择信息素浓度较高的路径．路径较长的信息素挥发得相对较多，路径较短的挥发得相对较少．下一只蚂蚁有更高的概率选择信息素较浓的路径，如此反复，较短的路径上走过的蚂蚁越来越多，得到了最优路径［15-18］，如图4所示．
从N点到M点共有4条路径NBAM、NBM、NCBAM、NCBM，第1只蚂蚁随机选择了NBAM路径到达M点，随着外出觅食的蚂蚁的数量增多，4条路径上均有蚂蚁经过并留下会随着时间挥发的信息素．随着信息素的挥发和增加，最短路径NBM上的信息素越来越多，同时越来越多的蚂蚁选择了这条路径，最终所有蚂蚁都找到了最短路径．
3.2 优化蚁群算法
电缆敷设问题也是一种路径寻优问题［6］，将传统蚁群算法应用于电缆敷设中，会存在一定的缺陷：传统蚁群算法初始信息素相同，选择下一节点的概率随机，需要长时间形成正反馈，导致收敛速度慢;如果初始信息素更新时，正反馈于次优解，很容易出现早熟收敛的现象，陷入局部最优.为此本文对传统蚁群算法优化处理［15-16］．
3.2.1 信息素限定
蚂蚁在路径选择过程中，会优先选择几条较好的路径，如果剩下的路径长时间没有蚂蚁路过并且信息素已经挥发完，会导致算法陷入停滞现象．本文在算法中引入τ max和τ min两个信息素界限：
τ min≤τ≤τ max， （7）
将算法每次迭代过程中的信息素限定在该范围内，可以改善停滞现象，
3.2.2 挥发因子自适应调整
信息素是传统蚁群算法的核心，挥发因子ρ的大小對信息素起着关键作用．信息素挥发因子过小时，前期信息素浓度差别不大，蚂蚁对支路选择的可靠性降低，需要更长的时间选择出最优路径，算法收敛时间更长;当信息素挥发因子过大时，较复杂的路径上的信息素会逐渐挥发至0，算法容易陷入局部最优．因此，引入Gompertz增长函数自适应调整挥发因子，如图5所示.
Gompertz模型一般用于精算科学和细菌生长曲线建模，是一个递增函数，刚开始随着时间增加，ρ
值增长速度快，到达某个时间点，增长速度就变慢，然后ρ
值会逐渐趋近于某个极限值α
．Gompertz函数：
ρ=αe-eβ-γx， （8）
该函数下限值是0，上限值是α
．β
是生长速度，γ
是生长速率，两者都与函数因变量变化快慢有关．本文将Gompertz函数应用于挥发因子ρ
自适应调整，将迭代次数t作为自变量．在算法前期，挥发因子小，对算法的引导能力弱，有利于全局搜索，提高算法准确性;随着迭代次数增加，挥发因子逐渐变大，算法的收敛速度也随之增加．面对不同的环境，函数系数α，β，γ
可以自行设定，提高算法的灵活性．
3.2.3 优化蚁群算法实现
对电缆敷设问题，蚁群算法的求解［17-20］步骤如下：
1）变电站设备、节点坐标等数据处理.
2）参数初始化．对蚁群系统中蚂蚁个数M
、迭代总次数N
、信息素影响因子α
、能见度影响因子β
等参数设置具体值.
3）将所有蚂蚁均匀放在路径寻优的初始设备上，并将初始节点记入路径表内.
4）利用式（1）计算选择下一节点的概率，并用轮盘赌法选择下一节点，如果遇到死路，重新开始步骤2），否则将下一节点记入路径表内.
5）利用式（3）更新信息素，迭代次数N c+1.
6）若迭代次数N c 7）输出最优路径解． 算法流程如图6所示． 4 算法仿真测试 为了验证优化后的蚁群算法在电缆敷设中的实效性，基于Matlab软件编写程序，将变电站的三维电缆路径图投影成二维图进行分析，再利用电缆缆道及节点坐标等数据，搭建如图7所示的电缆路径平面．其中，仿真参数设置如表1所示． 考虑到电缆敷设路径选择的多样性和设备节点间的树状结构，借助优化蚁群算法在最优路径树选择方面的优势，进行设备间的路径择优．Floyd算法也可以用于电缆敷设路径寻优，求取最短路径，但它只能计算两个端点的路径长度，有其算法固有的局限性．相比于Floyd算法，优化蚁群算法更适合于复杂线路，不仅可以敷设两端点之间的电缆，还可以多端点敷设． 4.1 路径寻优算例分析 在电缆路径平面图中，任意选择两个设备节点，比如设备3和设备7．两个节点之间共有3条路径，优化蚁群算法得出的路线L k=117，如图8所示．经验证，该路线符合最优路径原则，满足电缆敷设最初的要求． 任意选择3个设备进行敷设，寻找其中的最短路径，如图9的设备1、设备3和设备7，一共有多种敷设路径，各条路径长短不一．优化蚁群算法得出的结果是L k=167，经验证，符合最短路径需求． 任意选择4个设备进行敷设，寻找其中的最短路径，如图10的设备1、设备3、设备7和设备9，一共有多种敷设路径，各条路径长短不一．优化蚁群算法得出的结果是L k=222，经验证，符合最短路径需求． 4.2 算例对比分析 在电缆路径平面图的基础上，分别利用传统蚁群算法和优化蚁群算法进行多次路径寻优程序运行．面对简单不复杂路径，传统蚁群算法可以得出实际情况下的最短路径，但运行在交叉线路较多等复杂情况下的路径时，会存在局部最优，甚至出现停滞现象．如表2所示，累计进行30次实验，传统蚁群算法的局部最优率为16.67％，出现4次停滞现象;而优化后蚁群算法的局部最优率为3.33％，只出现1次停滞现象．可见改进算法可以较大地优化程序运行，为电缆找出最短路径． 如图11所示，不考虑信息素浓度限制，分别利用优化前后蚁群算法运行10、20、30、40次，记录并 计算出多次运行总时间的平均值．传统蚁群算法运 行30次所得时间平均值为0.251 s，优化后的蚁群算法为0.147 s．可以看出，相比于传统蚁群算法，加入Gompertz模型的优化蚁群算法迭代时间更短，收敛速度更快． 5 结语 基于计算机的三维数字化辅助电缆敷设平台，将优化蚁群算法应用于电缆敷设设计中，精确地规划了电缆敷设路径．本文给出了电缆敷设的具体过程以及优化蚁群算法的数学模型，并且针对传统蚁群算法在电缆敷设应用中存在的问题，在信息素和挥发因子两方面对蚁群算法优化改进．实验表明优化后的蚁群算法可以实现全局最优，并且收敛速度更快，提高了电缆敷设的实效性． 参考文献 References ［1］ 胡秋野，杨世春，欧景茹.论环网柜在城市电网中的应用［J］.高电压技术，2004，30（增刊1）：8-9 HU Qiuye，YANG Shichun，OU Jingru.Discussion on application of ring main in urban distribution system［J］.High Voltage Engineering，2004，30（sup1）：8-9 ［2］ 徐俊.电力电缆施工、运行故障案例及分析［J］.高电压技术，2004，30（增刊1）：89，93 XU Jun.Analysis of cable fault in construction and operation［J］.High Voltage Engineering，2004，30（sup1）：89，93 ［3］ 沙少川，温杰.基于三维数字化技术的光电缆敷设的方法探讨［J］.电子测试，2021（20）：119-121 SHA Shaochuan，WEN Jie.Discussion on the method of laying optical cable based on 3D digital technology［J］.Electronic Test，2021（20）：119-121 ［4］ 于洋，魏长江.优化蚁群算法在电缆敷设中的应用［J］.青岛大学学报（自然科学版），2020，33（3）：65-70，75 YU Yang，WEI Changjiang.Application of ant colony optimization algorithm in cable laying［J］.Journal of Qingdao University （Natural Science Edition），2020，33（3）：65-70，75 ［5］ 于洋.基于优化蚁群算法的PDMS电缆敷设设计路径方法研究［D］.青岛：青岛大学，2020 YU Yang.Research on PDMS cable laying design path method based on optimized ant colony algorithm［D］.Qingdao：Qingdao University，2020 ［6］ 鲍伟强.蚁群优化电缆敷设系统的研究［D］.南宁：广西大学，2012 BAO Weiqiang.Ant colony optimization for cable laying system［D］.Nanning：Guangxi University，2012 ［7］ 朱翰超，杜亚静，季节.Dijkstra算法在电力电缆敷设优化研究中的应用［J］.电气应用，2014，33（24）：115-118 ZHU Hanchao，DU Yajing，JI Jie.Application of Dijkstra algorithm in power cable laying optimization ［J］.Electrotechnical Application，2014，33（24）：115-118 ［8］ 刘召朝，张丹，周琛，等.基于改进粒子群算法的多分支电缆自动布线技术［J］.机械制造与自动化，2021，50（1）：177-179 LIU Zhaochao，ZHANG Dan，ZHOU Chen，et al.Automatic routing technology of multi-branch cable harness based on improved particle swarm optimization［J］.Machine Building ＆ Automation，2021，50（1）：177-179 ［9］ 黄祖光，朱安平，王凯，等.基于Dijkstra算法的电缆敷设系统设计及实现［J］.电网与清洁能源，2020，36（6）：105-110 HUANG Zuguang，ZHU Anping，WANG Kai，et al.Design and implementation of cable laying system based on Dijkstra algorithm［J］.Advances of Power System ＆ Hydroelectric Engineering，2020，36（6）：105-110 ［10］ 李旭明.基于A-Star算法的三维电缆设计系统的设计与实现［D］.哈尔滨：哈尔滨工业大学，2018 LI Xuming.The design and implementation of three-dimensional cable design system based on A-Star algorithm［D］.Harbin：Harbin Institute of Technology，2018 ［11］ 李治，韓丹，任兴龙，等.基于遗传算法和改进的Dijkstra算法的电缆敷设优化研究［J］.数学的实践与认识，2016，46（17）：160-167 LI Zhi，HAN Dan，REN Xinglong，et al.Research of the optimization of cable laying with genetic algorithm and improved Dijkstra algorithm［J］.Mathematics in Practice and Theory，2016，46（17）：160-167 ［12］ 罗建国，韦思亮.基于树状、网状搜索算法的电缆敷设设计与应用［J］.热力发电，2013，42（3）：103-105 LUO Jianguo，WEI Siliang.Tree and mesh search algorithm based cable laying：design and application［J］.Thermal Power Generation，2013，42（3）：103-105 ［13］ 何江濤，焦阳，叶笛，等.电缆不同敷设方式下温度场与载流量的仿真计算［J］.电测与仪表，2016，53（3）：99-104 HE Jiangtao，JIAO Yang，YE Di，et al.Simulation and computation of temperature field and ampacity of conduit cable laying in different ways［J］.Electrical Measurement ＆ Instrumentation，2016，53（3）：99-104 ［14］ 张徐亮，张晋斌.基于协同学习的蚁群电缆敷设系统［J］.计算机工程与应用，2000，36（5）：181-182 ZHANG Xuliang，ZHANG Jinbin.Ant colony cable laying system based on cooperative learning［J］.Computer Engineering and Applications，2000，36（5）：181-182 ［15］ 颜杰，秦飞舟，翟帅华.一种改进蚁群算法的移动机器人路径规划［J］.软件导刊，2019，18（2）：5-8 YAN Jie，QIN Feizhou，ZHAI Shuaihua.An improved ant colony algorithm for mobile robot path planning［J］.Software Guide，2019，18（2）：5-8 ［16］ 任红格，胡鸿长，史涛.基于改进蚁群算法的移动机器人动态路径规划［J］.现代电子技术，2021，44（20）：182-186 REN Hongge，HU Hongchang，SHI Tao.Mobile robot dynamic path planning based on improved ant colony algorithm［J］.Modern Electronics Technique，2021，44（20）：182-186 ［17］ Zhou J Z，Wang C，Li Y Z，et al.A multi-objective multi-population ant colony optimization for economic emission dispatch considering power system security［J］.Applied Mathematical Modelling，2017，45：684-704 ［18］ Birattari M，Pellegrini P，Dorigo M.On the invariance of ant colony optimization［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：732-742 ［19］ Deneubourg J L，Aron S，Goss S，et al.The self-organizing exploratory pattern of the argentine ant［J］.Journal of Insect Behavior，1990，3（2）：159-168 ［20］ 李奇才，舒远仲，洪宇轩.一种蚁群算法与自适应机制的路径规划算法优化［J］.机械科学与技术，2022，41（7）：1095-1101 LI Qicai，SHU Yuanzhong，HONG Yuxuan.Optimization of path planning algorithm based on ant colony algorithm and adaptive mechanism［J］.Mechanical Science and Technology for Aerospace Engineering，2022，41（7）：1095-1101 Cable laying path planning based on optimized ant colony algorithm DONG Pingxian1 GUO Fang1 CHEN Chen1 SONG Xiaofan1 WANG Hui1 BAI Pingping1 QI Huanruo1 QIAN Yiming2 ZHANG Haojie2 HAN Yunhao2 1Economic and Technological Research Institute of State Grid Henan Electric Power Company，Zhengzhou 450002 2School of Electric Power Engineering，Shanghai University of Electric Power，Shanghai 200090 Abstract To address the large error and low efficiency of traditional manual design in cable laying task，the computer-aided design optimized by Ant Colony Algorithm （ACA） is applied to cable laying path planning.The shortest path for cable laying is solved via the ACAs multi terminal path calculation for complex path planning.Furthermore，the planarized cable laying path is optimized via Gompertz function in aspects of pheromone restriction and self-adaptive adjustment of volatilization factor，thus improves the ACA in both convergence speed and global performance.The simulation results show that the optimized ant colony algorithm can quickly obtain the shortest cable laying path in the task of substation digital 3D cable laying，which saves the cost of manpower and materials，and improves the design accuracy. Key words ant colony algorithm （ACA）;cable laying;pheromone;volatilization factor;convergence rate