基于改进的最大最小蚁群算法求解电力线路最佳抢修路径

减小字体 增大字体 作者:朱永利 陈英伟 韩 凯 王 磊  来源:www.zhonghualunwen.com  发布时间:2009-10-13 00:33:39

  0 引言
  
  随着人们生活水平的提高和电力系统的发展,电力线路逐渐增多,线路故障时有发生。突如其来的自然灾害更易造成大面积的杆塔和线路故障,抢修不及时将严重影响生产、生活。因此,电力线路中的最佳抢修路径的研究就成为当今的一个热点问题。
  电力线路中的最佳抢修路径问题就是在检测到故障点后,派遣抢修人员及时地到达故障现场,减少故障造成的破坏,也就是交通网络中的最优路问题。现在已经存在多种算法来求解此问题,如Dijkstra算法、模拟退火算法、蚁群算法和遗传算法。但是Dijkstra算法随着网络规模的扩大,内部的二重循环将导致执行效率严重降低。模拟退火算法虽然能够找到最优解,但是冷却参数的设置很难把握。遗传算法作为一种随机优化算法,局部搜索能力较差,很容易出现早熟收敛现象。
  蚁群算法是一种全局启发式算法,它是在对自然界中真实蚁群的集体行为的研究基础上,由意大利学者Macro
   Dorigo等人提出来的[1]。求解效率最高的最大最小蚁群算法是德国学者T.Stuetzle等人[2]针对蚁群算法容易出现过早的停滞现象而提出的蚁群改进算法。本文就是将最大最小蚂蚁算法与噪声扰动算法相结合,利用蚁群算法的全局性避开局部极优,利用局部搜索加快求解速度,并采用信息素调解机制来求解电力线路最佳抢修路径。仿真结果表明这一改进算法效果比较理想。
  
  1 电力线路最佳抢修路径的数学模型
  
  电力线路中的最佳抢修路径就是交通网络中抢修人员从物资点到故障点花费时间最少的路径。所以,找到故障点邻近的交叉路口(目标节点T)和物资点邻近的交叉路口(初始节点S),然后在交通网络拓扑图中求取S~T耗费时间最少的路径。因此,交通网络中的路段抽象为平面图中的边,交叉路口抽象为平面图中的顶点,形成一个平面图G(V,E)。其中:V是顶点集合;E是边的集合。如果顶点i到顶点j有直接相连的边,则Xij=1;否则Xij=0。Wij是(i,j)的权重,即通过路段(i,j)所耗费的时间。最佳抢修路径就是S~T的一些中间节点的集合(a0(S),a1,…,ai,…,an(T)),因此电力线路最佳抢修路径的数学模型如式(1)所示。
  min∑(i,j)∈Ewijxij
  ∑j:(i,j)∈Exij-∑j:(j,i)∈Exji=1i=S-1i=T0i≠S,T(1)
  受到路段行使速度、交叉路口的延误、交通管制等交通因素的影响,路段(i,j)的权重wij由行驶时间和交叉路口延误的时间两部分组成。本文将路段的允许平均行驶速度划分为如表1所示的八个等级,则路段的行驶时间tij为路段的距离和行使速度的比值,即tij=dij/vij。利用道路等级来确定各交叉口的平均延误时间ti,每条路段均有两个交叉口,路段(i,j)的交叉口延误时间为(ti+tj)/2,则每个路段的权重如式(2)所示。
     wij=tij+(ti+tj)/2(2)
  表1 道路等级
  等级12345678
  速度/km/h510152025303540
  
  2 最大最小蚁群算法
  
  蚁群算法是一种求解组合优化问题的启发式搜索算法,它的正反馈机制确保了最优化过程的快速性,而其分布式计算特性又避免了过早收敛,既有贪婪启发式的搜索特性,又能在搜索的早期获得可以接受的问题解[3]。但基本蚁群算法在求解大规模的复杂问题时,容易出现早熟、停滞现象。最大最小蚁群算法对基本蚁群算法进行了许多改进,在一定程度上避免了过早停滞现象的发生[2]。最大最小蚁群算法的步骤如下:

[1] [2] [3] [4]  下一页

Tags:

作者:朱永利 陈英伟 韩 凯 王 磊
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论