基于禁忌搜索与蚁群最优结合算法的配电网规划
第 29卷 第 2期
2005年 1月
电 网 技 术
Power System Technology
、，01．29 N0．2
Jan． 2o05
文章编号：1000．3673(2005)02．0023．05 中图分类号：TM715 文献标识码 ：A 学科代码：470．405I
基于禁忌搜索与蚁群最优结合算法的配 电网规划
陈根军 ，唐国庆 2
(1．南京南瑞继保电气有限公司，江苏省 南京市 211100；2．东南大学 电气工程 系，江苏省 南京市 210096)
TABU SEARCH．ANT CoLoNY oPTIM IZATIoN HYBRID ALGom TIj[f BASED
DISTRIBUTIoN NETW oRK PLANNING
CHEN Gen-jun ，TANG Guo—qing
(1．Nari—Relays Electric Co．Ltd．，Nanjing 211100，Jiangsu Province，China；
2．Dept．of Electrical Engineering，Southeast University，Nanjing 2 1 0096，Jiangsu Province，China)
ABSTRACT：Tabu Search frs)behaves well in finding global
optim um of combined optimization problems，whereas its local
search is not satisfactory due tO diversi~； Ant Colony
Optimization (ACO)behaves well in finding local optimum ，
whereas its global search depends on selection of the evaporation
coeffi cient．An unsuitable evaporation coeffi cient may results in
loc al optim um offinal solutions．Tocom pe nsate somelimi tations
of single algorithm s，the authors integrate th e two algorithm s
togetheran dputforwardTS—ACO hybridalgorithm tO solvethe
distribution network planning．On the basis of simultaneously
taking account of the fixed expe nditure，which is required in the
expan sionof distributionnetw orkan dthe variable cost,which is
corresponding tO the electrical energy losses，a non—linear hybrid
integer math ematical model for distribution netw ork planning is
designed ．The testing results of a distribution netw ork which
po ssesses 6 substations an d 102 feeders show that the pre sented
TS—ACO hybridalgorithm iS effective．
KEY W ORDS：Power system ；Transmission an d distribution：
Distribution network planning；Tabu Search(TS)；Ant Colony
Op timi zation(ACo)；TS—ACO hybridalgorithm
摘要 ：禁忌搜索 (TS)算法具有强大的全局优化性能，但其
局部搜索性能易受分散性的影响：蚁群最优 (ACO)算法的
正反馈机制使其具有强大的局部搜索性能，但其全局优化性
能的优劣在很大程度上与蒸发系数的选择有关，如选择得不
合适易使算法陷于局部最优。文章将 TS算法与 ACO算法组
合起来，提出了TS．ACO混合算法，用于求解配电网规划问
题，在同时考虑扩展配电网所需的固定费用和与电能损失相
关的变化费用的基础上，设计了非线性混合整数配电网规划
数学模型，在一具有 6个变电所、102条馈线段的配 电网上
进行的测试结果表明了TS．ACO混合算法的有效性 。
关键词：电力系统 ：输配 电工程：配电网规划：禁忌搜索：
蚁群最优；TS．ACO混合算法
1 引言
配电网规划涉及变 电站和馈线段的建设时间、
建设地点及容量的最优选择，目的是满足未来负荷
增长的需求，同时服从变 电站容量大小、馈线段容
量大 小、电压 降落 、辐射状 网络结构 以及 可靠性要
求等约束 条件 。配 电网规划是一个非常 复杂的大规
模组合优化问题。传统的数学规划方法虽然能够从
理论上保证规划方 案的最优性 ，但 由于配 电网规划
的复杂性和组合性，用于求解规划问题时计算时间
较长、占用计算机内存也较大，因而在实际应用中
仅适用于小规模的配 电系统。
近年来，应用现代启发式方法，如模拟退火算
法 (Simulated Annealing，SA)、遗传算法 (Genetic
Algorithm，GA)、禁忌搜索 (Tabu Search，TS)、
蚁群最优 (Ant Colony Optimization，ACO)来求解
配电网规划问题比较有效可行【l 】。与传统搜索方法
相比，这类方法表现出一定的优越性，但单个现代
启 发式方法 在某些方 面也存在 不足之处 ，为改善单
一 算法 的局限性，进一步提高优化质量和搜索效
率 ，提 出了混合现代启发式方法，如文献【6】中的
SA+GA+TS混合算法、文献【7】中的 SA+GA混合算
法、文献【8】中的 ANN+GA混合算法等。
TS算法具有强大的全局搜索性能，而局部搜索
性能虽然具有“上山性”，但易受分散性的影响；ACO
算法的正反馈机制使其在搜索过程中具有强大的局
部搜索性能，而其全局最优性能的优劣在很大程度
上与蒸发系数的选择有关。蒸发系数选择得太大，
不利于搜索过程跳出局部最优；选择得太小，又会
维普资讯 http://www.cqvip.com
24 Power System Technology VO1．29 NO．2
丧 失搜索 历史中出现的优秀解 的影 响，不利 于快速
发现最优解 ，从而影响算法的局 部搜索性能 。
为充分利用这 两种算法 的优 点，弥补它们 各 自
的缺点 ，本文提 出了 TS—ACO混合算法 ，充 分利用
ACO算法的正反馈机制来弥补TS算法局部搜索的
分散性 ，使 TS算法进 行集 中化 的局 部搜 索 ，以此
来提高 TS算法的局部搜 索性 能 。
2 配 电网规划 的非线性混合整数规划模型
配 电网规 划 的 目标 是使 扩 展配 电网络 所需 的
固定费用和 与电能损 失相关 的变化 费用最小 ，同时
服从变 电站容量 大小、馈 线段 容量大 小、电压 降落 、
放射性网络结构以及可靠性要求等约束条件。由于
目标函数和约束条件均具有非线性特征，配电网规
划是一个 大规 模动态非线性混合 整数规划 问题 。本
文的配 电网规划数 学模型表达式 为
目标 函数 ：
min Z=∑∑ 瑶， +∑∑( tP,SCi +
t=l ieS￡ t=l ieSP
XitP
,
Sp 2)+∑∑XitE,FP／,E，，+
t=l ie
∑∑( ， ，，+XitP,FPD．，) (1)
t=l ieFP
式中 丁为规划 时间范围 ；S 为 已存在 变 电站的集
合：S 为可能的待建变 电站的集合： 为已存在馈
线段的集合 ： 为可 能的待建馈线段 的集合； 舱
为 已存在变 电站 i在 t时间段 的能量损失 费用 系数：
为可 能的待建变 电站 在 t时间段 的能量损失
费用系数；X 为已存在馈线段 i在 t时间段的能
量损失费用系数； 为可能的待建馈线段 i在 t
时间段的能量损失费用系数： =1表示变电站 i
在 t时间段 被建设 ，否 则
．
s=0； ，=l表 示馈
线段 i在 t时 间段被 建设 ，否则
．
，=0；
．
s 为在
t时 间段 建设变 电站 i折 算到当前年 的固定 费用：
为在 t时间段 建设馈线段 i折算 到当前年 的 固
定 费用： 为 t时间段 已存在 变 电站 供应 的潮
流 ； 为 t时间段可 能的待建变 电站 i供应 的潮
流 ； 为 ，时间段流过 已存在馈线段 的潮 流：
为 t时间段流 过可能 的待建馈 线段 i的潮流 。
约 束条件 ：
(1)潮流 约束
A =D (t=l，2，?，T) (2)
式中 A 为 t时段的节点弧关联矩阵；Pf为 t时段
的网络潮流矢量：D 为 t时段的负荷需求矢量。
(2)容量约束
． 一 (3)
式中 i∈S U SP U FE U Fp； t=1，?，T。
(3)电压 降落约束
≥ n V mj (4)
式中 i=1，?，N (Ⅳ 为节点数)；t=1，?，T：Vn为
t时间段节 点 i的 电压 ， 一 为该节 点 电压 的上 限：
mj 为该节 点电压 的下 限。
(4)辐射状 网络约 束
最终规划 的配 电网必须是辐射状 网络 ，不能形
成环 网。
(5)逻辑约束
用于描述规 划变量之 间的逻辑 关系 。例如 ，当
可能的待建变电站不存在时，连接该变电站和负荷
点的馈线段数 目为零 。
如果 T=I，上述模型就是一个单阶段的配电网
规划问题。本文仅考虑单阶段的配电网规划问题。
3 TS算法 与 ACO算法的性能分析
关于 TS、ACO基 本算法 的具体描述 参见文献
【9】、【10】。TS算法通过 对当前解进行 “移动 ”操作 ，
产生当前解邻域中可行的邻居解，取其最好邻居解
作 为新 的当前解来完 成解空 间的局部搜 索 。TS 的
局部搜索能力与其每次 “移动”操作所产生邻居解
的数 目密切相关 。邻居解太少 ，对 当前解邻域 空间
的搜 索也就越少 ，这将 影响 TS算法 的局部优化 性
能；邻居解太多，将会增加算法的执行时间。用于
求 解具体 的配 电网规 划 问题 时 ，TS 算法 中当前规
划解的邻居解是通过随机产生每一新负荷点的向
上节点得到的I引。对于特定负荷点，向上节点的选
择是随机的，即局部搜索具有分散性。局部搜索的
分散性似 乎有利于对局部 空间进行全方位搜索 ，但
当邻居 解 数 目一定 及 邻居 解 中 的优 秀 解较 为 集 中
时，这种分散性反而影响局部优化的性能。最终的
规划方案表明，每一新负荷点的向上节点是特定
的，尽管在搜索过程中并不能明确每一新负荷点的
向上节点，但却可以以某种机制来确定每一新负荷
点可能的向上节点的概率，并在 “移动”过程中以
概率为依据来选 择 向上节 点， 由此产生的 TS当前
解 的邻居解 大部分集 中在邻域 空间的特定区域 内，
而小部分分散在邻域空间的其它区域，本文称这种
维普资讯 http://www.cqvip.com
第 29卷 第 2期 电 嘲 技 术 25
现象为局部搜索的集中性，与之对应的是局部搜索
的分散性 。局部搜 索 的集 中性 显著增加 了发现 局部
最优解 的可能性 ，提 高了局部搜索 的性 能。图 1、
图 2分 别描述 了局部搜 索的分散性与集 中性 。
图 1 局部 搜 索 的分散 性
Fig．1 Diversity of local search
图 2 局 部搜 索 的集 中性
Fig．2 Aggregation of local search
“卜山性 ”是 TS算法 的重要特点 ，它的另一重
要特 点是允许一定的 “下 山”操作 (即解质量变 差 )，
从而提 高算法避开局部最优解 的能力 。此外 ，为避
免搜索路径 的往返重 复，TS使用 “Tabu表 ”来记录
搜索路径的历史信 息，这可在一定程度 避 开局部
极值 点，开辟新的搜索区域 。因此 ，虽然 TS算法并
不能从理论上保证一定能搜索到全局最优解，但却
能在较短 的时间内找到非常优秀的近似最优解 。
ACO算法 在本质上是一 个多代理算法 ，它通过
单个代理之间的低级交互形成整个蚁群的复杂行
为。在 ACO 算法 中，局部搜索是通 过多代理机制
来完成的，即通过多个人工蚂蚁 (代理 )的分布式
计算来产生新的解群。为在较少的迭代次数和迭代
时间 内迅速发现较 好的局部最优解 ，ACO算法采 用
了正反馈机制 ，即通 过可见度和不 断积累的信息素
等控 制参数来提 高优秀解 的产 生机 率 。从 ACO 算
法在配 电网规划 中的应用情况来看 ，该算法善于在
较短的迭代次数 内找到非常优秀 的规划解 ，这也说
明了 ACO算法具有 较强的局部搜 索能力 。
ACO 算 法 中的正 反馈 机制 使 ACO 算法在 搜
索 过程 中易 陷入 局部 最优 解 ，这 是因 为信 息素 在
正反馈机制的作用下不断积累 ，使某些局部最优
解 出现 的机 率远 大于 其 它优 化 解 出现 的机 率 。 为
避免这种现象的发生，ACO 算法又采用 了蒸发系
数的概念。蒸发系数通过削弱搜索过程中累积的信
息素密度，来减小搜索历史中出现的优秀解的影响，
因而有利于算法跳出局部最优，向解空间的其它区
域进行搜索。
4 配 电网规划的 TS-ACO 混合算法
本文 TS ACO混 合算 法的步骤 如下 ：
(1)通过 建立配 电网的最小生 成树来 形成配
电网规划 的初始解 Si inal，计算 Si inal的评价函数 。
令当前解矢量 S t=Si iⅡal，最好解矢量 Sbe t=Si njnal。
初 始化 “Tabu表 ”、释 放水平函数 A和候选支路集
合 S中所有支 路的 “信息素 ”密度 。为存放次优 解 ，
设置一个解集合 ，用于存放最优解及 次优解 ，其大
小可以根据实际需要来设定，初始化解集合 ，并
设 置该集合 中的第一 个元素 为 SiIlinal，其它元 素为
空。设置迭代计数器 K=O。
(2)如 等于预先设定 的最大 允许迭代次数
， 则输出S 作为最终的规划方案，集合S为
最 终的解集合 ；否则 令 K=K+1，并转 向步骤 (3)。
(3)将两种 “移动 ”操作作用于 S 一 生成
S 的一 个辐 射状 网络试验解 S，并 计算对应该
试 验解的评价函数 ．厂(S)。在执 行 “移动 ”的操作过
程中，依据各向上节点的转换概率来选择当前节点
的 向上节 点，而不是随机地选择 。重 复该过程 ，直
至达到指定 的邻居取样数 ，m 。
(4)如集合 S中仍有空元素，则将步骤 (3)
中的最好试验解 (具有最小目标函数的试验解)加入
到集合S中；否则将该最好试验解与集合 中存储的
历史解作比较。如该最好试验解比最差历史解要好，
就用该最好试验解替代集合 S中的最差历史解。
(5)如 果 Sbe 没有步骤 (3)中产生 的最好试
验邻居解好 ，就用 该最好试验 邻居解更新 S 并
同时更新释放水平 ；否则转 向步骤 (5)。
(6)如 果步骤 (3)中产 生的试验 邻居解对应
的 “移动 ”不在 “Tabu表 ”中 ，或虽在 “Tabu表 ”
中但 已达 到 其释 放水 平 ，则 用该试 验 邻居 解 更新
S 。将产生该试验邻居解的 “移动 ”的反方向
“移动 ”存入 “Tabu表 ”中，同时更新 “Tabu表 ”，
转向步骤 (2)。如产生该试验邻居解的对应 “移动”
在 “Tabu表 ”中还没有达 到其释放水平 ，就检查下
一 个次优试验邻居解 ，并 重复该过程 。
(7)更新候选支路集合 S 中所有 支路 的 “信
息素 ”密度 ，转 向步骤 (2)。
5 算例分析
通过一具有 6个变 电所 、102条馈 线段 的配 电
维普资讯 http://www.cqvip.com
Power System Technology 、，_01．29 No．2
网对上述基于TS—ACO的配 电网规划方法进行测试
(如 图 3所示 )。图 中，101和 102为现有 网络 中 已
经存在的变 电站，103～106为可能的待建变电站；
用连续 实线段来表示现有 网络中的馈线 ，而可 能的
待 架设馈 线用虚线段表 示。表 1列 出了图 3中各 负
荷点的负荷需求。
102
图 3 现有配 电网络及可能的扩展网络
Fig．3 Existing distribution system and proposed
new additions
表 1 各负荷节点的负荷需求
Tab．1 Load dem an dsforallload nodes
节点号 负荷需求 节点号 负荷需求瓜VA 节点号 负荷需"：F~kVA
l 0 25 50o 49 240
2 3l5 26 0 50 70
3 0 27 3l5 5l 3l5
4 630 28 0 52 250
5 l0o 29 50o 53 4OO
6 70 30 420 54 250
7 40o 3l 3l5 55 3l5
8 630 32 0 56 240
9 0 33 80o 57 3l5
l0 250 34 0 58 3l5
ll 50o 35 l0oO 59 250
l2 240 36 3l5 6o 3l5
l3 0 37 240 6l 40o
l4 l0o 38 4OO 62 240
l5 80o 39 250 63 3l5
l6 3l5 40 315 64 4OO
l7 80o 4l l0o 65 l0o
l8 240 42 3l5 66 250
l9 l0o 43 4OO 67 80o
20 50 44 3l5 68 315
2l 3l5 45 500 69 500
22 4OO 46 3l5 70 250
23 3l5 47 3l5 7l 3l5
24 0 48 250
得 到的最优规划方 案如 图 4所示 。此方 案中 ，
整 个配 电网 由四个 具有 辐 射状 网络 结构 的子 网组
成 ，分别由变电站 101、102、103、106供电，其
中，变 电站 103、106为规划期间内计划投建的变
电站，变 电站 101、102、103、106供应的负荷点
的总负荷分别为 4850kVA、5470kVA、5685kVA和
5605kVA。该规划方案 的总费用为 13738．9401万元 。
其 中 ， 投 资 费 用 为 6369．2 万 元 ， 运 行 费 用 为
7369．7401万元 。
1 u 1
5 2 1 4
／ L
l 12 11
9 l10 — I
20 15 13 l14
191 ． 16 呸
t 22
23 18
25 2 4 27
29 26 28 31
I J l36 l30
I I
37 ·
J38 34 35 39l
lUZ
图 4 基于 TS．ACO混合算法的最优规划方案
Fig．4 Optimal planning scheme based on
TS·ACO hybrid method
得到的次优方案如图 5所示，该方案的总费用
为 13740．671 l万元，其中投资费用为 6365．42万元，
运 行费用为 7375．25ll万 元 。图 6为混合算法 与单
个算法 TS、ACO迭代过程 的 比较结果 。
由图 6可知 ，TS—ACO 混合算法 与 TS算法在
迭代次数为 l0次时给出的评价函数值要比ACO算
法给出的评价函数值小，主要是因为前面两种算法
I 1 u 1
5 2 1 4
6 7 ＼
箜— ———一
12 11 9 I10 一 ●————●——一
l 264 2Q 主
13 Il4
三 191 ． 16
60 23 22 1 ；
25 2 4 27
T29 28 31
l36 l3o
l 32 33 40 I
37
I38 34 35 39
102
图 5 基于 TS．ACO混合算法的次优规划方案
Fig．5 Suboptim al planning schem e based on
TS·ACO hybridmethod
48
47
46
维普资讯 http://www.cqvip.com
第 29卷 第 2期 电 网 技 术 27
迭 代 次 数 ／ 次
图 6 混合算法 TS．ACO与 TS、ACO迭代过程的 比较
Fig．6 Iteration comparison among TS-ACO，TS and ACO
的初始解 是通过配 电网的最小生成树给 出的 ，最小
生成树 具有较好 的网络 结构 ，因而给其后 的迭代过
程一个 良好开端。对 ACO算法而言，在迭代次数
小于 30时，由于迭代次数较少，“信息素”密度积
累也相应较少，算法的正反馈机制还没有得到充分
发挥 ，评价 函数值 下 降较慢 。在迭代 次数 小于 50
时，ACO算法的正反馈机制得到了充分发挥，具体
表现 为评 价函数值下 降较 快 。在其后 的迭代过 程 中
ACO算法表现得相当平稳，评价函数值的变化也较
小。图 6中，ACO算法在迭代次数约为 50时给出
的规划解 已经相当优秀，这也充分表 明，该算法具
有强大 的局 部搜索能力 。
与 ACO算法的迭代过程相比，TS算法要平缓
得 多。除在 开始阶段 以外 ，迭代 次数小于 90时 TS
算法的评价函数值均比 ACO算法的大。迭代次数
达到 190次时，TS算法给出的最优规划解的评价
函数值却比 ACO 算法给出的小，虽然两者的差别
极其微弱，这也从具体事例上证 明了 TS算法具有
良好 的全局搜 索性能 。
与单个算法相比，TS—ACO混合算法给出的迭代
过程更加令人振奋。除在开始阶段以外，这种算法在
其它时刻给 出的最优规 划解的评价 函数值均 不大于
单个算法给出的值。尽管 TS—ACO 混合算法在迭代
次数达到 170以后给出的最优规划解的评价函数值
与 TS算法相同，但与 TS算法相比，它具有更好的
局部搜索性能，从而有利于较早发现优 秀规划解。
6 结 论
(1)ACO算法能迅速找到比较优秀的规划解，
但找到最优解的过程很漫长，表明其具有强大的局部
搜索能力 ，但全局搜索性能不强 ；
(2)TS算法找到优秀规划解的迭代次数比ACO
算法的多，但它能够找到更为优秀的解，表明其具有
强大的全局优化性能；
(3)TS—ACO算法兼具 ACO算法和 TS算法的
优点 ，它既能迅速找到 比较优秀的规划解，又能找到
TS算法所找到的最优解。
参考文献
[1】 Ramirez-Rosado 1 J·Bemal-Agustin J L．Genetic algorithms applied
to the design of large power distribution systems[J】．IEEE Trans on
PowerSystems· 1998， l3(2)：696-703．
[2】 卢鸿宇．胡林献 ．刘莉．基于遗传算法和 TS算法的配电网电容器
实时优化投切策略[J1．电网技术，2000，24(1 1)：56-59．
Lu Hongyu，Hu Linxian，Liu Li．Optimal real-time capacitor strategy
in distribution netoworks based on GA and TS[J】．Power System
Technology，2000．24(11 ： 56-59．
[3】 陈根军 ，李继洗 ．王磊．等．基于 Tabu搜索 的配 电网络规划[J1．电
力系统 自动化，2001，25(7)：4o-44．
ChenGenjun，LiKK，WangLei，eta1．Distribution networkplanning
by a Ta bu search approach[J】．Automation ofElec tric Power Systems．
2001．25(7)：40-44．
[4】 王成 山．王赛一．基于空间 GIS和 Tabu搜索技 术的城市 中压配 电
网络规划[J】．电网技术，2004，28(14)：68．73，
W an g Chengshan · Wan g Salyi． M ed ium-voltage city distribution
network plan ning based onG1San dTabu searchtec hnique[J】．Power
System Technology，2004，28(14)：68-73．
[5】 陈根军 ．王磊 ，唐国庆 ．基于蚁群最优 的配 电网规划方法[J1． 电
网技术，2003．27(3)：71-75．
Chen Genjun·Wang Lei，Tang Guoqing，An ant colony optimization
based method for distribution network planning[J】．Power System
Technology，2003，27(3)： 71-75．
[6】 程国 良，王 熙法 ，庄镇泉 ，等．遗传算法及其应用IM】．北京：人
民邮电出版 社．1996．
[7】 陈章潮 ．顾洁 ．孙纯军 ．改进 的混合模拟退火 一遗 传算法应 用于
电网规划 [J】．电力系统 自动化 ．1999．23(10)：28—31．
Chen Zhangchao·Gu Jie·Sun Chunjun ．Application of improved
combined simulated annealing meth od an d genetic algorithms to
power netw ork plan ning[J】．Automation ofElectric Power Systems ·
1999， 23(10)：28-31．
[8】 岑文辉．雷友坤 ．谢恒 ．应用人工神经 网与遗传算法进行短期 负
荷预测 【J】．电力系统 自动化 ，1997．21(3)：29．32．
Cen W enhui·Lei Youkun·Xie Heng．Application ofANN an d GA to
short-term load forecasting[J】． Automation of Electric Power
Systems·1997．2l(3)： 28-32．
[9】 Glover F．Laguna M ．Tabu Search[M 】．Basel： Science Publishers．
1993．
[10】Dofigo M ·M aniezzo V·Colomi A．Ant system：optimization by a
colony of cooperating agents[J】．IEEE Trans on Systems ，Man and
Cybernetics—Part B： Cybernetics． 1996．26(1)： 1-13．
收稿 日期：2004—10-15。
作者简介：
陈根军 (1974一)．男 ．博士．从事 EMS高级应用软件和 配网自动
化 的外发和研究工作；
唐国庆 (1937．)，男 ．教授 ．博士生导师 ．从事电力系统运行与控
制 、配网 自动化、电力电子在配 电网中的应用、人工智能在电力系统中
应用方面的研究工作
维普资讯 http://www.cqvip.com
基于禁忌搜索与蚁群最优结合算法的配电网规划.pdf
