基于多种群遗传算法的输电系统扩展规划叶在福　单渊达摘　要：在简要介绍标准遗传算法（SGA）的基础上，详细分析了造成遗传算法未成熟收敛的原因，提出了一种多种群遗传算法结构（MPGA）。将这一方法应用于输电系统扩展规划，可以大大降低遗传控制参数的不当设定对规划结果的影响，对抑制未成熟收敛的发生有明显的效果，同时可以给出最优和若干次优规划方案。通过两个不同规模的算例，证明了该方法的有效性。
关键词：电力系统；输电系统扩展规划；遗传算法；未成熟收敛
分类号：TM715；TP18ANEWTRANSMISSIONNETWORKEXPANSIONPLANNINGBASEDON
MULTIPLE-POPULATIONGENETICALGORITHMYeZaifu,ShanYuanda
(SoutheastUniversity,Nanjing210096,China)Abstract：Afterabriefdiscussionaboutstandardgeneticalgorithm(SGA),thispaperanalyseswhyprematureconvergenceiscausedbygeneticalgorithm.Thenanewtransmissionnetworkexpansionplanningbasedonmultiple-populationgeneticalgorithm(MPGA)ispresented,inwhichtheMPGAisdesignedtocopewiththecausesofprematureconvergence.Usingthismethod,theinfluenceofimpropergeneticcontrolparametersonplanningresultcanbegreatlydecreasedandprematureconvergencecanbeovercomeeffectively.TwopracticalapplicationsofthismethodprovethatMPGAiseffective.
Keywords：powersystems;transmissionnetworkexpansionplanning;geneticalgorithm;prematureconvergence▲0　引言　　输电系统扩展规划是在已知规划水平年的电源规划和负荷预测的基础上，根据现有的电网结构，合理地选择新建线路以满足安全运行和经济性最优。从数学上讲，输电系统扩展规划是一个带有大量等约束和不等约束的非线性整数规划问题。除传统的规划方法外，近年来，遗传算法作为一种智能优化方法，在电力系统电网规划、无功优化、经济调度、故障诊断、配网重构等领域都得到了广泛的应用^［1～5］。遗传算法虽然简单、通用，但算法本身客观存在的未成熟收敛问题一直没有得到很好解决。针对这一问题，本文对遗传算法进行了扩展，提出了一种多种群的算法结构，并用于输电系统扩展规划。1　输电系统扩展规划的数学模型　　输电系统扩展规划的目标是在满足运行可行性和运行安全性的前提下，求取经济性最优的规划方案，其目标函数可描述为：　(1)其中　C_i为新建线路的单位综合造价；L_i为新建线路的长度；N_L为新建线路总数；P_LOSS为规划方案在指定运行方式下的总网损；Y_LIM为抵偿年限；τ为最大损耗小时数；p为规划水平年的单位发电成本。
　　规划方案的运行可行性应满足功率平衡方程：　(2)　　安全性则要求任一电气元件在正常运行方式下不过载：　(3)其中　T_ij为电气元件在正常运行方式下承载的有功功率，包括线路和变压器支路。2　遗传算法及未成熟收敛问题2.1　遗传算法
　　遗传算法是一种启迪于生物界自然选择和自然遗传机理的并行优化搜索方法，它能在搜索过程中自动获取和积累对解空间的认识，并自适应地控制搜索过程以求得最优解。和其他优化方法相比，其优越性主要表现在：①优化计算时不依赖于梯度信息，不要求目标函数连续和可导；②以群体搜索代替单点搜索，强调群体中个体之间的信息交换，在搜索过程中不易陷入局部最优，尤其适合于处理传统搜索方法难以解决的大规模、非线性组合优化问题^［6］。
　　求解问题时，遗传算法从一初始化的群体出发，以适应度函数为依据，通过对群体中的个体不断施加选择、交叉、变异等遗传操作，实现个体之间的信息交换和结构重组，使群体品质不断提高并逐渐逼近全局最优解。其主要计算流程如下。
　　a.参数编码：将待求问题的变量表示成适于遗传算法求解的码串形式；
　　b.生成初始群体：设定遗传计算的起点；
　　c.计算个体适应度值：评价个体优劣程度；
　　d.对群体中的个体施加遗传操作：按优胜劣汰的原则生成子代群体；
　　e.计算子代个体的适应度值：评价子代个体的优劣程度；
　　f.如果满足算法终止条件，则停止计算并输出问题的优化解，否则，以子代群体代替父代群体后转入步骤d。
　　具有以上结构的遗传算法称为标准遗传算法（standardgeneticalgorithm，简称SGA）。
2.2　产生未成熟收敛问题的原因
　　未成熟收敛是遗传算法中不可忽视的现象，主要表现在群体中的所有个体都趋于同一状态而停止进化，算法最终不能给出令人满意的解。未成熟收敛的发生主要和下列几个方面有关：
　　a.选择操作是根据当前群体中个体的适应度值所决定的概率进行的，当群体中存在个别超常个体时（该个体的适应度比其他个体高得多），该个体在选择算子作用下将会多次被选中，下一代群体很快被该个体所控制，群体中失去竞争性，从而导致群体停滞不前。
　　b.交叉和变异操作发生的频度是受交叉概率P_c和变异概率P_m控制的。P_c和P_m的恰当设定涉及遗传算法全局搜索和局部搜索能力的均衡，进化搜索的最终结果对P_c，P_m的取值相当敏感，不同的P_c，P_m取值很可能会导致不同的计算结果。
　　c.群体规模对遗传算法的优化性能也有较大的影响：当群体规模较小时，群体中多样性程度低，个体之间竞争性较弱，随着进化的进行，群体很快趋于单一化，交叉操作产生新个体的作用渐趋消失，群体的更新仅靠变异操作来维持，群体将很快终止进化；当群体规模取值较大时，势必造成计算量的增加，计算效率受到影响。
　　d.遗传算法常用的终止判据是：当迭代次数到达人为规定的最大遗传代数时，则终止进化。如迭代次数过少，进化不充分，也会造成未成熟收敛。
　　为克服未成熟收敛，许多学者对算法改进进行了一些有益的探索，特别对遗传控制参数的设定，提出了自适应的交叉和变异，并获得了一些有益的结论。但是，遗传算法的未成熟收敛与上述诸多因素有关，在应用遗传算法解决实际问题时，控制参数如何设定，遗传算子如何设计往往是根据实际问题试探性地给出，不恰当的设定会在很大程度上影响算法的性能。3　克服未成熟收敛的MPGA算法　　针对遗传算法所存在的上述问题，一种多种群遗传算法结构模型（multiple-populationGA，简称MPGA）可以用来取代常规的标准计算模型^［7］。
　　MPGA在SGA的基础上主要引入了以下几个概念：
　　a.突破SGA仅靠单个群体进行遗传进化的框架，引入多个种群同时进行优化搜索；不同的种群赋以不同的控制参数，实现不同的搜索目的。
　　b.各个种群之间通过移民算子进行联系，实现多种群的协同进化；最优解的获取是多个种群协同进化的综合结果。
　　c.通过人工选择算子保存各种群每个进化代中的最优个体，并作为判断算法收敛的依据。
　　MPGA的算法结构如图1所示。图1　MPGA的算法结构示意图
Fig.1　StructurediagramofMPGA　　图1中，种群1～种群3的进化机制都是常规的SGA，采用赌轮选择、一点交叉和位点变异。在求解输电系统规划问题时采用了逐线编码，即每一回待选线路均用一位二进制表示，“1”表示该线路被选中加入系统，“0”则反之。
　　各种群的搜索目的是不同的。前文已提及，交叉概率P_c和变异概率P_m的取值决定了算法全局搜索和局部搜索能力的均衡。在SGA中，P_c，P_m取较大值时，算法侧重于全局搜索，而导致局部细化搜索能力不足；P_c，P_m取较小值时，算法局部搜索能力得以增强，但[1][2][3]下一页