精英遗传算法在曝气鼓风机组调度上的应用.DOC

1、省重点技术创新项目作者简介：杨光年，研究方向：工业控制；祁伟，研究方向：高性能计算；周军，研究方向：工业控制精英遗传算法在曝气鼓风机组调度上的应用杨光年 1 祁伟 2 周军 31 ( 连云港杰瑞深软科技有限公司 连云港 222000)2(南京信息工程大学 计算机科学与软件学院 南京 210044)3 ( 连云港杰瑞深软科技有限公司 连云港 222000)摘 要 目前，我国污水处理工 艺主要依靠曝气鼓风机维持生物化学反映的溶氧环境，使污水中的有机污染物转化为无害物质。对曝气鼓风 机资源的调度，是 污水处理行业的关 键问题。而传统的调度算法，存在一定的缺陷，如不能很好的满足供气量与能耗的要求，与最

2、优解存在较 大的偏差等。本文提出了基于改进遗传算法的资源调度策略，采用了逐次逼近最 优保存策略和混合交叉等算法，实现曝气鼓风机资源的调度。通过仿真试验表明， 应 用遗传算法实现 的资源调度，能 够有效的减少系统总执 行时间和任务完成时间，具有较强的稳定性和适应性。关键词 遗传算法 资源调度 混合交叉 择优保存Elite genetic algorithm application on blower resource schedulingYang guang nian1 Qi Wei2 Zhou Jun21 (Jari deepsoft technology ltd, Lianyungang 2

3、22000, China)2 (Department of Computer Science and Technology , Nanjing University of Information Science & Technology, Nanjing 210044, China)3 (Jari deepsoft technology ltd, Lianyungang 222000, China)Abstract Now, Our sewage treatment industry mainly depend on the blower of aeration act as metaboli

4、c, absorbed in the toxic substances. Blower resources management is the key issue of sewage treatment. Traditional resource scheduling algorithm exist some defects , for example it can not well meet the quality requirements and can not get the Optimal solution. This article give an new resource sche

5、duling method based on Improved genetic algorithm. It achieves grid resource scheduling by using real number encoding and activities point crossover. Experiments show that genetic algorithm can reduce excuting time and task completion time,and further improve the scalability of resource scheduling m

6、odel.This algorithm has stability and high efficience in grid enviroment. Keywords Genetic algorithm Resource scheduling Cross Selection of the best preserved.0 引 言Now, Our sewage treatment industry mainly depend on the blower of aeration act as metabolic, absorbed in the toxic substances.目前我国城市污水处理

7、较多采用微生物的代谢作用，使污水中呈溶解、胶体状态的有机污染物转化为稳定的无害物质。Biological process is a complicated process of chemical reactions.生物处理过程是个复杂的生物化学反应过程，通过曝气维持好溶氧环境是其中一个非常重要的环节。鼓风机作为污水处理曝气环节中经常采用的机械设备，对污水处理厂的正常运行起着重要作用，要保证不同污水处理工艺对鼓风曝气的控制要求，鼓风曝气系统的精细化控制对整个污水处理厂的节能运行意义重大。污水处理系统中，最关键的问题是对多台鼓风机的控制，在保证系统安全性，稳定性等性能指标的前提下，让鼓风机组以最

8、低的能耗满足系统的需求。本文将改进的遗传算法，应用于风机组的控制，实验表明有很好的效果，给曝风机组控制提供了一种新的方法。1 曝气鼓风机自动控制系统1.1 系统组成曝气鼓风机自动控制系统由就地控制柜（LCP）和主控制柜（ MCP）组成。主控制器（MCP）对二至十五台曝气鼓风机进行控制，负责整个系统的联动控制，根据空气总管出口的压力和流量的需求控制各台鼓风机的启停，以满足所需的空气供应量，并根据各鼓风机的优先权的设定选择运行状态；就地控制器（LCP）控制本台机组的正常运行，并根据进出口压差和流量需求自动调节出口/入口导叶的开度，在满足空气流量供给需要的前提下尽量降低系统功耗。图 1 系统总体架构

9、1.2 系统性能指标(1) 流量控制通过出口导叶的开度的变化来控制进气流量的大小。在“远程”控制方式下，由主控制系统（MCP）根据总管进气的需求量调节出口导叶的开度；在“就地”控制方式下，由人工设定出口导叶的开度。(2) 功耗控制-通过出口导叶开度的变化来控制进气流量的大小。在“远程”控制方式下，由主控制系统（MCP）根据总管进气的需求量调节出口导叶的开度；在“就地”控制方式下，由人工设定出口导叶的开度。(3) 优先权分配每一台鼓风机都配有唯一的优先权，所选的优先权决定了由主控柜控制的鼓风机起动顺序。优先权设置必须连续，无效的优先权设置系统不能接受并做出提示。(4) 多机启动补偿启动补偿只在鼓

10、风机启动过程中使用。主控柜发出起动指令给优先权为 2 的就地控制柜，启动鼓风机时，起动补偿定时器激活，主控柜控制优先权为 1 的鼓风机的风量控制直到定时结束，当鼓风机的启动补偿时间结束时，优先权为的鼓风机供风量增加，直至其到达最大供风量，然后系统控制优先权为 2 的鼓风机工作。1.3 系统分析该 系 统 由 主 控 制 器 （MCP ）对整个风机组进行统一管理，每个风机有很多性能指标如：温度，可靠性，安全性，出口导叶开度，震动幅度等。MCP 控制整个风机组，在保证系统安全性，可靠性等基础上，让风机产生的风力之和满足系统风力的需求。从以上的分析来看，如果把每个风机当成一个资源，而风机的性能，当成

11、资源的参数。那么，MCP 的调度算法，可看成资源调度。从而把曝风机调度问题转化为一个多重目标约束问题。而多重目标约束问题可用遗传算法来解决，实验表明有很好的性能。本文对传统的遗传算法加以改进，在传统的遗传算法上，加上混合交叉算法和最优保存策略，应用于 MCP 的控制，实验证明，该算法具有很好的性能。2 算法实现2.1 曝气鼓风机调度的数学模型曝气鼓风机组调度方案要满足各种用户不同的需求，包含了承受时间、计算量、资源数、可靠性、安全性等，曝气鼓风机组调度可描述为从一定资源库中抽取满足调度目标要求的一组曝气鼓风机， 从而把调度问题转化为一个多重约束目标问题。假设资源需求包含 m 个资源、n 个指标

12、，因此，在资源调度前，首先建立资源控制指标相应的目标矩阵。图 6 资源模型S 的每一行由某一曝气鼓风机的控制指标组成，如承受时间、计算量、资源数、可靠性、安全性等，并且这些属性指标都进行编码表示成二进制形式，而每一列是资源库中某一指标的全部取值。由上面对问题的描述可以看出，曝气鼓风机组调度问题是一个多重约束目标问题。假设资源库中有 m 个曝气鼓风机，随着 m 的增大，计算的复杂度无论在时间还是空间上都将成指数增长，这对于规模较大的调度问题是难以接受的，所以有必要寻找新的求解方法。本文引入遗传算法并加以改进用于对该问题进行求解。2.2 曝气鼓风机调度方案的评价策略评价一个曝气鼓风机组调度方案的满

13、足程度，即是判断该调度方案里所有曝气鼓风机满足程度之和，而每个曝气鼓风机的满足程度，为该曝气鼓风机的各个属性的满足程度之和。曝气鼓风机属性的满足程度 (4)()(pDAAtrubi为目标值， 当前值。)(pD)(pA曝气鼓风机的满足程度(5)njjitrubqsourceE1R其中 为属性 i 所占的比重。j曝气鼓风机组调度方案的满足程度(6)njjisourceSolut12.3 曝气鼓风机调度方案的选择算子从 群 体 中 选 择 优 胜 的 个 体 ， 淘 汰 劣 质 个 体 的操 作 叫 选 择 。 选 择 算 子 有 时 又 称 为 再 生 算 子(reproduction opera

14、tor)。 选 择 的 目 的 是 把 优 化 的个 体 (或 解 )直 接 遗 传 到 下 一 代 或 通 过 配 对 交 叉 产生 新 的 个 体 再 遗 传 到 下 一 代 。将每个曝气鼓风机组调度方案，看做一个DNA、根据生物进化优胜劣汰的原则，如果该DNA 的评价值较高，则该 DNA 以较高的概率进行下一轮的竞争。曝气鼓风机组调度方案的选择概率(7)Mjjii ESolutinltPselct1曝气鼓风机组调度解决方案的累计概率 (8)ijselctAlt1对每个产生一个0，1的随机数 r，若，该资源调度方案得以遗iiPsltrselct1传到下一代。2.4 曝气鼓风机调度方案的混合

15、交叉算子在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。采用实数编码3方式，一般的交叉算子，将每个资源调度方案看做一个 DNA，对每个 DNA里的基因进行排序，然后将两个 DNA 从中断开，重新结合成新的 DNA。图 7 普通的交叉算法采用混合交叉编码后，交叉算子一改以往的形式，采用先混，后分离的方法，继承式的扩展了 DNA 的形态。图 8 改进的混合算法2.5 资源调度的变异算子遗 传 算 法 导 引 入 变 异

16、的 目 的 有 两 个 ： 一 是使 遗 传 算 法 具 有 局 部 的 随 机 搜 索 能 力 。 当 遗 传 算法 通 过 交 叉 算 子 已 接 近 最 优 解 邻 域 时 ， 利 用 变 异算 子 的 这 种 局 部 随 机 搜 索 能 力 可 以 加 速 向 最 优 解收 敛 。 显 然 ， 此 种 情 况 下 的 变 异 概 率 应 取 较 小 值 ，否 则 接 近 最 优 解 的 积 木 块 会 因 变 异 而 遭 到 破 坏 。二 是 使 遗 传 算 法 可 维 持 群 体 多 样 性 ， 以 防 止 出 现未 成 熟 收 敛 现 象 。 此 时 收 敛 概 率 应 取 较 大

17、 值 。在 资 源 不 重 复 的 前 提 下 ， 随 机 的 在 资 源 调度 方案中去掉一个资源，并随机的产生另一个资源，这样模仿实现了自然界中的变异算子。图 9 变异策略3 试验分析本 文 对 改 进 的 遗 传 算 法 ， 进 行 了 模 拟 试 验 ，采 用 语 言 为 java。 试 验 如 下 ：仿 真 试 验 模 拟 了 可 用 资 源 ， 产 生 具 有 2 个目 标 的 风 机 调 度 方 案 。 采 用 改 进 的 基 于 实 数 编码 和 混 合 交 叉 遗 传 算 法 。 资 源 的 描 述 如 下图 10 曝风机资源描述试 验 要 从 可 用 曝 气 鼓 风 机 中

18、 ， 选 择 2 个 目标 曝 气 鼓 风 机 ， 目 标 曝 气 鼓 风 机 的 目 标 值 为130， 0.8， 0.6； 150， 0.75， 0.4比 重 参 数 为 ， ， 。 试 验 结 果 如 下 图 11q23q所 示 ， 普 通 的 遗 传 算 法 ， 平 均 收 敛 代 数 是 改 进 遗传 算 法 的 3 倍 ， 改 进 遗 传 算 法 的 成 功 率 也 明 显 高于 普 通 的 遗 传 算 法 。图 11 与普通遗传算法比较随 着 曝 气 鼓 风 机 数 的 增 加 ， 遗 传 算 法 的 成 功率 随 之 减 低 ， 当 资 源 为 30 个 的 时 候 ， 普 通

19、 遗 传算 法 成 功 率 为 95%左 右 ， 而 改 进 的 遗 传 算 法 成功 率 约 为 100%。 当 曝 气 鼓 风 机 数 增 至 180 个 的时 ， 普 通 遗 传 算 法 的 成 功 率 仅 为 55%左 右 ， 而改 进 的 遗 传 算 法 为 80%。 可 见 改 进 的 遗 传 算 法 ，较 普 通 的 遗 传 算 法 在 时 间 和 性 能 上 ， 都 有 提 高 。图 12 任务提交成功率和 其 他 算 法 比 较 ， 改 进 的 遗 传 算 法 引 入 最优 保 存 策 略 机 制 和 混 合 交 叉 算 子 ， 在 性 能 上 ，也 有 明 显 的 优 势

20、。 如 图 13 所 示 。图 13 试验资源从 实 验 结 果 可 以 看 出 ， 同 等 条 件 下 ， 改 进的 遗 传 算 法 ， 在 迭 代 70 次 的 情 况 ， 与 最 优 解 偏差 为 ， 0.74， 而 禁 忌 搜 索 算 法 ， 和 蚁 群 算 法 在迭 代 100 次 的 时 候 ， 与 最 优 解 偏 差 分 别 为 0.98和 0.78。 在 时 间 上 ， 改 进 遗 传 算 法 为88.38ms， 禁 忌 搜 索 算 法 ， 和 蚁 群 算 法 分 别 为90.59ms 和 80.48ms， 显 然 改 进 的 遗 传 算 法 ， 在曝 气 鼓 风 机 调 度

21、上 面 ， 表 现 出 更 好 的 性 能 。4 结束语目前， 曝 气 鼓 风 机 调 度 是 我国城市污水处理的 关 键 问 题 。 好 的 调 度 算 法 ， 不 仅 能 提 供 系 统 安全 性 ， 可 靠 性 ， 而 且 ， 也 降 低 了 系 统 能 耗 ， 降 低污 水 处 理 的 成 本 。 改 进 工 业 的 控 制 算 法 ， 是 工 业控 制 的 关 键 问 题 ， 也 是 理 论 问 题 走 向 实 践 的 必经 之 路 。 本 文 对 污 水 处 理 行 业 的 曝 气 鼓 风 机 调度 进 行 了 深 入 的 研 究 ， 提 出 了 一 种 ， 基 于 改 进遗 传

22、算 法 的 调 度 方 法 ， 在 同 样 条 件 下 ， 该 方 法 较禁 忌 搜 索 算 法 ， 和 蚁 群 算 法 ， 表 现 出 更 好 的 性能 。 为 污 水 处 理 行 业 的 曝 气 鼓 风 机 调 度 ， 提 供了 一 种 参 考 方 法 。参 考 文 献1 姚文俊 遗传算法及其研究进展J 计算机与数学工程，2004，32（4）：41432 于淼，王日宏 改进遗传算法在自动组卷中的应用研究J 计算机工程与应用，2008，44（25）：2362383 李勇，曹广益，朱新坚 一种基于复合交叉的实数编码遗传算法J 计算机仿真，2006，23（6）：1661694 JHHolland

23、 ，Adaptation in natura land artificial systemsM，Ann arbor: Universityof Michigen press,1975.5 胡守仁等.神经网络导论 M.长沙:国防科技大学出版社,1993.113117. 6 Aladdin Masria, Thomas Bourdeaudhuya, Armand Toguyenia. Performance Analysis of IEEE 802.11b Wireless Networks with Object Oriented Petri NetsJ. Electronic Notes in

24、 Theoretical Computer Science, 2009, 242(2): 73-85.7 姚新,陈国良,徐惠敏等 .进化算法研究进展 J.计算机学报,1995,18(9):694-706. 赵建立, 闻英友, 商瑞强 , 王光兴. 一种新型卫星网管协议的 Petri 网描述与验证J.东北大学学报, 2004, 25(4): 325-328.8 Chiang TC, Tai CF, Hou TW. A knowledge-based inference multicast protocol using adaptive fuzzy Petri netsJ. EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36(4): 811