基于遗传算法的配电网优化课件

1、学号：S100301001姓名：陈诚导师：朱伟基于遗传算法的配电网优化规划1 遗传算法简介 遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局 优化概率搜索方法。 它最早由美国密西根大学的H.Holland教授提出，起源于60年代对自然和人工 自适应系统的研究； 1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（ Genetic Algorithm）”一词。 70年代 De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化 计算实验。 在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。

2、1.11遗传算法概要： 在遗传算法中将n维决策向量Xx1,x2,xnT用n个记号Xi(i=1,2,n)所组成的符号串X来去示： Xxlx2xn Xx1，x2， ,xnT 把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个 染色体。 这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的 一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可 表示为一个二进制符号串。 这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。 对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应 的个体表现型X的目标函数值相

3、关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。 遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个 体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类 似，遗传算法的运算过程也是一个反复迭代过程： 第t代群体记做 P(t)， 经过一代遗传和进化后，得到 t+1 代群体，记做 P(t+1), 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应 度较高的个体更多地遗传到下一代，这样最

4、终在群体中将会得到一个优良的个体 X，它所对应的表现型X将达到或接近于问题的最优解X*。1.1.2 遗传策法的运算过程选择(复制)： 根据各个个体的适应度，按照一 定的规则或方法，从第t代群体P(t) 中选择出一些优良的个体遗传到下 一代群体P(t+1)中；交叉： 将群体P(t)内的各个个体随机搭配 成对，对每一对个体，以某个概率 (称为交叉概率）交换它们之间的 部分染色体；变异： 对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某 一个或某一些基因座上的基因值为其他基因值。实际问题参数集编码群体t计算适值运算：复制 交叉 变异群体t+1满足要求？解码改善或解决实际问题群体t+1群

5、体tYN1.1.3 遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。 例：求下述二元函数的最大值： max f(x1,x2)=x12+x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种 符号串。本题中，用无符号二进制整数来表示。 因 x1, x2 为 0 7之间的整数，所以分别用3位无符号二进制整数来表示，将它 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可 行解。 例如，

6、基因型 X101110 所对应的表现型是：x 5，6 。 个体的表现型x和基因型X之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始 群体数据。 本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机 方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。 (4) 选择运算 选择运

7、算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是： 先计算出群体中所有个体的适应度的总和 fi ( i=1.2,M ); 其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传 到下一代群体中的概率， 每个概率值组成一个区域，全部概率值之和为1； 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。0124%24%17%35%1#2#

8、3#4#个体编号初始群体p(0)适值占总数的百分比总和1234011101101011011100111001343425500.240.240.170.351431选择次数选择结果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 1(5) 交叉运算 交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某 两个个体之间的部分染色体。 本例采用单点交叉的方法，其具体操作过程是： 先对群体进行随机配对； 其次随机设置交叉点位置； 最后再相互交换配对染色体之间的部分基因。选择结果01 110111 10011010 111110 01配对

9、情况交叉点位置个体编号12341-23-41-2：23-4：4交叉结果011001 111101101001111011 可以看出，其中新产生的个体“111101”、“111011”的适应度较原来两个个体 的适应度都要高。(6) 变异运算 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进 行改变，它也是产生新个体的一种操作方法。 本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是： 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置， 其中的数字表示变异点设置在该基因座处； 然后依照某一概率将变异点的原有基因值取反。对群体P(t)进行一轮选择、交叉

10、、变异运算之后可得到新一代的群体p(t+1)。个体编号1234交叉结果011001 111101101001111011变异结果变异点4526011101 111111111001111010子代群体p(1)011101 111111111001111010 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得 到了明显的改进。事实上，这里已经找到了最佳个体“111111”。 注意 需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题， 我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中 有可能需要一定的循环次数才能达到这个最优结果。个体编号子

11、群体p(1)适值占总数的百分比总和1234011101 111111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 2个体编号初始群体p(0) 适值fi(x1,x2)占总数的百分比fi / f1234011101101011011100111001343425500.240.240.170.35 x1 x2 3 5 5 3 3 4 7 1fi=143fmax=50f=35.75选择结果011101111001101011111001配对情况交叉点位置1-23-41-2：23-4：4交叉结果011001 111101101

12、001111011选择次数1102变异结果变异点4526011101 111111111001111010子代群体p(1) 适值fi(x1,x2)占总数的百分比fi / f011101 111111111001111010349850530.140.420.210.23 x1 x2 3 5 7 7 7 1 7 2fi=253fmax=98f=58.752.配电网网架优化问题配电网网架优化渉及到馈线段建设时间、建设地点和线径等的最优选择，以满足负荷增长的需求，同时服从馈线容量、电压降落、网络结构、可靠性等约束。因此，网架优化是一个大规模的组合优化问题。常规的数学优化方法很难在合理的时间内得到问题

13、的最优解，而遗传算法不是对函数和它们的控制变量直接操作，所以不受函数约束条件的限制，能以较大的概率找到全局最优解。2.1网架优化模型2.11 目标函数此模型中计及资金的时间价值，安等额分付资本回收计算，一年费用最小为目标函数为： （1）式中 Z为方案的线路建设投资费用， 为方案第t年的运行费用。当以水平年为目标时，设电气设备的使用寿命n为25a，贴现率i为0.1，并假定使用年限内运行费用相等，则式（1）细化为 式（2）如下： 2.12约束条件a. 辐射网结构。B. 电压降落限制C. 负荷要求，AP=D式中 A为节点关联弧矩阵，P为网络潮流，D为负荷要求。d. 线路潮流限制，式中 为支路潮流，

14、为满足某种条件的支路最大允许容量。2.2 编码策略及初始解的产生采用常规二进制编码策略，将新建可行线路的投运与否作为优化变量（投运为1，否则为0）。有随机产生的备选网络的生成树替代常规遗传算法随机产生的初始解作为遗传算法的初始解。生成树的算法如下：属于一个连通图的顶点的集合称为桶。初始状态，所有各线条路都未标记，定义的若干个桶也都是空的。第一步任意选择一条线路。将它的两个端点放入同一空桶内，并标记该线路。第二部任意选择一条未标记的线路（如果没有这样的线路，则算法停止），判断两端点是否都在同一桶内。若是，返回第二步；否则，标记该线路，转向第三步。第三步若两端点中的一个在桶内，另一个不在，将不在桶

15、内的端点放入另一个端点所在桶内；若两端点在不同的桶内，将两桶合并，使另一个成为空桶。如果图的所有顶点都在一桶内，则所有已标记的线路构成一个生成树，算法停止。否则，返回第二步。2.3适应值计算遗传算法搜索的目标是找到适应值最大的解。右图为适应值的计算框图。染色体解码检查网络的连接结构和辐射条件是否辐射网交流潮流功率是否越限压降是否越限适应值=f（功率损耗，电压降，投资）适应值=g(与电源相连的负荷节点数)适应值=h(功率越限数目)适应值=v（压降越限数目）NYYYNN2.4遗传算子的设计2.4.1 选择 应用竞争法则，每次按一定概率从群体中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体中，体现自然界优胜劣汰的思想。 2.4.2 杂交 采用单点杂交，即随机地在两个父染色体上选择一个杂交点，仅交换该点对应基因。因为原有父染色体均对应辐射形网络，经上述随机杂交后，辐射形结构可能被破坏，因此，需区别不同的情况进行处理：