基于遗传算法的机组组合问题的建模与求解基于遗传算法的机组组合问题的建模与求解摘要摘要本文针对当前科技水平不足以有效存储电力的情况下产生的发电机机组组合的问 题，考虑负荷平衡、输电线传输容量限制等实际情况产生的约束条件，建立机组组合 优化模型，追求发电成本最小。同时采用矩阵实数编码遗传算法（MRCGA）和穷举搜 索算法，利用 MATLAB 7.0.1 和 C+编程，分别对模型进行求解，并对所得结果进行 分析比较，以此来帮助电力部门制定机组启停计划。 首先，建立发电成本最小目标函数和各项约束条件的数学表达式。其中机组空载 成本和增量成本之和随该机组发电出力增长呈折线关系，在分析计算时为了简便，本 文采用一条平滑的二次曲线来近似代替。 对于问题 1，选取相应的约束条件对目标函数进行约束，从而给出优化模型。由 于问题 1 的求解规模很小，所以采用穷举搜索算法，利用 C+编程求解，得到了 3 母 线系统 4 小时的最优机组组合计划（见表一） 。 对于问题 2，在优化模型的基础上，增加最小稳定运行出力约束、机组启动和停 运时的出力约束以及机组最小运行时间和最小停运时间约束这三个约束条件，建立了 优化模型 II。同时采用遗传算法和穷举搜索算法，利用 MATLAB 和 C+编程，分别对 模型进行求解，部分结果如下： 发电总成本（单位：元）矩阵实数编码遗传算法6780 穷举搜索算法6820 在对所得结果进行了分析比较，重新制定了 3 母线系统 4 小时最优机组组合计划 （见表三） 。 对于问题 3，用 IEEE118 系统对优化模型 II 进行测试。由于求解规模巨大，同样 采用遗传算法和穷举搜索算法，利用 MATLAB 和 C+编程，分别对模型进行求解，部 分结果如下： 发电总成本（单位：百 万） 矩阵实数编码遗传算法2.034 穷举搜索算法2.135 在对所得结果进行比较时发现对于大规模问题，遗传算法优势明显，将其求解结 果作为 24 小时的最优机组组合计划（见附录） 。 最后，我们就模型存在的不足之处提出了改进方案，并对优缺点进行了分析。关键字关键字 机组组合优化模型 矩阵实数编码遗传算法 穷举搜索算法1一、问题的提出一、问题的提出当前的科学技术还不能有效地存储电力，所以电力生产和消费在任何时刻都要相等，否则就会威胁电力系统安全运行。为了能够实时平衡变化剧烈的电力负荷，电力部门往往需要根据预测的未来电力负荷安排发电机组起停计划，在满足电力系统安全运行条件下，追求发电成本最小。在没有电力负荷损耗以及一个小时之内的电力负荷和发电机出力均不变的前提下，假定所有发电机组的发电成本都是由 3 部分组成:1.启动成本（Startup Cost） ，2.空载成本（No load cost） ，3.增量成本（Incremental Cost） 。需要考虑的约束有: 1负荷平衡约束 2系统备用约束 3输电线路传输容量约束 4发电机组出力范围约束 5机组增出力约束 6机组降出力约束。问题问题 1：3 母线系统母线系统有一个 3 母线系统，其中有 2 台机组、1 个负荷和 3 条输电线路，已知 4 个小时的 负荷和系统备用要求。请求出这 4 个小时的最优机组组合计划。最终结果应该包括总 成本、各小时各机组的状态、各小时各机组的发电出力和各小时各机组提供的备用。G1 L Bus 2 Bus 1 Bus 0 G2 Line 0-1 Line 0-2 Line 1-2 问题问题 2：3 母线系统母线系统在问题 1 的基础上，考虑发电机组的下列物理特性约束:1.发电机组的稳定出力范 围约束 2.机组启动时的出力约束 3.机组停运时的出力约束 4.机组最小运行时间约束 5. 机组最小停运时间约束。重新制定最优机组组合计划。问题问题 3：IEEE 118 系统系统用 IEEE118 节点的电力系统对问题 2 的求解模型进行测试，试求出 24 个小时的 最优机组组合计划。最终结果应该包括总成本、各小时各机组的状态、各小时各机组 的发电出力和各小时各机组提供的备用。 二、问题的分析二、问题的分析机组优化组合和优化启停就是要在满足约束条件的情况下，优化地选定各时段参 加运行的机组，求出机组的最佳运行方案，实现发电成本最小。 然而，机组组合问题是一个多变量、多约束的混合整数非线性规划问题。针对此 类问题的求解，数学类优化方法如线性规划、非线性规划、动态规划等，都存在明显 不足之处。而采用智能优化算法对此问题的研究较多，主要包括遗传算法、模拟退火 算法、禁忌搜索、人工神经网络、模糊优化等算法。其中模拟退火算法收敛速度慢、2禁忌搜索算法对初始解依赖性较强、人工神经网络算法存在网络合适的隐含层数目和 节点数目难以确定、模糊优化方法的隶属函数和模糊推理规则的确定较困难。鉴于遗 传算法作为一种新的全局 优化搜索算法，以其简单通用、鲁棒性强、适于并行处理 及应用范围广等显著特点，本文采用基于矩阵实数编码遗传算法来解决机组组合问题。可以将整个问题分为以下两个任务来完成： 一、建立机组组合问题的数学模型 二、采用穷举搜索法和遗传算法，利用 C+或者 MATLAB 编程，求解模型，得到 最优机组组合计划 由于题目中的三个问题所考虑的约束条件复杂程度不同，发电机组数与负荷情况 也不相同，本文将三个问题逐一建立模型并求解： 问题问题 1 根据负荷平衡、系统备用、输电线路传输容量、发电机组出力范围、机组增出力、 机组降出力等约束建立优化模型 I，采用穷举搜索算法，利用 C+编程进行求解。 问题问题 2 和问题和问题 3 在问题 1 的基础上，增加机组启动和停运时的出力、机组最小运行时间和最小停 运时间约束条件，建立了优化模型 II，采用穷举搜索法和遗传算法，分别利用 C+和 MATLAB 编程进行求解。三、模型假设和符号系统三、模型假设和符号系统3.1 模型假设模型假设1. 假设系统不存在电力负荷损耗2. 假设一个小时之内的电力负荷和发电机出力均不变3. 假设参加交叉运算的染色体个数占全体染色体总数的比例为 0.40.994. 假设发生变异的基因位数所占全体染色体的基因总位数的比例为 0.00010.13.2 符号系统符号系统为机组 在 时段的运行状态，ituit10itu ，表示运行，表示停机为机组 的启动成本iSi为机组 在 时段的发电成本itfit为机组 在 时段的出力；itpit为负荷在 时段的负荷量；jtLjt为发电机组 的最大出力；maxipi3为 时段系统备用要求；tRt为线路上流过的电能；linekplinek为第根输电线路第 条母线的线性传输因子；klxkl为母线 上的注入功率；,inj buslpl为第根输电线路的最大传输容量；maxkp发电机组最小稳定运行出力；minip为机组 最大减出力；diri为机组 最大增出力；riri为机组 最小运行时间；1 iTi为机组 最小停运时间；2iTi四、模型的建立与求解四、模型的建立与求解4.1 模型建立分析模型建立分析4.1.1 先考虑目标函数先考虑目标函数1)空载成本和增量成本 观察空载成本和增量成本构成的部分成本随该机组发电出力变化特性图，如图 一中折线所示。图一 空载成本和增量成本之和随该机组发电出力增长走势图4在分析计算时为了简便，通常用一条平滑曲线来近似代替有起伏的部分成本特 性，如图一中平画曲线所示。当 n 段直线近似表示时，部分成本特性可表示为（1）2 ititiitiitifpapb pc2)启动成本（2）11itii tuuS其中：为机组 在 时段的运行状态，ituit10itu ，表示运行，表示停机为机组 的启动成本iSi3)目标函数 机组组合的目的是针对在指定的周期内，满足系统负荷、备用容量、机组最小 时间和最小停机时间等限制，优化确定各机组的启停机计划和优化分配其发电负荷， 使发电总费用最小。因此，要以机组的费用最小为依据建立相应的目标函数。 设所研究的计划周期为，机组台数为，则该问题的目标函数可以表示为:Tn（3）1 11min1Tnititititii t tiFu fpuuS 其中：为机组 在 时段的发电成本itfit4.1.2 再考虑约束条件再考虑约束条件1)负荷平衡约束 任何时段，电力负荷之和必须等于发电机发电出力之和。（4）11nmititjt iju pL其中：为机组 在 时段的运行状态，；ituit10itu ，表示运行，表示停机为机组 在 时段的出力；itpit为负荷在 时段的负荷量；jtLjt2)系统备用约束 任何时段，发电机的备用容量之和必须大于系统备用要求。（5）max 1nitiitt iuppR其中：为发电机组 的最大出力；maxipi为 时段系统备用要求；tRt53)输电线路传输容量约束 线路传输的电能必须在它的传输容量范围内。（6）,max 0Nlinekklinj buslk lpx pp 其中：为线路上流过的电能；linekplinek为第根输电线路第 条母线的线性传输因子；klxkl为母线 上的注入功率；,inj buslpl为第根输电线路的最大传输容量；maxkp4)发电机组出力范围约束与稳定出力范围约束 处于运行状态的发电机组的发电出力必须小于其最大发电出力，同时必须大于 其最小稳定运行出力。（7）minmaxiitippp其中：发电机组最小稳定运行出力；minip5)机组增降出力约束 发电机组在增加发电出力时，增加出力的速度要小于其最大增出力；发电机组 在减少发电出力时，减少出力的速度要小于其最大减出力。（8）111diitrii trppr 其中：为机组 最大减出力；diri为机组 最大增出力；riri6)机组启动和停运时的出力约束 当机组从停运状态变为运行状态时，机组在该小时的发电出力必须为其最小稳 定运行出力，且当机组从运行状态变为停运状态时，机组在该小时的发电出力必须 为其最小稳定运行出力。（9）min11itiititi ti tppuuuu如果=0且=1；或=1且=07)机组最小运行时间和最小停运时间约束 机组每次启动后，连续运行时间至少为该台机组的最小运行时间。机组每次停 运后，连续停运时间至少为该台机组的最小停运时间。（10）11111ititijii ti t j t TuuuuT （11）21211itititijii t j t TuuuuT 6其中：为机组 最小运行时间；1 iTi为机组 最小停运时间；2iTi4.24.2 模型及其求解模型及其求解问题问题 11）优化模型优化模型问题 1 中的 3 母线系统仅考虑负荷平衡约束 系统备用约束、输电线路传输容 量约束、发电机组出力范围约束与稳定出力范围约束和机组增降出力约束，所建优 化方程模型如下。（12）1 11min1Tnititititii t tiFu fpuuS . st（13）11max 1,max 0max1. .1101nmititjt ijnitiit iNlinekklinj buslk litidiitrii titu pLuppRstpx pppprppru 为或者其中：为机组 在 时段的发电成本；itfit2 ititiitiitifpapb pc为机组 的启动成本；iSi2)优化模型优化模型的求解算法的求解算法机组组合问题在数学规划上属于 NP 完全问题，任何 NP 完全问题只有通过列举所 有可能的组合，才能得到最优解，即采用穷举搜索法。由于问题 1 的求解规模不大， 所以该问题将采用穷举搜索法对模型进行求解。我们设置一计数器（）用T1 2