范大鵬, 王雪丹, 李 丹

(1.黑龍江科技學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,哈爾濱 150027; 2.黑龍江科技學(xué)院 電氣與信息工程學(xué)院,哈爾濱 150027)

選煤廠配煤調(diào)度中的云模型改進(jìn)遺傳算法

范大鵬1, 王雪丹2, 李 丹1

(1.黑龍江科技學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,哈爾濱 150027; 2.黑龍江科技學(xué)院 電氣與信息工程學(xué)院,哈爾濱 150027)

針對(duì)傳統(tǒng)遺傳算法求解最優(yōu)值存在搜索速度慢、容易陷入局部最優(yōu)解的問題,基于傳統(tǒng)遺傳算法和云模型,提出了云自適應(yīng)遺傳算法和云遺傳算法,建立了選煤廠三產(chǎn)品配煤調(diào)度模型,并分別采用改進(jìn)算法和傳統(tǒng)遺傳算法求解。實(shí)例表明,兩種改進(jìn)算法優(yōu)于傳統(tǒng)遺傳算法,為選煤廠配煤調(diào)度優(yōu)化提供了技術(shù)途徑。

云模型;云自適應(yīng)遺傳算法;云遺傳算法;配煤調(diào)度

0 引 言

基本遺傳算法(GA)和自適應(yīng)遺傳算法存在搜索速度慢、容易局部陷入最優(yōu)解等問題。遺傳算法的操作規(guī)則是概率性而非確定性的。當(dāng)傳統(tǒng)遺傳算法交叉變異操作以一定概率執(zhí)行后,交叉點(diǎn)和變異位隨機(jī)變化,所生成的下一代個(gè)體也隨機(jī)變化,所以其進(jìn)化的方向是隨機(jī)的、不可控的和無記憶的。實(shí)數(shù)編碼雖然很大程度上解決了 GA算法精度和存儲(chǔ)量的問題,但其作為主要交叉算子的算術(shù)交叉都為凸運(yùn)算[1],使整個(gè)群體尋找最優(yōu)受到了限制,并有未成熟收斂于局部最優(yōu)的可能,而且同樣沒有解決進(jìn)化方向的無記憶和隨機(jī)性問題。

云模型的概念是著名學(xué)者李德毅院士提出的。筆者在分析傳統(tǒng)遺傳算法的基礎(chǔ)上,利用云模型的定性與定量間的轉(zhuǎn)換方法,提出了云自適應(yīng)遺傳算法和云遺傳算法,并將其應(yīng)用于選煤廠配煤調(diào)度中。

1 傳統(tǒng)遺傳算法

1.1 基本遺傳算法

基本遺傳算法[1]可以表示為

其中,C為個(gè)體的編碼方法,E為個(gè)體適應(yīng)度評(píng)價(jià)函數(shù),P0為初始種群,M為種群大小,Φ為選擇算子,Γ為交叉算子,Ψ為變異算子,T為遺傳運(yùn)算終止條件。其流程如圖1所示。

圖1 基本遺傳算法流程Fig.1 Flow chart of GA

1.2 自適應(yīng)遺傳算法

自適應(yīng)遺傳算法是指具有比例復(fù)制、自適應(yīng)交叉和變異操作的遺傳算法,與一般遺傳算法相比,它能夠較好解決早熟和停滯的問題。

該算法中的交叉Pc和變異Pm可表示為[1]:

2 改進(jìn)遺傳算法

2.1 云模型

設(shè)U是一個(gè)用精確數(shù)值表示的定量論域,X?U,T是U空間上的定性概念,若元素x(x∈X)對(duì)T所表達(dá)的定性概念的隸屬確定度CT(x)(CT(x)∈[0,1])是一有穩(wěn)定傾向的隨機(jī)數(shù),則概念T從論域U到區(qū)間[0,1]的映射在數(shù)域空間的分布稱為云(Cloud)。CT(x)在[0,1]上取值,故云是從論域到區(qū)間[0,1]的映射,即

從云的基本定義可以看出,論域中某一元素與它對(duì)T的隸屬度之間的映射是一對(duì)多的關(guān)系,而不是傳統(tǒng)模糊隸屬函數(shù)中的一對(duì)一的關(guān)系[2]。

云模型包括正態(tài)云、X條件云、Y條件云三種。

云模型具有穩(wěn)定性和隨機(jī)性,筆者根據(jù)這一特點(diǎn),基于基本遺傳算法和自適應(yīng)遺傳算法,提出了云自適應(yīng)遺傳算法和云遺傳算法。

2.2 云自適應(yīng)遺傳算法

云自適應(yīng)遺傳算法[3]過程如下:

(1)初始化種群。

(2)計(jì)算適應(yīng)度。

(3)選擇操作。

(4)交叉。具體步驟為:

a 計(jì)算父母染色體適應(yīng)值、種群規(guī)模的平均適應(yīng)值 ave-f;

b 選取父母染色體大的適應(yīng)值f;

c 當(dāng)f小于 ave-f,選Pc為大概率交叉概率k3值,k3為[0,1]區(qū)間的數(shù)據(jù);

d 當(dāng)f大于 ave-f,Pc由云發(fā)生器產(chǎn)生,云發(fā)生器是以平均適應(yīng)度為期望值,以適應(yīng)度最大值減去平均適應(yīng)度為熵和超熵產(chǎn)生的云模型圖,云圖的確定度μ是[0,l]區(qū)間的隨機(jī)數(shù),即要選取的交叉概率Pc。

(5)變異。具體步驟為:

a 計(jì)算當(dāng)前染色體適應(yīng)值f、種群規(guī)模的平均適應(yīng)值 ave-f;

b 當(dāng)f小于 ave-f,選Pm為大概率交叉概率k4值,k4為[0,1]區(qū)間的數(shù)據(jù);

c 當(dāng)f大于 ave-f,Pm由云發(fā)生器產(chǎn)生,云圖的確定度μ是[0,l]區(qū)間的隨機(jī)數(shù),即要選取的交叉概率Pm;

d 隨機(jī)產(chǎn)生變異點(diǎn),采用單點(diǎn)變異,新個(gè)體復(fù)制到選擇個(gè)體中,保留最優(yōu)個(gè)體。

(6)將新種群復(fù)制到原種群,判定終止條件是否達(dá)到,若達(dá)到則轉(zhuǎn)到步驟(7),否則轉(zhuǎn)到步驟(2)。

(7)輸出結(jié)果。

2.3 云遺傳算法

云遺傳算法(CGA)描述如下:

(1)初始化種群。

(2)計(jì)算適應(yīng)度。

(3)選擇操作。

(4)交叉。具體步驟為:

數(shù)Temp,當(dāng)μ>Temp時(shí),更新個(gè)體。

(6)轉(zhuǎn)步驟(2),直到滿足停止條件。

xf和xm分別為交叉操作的父個(gè)體和母個(gè)體,Ff和Fm則分別對(duì)應(yīng)它們的適應(yīng)度。F′為交叉父個(gè)體的最大值,意味著交叉操作中的Ex由父母雙方按適應(yīng)度大小加權(quán)確定,并向適應(yīng)度大的一方靠近。c1、c2、c3、c4為控制系數(shù)。

顯然,交叉操作實(shí)現(xiàn)了染色體(個(gè)體)的整體進(jìn)化,而變異操作則反映染色體中某個(gè)基因在一定范圍內(nèi)的突變。CGA不再引入交叉和變異概率。

3 選煤廠配煤調(diào)度模型

3.1 三產(chǎn)品配煤模型

設(shè)三種參配產(chǎn)品的灰分、百分率分別為K1、K2、K3、X1、X2、X3,X1+X2+X3=1;目標(biāo)產(chǎn)品灰分為K,滿足Kmin

目標(biāo)產(chǎn)品與參配產(chǎn)品存在如下關(guān)系:

可以看出,該問題為一定約束條件下的目標(biāo)函數(shù)優(yōu)化問題。設(shè)三種參配產(chǎn)品的生產(chǎn)成本分別為C1、C2、C3,則配煤的目標(biāo)應(yīng)為追求成本F(x)最低,即

其約束條件為:

對(duì)于上述線性規(guī)劃模型,需根據(jù)約束條件和目標(biāo)函數(shù)求解百分率,即求X1、X2和X3。

3.2 調(diào)度模型

假設(shè)選煤廠洗選各種煤所消耗的噸原煤單位時(shí)間成本是近似相同的,調(diào)度模型就可轉(zhuǎn)化為求一組合適的Km、Bk,使其經(jīng)濟(jì)效益最大。這是帶有約束的數(shù)學(xué)規(guī)劃問題,目標(biāo)函數(shù)[4-5]為

其中,Km為實(shí)際生產(chǎn)精煤的灰分,Ke為單日計(jì)劃(合同)要求的精煤灰分,K0為原煤的灰分,We為日計(jì)劃目標(biāo)精煤的產(chǎn)量,Wm為庫存精煤量,W0為用來和實(shí)際生產(chǎn)的精煤配煤的原煤量,P為合同要求的精煤的價(jià)格,P0為原煤價(jià)格,Pb為中煤和煤泥的價(jià)格,Cm為洗煤時(shí)單位時(shí)間生產(chǎn)成本,Φ(K0,Km)為精煤的產(chǎn)率函數(shù),V(K0,Ke)為洗煤廠的分選速度函數(shù),Γ(K0,Ke)為中煤和煤泥的產(chǎn)率函數(shù)。

目標(biāo)函數(shù)的約束條件為:

其中,Kk為庫存精煤的灰分,Wk為實(shí)際生產(chǎn)精煤量,Bk為庫存精煤用來配煤的百分比。

(2)運(yùn)輸工具(火車)到達(dá)時(shí),應(yīng)完成選煤過程,且

其中,Ttrain為運(yùn)輸工具到達(dá)時(shí)間。

(3)根據(jù)現(xiàn)實(shí)情況,還應(yīng)有邊界條件,如 0≤Bk≤1,K0≥Ke,K0≥Km,K0≥Kk。

4 實(shí) 例

以南屯選煤廠為例[6],合同要求和目前生產(chǎn)情況如表1所示。

該廠單位時(shí)間生產(chǎn)成本為 43元,基本處理速度為 1 500 t/h,中煤和煤泥的價(jià)格為 290元/t。已知 GA算法中交叉數(shù)值為 0.25,變異數(shù)值為 0.05,種群個(gè)數(shù)為 50個(gè),分別采用基本遺傳算法(GA)、云遺傳算法(CGA)、自適應(yīng)遺傳算法(AGA)、云自適應(yīng)遺傳算法(CAGA)進(jìn)行仿真,如圖 2所示。

圖2 四種算法的運(yùn)行結(jié)果Fig.2 Run results of four algorithm s

從圖 2可以看出,基本遺傳算法的運(yùn)行時(shí)間最長,云遺傳算法運(yùn)行時(shí)間最短,云自適應(yīng)遺傳算法和云遺傳算法的運(yùn)行時(shí)間均少于基本遺傳算法和自適應(yīng)遺傳算法。從運(yùn)行結(jié)果來看,云遺傳算法運(yùn)行結(jié)果精度最高,基本遺傳算法運(yùn)行結(jié)果精度最低。綜上,改進(jìn)的遺傳算法優(yōu)于傳統(tǒng)遺傳算法。

5 結(jié)束語

根據(jù)基本遺傳算法、自適應(yīng)遺傳算法及云模型理論,提出云自適應(yīng)遺傳算法和云遺傳算法。前者保留了交叉概率和變異概率,而后者去掉了交叉概率和變異概率。將兩種改進(jìn)算法應(yīng)用于選煤廠配煤調(diào)度優(yōu)化中,并與傳統(tǒng)算法進(jìn)行比較。結(jié)果表明,兩種改進(jìn)的遺傳算法均優(yōu)于傳統(tǒng)遺傳算法,具有應(yīng)用價(jià)值。該研究為選煤廠配煤調(diào)度優(yōu)化提供了更好的途徑。

[1] 雷英杰,張善文,李續(xù)武,等.遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2005.

[2] 李德毅,杜 鹢.不確定性人工智能[M].北京:國防工業(yè)出版社,2005.

[3] 戴朝華,朱云芳,陳維榮,等.云遺傳算法及其應(yīng)用[J].電子學(xué)報(bào),2007,35(7):1 419-1 424.

[4] 高 莉,于洪珍,王艷芬.基于多傳感器信息融合的選煤廠配煤調(diào)度[J].中國礦業(yè)大學(xué)學(xué)報(bào),2004,33(1):100-102.

[5] 郭西進(jìn).選煤廠 C IMS環(huán)境下管理信息系統(tǒng)的分析、設(shè)計(jì)、應(yīng)用[M].徐州:中國礦業(yè)大學(xué)出版社,2003.

[6] 路邁西.選煤廠技術(shù)管理 [M].徐州:中國礦業(yè)大學(xué)出版社,2005.

[7] 劉立民,潘 偉,龐彥軍,等.多階段復(fù)合型遺傳算法的結(jié)構(gòu)及性能研究[J].河北工程大學(xué)學(xué)報(bào):自然科學(xué)版,2010(2): 107-112.

Improved cloud-based genetic algorithm for coal blending scheduling in coalpreparation plant

FAN Dapeng1,WANG Xuedan2,L I Dan1
(1.College of Computer&Infor mation Engineering,Heilongjiang Institute of Science&Technology,Harbin 150027,China; 2.College of Electric&Infor mation Engineering,Heilongjiang Institute of Science&Technology,Harbin 150027,China)

In response to traditional genetic algorithm(GA)suffering from a lower convergent speed and greater tendency to get stuck at a local optimum solution,as is evident in the opt imal value solution, this paper proposes a cloud-based adaptive genetic algorithm(CAGA)and cloud-based genetic algorithm (CGA),based on traditional genetic algorithm and cloud model.The paper offers coal blending schedulingmodel of three productions,as is shown by reference[4]and provides solution by the two improved algorithms and GA respectively.The exper iment confi rms that the two improved algorithms exhibiting advantages over GA,are of application value.

cloud model;cloud-based adaptive genetic algorithm;cloud-based genetic algorithm; coal blending scheduling

TP301.6;TD928.9

A

1671-0118(2011)02-0112-04

2011-03-14

范大鵬(1979-),男,黑龍江省哈爾濱人,工程師,碩士,研究方向:智能控制、數(shù)據(jù)融合,E-mail:fandap-02@yahoo.com.cn。

(編輯荀海鑫)