优化动力配煤数学模型寻优算法的研究.pdf

60 洁净煤技术2005年第11卷第4期 优化动力配煤数学模型寻优算法的研究 董 平 陈彦杰 黑龙江科技学院 资源与环境工程学院 黑龙江 哈尔滨 150027 摘要 根据用户对配煤煤质特性指标和燃烧特性指标的要求 笔者确立了非线性动力配 煤优化模型 并详细研究了几种常用的寻优算法的基本原理 特点及其在优化动力配煤数学 模型中的应用效果 研究结果表明 穷举法准确但效率太低 而混合离散变量优化设计 MDOD 法只能局部优化并易陷入局优解 遗传算法鲁棒性强 具有较好的全局搜索性能 模拟退火算法简单 通用 具有很好的局部搜索能力 在此基础上 笔者总结出一种遗传算 法与模拟退火法相结合的混合算法 关键词 动力配煤 穷举法 MDOD法 遗传算法 模拟退火算法 中图分类号 TD849 O242 文献标识码 A 文章编号 100626772 2005 0420060 05 收稿日期 2005 06 06 基金项目 黑龙江省科技厅攻关项目 GC03J102 作者简介 董平 1963 男 辽宁北票人 教授 博士 黑龙江省洁净煤技术研究中心主任 从事洁净煤技术的研究工作 目前动力配煤技术是相对成熟 投入较低 见 效较快 符合中国国情 应予优先发展的洁净煤技 术之一 动力配煤是以煤化学 煤燃烧学为基础 结合煤质检测 计算机优化控制等新技术应用 与 筛选等工艺组合 以实现煤质互补 提高燃煤质 量 取得较好的经济 社会与环境效益 1 动力 配煤所要解决的问题是 在用户提出的燃煤指标的 基础上 从煤场所拥有的多煤种中选择几种煤进行 配伍以使配煤产品满足用户的要求 因此 建立一 套比较完整合理的优化动力配煤数学模型 选择合 适的寻优算法至关重要 为此 笔者根据近年来众 多学者 专家对动力配煤数学模型的研究 综合考 虑配煤发热量 挥发分 水分 灰分 硫分等煤质 特性指标及配煤燃烧特性指标的影响 确立了非线 性动力配煤优化模型 并详细研究了穷举法 混合 离散变量优化设计 MDOD 法 遗传算法及模拟 退火算法等多种寻优算法的原理 流程及优缺点 并在此基础上总结出一种遗传算法与模拟退火法相 结合的混合算法 1 非线性优化动力配煤数学模型 2 根据用户对配煤的煤质特性和燃烧特性的要 求 建立优化动力配煤问题的数学模型常需考虑以 下10个配煤指标 包括 发热量 挥发分 硫分 水分 灰分 灰熔点 结渣特性 着火特性 燃烬 特性及SO2的排放特性 优化动力配煤的数学模型 可写为 目标函数 Pmin n i 1 CiXi 或其他追求目标 约束条件 发热量 QA Q fq X i Qi Mi Ai Vi Fi QB 挥发分 VA V fv X i Qi Mi Ai Vi Fi VB 硫分 SA S fs X i Si SB 水分 MA M fm X i Qi Mi Ai Vi Fi MB 灰分 AA A fa X i Qi Mi Ai Vi Fi AB 灰熔点 T2A T2 ft2 X i 各单一煤种的灰成 分分析 T2B 着火温度 tA t ft X i Qi Mi Ai Vi Fi tB 结渣特性 RA R fr X i 各单一煤种的灰成 优化动力配煤数学模型寻优算法的研究61 分分析 RB 燃烬特性 DA D fd X i Qi Mi Ai Vi Fi DB S02排放特性 qA q fso2 X i Si Qi 各单一煤 种的灰成分分析 qB 上述模型的目标函数中 Pmin表示配煤所追求 的最低成本 n表示参配的煤种数 Ci为各参配煤的 单价 Xi为各参配煤的比例 约束条件中 符号Q V S M A T2 t R D和q 分别为配煤的发热量 挥发分 硫分 水分 灰分 灰 熔点 着火温度 结渣特性指标 燃烬特性指标和 SO2排放指标 其中不等式的左边 带下标 A 分别 表示各相应指标的下限 而不等式的右边 带下标 B 则表示对应的上限 约束条件中的各函数fq fv fm fa ft2 ft fr fd及fso2分别表示配煤的发热量 挥发 分 硫分 水分 灰分 灰熔点 着火温度 结渣特性指 标 燃烬特性指标和SO2排放指标与相关因素的函 数关系 约束条件中各函数的自变量Xi Qi Mi Ai Vi Fi及Si分别表示各参配单一煤种的配比 发 热量 全水分 灰分 挥发分 固定碳及全硫分 2 穷举法 211 穷举法的原理和实现 穷举法是一种寻遍所有组合可能性的算法 即 在一个连续有限搜索空间或离散无限搜索空间中 计算空间中每个点的目标函数值 且每次计算一 个 对于搜索满足上述约束条件集Pmin 以单价分 别为C1 C2 C3的3种参配煤进行配伍为例 设 煤种库中总共有N种单一煤种 配煤精度为1 配煤主程序核心程序如下 forC1 单一煤种1 单一煤种N forC2 单一煤种1 单一煤种N forC3 单一煤种1 单一煤种N 调用 配煤子程序 则从N种单一煤种中取3种进行参配的可能 组合有C 3 N种 即需要从配煤主程序中调用 配煤 子程序 C 3 N次 由于在实际配煤过程中 参配煤 种的比例必须大于或等于10 因此 配煤子程 序核心程序如下 forX1 10 80 步长1 forX2 10 80 步长1 forX3 10 80 步长1 if P Pmin then Pmin P 因此 对于每次运算配煤子程序 所有可能的 配比组合为80 3 并且在这每种可能的配比组合 下 需要对所有的约束条件进行判断 并保留当前 最优解 运算量非常大 212 穷举法应用于优化配煤模型的优缺点 1 优点 结果准确 由于穷举法遍历了所 有可能的参配煤种和所有可能的参配配比 它计算 出的结果是准确可靠的 2 缺点 效率低 耗时长 随着参配煤种 的增加 单一煤种总数的增加和配煤精度的提高 计算时间也急剧变长 特别当单一煤种总数大于 30种且配煤精度为1 的情况下 计算时间竟高达 3000s 让人难以忍受 3 混合离散变量优化设计 MDOD 法 311 MDOD法的原理 MDOD法构造思想如下 3 首先从一个可行 的离散点出发 沿相对混合次梯度方向进行离散一 维搜索 从而得到一个使目标函数值减小同时又满 足约束条件的新离散点 然后由此点开始继续重 复 直至当得不到这样的一个新点时 就开始在离 散子空间E D和连续子空间 E C内进行轮变搜索 若 轮变搜索后能得到一个新的可行离散点 则返回第 一步的搜索过程 否则 即可根据停留的离散点的 目标函数和约束函数所提供的信息 按确定的规则 在单位领域内查点 若查找到了新离散点 则返回 第一步搜索过程 否则根据最优解的基本性质 此 点即为局部离散最优解 312 MDOD算法应用于优化配煤模型的优缺点 实践证明 当配煤精度为1 时 MDOD法的 计算时间少于穷举法 这是由于配煤子程序内部用 MDOD法寻优 从而节省了时间 但是正是由于这 种寻优是局部性的 随着单一煤种总数的增加和参 配煤种数的增加 其计算时间也急剧增加 尤其 当单煤总数为30 四种煤相参配时 计算时间可 高达350s 大大超出了正常的等待时间 MDOD算法在优化配煤模型中应用时的最大缺 陷在于它只能在参配煤种确定的情况下对参配煤种 的配比进行优化 而对于使用哪几种煤进行参配却 无法优化 因此 只能用它进行局部的寻优 即在 配煤子程序 内部采用MDOD 而在 配煤主程 序 还是只能采用穷举法 62 洁净煤技术2005年第11卷第4期 4 遗传算法 411 遗传算法的原理 遗传算法是一种以群体中的所有个体为对象 具有 生成 检测 的迭代过程的搜索算法 尤 其适用于处理传统搜索方法难以解决的复杂和非线 性问题 选择 交叉 变异是遗传算法的3个主要操作 算子 它们构成了所谓的遗传操作 遗传算法从任 一初始化的群体出发 通过随机选择 使群体中 优秀的个体有更多的机会传给一下一代 交叉 体现了自然界中群体内个体之间的信息交换 和 变异 在群体中引入新的变种确保群体中信息的 多样性 等遗传操作 使群体一代一代地进化到 搜索空间中越来越好的区域 直至抵达最优解 点 4 412 遗传算法的核心内容 1 参数编码 2 初始群体的设定 3 适应度函数的设计 4 遗传操作设计 5 控制参数设定 主要是指群体大小和使 用遗传操作的概率等 413 遗传算法的主要特点 遗传算法具有很强的鲁棒性 5 这是因为比 起普通的优化搜索方法 它采用了许多独特的方法 和技术 主要有以下几个方面 l 遗传算法的处理对象不是参数本身 而是 对参数集进行了编码的个体 此编码操作 使得遗 传算法可直接对结构对象 集合 序列 矩阵 树 图 链和表等一维或二维甚至三维结构形式的 对象 进行操作 2 许多传统搜索方法都是单点搜索算法 即通过一些变动规则 问题的解从搜索空间中的当 前解 点 移到另一解 点 这种点对点的搜索 方法 对于多峰分布的搜索空间常常会陷入局部的 某个单峰的优解 而遗传算法是采用同时处理群体 中多个个体的方法 即同时对搜索空间中的多个解 进行评估 更形象的说 遗传算法是并行地爬多个 峰 这一特点使遗产算法具有较好的全局搜索性 能 减少了陷入局部优解的风险 6 3 在标准的遗传算法中 基本上不用搜索 空间的知识或其它辅助信息 而仅用适应度函数值 来评估个体 并在此基础上进行遗传操作 遗传算 法的适应度函数不仅不受连续可微的约束 而且其 定义域可以任意设定 7 4 遗传算法不是采用确定性规则 而是采 用概率的变迁规则来指导它的搜索方向 8 414 遗传算法在优化配煤模型中应用的优缺点 遗传算法应用于优化配煤模型时 采用并行计 算的方法 可对参配配比和参配煤种同时优化 其 计算时间远远小于穷举法 并且其计算复杂度基本 不受配煤精度和煤种库中单一煤种总数的大小的影 响 当单一煤种总数为20和30时 计算均可低达 4s左右 然而遗传算法也存在自身缺陷 1 遗传算法求解约束优化问题的能力不强 对于要解决的约束优化问题 一般采用基于罚函数 的罚函数类方法 而事先确定适当的罚函数是很困 难的 往往需要通过多次试验来不断进行调整 9 而对于多个约束条件 其罚因子的选取对于遗传算 法的结果更是有很大的影响 2 遗传算法局部搜索能力不强 理论上已 证明 在遗传算法中 如果选择算子作用后保留当 前最优解 那么该遗传法能最终收敛于全局最优 解 但是 遗传算法的局部搜索能力不足 要达到 真正的最优解可能需要花费很长时间 10 5 模拟退火算法 511 模拟退火法的原理 11 模拟退火法使用基于概率的双方向随机搜索技 术 当基于邻域的一次操作使当前解的质量提高 时 模拟退火法接收这个被改进的解作为新的当前 解 在相反的情况下 模拟退火法以一定的概率 exp C T 接收相对当前解来说质量较差的 解作为新的当前解 算法终止时的当前解即为所得 近似最优解 其中 C为邻域操作前后解的质量 差 T为退火过程的控制参数 512 模拟退火算法的优越性 模拟退火算法依据Metropolis准则接受新解 因此 除接受优化解外 还在一定范围内接受恶化 解 这正是模拟退火算法与局部搜索算法的本质区 别所在 开始时T值大 可能接受较差的恶化解 随着T值的减小 只能接受较好的恶化解 最后 在T值趋于零时 就不再接受任何恶化解了 因 此 该方法最突出的特点是 它不仅要保留目前表 现不太好的点 而且还有把这些点作为下次分析检 验的中心的可能性 模拟退火算法既可以从局部最 优化动力配煤数学模型寻优算法的研究63 优的 陷阱 跳出 更有可能求得组合优化问题 的整体最优解 又不失简单性和通用性 12 513 模拟退火算法的渐进收敛性 13 对于恶化解 随着T值的衰减 exp C T 0 故T衰减到一定程度时即不再接受 至 于优化解 由于算法中产生新解的邻域结构通常选 得较简单 否则可能因专注个别问题特征而丧失 算法通用性 或者因变成精确算法而导致算法不可 行 因此在不能由解的恶化跳出当前邻域时 一 般均可较快地探索到该邻域的最优解 从而无法再 优化 总之 算法在有限时间内必定会现出解在连 续M个Markov链中无任何改变的情况 即完全可 以在有限时间内终止 因此从概率的角度是渐进收 敛的 514 模拟退火算法的核心内容 1 初始解的生成 2 在邻域内寻找新的当前解 3 退火 4 降温 515 模拟退火算法在优化动力配煤模型中的应用 效果 1 应用于优化配煤模型时 模拟退火算法 具有较强的局部搜索能力 其计算时间远远小于穷 举法 并且煤种库的大小对其计算的复杂度也没有 多大的影响 2 模拟退火算法的搜寻结果能非常接近最 优解 但是要达到最优解还是有相当的难度 3 理论上 模拟退火算法的控制参数T越 高 则搜索到全局最优解的可能性越大 但实际 上 当T非常大时 模拟退火算法儿乎接受所有 的恶化解 这不仅没有任何意义 无谓的增加计算 时间 还可能导致搜索的方向偏离最优解 搜索的 结果反而没有T取小一些的时候好 因此 必须 根据实际情况来指定T值 6 预测性的遗传算法与模拟退火法相结合 的混合算法 在遗传算法中 选择是最重要的机制 也是影 响遗传算法性能的追重要的因素 理论上 如果选 择算子作用后保留当前最优解 那么该遗传法能 最终收敛于全局最优解 在遗传算法运算初期 需 要在尽量大的解空间中进行求泛搜索 选择压力较 小 随着搜索的深入 尤其在遗传算法运算后期 群体中的个体越来越集中到解空间的某各局部范围 内 由于遗传算法的局部搜索能力不足 要进行求 精搜索 得到真正的最优解 往往对选择压力要求 过大 常以时间作为代价 根据对模拟退火法的原 理和特点的研究可知 模拟退火法具有较强的局部 搜索能力 因此 可以考虑对遗传算法设定适当的 迭代次数 使其运算中止 并把运算结果作为模拟 退火法的初始解 利用模拟退火法进行更深入的求 精搜索 因此可以预测 在优化动力配煤模型中运用遗 传算法与模拟退火法相结合的混合寻优算法效果会 比单独采用遗传算法和模拟退火法更好 7 结 语 确立非线性动力配煤优化模型比目前局限于线 性规划的配煤技术更合理 更完整 更易满足用户 的要求 综合研究上述各寻优算法可知 穷举法准 确 但 效 率 太 低 而 混 合 离 散 变 量 优 化 设 计 MDOD 法只能局部优化并易陷入局优解 遗传 算法鲁棒性强 具有较好的全局搜索性能 但局部 搜索能力不强 模拟退火算法简单 通用 具有很 好的局部搜索能力 本文在着重考虑遗传算法与模 拟退火法的优点的基础上 总结出一种遗传算法与 模拟退火法相结合的混合寻优算法 对该混合算法 的运算机理及在实际应用中的运算效果 将是本人 下阶段的研究重点 参考文献 1 成玉琪 俞珠峰 1洁净煤技术是中国洁净能源新技 术的重点领域 J 1洁净煤技术 2000 6 2 5 151 2 程军 曹欣玉 周俊虎 等 1多元优化动力配煤方 案的研究 J 1煤炭学报 2000 2 1 81 841 3 余俊 周济 1优化方法程序库OPB 1 原理及使用 说明 M 1北京 机械工业出版社 19891 4 周明 孙树栋 1遗传算法原理及应用 M 1北京 国防工业出版社 19991 5 席裕庚 柴天佑 1遗传算法综述 J 1控制理论与 应用 1996 13 6 697 7041 6 张晓绩 戴冠中 1一种新的优化算法 遗传算法 J 1控制理论与应用 1995 12 3 265 2731 7 张文修 梁怡 1遗传算法的数学基础 M 1西安 西安交通大学出版社 20001 8 傅学芳 1遗传算子的代数形式和概率特征 J 1工 科数学 2001 17 2 50 531 9 林丹 李敏强 1基于遗传算法求解约束优化问题的 一种算法 J 1软件学报 2001 12 4 1 64 洁净煤技术2005年第11卷第4期 10 杨启文 蒋静坪 1遗传算法优化速度的改进 J 1软件学报 2001 12 2 270 2751 11 谢云 1模拟退火算法的原理及实现 J 1高等学 校计算数学学报 1999 9 3 1 12 张天学 1模拟退火算法在多目标决策中的应用研 究 J 1郑州航空工业管理学院学报 1995 3 1 13 谢云 1模拟退火算法的原理及实现 J 1高等学 校计算数学学报 1999 9 31 Algorithm s for Opti m izing the M odel of Steam Coal Blending DONG Ping CHEN Yan jie Heilongjiang Institute of Science and Technology Harbin 150027 China Abstract This paper focuses on modelling of steam coal blending with application of some non linear theories based on the requirement of consumers and the principle fundaments of some algorithms to opti mising steam coal blending process The result of studies state clearly as follows Enumerative algorithm is accurate but not efficient while mixed discrete variables optimisation design can only achieve part opti misation and is easily trapped into partially optimised result W ith strong robustness genetic algorithm is good at searching for the final opti mised re2 sult And simulated annealing algorithm is si mple and of a great ability of local searching On the basisof the two later algorithms this paper proposes a hybrid algorithm of genetic algorithm and si mulated annealing algorithm The new hybrid algorithm may produce a more marked effect than other single algorithm Keywords power coal blending Enumerative algorithm MDOD genetic algorithm simulated annealing algo2 rithm 上接67页 Fouling characterization in membrane bioreaction J Separation Purfication and Technology 2001 22 5 123 132 5 Eriksson P Nanofiltration Extends the Range of Mem2 brane Filtration J 1Environmental Progress 1988 7 1 58 62 Study on the Application of Nanofiltration M embrane in CoalM in ingWater Treatment N IE Jin xu 1 2 XI AO Xian min 1 1 Guangzhou Insti