基于蚁群算法的配电网网架优化规划方法①>
王志刚 杨丽徙 陈根永
（郑州大学电气工程学院 郑州市 450002）
摘 要 蚁群算法是一种求解组合优化问题的新型通用启发式方法，该方法的主要特点是正反馈、分布式计算和富于建设性的贪婪启发式搜索。配电网网架优化规划是一个复杂的非线性组合优化问题。本文将蚁群算法用于配电网网架优化规划问题的研究，建立了网架规划的数学模型，该模型以线路的年综合费用和过负荷惩罚费用之和最小为目标函数，并在此基础上设计了相应的算法。算例证明了该算法在配电网网架优化规划中应用的可行性和有效性。
关键词 蚁群算法 组合优化 配电网 优化规划
1 引言
网架优化的目的在于根据投资及运行等费用最小的原则，确定扩建线路的类型、时间及地点，建设技术上安全可靠、经济上费用最省的电网结构。因此，网架优化是一个大规模的组合优化问题。
近年来，在配电网网架优化规划方面涌现了不少新思路和新方法，如遗传算法［1］（GA）、搜索禁忌算法［2］（Tabu Search）和模拟退火算法等。
蚁群算法最初是由Dorigo等人提出［3］，是一种求解组合优化问题的新型通用启发式方法。该方法的主要特点是正反馈、分布式计算以及富于建设性贪婪启发式搜索。正反馈有助于快速发现较好的解；分布式计算避免了在迭代过程中早熟现象的出现；而贪婪启发式搜索的运用则使得搜索过程中较早发现可接受解成为可能［3，4］。虽然蚁群算法的出现只是近几年的事，但已经成功应用于许多组合优化问题，例如TSP问题［3，5］、JSP问题［3］等。而该算法在电力系统中的应用才刚刚起步［4］。
本文提出了一种基于蚁群算法来求解配电网网架优化规划问题的方法，建立了数学模型，设计了相应的求解算法及程序，并将该算法用文献［6］的算例进行了测试。结果表明，本文提出的优化方法是可行、有效的。
2 网架优化模型
本文中网架优化模型以线路的年综合费用和过负荷惩罚费用之和最小为目标函数。数学模型可用下式表达：
式中X为n维决策矢量，代表问题的解；xi是矢量X的元素，当待选线路i被选中时xi＝1否则xi＝0；C1i＝γi＋αi，γi是投资回收率，αi是设备折旧维修率；C2i是电价（元／kWh）；ΔPi是线路i的有功损耗（kW）；τmax i是相应的年最大损耗时间（h）；A1是过负荷惩罚系数；L是网络的过负荷（即超过线路最大允许负荷）的部分，其数值可以通过网络的负荷潮流求得；A2是一个大数，代表网络为非辐射网时的惩罚值。
3 蚁群算法原理
蚁群算法主要是受启发于蚁群搜索食物的过程。蚂蚁与密蜂、飞蛾一样属群居昆虫；通过对蚁群行为的研究，人们发现虽然其单个昆虫的行为非常简单，但由单个简单的个体所组成的群体却表现出极其复杂的行为；原因是什么呢？仿生学家经过大量细致的观察研究发现，蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递的；蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的［7］，该过程可以用图1来描述。
设A是巢穴，E是食物源，H、D为障碍物。由于障碍物的存在，蚂蚁只能经由H或D由A到达E，或由E到达A，各点之间的距离如图所示。设每个时间单位有30只蚂蚁由A到达B，有30只蚂蚁由E到达C，每只蚂蚁过后留下的激素量（以下我们称之为信息）为1。在初始时刻t0，由于路径BH、BD、CH、CD上均无信息存在，位于B和C的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择这四条路径。经过一个时间单位后，在路径BDC上的信息量是路径BHC上信息量的两倍。t1时刻，将有20只蚂蚁由B和C到达D，有10只蚂蚁由B和C到达H。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BDC，最终完全选择路径BDC，从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。
4 用蚁群算法求解配电网网架优化
在本文提出的蚁群算法中，首先将规划区域内n条可行待选线路从1到n编号；然后求出每条待选线路的转换概率Pki。在迭代过程中，蚂蚁每次从这n个元素中按每个元素的转换概率选取1个元素。对于每只蚂蚁，该过程同时重复的次数为（nodenum－subnum－oldlinenum），其中nodenum为节点数目，subnum为变电站数目，oldlinenum为老线路数目。最终每只蚂蚁形成一个线路集，该线路集形成一个规划方案。当一次循环完成后，从所有蚂蚁形成的规划方案中选择具有最小目标函数值的规划方案，并与当前保存的最优方案进行比较。如果新方案比当前保存的最优方案进行比较。如果新方案比当前保存的最优方案还要好，那么用新方案比当前保存的方案；否则维持当前的最优方案。重复上述过程直至达到最大迭代次数。
每个元素的初始信息素是相等的。设信息素τi（0）＝C（i＝1，2，…，n），其中C为常数。寻优过程中，其信息素τi将随着蚁群过后留下的激素量的变化而变化。
蚂蚁k在运动过程中是根据各个元素的转换概率来决定选取哪一个元素的，转换概率
式中allowedLk为蚂蚁k还没有访问过的元素集；α，β分别表示蚂蚁在运动过程所积累的信息及启发式因子在蚂蚁选择元素中所起的不同作用；ηi表示选择元素i的期望程度，且其数值定义为待选线路i的长度或投资的倒数。
完成一次迭代后，每条待选线路的信息素被更新为：
式中ρ是一系数，1－ρ是时刻t到t＋n之间各线路上信息素的蒸发系数；m为蚂蚁数目；δτi（t，t＋n）是时刻t到t＋n之间释放在待选线路i上的信息量；
式中Q为一常数；fk（X）为蚂蚁k所得规划方案的目标函数值，可由式（1）计算而得。
基于蚁群算法的配电网网架优化规划算法具体步骤如下：
（1）给每个元素赋初始信息素值τi（0）＝C，设迭代次数N＝0，并且令
（2）利用式（2）计算所有未被加入tabu表的待选线路的转换概率
（3）如果在步骤（2）中找到的规划方案的目标函数值比fmin小，那么用该值替换fmin，并记下该规划方案；否则转向步骤（4）。
（4）利用式（5）计算信息素增量值
（5）令迭代次数N＝N＋1。若N＜Nmax，则清空所有的tabu表，转向步骤（2），否则输出最好的规划方案，停止。
5 算例
本文引用文献［6］中的算例对基于蚁群算法的配电网网架优化规划方法进行验证。算例为一个具有10节点、2条现有支路和14条可扩建支路的10 kV配电网扩展规划，如图2所示。图中1节点为变电站，实线表示已架线路，虚线表示待选线路。
在蚁群算法中，参数设置如下：C＝0．5，α＝1，β＝1，ρ＝0．8，Q＝1，m＝30及Nmax＝50。经过计算，最终得到的总费用最小的规划方案如图3所示。优化结果与文献［6］的结果一致。
6 结论
本文将蚁群算法应用于配电网网架优化规划，以年综合费用和过负荷惩罚费用之和最小为目标函数，建立了相应的求解算法，并通过了算例验证。结果表明，本文提出的基于蚁群算法的配电网网架优化规划方法是可行和有效的。
