最新机组组合问题用遗传算法求解-药学医学精品资料.ppt

《最新机组组合问题用遗传算法求解-药学医学精品资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最新机组组合问题用遗传算法求解-药学医学精品资料概要遗传算法是一种模拟生物进化中自然选择、基因重组、适者生存思想的算法。本文用遗传算法来解决机组组合问题，虽然多数情况下找不到最优解，但能得到的满意结果。并将遗传算法所得的结果与拉格朗日松弛法、动态规划所得的结果进行了对比。用遗传算法求解机组组合问题机组组合问题及求解方法简介遗传算法简介遗传算法求解机组组合问题3.1基本方法3.2改进措施13.3改进措施23.4改进措施3模拟结果结论讨论1.机组组合问题及求解方法简介优先级表法优先级表法的基本原理是按机组实

2、际运行统计其运行的平均费用，按此顺序进行排队，随着系统负荷升降而启停机组，这样使平均运行费用低的机组在周期内多发电，期望系统总的运行费用降至最低。优先级表法简单而实用，计算速度快，占用内存少，但常常找不到最优解，但能满足一般的应用要求。其在机组的经济调度中获得了广泛的应用。1.机组组合问题及求解方法简介动态规划法用动态规划法求解机组组合问题时,整个调度期间T被分成若干个时段，通常每个时段为1h，每个时段即动态规划过程中的一个阶段。各阶段的状态即为该时段所有可能的机组开停状态组合。从初始阶段开始，从前向后计

3、算到达各阶段各状态的累计费用(包括开停机费用和运行时的燃料费)，再从最后阶段累计费用最小的状态开始，由后向前回溯，依次记录各阶段使总的累计费用最小的状态，这样就可得到最优的开停机方案，对于N台机组的系统，若要考虑T个时段的机组组合问题，则总的状态数为2N×T，当N和T增大时，计算量将急剧增加，形成所谓“维数灾”。为克服这个困难，常采取一定的措施来限制状态的数目。1.机组组合问题及求解方法简介拉格朗日松弛法拉格朗日松弛法在机组组合问题中应用时,把所有的约束分成两类,一类是全系统的约束,一类是可以按单台机组分

4、解的约束,系统约束可以写成惩罚项的形式,加入目标函数,形成拉格朗日函数,拉格朗日函数可按单台机组分解成一系列的子问题。优点:随着机组数的增加,计算量近似线性增长,克服了维数障碍,且机组数目越多,算法效果越好；缺点:由于目标函数的非凸性，用对偶法求解时,存在对偶间隙,需要根据对偶问题的优化解采取一定的措施构造原问题的优化可行解。2.遗传算法简介设现在有这么个问题需要解决。求f(x)=x2在0～31之间取整数值时函数的最大值。准备：对定义域[0，31]内的非负整数x进行二进制编码，如x=8时取x=01000，

5、随机生成4个二进制数:01101(13)、11000(24)、01000(8)、10011(19);这4个数被称为一个种群，种群中的每个数就是一个个体。交叉：将原有种群中的两个个体随机匹配，进行交叉繁殖。比如选取01000(8)与10011(19)；将第3位进行交换,得01011(11)与10000(16)。2.遗传算法简介变异：以很小的概率随机地改变一个个体中的位值。比如若10011(19)被选中，将其第4位由1变为0。变异的概率很小一般只有千分之几，其目的是为了防止丢失一些有用的因子。选择：按个体的适

6、应度进行复制，这里定义个体所定义的函数值为适应度，比如01101(13)的适应度为169。则每个个体在下一代中的数量为：2.遗传算法简介mj(t)——为第j个个体在t代中的数量;mj(t+1)——为第j个个体在t+1代中的数量;fj——为第j个个体在t代中的适应度。2.遗传算法简介这样经过交叉、变异、选择后，“适者生存，不适者淘汰”经每迭代（进化）一次，种群的适应度会有所提高，只要迭代多次，最终会走向全局最优解。可见，遗传算法中，每一步的操作是非常简单的，而且对问题的依赖性很小，并不要求目标函数有连续光滑

7、或要求目标函数的导数等。3.遗传算法求解机组组合问题3.1基本方法考虑问题，“有N台机组在在H小时内运行，要求制订一个开停机的计划，使得机组运行的总费用最小。”假定每小时内，发电机不是开启就是关闭，开启状态用“1”表示，关闭状态用“0”表示。如图1所示:3.遗传算法求解机组组合问题3.1基本解决方法3.遗传算法求解机组组合问题3.1基本方法用遗传算法的思想来解决问题。设N=20，H=24则每个个体的位数为20×24=480，搜索空间内的元素个数为2480=3.12×10144。随机选取一个种群，种群中的个

8、体为480位二进制编码。适应度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