基于无向图所有生成树的网络重构遗传算法

摘要

本发明公开了一种基于无向图所有生成树的网络重构遗传算法，首先构建出配电网的简化图，搜索出配电网简化图的所有生成树，得到连支，连支的每条边上有且仅有一个开关打开；提出了以连支每条边的开关数量为基向量、打开开关在边上的编号为优化变量的十进制编码方法，大大缩短了编码长度；每棵生成树对应一个子种群，并行计算子种群中的遗传操作，得到的子代个体自动满足配电网辐射状、无孤岛运行的约束条件，避免了传统网络重构遗传算法产生大量不可行解，搜索效率低的弊端。

主权项

基于无向图所有生成树的网络重构遗传算法，其特征在于，包括以下步骤：1）、构建配电网的简化图，采用无向图所有生成树的搜索算法搜索出简化图中所有的生成树和连支，所述简化图的构建方法为：城市配电网拓扑结构图是以配变或线路为支路、负荷母线为节点的有环、无向、连通图，将配电网拓扑结构图中不在环路中的支路去掉、度为2的相邻节点所在的支路合并成一条边，由此构成一个简化图；所述生成树是指包含简化图的所有节点，但不包含简化图的所有边的简化图的子图；所述连支是指简化图减去生成树剩下的边组成的集合；2）、计算所述步骤1） 的所有的连支的基向量和连支的候选解个数，所述连支的基向量是指以连支中每条边上的开关数量为分量组成的向量；所述候选解个数的计算方法为将连支基向量的每个分量作乘积运算即为该连支对应的候选解数目；3）、并行产生初始的子种群，所述子种群与连支一一对应，子种群中染色体的长度等于连支上边的个数，所述染色体每一位的取值等于对应边上打开开关的编号，染色体第i位取0，1，2……N_i‑1中的某一个值，N_i为连支第i条边上的开关数目；4）、并行计算子种群中染色体的适应度值，具体计算方法为：对染色体代表的配电网中打开的开关采用十进制编码方法进行解码，采用并行前推回代算法计算网损值，对子种群中每个染色体对应的网损值按照从小到大进行排序并编号，将编号等间隔线性映射为0‑2中实数作为每个染色体对应的适应度，并定义网损值最大的染色体对应的适应度值为0，网损值最小的染色体对应的适应度值为2，相邻的染色体适应度值间隔相等；5）、并行在子种群中进行基因操作，具体包括如下步骤：5‑1）进行子种群选择操作对于每个子种群，根据染色体的适应度值，采用 “赌轮盘”法选择N个染色体，所述N为偶数；5‑2）进行子种群交叉操作按照指定的概率将双亲染色体对应基因位数值互换；5‑3）进行子种群变异操作按照指定的变异概率将双亲染色体中一位或多位基因替换为小于基向量对应位的非负整数值；5‑4）进行子种群重插入操作将每个子种群中选择的N个染色体完成了交叉、变异操作的染色体重新插入父代，同时计算子种群中染色体的适应度值，淘汰掉子种群父代中适应度值最小的N个染色体；6）、完成所有子种群的基因操作后，整个种群中网损值最小的染色体即为最优解，即按照该染色体所代表的配电网中打开的开关组合进行配电网网络重构。