基于dijkstra算法的农网路径优化

摘要：在线路设计中路径的选择极甚为关键的环节，它会严重影响工程的总造价和运行的稳定性。根据送电线路路径选择上的一些特点，建立在全局基础上最优的路径搜索模型，并且把地质情况、水文状况和林带等影响线路的路径选择的因素统统包括在内，最后运用dijkstra算法在模型上进行最优路径搜索。仿真结果说明，dijkstra算法可以正确地计算出全局最优路径。

关键词：农村地区；送电线路；路径寻优；dijkstra算法

中图分类号：TP301.6文献标识码：A文章编号：1672-7800（2013）001-0051-03

0引言

在农村电力建设中，最为关键与首要的任务便是线路的路径选取。工程的总造价、线路运行费用、线路安全稳定性等都与最初的线路路径选择有着重要的关联，对线路的影响是长久而深远的。过去在对线路路径选择时人为因素比较多，容易带来路径选取上的不合理，造成很多不必要的浪费。这些年来，伴随着GIS（地理信息系统）技术在各行各业中的运用，人们也在将GIS技术尝试着应用到送电线路路径选取工作中。就目前来看，在送电线路路径的选择领域所运用的算法比较少。本文运用dijkstra经典算法进行线路优化，根据送电线路选线的特点，将dijkstra算法应用在线路选线当中，运用VB进行编程，根据测量距离，完成路径选择，利用dijkstra算法直接在模型上进行全局最优路径搜索。

1问题描述与环境建模

在给出地形图后，选取几个适合立杆的位置，这些立杆位置就是图中标号圆圈，然后根据这些电杆位置及走向选择出路径最短的线路，如图1所示。

图1真实路径示意

由于路径中存在诸多的影响因素，如沼泽、湿地、流砂等地质状况及林地征地、施工困难等等，这些因素将直接影响线路工程的总造价，为此引入“虚拟路径距离”，虚拟参数取值参见表1，根据虚拟路径可以得出图2所示示意图。虚拟路径公式计算如下：d*（i，j）=d（i，j）×［1+ωij+rij］（1）表1虚拟参数取值

12地质状况ωij12林地系数rij（按树龄计）流沙12岩石12沼泽12≤20年12＞20～50年12＞50年参数值121.2120.5121.8120.2120.3120.5从结果可以看出，AIAC能有效地优化节点间路径，使节点间信息以最优路径传递。

5结论与分析

本文提出了用AIAC来解决WSN中路径优化的问题，在蚂蚁算法处理路径优化问题效率较高的基础上，人工免疫算法把最优路径长度作为抗原，这就能保证所生成的抗体直接与问题相联系，收敛方向能得到有效的控制，不至于使得出的解偏离最优值。保留与抗原具有高亲和力的抗体，能促进快速求解，避免对劣质抗体做过多的操作，降低了求解效率。算法中的人工免疫算子增强了抗体的多样性，保证了算法不至于陷于局部最优解。本算法解决WSN路径优化问题可达到更高的效率，仿真结果也证实了这一点。

参考文献：

[1]莫宏伟，左兴权.人工免疫系统[M].北京：科学出版社，2009.

[2]莫宏伟，基于免疫网络的数据挖掘原理与应用研究[D].哈尔滨：哈尔滨工程大学，2005.

[3]肖人彬，王磊.人工免疫系统：原理，模型，分析及展望[J].计算机学报，2002（12）.（责任编辑：余晓）