基于遺傳算法的一體化通風網絡優化算法

厙向陽 ，常新坦

(1. 西安科技大學 計算機科學與技術學院，陜西 西安，710054；

2. 西安科技大學 西部礦井開采及災害防治教育部重點實驗室，陜西 西安，710054)

礦井通風系統的任務是利用通風動力，以最經濟的方式向井下各用風地點提供質優量足的新鮮空氣，以保證井下作業人員的生存、安全和良好的工作環境。隨著礦井開采向深度、廣度擴展和機械化程度不斷提高，礦井通風網絡安全運行、維護和管理成本不斷增加，通風網絡優化研究與應用的重要性日漸凸現出來。礦井通風網絡可分為自然分風網絡、控制型分風網絡和混合型分風網絡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)所示。

式中：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]直接求解，可分為非線性優化方法和遺傳算法加罰函數法。兩步法就是將混合型通風網絡優化問題分成 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)進行通風網絡風量分配計算。

式中：qj為分支j的風量；qs為余樹弦s的風量，由2部分組成，其中，前k個余樹弦風量已知，其余分風量未知，通過對2類子串染色體解碼可以獲得，它們分別對應式(7)右端的第1項和第2項；csj為獨立回路矩陣Cq={csj}中的元素；k為已知風量的分支數目；b為余樹弦數目或獨立回路個數，b=n-m+1。

根據通風網絡調風用的隨機矩陣，求解對應的附有條件的最小支撐樹及其相應獨立回路矩陣CH，按照式(8)進行通風網絡調風計算。

式中：ΔHY為余樹弦的阻力調節值向量，為余樹弦的阻力向為樹枝的阻力向量，為對應樹枝組成的列，為通風網絡獨立回路所含的通風能量矩陣，

(5) 群體評價。按照式(9)計算廣義目標函數值，對染色體群體進行評價。

式中：||||輔F為優化方案輔助扇風機數量；輔限N為限定的輔助扇風機數量；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.