改进遗传模拟退火算法

改进遗传模拟退火算法在配电网络重构中的应用 刘扬, 杨建军, 魏立新(大庆石油学院, 大庆 163318)摘要:对遗传模拟退火算法中的交叉、变异操作进行了改进，并实施了最优保留策略，形成了改进遗传模拟退火算法。以网损最小为目标函数，以配电网电压降的限制、线路电流量的限制等为约束条件，建立了配电网络重构优化模型。在考虑配电网自身特点的基础上，利用改进遗传模拟退火算法求解。重构算例说明，该优化方法有效、实用。关键词: 配电网络; 网络重构; 遗传算法; 模拟退火 Application of the Improved Genetic Simulated Annealing Algorithmin Distribution 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 annealing algorithm were improved, and the optimized reserved strategy was used to form the improved genetic simulated annealing algorithm. An optimization model of distribution network reconfiguration is established, in which the minimum network loss is taken as objective function, the restrictions to the decline of voltage and current are taken as constraint conditions. Based on the features of distribution network, the improved genetic simulated annealing algorithm is used in network reconfiguration. Reconfiguration results show that the algorithm is efficient and practical.Key words: distribution network; network reconfiguration; genetic algorithm; simulated annealing 1前言网络重构作为配电系统经济运行自动控制的一个重要问题已被广泛关注。网络重构的基本原理就是在满足系统约束条件的前提下，通过调整网络中分段开关和联络开关的分合来寻求一种符合某特定运行要求（如使网损最小）的拓扑结构。理论上，在各种约束条件下，配电网络重构问题是一个大规模非线性组合优化问题。由于配电网中作为优化变量的开关数目巨大，穷举搜索将面临“组合爆炸”问题。近年来，模拟退火算法和遗传算法在配电网络重构中得到了应用，但单一算法的搜索能力和效率不高，而且受初始参数的影响较大。遗传算法参数选择不当易陷入“早熟”，模拟退火算法对“退温”历程的限制条件很苛刻，优化时间性能较差。本文将遗传算法和模拟退火算法有效结合起来，并对遗传算法的适应函数、交叉率和变异率进行了改进，计算过程考虑了配电网自身的特点，使算法的优化性能得到了大幅度提高。2网络重构数学模型以网损最小为目标函数的网络重构数学模型为式中：PLi为第i段线路的有功损耗，kW；N为线路总数量；Ri为线段i的单位电阻，；Li为线段i的长度，km；Pi为第i线路的有功潮流，kW；Qi为第i线路的无功潮流，kvar；Ui为第i线路的电压值，kV。不等式约束包括电压降的约束、线路电流值约束、电源容量约束1，即式中：Uimin为第i节点要求的最低工作电压值，kV；Iimax为第i线路导线型号对应的载流量值，A；St为第t个变电所的负荷值，kVA；Stmax为第t个变电所的供电能力，kVA。此外，还应保证每组开关组合不形成环网和出现“孤岛”的情况，即每次循环中遍历的节点个数应等于整个网络的负荷节点总数。3改进遗传模拟退火算法及其在配电网络重构中的应用3.1编码在遗传算法中，问题的解用数字串来表示，每个数字串叫做一个染色体，遗传算子也是直接对串进行操作。遗传算法常用的有十进制编码和二进制编码。配电网络重构的实质就是通过改变开关的开合状态来改变网络的拓扑结构，目的是找到最优的网络结构所对应的开关状态，以使网损降到最小。因此，取开关状态为控制变量比较合适，将网络中的开关状态自然地用0或1表示（0表示开，1表示合），每个开关占据染色体的一位，各开关状态组合在一起，就形成了一条染色体，染色体的长度为网络中开关的数量总和。这种方案简洁明了，而且无需二进制与十进制之间的相互转换，节省了计算时间。3.2产生初始种群随机产生pop-size个长度为l（l为网络中开关数量的总和）的二进制编码，作为初始种群。为了让初始种群遍及整个解空间，尽量反映搜索空间的性态，pop-size不能取太小，且随节点数的增多而变大，不过太大会使运算时间增加。由于配电网具有闭环设计开环运行的特点，开关状态的组合应保证网络处于开环运行状态，同时保证每个负荷的供电，即不形成孤岛。因此在配电网潮流计算程序中应加入搜索判断程序，将不符合实际运行条件的个体去掉。3.3初温的确定及退温操作初温选择t0=K的形式，其中：K为充分大的数，可以选K=10，20，100，等试验值；=fsmax-fsmin，fsmax为初始种群中最大的目标函数值，fsmin为初始种群中最小的目标函数值。退温函数选用常用的tk+1=tk形式，其中01。 3.4适应函数的确定适应函数值是遗传算法指导搜索方向的依据，首先应保证适应函数值不为负。其次，因为在轮盘赌选择过程中，适应函数值大的染色体被选中的概率大，因此目标函数的优化方向对应适应函数值增加的方向。网络重构的目标函数是网损最小，属于最小值优化问题，应加以调整。其变换方式如下2式中：f(i)为染色体对应的目标函数值；fmin为当前代进化群体中最小的目标函数值；t为温度参数。这是一个非常好的加速适应函数，当温度较高时加速性不明显，当温度较低时加速性非常明显，这正是我们所需要的。3.5终止规则因为按上面的适应函数形式，每代计算出的最大适应函数值均等于1，不发生变化，所以应通过监控每代进化群体中最小目标函数值fmin的变化情况来判断算法是否终止。当连续q代没有发生变化时，即可认为算法收敛，此时停止计算。3.6遗传算法的选择复制根据适应函数值的大小进行群体选择，选择方法采用常用的轮盘赌选择法，但为了保证算法能够收敛到全局最优解，实施了最优保留策略。即将中间群体中性能最好的个体无条件地复制到下一代群体中，这样就会保留中间群体中的最好解，使算法可以以概率1收敛到全局最优解，保证了算法的收敛。3.7基因操作交叉、变异在优化时发现，即使对于同一个问题，交叉率Pc和变异率Pm取值不同也会产生不同的结果。目前，常用方法是Pc、Pm依经验取固定值，一般Pc0.25，0.95，Pm0.005，0.1，具有一定的盲目性。Srinivas等人提出了Pc、Pm随适应函数值自动改变（adaptive）的方法3，主要思想是根据种群的进化情况来动态地调整交叉率Pc和变异率Pm，以达到克服过早收敛及加快搜索速度的目的。根据其原理，本文建立的表达式如下 式中：k1、k2为常数，具体值根据实际情况确定；favg为当前代进化群体的平均目标函数值；f为两个交叉个体中目标函数值较小的一个。在操作过程中，适应函数值小的个体，具有较大的交叉率和变异率，这样有利于加快搜索速度。当遗传算法陷入问题的局部极值时，即favgfmin时，根据式（6）和（7），适应函数值较大的个体对应的Pc、Pm也将增大，这样有利于避免“早熟”。但太大的Pc、Pm有可能造成解空间过于分散，甚至可能导致原有的解被破坏。为此，一旦fmin-favg时，就固定Pc、Pm值，以避免原有解空间被完全破坏。同时，在基因操作时，为了不破坏配电网络的辐射运行状况以及不形成孤岛，变异需成对进行，设选中了某染色体的某一位进行变异，如0变1，与此同时，必须将该染色体中与该位相邻二进制码为1的位变成0，反之亦然。这样操作可以大量避免不可行解的产生，极大地提高了计算效率。3.8基于Metropolis判别准则的复制策略以经过遗传算法选择复制、交叉、变异操作的群体作为初始群体，运用基于Metropolis判别准则的复制策略，产生下一代群体。基于Metropolis判别准则的复制策略可分为两步：1.实施最优保留策略。2.实施Metropolis判别准则的复制策略。即在染色体i的邻域中随机产生新个体j，i和j竞争进入下一代群体的准则，采用Metropolis判别准则，令f=f(xj)-f(xi)，若f0，则把xj复制到下一代群体,否则产生0，1之间的随机数r。如果rexp(f/tk)，则同样把xj复制到下一代群体，否则把xi复制到下一代群体。基于Metropolis判别准则的复制策略，一方面保证中间群体中的最优个体进入下一代，另一方面在接受优化解外，有限度地接受劣质解，保证了群体的多样性，避免陷入局部最优解。3.9改进遗传模拟退火算法的计算过程Step 1给定群体规模popsize，和算法中其它系数值，具体如下：选择初温时的系数K；退温时的系数；交叉和变异操作时的系数k1、k2；和终止规则中的q；令迭代次数n=0。Step 2随机产生popsize个染色体作为初始种群pop(0)，计算各染色体的目标函数值，确定初温，令初始最优解，并令p=0。Step 3计算出染色体的适应函数值，采用轮盘赌方法进行群体选择，同时实施最优保留策略。Step 4重新计算染色体的目标函数值，按交叉概率Pc执行遗传算法的交叉操作，同时实施最优保留策略。Step 5重新计算染色体的目标函数值，按变异概率Pm执行遗传算法的变异操作，同时实施最优保留策略。Step 6执行基于Metropolis判别准则的复制策略，产生下代群体pop(n+1)。Step 10判断p是否大于或等于q，如果是，则以s*作为最终解输出，并停止计算。否则，返回Step3。下面给出改进遗传模拟退火算法的结构流程图，见图1。4算例根据本文算法，用C+Builder5.0编制了网络重构程序，并以喇嘛甸油田6kV配电系统中的喇十四变电所、喇三变电所以及喇十二变电所间的部分配电线路（如图2）为例进行了试算。此系统共有338条线段，129台变压器，26个开关。计算时染色体长度l等于开关数26，群体规模pop-size取60，算法中各系数确定如下：选择初温时系数K=20，退温时的系数=0.8，交叉和变异操作时的系数k1=0.8，k2=0.2，当fmin-favg0.05fmin时，交叉率和变异率固定为0.6和0.05，算法终止判断条件中q=20。优化结果见表1，从优化结果中可以看到，不但配电网网损率降低了1.7%，而且配电网末端电压质量得到了明显改善。5结论本文探讨了如何利用改进遗传模拟退火算法来进行网络重构优化，以减少网损。改进遗传模拟退火算法的混合策略是一个两层并行搜索结构，其优化性能，尤其是避免陷入局部极小的 能力，得到了提高。其优化过程包含了遗传算法的复制、交叉、变异和模拟退火算法的状态 产生函数等不同的邻域搜索结构，从而增强了算法在解空间中