基于遗传算法的机组组合问题的建模与求解word格式.doc

《基于遗传算法的机组组合问题的建模与求解word格式.doc》由会员分享，可在线阅读，更多相关《基于遗传算法的机组组合问题的建模与求解word格式.doc（24页珍藏版）》请在三一办公上搜索。

1、基于遗传算法的机组组合问题的建模与求解摘要本文针对当前科技水平不足以有效存储电力的情况下产生的发电机机组组合的问题，考虑负荷平衡、输电线传输容量限制等实际情况产生的约束条件，建立机组组合优化模型，追求发电成本最小。同时采用矩阵实数编码遗传算法（MRCGA）和穷举搜索算法，利用MATLAB 7.0.1和C+编程，分别对模型进行求解，并对所得结果进行分析比较，以此来帮助电力部门制定机组启停计划。首先，建立发电成本最小目标函数和各项约束条件的数学表达式。其中机组空载成本和增量成本之和随该机组发电出力增长呈折线关系，在分析计算时为了简便，本文采用一条平滑的二次曲线来近似代替。对于问题1，选取相应的约束

2、条件对目标函数进行约束，从而给出优化模型。由于问题1的求解规模很小，所以采用穷举搜索算法，利用C+编程求解，得到了3母线系统4小时的最优机组组合计划（见表一）。对于问题2，在优化模型的基础上，增加最小稳定运行出力约束、机组启动和停运时的出力约束以及机组最小运行时间和最小停运时间约束这三个约束条件，建立了优化模型II。同时采用遗传算法和穷举搜索算法，利用MATLAB和C+编程，分别对模型进行求解，部分结果如下：发电总成本（单位：元）矩阵实数编码遗传算法6780穷举搜索算法6820在对所得结果进行了分析比较，重新制定了3母线系统4小时最优机组组合计划（见表三）。对于问题3，用IEEE118系统对优

3、化模型II进行测试。由于求解规模巨大，同样采用遗传算法和穷举搜索算法，利用MATLAB和C+编程，分别对模型进行求解，部分结果如下：发电总成本（单位：百万）矩阵实数编码遗传算法2.034穷举搜索算法2.135在对所得结果进行比较时发现对于大规模问题，遗传算法优势明显，将其求解结果作为24小时的最优机组组合计划（见附录）。最后，我们就模型存在的不足之处提出了改进方案，并对优缺点进行了分析。关键字 机组组合优化模型 矩阵实数编码遗传算法 穷举搜索算法一、问题的提出当前的科学技术还不能有效地存储电力，所以电力生产和消费在任何时刻都要相等，否则就会威胁电力系统安全运行。为了能够实时平衡变化剧烈的电力负

4、荷，电力部门往往需要根据预测的未来电力负荷安排发电机组起停计划，在满足电力系统安全运行条件下，追求发电成本最小。在没有电力负荷损耗以及一个小时之内的电力负荷和发电机出力均不变的前提下，假定所有发电机组的发电成本都是由3部分组成:1.启动成本（Startup Cost），2.空载成本（No load cost），3.增量成本（Incremental Cost）。需要考虑的约束有: 1负荷平衡约束2系统备用约束3输电线路传输容量约束4发电机组出力范围约束5机组增出力约束6机组降出力约束。问题1：3母线系统有一个3母线系统，其中有2台机组、1个负荷和3条输电线路，已知4个小时的负荷和系统备用要求。请

5、求出这4个小时的最优机组组合计划。最终结果应该包括总成本、各小时各机组的状态、各小时各机组的发电出力和各小时各机组提供的备用。问题2：3母线系统在问题1的基础上，考虑发电机组的下列物理特性约束:1.发电机组的稳定出力范围约束2.机组启动时的出力约束3.机组停运时的出力约束4.机组最小运行时间约束5.机组最小停运时间约束。重新制定最优机组组合计划。问题3：IEEE 118系统用IEEE118节点的电力系统对问题2的求解模型进行测试，试求出24个小时的最优机组组合计划。最终结果应该包括总成本、各小时各机组的状态、各小时各机组的发电出力和各小时各机组提供的备用。 二、问题的分析机组优化组合和优化启停

6、就是要在满足约束条件的情况下，优化地选定各时段参加运行的机组，求出机组的最佳运行方案，实现发电成本最小。然而，机组组合问题是一个多变量、多约束的混合整数非线性规划问题。针对此类问题的求解，数学类优化方法如线性规划、非线性规划、动态规划等，都存在明显不足之处。而采用智能优化算法对此问题的研究较多，主要包括遗传算法、模拟退火算法、禁忌搜索、人工神经网络、模糊优化等算法。其中模拟退火算法收敛速度慢、禁忌搜索算法对初始解依赖性较强、人工神经网络算法存在网络合适的隐含层数目和节点数目难以确定、模糊优化方法的隶属函数和模糊推理规则的确定较困难。鉴于遗传算法作为一种新的全局 优化搜索算法，以其简单通用、鲁棒

7、性强、适于并行处理及应用范围广等显著特点，本文采用基于矩阵实数编码遗传算法来解决机组组合问题。可以将整个问题分为以下两个任务来完成：一、 建立机组组合问题的数学模型二、 采用穷举搜索法和遗传算法，利用C+或者MATLAB编程，求解模型，得到最优机组组合计划由于题目中的三个问题所考虑的约束条件复杂程度不同，发电机组数与负荷情况也不相同，本文将三个问题逐一建立模型并求解：问题1根据负荷平衡、系统备用、输电线路传输容量、发电机组出力范围、机组增出力、机组降出力等约束建立优化模型I，采用穷举搜索算法，利用C+编程进行求解。问题2和问题3在问题1的基础上，增加机组启动和停运时的出力、机组最小运行时间和最

8、小停运时间约束条件，建立了优化模型II，采用穷举搜索法和遗传算法，分别利用C+和MATLAB编程进行求解。三、模型假设和符号系统3.1 模型假设1. 假设系统不存在电力负荷损耗2. 假设一个小时之内的电力负荷和发电机出力均不变3. 假设参加交叉运算的染色体个数占全体染色体总数的比例为0.40.994. 假设发生变异的基因位数所占全体染色体的基因总位数的比例为0.00010.13.2 符号系统为机组在时段的运行状态，为机组的启动成本为机组在时段的发电成本为机组在时段的出力；为负荷在时段的负荷量；为发电机组的最大出力；为时段系统备用要求；为线路上流过的电能；为第根输电线路第条母线的线性传输因子；为

9、母线上的注入功率；为第根输电线路的最大传输容量；发电机组最小稳定运行出力；为机组最大减出力；为机组最大增出力；为机组最小运行时间；为机组最小停运时间；四、模型的建立与求解4.1模型建立分析4.1.1先考虑目标函数1) 空载成本和增量成本观察空载成本和增量成本构成的部分成本随该机组发电出力变化特性图，如图一中折线所示。图一 空载成本和增量成本之和随该机组发电出力增长走势图在分析计算时为了简便，通常用一条平滑曲线来近似代替有起伏的部分成本特性，如图一中平画曲线所示。当n段直线近似表示时，部分成本特性可表示为 （1）2) 启动成本 （2）其中：为机组在时段的运行状态，为机组的启动成本3) 目标函数机

10、组组合的目的是针对在指定的周期内，满足系统负荷、备用容量、机组最小时间和最小停机时间等限制，优化确定各机组的启停机计划和优化分配其发电负荷，使发电总费用最小。因此，要以机组的费用最小为依据建立相应的目标函数。设所研究的计划周期为，机组台数为，则该问题的目标函数可以表示为: （3）其中：为机组在时段的发电成本4.1.2再考虑约束条件1) 负荷平衡约束任何时段，电力负荷之和必须等于发电机发电出力之和。 （4）其中：为机组在时段的运行状态，；为机组在时段的出力；为负荷在时段的负荷量；2) 系统备用约束任何时段，发电机的备用容量之和必须大于系统备用要求。 （5）其中：为发电机组的最大出力；为时段系统备

11、用要求；3) 输电线路传输容量约束线路传输的电能必须在它的传输容量范围内。 （6）其中：为线路上流过的电能；为第根输电线路第条母线的线性传输因子；为母线上的注入功率；为第根输电线路的最大传输容量；4) 发电机组出力范围约束与稳定出力范围约束处于运行状态的发电机组的发电出力必须小于其最大发电出力，同时必须大于其最小稳定运行出力。 （7）其中：发电机组最小稳定运行出力；5) 机组增降出力约束发电机组在增加发电出力时，增加出力的速度要小于其最大增出力；发电机组在减少发电出力时，减少出力的速度要小于其最大减出力。 （8）其中：为机组最大减出力；为机组最大增出力；6) 机组启动和停运时的出力约束当机组从

12、停运状态变为运行状态时，机组在该小时的发电出力必须为其最小稳定运行出力，且当机组从运行状态变为停运状态时，机组在该小时的发电出力必须为其最小稳定运行出力。 （9）7) 机组最小运行时间和最小停运时间约束机组每次启动后，连续运行时间至少为该台机组的最小运行时间。机组每次停运后，连续停运时间至少为该台机组的最小停运时间。 （10） （11）其中：为机组最小运行时间；为机组最小停运时间；4.2模型及其求解问题11） 优化模型问题1中的3母线系统仅考虑负荷平衡约束 系统备用约束、输电线路传输容量约束、发电机组出力范围约束与稳定出力范围约束和机组增降出力约束，所建优化方程模型如下。 （12） （13）其

13、中：为机组在时段的发电成本；为机组的启动成本；2)优化模型的求解算法机组组合问题在数学规划上属于NP完全问题，任何NP完全问题只有通过列举所有可能的组合，才能得到最优解，即采用穷举搜索法。由于问题1的求解规模不大，所以该问题将采用穷举搜索法对模型进行求解。我们设置一计数器（）用以记录机组已运行的时间。 读取各机组和负荷的原始数据。另。 设置机组1的第小时的出力大小（从小到大依次搜索，跨度为1），使其出力大小的变化满足增出力约束和降出力约束。 判断机组1是否满足其出力范围约束。若满足则继续下一步，否则，重复步骤2。 根据系统负荷平衡约束，求出机组2的出力大小。 判断机组2出力大小的变化和出力范围

14、是否满足增出力约束、降出力约束和出力范围约束。若满足则继续下一步，否则重复步骤2、3、4。 判断机组1和机组2是否满足系统备用约束，若满足则继续下一步，否则重复步骤2、3、4、5。 判断机组1和机组2是否满足输电线路传输容量约束，若满足继续下一步，否则重复步骤2、3、4、5、6。 判断计数器是否为4，若是则输出该种情况下两台机组各时段出力大 小，否则重复步骤2、3、4、5、6、7，另。直到所有的情况搜索完毕为止。执行完该算法，可以得到一最优机组组合计划。3)模型求解与分析我们根据上面的算法步骤，我们编C+程序（附录1），并代入各机组和负荷的初始数据。可以得到一总成本为6580￥的最优机组组合计

15、划，如表一所示：表一 3母线系统的最优机组组合计划机组G1机组G2小时1状态运行关机出力(MW)1000备用(MW)10002状态运行关机出力(MW)1300备用(MW)7003状态运行运行出力(MW)13040备用(MW)70604状态运行关机出力(MW)1400备用(MW)600总成本(￥)6580使用穷举搜索法对该问题虽然能得出结果，但其运行效率太低，不能用于求解大规模问题，且编程实现较复杂，不是一种优良的算法。问题2和问题31） 优化模型问题2和问题3的优化模型为 （14） （15）2）求解算法对于问题2和3，我们同时采用穷举搜索法和遗传算法两种算法进行求解，并将求得结果进行比较，以比

16、较两种算法的优劣。穷举搜索法的算法思想与问题1的求解算法思想一致。遗传算法的流程图如图二所示。算法开始编码确定适应值函数产生初始种群计算适应值函数适应值定标满足终止条件？解码确定最优解输出最优解算法结束选择交叉变异是否图二 遗传算法流程图矩阵实数编码遗传算法的描述： 针对机组组合问题的矩阵实数编码本文以要安排发电机组起停计划作为遗传算法中的个体，采用实数矩阵形式进行编码。其具体形式为 （16）其中： 为遗传种群中的第个个体为编码矩阵中的第行第列元素，含义为发电机组在时段的发电出力为编码矩阵中的第个列向量，含义为时段内发电机组间的负荷分配情况为编码矩阵中的第个行向量，含义为发电机组在发电计划制定

17、周期内的出力过程发电机组的运行状态取决于矩阵中元素的具体取值，即根据机组在某时段中的出力大小来确定启停状态，具体表达式为 （17） 遗传种群初始化遗传种群初始化时，按编码矩阵中列向量的顺序进行。以中为例，初始过程如下：（1）生成服从均匀分布的随机数数组 （18）其中：为在发电机组最大最小出力之间随机生成的正数（2）计算百分比系数数组 （19）其中： （3）初始化各台发电机组的出力，即初始化 （20）其中： 为负荷在时段的负荷量 个体调整方法在进行个体调整时按列向量的先后顺序进行。以个体中为例，具体调整措施如下：（1）根据机组组合问题对精度的要求，对列中的各个元素保留（2）调整列中的元素取值，使

18、其满足相应发电机组出力范围约束。其方法如下： （21）其中：为调整前发电机组在时段的发电出力为调整后发电机组在时段的发电出力为介于0、1之间的常数，本文取发电机组最小稳定运行出力；发电机组最大出力；（3）调整列中的元素取值，使其满足相应发电机组的增出力和降出力约束约束。具体如下： （22）其中：为前一步调整完成的发电机组在时段的发电出力为此步调整后的发电机组在时段的发电出力为机组最大减出力为机组最大增出力（4）调整发电机组启停状态使其满足系统备用约束。具体调整方法如下：当 时，增开发电机组，令新投入运行的发电机组发电出力为其最小出力，直至满足系统备用约束为止。其中，为时段系统备用要求（5）经过

19、上述三步调整后，列中所有元素的总和可能不等于时段中的系统总负荷。因此要进行负荷分配的调整。具体的调整办法为：当时，通过增加运行发电机组出力来满足负荷平衡约束；反之，若，则降低运行发电机组的出力。此步调整中，只能在发电机组的最大出力允许范围内进行调整，不能改变机组的运行状态。（6）算法趋于收敛时，若发电机组的出力过程不满足最小运行、停运时间约束条件，则通过调整违反约束发电机组的运行状态满足此项约束条件，即：时，延长发电机组的运行时间；时，采用将发电机组违反约束的全部停运状态转变为运行状态的方式来满足约束条件，并令相应的出力为机组的最小出力。其中：为机组最小运行时间；为机组最小停运时间； 适度函数

20、的选取采用个体调整方法后，在求解的过程中只有发电机组的最小运行、停运时间约束条件可能得不到满足。为了加快算法收敛，本文的适度函数采用如下形式： （23）其中： 为发电机组违反最小运行或停运时间约束条件时的惩罚量，本文取为机组的启动成本；为惩罚因子，本文取；为违反此项约束的次数；为正常数，本文取。其含义为：发电机组违反1次最小运行时间或停运时间约束，便以机组的倍的启动成本进行惩罚。 选择复制（1）群体中各个体的选择概率选择概率的计算公式为： （24）其中：为第个体的选择概率为第个个体，即本文中机组各个时段的发电出力（2）赌轮选择法赌轮选择法用下面的子过程来模拟： 在区间内产生一个均匀分布的随机数

21、； 若,则染色体被选中； 若, 则染色体被选中。其中称为染色体的积累概率, 其计算公式为 （25） 交叉通过在父代中选择交配个体后，将准备进行交叉操作的父代个体表示为 （26）交叉操作产生的个体记为、，保留到子代中的个体记为、。本文的交叉操作是在2个父代个体奇数列与偶数列之间进行的。具体操作过程为：（1）生成随机数；生成随机交叉位。（2）交叉操作生成个体、，其表达式为 （27）（3）对交叉生成的个体依照个体调整方法进行个体调整，然后计算出、的适度值。（4）采用局部锦标赛选择法在父代个体和交叉产生的个体间进行子代选择，具体方法如下： （28） 变异通过个体交叉后，将准备进行变异的父代个体表示为

22、（29）变异后产生的个体记为、，保留到子代中的个体记为、。本文只对某列进行变异处理。具体操作过程为：（1） 生成随机变异因子；生成随机变异时段；生成随机变异个体选择因子（2）变异后生成个体、，其表达式为 （30）（3）对变异后生成的个体依照个体调整方法进行个体调整，然后计算出、的适度值。（4）采用局部锦标赛选择法在父代个体和变异产生的个体间进行子代选择，具体方法如下： （31） 终止条件遗传算法的终止条件有两类常见条件：第一类：采用设定最大遗传代数的方法，一般可设为50代，此时就可能得出最优解。第二类：根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制。本文采用

23、第一类方法，将、个体依照个体调整方法进行个体调整，然后计算出对应的适度值，直到第代，循环迭代结束，输出最优解Tc0。3)模型求解利用穷举搜索法和遗传算法可以分别求解问题1和2。问题2利用C+程序对穷举搜索法进行实现，然后求解，所得结果如表二所示。表二 问题二穷举搜索法求解结果机组G1机组G2小时1状态运行关机出力(MW)1000备用(MW)10002状态运行运行出力(MW)11020备用(MW)90803状态运行运行出力(MW)11060备用(MW)90404状态运行运行出力(MW)10040备用(MW)10060总成本(￥)6820利用MATLAB程序对遗传进行实现，然后求解。由于遗传算法具

24、有随机性，所程序每次运行所得的结果有略微差别，我们从多次运行的解中选取总成本最小的一组机组组合计划，结果如表三所示。表三 问题二遗传算法求解结果机组G1机组G2小时1状态运行关机出力(MW)1000备用(MW)10002状态运行关机出力(MW)1300备用(MW)7003状态运行运行出力(MW)15020备用(MW)50804状态运行运行出力(MW)12020备用(MW)8080总成本(￥)6780从问题2两种算法的求解结果中我们可以发现，遗传算法的求解结果优于穷举搜索法，但遗传算法有一定的随机性，有时需多运行几次才能得到最优解。且遗传算法比穷举搜索法更容易实现。问题3利用穷举搜索法和矩阵实数

25、编码遗传算法分别求解问题3。穷举搜索法求解结果见附录三。由于矩阵实数编码遗传算法得到的成本最小值具有一定的随机性，且随算法中迭代次数的变化而变化，所程序每次运行所得的结果有略微差别。为求得更为精确的结果，我们变换迭代次数，以判断迭代多少次为最优（这里取30、50、100次的结果），见图三、四、五，详细结果见附录四、五图三 迭代30次的运行结果图四 迭代50次的运行结果图五 迭代100次的运行结果我们从多次运行的结果中选取最优机组组合计划，使用矩阵实数编码遗传算法求得的最优解为迭代次数为50次（总成本、各小时各机组的状态、各小时各机组的发电出力和各小时提供的备用）见附录五从问题3的求解结果中，通

26、过不同迭代次数之间的比较以及穷举搜索法与矩阵实数编码遗传算法的对比分析，看出矩阵实数编码遗传算法在进行大规模机组组合问题求解时，具有很强的适应性和全局搜索能力，而且系统规模越大算法的优化结果越理想。因此，矩阵实数编码遗传算法的求解结果优于穷举搜索法，但矩阵实数编码遗传算法有一定的随机性，需多运行几次才能得到最优解。六、模型的改进及评价6.1模型的改进模型改进一：机组组合优化模型I与II的改进在机组组合优化模型I、II中，通过二次函数对空载成本和增量成本曲线参数进行拟合过程中，采用二次函数拟合误差比较大（增量成本变化幅度比较小），特别是机组规模比较小的时候更是如此。鉴于此种情况，当机组规模比较大

27、时，可以采取平滑曲线进行拟合。如问题三，可以利用二次函数进行拟合，根据运行结果可以看出误差更小，机组启停更合理，发电成本更小。此外，当机组规模相对较小时，可以不进行曲线拟合，直接采取分段函数，编程求解。如问题一和二，利用C+编程，采取穷举搜索法求解，精度会更高。模型改进二：基于矩阵实数编码遗传算法的改进在矩阵实数编码遗传算法步骤中，根据实际情况（如机组规模，时段等问题）可以对各步骤进行优化或改进。如变异，本文实在时段内列向量进行的，相当于发电机组在不同时段发电出力的重新调整。因此，还可以采用多窗口变异操作【1】。此操作是在个体内行向量间进行的，相当于在不同发电机组间进行发电出力的重新调整。此法

28、具有经济负荷分配的功能，并且，由于是同时进行多个时段的负荷分配调整，故执行效率较高。当然，二者相结合，效果更佳。6.2模型的评价优点：第一，提供了一种求解多变量、多约束的混合整数非线性规划的机组组合优化问题的思路，此方法新颖可靠易行，极具参考价值。第二，采用MRCGA算法求解机组组合问题的新方法。利用二维实数矩阵对发电计划安排进行编码，将机组组合问题转化为单层优化问题进行求解，因而降低了算法的时间复杂度。运用个体调整方法处理各项约束条件，确保了优化结果的可行性，使该算法更易于应用实际。第三， 矩阵实数编码遗传算法（MRCGA）适合求解大规模机组组合问题。通过MATLAB仿真计算、不同迭代次数比

29、较分析以及同其他方法（如穷举法）的对比分析，验证了该方法在进行大规模机组组合问题求解时，具有很强的适应性和全局搜索能力，而且系统规模越大算法的优化结果越理想。缺点：第一，采用二次函数对空载成本和增量成本曲线参数进行拟合过程中，拟合误差比较大。特别是机组规模比较小时更是如此。第二，MRCGA算法对小规模机组组合问题求解结果精度不高，误差大。参考文献：1 刘琼荪，龚劬，何中市，傅鹂，任善强，数学实验，北京：高等教育出版社，20042 姜启源，谢金星，叶俊，数学模型，北京：高等教育出版社，20063 孙力勇，张焰，蒋传文，基于矩阵实数编码遗传算法求解大规模机组组合问题，中国机电工程学报，第26卷（2

30、期），20064 赵东方，数学模型与计算，北京：科学出版社，2007附录 问题1的C+求解程序#include #include using namespace std;double cost1(double x);double cost2(double x);int get_total_price();void fun(int i);ofstream fout(11.doc);const int hour = 5;/ 最大出力int pmax2 = 200, 100;/ 最大增出力int pcmax2 = 30, 40;/ 最大减出力int pdmax2 = 50, 60;/ 状态int s

31、tate2hour = 1, 0;/ 负荷int demand5 = 0, 100, 130, 170, 140;/ 启动费用int start2 = 350, 100;/ 机组各时段状态int power25 = 100, 0;/ 系统备用要求int b_powerhour = 0, 20, 30, 50, 40;/ 最小费用int minprice = 9999999;int main()fun(1);return 0;/ 机组1成本double cost1(double x)if (x = 100)return 100 + 10*x;elsereturn 14*x - 300;/ 机组2

32、成本double cost2(double x)if (x = 60)return 12*x + 200;elsereturn 15*x + 20;/ 总成本int get_total_price()int i = 0, j;double price = 0;for (j = 1; j hour; j+)price += stateij*cost1(powerij)+ stateij*(1-stateij-1)*starti;i = 1;for (j = 1; j price ? price: minprice);/cout minprice ;fout minprice ;return pr

33、ice;void fun(int i)for (int j = -50; j = 30; j+= 1)/ 机组1power0i = power0i-1 + j;/ 机组1出力范围约束if (power0i 200)continue;/ 机组1增出力和减出力约束if ( (power0i-power0i-1) pcmax0) & (power0i power0i-1) | (power0i-1-power0i) pdmax0) & (power0i-1 power0i)continue;/ 机组2/ 负荷平衡约束power1i = demandi - power0i;/ 机组2出力范围约束if

34、(power1i 100)continue;/ 机组2增出力和减出力约束if ( (power1i-power1i-1) pcmax1) & (power1i power1i-1)|(power1i-1-power1i) pdmax1) & (power1i-1 power1i)continue;/ 机组1状态if (power0i 0)state0i = 1;elsestate0i = 0;/ 机组2状态if (power1i 0)state1i = 1;elsestate1i = 0;/ 系统备用约束int bei = 0;int k = 0;for ( k = 0; k 2; k+)bei += stateki * (pmaxk - powerki);if (bei b_poweri)continue;if (i = hour - 1)/cout get_total_price() ;/for (k = 0; k hour; k+)/cout power0k - power1k ;/cout endl;fout get_total_price() ;for (k = 0; k hour; k+)fout power0k - power1k ;fout endl;else/ 继续递归求解fun(i + 1);文档来源网络，版权归原作者。如有侵权，请告知，我看到会立刻处理。