基于遗传算法的一体化通风网络优化算法
厍向阳1, 2，常新坦2
(1. 西安科技大学 计算机科学与技术学院，陕西 西安，710054；
2. 西安科技大学 西部矿井开采及灾害防治教育部重点实验室，陕西 西安，710054)
摘要：概括混合型一体化通风网络优化的模型，分析目前混合型通风网络优化的4种求解方法优缺点。针对混合型通风网络优化的要求，提出混合型通风网络风量分配和风流调控一体化的优化思路。在通风网络理论和图论的基础上，引入遗传算法随机产生2个动态网络的邻接矩阵和余树弦风量值，使用附有条件的最小支撑树算法产生2个最小支撑树，进而求得相应的回路矩阵。通过余树弦风量值和回路矩阵等分别计算通风网络风量分配值和风阻调节值，基于通风总功率和约束条件构建广义最小化目标函数，依此对分风和调风方案进行评价，使用遗传算法中进化算子对分风和调风方案实施进化操作，最终得到满意解。研究结果表明：该算法是严格数学意义上全局优化算法，解决调风地点约束的通风网络优化问题，利用网络结点流量平衡的等式约束条件，减少最优化模型中变量数目，提高算法效率。
关键词：
中图分类号：TP393.3 文献标志码：A 文章编号：1672-7207(2011)06-1676-09
Integrative optimization algorithm of min ventilation networks based on genetic algorithm
SHE Xiang-yang1, 2, CHANG Xin-tan2
(1. Computer Science and Technology College, Xi’ an University of Science and Technology, Xi’an 710054, China;
2. Key Laboratory of Western Mine Exploitation and Hazard Prevention,
Xi’an University of Science and Technology, Xi’an 710054, China)
Abstract: The mixing optimization model of min ventilation networks was summed up, the four way advantage and disadvantages of sloving mixing ventilation networks optimization problem were analysed.Facing the demand of mixing ventilation networks, integrative optimization way optimizing min ventilation networks was put forward. The two adjacency matrix of dynamic networks were initialized on random according to genetic algorithm thought based on min ventilation networks theory and graph theory. The two minimum spanning tree of the dynamic network was searched by the way of minimum spanning tree algorithm confined in conditions,two independence circuit matrix were calculated, and then the ventilation volume of networks branchs and resistance adjusting values of remaining tree branchs were calculated by the ventilation volume of remaining tree branchs and circuit matrix. The generalized objective function is set up in the sum ventilation power and restriction conditions, The ventilation volume distributing and adjusting schemes were judged by the generalized objective function, and schemes codes were evolved by genetic operator. Finally, the satisfaction ventilation volume distribution and adjustment schemes was attained by iterative. The algorithm is a globe optimization in strict mathematics define. The algorithm deals with adjusting location restriction very well. The results show that the algorithm reduces variable number in mode, and is good at efficiency, through making use of the node int-flow and out-flow balance restriction.
Key words: ventilation networks optimization; genetic algorithm; optimization theory; minimum spanning tree
矿井通风系统的任务是利用通风动力，以最经济的方式向井下各用风地点提供质优量足的新鲜空气，以保证井下作业人员的生存、安全和良好的工作环境。随着矿井开采向深度、广度扩展和机械化程度不断提高，矿井通风网络安全运行、维护和管理成本不断增加，通风网络优化研究与应用的重要性日渐凸现出来。矿井通风网络可分为自然分风网络、控制型分风网络和混合型分风网络3类。已经证明：在满足矿井总风量要求的条件下，自然分风网络的功耗自动达到最 小[1-2]。当矿井采用自然通风网络分风解算后不能满足矿井用风地点的风量要求时，就要采用一定的调节措施满足矿井安全生产的实际需要。在控制型分风网络中，各分支的风阻和风量已知，其风压也自然确定，因而这种网络的优化与调节问题是一个线性规划问题，求解方法有单纯形法、关键路径法、回路法和道路法等[2-4]。自然分风网络解算、控制型分风网络优化目前已经得到较好的解决。混合型分风网络优化是在满足网络需风分支的风量、网络风量平衡、网络风压平衡和调风地点约束条件下，使得通风网络运行的总功率最小化。混合型通风网络优化模型是一个非凸规划模型，难以寻找可靠的求解方法。调节设施的位置待定，通风网络优化模型变量非常多，因而，混合型通风网络优化模型的求解十分困难，成为目前研究的重点和难点。陈开岩等[3-9]研究用非线性规划的方法来解决矿井通风网络优化调节问题，但存在函数求导、矩阵求逆、初始值敏感和算法效率低的缺陷。王惠宾等[1，10]将通风网络优化问题分解为风量最优分配和最优调节2个子问题，并给出了求解风量最优分配问题的非线性规划数学模型和求解方法。这种方法减少非线性规划问题的规模，对于混合型通风网络的优化调节具有一定的理论和实际意义，但是，它将混合型通风网络优化问题转化为局部最优化问题。由于风量分配优化模型仍然为非凸、非线性优化模型，同样存在传统非线性规划方法的缺陷。李湖生[11]介绍了1995年以前矿井按需分风优化调节方面的研究进展，分析了各种方法的特点和局限性，具有重要的参考价值。张玉祥等[12-15]将遗传算法引入到通风网络优化中，取得了一定成果，但是未能将遗传算法与通风网络理论、图论和矿井实际密切结合，未能很好地解决调风地点约束和大规模通风网络优化问题。本文概括了混合型一体化通风网络优化的模型，归纳了目前混合型通风网络优化的4种求解方法优缺点。针对混合型通风网络优化的要求，提出了混合型通风网络风量分配和风流调控一体化优化思路。在通风网络理论和图论的基础上，引入遗传算法随机产生2个动态网络的邻接矩阵和余树弦分量值，使用附有条件的最小支撑树算法产生2个最小支撑树，进而求得相应的回路矩阵。通过余树弦风量值和回路矩阵等分别计算通风网络风量分配值和风阻调节值，以通风总功率和约束条件构建广义最小化目标函数，依此对调节方案进行评价，使用遗传算法中进化算子对调节方案实施进化操作，最终得到满意解。最后通过典型通风网络实例测试算法的可行性和有效性。
1 一体化通风网络优化模型
对于矿井通风网络G=(V，E)，V和E分别为图G的结点和分支集合，且|V|=m，|E|=n，为图G中结点和分支数，通风网络的独立回路个数b=n-m+1，k条边风量已知，且k≤b。一体化通风网络优化模型如式(1)~(6)所示。
(1)
(2)
(3)
(4)
(5)
(6)
式中：rj为第j分支风阻；qj为第j分支风量；F为安置风机(包括主扇和辅扇)分支标号集合；Δhj为第j分支的阻力调节值；hj为第j分支风压；hNj为第j分支内位能差，亦为自然风压；qj-min为第j分支允许风量下限；qj-max为第j分支允许风量上限；Δhj-min为第j分支允许风压调节下限；Δhj-max为第j分支允许风压调节上限；{cij}为基本回路矩阵；{bij}为基本关联矩阵。
式(1)为优化目标函数，式(2)为风量平衡约束条件，式(3)为风压平衡约束条件，式(5)和式(6)为风量和风压调节上下限约束。当某一分支风量已知时，则式(5)约束变成为qj-min=qj=qj-max；当某一分支不允许安设调风设施时，则式(6)约束变成为Δhj-min=Δhj= Δhj-max=0。故式(5)和式(6)包含通风网络分支风量已知和调风地点约束条件。
混合型一体化通风网络优化模型(1)~(6)中的决策变量为余树弦中未知风量分枝的qj(共b-k=n-m+1-k个)和n个分支的阻力调节值Δhj。由理论分析可知：(1) 该模型是一个非凸规划模型，难以寻找可靠的求解方法；(2) 调节设施的位置待定，整个网络中有n个未知的阻力调节值变量，使得该模型的变量个数非常大。对于非线性规划问题，即使能解，其算法效率也会随着变量个数的增加而急剧降低。欲获得实际可行的模型和算法，应该一方面使模型凸性化，另一方面尽量减少变量数目。
2 通风网络优化模型求解的方法 比较
根据非线性优化理论、遗传算法和通风网络理论研究的已有成果，可将混合性通风网络优化模型求解分成直接法和两步法2个大类。直接法就是直接使用非线性优化理论[1, 4-10]或进化算法[12-14]直接求解，可分为非线性优化方法和遗传算法加罚函数法。两步法就是将混合型通风网络优化问题分成2个子问题：(1) 在满足约束条件下的分风计算；(2) 风量调节优化。按照通风网络分风方法的不同，两步法又可分为自然分风子网(即子网络中不包括需风分支)自然分风加风流调控优化和风量分配优化加风量调控优化[4, 11]2种。各种混合型通风网络优化模型求解方法比较如表1所示。
从表1可以看出：4种方法均具有对调风地点约束的网络优化问题求解不方便的缺点，而这样的约束条件在生产矿井通风网络解算和优化中具有普遍性。2种直接法均具有大规模问题效率很低的缺陷，解决这一问题的出路在于充分利用通风网络理论和图论的相关理论来减少变量个数。两步法求解通风网络模型均并非全局最优解，解决这一问题的关键在于引入图论、通风网络理论和遗传算法进行通风网络优化求解。
表1 混合型通风网络优化模型求解方法比较
Table 1 Comparison between ways sloving mixing ventilation networks
3 基于遗传算法的一体化通风网络优化
3.1 基本思想
在满足风量平衡、部分分支风量已知的约束条件下，风量分配方案对目标函数的贡献取决于分风方案对应的支撑树中余树弦风量。在满足风压平衡、调风地点约束约束的条件下，风流调控方案对目标函数的贡献取决于调风方案对应的支撑树的选取方案和余树弦风压调节值。在部分分支风量已知条件下，分风用支撑树必须需满足已知风量在余树弦上。在限定调风地点约束条件下，调风用最小支撑树必须满足限定的调风分支在余树边上。每一个混合型通风网络的分风调节方案对应调风用最小支撑树、分风用最小支撑树和对应余树弦风量三者的一种组合。为了获得混合型一体化通风网络优化最优方案，可以对满足约束条件的所有组合方案进行遍历，通过比较目标函数值而得到最优方案。对于一般的矿井，通风网络的规模比较大，因此，遍历的方法显然是不可取的。引入遗传算法随机产生多组通风网络风量分配和调控方案，每一个方案对应的一对动态邻接矩阵(仅仅改变通风网络结点的距离，不改变结点间的邻接关系)和分风用支撑树对应余树弦未知风量值初始值。使用附有条件的最小支撑树算法，求解每组相应的2个附有条件的最小支撑树[16]及其对应回路矩阵。根据第1个附有条件的最小支撑树和余树弦中待求的风量初始值，进行风量分配计算，根据第2个附有条件的最小支撑树，进行通风网络风流调节计算。基于通风总功率和约束条件构建广义最小化目标函数[17]，依此对风流分配调节方案进行评价。通过遗传算法中的进化算子对每个方案的编码进行进化操作[18]。最终得到最优的风量分配方案。
3.2 基于遗传算法的一体化通风网络优化算法
算法：基于遗传算法的一体化通风网络优化。
输入：通风网络的分支风量，风阻对应的邻接矩阵，分支调节阻力和风量约束上、下限。
输出：分支风量分配值、风阻调节值和最优目标函数值。
方法：
(1) 随机产生通风网络分风用的动态邻接矩阵，求解对应的附有条件的最小支撑树及其相应独立回路矩阵Cq。
(2) 设置GA相关参数，包括最大迭代次数、群体大小、交叉概率、变异概率。
(3) 群体初始化。使用计算机随机产生规定数量的染色体群体。染色体群中每一串染色体对应两类染色体子串，一类子串是通风网络调风用的动态邻接矩阵。二类子串是余树弦中待求的风量初始值。
(4) 染色体解码。根据独立回路矩阵和对应余树弦风量值，按式(7)进行通风网络风量分配计算。
(7)
式中：qj为分支j的风量；qs为余树弦s的风量，由2部分组成，其中，前k个余树弦风量已知，其余分风量未知，通过对2类子串染色体解码可以获得，它们分别对应式(7)右端的第1项和第2项；csj为独立回路矩阵Cq={csj}中的元素；k为已知风量的分支数目；b为余树弦数目或独立回路个数，b=n-m+1。
根据通风网络调风用的随机矩阵，求解对应的附有条件的最小支撑树及其相应独立回路矩阵CH，按照式(8)进行通风网络调风计算。
(8)
式中：ΔHY为余树弦的阻力调节值向量，
；HY为余树弦的阻力向量，
；HT为树枝的阻力向量，
；C12为对应树枝组成的列，CH=[C11 C12]；PC为通风网络独立回路所含的通风能量矩阵，
。
(5) 群体评价。按照式(9)计算广义目标函数值，对染色体群体进行评价。
(9)
式中：
为优化方案辅助扇风机数量；
为限定的辅助扇风机数量；M1，M2和M3为违反约束条件的惩罚因子、任意大的实数。
(6) 染色体选择。依据评价结果，选择较优的染色体，进行下一步操作。
(7) 染色体交叉。
(8) 染色体变异。
(9) 染色体保留。
(10) 中止条件检验。若小于最大迭代次数，则转向步骤(4)，否则停止迭代，输出分支风量分配值、风阻调节值和最优目标函数值。
若通风网络所有分支风量已知(满足风量平衡条件)，亦混合通风网络演变为控制型通风网络，则步骤(3)，(4)和(5)不需要随即产生分风用邻接矩阵、最小支撑树对应余树弦风量初始值及其相应的计算。对于自然分风子网或自然通风网络分风，可令式(4)和(6)中的Δhj=0，其余不变，同样可以使用该模型进行求解。因此，该算法对于自然分风网络、控制型通风网络同样适用。
4 通风网络优化实例
4.1 简单通风网络优化调控
某一通风网络如图1所示[1, 5]。通风网络有10个结点，16条弧，圈起来的标号为通风网络分支标号，未圈起来的标号为通风网络结点标号，箭头表示风流方向。
图1 简单通风网络图
Fig.1 Simple ventilation networks figure
方案1：主扇安置在分支e1，1台副扇，qj∈(-30，-0.5]
[0.5，40)，Δhj∈(-100，100)(主扇除外)，调风地点没有限制。
方案2：主扇安置在e1，1台副扇，qj∈(-30，-0.5][0.5，40)，Δhj∈(-100，100) (主扇除外)，调分设施必须安置在分支e15，分支e14禁止安置条分设施。
方案3：主扇安置在e1，不允许安置副扇，qj∈(-30，-0.5][0.5，40)，Δhj＜0(主扇除外)；分支e14的风量为-9 s/m3(改变风向)，其余调风地点没有限制。
方案4：主扇安置在e1，不允许安置副扇，qj∈(-30，-0.5][0.5，40)，Δhj＜0(主扇除外)，亦不允许安置副扇；分支e14的风量为-9 s/m3(改变风向)，分支e06禁止安置调风设施。
4个方案的染色体群体规模为50，交叉概率为0.8，变异概率为0.05，迭代2 000次后的结果如表2所示。经过检验计算，4个方案满足通风网络结点风量平衡、独立闭合回路风压闭合和调风地点约束条件。
4.2 多风机通风网络优化调控
某一通风网络如图2所示[4]，有35个结点，55条弧。通风网络分支e9，e11，e12，e14，e15，e27，e28，e29，e37，e40，e41，e42，e45和e46风量已知。
方案1：3台主扇分别安置在e18，e31和e50分支，qj∈(-30，-0.5][0.5，45)，Δhj＜0(主扇除外)，亦不允许安置副扇，调风地点没有限制。
方案2：3台主扇分别安置在e18，e31和e50分支，qj∈(-30，-0.5][0.5，45)，Δhj＜0(主扇除外)，亦不允许安置副扇，e49禁止安设调风设施。
方案3：3台主扇分别安置在e18，e31和e50分支，1台副扇，qj∈(-30，-0.5][0.5，45)，Δhj∈(-50，50)(主扇除外)，调风地点没有限制。
方案4：3台主扇分别安置在e18，e31和e50分支，1台副扇，qj∈(-30，-0.5][0.5，45)，Δhj∈(-50，50)(主扇除外)，e41禁止安设调风设施。
4个方案的染色体群体规模为50，交叉概率为0.8，变异概率为0.05，迭代2 000次后的结果如表3所示。经过检验计算，4个方案满足通风网络结点风量平衡、独立闭合回路风压闭合和调风地点约束条件。
从实验结果分析可得：(1) 该算法可以满足生产实际中混合型通风网络优化的特定要求；(2) 在某一特定的通风网络中，增加副扇数量能降低通风网络的能耗，但增加了通风网络日常风机管理复杂程度，在非常时期，通风网络调控难度增加；(3) 增加额外调风附加约束条件，是以增加通风网络额外的能耗为代价。
表2 简单通风网络优化调控结果
Table 2 Results of ventilation optimization and adjustment on simple ventilation networks
图2 多风机通风网络图
Fig.2 Multiple-fan ventilation networks figure
表3 多风机通风网络优化调控结果
Table 3 Results of ventilation optimization adjustment on multiple-fan ventilation networks
5 结论
(1) 一体化通风网络优化模型减少了变量数目，提高了算法效率。使用图论和通风网络理论时，以分风用最小支撑树对应余树弦中未知风量为风量变量，而风流调节变量数目为调风用最小支撑树对应余树弦数目。
(2) 该方法把遗传算法与最优化理论、图论、通风网络理论有机结合，发挥各自优势，弥补了各自的缺陷。
(3) 该一体化通风网络优化算法可适用于自然分风网络、控制型分风网络和混合型分风网络3类，具有广泛的适应性。
(4) 该方法把通风网络分风、调风作为一个整体来进行优化，因而是一种严格数学意义上的全局最优化求解方法，克服了通风网络优化两步法解算的局部最优解的问题，在理论上具有严密性。
(5) 通过简单通风网络优化和多风机通风网络优化实例的多个方案测试和正确性验证，表明该算法可按照生产需求实现对通风网络的优化调控，具有一定的有效性、可行性和实用性。
(6) 只要通风网络的优化模型在理论上有可行解，本算法便均可进行通风网络优化。
该一体化通风网络优化算法尽管具有上述许多优点，但仅仅适用于正常生产矿井通风网络优化，对于非常时期(如火灾、瓦斯浓度接近爆炸极限)生产矿井通风网络调控并不适用；同时，该算法没有考虑温度、湿度对风流的影响，这有待于下一步研究。
参考文献：
[1] 王惠宾. 矿井通风网络理论与算法[M]. 徐州: 中国矿业大学出版社, 1996: 97-132.
WANG Hui-bin. Theory and algorithm of mine ventilation network[M]. Xuzhou: China University of Mine and Technology Press, 1996: 97-132.
[2] 徐竹云. 矿井通风系统优化原理与设计计算方法[M]. 北京: 冶金工业出版社, 1996: 107-150.
XU Zhu-yun. Optimization theory and computing method of mine ventilation[M]. Beijing: China Metallurgical Industry Press, 1996: 107-150.
[3] 陈开岩. 矿井通风系统优化理论及应用[M]. 徐州: 中国矿业大学出版社, 2003: 51-87.
CHEN Kai-yan. Optimization theory and application of mine ventilation[M]. Xuzhou: China University of Mine and Technology Press, 2003: 51-87.
[4] 李恕和. 矿井通风网络图论[M]. 北京: 煤炭工业出版社, 1984: 112-128.
LI Shu-he. Mine ventilation network graph theory[M]. Beijing: China Coal Industry Publishing House, 1984: 112-128.
[5] HU Wei-min, Longspn I. A computer method for the generalized controlled flow problem in ventilation networks[J]. Mining Science and Technology, 1989, 8(2): 153-168.
[6] Ueng T H, Wang Y J. Analysis of mine ventilation networks using nonlinear programming techniques[J]. Int J of Mining Engineering, 1984(2): 245-252.
[7] 卢新明. 非线性管道网络中的数学规划问题及解法[J]. 应用数学学报, 1989, 12(3): 281-291.
LU Xin-ming. Mathematical programing problems in nonlinear pipeline networks and their solutions[J]. Acta Mathematicae Applicatae Sinica, 1989, 12(3): 281-291.
[8] XU Zhu-yun, WANG Yin-min. Study on optimum ventilation networks using nonlinear programming techniques[C]//Proceedings of 5th US Mine Ventilation Symposium. Morganton: West Virginia University, 1991: 440-444.
[9] HUANG Chang-hong, Wang Y J. Mine ventilation network optimization using the generalized reduced gradient method[C]// Proceeding of the 6th US Mine Ventilation Symposium. Salt Lake City: University of Utah, 1993: 153-161.
[10] 黄元平, 李湖生. 矿井通风网络优化调节问题的非线性规划解法[J]. 煤炭学报, 1995, 20(1): 14-20.
HUANG Yuan-ping, LI Hu-sheng. Solution of problems relevant to optimal control of mine ventilation network by non-linear programming technique[J]. Journal of China Coal Society, 1995, 20(1): 14-20.
[11] 李湖生. 矿井按需分风优化调节的研究进展[J]. 矿业安全与环保, 1997, 1: 8-11.
LI Hu-sheng. Development of optimized regulation of air distribution according to demand in mine[J]. Mining Safety & Environmental Protection, 1997, 1: 8-11.
[12] 张玉祥, 杨昌玲. 快速模拟退火算法及矿井通风网络全局优化[J]. 武汉工业大学学报, 1998, 20(1): 40-42.
ZHANG Yu-xiang, YANG Chang-ling. A fast simulated annealing algorithm and its application to globaloptimal design of ventilation network in mine[J]. Journal of Wuhan University of Technology, 1998, 20(1): 40-42.
[13] 钟茂华, 陈宝智. 基于遗传算法的矿井火灾时期风流优化控制[J]. 煤炭学报, 1998, 23(2): 161-164.
ZHONG Mao-hua, CHEN Bao-zhi. Optimal control of airflow in a mine fire based on genetic algorithm[J]. Journal of China Coal Society, 1998, 23(2): 161-164.
[14] 王战权, 赵朝义, 云庆夏. 用遗传算法进行通风系统优化的研究[J]. 矿业安全与环保, 1999, 6: 6-8.
WANG Zhan-quan, ZHAO Chao-yi, YUN Qing-xia. Research on optimization of ventilation system by genetic algorithm[J]. Mining Safety & Environmental Protection, 1999, 6: 6-8.
[15] 李江, 陈开岩, 林柏泉. 遗传算法在矿井通风网络优化中的应用[J]. 中国矿业大学学报, 2007, 36(6): 789-793.
LI Jiang, CHEN Kai-yan, LIN Bai-quan. Genetic algorithm for optimization of mine ventilation network[J]. Journal of China University of Mining & Technology, 2007, 36(6): 789-793.
[16] 厍向阳, 罗晓霞. 附有条件的的最小支撑树算法[J]. 西安科技大学学报, 2008, 28(4): 771-774.
SHE Xiang-yang, LUO Xiao-xia. Minimum spanning tree algorithm confined in conditions[J]. Journal of Xi’an University of Science and Technology, 2008, 28(4): 771-774.
[17] 陈宝林. 最优化理论与算法[M]. 2版. 北京: 清华大学出版社, 2005: 394-413.
CHEN Bao-lin. Optimization theory and algorithms[M]. 2nd ed. Beijing: Tsinghua University Press, 2005: 394-413.
[18] 玄光男, 程润伟. 遗传算法与工程优化[M]. 于歆杰, 周根贵译. 北京: 清华大学出版社, 2004: 1-9.
XUAN Guang-nan, CHENG Run-wei. Genetic algorithms and engineering optimization[M]. Beijing: Tsinghua University Press, 2004: 1-9.
(编辑 陈爱华)
收稿日期：2010-04-25；修回日期：2010-07-08
基金项目：陕西省自然科学基金资助项目(2009JM7007)；陕西省教育厅专项科研计划项目(08JK354)
通信作者：厍向阳(1968-)，男，陕西周至人，博士后，副教授，从事数据挖掘与智能信息处理、人工智能与模式识别、复杂系统建模与优化等研究；电话：18729075261；E-mail：xianyangshe@sohu.com
