遗传模拟退火算法

1、改进遗传模拟退火算法在配电网络重构中的应用岸刘扬，杨建军，魏立新（大庆石油学院，大庆163318）摘 要:对遗传模拟退火算法中的交叉、变异操作进行了改进，并实施了最 优保留策略，形成了改进遗传模拟退火算法。以网损最小为目标函数，以配电网 电压降的限制、线路电流量的限制等为约束条件，建立了配电网络重构优化模型。 在考虑配电网自身特点的基础上，利用改进遗传模拟退火算法求解。重构算例说 明，该优化方法有效、实用。关键词：配电网络；网络重构；遗传算法；模拟退火Application of the Improved Genetic Simulated Annealing Algorithm in Dis

2、tribution Network ReconfigurationLIU Yang, YANG Jianjun, WEI Lixin(Daqing Petroleum Institute, Daqing 163318,China)Abstract:In the paper, the crosser and mutation in the genetic simulated annea ling algorithm were improved, and the optimized reserved strategy was used to form the improved genetic si

3、mulated annealing algorithm. An optimization model of distri bution network reconfiguration is established, in which the minimum network loss is taken as objective function, the restrictions to the decline of voltage and curren t are taken as constraint conditions. Based on the features of distribut

4、ion network, the improved genetic simulated annealing algorithm is used in network reconfigurat ion. Reconfiguration results show that the algorithm is efficient and practical.Key words: distribution network; network reconfiguration; genetic algorithm; s imulated annealing1刖言网络重构作为配电系统经济运行自动控制的一个重要问

5、题已被广泛关注。网 络重构的基本原理就是在满足系统约束条件的前提下，通过调整网络中分段开关 和联络开关的分合来寻求一种符合某特定运行要求（如使网损最小）的拓扑结构。理论上，在各种约束条件下，配电网络重构问题是一个大规模非线性组合优 化问题。由于配电网中作为优化变量的开关数目巨大，穷举搜索将面临“组合爆 炸”问题。近年来，模拟退火算法和遗传算法在配电网络重构中得到了应用，但 单一算法的搜索能力和效率不高，而且受初始参数的影响较大。遗传算法参数选 择不当易陷入“早熟”，模拟退火算法对“退温”历程的限制条件很苛亥U，优化 时间性能较差。本文将遗传算法和模拟退火算法有效结合起来，并对遗传算法的适应函数

6、、 交叉率和变异率进行了改进，计算过程考虑了配电网自身的特点，使算法的优化 性能得到了大幅度提高。2网络重构数学模型以网损最小为目标函数的网络重构数学模型为 TOC o 1-5 h z mm/ =字.L 写工H）式中： PLi为第i段线路的有功损耗，kW； N为线路总数量；Ri为线段i的单 位电阻，。；L为线段i的长度，km； P为第i线路的有功潮流，kW； Q为第i iii线路的无功潮流，kvar； Ui为第i线路的电压值，kV。不等式约束包括电压降的约束、线路电流值约束、电源容量约束，即心5式中：Uimin为第i节点要求的最低工作电压值，kV； Iimax为第i线路导线型号对 应的载流量值

7、，A； St为第t个变电所的负荷值，kVA； Stmax为第t个变电所的供 电能力，kVA。此外，还应保证每组开关组合不形成环网和出现“孤岛”的情况，即每次循 环中遍历的节点个数应等于整个网络的负荷节点总数。3改进遗传模拟退火算法及其在配电网络重构中的应用3.1编码在遗传算法中，问题的解用数字串来表示，每个数字串叫做一个染色体，遗 传算子也是直接对串进行操作。遗传算法常用的有十进制编码和二进制编码。配 电网络重构的实质就是通过改变开关的开合状态来改变网络的拓扑结构，目的是 找到最优的网络结构所对应的开关状态，以使网损降到最小。因此，取开关状态 为控制变量比较合适，将网络中的开关状态自然地用0或

8、1表示（0表示开，1 表示合），每个开关占据染色体的一位，各开关状态组合在一起，就形成了一条 染色体，染色体的长度为网络中开关的数量总和。这种方案简洁明了，而且无需 二进制与十进制之间的相互转换，节省了计算时间。3.2产生初始种群随机产生pop-size个长度为1（1为网络中开关数量的总和）的二进制编码， 作为初始种群。为了让初始种群遍及整个解空间，尽量反映搜索空间的性态，P op-size不能取太小，且随节点数的增多而变大，不过太大会使运算时间增加。 由于配电网具有闭环设计开环运行的特点，开关状态的组合应保证网络处于开环 运行状态，同时保证每个负荷的供电，即不形成孤岛。因此在配电网潮流计算程

9、 序中应加入搜索判断程序，将不符合实际运行条件的个体去掉。3.3初温的确定及退温操作初温选择t0=K6的形式，其中：K为充分大的数，可以选K=10，20，100， 等试验值；6=fsmax-fsmin，fsmax为初始种群中最大的目标函数值，fsmin为初始种群 中最小的目标函数值。退温函数选用常用的tk+1=a tk形式，其中0Va V1。3.4适应函数的确定适应函数值是遗传算法指导搜索方向的依据，首先应保证适应函数值不为负。其次，因为在轮盘赌选择过程中，适应函数值大的染色体被选中的概率大， 因此目标函数的优化方向对应适应函数值增加的方向。网络重构的目标函数是网 损最小，属于最小值优化问题，

10、应加以调整。其变换方式如下式中：f(i)为染色体对应的目标函数值；fmin为当前代进化群体中最小的目标 函数值；t为温度参数。这是一个非常好的加速适应函数，当温度较高时加速性 不明显，当温度较低时加速性非常明显，这正是我们所需要的。3.5终止规则因为按上面的适应函数形式，每代计算出的最大适应函数值均等于1，不发 生变化，所以应通过监控每代进化群体中最小目标函数值fmin的变化情况来判断 算法是否终止。当连续q代没有发生变化时，即可认为算法收敛，此时停止计算。 3.6遗传算法的选择复制根据适应函数值的大小进行群体选择，选择方法采用常用的轮盘赌选择法， 但为了保证算法能够收敛到全局最优解，实施了最

11、优保留策略。即将中间群体中 性能最好的个体无条件地复制到下一代群体中，这样就会保留中间群体中的最好 解，使算法可以以概率1收敛到全局最优解，保证了算法的收敛。3.7基因操作一交叉、变异在优化时发现，即使对于同一个问题，交叉率Pc和变异率Pm取值不同也会 产生不同的结果。目前，常用方法是P、P依经验取固定值，一般P 0.25, c mc0.95，Pme0.005，0.1，具有一定的盲目性。Srinivas等人提出了 P、P随适应函数值自动改变(adaptive )的方法， 主要思想是根据种群的进化情况来动态地调整交叉率Pc和变异率Pm，以达到克 服过早收敛及加快搜索速度的目的。根据其原理，本文建

12、立的表达式如下虹一 /i.un （虹一 /i.un （/ min.I k-.（7）式中：k、k为常数，具体值根据实际情况确定；f为当前代进化群体的平均目12avg标函数值；f为两个交叉个体中目标函数值较小的一个。在操作过程中，适应函数值小的个体，具有较大的交叉率和变异率，这样有 利于加快搜索速度。当遗传算法陷入问题的局部极值时，旺皿一fmin时，根据式 (6)和(7)，适应函数值较大的个体对应的七、Pm也将增大，这样有利于避免 “早熟”。但太大的Pc、廿有可能造成解空间过于分散，甚至可能导致原有的 解被破坏。为此，一旦I f -f 1时，就固定P、P值，以避免原有解空 min avgc m间被

13、完全破坏。同时，在基因操作时，为了不破坏配电网络的辐射运行状况以及不形成孤岛， 变异需成对进行，设选中了某染色体的某一位进行变异，如0变1，与此同时， 必须将该染色体中与该位相邻二进制码为1的位变成0，反之亦然。这样操作可 以大量避免不可行解的产生，极大地提高了计算效率。3.8基于Metropolis判别准则的复制策略以经过遗传算法选择复制、交叉、变异操作的群体作为初始群体，运用基于 Metropolis判别准则的复制策略，产生下一代群体。基于Metropolis判别准则 的复制策略可分为两步：实施最优保留策略。实施Metropolis判别准则的复制策略。即在染色体i的邻域中随机产生 新个体j

14、，i和j竞争进入下一代群体的准则，采用Metropolis判别准则，令 f=f(x)-f(x)，若 f颈，则把x复制到下一代群体，否则产生0，1之间jij的随机数r。如果rE Ihc dhlrjhulkm nrtwirkH i 幅壕虻优帏后辫比蠢Tib. Ilahk of sACrm Endilhw bvfckrr and jflrr bplinkiution配电X物手供围牝kw配电m时bi宰配电阡+册最大成序耽十的汗性佣为林归的Jf美ks.Kl.Kii.ki 顽“曲、hl ,K,KW.K部l.K .Kl KJ.KE,K?,Kll,(tit 喘mm1,2L*邱Kr.4算例根据本文算法，用C+B

15、uilder5.0编制了网络重构程序，并以喇嘛甸油田6k V配电系统中的喇十四变电所、喇三变电所以及喇十二变电所间的部分配电线路 （如图2）为例进行了试算。此系统共有338条线段，129台变压器，26个开关。计算时染色体长度l等于开关数26,群体规模pop-size取60，算法中各系 数确定如下：选择初温时系数K=20，退温时的系数a =0.8，交叉和变异操作时 的系数k=0.8，k=0.2，当If -f l0.05f时，交叉率和变异率固定为0.12min avgmin6和0.05,算法终止判断条件中q=20。优化结果见表1，从优化结果中可以看到， 不但配电网网损率降低了 1.7%，而且配电网

16、末端电压质量得到了明显改善。5结论本文探讨了如何利用改进遗传模拟退火算法来进行网络重构优化，以减少网 损。改进遗传模拟退火算法的混合策略是一个两层并行搜索结构，其优化性能， 尤其是避免陷入局部极小的能力，得到了提高。其优化过程包含了遗传算法的 复制、交叉、变异和模拟退火算法的状态产生函数等不同的邻域搜索结构，从 而增强了算法在解空间中的探索能力和效率。它的搜索行为是可控的。即通过 退温历程（即初温、退温函数）加以控制，控制初温，可控制算法的初始搜索 行为。控制温度的高低，可控制算法突跳能力的强弱。高温下的强突跳性有利于 避免陷入局部极小，低温下的趋化性寻优有利于提高局部搜索能力。控制温度 的下降速率，可控制突跳能力的下降幅度，影响搜索过程的平滑性。由此可见， 在优化机制、结构和行为上，改进遗传模拟退火算法的混合优化策略均结合了 遗传算法和模拟退火算法的特点，两种算法的搜索能力得到相互补充，使该算 法在优化能力、效率和可靠性方面得到了提高。参考