改进的遗传算法在汕头电网规划中的应用

>　　黄武忠¹钟丹虹²孔德键³吴捷²



自适应代沟遗传算法电网规划
1电网规划
　　电网规划问题由于其离散性、非线性、大规模以及有众多与政治、经济、社会因素相关的约束等原因，一直未能得到很完满的解决。所谓电网规划，就是确定在何时、何地建设何种类型的电源和输变电设施，以取得最安全经济的电能输送效益。从数学上来讲，它是一个求最优解的问题，其数学表达式为：
目标函数C


这是一个典型的有约束的最优化问题，其离散性表现为线路建设与否是整型变量，非线性表现为规划所必须的潮流约束本身是非线性的，大规模则表现为决策变量数量较多。对这一最优化问题的求解，传统上有启发式和数学优化两大类型的方法^［1］。
　　启发式方法概念明确，计算量小，但只能给出次优解而非最优解。数学优化方法有线性规划法、非线性规划法、混合整数规划法等，研究者采用最优化理论中的各种数学方法，对多阶段、多目标、不确定等情况下的电网规划问题进行了探讨并取得不少成果。数学优化方法原理严格，但用于电网规划存在三大缺陷：一是电网规划的复杂性很难用数学模型精确模拟，模拟越精确求解越困难，以致难以实用，若采取简化处理又可能丢失最优解；二是当求解问题不是数学上的凸规划问题时，其单路径能得到一个最优解，而在实际工作中，规划人员往往除最优解外还希望得到一批次优解。
2改进的遗传算法
2.1简单遗传算法
　　遗传算法是由自然界生物遗传机理抽象出来而形成的一种新型优化算法。其计算过程是：首先将实际优化问题编码成符号串，也称染色体，将实际问题的目标函数转变成染色体的适应度函数，然后在随机产生一批初始染色体基础上，根据各染色体的适应度函数进行繁殖、交叉及变异等遗传操作，产生下一代染色体。适应度函数值的大小决定了该染色体被繁殖的概率，它反映了适者生存的原理，交叉和变异操作通过随机和结构化地交换各染色体之间的信息而可能产生更优秀的染色体。这样，经过逐代遗传，产生出一批适应函数值很高的染色体，最后将这些染色体解码还原就可以获得原问题的解。当染色体域足够大、遗传代数足够多时，理论上讲，遗传算法一定可以逼近原问题的最优解。
　　遗传算法在电力系统中的应用研究已有了数年历史，在电力系统经济运行、网络分割、故障诊断、电力系统控制等方面，研究者运用遗传算法取得了不同程度的结果。而在电网规划中，遗传算法的应用虽然起步不久，但相对于其他领域的研究更为全面和深入^［2～5］，这是由于电网规划本身就是一个优化问题，遗传算法可以直接应用其中。遗传算法用于电网规划有其独特的优点。如前文所述，电网规划在应用传统优化方法中遇到离散性、非线性、高维数、多约束、多目标等困难，遗传算法本身的优点可以较好地解决这些问题。因为二值编码符合最小字符集的编码规则，通常采用较多的是二值编码，而二值编码正好对应于电网规划中有整型变量的要求，这使得求解过程中编码和译码都比较方便，不存在连续优化方法中因舍入而存在的误差问题。
　　遗传算法对目标函数的要求很宽松，不需要导数等辅助信息，这使得电网规划的非线性、多约束、多目标的求解难度降低。实际上，各种约束以函数的形式，各种目标以多目标处理方式计入目标函数后，增加的工作量只是在适应度函数的计算上，遗传算法的整个操作过程没有受到大的影响。遗传算法的搜索结果在给出最优解的同时给出一批次优解，十分适合于规划人员根据其他难以计入模型的因素进行取舍，得到符合实际的最优解。此外遗传算法的全局优化能力、对高维系统的搜索能力也是比其他方法优越之处。虽然从原理上遗传算法可以收敛到全局最优解，但在实际应用中遗传算法仍存在未成熟收敛、收敛于局部最优解、收敛速度慢等问题。简单遗传算法采用世代替换方式，它对许多问题有效。但是，理论上已经证明，简单遗传算法可能发现全局最优解、但不能保证每次都收敛于全局最优解。究其原因，主要是简单的遗传算法发现的全局最优解不能保持。
2.2改进措施
　　影响遗传算法性能的因素，可以归结为以下四类：参数选择与初始化，进行遗传操作产生后代，种群评估和最优个体选择，终止条件判断。这些因素对遗传算法的影响集中在两大方面：优化结果和计算时间。如何对这些因素进行最合适的选取或调整，使遗传算法发挥出最佳性能，是当前遗传算法研究和应用的一个重点。
　　寻求特定领域的高性能遗传算法，往往需要对算法作一些特殊调整使之适应具体问题的特殊要求，包括采用适合求解问题的特殊技术，适合这些技术的参数设置，以及结合问题要求的特殊操作因子等。在汕头电网规划中运用遗传算法时，我们针对求解过程中存在的未成熟收敛和收敛速度慢的问题，对形成新一代群体的方法进行改进，取得了较好的结果。改进的措施如下：
　　对于某一代群体，通过选择、交叉、变异的遗传操作后，就产生了新的个体———子代。子代是否完全代替父代继续下面的遗传操作是一个值得研究的问题。现有的替代方式可以分为父代全部被子代取代的世代替换方式、保留一个最好的父串的最佳保留方式、按一定比例更新群体中部分个体的代沟方式以及子代和父代同等看待的代际综合方式。在运用遗传算法进行电网规划时，同样遇到收敛于局部解、收敛速度慢的问题。要解决这一问题，必须对算法本身进行改进。
　　改进的方案是加入最优保存操作，数学已证明，只要保留最优方案，遗传算法一定能收敛到全局最优解。但是，在寻求最优方案的过程中，还会出现收敛于局部最优方案的现象。要跳出局部最优解需增大变异率并花费大量时间。这与上述新群体形成方法所采用的都是代沟固定的方法有关。当代沟固定时，无论某一代所产生的好的染色体是多还是少，其被保留到下一代的个数都一样。
　　新群体形成的四种方法，实际上可以统一为代沟方法。其中对于世代替换方法,代沟G＝1；对于后三种方法，0＜G＜1，每一代的代沟都是固定的。最近，研究遗传算法的学者提出了自适应代沟的替代策略，其特点是代沟不再固定而随着计算过程动态变化，若子代中有较多个体比父代的适应度高，则该代的代沟就大，有更多的父代被替换，反之则父代保留较多。这种方法实质上是从父子两代中选取最好的个体组成下一代，使每一代中的优秀个体被聚集到一起，通过交叉操作，优秀的基因有较大机会组合在一起形成更优解甚至最优解。由于遗传算法每一代产生的更好解的个数是不确定的，因此人为地规定保留解的个数，将导致在某些代中好解被丢失，搜索过程变长。自适应代沟使代沟的形成过程根据每一代的情况而定，提高了遗传算法的自适应程度，经用测试函数检验证实它能提高遗传算法的搜索效率。
3应用实例
3.1数学模型
　　在汕头电网规划中，采用了遗传算法对网架的优化规划进行求解，目标函数与式(1)相同，约束条件为


式中　B———系统导纳矩阵；
B_L———线路导纳矩阵；
θ———各节点的相角向量；
P———各节点的注入功率向量；
P_L———线路潮流向量；
P_Lm———线路允许最大电流向量值；
θ_L———线路两端的电压相角差。
　　“N－1”安全准则：任一条线路开断时系统不出现过负荷。
通常采用遗传算法得出的各种优化方案的运行费用差异较小，故目标函数可简化为只计投资费用。
3.2操作步骤
运用遗传算法求解上述模型的步骤如下：
　　a）准备必要数据。在求解最优网架之前需要知道确定建设的变电站站址，待选线路的电阻、电抗、允许热稳定极限、长度、投资等参数；并需有规划年份各站的负荷和各电源的出力。
　　b）编码。对方案的所有决策变量进行编码。
在遗传算法中每一个网络方案对应于一个染色体。采用整数编码，每条待选线路对应于一个基[1][2]下一页