沙智明，郝育黔，郝玉山，杨以涵
(华北电力大学电力工程系，河北保定071003)
摘要：将进化衰减因子引入了遗传算法，构造了一种新的自适应遗传算法。新算法在进化过程中能够同时根据个体适应度和进化时间的变化自动调整交叉与变异概率，克服了遗传算法易早熟的缺点，提高了最优解的多样性，加快了算法寻优速度。精英个体保留策略保证了整个算法的全局收敛性。算法约束条件处理采用了不可行解启发性修复方法，保证了全部优化结果都被严格限定在了满足约束条件的解空间内。基于图论的深度优先搜索方法用于系统可观性分析。将新的自适应遗传算法应用于优化P MU安装地点选择，实现了安装地点最少，而整个系统可观的目标。该算法已在某省电网P MU安装地点选择优化计算中得到了实际应用。关键词：相量测量装置; 可观性; 自适应遗传算法; 最优化 中图分类号:T M744;TP18 文献标识码:A 文章编号:100324897(2005)0720031206
0 引言
在大电网中，基于GPS的同步相量测量装置P MU(Phas or Measure ment Unit)的作用日益突出[1,2]。在所有的变电站与发电厂都安装P MU，将大大改善电力系统的监控水平[3]。但由于目前P MU价格昂贵，
这样做会增加系统的一次性投资，而分阶段安装P MU比较现实，即在初期先安装一定数量的P MU，以保证系统可观，以后再逐步增加P MU安装数量，以提高测量冗余度。
在保证系统可观的前提下，在哪些节点安装P MU，才能既保证测量系统可观又使P MU安装数量最少，就涉及到了组合优化的问题。求解这类最优化问题主要有三种方法：枚举法、启发式算法和搜索算法。枚举法的效率比较低，在空间规模较大时会出现组合爆炸。启发式算法效率较高，但针对不同的问题需要出其特定的规则，不具通用性。搜索算法使用了某种规则随机搜索最优解，可以同时在解的质量与效率上达到好的平衡，已被广泛应用于各种优化计算中[4]。 Bald win最先研究了在电网中安装最少数量的P MU并保证系统可观的问题[5]。他采用了修正的二分搜索方法(B isecting Search)和模拟退火方法(Si m ulated Annealing)相结合的双搜索算法，来求解P MU安装数量的最小子集。但由于此方法的计算量过大，影响了其在较大规模系统中的应用。Ki2 Seon Cho分别采用改进的模拟退火法、直接组合法(D irect Combinati on)和禁忌搜索法(Tabu Search)研究此问题[6]。由于改进的模拟退火法只是针对不同的解集合对算法的初始温度及冷却过程等方面进行了改进，在本质上并没有摆脱模拟退火法收敛慢的弱点。直接组合法可大大减小搜索空间，从而避免了模拟退火法的计算时间长的问题，但需要根据不同的问题制定相应的启发性规则。禁忌搜索法通过在算法中定义一个禁忌列表来记录历史搜索结果，来保证不发生重复搜索，以减小搜索空间，加快搜索速度。但该算法对初始解有较强的依赖性，而且禁忌列表的长度对算法性能有显著影响。若列表长度
过短，会造成重复搜索，从而导致算法收敛太慢。若列表长度过长，会造成算法早熟[7]。文献[6]是针对不同的问题，通过反复尝试的方法来确定列表的长度，虽然提高了寻优过程的计算速度，但通用性仍较差。
针对上述问题，本文提出了一种新的自适应遗传算法，在遗传算法中引入了进化参数衰减因子，使得算法能够同时根据个体适应度变化和进化时间自动调整交叉与变异概率，提高了解的多样性，克服了算法早熟，加快了寻优速度。在遗传算法的约束条件处理时，采用了不可行解启发性修复方法，保证了全部优化结果都被严格限定在满足约束条件的解空间内。基于图论的深度优先搜索方法用于P MU测量系统的可观性分析。新的自适应遗传算法具有良好的通用性，在I EEE14节点系统、I EEE39节点系统的优化计算中取得了满意效果，并在某省电网46节点系统的优化计算中得到了实际验证与应用。
13
第33卷 第7期2005年4月1日
奥巴马复旦大学演讲
喷射混凝土用速凝剂继电器
RELAY
Vol.33No.7
Ap r.1,2005
1 电力系统可观性分析方法
1.1 电力系统可观的定义[8,9]
考察一个系统是否可观，可以从两个角度来分析，即代数可观(A lgebraically observable)与拓扑可观(Topol ogically observable)。
1)代数可观
一个N节点，有m个测量量的电力系统，可以用下面的线性化测量方程来描述:
z=H x+v(1)其中:z为m维测量向量,H为m×(2N-1)维测量雅可比矩阵，为2N-1维电压状态向量,v是m维测量噪声向量。
如果测量雅可比矩阵H是满秩和良态的，即满足R ank(H)=2N-1，则这个系统是代数可观的。
2)拓扑可观
从图论的角度，可以将电力系统看作是一个由N个顶点b条边构成的图G=(V,E),V表示图的顶点集合,E
表示图的边集合，它们分别对应于系统的母线与支路的集合。测量网络构成了一个测量子图G′=(V′,E′)，并有V′ΑV,E′ΑE。如果测量子图G′与图G的关系满足VΑV′，即子图G′包含了图G的所有顶点，则系统是拓扑可观的。
1.2 虚拟测量
由于P MU可同时测量节点电压与支路电流相量，安装P MU的节点电压与支路电流可被直接测量，而未安装P MU的节点电压与支路电流可以经虚拟测量来获得。虚拟测量(Pseudo-measure ment)是一种不通过直接测量，而是利用与待测量相关的测量量经计算而得出待测量的方法[10]。在电网中，虚拟测量有以下三种类型[5]:
1)已知支路一端节点电压和支路电流，则支路另一端节点电压被虚拟测量;
2)已知支路两端节点电压，则支路电流被虚拟测量;
3)节点除一条支路外，其余支路电流都已知，则未知电流支路的电流被虚拟测量。
1.3 基于图深度优先搜索的可观性分析方法
分析电力系统的可观性的过程，就是构造系统测量生成树(Measure ment Spanning Tree)的过程。本
文根据系统网络邻接矩阵所确定的节点之间的连通关系，采用深度优先搜索(Dep th First Search)技术[11]，从安装P MU的节点开始，通过测量或虚拟测量的电流支路，扩张到虚拟测量的电压节点，然后再从这些电压节点通过电流支路继续向外扩张，在所有节点扩张完成后会生成一棵测量树。若这棵树包含了所有系统节点，则整个系统就是拓扑可观的。若某些系统节点没有包含在测量树上，则系统不完全可观，且这些节点也不可观。
若有一个n节点的电力系统，需要在m个节点处安装P MU，以实现系统可观测，其可观性的具体判断算法如下:
算法调用将从所有安装P MU的节点开始，向不可观测节点扩张搜索。
1)将当前节点标记为电压可观测;
2)若当前节点安装了P MU，则将与当前节点关联的各支路电流标记为可观测;
3)若当前节点没有安装P MU，则搜索当前节点是否存在2.2中的第2类虚拟测量电流支路;
4)若当前节点是无负荷节点，则搜索当前节点是否存在2.2中的第3类虚拟测量电流支路;
5)确定子节点的搜索方向。原则为：子节点没有安装P MU、或支路连通且可观测、或子节点不可观测。如果存在多个搜索方向，则先按节点序号小的方向搜索;
6)根据上一步确定的搜索方向，从步骤1开始进行递归调用，遍历所有可扩张子节点;
7)根据搜索结果，生成测量树。若测量棵树包含了所有系统节点，则系统是可观的，否则列出不可观测节点，输出结果。
2 改进的自适应遗传算法
遗传算法是一种搜索能力很强的全局优化算法。它不依赖于具体问题，对目标函数及约束条件既不要求连续，也不要求可微，对优化设计的限制较少，因而在很多领域取得了广泛应用[4]。在遗传算法中，交叉概率与变异概率的取值对算法的性能有着至关重要的作用。交叉运算是遗传算法产生新个体的主要方法，它决定了遗传算法的全局搜索能力。交叉概率取较大值会加快新个体的产生，与此同时也会迅速破坏优良个体，取较小值又会使得算法搜索停滞不前。变异运算是产生新基因的方法，它决定了算法的局部搜索能力。变异概率取值过大会使算法退化为随机搜索，取值过小将难以产生新基因，造成算法早熟[12]。
2.1 传统的自适应遗传算法
标准遗传算法对交叉与变异概率的取值一般是凭经验和反复试验来确定，而且是针对不同的问题
23继电器
取不同的值，数值通常也是固定的。为此,Srinivas 提出了一种自适应遗传算法AG A(Adap tive G A)，其交叉概率与变异概率会随着个体适应度变化而自动调整[13]，如下式:
P c=K1·
f max-f′
f max-f avg
, f′≥f avg
K3, f′<f avg
(2)
P m=K2·
f max-f
f max-f avg
,f≥f avg茶细蛾
K4,f<f avg
(3)
其中:f
avg 为体平均适应度,f
max
为体最大适应
度,f′为参与交叉的两个体适应度的较大值。他同
时建议K
1、K
3
取1.0,K
2
、K
4
取0.5，这意味着低于
平均适应度的个体会全部参与交叉并以较大概率进行变异运算，以产生新解和引入新基因；而高于平均适应度的个体将减小交叉和变异的机会，而不受到破坏。自适应遗传算法在一定程度上改善了标准遗传算法因参数选取不当而引起的早熟现象，而且进化结果的多样性也优于标准遗传算法。但此方法对于体处于进化后期相对有利，而对进化初期存在一定的不利影响。在进化初期，体的最大适应度与优良个体的适应度之差接近或等于0，使得优良个体的交叉与变异的概率近似为0，从而造成了优良个体处于一种不交叉和不发生变异的状态。而此时的优良个体不一定是全局最优解，这造成了算法容易陷入局部最优[14]。
2.2 改进的自适应遗传算法
为了提高算法摆脱局部最优的能力，应该使进化早期与中期的优良个体保持一定的交叉与变异概率。另外，从体的整个进化过程来看，在进化初期与中期个体交叉和变异的概率的取值应该大一些，以
便开拓新的搜索空间，并防止早熟。在进化晚期，个体交叉与变异概率的取值要小一些，以保护全局最优解不被破坏。个体交叉和变异的概率在总体上应随着进化代数的增加而动态地逐步减小。
为此，本文提出了一种改进的自适应遗传算法I A G A(I m p r oved Adap tive G A)，该算法可同时根据个体的适应度与进化时间的变化自动调整交叉与变异的概率。新算法如下式所示:
P c=F(t)·[K0+(K1-K0)·
f max-f′
f max-f avg
],f′≥f avg
K1,f′<f avg
(4)
P m=
F(t)·[K2+(K3-K2)·
f max-f
f max-f avg
],f≥f avg
K3,f<f
avg
(5)
式中:F(t)=λe-β(t T)α为进化衰减因子,t为进化时
间,T为总进化代数,λ、T、α、β等参数共同决定了衰
减因子的作用幅度与下降速度。图1是衰减因子在
不同参数下的衰减曲线。其中参数λ=1。从图中
可看出，衰减因子F(t)随时间变化的衰减程度，在
进化初期与中期基本没有衰减，而在接近进化结束
时，衰减会十分剧烈，衰减倍数随着进化代数的增加
迅速下降到0。
图1 不同参数时的衰减因子
Fig.1 A ttenuati on fact ors with different para meters输液管
通过对公式(4)、(5)的分析可知：在进化初期
与中期，取λ=1时，衰减因子F(t)=λe-β(1T)α≈1,
衰减因子的衰减作用并不明显，高于平均适应度的
个体的交叉与变异概率可以根据适应度变化自动调
整，调整的范围分别为K
～K
1
和K
2
～K
3
。由于高
于平均适应度的优良个体保持的最小的交叉与变异
概率分别为K
和K
2
，使得算法在总体上保持了较
高的交叉与变异概率，能够抑制算法早熟，并有利于
新个体产生。随着进化的进行，体趋向于最优化,
变异与交叉的概率将缓慢减小。在进化晚期，个体
的交叉与变异概率在衰减因子作用下迅速减小，从
而可以有效保护最优解不被破坏。
算法还采用了精英个体(Elitist)保留策略，在进
化过程中一定数量的精英个体将不参加交叉和变异
操作，而是被直接复制到下一代，从而保证了整个算
法的全局收敛性[15]。
3 相量测量装置安装地点选择的优化算法
3.1 优化算法的数学模型
P MU的安装地点选择是一个组合优化的问题,
33沙智明，等 电力系统P MU安装地点选择优化算法的研究
可用以下数学模型描述:
M in J=m(6)
i
=0,i=1,…,N
其中:m为P MU安装数量,U
i
表示第i个节点不可观,N为系统节点数。
3.2 染体编码
染体采用二进制编码，染体长度等于系统节点数N，每个基因位值由下式确定:
X i=1, 节步i安装了P MU
断章 赏析0, 节点i未安装P MU
(7)
其中:i=1,…,N
3.3 适应度函数与约束条件处理
优化对象的约束条件是U
i
=0，即保持整个系统可观。当出现不满足约束条件的解(存在不可观节点)时，本文采用了不可行解的启发性修复方法进行处理。具体为：首先从不可观节点中选择支路数最多的节点，为其安装1台P MU，即将该节点对应的染体基因位置“1”；然后再判断染体是否满足约束条件，如果不满足则重复上述过程，直到约束条件得到满足为止。经过这个修复过程，问题的解就被严格限定在了满足约束的可行解空间内。
由于经过处理的所有染体都满足约束条件，适应度函数可定义为:
f=C max-C1·6N i=1X i(8)
其中:C
max
为一个较大的数以保证适应度函数值大
于0,C
1为比例系数。本文取C
max
=50,C1=1。
经过对比测试，不可行解的启发性修复方法的效
果要优于遗传算法普遍采用惩罚函数等处理方法。
3.4 遗传操作
遗传操作主要包括选择、交叉与变异等运算过程。选择运算是模拟自然界生物进行优胜劣汰的过程，选择算子将适应度高的个体以较大机率复制到下一代，而淘汰适应度低的个体。选择算子有很多种，如Roulette赌法、排序法、随机联赛法(St o2 chastic Tourna ment)等[4]。本文算法采用随机联赛法类型的选择算子，联赛规模取2，同时算法保留精英个体。交叉运算是遗传算法产生新个体的主要方法，它决定了遗传算法的全局搜索能力。交叉算子用式(4)确定的自适应交叉概率P
c
进行两点交叉
操作，即随机选取两个交叉点，以概率P
c
交换两点之间的基因。变异运算是产生新基因的方法，它决定了算法的局部搜索能力。本文变异算子采用式(5)确定的自适应变异概率P m进行两点变异操作。3.5 算法主要步骤
1)产生规模为M的初始体，设定进化代数T;
2)自适应交叉与自适应变异;
3)可观测性分析及不可行解修复;
4)计算个体适应度;
5)随机联赛法选择及精英个体保留，产生新一代体;
6)如果没有达到进化代数转第2步，否则程序结束。
4 算例分析
本文应用在Matlab6.5软件下开发的自适应遗传算法、P MU测量网络可观性分析及P MU安装地点选择优化程序，分别对以下算例进行了验证。
4.1 算例1
I EEE14节点系统如图2所示，其中节点7为无负荷节点[10]。使用改进的自适应遗传算法，取体规模M
=40，进化代数T=30，即可收敛到最优解。计算结果为，在2、6、9节点安装测量装置即可使全系统可观。
图2 I EEE14节点系统
Fig.2 I EEE142bus syste m
4.2 算例2
图3为I EEE39节点系统，其中1、2、5、6、9、10、11、13、14、17、19、22节点为无负荷节点。使用改进的自适应遗传算法，取体规模M=100，进化代数T=60。计算结果为，只需安装9台P MU即可使全系统可观，并到多种安装方案。表1是其中的几种优化结果。
表1 I EEE39节点系统的优化方案
Tab.1 Op ti m al sche me of I EEE392bus system
序号安装地点方案
1238101620232529
2238121623293437
33610162023252939
43812162325293439
561018202123293739
43继电器
图3 I EEE39节点系统
Fig .3 I EEE392bus syste m
4.3 算例3
图4是某省电网的结构图，本文分别使用标准
遗传算法SG A (Standard G A )、文献[13]的自适应遗传算法(AG A )和改进的自适应遗传算法(I A G A )进行了安装地点的选择优化计算。每种算法均取体规模100，进化100代，各算10次。优化计算对三种算法的全局收敛性、解的多样性和收敛速度等方面做了比较，计算结果如表2所示
。
图4 某省电网结构图
Fig .4 A 462bus syste m in one p r ovince
表2 三种算法性能的比较
Tab .2 Perfor mance comparis on of I A G A,AG A and SG A
算法
收敛到全局
最优次数
收敛到局部最优次数最优解多样性
I A G A 7321种AG A 4612种SG A
1
9
1种
由表2的结果可以看出：在全局收敛性方面,I A G A 收敛到全局最优的次数最多，达到了7次,AG A 收敛到全局最优的次数为4次，而SG A 很难收敛到最优解；在解的多样性方面,I A G A 总共到了
21种最优解,AG A 只到了12种，而SG A 只到1
种；在收敛速度方面，由于平均适应度上升程度反映
了体的优化速度，从图5的平均适应度的变化曲线可知,I A G A 和SG A 的平均适应度上升的速度较快,AG A 的上升速度要慢一些，这说明I A G A 和SG A 比AG A 收敛速度快。上述结果表明,I A G A 在整体性能上要优于AG A 和SG A
。
图5 不同算法的平均适应度比较
Fig .5 Comparis on of average fitness value
for I A G A,AG A and SG A
本文使用I A G A 算法进行P MU 安装地点优化
过程中，在未考虑某些节点在系统中的重要程度的情况下,I A G A 在10次计算中到了21种最优解，结果均为只需要在系统中安装13台P MU 就可以使全系统电压可观。如果要考虑某些节点在系统中的重要程度，则可依据节点的重要性为其设置不同的权值，并作为启发性规则加入到优化算法中。这样，重要的变电站、发电厂就可配置P MU，直接测量其母线电压相量，可得到表3中的优化结果。
表3 优化的安装地点方案
Tab .3 Op ti m alized P MU l ocati ons in
the 462bus syste m
序号
安装地点方案
1151115202324262732354546225911141520262732344243323581415202426293234434
6
9
11
14
15
20
23
24
26
29
32
35
45
5 结论
新的自适应遗传算法可在进化过程中同时根据个体适应度和进化时间的变化自动调整交叉与变异概率，克服了原有自适应遗传算法易早熟的缺点，提高了最优解的多样性，加快了算法寻优速度，有效地保护了最优解不被破坏。将新算法应用于P MU 安装地点的优化选择，达到了在保证全系统可观的前提下，使P MU 的安装数量最少的目标。在某省46
5
3沙智明，等 电力系统P MU 安装地点选择优化算法的研究第一首完整的七言诗
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议