基于蚁群算法的光缆巡检最短路径规划研究

国网湖北省电力有限公司恩施供电公司 李 锋 赵 芳 湖北民族大学信息工程学院 王新磊 钟建伟

电力系统通信是电力系统的重要组成部分，是电网智能调度、生产管理现代化，以及保障电网安全、稳定、经济运行的基础。电力通信光缆承载着电力系统通信的安全稳定运行，因此，为了保证光缆的可靠性，定期对光缆进行巡检是重中之重［1］。每个地区都有多个巡检点需要检查，巡检人员需要遍历每一个巡检地点，因此为了提高巡检效率，要尽可能地保证巡检人员到达所有巡检点时经过的路线最短。此问题明显是一个的旅行商问题（Travelling salesman problem,TSP），已经有很多解决方法［2-4］。本文将主要用蚁群算法和遗传算法、模拟退火算法对比，以三个巡检点数目不同的地区为实例，结果表明蚁群算法在求解质量和收敛速度上都具有优越性。

1 解决TSP问题的相关算法

TSP问题的解决方法有很多，本节主要介绍遗传算法、模拟退火算法与蚁群算法解决巡检最短路径规划问题的步骤。

1.1 遗传算法

遗传算法以“物竞天择，适者生存”为算法进化原则，结合生物进化过程，通过遗传、交叉、变异、自然选择等操作找到适应度高的解，其解决巡检最短路径规划问题的步骤如下：

步骤一：初始种群。设置巡检点个数、种群数量、最大迭代次数、交叉概率、变异概率、迭代次数等参数，随机生成初始种群；步骤二：个体评价。写出适应度函数，本文的目标是巡检距离最短，巡检距离越短，适应度越高；……