遗传算法简介及基于单亲遗传算法的配电网扩展规划

中图分类号：TM421 文献标识码：A

1. 遗传算法简介

遗传算法是一种借鉴生物界自然选择和自然遗传机制的稳健的、随机化搜索寻优技术，它的稳健性来自于对多峰值情况下全局最优解的定位能力。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是二十一世纪有关智能计算的关键技术之一。

遗传算法的本质是一个群体的迭代寻优过程。其主要特点是：①利用目标函数变量的编码（个体）进行进化；②在解空间中从多点寻找问题解；③引入了概率转换规则，因此能搜索离散的有噪声的多峰值复杂空间；④使用随机操作，同时具有一定的方向性，它使用随机工具来指导搜索向一个最优解前进，的方向性使得它的效率远远高于一般的随机算法；⑤具有隐含的并行性。

遗传算法中包含了如下五个基本要素:

1 编码

利用遗传算法进行问题求解时，首先确定问题的目标函数和变量，然后对变量进行编码。编码方式一般分为二进制编码和实数编码。

2 初始群体的产生

为满足遗传算法的群体型操作的需要，必须为遗传操作准备一个由若干初始解组成的初始群体。一般来说，初始群体的产生可采取如下的策略：

(1) 根据问题的固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后在此分布范围内设定初始群体。

(2) 随机生成一定数目的个体，然后从中挑选出最好的个体加到初始群体中。这一过程不断迭代，直到初始群体中的个体数达到了预先确定的规模。

3 适应度函数的设计

遗传算法使用目标函数即适应度函数来评估个体或解的优劣，并作为以后遗传操作的依据。适应函数的构造应根据具体规划而定。通常是规划目标函数和约束条件的另一种描述方式。

4 遗传操作设计

选择(selection)、交叉(crossover)、和变异(mutation)是遗传算法的三个主要操作，它们构成了所谓的遗传操作，使遗传算法具有了其它传统方法所没有的特性。

选择操作：比例选择是以适应度的大小为比例进行遗传过程中的父体选择，被选中的个体作为父代参与后面的遗传操作以产生子代，也就是给那些处于优势的个体以更多的繁衍机会。

交叉操作：是产生新个体的主要手段。它仿照生物学中的杂交原理，将两个个体（染色体）的部分字符（基因）互相交换以产生新个体。实行交叉的个体是随机选择的，参与交叉的个体总数由交叉概率Pc控制。交叉点的选择也是随机的。

变异操作：是遗传算法中产生新个体的另一种方法，它是将某一个体的某一位字符进行补运算。变异个体的选择以及变异位置的确定，都是采用随机的方法产生，参与变异的字符量由变异概率Pm控制。针对每个字符在[0,1]之间产生三位有效数的均匀分布随机数，凡是随机数小于Pm所对应的字符，将实行变异。

5 控制参数设计（主要指群体规模的大小和使用遗传操作的概率）。

这五个要素构成了遗传算法的核心内容。

2. 单亲遗传算法简介

2.1 单亲遗传算法简介

单亲遗传算法 (Partheno-Genetic Algorithm，PGA)在遗传操作中通过单个父代个体产生子代个体，不进行两条染色体之间基因的交叉操作，而是通过一条染色体中基因的换位等操作来实现遗传。只通过选择和变异算子繁殖后代，其选择算子跟传统遗传算法的一样，而变异算子则有较大区别。

PGA同常规遗传算法类似，也是一种采用随机搜索方式的种群算法：通过遗传算子等操作，产生出适应性更强的后代种群；通过不断繁衍而获得种群的进化。PGA不采用杂交算子，而是只通过选择和变异算子繁衍后代。其选择算子同常规遗传算法一样，可以采用赌等多种策略，而变异算子则与通常的遗传算法有所不同。

PGA的变异操作包括基因突变、基因换位等。

与常规遗传算法相比，单亲遗传算法具有计算效率高、不存在“早熟（局部收敛）”等优点。

单亲遗传算法(PGA)是一种适合于求解组合优化问题的新型算法，它与传统遗传算法相比，具有不要求初始群体的广泛多样性、不存在“早熟收敛”问题、操作简单和计算效率高等优点。

2.2 提高单亲遗传算法计算效率的措施

在遗传迭代的不同阶段使用不同的遗传操作方法有利于提高计算效率。因此，在遗传迭代过程中引入一些启发式规划，构成自适应启发式PGA，是提高计算效率的有力措施。其启发式规则的构造应视具体问题作具体分析。通用的启发式规则有：

1 在种群具有多样性时，使用单点遗传算子；而在种群不具有多样性时，使用多点遗传算子。

2 在遗传迭代的早期，使用先繁殖后选择的运算方式；而在遗传迭代的晚期，使用先选择后繁殖的运行方式。

3 若初始群体不具有多样性，则应使用多点遗传算子使种群中个体尽快分布到整个串空间。

3. 基于模糊的配电网扩展规划的多目标数学模型

配电网网架优化的目标是在规划水平年负荷预测已知的条件下，确定满足运行要求的最经济的接线方案。其中，运行要求指的是满足基态运行约束（过负荷约束、电压降落约束、辐射状网络以及可靠性等约束）。经济性目标通常为网络的建设费用和运行及损耗费用。因此配电网网架优化是一个多目标、大规模、非线性的混合整数优化问题。

配电网网架规划的基本要求：

1 要有稳定可靠的供电能力。

2 要有较大的灵活性和适应性。

3 经济性。

4 网架结构分层分片。

5 简化接线增大容量。

传统的数学规划方法能够从理论上保证规划方案的最优性，但当网络规模增大时，就使得问题求解所需时间较长、占用计算机内存大。遗传算法模拟生物进化过程，以概率搜索全局最优点，具有全局收敛性、鲁棒性强、无函数连续可微要求等优点，使得遗传算法在配电网网架优化方面有较好的应用性。

3.1 配电网扩展规划的数学模型

配电网规划的目的在于根据投资及运行等费用最小的原则，在满足一定约束条件下，确定待建线路的类型、时间及地点，保证安全可靠地将电力由变电站送给用户，并且电源仓位及沿途环境等都可以接受。

在现有旧网架的基础上进行配电网扩展规划，是符合目前城市配电网改造和规划的现状的。研究此问题下的配电网扩展优化规划，有显著的现实意义和经济效益。本文规划模型考虑以下两个经济指标：

1 目标函数一 ———— 投资最小

配电网络年计算费用包括线路投资等年值、折旧维护费、运行费用。

目标函数表达式如下:

其中N为负荷变压器节点数目；Si为连接第i个节点的馈线的截面；Ci为第i条馈线的年投资费用及折旧维护费用；Di为年运行费用（网损）；M为出线条数；Ei为出线仓位投资等年值。

馈线投资费用与导线近似有线性关系：

其中a为等年值系数和折旧率之和，和为常数，为馈线长度。

等年值系数a的表达式如下：

其中r为贴现率，Y为折旧率。

年运行费用Di和多种因素有关：

其中为馈线电阻率，为最大负荷损耗小时数，为电价，Pi、Qi为最大负荷值，为线路额定电压。

出线仓位投资等年值Ei的表达式：

其中a等年值系数是，Fi为出线仓位投资。

2 目标函数二 ———— 改造成本最小

定义差异目标函数如下：现有负荷点间的线路和规划结果不同时，改造线路、新建线路等的综合费用函数。

其中为单位改造成本；

3 约束条件：

（1）功率平衡：

（2）容量约束： 对线路 ；对变电站

（3）网络连通性：要求对所有负荷点供电。

（4）网络辐射性：由于配电网开环运行，每个负荷点只能由一个电源供电。

（5）电压质量：

3.2 目标函数的模糊处理

虽然改造成本可转化为与投资成本相同量纲，但是两者的重要程度在规划人员或决策者心目中是不一样的，实际上，考虑全局优化的投资最小的规划结果往往占有较重要的地位。但是，如果投资成本过大，方案合理性会降低；同样，对于一个现有网络，如果改造规模过大，规划人员或决策者会不太愿意接受这样的结果。因此，考虑到规划人员或决策者的判断能力，目标函数可通过隶属度函数来表示：

式中：和Fi分别是模型的第i个目标函数的下限和当前目标值。从式中可见，为使Fi达到最小值，在式（5-7）中转变为使Fi达到最大值。

4. 基于改进单亲遗传算法的配电网扩展规划

已知变电站位置、容量和供电范围，给定负荷变压器的个数、位置及大小，按规划到用户（负荷）的思想[13]，布线目的是把整个规划区中的所有变压器联结起来，在辐射性、连通性、电压损耗等约束条件下进行优化规划，同时确定导线型号。本文主要在编码、变异、修补染色体三方面做了改进。

4.1 编码方式

由于配网开环运行,每个节点只有一个父节点：假设配网中有N个节点（编号从1到N，变电站编号为0），建立一个N阶方阵，元素为0、1两种取值，用方阵来描述该网络拓扑。方阵的列号与节点号相同，如第一列对应节点1，第二列对应节点2，依次类推。矩阵元素的取值含义如下：矩阵元素为“1”则相连，表示该元素对应的列节点，是对应行一节点的子节点；为“0”则不相连。父节点记录在一个列向量b(N)中（第一个元素始终为0，即表示该父节点是变电站）；b(N)中的其他元素是方阵中矩阵元素为1对应的列节点编号（即节点编号），逐行按其出现的先后顺序形成的。将b(N)记录在矩阵的左侧，与矩阵的行对应。b(1)为0，表示矩阵第一行的父节点是变电站。如方阵第1行中元素a1m为1代表节点m与新建的变电站直接相连（即m是b(1)的子节点）；a3n为1表示节点n是b(3)的子节点。

例如某网络有4个负荷点，接线示意图如图5-2，图5-3为该图对应的矩阵表示（b(N)在矩阵左侧），其中1、3号负荷直接与变电站相连，2、4号负荷点与1号负荷点相连，列向量b(N)是由方阵中为1的元素对应的列号逐行按出现的先后次序形成的（b(1)为0）。第一行为1的列号为1、3，则b(2)、b(3)为1、3，依次形成，直到b(N)。图5-3矩阵的b(N)为{0，1，3，2}。

采用方阵中每列为1的元素所在的行数为优化变量（染色体基因），用遗传算法来优化馈线网络。如图5-2的染色体为{1，2，1，2}。

4.2 遗传算子设计

如前文所述，本算法的遗传操作仅由选择和变异算子构成，其中选择操作采用赌方式，适应度大的以较大概率进入下一代，最优个体直接进入到下一代。

算法的变异操作则结合本文所探讨的配网网架结构优化问题的特点，采用两种基因突变方式。该变异操作实际上相当于顶点突变和顶点换位，从而保证了算法的收敛。

第一种为交换变异：首先确定要进行交换变异的两个基因，然后交换它们。例如对于图5-3表示的染色体{1，2，1，2}，若交换变异的基为1和3，则进行交换变异后为{1，3，1，3}。

第二种为插入变异：首先确定要变异的位，搜索其可变异的行号集合，然后在该集合中随机选择完成突变。例如对于图5-3表示的染色体{1，2，1，2}，若变异的位为3（该位值为1），则可供变异的值（行号）集合为{2，4}。

由于变异会造成不可行解，必须在突变时加以控制。本算法采用修补染色体[22]的方式：首先将染色体解码，找到以该变异点为父节点的所有节点；对于第一种变异，只将顶点交换后重新编码；对于第二种变异，将该父节点的所有节点随着原父节点移到新的父节点下，然后重新编码。以第二种变异的修补过程为例：对于图5-3表示的染色体{1，2，1，2}，变异位为1（该位值为1），其变异后的值为3，则修补后的染色体为{2，3，1，3}。这样，经修补后，不可行解理论上不会出现，保证了变异操作后方案的可行性，同时又保持了种群多样性，加快了收敛。

本算法与常规遗传算法在计算流程上是一样的（图3-1），只是在遗传操作这一步骤中，本算法中没有杂交算子，同时采用了特殊定义的变异算子，并经过修补以保证变异后方案的可行性。

4.3 其他部分的设计

1 初始种群的产生

为防止算法的过早收敛并保证搜索的全局性，采用随机初始化的方案，随机产生馈线条数，馈线首个负荷点从距离变电站较近的负荷点集合中产生，按“就近原则”将其余负荷点分配给各条馈线。

2 适应度计算

本文仅讨论单一水平年的配电网规划问题即静态规划，在优化过程中不计及网损：

染色体的适应度取公式（5-8）的倒数，为防止适应度过小，可乘以常数A：

本算法与常规遗传算法在计算流程上是一样的（图3-1），只是在遗传操作这一步骤中，本算法中没有杂交算子，同时采用了特殊定义的变异算子，并经过修补以保证变异后方案的可行性。