遗传算法在矿井通风网络优化中的应用.pdf

第3 6 卷第6 期中国矿业大学学报V 0 1 ．3 6N o ．6 2 0 0 7 年1 1 月J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e e h n o l n g yN o v ．2 0 0 7 文章编号1 0 0 0 1 9 6 4 2 0 0 7 0 60 7 8 9 0 5 遗传算法在矿井通风网络优化中的应用 孝 江，陈开岩，林柏泉 中国矿业大学煤炭资源与安全开采国家重点实验室能源与安全工程学院，江苏徐州2 2 1 0 0 8 摘要建立了矿井通风系统网络优化的非线性规划数学模型，井用遗传算法来求解该优化模型． 使用罚函数法对优化模型所包舍的约束方程进行转化和处理，使之适用于遗传算法．罚函数的形 式采用不可微精确罚函数，并在惩罚参数的选择上参考了模拟退火算法的一些优点，设计出一种 动态罚函数．应用遗传算法对一个简单通风网络的优化模型进行求解．结果表明优化后通风系 统总能耗降低了7 ．7 8k W ，其下降幅度约为3 ％． 关键词遗传算法；矿井通风网络；优化模型I 罚函数；模拟退火算法 中图分类号T D7 2 5文献识别码A G e n e t i cA l g o r i t h mf o rt h eO p t i m i z a t i o no f M i n eV e n t i l a t i o nN e t w o r k L IJ i a n g ，C H E NK a i y a n ，L I NB a i q u a n S t a t eK e yL a b o r a t o r yo fR e s o u r c e sa n dM i n eS 日f e t y ．S c h o o lo fM i n i n ga n dS a f e t yE n g i n e e r i n g ． C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，X u z h o u ，J i a n g s u2 2 1 0 0 8 ．C h i n a A b s t r a c t ．．Ag e n e r a ln o n l i n e a rm a t h e m a t i c sp r o g r a m m i n gm o d e lf o ro p t i m i z i n gt h em i n ev e n t i l a t i o nn e t w o r kw a se s t a b l i s h e da n ds o l v e db yg e n e t i ca l g o r i t h m ．T h ep e n a l t yf u n c t i o nm e t h o d w a su s e di nt r e a t i n ga n dt r a n s f o r m i n gt h ec o n s t r a i n te q u a t i o n sc o n t a i n e di nt h eo p t i m i z i n gr o o d e ls oa st ob es u i t a b l ef o rt h eg e n e t i ca l g o r i t h m ．N o n - d i f f e r e n t i a b l ea c c u r a t ep e n a l t yf u n c t i o n s w e r ec h o s e ni nt r e a t i n gt h ec o n s t r a i n te q u a t i o na n dt h ea d v a n t a g e so fs i m u l a t e da n n e a l i n ga l g o - r i t h mw a su s e df o rr e f e r e n c ei nd e t e r m i n i n gp e n a l t yp a r a m e t e r s ．O nt h eb a s i so ft h i s ．ad y n a m i cp e n a l t yf u n c t i o nw a sd e s i g n e d ．T h e nt h eg e n e t i ca l g o r i t h mw a su s e dt os o l v i n gt h eo p t i m i z e d m o d e lf o ras i m p l ev e n t i l a t i o nn e t w o r k ．T h er e s u l ts h o w st h a tt h eo v e r a l le n e r g yc o n s u m p t i o n o ft h eo p t i m i z e dv e n t i l a t i o ns y s t e mh a sad e c r e a s eo f7 ．7 8k W ，w i t had e c r e a s i n gr a t eo f3 ％． K e yw o r d s g e n e t i ca l g o r i t h m s ；m i n ev e n t i l a t i o nn e t w o r kso p t i m i z a t i o nm o d e l ；p e n a l t yf u n c t i o n s ；s i m u l a t e da n n e a l i n ga l g o r i t h m s 矿井通风的根本目的就是满足井下各用风地 点安全生产对新鲜空气的需要．因此对流入井下的 风流不能放任自流，必须按需分配．矿井通风网络 是一个关联程度很高的复杂系统，其中一条分支的 风量有可能通过在多条分支中安设凋节设施而改 变．因此，能满足通风需求的控风方案多种多样．如 何确定一种既能满足通风需求和生产条件的限制、 符合有关法规规定，又能使矿井通风所需的费用最 少的控风方案，是矿井通风安全技术工作者十分关 注的问题，也是长期以来通风界研究的热点和难点 收稿日期Z 0 0 7 0 1 0 1 ．基盒项目国家自然科学基金资助项目 5 0 5 3 4 0 9 0 ，5 0 5 7 4 0 9 3 } 国家重点基础研究发展 9 7 3 计划 2 0 0 5 c b 2 2 1 5 0 6 ，国家十五重点科技 攻兰项目 2 0 0 5 B A 8 1 3 8 0 7 作者筒介李g r 1 9 7 8 - ．男，河南省太康县人，博士研究生．从事矿井通风系统优化、煤矿安全评价与预耐方面的研究． E - m a i l IJ i a n g _ L e e1 9 7 8 Y a h o o ．c o m ．c t lT e l 0 5 1 6 - 8 3 8 8 5 3 3 1 万方数据 7 9 0 中国矿业大学学报第3 6 卷 之一． 通风网络中部分风量已知，部分风量待求，调 节分支和调节量都待求的风量调节问题，是最一般 的通风网络优化调节问题．解决了这一问题，则通 风网络分析中的许多问题都可以迎刃而解．这一问 题通常可归结为非线性规划问题，传统上采用解析 法或数值迭代法求解．当目标和约束函数状态较为 简单、变量数较少时，采用解析法求解是有效的，可 得到精确解．但是基于矿体赋存环境的复杂性，多 数最优化设计问题的目标和约束函数状态较复杂 而且变量数也较多，因此常采用数值迭代法求 解n 4 ] ．但对于通风网络优化问题中普遍存在的多 峰现象，传统的数值迭代法足有局限性的，往往只 能得到局部最优解而得不到全局最优解．因此不少 学者开始将已经在其它领域取得很好效果的优化 算法引入矿井通风网络优化中，用来解决矿井风量 优化调节问题，并且已经取得了一定的成果”。] ．本 文运用遗传算法对矿井通风网络优化问题进行求 解，并探讨其求解全局最优解的可行性． 1 遗传算法简介 遗传算法 G e n e t i ca l g o r i t h m s ，简称G A 是模 拟生物在自然环境中的遗传和进化过程而形成的 一种自适应全局优化概率搜索算法．它是从代表问 题可能潜在解集的一个种群 p o p u l a t i o n 开始的， 而一个种群则由经过基因 g e n e 编码 c o d i n g 的 一定数目的个体 i n d i v i d u a l 组成．每个个体实际 上是染色体 c h r o m o s o m e 带有特征的实体．初始 代种群产生之后，仿照生物学中适者生存和优胜劣 汰的原理，逐代 g e n e r a t i o n 演化产生出越来越好 的近似解．在每一代，根据问题域中个体的适应度 f i t n e s s 大小挑选 s e l e c t i o n 个体，并借助于自然 遗传学的遗传算子 g e n e t i co p e r a t o r s 进行组台交 叉 c r o s s o v e r 和变异 m u t a t i o n ，产生出代表新的 解集的种群．这个过程将导致种群像自然进化一样 的后代种群比前代更加适应于环境，末代种群中的 最优个体经过解码 d e c o d i n g ，可以作为问题最优 解． 7 遗传算法与传统优化方法相比有很多的优点， 如对于一些无数值概念或很难有数值概念，而只有 代码概念的优化问题具有独特的优越性；比较方便 求解目标函数是无法或很难求导的函数，更适合于 导数不存在的函数的优化问题，以及组合优化问 题；全局搜索能力较强，可以有效的避免陷入局部 最优解，而求得全局最优解等等o ] ． 正因为遗传算法有上述的优点，因此被广泛的 应用在了很多方面，如电网优化“] 、公共交通线网 优化”3 等．而矿井通风网络的特点是联接复杂，大 型，多变量，因而其优化方法应该具有针对性．遗传 算法在理论上是完全可以应用在矿井通风网络优 化方面的，某些特殊优点对弥补传统方法的不足， 具有一定的优越性．因而将遗传算法引入矿井通风 网络优化，从理论上和应用上进行探索性的研究， 是非常重要和有价值的． 2 优化模型建立 由于能够满足通风需求的控风方案一般不只 1 种，因此可以给出一定的优化指标，以比较各种 控风方案的优劣，并在其中选择1 种最佳的方案． 这个优化指标的数学描述就是“目标函数”．在矿井 通风调节中应该使控风方案“安全、经济、可行”．安 全性和可行性一般可以在需风量、风量与调节量的 上下限及分支的可调性中得到反应．因此优化调节 问题的目标函数一般都是从经济方面考虑，即使通 风总费用最小．由于通风费用中风机的能耗占有很 大的比重，通常可直接用风机功率作为目标函数． 优化调节问题的约束方程即为节点风量平衡方程 和回路风压平衡方程，以及所给定的分支可调性， 各个分支的可调节阻力和风量的上、下限等⋯] ． 据此建立的矿井通风网络优化的数学模型为 N F r a i n W ≥IH ．{ lQf ， s ．t ．∑a o O ， 0 ， 江1 ，2 ，⋯，M J l N ∑b 。H ，一P ．一F 。 Q ． 一0 ， i 一1 ，2 ，⋯，M ， Q ．。≤Q ，≤Q ⋯ H ～≤H ，≤H 一， 式中Ⅳ为通风能耗，k W ；N ，为风机台数；N 为分 支数；M 为回路数，M N J 1 ；J 为节点数；H 。 为第{ 个风机的风压，P a ；Q 。为第i 个风机的风量， m V s ；Q 为j 分支的风量，一／s ；H J 为j 分支的风 压，P a ；P ，为i 回路自然风压的代数和，P 一 Ⅳ ∑6 。P ，，只为J 分支的自然风压，P a ；F Q A 为第 J 一1 i 个风机的风压，P a ，F Q 。 一0 ，i N F l ，N F 2 ．．，M ；Q 。。，Q 。；分别为分别风量调节上，下限， m 3 ／s ；H 。m ，H 。；分别为风压调节上、下限，P a ； 万方数据 第6 期李江等遗传算法在矿井通风网络优化申的应用7 9 1 f 1i 节点j 够分支的端点且Q 流向该节点， n 。一{ 一1i 节点为j 分支的端点且Q ，背离该节点， 1 0i 节点不是』分支的端点； f 1J ∈i 且同向， b i 一 Ir a i n { 0 ， Q 址；一Q } 芦 r a i n { 0 ， Q ，一Q 。。 l ， 式中y ，p 均为罚因子． 在罚函数中惩罚参数，即罚因子的选择是非常 重要的．如果罚因子取得过小，会使新目标函数的 适应度主要取决于原目标函数的大小，使惩罚失去 意义，并有可能导致算法过早地收敛于非极值点； 而罚因子取得过大，又会使目标函数的适应度主要 取决于“惩罚项”的大小．由于优化模型的可行解可 能不只一个，所以会影响解的多样性，使得算法不 能收敛于最优解． 为了克服上述缺陷，本文设计了一种动态罚函 数法，即惩罚参数是迭代次数的函数．这种动态罚 函数法参考了模拟退火算法的一些优点，可以被称 为模拟退火罚函数法，罚因子一定义为 1 口一砉， i 一1 ，2 ，⋯，N 一1 ， 1 ‘ T “l a T ．， i 1 ，2 ，⋯，N 一1 ， 式中N 为总进化代数；t 原为进化到第i 代系统 的热力学温度，这里仅是一个参数；a 为一个系数， a ∈ o ，1 ．罚因子口吸取了模拟退火的思想，使丁 逐渐下降，即一逐渐增大，其增加速度由参数来控 制．这样随着进化的不断进行，口逐渐增大，使解群 趋于可行解”2 。1 3 ] ．当然罚因子d 也不能无限增大， 应通过总进化代数N 对其进行控制，当进化结束 后，一将成为一个常量，不再改变． 矿井通风网络优化模型，从目标函数看是要求 一个最小值．而遗传算法是不能直接应用于最小值 问题的，因此不能使用目标函数直接作为适应度函 数．需要对目标函数进行转换，我们采取的转化方 式为 F i t r z 一一厂 z ． 3 优化实例 图1 为一多风机通风网络图，共有1 7 条分支， 1 1 个节点，独立回路数为1 7 1 1 1 7 条，风机 为3 台，分别为分支1 ，2 和3 ．出风节点l l 与进风 节点l 之间的伪分支1 7 没有画出叫． 图1 多风机通风网络 F i g ．1 Am u l t i p l e - f a nv e n t i l a t i o nn e t w o r k 假设的用风分支为5 条，分别为分支4 ，5 ，6 ， 1 0 和1 2 ，用加“* ”来表示，其固定风量分别为2 6 ， 3 1 ，3 1 ，1 和3 2m 3 ／s ．各个分支风阻值的具体数据 在表1 中列出，分支风量是在风机分支风量固定的 情况下自然分风所得出的结果． 该网络的7 条余树分支分别为2 ，4 ，5 ，6 ，7 ， 1 0 ，1 2 ．则7 条独立回路分别为2 一 一3 一 一1 6 万方数据 中国矿业大学学报 第3 6 卷 一1 3 ；4 1 1 7 8 ；5 1 1 一 一1 3 一1 6 3 1 7 8 - - 9 ；6 3 1 7 1 4 ；7 一 一1 5 一 一1 4 一8 9 ； 1 0 - - 1 1 一 一1 3 一 一1 6 一3 一 一1 ；1 2 1 6 3 一1 7 1 4 1 5 ．其中负号代表风流方向与图1 所示 的风流方向相反． 运行程序迭代计算后的结果列在表1 中．对于 装机分支其调节量即为风机的负压． 表1多风机通风网络原始数据和计算结果 T a b l e1 P r i m a r yd a t aa n dc o m p u t e dr e s u l t so fam u l t i p l e - f a nv e n t i l a t i o nn e t w o r k 拄* 表币固定风量的用风分支． 优化结果是否可以被接受不仅要看其目标函 数，还必须符合实际的情况，因此一定要对优化结 果进行检验．较为常用的方法就是将结果带入风网 解算的程序中加以验证．如果优化中的每一条定流 分支在解算结果中都能满足其所需风量，就说明优 化结果是较为优秀的，反之则说明还有改进提高的 必要．因此将上例的优化结果带入风网解算程序， 其结果见表2 ．结果基本能满足需风量的要求． 就优化的目标来讲，优化结果数据中的风机总 能耗应该与优化前的总能耗作一比较，如果总能耗 比优化前有所降低，则说明优化起到了一定的效 果，优化结果就是可以接受的．反之，则说明优化没 有起到作用． 对于本例而言，优化前后的风机总能耗比较见 表3 ．从实施结果来看通风系统总能耗降低了7 ．7 8 k W ，其下降幅度约为3 ％．因此这一优化结果是可 以接受的． 寰2多风机通风网络风网解算结果 T a b l e2 R e s u l t s0 fv e n t g a t i o nn e t w o r kc a l c u l a t i o no n 分支号 ≯影。 调嚣7分支号 m 风3 ．1 5 ／一1 调k 节P 量a ／ 12 5 ．0 019 1 61 0 。1 ．0 30 ．0 1 1 25 4 ．9 42 ．1 7 91 13 I ．4 00 34 0 ．0 62 ．0 5 51 2 ’3 2 ．1 10 4 2 6 ．0 3 01 3 2 3 ．5 40 5 ‘3 0 ．3 701 45 7 ．5 70 6 。3 1 ．4 B 01 52 6 ．0 90 76 ．0 201 68 ．5 8O 86 2 ．4 301 71 2 0 ．0 00 93 6 ．3 90 衰3 通风总能耗比较 T a b l e3 C o m p a r i s o nb e t w e e nt o t a lv e n t i l a t i o np o w e rc o n s u m p t i o n 4 结论 1 作为矿井通风系统网络优化模型，以风机 能耗为目标函数，以矿井通风网路节点风量平衡方 程、回路风压平衡方程、分支可调性、风量和调节量 上下限等为约束方程的非线性规划数学模型，能够 在满足通风需求和生产条件的限制、符合有关法规 规定的基础上，使矿井通风所需的费用最少这一优 化目标．因而适用于求解各种矿井通风网络优化调 节问题． 万方数据 第6 期李江等遗传算法在矿井通风网络优化中的应用7 9 3 2 参考模拟退火算法的一些优点，设计出一 种动态的不可微精确罚函数法，即模拟退火罚函数 法，对矿井通风系统网络优化模型的约束方程进行 处理，较好的解决了遗传算法不能用于处理含有等 式约束的优化问题的缺陷．使遗传算法能够应用于 矿井通风系统网络优化模型． 3 通过将遗传算法应用于一个简单的多风机 通风网络，对该网络风流定量优化控制问题进行求 解，计算结果表明通风系统总能耗降低了7 ．7 8 k W ，下降了约3 ％．说明遗传算法克服了传统通风 网络优化算法的某些局限性，能以很大的概率找到 所求问题的全局最优解．并且拥有算法先进、可靠 性好，适用性广等优点． 参考文献 [ 1 ] 黄元平，李湖生．矿井通风网络优化调节问题的非 线性规划解法[ J 3 ．煤炭学报，1 9 9 5 ，Z O 1 1 4 2 0 ， H U A N GY u a n - p i n g ，L IH u - s h e n g ．S o l u t i o no fp r o b - l e m sr e l e v a n tt oo p t i m a lc o n t r o lo fm i n ev e n t i l a t i o n n e t w o r kb yn o n - l i n e a rp r o g r a m m i n gt e c h n i q u e [ J ] ， J o u r n a lo f C h i n a C o a lS o c i e t y ，1 9 9 5 ，2 0 1 1 4 2 0 ． [ 2 ] 李湖生．矿井接需分风优化调节的研究进展[ J ] ．矿 业安全与环保，1 9 9 7 ，1 j 8 - 1 1 ． L IH u - s h e n g ．D e v e l o p m e n to fo p t i m i z e dr e g u l a t i o no f a i rd i s t r i b u t i o na c c o r d i n gt od e m a n di nx n i n e [ J ] ． M i n i n gS a f e t y ＆E n v i r o n m e n t a lP r o t e c t i o n ．1 9 9 7 ，1 { 8 - 1 1 ． [ 3 3 钟茂华，陈宝智．基于遗传算法的矿井火灾时期风 流优化控制口] ．煤炭学报，1 9 9 8 ，2 3 2 1 6 1 1 6 4 ． Z H O N GM a o - h u a tC H E NB a o - z h i ．O p t i m a lc o n t r o l o fa i r f l o wi nam i n ef i r eb a s e do ng e n e t i ca l g o r i t h m [ J ] ．J o u r n a lo f C h i n a C o a lS o c i e t y ，1 9 9 8 ，2 9 2 1 6 1 1 6 4 ． [ 4 ] 张玉祥．杨昌玲．快速模拟退火算法及矿井通风网 络全局优化[ J ] ．武汉工业大学学报，1 9 9 8 ，2 0 1 4 0 一4 2 ． Z H A N GY u - x i a n g ，Y A N GC h a n w l i n g ．Af a s ts i m u - l a t e da n n e a l i n ga l g o r i t h ma n di t sa p 讲i c a t i o nt og l o b a l o p t i m a ld e s i g no fv e n t i l a t i o nn e t w o r ki nm i n e [ J ] ． J o u r n a lo fW u h a nU n i v e r s i t yo fT e c h n o l o g y ，1 9 9 8 ，2 0 1 4 0 - 4 2 ． [ s J 王小平，曹立萌．遗传算法理论，应用与软件实现 [ M ] ．西安西安交通大学出版社．2 0 0 2 7 ． [ 6 ] 谢敬东，王磊，唐国庆，遗传算法在多目标电两优 化规划中的应用[ J ] ．电力系统自动化。1 9 9 8 ，2 2 1 0 2 0 2 2 ． X 1 EJ i n g - d o n g ，W A N GL e i ，T A N GG u o - q i n g ．T h e a p p l i c a t i o no fg e n e t i ca l g o r i t h mi nt h em u l t i - o b j e c t i v e t r a n s m i s s i o nn e t w o r ko p t i m i z a t i o np l a n n i n g [ J ] ．A u t o m a t i o no fE l e c t r i cP o w e rS y s t e m s ．1 9 9 8 ，2 2 1 0 t 2 0 4 2 ． [ 7 ] 冯树民，陈洪仁．公共交通线网优化研究[ 刀．哈尔 滨工业大学学报，2 0 0 5 ．3 7 5 6 9 1 6 9 3 ． F E N GS h u - m i n ，C H E NH o n g - r e mS t u d yo fp u b l i c t r a n s i tn e t w o r ko p t i m i z a t i o nm e t h o d [ J ] ．J o u r n a lo f H a r b i nI n s t i t u t eo fT e c h n o l o g y ，2 0 0 5 ，3 7 5 6 9 1 6 9 3 ． [ 8 ] 张惠忱．计算机在矿井通风中的应用[ M ] ．徐州中 国矿业大学出版社，1 9 9 2 1 2 2 0 ． [ 9 3 王战权，赵朝义，云庆夏．用遗传算法进行通风系统 优化的研究[ J ] ．矿业安全与环保，1 9 9 9 ，6 68 ． W A N GZ h a n - q u a n ，Z H A OC h a o - y i ，Y U NQ i n g - x i a ． R e s e a r c h0 1 1o p t i m i z a t i o no fv e n t i l a t i o ns y s t e mb yg e - r e t i ea l g o r i t h m [ J ] ．M i n i n gS a f e t y8 LE n v i r o n m e n t a l P r o t e c t i o n ，1 9 9 9 ，6 6 8 ． [ 1 0 3 解可新，韩立兴，林友联．最优化方法[ M ] ．天津 天津大学出版社．1 9 9 7 1 5 2 - 1 6 4 ． [ 1 1 ] 郭伟，席裕庚．基于精确罚函数法的遗传算法求 解时延约束组播路由问题[ 刀．电子学报，2 0 0 1 ，2 9 4 5 0 6 5 0 9 ． G U OW e i ．X 1Y u - g e n g ．S o l v i n gd e l a yc o n s t r a i n e d m u l t i c a s tr o u t i n gp r o b l e mw i t hg e n e t i ca l g o r i t h m b a s e do na o e u r a e yp e n a l t yf u n c t i o n [ J ] ．A e t aE l e c t r o n i c aS i n i e a ．Z 0 0 1 2 9 4 5 0 6 5 0 9 ． [ 1 2 ] 吴志远，邵惠鹤。吴新余、基于遗传算法的退火精 确罚函数非线性约束优化方法[ J ] ．控制与决策， 】9 9 8 ．1 3 2 1 3 6 1 4 0 ． W UZ h i - y u a n ，S H A OH u i h e ，W UX i m y u ．A n n e a l i n ga c c u r a c yp e n a l t yf u n c t i o nb a s e dn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o nm e t h o dw i t hg e n e t i ca l g o - r i t h m s [ J ] ．C o n t r o la n dD e c i s i o n ，1 9 9 8 ，1 3 2 1 3 6 1 4 0 ． [ 1 3 ] 严刚峰。赵宪生．基于模拟退火一遗传算法的过程控 制参散寻优研究口] ．四川I 大学学报自然科学版． 2 0 0 3 ，4 0 5 8 7 4 - 8 7 7 ． Y A NG a n g - f e n g ．Z H A OX i a n - s h e n g ．T h er e s e a r c h o fb a s e do ns i m u l a t e da n n e a l i n ga n dg e n e t i ca l g o - r i t h r n ’so p t i m a ls e l e c t i o no fc o n t r o l sp a r a m e t e r [ J ] ． J o u r n a lo fS i c h u a nU n i v e r s i t y N a t u r a lS c i e n c eE d i - t i o n ，2 0 0 3 ，4 0 5 8 7 4 8 7 7 ． 责任编辑王继红 万方数据