基于退火演化算法和遗传算法

基于退火演化算法和遗传算法的机组优化组合算法吴金华，吴耀武，熊信艮（华中科技大学电力工程系，湖北省武汉市430074）摘要：机组组合问题是编制短期发电计划时首先要解决的问题，合理的开停机方案将带来很大的经济效益。现代电力系统对机组优化组合算法的收敛速度和解的质量要求越来越高，作者从改善传统算法这两方面着手，根据退火演化算法和遗传算法各自的特点，提出了一种用于机组优化组合的组合算法。与传统的一些优化算法相比，该组合算法具有搜索速度快，收敛性好，而且解的质量相当高。通过对实际系统的测算，验证了该方法的有效性和优越性。该方法具有良好的并行性，易于在并行计算机上实现。关键词：机组优化组合；退火演化算法；遗传算法；电力系统；并行计算1引言电力系统的机组组合问题，就是在满足系统负荷及备用要求和机组运行的技术条件约束的情况下，确定未来一定期间内各机组的开停机时间并在机组间分配负荷，使系统总的运行费用达到最小。合理的开停机方案能节省一次能源，延长机组使用寿命，带来巨大的经济效益。据国外资料和国内部分机组的实际测算表明，优化组合是编制短期发电计划首先要解决的问题，一般而言，其经济效益远大于负荷经济分配所得到效益。从数学的角度来讲，机组组合问题是一个高维的、非凸的、离散的混合整数非线性优化问题。当系统规模较大时，很难找出理论上的最优解。由于它能够带来显著的经济效益，人们一直在积极研究和开发各种算法来解决这个问题，如优先顺序法、分支定界法、动态规划法和拉格朗日松弛法等[1-4]。近年来，对专家系统法、遗传算法、模拟退火法、人工神经网络及一些组合算法[9]也进行了一些尝试。在研究基本遗传算法和退火演化算法的基础上，本文提出了一种适合于机组组合的组合算法[9]。在计算过程中，对遗传算法的适应度函数、杂交及变异方式作了一些改进，有效地避免了简单遗传算法在机组组合问题中的早熟问题，并且提高了收敛速度。2机组组合问题的数学模型设系统调度期间的时段数为H，系统中机组或等效机组数为G，各时段系统总负荷为PDt，则其数学描述如下（1）目标函数式中Fit(Pit)为t时段i机组的运行费用；STi为i机组的启停费用；△STi为i机组的停运时间；Uit为i机组在时段t内的状态，Uit=1为运行状态，Uit=1为停运状态；Pit为机组i在时段t内的有功功率。（2）机组组合的约束条件在机组组合的过程中，主要的约束条件为1）电力平衡约束2）单机约束式(2)～(4)中Ct为系统在时间t的网损；PDt为时间t系统总负荷；k为备用系数；Mi为i机组在计算周期内允许启停的次数；为i机组的上、下限出力；△i为i机组每时段可加减负荷的最大值；TOi为i机组的最小运行时间；为i机组的最小停运时间。本文中发电机组的运行费用采用发电功率的二次函数表示，即式中ai、bi、ci为常数。机组的启停费用有两种模型（1）冷却启动式中K3为压火运行一小时的费用。本文中将网损作为常数处理，即按总负荷的一定比例（7％）考虑。更详细的模型应包括线路潮流限制、分区功率平衡、机组的燃料限制和随机停运的影响等，但本文模型未考虑这些因素。3遗传和退火演化组合算法及其改进3.1基本遗传算法及其改进遗传算法（GA）是一种基于生物界自然选择和自然遗传机制的随机化搜索算法。在随机产生的一个初始解群中利用适应度函数衡量各个解的优劣，根据“优胜劣汰”的准则选出父辈解群，通过杂交和变异操作来实现群体内个体结构的重组，使群体内个体一代一代得以优化并逐渐逼近全局最优解。本文所提出的算法，在保留了GA算法的基本步骤和特点的同时，作了如下几点改进。（1）适应度函数比例变换为了避免遗传算法在搜索初期易产生的“早熟”现象和搜索结束阶段易产生的随机漫游现象，本文对适应度函数进行了指数比例变换式中F为原适应度函数；F'为变换后的适应度函数，β为比例调整系数。系数β的值决定选择的强制性[2]，在搜索初期，赋给β一个较小值，来缩小一些超常个体的函数值以降低异常个体的竞争力；在结束阶段，则赋给β一个相对较大值，来放大相应的适应度函数值来提高个体的竞争力。（2）杂交概率和变异概率可变在迭代前期，采用较大的杂交概率和较小的变异概率，以提高繁殖效率；在迭代后期，解群中的码链已趋于稳定，此时交叉作用已经减小，杂交概率可降低，而为了防止收敛于局部最优解，可增大变异概率。本文借鉴了文献[7]采用的杂交概率和变异概率变化公式（3）网络式遗传操作为了保证算法收敛的稳定与快速，采用了一种网络式遗传操作，即在一个总的遗传算法中采用了多个子遗传操作。由于技术限制，本文在算例中仅采用了两个子遗传操作，在两个子算法中分别采用不同的杂交、变异方式，形成两个不同的新解群。3.2退火演化算法及其与遗传算法结合退火演化算法（AEA）是模拟退火算法（SA）的一种改进算法。为了改善搜索过程，避免落入局部最优，基于群体和选择的思想，退火演化算法（AEA）采用了一种新的演化策略，即通过变异和选择不断改善一个解的群体，而不是象普通模拟退火算法那样采取单点迭代方式，从而大大减小了陷入局部极小的概率，并且可导致快速收敛到全局极小值。本组合算法的基本思想就是：算法首先从一个包含N个点的初始群体出发，在每个冷却步上，用遗传算法作为退火演化算法产生新解的规则，设有L个子遗传操作用来产生新解，这些新解分别采用Metropolis接受准则被接受或舍弃；经过一个冷却步后，群体规模则增加到包含N´L个点，按照与这些点的适应值成比例的概率从中选择N个个体作为生存集；如果最好的点不在生存集中，则从N个点中随机舍弃一个点，然后把最好的点加入其中，算法再在一个降低的控制参数下重复上述过程。遗传算法会在每一代中不断产生新解，用退火演化算法对这些新解群进行检验和改善。随着计算次数的增加，温度逐渐降低，接受恶化解的概率逐渐减小，遗传算法寻优朝着更有效的方向进行，由此大大改善了遗传算法的收敛性。4组合算法用于机组组合（1）编码方法采用二进制码表示机组对应状态Uit，对于有G台机组，H个时段的情况，一个串长为L=H´G的串就表示了系统在一个调度周期内的机组组合状态，在各时段上进行负荷经济分配之后，得到机组一天的运行情况。（2）约束处理对于功率平衡约束和旋转备用约束，采用罚函数法以构成增广函数，适应度函数取为增广函数的倒数。而对各种单机约束则采用硬约束，即当超出约束条件时，直接将适应值置零。（3）收敛判据本文在算法迭代的结果满足以下两个条件之一时结束：1）适应度最大值大于某一个值且连续若干代所获得的最优解没有变化，则认为解已成熟收敛；2）迭代次数超过某一个规定的限值。（4）算法流程1）读入系统和机组的参数，初始化GA、AEA的参数，令迭代次数：k=0；2）产生初始解群，计算各染色个体的适应值；3）每一冷却步，利用GA为AEA产生L个新解，每个子GA算法中分别进行不同遗传操作，采用Metropolis接受准则对新解进行检验，保留优良个体。若满足了收敛判据，则转入5），否则进入4）；4）AEA算法改善整个解群。转入4），改变控制参数；5）得到并输出最优解。5算例结果及分析取控制参数：群体规模N=80；=0.900；＝0.001；选择策略：R=E；最大迭代次数：Max=100；初始温度：T=1000K；温度系数：ɥ=0.96。对实际算例进行了测算，限于篇幅，算例原始数据未列出。算例1：文献[6]的10机系统，利用本组合算法测算，迭代38次，结果如表1所示，计算出运行耗量为78673t标准煤；启动耗量为260t标准煤。总耗量为78933t标准煤。较文献[6]利用拉格朗日松弛法测算结果节省2.834％（2305t标准煤，其迭代60次）。较文献[7]利用一般遗传算法测算结果节省1.095％（874t标准煤）。算例2：文献[8]的61机系统，其中18台可调。利用本组合算法计算出总耗量27100t标准煤，较文献[5]和文献[8]利用改进遗传算法测算结果节省0.892％（244t标准煤）。算例结果表明，本文所提出的组合方法是有效的，迭代次数少，进行机组优化组合的解质量也相当高。本文采用的退火演化算法，采用解群迭代来替代单个点的迭代，明显减少了陷入局部极小的概率，并且可快速收敛到全局极小值，而且退火演化算法实际上可以视为模拟退火算法的并行执行。本文采用的网络式遗传操作，使得该方法易于在并行计算机上应用，可使优化速度得到很大提高，可望应用于实际电力系统的经济运行。参考文献[1]侯煦光，等（HouXuguangetal）．电力系统最优规划（Powersystemoptimization）[M]．武汉：华中理工大学出版社（HuazhongUniversityofScienceandTechnologyPress），1991．[2]康立山，等（KangLishanetal）．非数值并行算法,第一分册,模拟退火算法（Non-numericalparallelalgorithms—simulatedannealingalgorithm）[M].北京:科学出版社（SciencePress），1994．[3]刘勇，等（LiuYongetal）．非数值并行算法，第二分册，遗传算法（Non-numericalparallelalgorithms—geneticalgorithm）[M]．北京：科学出版社（SciencePress），1995．[4]陈皓勇，王锡凡（ChenHaoyong,WangXifan）．机组组合问题的优化方法综述（Asurveyofoptimization-basedmethodsforunitcommitment）[J]．电力系统自动化（AutomationofElectricPowerSystem），1999，23(4)．[5]韦柳涛，曾庆川，等（WeiLiutao，ZengQingchuanetal）．启发式遗传基因算法及其在电力系统机组组合优化中的应用（Anewhenristicgeneticalgorithmanditsapplicationinsolutionoftheunitcommitment）[J]．中国电机工程学报（ProceedingoftheCSEE），1994，14(2)．[6]韩学山，等（HanXueshanetal）．考虑发电机组输出功率速度限制的最优机组组合（Optimalunitcommitmentconsideringunit’sramp-ratelimits）[J]．电网技术（PowerSystemTechnology），1994，18(2)．[7]蔡超豪，蔡元宇（CaiChaohao，CaiYuanyu）．机组优化组合的遗传算法（Optimizationofunitcommitmentbygeneticalgoritm）[J]．电网技术（PowerSystemTechnology），1997，21(1)．[8]刘青松（LiuQingsong）．改进遗传算法确定发电机组的优化组合（Optimalgeneratingunitcommitmentbyimprovedgeneticalgo-rithm）[J].电网技术（PowerSystemTechnology）[J]，1998，22(12)．[9]KimH，YasuhiroH，KoichiN．AnalgorithmforthermalunitmaintenanceshedulingthroughcombineduseofGASAandTS[J]．IEEETransonPWRS.，1997，12(1)．