配电网重构中遗传算法编码策略的研究

2012-07-12三峡大学电气与新能源学院赵辛欣

电子世界 2012年8期

三峡大学电气与新能源学院叶婧赵辛欣

1.引言

配电系统具有闭环结构、开环运行的特点，包含了大量的常合分段开关及少量常开的联络开关。在正常的运行条件下，配电调度员根据运行情况进行开关操作以调整网络结构。通过配电网网络重构，一方面平衡负荷，消除过载，提高供电电压质量；另一方面降低网损，提高系统的经济性。配电网络重构是提高配电系统安全性和经济性的重要手段。理论上，在满足各种运行约束条件下，以网损最小为目标的配电网络重构问题是一个非线性组合优化问题。其中作为优化变量的开关数量巨大，穷举搜索将面临“组合爆炸”问题。

遗传算法(genetic algorithm，缩写为GA)是模拟生物进化过程的计算模型，由于GA的整体搜索策略和优化时不依赖梯度信息的特点，使其在自适应控制、组合优化和模式识别等方面得到了广泛应用。近几年来，不少学者将GA应用于以网损最低为目标的配电网重构中。由于GA并不直接作用于待求变量本身，而是先将待求变量进行编码，然后GA对这些编码进行交叉、变异等操作，从而找到最优解，所以在使用GA前必须先选择一种编码方法。一般说来，由于GA的鲁棒性，它对编码的要求并不苛刻。但是，GA中编码的策略或方法对遗传操作，尤其是对于交叉操作的功能有很大的影响，在很多情况下，编码形式也就决定了交叉操作。本文将针对现有的遗传算法编码方式的计算效率进行分析。

2.传统的2进制编码

用2进制表示时，一般将网络中的开关状态用0和1表示，每个开关占染色体的1位，0代表分闸状态，1代表合闸状态，各支路状态组合在一起就形成了一条染色体，染色体的长度为网络中开关的数目。如图1所示的馈线系统的开关状态可用二进制表示为：[1110111110111110]。种方案简洁明了，但在GA的运行过程中会产生大量的不可行解，严重影响了GA的计算效率。

对于图1所示的配电系统，一共有16条支路，一般认为每条支路上均有开关，按上述编码方法，染色体长度为16，该配电系统GA空间将有216＝32758个染色体。通过组合数学可以得出图1中的配电系统GA表现型个体为190个[1]。有效候选解只占 1 90 / 32768= 0 .5798%。这表明：按照传统的二进制编码方式进行编码，在GA运行过程中，只能产生非常少的可行解，因此按这种编码方式，搜索效率是非常低的。

图1 IEEE典型三馈线系统

3.基于环路的2进制编码

配电网在正常运行时呈放射形，并且每个节点的负荷都必须有电能的供给，因此配网中开关的开合并不是任意组合的。为了提高有效侯选解比例，很多文章提出了基于环路的2进制编码策略[1，3，4]，对于环路，不同的文章定义不同，由此也产生了不同的编码方式。

3.1 一个联络开关对应一个环路的编码策略

文献[1，4]提出采用构成同一环路的开关在同一基因块内、相邻开关在染色体中相邻的染色体编码策略。文献[1，4]中一个环路对应着一个联络开关。如果一个联络开关合上，则会构成一个小环，必须在此环中打开一个分段开关，使配网保持辐射型。采用这种编码策略，不可行解数目大大降低。文献[1]对图1的配电系统编码如表1所示。

表1 图1的编码结果

文献[1，4]采用交叉操作只进行对应基因块的交换，而变异操作限制在基因块内的遗传操作策略。在同一个环内即同一个基因块内，选择一个开关断开，以此形成初始解。变异操作时，首先选定一基因块，然后在确定的基因块中随机选定一位基因将其值取反，产生不可行解后，再按一定的方式将不可行解消除。

采用这种编码方式，相对于传统的二进制编码方式而言，产生初始解以及经过交叉变异产生的候选解中不可行解的比例大大降低。但是复杂的配电系统环路间存在公共开关的可能，故各环路对应基因块可能重叠。因此，这种一个联络开关对应一个环网，一个环网内只允许有一个断开开关的编码方式，在存在公共开关的系统中，仍然会产生一些不可行解。

3.2 一个回路对应一个环路的编码策略

文献[3]提出一种新的环路的概念，即环路指的是配电网的开关全部闭合时，在网络中形成的闭环回路，有2种形式：（1）从配电网的一个电源节点出发，每个节点只经过一次，到达另一个电源节点的环为第一类环；（2）从配电网的某一个节点出发，每个节点只经过一次，又回到这个节点的环称为第二类环。

对图1所示的网络，按照文献[1]中环路的定义，对应的三个环路为[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]。而按照文献[3]环路的定义，则图1中含有五个环路，分别是[1 5 10 9 7 6]；[6 11 16 15 12]；[1 2 3 4 14 13 12]；[1 5 10 9 7 11 16 10 12]；[2 3 4 14 13 15 16 11 7 9 10 5]。其中前4个环路为第一类环，第5个环为第二类环。

文献[3]产生初始解的方法为：(1)令所有基因值均为1；(2)按顺序判断各环路中是否有断开的开关，如果没有，则随机断开该环路中任一个开关，这样可以保证不形成闭环；如果已经存在，不论几个，都不再操作，因为当一个环路与其它环路有公共开关时，可能出现一个环路中断开多个开关的情况，但不会行成孤岛。

按这种方法产生的初始解都为可行解。这种方法避免了文献[1]中的初始解出现不可行解情况，但是在交叉和变异过程中，含有公共开关时，仍然可能产生不可行解。

4.十进制编码策略

4.1 基于环路的编码策略

采用二进制编码染色体的长度很长，采取开关状态为控制变量，用0或1表示，并且不采用任何缩短染色体长度策略时，染色体的长度为网络开关数总和。基于上述原因文献[2]提出了十进制编码规则。

首先将全网的联络开关以自然数编号，并在每个联络开关所确定的环网内将开关单独编号（从1到小环里的开关总数）。遗传编码以联络开关确定的小环网为基因位，该位上的值是该环网里打开的开关编号，基因位上的取值是受限制的，必须是正整数，并且从1到小环里的开关总数。染色体长度等于联络开关数（环网数）。

文献[2]中环路的定义同文献[1]中相同，即一个联络开关对应着一个环路，一个环路只能存在一个断开的开关。采取这种编码方式，有效地缩短了染色体的长度，但对于环路间含有公共开关的复杂配电网，由于公共开关，与文献[1]中的方法存在着同样的问题，在初始解的形成和基因操作过程中会产生不可行解。并且文献[2]中所提方法需要对联络开关进行编号，并且在每个环网中需要对每个开关进行重新编号，与二进制编码相比更为复杂。

4.2 基于随机生成树策略的编码方法

常规的编码策略容易产生不可行解，文献[7]利用图论的避圈策略生成树，保证重构后的结果为放射形，避免了不可行解的产生。

对配网中所有的开关支路进行十进制编码，将不在环路中的开关始终保持闭合状态，将环路中的所有支路按顺序组成一个支路序列。如图1所示网络，可形成染色体:[5 10 9 7 11 16 15 2 3 4 14 13]，改变基因座的顺序可以得到其它的染色体。任一染色体对应着可以生成一棵树，通过图论“避圈法”文献[7]保证了所生成的树都为连通的放射型。

文献[7]所提方法，在配电网重构过程中可以避免不可行解的产生，提高了计算效率。但在染色体解码过程中不如其它方式简单直观。