4、基于知识的高效最短路算法
尽管最短路遗传算法不会有维数灾问题。
但是基本的Dijkstra最短路算法的计算时间复杂性是O（N2），其中N是规划问题的网络流模型的节点数，因此，基于最短路算法的局部优化算法的计算时间复杂性是O（N3）（认为负荷数与节点数成一定比例）；若遗传算法的种群个体数和最大代数取固定值，则最短路遗传算法的计算时间复杂性是O（N3）。可见随问题规模的增大，最短路遗传算法的计算时间也将很长。 实际上，直接在输配电系统规模非常庞大的网络上利用常规的最短路算法为某一个负荷点寻找供电路径是很不必要的。对于一个负荷点来说，整个系统中可能为其供电的元件只是很小的一部分。如果能根据输配电系统的实际信息把这一小部分元件提取出来后再应用最短路算法，则最短路算法的寻路时间将大大缩短。而由前面的分析可知，最短路算法的计算时间复杂性决定了整个算法的计算时间复杂性。我们称这个被提取出来供寻找负荷m的最经济供电路径的网络为寻路网络Gm.用以提取寻路网络的方法应具备以下特点：
① 易于计算机实现。
② 在保证不丢失最优解的基础上，尽可能缩小寻路网络。下面，以一个实例来说明如何实现基于输配电系统知识的最短路算法。
若现有10kV，66kV，220kV，3个电压等级系统，要寻找负荷m的最优供电路径，则可按以下步骤提取寻路网络Gm.
（1）将输配电系统按电压等级分层，负荷点通常在最底层10kV层，虚拟电源点在最高电压等级层220 kV层。
（2）定义元件Aij到负荷点m的距离为式中为元件Aij的起点坐标；XB-ij、yE-ij为元件Aij的终点坐标；Xm 、Ym为负荷点m的坐标；Kij-m为元件Aij到负荷点m的距离调节系数，通常取1，可用于考虑一些特殊供电情况。按最大供电半径Rm选择出可能给负荷点m供电的10kV区域：若10kV元件（线路、变压器或变电站）与负荷点m的距离大于Rm，则认为其不可能为m供电，因此不加入寻路网络。反之，则将相应的元件加入负荷点m的寻路网络。
（3）通常希望尽可能通过具有主干线型或可靠性高的主干网络传送电能，并且减少电能在主干线型和次要线型间的转换。因此，规定最大精细寻路半径rm.在此半径之外，凡是具有非主干线型或位于次要分支线路或非主干路由（对于规划问题由于许多路由上线型未确定，因此这里用“非主干路由”一词）上的元件都不加入寻路网络，而在此半径之内的元件全加入寻路网络。
（4）经上述步骤形成的10kV系统范围内的寻路网络Gm_10包含有若干66kV/10kV变电站，它们对于10kV负荷点m来说是可能的供电点，而对于66kV系统来说是可能的负荷点。对这些变电站的每一个均采用与步骤（2）、（3）类似的方法，可得到其在66kV系统范围内的寻路网络，这些网络的并集构成负荷m在66kV系统范围内的寻路网络Gm_66.
（5）同理，Gm_66中所包含的220kV/66kV变电站也可看成220kV系统的负荷点。采用与步骤（4）同样的方法可获得负荷点m在220kV系统范围内的寻路网络Gm_220.当然，Gm_66中也可能包含发电厂，此时，可认为其是通过一条无损耗、无费用的虚拟弧，由设于220kV系统的虚拟源点供电。
（6）获得负荷点m在整个输配电系统的寻路网络为 显然，经过以上步骤处理后，得到的负荷点m的寻路网络Gm要比初始的整个网络要小得多，因此最短路算法的计算量也将大大缩小。
5、结论
本文对多电压等级、不同网络结构的输配电系统的综合规划问题进行了研究。在解决了电压等级折算问题后，给出了基于最短路遗传算法的纯开环输配电系统综合规划的方法。以此为基础，通过控制节点出入度，并且只针对有功潮流进行优化，又提出了开环与非开环混合的输配电系统综合规划问题的近似解决方法。为了解决输配电系统规模大而造成的计算量问题，给出了基于输配电系统知识的最短路算法的实现方法。
参考文献
[1]余贻鑫，段刚（Yu Yixin，Duan Gang）。基于最短路算法和遗传算法的配电网络重构（Shortest paty algoithm and genetic algorithm based distribution system reconfiguration）[J]. 中国电机工程学报（Proceedings of the CSEE），2000，20（9）：44-49.
[2] 段 刚，余贻鑫（Duan Gang，Yu Yixin）。中压配电网联络线优化的算法和实现（An algorithm ofr tie lines planning of power distribution systems）[J]. 电力系统自动化（Automation of Electric Power Systems），1999，23（15）：10-14.
[3] 孙洪波（Sun Hongbo）。电力网络规划（Power Grid Planning）[M]. 重庆：重庆大学出版社（Chongqing：Chongqing University Press），1996.
责任编辑：xiaohan
您现在的位置： 