精英遺傳算法在曝氣鼓風(fēng)機(jī)組調(diào)度上的應(yīng)用

1、精英遺傳算法在曝氣鼓風(fēng)機(jī)組調(diào)度上的應(yīng)用楊光年祁偉 2周軍1 （ 連云港杰瑞深軟科技有限公司 連云港 222000）2（南京信息工程大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院 南京 210044）33 （ 連云港杰瑞深軟科技有限公司 連云港 222000）摘 要目前， 我國(guó)污水處理工藝主要依靠曝氣鼓風(fēng)機(jī)維持生物化學(xué)反映的溶氧環(huán)境，使污水中的有機(jī)污染物轉(zhuǎn)化為無害物質(zhì)。對(duì)曝氣鼓風(fēng)機(jī)資源的調(diào)度，是污水處理行業(yè)的關(guān)鍵問題。而傳統(tǒng)的調(diào)度算法，存在 一定的缺陷，如不能很好的滿足供氣量與能耗的要求，與最優(yōu)解存在較大的偏差等。本文提出了基于改進(jìn) 遺傳算法的資源調(diào)度策略， 采用了逐次逼近最優(yōu)保存策略和混合交叉等算法， 實(shí)現(xiàn)曝氣鼓

2、風(fēng)機(jī)資源的調(diào)度。 通過仿真試驗(yàn)表明，應(yīng)用遺傳算法實(shí)現(xiàn)的資源調(diào)度，能夠有效的減少系統(tǒng)總執(zhí)行時(shí)間和任務(wù)完成時(shí)間，具 有較強(qiáng)的穩(wěn)定性和適應(yīng)性。關(guān)鍵詞 遺傳算法 資源調(diào)度 混合交叉 擇優(yōu)保存Elite genetic algorithm application on blower resource scheduling1 2 2Yang guang nian Qi Wei Zhou Jun1（Jari deepsoft technology ltd, Lianyungang 222000, China）2（Department of Computer Science and Technology ,

3、Nanjing University of Information Science & Technology, Nanjing 210044, China）3（Jari deepsoft technology ltd, Lianyungang 222000, China）Abstract Now, Our sewage treatment industry mainly depend on the blower of aeration act as metabolic, absorbed in the toxic substances. Blower resources managem

4、ent is the key issue of sewage treatment. Traditional resource scheduling algorithm exist some defects , for example it can not well meet the quality requirements and can not get the Optimal solution. This article give an new resource scheduling method based on Improved genetic algorithm. It achieve

5、s grid resource scheduling by using real number encoding and activities point crossover. Experiments show that genetic algorithm can reduce excuting time and task completion time,and further improve the scalability of resource scheduling model.This algorithm has stability and high efficience in grid

6、 enviroment.Keywords Genetic algorithm Resource scheduling Cross Selection of the best preserved.0 引 言Now, Our sewage treatment industry mainly depend on the blower of aeration act as metabolic, absorbed in the toxic substances目. 前我國(guó)城市污水 處理較多采用微生物的代謝作用，使污水中呈溶 解、膠體狀態(tài)的有機(jī)污染物轉(zhuǎn)化為穩(wěn)定的無害物 質(zhì)。 Biological proc

7、ess is a complicated process of chemical reactions.生物處理過程是個(gè)復(fù)雜的生物化 學(xué)反應(yīng)過程，通過曝氣維持好溶氧環(huán)境是其中一個(gè) 非常重要的環(huán)節(jié)。鼓風(fēng)機(jī)作為污水處理曝氣環(huán)節(jié)中 經(jīng)常采用的機(jī)械設(shè)備，對(duì)污水處理廠的正常運(yùn)行起 著重要作用，要保證不同污水處理工藝對(duì)鼓風(fēng)曝氣 的控制要求，鼓風(fēng)曝氣系統(tǒng)的精細(xì)化控制對(duì)整個(gè)污省重點(diǎn)技術(shù)創(chuàng)新項(xiàng)目 作者簡(jiǎn)介：楊光年，研究方向：工業(yè)控制； 祁偉，研究方向：高性能計(jì)算；周軍，研究方向：工業(yè)控制 水處理廠的節(jié)能運(yùn)行意義重大。 污水處理系統(tǒng)中，最關(guān)鍵的問題是對(duì)多臺(tái)鼓風(fēng) 機(jī)的控制，在保證系統(tǒng)安全性，穩(wěn)定性等性能指標(biāo) 的前提下

8、，讓鼓風(fēng)機(jī)組以最低的能耗滿足系統(tǒng)的需 求。本文將改進(jìn)的遺傳算法， 應(yīng)用于風(fēng)機(jī)組的控制， 實(shí)驗(yàn)表明有很好的效果，給曝風(fēng)機(jī)組控制提供了一 種新的方法。1 曝氣鼓風(fēng)機(jī)自動(dòng)控制系統(tǒng)1.1 系統(tǒng)組成 曝氣鼓風(fēng)機(jī)自動(dòng)控制系統(tǒng)由就地控制柜 （LCP ） 和主控制柜（ MCP ）組成。主控制器（ MCP）對(duì)二 至十五臺(tái)曝氣鼓風(fēng)機(jī)進(jìn)行控制，負(fù)責(zé)整個(gè)系統(tǒng)的聯(lián) 動(dòng)控制，根據(jù)空氣總管出口的壓力和流量的需求控制各臺(tái)鼓風(fēng)機(jī)的啟停，以滿足所需的空氣供應(yīng)量， 并根據(jù)各鼓風(fēng)機(jī)的優(yōu)先權(quán)的設(shè)定選擇運(yùn)行狀態(tài)；就 地控制器( LCP )控制本臺(tái)機(jī)組的正常運(yùn)行，并根 據(jù)進(jìn)出口壓差和流量需求自動(dòng)調(diào)節(jié)出口/入口導(dǎo)葉的開度，在滿足空氣流量供給

9、需要的前提下盡量降 低系統(tǒng)功耗。圖 1 系統(tǒng)總體架構(gòu)1.2 系統(tǒng)性能指標(biāo)(1) 流量控制 通過出口導(dǎo)葉的開度的變化來控制進(jìn)氣流量 的大小。在“遠(yuǎn)程”控制方式下，由主控制系統(tǒng) (MCP)根據(jù)總管進(jìn)氣的需求量調(diào)節(jié)出口導(dǎo)葉的開 度；在“就地”控制方式下，由人工設(shè)定出口導(dǎo)葉 的開度。(2) 功耗控制 - 通過出口導(dǎo)葉開度的變化來控制進(jìn)氣流量的 大小。在“遠(yuǎn)程”控制方式下， 由主控制系統(tǒng) (MCP) 根據(jù)總管進(jìn)氣的需求量調(diào)節(jié)出口導(dǎo)葉的開度；在 “就地” 控制方式下， 由人工設(shè)定出口導(dǎo)葉的開度。(3) 優(yōu)先權(quán)分配 每一臺(tái)鼓風(fēng)機(jī)都配有唯一的優(yōu)先權(quán)，所選的優(yōu) 先權(quán)決定了由主控柜控制的鼓風(fēng)機(jī)起動(dòng)順序。優(yōu)先 權(quán)設(shè)

10、置必須連續(xù)，無效的優(yōu)先權(quán)設(shè)置系統(tǒng)不能接受 并做出提示。(4) 多機(jī)啟動(dòng)補(bǔ)償 啟動(dòng)補(bǔ)償只在鼓風(fēng)機(jī)啟動(dòng)過程中使用。主控柜 發(fā)出起動(dòng)指令給優(yōu)先權(quán)為 2 的就地控制柜，啟動(dòng)鼓 風(fēng)機(jī)時(shí)，起動(dòng)補(bǔ)償定時(shí)器激活，主控柜控制優(yōu)先權(quán) 為 1 的鼓風(fēng)機(jī)的風(fēng)量控制直到定時(shí)結(jié)束，當(dāng)鼓風(fēng)機(jī) 的啟動(dòng)補(bǔ)償時(shí)間結(jié)束時(shí)，優(yōu)先權(quán)為的鼓風(fēng)機(jī)供風(fēng) 量增加，直至其到達(dá)最大供風(fēng)量，然后系統(tǒng)控制優(yōu) 先權(quán)為 2 的鼓風(fēng)機(jī)工作。1.3 系統(tǒng)分析該系統(tǒng)由主控制器( MCP )對(duì)整個(gè)風(fēng)機(jī)組進(jìn) 行統(tǒng)一管理，每個(gè)風(fēng)機(jī)有很多性能指標(biāo)如：溫度， 可靠性， 安全性， 出口導(dǎo)葉開度， 震動(dòng)幅度等。 MCP 控制整個(gè)風(fēng)機(jī)組，在保證系統(tǒng)安全性，可靠性等基 礎(chǔ)上，讓

11、風(fēng)機(jī)產(chǎn)生的風(fēng)力之和滿足系統(tǒng)風(fēng)力的需 求。從以上的分析來看，如果把每個(gè)風(fēng)機(jī)當(dāng)成一個(gè) 資源，而風(fēng)機(jī)的性能， 當(dāng)成資源的參數(shù)。 那么，MCP 的調(diào)度算法，可看成資源調(diào)度。從而把曝風(fēng)機(jī)調(diào)度 問題轉(zhuǎn)化為一個(gè)多重目標(biāo)約束問題。而多重目標(biāo)約 束問題可用遺傳算法來解決，實(shí)驗(yàn)表明有很好的性 能。本文對(duì)傳統(tǒng)的遺傳算法加以改進(jìn)，在傳統(tǒng)的遺 傳算法上，加上混合交叉算法和最優(yōu)保存策略，應(yīng) 用于 MCP 的控制，實(shí)驗(yàn)證明，該算法具有很好的 性能。2 算法實(shí)現(xiàn)2.1 曝氣鼓風(fēng)機(jī)調(diào)度的數(shù)學(xué)模型 曝氣鼓風(fēng)機(jī)組調(diào)度方案要滿足各種用戶不同 的需求，包含了承受時(shí)間、計(jì)算量、資源數(shù)、可靠 性、安全性等，曝氣鼓風(fēng)機(jī)組調(diào)度可描述為從一定

12、資源庫(kù)中抽取滿足調(diào)度目標(biāo)要求的一組曝氣鼓風(fēng) 機(jī)， 從而把調(diào)度問題轉(zhuǎn)化為一個(gè)多重約束目標(biāo)問 題。假設(shè)資源需求包含 m 個(gè)資源、 n 個(gè)指標(biāo)，因 此，在資源調(diào)度前，首先建立資源控制指標(biāo)相應(yīng)的 目標(biāo)矩陣。圖 6 資源模型S 的每一行由某一曝氣鼓風(fēng)機(jī)的控制指標(biāo)組 成，如承受時(shí)間、計(jì)算量、資源數(shù)、可靠性、安全 性等，并且這些屬性指標(biāo)都進(jìn)行編碼表示成二進(jìn)制 形式，而每一列是資源庫(kù)中某一指標(biāo)的全部取值。 由上面對(duì)問題的描述可以看出，曝氣鼓風(fēng)機(jī)組調(diào)度 問題是一個(gè)多重約束目標(biāo)問題。 假設(shè)資源庫(kù)中有 m 個(gè)曝氣鼓風(fēng)機(jī)，隨著 m 的增大，計(jì)算的復(fù)雜度無 論在時(shí)間還是空間上都將成指數(shù)增長(zhǎng)，這對(duì)于規(guī)模 較大的調(diào)度問題是

13、難以接受的，所以有必要尋找新 的求解方法。本文引入遺傳算法并加以改進(jìn)用于對(duì) 該問題進(jìn)行求解。2.2 曝氣鼓風(fēng)機(jī)調(diào)度方案的評(píng)價(jià)策略 評(píng)價(jià)一個(gè)曝氣鼓風(fēng)機(jī)組調(diào)度方案的滿足程度， 即是判斷該調(diào)度方案里所有曝氣鼓風(fēng)機(jī)滿足程度 之和，而每個(gè)曝氣鼓風(fēng)機(jī)的滿足程度，為該曝氣鼓 風(fēng)機(jī)的各個(gè)屬性的滿足程度之和。曝氣鼓風(fēng)機(jī)屬性的 滿足程度 Attrubt i D(p) A(p) D(p) (4) D ( p)為目標(biāo)值， A(p) 當(dāng)前值。DNA 的形態(tài)曝氣鼓風(fēng)機(jī)的 滿足程度nE Re sourcei qj Attrubt j (5) j1其中 qj 為屬性 i 所占的比重。曝氣鼓風(fēng)機(jī) 組調(diào)度方案 的滿足程度nESo

14、lution iE Resourcej(6)j12.3 曝氣鼓風(fēng)機(jī)調(diào)度方案的選擇算子 從群體中選擇優(yōu)勝的個(gè)體， 淘汰劣質(zhì)個(gè)體的 操作叫選擇。選擇算子有時(shí)又稱為再生算子 (reproduction operator) 。選擇的目的是把優(yōu)化的 個(gè)體 (或解 ) 直接遺傳到下一代或通過配對(duì)交叉 產(chǎn)生新的個(gè)體再遺傳到下一代。將每個(gè) 曝氣鼓風(fēng)機(jī) 組調(diào)度方案，看做一個(gè) DNA 、根據(jù)生物進(jìn)化優(yōu)勝劣汰的原則， 如果該 DNA 的評(píng)價(jià)值較高，則該 DNA 以較高的概率進(jìn)行下一 輪的競(jìng)爭(zhēng)。圖8 改進(jìn)的混合算法2.5 資源調(diào)度的變異算子遺傳算法導(dǎo)引入變異的目的有兩個(gè)： 一是使 遺傳算法具有局部的隨機(jī)搜索能力。 當(dāng)

15、遺傳算法 通過交叉算子已接近最優(yōu)解鄰域時(shí)， 利用變異算 子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解 收斂。顯然，此種情況下的變異概率應(yīng)取較小值， 否則接近最優(yōu)解的積木塊會(huì)因變異而遭到破壞。二是使遺傳算法可維持群體多樣性， 以防止出現(xiàn) 未成熟收斂現(xiàn)象。此時(shí)收斂概率應(yīng)取較大值。在資源不重復(fù)的前提下， 隨機(jī)的在資源調(diào)度方案中去掉一個(gè)資源，并隨機(jī)的產(chǎn)生另一個(gè)資源， 這樣模仿實(shí)現(xiàn)了自然界中的變異算子。曝氣鼓風(fēng)機(jī) 組調(diào)度 方案的選擇概率PseleictESo lutiiSolutij on(7)曝氣鼓風(fēng)機(jī) 組調(diào)度 解決方案的累計(jì)概率iPAselect i Pselectj1圖 9 變異策略(8)對(duì) 每 個(gè)

16、產(chǎn) 生 一 個(gè) 0 ， 1 的 隨 機(jī) 數(shù) r ， 若 PAseleic1t r PAselei c，t該資源調(diào)度方案得以遺 傳到下一代。3 試驗(yàn)分析本文對(duì)改進(jìn)的遺傳算法，進(jìn)行了模擬試驗(yàn)， 采用語言為 java 。試驗(yàn)如下：仿真試驗(yàn)?zāi)M了可用資源， 產(chǎn)生具有 2 個(gè)目 標(biāo)的風(fēng)機(jī)調(diào)度方案。 采用改進(jìn)的基于實(shí)數(shù)編碼和 混合交叉遺傳算法。資源的描述如下2.4 曝氣鼓風(fēng)機(jī)調(diào)度方案的混合交叉算子 在自然界生物進(jìn)化過程中起核心作用的是生 物遺傳基因的重組 (加上變異 )。同樣，遺傳算法中 起核心作用的是遺傳操作的交叉算子。所謂交叉是 指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生 成新個(gè)體的操作。通過交叉，遺

17、傳算法的搜索能力 得以飛躍提高。采用實(shí)數(shù)編碼 3方式， 一般的交叉算子， 將每 個(gè)資源調(diào)度方案看做一個(gè) DNA ，對(duì)每個(gè) DNA 里的 基因進(jìn)行排序，然后將兩個(gè) DNA 從中斷開，重新 結(jié)合成新的 DNA 。圖7 普通的交叉算法采用混合交叉編碼后，交叉算子一改以往的形 式，采用先混，后分離的方法，繼承式的擴(kuò)展了圖 10 曝風(fēng)機(jī)資源描述試驗(yàn)要從可用曝氣鼓風(fēng)機(jī)中， 選擇 2 個(gè)目標(biāo) 曝氣鼓風(fēng)機(jī)，目標(biāo)曝氣鼓風(fēng)機(jī)的目標(biāo)值為 130 ， 0.8，0.6 ；150 ，0.75 ，0.4 比重參數(shù)為， q1 0.6， q2 0.3， q3 0.1。試驗(yàn)結(jié)果如下圖 11 所示，普 通的遺傳算法， 平均收斂代數(shù)

18、是改進(jìn)遺傳算法的 3 倍， 改進(jìn)遺傳算法的成功率也明顯高于普通的遺傳算法。4 結(jié)束語圖 11 與普通遺傳算法比較 隨著曝氣鼓風(fēng)機(jī)數(shù)的增加， 遺傳算法的成功 率隨之減低，當(dāng)資源為 30 個(gè)的時(shí)候，普通遺傳 算法成功率為 95% 左右，而改進(jìn)的遺傳算法成 功率約為 100% 。當(dāng)曝氣鼓風(fēng)機(jī)數(shù)增至 180 個(gè)的 時(shí)，普通遺傳算法的成功率僅為55% 左右，而改進(jìn)的遺傳算法為 80% ?？梢姼倪M(jìn)的遺傳算法， 較普通的遺傳算法在時(shí)間和性能上，都有提高。圖 12 任務(wù)提交成功率 和其他算法比較， 改進(jìn)的遺傳算法引入最優(yōu) 保存策略機(jī)制和混合交叉算子， 在性能上， 也有 明顯的優(yōu)勢(shì)。如圖 13 所示。圖 13

19、試驗(yàn)資源 從實(shí)驗(yàn)結(jié)果可以看出， 同等條件下， 改進(jìn)的 遺傳算法，在迭代 70 次的情況，與最優(yōu)解偏差 為， 0.74 ， 而禁忌搜索算法，和蟻群算法在迭 代 100 次的時(shí)候，與最優(yōu)解偏差分別為 0.98 和 0.78 。在時(shí)間上，改進(jìn)遺傳算法為88.38ms ，禁忌 搜 索 算 法 ， 和 蟻 群 算 法 分 別 為 90.59ms 和 80.48ms ，顯然改進(jìn)的遺傳算法，在曝氣鼓風(fēng)機(jī) 調(diào)度上面，表現(xiàn)出更好的性能。目前，曝氣鼓風(fēng)機(jī)調(diào)度是我國(guó)城市污水處理 的關(guān)鍵問題。 好的調(diào)度算法， 不僅能提供系統(tǒng)安 全性，可靠性，而且，也降低了系統(tǒng)能耗，降低 污水處理的成本。 改進(jìn)工業(yè)的控制算法， 是工業(yè)

20、 控制的關(guān)鍵問題， 也是理論問題走向?qū)嵺`的必經(jīng) 之路。本文對(duì)污水處理行業(yè)的曝氣鼓風(fēng)機(jī)調(diào)度進(jìn) 行了深入的研究， 提出了一種， 基于改進(jìn)遺傳算 法的調(diào)度方法， 在同樣條件下， 該方法較禁忌搜 索算法，和蟻群算法，表現(xiàn)出更好的性能。為污 水處理行業(yè)的曝氣鼓風(fēng)機(jī)調(diào)度， 提供了一種參考 方法。參考文獻(xiàn)1 姚文俊 遺傳算法及其研究進(jìn)展 J 計(jì)算機(jī)與數(shù)學(xué)工 程， 2004，32( 4)： 41432 于淼，王日宏 改進(jìn)遺傳算法在自動(dòng)組卷中的應(yīng)用研 究J 計(jì)算機(jī)工程與應(yīng)用， 2008，44( 25)：2362383 李勇，曹廣益，朱新堅(jiān) 一種基于復(fù)合交叉的實(shí)數(shù)編 碼遺傳算法 J 計(jì)算機(jī)仿真， 2006， 23(6)： 166 169