机组组合问题用遗传算法求解

上传人:wt****50 文档编号:35620185 上传时间:2018-03-18 格式:PPT 页数:48 大小:797KB
返回 下载 相关 举报
机组组合问题用遗传算法求解_第1页
第1页 / 共48页
机组组合问题用遗传算法求解_第2页
第2页 / 共48页
机组组合问题用遗传算法求解_第3页
第3页 / 共48页
机组组合问题用遗传算法求解_第4页
第4页 / 共48页
机组组合问题用遗传算法求解_第5页
第5页 / 共48页
点击查看更多>>
资源描述

《机组组合问题用遗传算法求解》由会员分享,可在线阅读,更多相关《机组组合问题用遗传算法求解(48页珍藏版)》请在金锄头文库上搜索。

1、A Genetic Algorithm Solution To The Unit Commitment Problem(用遗传算法求解机组组合问题),概 要,用遗传算法求解机组组合问题,1.机组组合问题及求解方法简介,机组组合问题 由于当前的科学技术还不能有效地存储电力,所以电力生产和消费在任何时刻都要相等,否则就会威胁电力系统安全运行。又由于发电机组的物理特性限制,(系统备用约束 、发电机组出力范围约束 、最小启停机时间 等等)发电机组不能够随心所欲地发出需要的电力。为了能够实时平衡变化剧烈的电力负荷,需要根据预测的未来电力负荷安排发电机组起停计划,在满足电力系统安全运行条件下,追求发电成本

2、最小。下面是机组组合问题的一个数学模型。,1.机组组合问题及求解方法简介,该模型要解决的是一个混合整数规划问题定义一个向量变量xit, 其分量为发电机i 在t 时段的所有连续变量, 。例如, xit =pit, rit T , pit 表示发电机i 在t 时段的有功; rit 表示该发电机提供的备用。定义一个标量(或向量) 变量zit 来表示发电机i 在t 时段的所有离散变量。把所有的xit 和zit 写成矩阵X 和Z 。,是各机组各时段燃料费用的总和;,是各机组各时段燃料费用的总和;,是各机组的开停机费用之和。,1.机组组合问题及求解方法简介,机组组合问题,可见机组组合问题是一个高维数,非凸

3、、离散、非线性的问题,找出其最优解是很困难的。对于机组组合问题,国内外电力科研工作者一直积极研究,提出各种方法来解决这个问题。本文回顾了优先级表法、动态规划法、拉格朗日松弛法。,P (X) 是系统的负荷和备用约束;R (X, Z) 表示机组爬坡速率限制、燃料总量限制等;M (X,Z)是耦合离散变量zit 和连续变量xit 的约束;U (Z) 是机组最短开停机时间限制。,1.机组组合问题及求解方法简介,优先级表法 优先级表法的基本原理是按机组实际运行统计其运行的平均费用,按此顺序进行排队,随着系统负荷升降而启停机组,这样使平均运行费用低的机组在周期内多发电,期望系统总的运行费用降至最低。优先级表

4、法简单而实用,计算速度快,占用内存少,但常常找不到最优解,但能满足一般的应用要求。其在机组的经济调度中获得了广泛的应用。,1.机组组合问题及求解方法简介,动态规划法 用动态规划法求解机组组合问题时,整个调度期间 T 被分成若干个时段,通常每个时段为 1h,每个时段即动态规划过程中的一个阶段。各阶段的状态即为该时段所有可能的机组开停状态组合。从初始阶段开始,从前向后计算到达各阶段各状态的累计费用(包括开停机费用和运行时的燃料费),再从最后阶段累计费用最小的状态开始,由后向前回溯,依次记录各阶段使总的累计费用最小的状态,这样就可得到最优的开停机方案,对于 N 台机组的系统,若要考虑 T 个时段的机

5、组组合问题,则总的状态数为 2NT,当 N 和 T 增大时,计算量将急剧增加,形成所谓“维数灾”。为克服这个困难,常采取一定的措施来限制状态的数目。,1.机组组合问题及求解方法简介,拉格朗日松弛法 拉格朗日松弛法在机组组合问题中应用时,把所有的约束分成两类,一类是全系统的约束,一类是可以按单台机组分解的约束,系统约束可以写成惩罚项的形式,加入目标函数,形成拉格朗日函数,拉格朗日函数可按单台机组分解成一系列的子问题。 优点:随着机组数的增加,计算量近似线性增长,克服了维数障碍,且机组数目越多,算法效果越好; 缺点:由于目标函数的非凸性,用对偶法求解时,存在对偶间隙,需要根据对偶问题的优化解采取一

6、定的措施构造原问题的优化可行解。,2.遗传算法简介,设现在有这么个问题需要解决。求f(x)=x2在031之间取整数值时函数的最大值。准备:对定义域0,31内的非负整数x进行二进制编码, 如x=8时取x=01000,随机生成4个二进制数:01101(13) 、11000(24)、 01000(8)、10011(19);这4个数被称为一个种群,种群中的每个数就是一个个体。交叉:将原有种群中的两个个体随机匹配,进行交叉繁殖。比如选取01000(8) 与 10011(19);将第3位进行交换,得01011(11) 与 10000(16)。,2.遗传算法简介,变异:以很小的概率随机地改变一个个体中的位值

7、。比如若10011(19)被选中,将其第4位由1变为0。变异的概率很小一般只有千分之几,其目的是为了防止丢失一些有用的因子。选择:按个体的适应度进行复制,这里定义个体所定义的函数值为适应度,比如01101(13) 的适应度为169。则每个个体在下一代中的数量为:,2.遗传算法简介,mj(t) 为第j个个体在t代中的数量;mj(t+1)为第j个个体在t+1代中的数量; fj 为第j个个体在t代中的适应度。,2.遗传算法简介,这样经过交叉、变异、选择后,“适者生存,不适者淘汰”经每迭代(进化)一次,种群的适应度会有所提高,只要迭代多次,最终会走向全局最优解。可见,遗传算法中,每一步的操作是非常简单

8、的,而且对问题的依赖性很小,并不要求目标函数有连续光滑或要求目标函数的导数等。,3.遗传算法求解机组组合问题,3.1基本方法考虑问题,“有N台机组在在H小时内运行,要求制订一个开停机的计划,使得机组运行的总费用最小。”假定每小时内,发电机不是开启就是关闭,开启状态用“1”表示,关闭状态用“0”表示。如图1所示:,3.遗传算法求解机组组合问题,3.1基本解决方法,3.遗传算法求解机组组合问题,3.1基本方法用遗传算法的思想来解决问题。设N=20,H=24则每个个体的位数为2024=480,搜索空间内的元素个数为2480=3.1210144。随机选取一个种群,种群中的个体为480位二进制编码。适应

9、度F定义如下:,3.遗传算法求解机组组合问题,3.1基本方法,(1),(1),(2),且,FCT:燃料的总费用SUT:机组启动的总费用SDT:机组关闭的总费用NC :违反约束的数量,VIOLj:违反约束的数量值PFj :违反约束的罚项j :罚因子,(1),(2),(1),(2),(1),且,(2),(1),3.遗传算法求解机组组合问题,3.1基本方法交叉(Crossover),3.遗传算法求解机组组合问题,3.1基本方法变异(Mutation),3.遗传算法求解机组组合问题,3.1基本方法选择(Selection),图3.1 选择操作的轮盘赌转盘,3.遗传算法求解机组组合问题,3.1基本方法积

10、木块假设(Duilding-blocking Hypothesis) 积木块假设遗传算法中,分别具有高适应值、短定义矩或低阶的模式(积木块)在遗传算子的作用下相互结合,形式同时具有高适应值、短定义矩和低阶的更优秀的模式,最终接近全局最优解。,3.遗传算法求解机组组合问题,3.1基本方法可能出现的问题及检测 用遗传算法解决问题时,可能出现过早收敛和分散过广的情况。可用交叉率(crossover probability)和变异率(mutation probability)来检测。如下表如示,3.遗传算法求解机组组合问题,3.1基本方法可能出现的问题及检测,状态,项目,3.遗传算法求解机组组合问题,

11、3.1基本方法实例,启动费用,热启动费用 若关机时间冷启动间隔,冷启动费用 其它,热启动费用 若关机时间冷启动间隔,冷启动费用 其它,热启动费用 若关机时间冷启动间隔,冷启动费用 其它,3.遗传算法求解机组组合问题,3.1基本方法选取50个个体组成一个种群,进化500代;用20个种群并行计算,结果如下:,3.遗传算法求解机组组合问题,3.1基本方法,3.遗传算法求解机组组合问题,3.2改进措施1窗交换(Swap-window Operator) 0.3窗变异(Window-mutation Operator) 0.3,3.遗传算法求解机组组合问题,加入这两个操作结果如下:,3.遗传算法求解机组

12、组合问题,3.3改进措施2交换变异(Swap-mutation Operator) 窗交换爬坡(Swap-window Hill-climb Operator) 0.3仅用于适应度最好的个体。交换变异:选定两个个体,再选定一个H时间,交换该位。将交换后的结果与交换前的结果进行比较。或选定一个个体,再选定一个H时间,改变该位。将改变后的结果与交换前的结果进行比较。窗交换爬坡:按小时逐次进行窗交换,比较。如下图:,3.遗传算法求解机组组合问题,3.3改进措施2,3.遗传算法求解机组组合问题,执行结果:,3.遗传算法求解机组组合问题,3.4改进措施3改变罚因子:,约束j的最终罚因子,世代数,总的世代

13、数,3.遗传算法求解机组组合问题,3.4改进措施3执行结果,4.模拟结果,在10、20、40、60、80、100台机组上进行模拟,时间为24小时。下图是10台机组的相关数据.,4.模拟结果,4.模拟结果,4.模拟结果,模拟20台机组的问题时,将前面的10台机组翻倍,用电的需求量也翻倍。备用电量取需求量的10%。其余情况依此类推。下面对10台机组进行模拟运算,选取20个种群,每个种群包含50个个体,世代选为500。将运算结果与动态规划法、拉格朗日松弛法进行对比。如下表:,4.模拟结果,4.模拟结果,为什么选50个个体?一般说来,当个体数量增加时,收敛性变差;当每个种群选取75或100个个体时,经

14、过运算测试,收敛性无明显改善。另一方面,每次“进化”时,CPU的计算时间也会随个体数目线性增加。(CPU时间是基于此芯片得出HP Apollo 720 workstation),4.37h,2.79h,4.37h,2.79h,4.37h,2.79h,4.模拟结果,算法程序运行的时间与机组数量的关系如下图。,y=x2,5.结 论,遗传算法的好处是它可以对基于时间和耦合的限制进行建模。遗传算法可以在多台计算机上并行操行,用机器的数量来缩短计算时间。遗传算法的缺点是无法保证能找到最优解,且运算时间较长。,6.讨 论,问题1:交叉产生的下一代个体中,存在违反约束的个体(爬坡限制、最小开机时间、最小关机

15、时间等),是否可以在选择过程中用启发式算法滤去这些违反约束的个体? 启发式算法的定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计。启发式算法常能发现很不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。,6.讨 论,回答:在问题的约束很多时,采用启发式算法来降低问题的复杂度,将不可行的解转化为最近的可行解,这种方法有两种方案:a)将不可行的解转化为最近的可行解,用可行解替换掉原来的解;b)将不可行的解转化为最近的可行解,保持原来的解。按方案a)进行“进化”过程的选择,会滤掉所有违反约束的个体。若可行解空间很大,这个方案是可行的,但在机组组合问题中,可行解空间常常被不可行解所包裹着,采用a)会削减种群的多样性,可能会丢掉全局最优解。按方案b)进行“进化”过程的选择,新产生的可行解会对整个算法有严重的误导作用,导致偏离全局最优解。,6.讨 论,问题2:采用罚函数可以区别可行解与不可行解,但当适应度的罚项的值很大时,则难以与可行解区分开来,会导致收敛速度很慢。,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 社会民生

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号