基于遺傳算法的通風網絡兩步法風流調節優化算法

厙向陽 ，常新坦，孫藝珍

(1. 西安科技大學 計算機科學與技術學院，陜西 西安，710054；2. 西安科技大學 西部礦井開采及災害防治教育部重點實驗室，陜西 西安，710054)

隨著礦井開采向深度、廣度擴展和機械化程度不斷提高，礦井通風網絡安全運行、維護和管理成本不斷增加，通風網絡優化研究與應用的重要性日漸凸現出來。礦井通風網絡可分為自然分風網絡、控制型分風網絡和混合型分風網絡3類。已經證明，在滿足礦井總風量要求的條件下，自然分風網絡的功耗自動達到最小[1-3]。在控制型分風網絡中，各分支的風阻和風量已知，其風壓也自然確定，這種網絡的優化與調節問題是一個線性規劃問題，求解方法有單純形法、關鍵路徑法、回路法和道路法等[3-5]。自然分風網絡解算、控制型分風網絡優化目前已經得到較好解決。混合型通風網絡優化模型是一個非凸規劃模型，目前還沒有可靠的求解方法。由于調節設施的位置待定，通風網絡優化模型變量數目非常大。因而混合型通風網絡優化模型的求解十分困難，成為目前研究的重點和難點。文獻[4, 6-10]研究用非線性規劃的方法來解決礦井通風網絡優化調節問題，但存在函數求導、矩陣求逆、初始值敏感和算法效率低的缺陷。文獻[1, 11]將通風網絡優化問題分解為風量最優分配和最優調節2個子問題,并給出了求解風量最優分配問題的非線性規劃數學模型和求解方法。這種方法減少了非線性規劃問題的規模, 對于混合型通風網絡的優化調節具有一定的理論和實際意義，由于風量分配優化模型仍然為非凸、非線性優化模型，同樣存在傳統非線性規劃的方法缺陷。李湖生[12]介紹了 1995年以前礦井按需分風優化調節方面的研究進展，分析了各種方法的特點和局限性，具有重要的參考意義。張玉祥等[13-16]將遺傳算法引入到通風網絡優化中，取得了一定成果，但是未能將遺傳算法與通風網絡理論、圖論和礦井實際密切結合，未能很好地解決調風地點約束和大規模通風網絡優化問題。在此，本文作者概括了混合型通風網絡優化的模型，歸納了混合型通風網絡風量最優分配和風流最優調控兩步法優化基本框架。首先，在滿足礦井通風風量需求的基礎上，實現風量分配優化或者自然分風子網進行自然分風計算。然后，結合礦井通風網絡實際調風需求，引入遺傳算法隨機產生動態網絡的鄰接矩陣，使用附有條件的最小支撐樹算法求解部分余樹弦(調風地點)約束下的最小支撐樹和獨立回路矩陣，計算通風網絡分支風阻調節值，在通風總功率和約束條件基礎上構建廣義最小化目標函數，依此對調節方案進行評價，使用遺傳算法中的進化算子對調節方案編碼實施進化操作，最終得到滿意解。最后通過典型通風網絡實例測試算法的可行性和有效性。

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所示。

2.1 混合型通風網絡風量最優分配

在風量平衡、部分分支風量已知的約束條件下，風量分配方案對目標函數的貢獻取決于分風方案對應的支撐樹的選取方案和余樹弦風量的大小。理論上已經證明，在滿足礦井總風量要求的條件下，自然分風網絡的功耗自動達到最小。因此，可以對通風網絡中自然分風分支組成的子網實現自然分風計算，可采用牛頓法、擬牛頓法、斯考特-恒斯雷法、京大一試法、擬線性解法等方法求解，這些方法理論嚴密，求解方便，但存在函數求導，矩陣求逆，對初始值敏感等缺陷。另外一個方法是將混合型通風網絡風量最優分配轉化為一個優化問題[1]，該模型和混合型通風網絡優化模型相比，由于暫時沒有考慮調風問題，變量數目大大減少，但仍是一個非線性優化問題，求解仍有一定難度。

2.2 混合型通風網絡風流最優調控

在滿足風壓平衡、調風地點約束約束的條件下，以網絡運行功率最小化作為目標函數，對通風網絡調風進行優化。通風網絡風流調控有許多成熟的方法，如單純形法、關鍵路徑法、回路法和道路法等。這些方法求解方便快捷，基本上能夠滿足生產實際需求，但是，在最優調控算法和處理調風地點約束的優化方面不完善。

3 基于遺傳算法的通風網絡兩步法風流調節優化算法

3.1 基本思想

按照混合型通風網絡兩步法優化的基本框架，首先進行混合型通風網絡風量分配優化或混合型通風網絡子網自然分風解算，求得混合型通風網絡分支風量。然后將遺傳算法與通風網絡回路法風流調節算法相結合進行混合型通風網絡風流最優調控。

圖1 混合型通風網絡兩步法優化的基本框架Fig.1 Basic frame of two step way on mixing ventilation networks optimization

在滿足風壓平衡、調風地點約束約束的條件下，風流調控方案對目標函數的貢獻取決于調風方案對應的支撐樹的選取方案和余樹弦風壓調節值。在限定調風地點約束條件下，調風用最小支撐樹必須需滿足限定的調風分支在余樹弦上。為了獲得通風網絡風流最優調控方案，可以對滿足限定余樹弦約束的所有支撐樹進行遍歷，通過比較目標函數值而得到最優方案。對于一般的礦井，通風網絡的規模都會比較大，遍歷的方法顯然是不可取的。引入遺傳算法隨機產生多組調控方案，每一個方案對應一個動態鄰接矩陣(僅僅改變通風網絡結點的距離，不改變結點間的鄰接關系)。使用動態網絡條件下最小支撐樹算法，求解每組相應的附有條件的最小支撐樹[17]及其對應回路矩陣。根據回路矩陣計算通風網絡風壓調節值。基于通風總功率和約束條件構建廣義最小化目標函數[18]，依此對每個通風網絡風量調控方案進行評價。通過遺傳算法中的進化操作算子對每個風量調控方案的編碼進行進化操作[19]。最終得到最優的風流調節方案。

3.2 基于遺傳算法的通風網絡兩步法風流調節優化算法

(1) 算法：基于遺傳算法的通風網絡兩步法風流調節優化算法。

(2) 輸入：通風網絡的分支風量，風阻對應的鄰接矩陣，分支調節阻力上、下限。

(3) 輸出：輸出分支風阻調節值和最優目標函數值。

(4) 方法：

Step 1 設置GA相關參數，包括最大迭代次數、群體大小、交叉概率、變異概率。

Step 2 群體初始化。使用計算機隨機產生規定規模的染色體群體。染色體群中每一串染色體對應通風網絡調風用的隨機鄰接矩陣。

Step 3 染色體解碼。根據通風網絡調風用的隨機鄰接矩陣，求解對應的附有條件的最小支撐樹及其相應獨立回路矩陣CH。按照下式進行通風網絡調風計算：

式中：ΔHY為余樹弦的阻力調節值向量，HY為余樹弦的阻力向量，為樹枝的阻力向量，為獨立回路矩陣CH中由與樹枝對應的列組成的子矩陣，為獨立回路矩陣CH中由與余樹枝對應的列組成的子矩陣，為單位方陣；PC為通風網絡獨立回路所含的通風能量和矩陣，。

Step 4 群體評價。按照下式計算廣義目標函數值，依此對染色體群體進行評價。

Step 5 染色體選擇。依據評價結果，選擇較優的染色體，進行下一步操作。

Step 6 染色體交叉。

Step 7 染色體變異。

Step 8 染色體保留。

Step 9 中止條件檢驗。如果小于最大迭代次數，則轉向Step 3，否則停止迭代，輸出分支風阻調節值和最優目標函數值。

4 通風網絡優化實例

4.1 簡單通風網絡優化調控

某一通風網絡如圖2所示[1,5]，通風網絡有10個結點，16條弧，圈起來的數字為通風網絡分支標號，未圈起來的數字為通風網絡結點標號。通風網絡分支編號和分支風阻見表1第1列和第2列。通風網絡中自然分風分支組成的子網實現自然分風計算，計算結果見表1中第3列。

圖2 簡單通風網絡圖Fig.2 Simple ventilation networks figure

方案1：主扇安置在分支e1，Δhj＜0(主扇除外)，亦不允許安置副扇，調風地點沒有限制。

方案2：主扇安置在分支e1，Δhj＜0(主扇除外)，亦不允許安置副扇，分支e7禁止安置調風設施。

方案3：主扇安置在分支e1，允許安置1臺副扇，Δhj∈(-50, 50) (主扇除外)，調風地點沒有限制。

方案4：主扇安置在分支e1，允許安置1臺副扇，Δhj∈(-50, 50) (主扇除外)，分支e14禁止安置調風分設施，分支e9不允許安置副扇。

遺傳算法的染色體群體規模為30，交叉概率0.8，變異概率為0.05，迭代100次后的結果如表1所示。經過檢驗計算，表1中所有方案滿足通風網絡結點風量平衡、獨立閉合回路風壓閉合和調風地點約束條件。

4.2 多風機通風網絡優化調控

某一通風網絡如圖3所示[5]，有35個結點，55條弧。通風網絡分支編號和分支風阻見表2中第1列和第2列。通風網絡中自然分風分支組成的子網實現自然分風計算，計算結果見表2中第3列。

圖3 多風機通風網絡圖Fig.3 Multiple-fan ventilation networks figure

表1 簡單通風網絡優化調控結果Table 1 Results of ventilation optimization adjustment on simple ventilation networks

表2 多風機通風網絡優化調控結果Table 2 Results of ventilation optimization adjustment on multiple-fan ventilation networks

方案1：3臺主扇分別安置在分支e18，e31和e50，Δhj＜0(主扇除外)，亦不允許安置副扇，調風地點沒有限制。

方案2：3臺主扇分別安置在分支e18，e31和e50，Δhj＜0(主扇除外)，亦不允許安置副扇，分支e28禁止安設調風設施。

方案3：3臺主扇分別安置在分支e18，e31和e50，1 臺副扇，Δhj∈(-50, 50) (主扇除外)。

方案4：3臺主扇分別安置在分支e18，e31和e50，1臺副扇，Δhj∈(-50, 50) (主扇除外)，分支e22不允許安置副扇。

4個方案的染色體群體規模為30，交叉概率0.8，變異概率為0.05，迭代100次后的結果如表2所示。經過檢驗計算，4個方案滿足通風網絡優化模型(1)～(6)中的約束條件。

從實驗結果分析可得：(1) 該算法可以滿足生產實際中混合型通風網絡優化的特定要求；(2) 在某一特定的通風網絡中，科學合理的增加副扇數量，會降低能耗，但增加了通風網絡日常風機管理復雜程度，在礦井災變時期，通風網絡調控難度增加；(3) 增加額外調風附加約束條件是以增加通風網絡額外的能耗為代價。

5 結論

(1) 兩步法思想把混合型通風網絡優化問題轉化為通風網絡風量分配優化和通風網絡調控優化兩個問題，大大減小優化模型的變量數目，提高了算法的效率。

(2) 該方法把遺傳算法和通風網絡回路法風流調節有機結合，發揮各自優勢，彌補了各自的缺陷。

(3) 該方法可以方便地解決調風地點約束的通風網絡優化求解問題。

(4) 通過簡單通風網絡優化和多風機通風網絡優化實例的多個方案的測試和正確性驗證，表明該算法可按照生產需求實現對通風網絡的優化調控，具有一定的有效性、可行性和實用性。

(5) 只要通風網絡的優化模型理論上有解，本算法均可進行通風網絡優化。

[1] 王惠賓. 礦井通風網絡理論與算法[M]. 徐州: 中國礦業大學出版社, 1996: 97-100.WANG Hui-bin. Theory and algorithm of mine ventilation network[M]. Xuzhou: China University of Mine and Technology Press, 1996: 97-100.

[2] Hartman H L. Mine ventilation and air conditioning[M]. New York: John Wiley & Sons, 1982: 483-516.

[3] 徐竹云. 礦井通風系統優化原理與設計計算方法[M]. 北京:冶金工業出版社, 1996: 107-128.XU Zhu-yun. Optimization theory and computing method of mine ventilation[M]. Beijing: China Metallurgical Industry Press,1996: 107-128.

[4] 陳開巖. 礦井通風系統優化理論及應用[M]. 徐州: 中國礦業大學出版社, 2003: 71-87.CHEN Kai-yan. Optimization theory and application of mine ventilation[M]. Xuzhou: China University of Mine and Technology Press, 2003: 71-87.

[5] 李恕和. 礦井通風網絡圖論[M]. 北京: 煤炭工業出版社,1984: 112-133.LI Shu-he. Mine ventilation network graph theory[M]. Beijing:China Coal Industry Publishing House, 1984: 112-133.

[6] 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.

[7] Ueng T H, Wang Y J. Analysis of mine ventilation networks using nonlinear programming techniques[J]. International Journal of Mining Engineering, 1984, 3(2): 245-252.

[8] 盧新明. 非線性管道網絡中的數學規劃問題及解法[J]. 應用數學學報, 1989, 12(3): 281-291.LU Xin-ming. Mathematical programming problems in nonlinear pipeline networks and their solutions[J]. Acta Mathematicae Applicatae Sinica, 1989, 12(3): 281-291.

[9] 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.

[10] 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.

[11] 黃元平, 李湖生. 礦井通風網絡優化調節問題的非線性規劃解法[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.

[12] 李湖生. 礦井按需分風優化調節的研究進展[J]. 礦業安全與環保, 1997, 24(1): 8-11.LI Hu-sheng. Development of optimized regulation of air distribution according to demand in mine[J]. Mining Safety &Environmental Protection, 1997, 24(1): 8-11.

[13] 張玉祥, 楊昌玲. 快速模擬退火算法及礦井通風網絡全局優化[J]. 武漢工業大學學報, 1998, 20(1): 40-42.ZHANG Yu-xiang, YANG Chang-ling. A fast simulated annealing algorithm and its application to global optimal design of ventilation network in mine[J]. Journal of Wuhan University of Technology, 1998, 20(1): 40-42.

[14] 鐘茂華, 陳寶智. 基于遺傳算法的礦井火災時期風流優化控制[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.

[15] 王戰權, 趙朝義, 云慶夏. 用遺傳算法進行通風系統優化的研究[J]. 礦業安全與環保, 1999, 22(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, 22(6): 6-8.

[16] 李江, 陳開巖, 林柏泉. 遺傳算法在礦井通風網絡優化中的應用[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.

[17] 厙向陽, 羅曉霞. 附有條件的最小支撐樹算法[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.

[18] 陳寶林. 最優化理論與算法[M]. 2版. 北京: 清華大學出版社,2005: 394-413.CHEN Bao-lin. Optimization theory and algorithms[M]. 2nd ed.Beijing: Tsinghua University Press, 2005: 394-413.

[19] 玄光男, 程潤偉. 遺傳算法與工程優化[M]. 于歆杰, 周根貴,譯. 北京: 清華大學出版社, 2004: 1-9.XUAN Guang-nan, CHENG Run-wei. Genetic algorithms and engineering optimization[M]. YU Xin-jie, ZHOU Gen-gui,translate. Beijing: Tsinghua University Press, 2004: 1-9.