一種改進(jìn)的遺傳算法在間歇化工過程設(shè)計中的應(yīng)用

魏良霄,張 婷,黨樂平,郝 琳

(天津大學(xué)化工學(xué)院,天津 300072)

為了在全球市場上保持競爭力,優(yōu)化生產(chǎn)流程的設(shè)計和管理是重中之重。 間歇化工過程以其技術(shù)密集性、動態(tài)性、多樣性、靈活性和不確定性等特點在化工及相關(guān)行業(yè)中發(fā)揮著重要作用[1]。 雖然在間歇過程的設(shè)計和優(yōu)化方面均有了很大的進(jìn)展,但由于這是一個離散變量和連續(xù)變量共存的混合整數(shù)非線性規(guī)劃MINLP (Mixed-Integer Nonlinear Programming)問題[2],求解過程中目標(biāo)函數(shù)的復(fù)雜度隨著變量的數(shù)量變化呈指數(shù)增長趨勢。 所以對問題進(jìn)行建模和求解仍然相當(dāng)困難[3]。

差分運算是間歇過程設(shè)計中最早使用的方法[4],但解決方案的復(fù)雜性使得該方法很快被分支定界法[5-6]、數(shù)學(xué)規(guī)劃法和其他啟發(fā)式方法所取代[7-8]。 然而,這些方法即使是在解決簡單問題的過程中就非常麻煩,顯然不適合解決大規(guī)模問題。人工智能算法或通過多種方法相結(jié)合的方式來解決上述問題獲得了成功的應(yīng)用。 Loonkar 和Robinson[9]使用迭代方法來最小化設(shè)備投資。 Yeh等[10]使用啟發(fā)式算法討論單一產(chǎn)品化學(xué)過程的綜合問題。 鄭國文等[11]基于Yeh 的研究通過添加中間存儲單元,進(jìn)一步研究了這一過程。 Kirkpatrick等[12]提出了模擬退火算法(SAA),Yuan 等[13]在間歇過程的設(shè)計和調(diào)度中使用了該算法。 楊志才等[14]提出了一種分解策略,然后引入了基于該策略和隨機(jī)算法的組合算法來解決間歇過程優(yōu)化的MINLP 問題。 正如Moniz 等[15]所指出的,我們?nèi)匀恍枰碌姆椒?它應(yīng)該對啟發(fā)式方法和智能優(yōu)化算法進(jìn)行整合,以解決現(xiàn)實中更加復(fù)雜的問題。

本研究提出了一種基于遺傳算法(GA)的MINLP 模型,并用回溯法對該模型進(jìn)行了補充。 該算法在保持遺傳算法優(yōu)點的前提下結(jié)合回溯法指導(dǎo)搜索過程,消除劣質(zhì)基因;并且在建模過程中,考慮了設(shè)備利用率最大化問題。 最后通過實例與利用枚舉法和回溯法相結(jié)合的方法建立的模型進(jìn)行了比較。

1 遺傳算法的基本原理

遺傳算法是由美國密歇根大學(xué)的Holland[16]提出的。 它是解決復(fù)雜系統(tǒng)問題的框架,具有良好的適用性和魯棒性。 一個典型的遺傳算法的基本要求是:1)解域的遺傳表示。 2)用于評估解域的適應(yīng)度函數(shù)。

每個候選解決方案的標(biāo)準(zhǔn)表示形式是位數(shù)組。其他類型和結(jié)構(gòu)的數(shù)組基本上可以以相同的方式使用。 如圖1 所示,遺傳算法的過程包括以下步驟[17]:1)創(chuàng)建一組編碼方案。 2)使用適應(yīng)度函數(shù)評估不同的字符串。 3)字符串根據(jù)其評估的適應(yīng)度大小進(jìn)行排序。 4)然后創(chuàng)建2 個子節(jié)點,對2 個字符串進(jìn)行交叉和編譯操作,然后替換上一代的2個字符串。 5) 最后重復(fù)該循環(huán),直到達(dá)到停止標(biāo)準(zhǔn)。

2 數(shù)學(xué)模型

2.1 假設(shè)

圖1 遺傳算法典型流程圖Fig.1 Typical structure of genetic algorithm

為降低模型建立時的復(fù)雜程度,我們做如下假設(shè):1)生產(chǎn)工藝和配方已知;2)總生產(chǎn)時間和生產(chǎn)需求已經(jīng)明確;3)有充足的原料供應(yīng);4)設(shè)備在整個時間段內(nèi)無故障;5)設(shè)備為非標(biāo)設(shè)備;6)設(shè)備數(shù)量不加以限制;7)處理時間已經(jīng)確定,不會改變;8)處理時間包括進(jìn)料時間、出料時間、反應(yīng)時間和清洗時間。

2.2 約束方程

為了提高設(shè)備的利用率,規(guī)定可以將前一間歇級的產(chǎn)品分為xi次生產(chǎn),即設(shè)置中間存儲,如圖2 間歇級2 所示。 很明顯如果間歇級1 中的物料尚未被間歇級2 處理完,間歇級1 是不能接受新的物料的投入的,否則會造成中間存儲中物料的積壓。 于是可以將這個分次生產(chǎn)過程等效為一個處理時間較長的過程,因此有:

式(1)中:ti為產(chǎn)品在間歇級i 的處理時間,h; t′i為產(chǎn)品在間歇級i 的等效處理時間,h;xi為上一級產(chǎn)品在在下一級的分批生產(chǎn)次數(shù)。

間歇化工過程通常包含1 個或多個瓶頸階段。通常這些階段涉及到更長的處理時間或者資本密集型設(shè)備[18]。 將與瓶頸階段相對應(yīng)的時間稱為循環(huán)時間:

式(2)中:ni為間歇級i 的異步平行單元數(shù);T 為限制循環(huán)時間,h。

圖2 分段生產(chǎn)示意圖Fig.2 Schematic diagram of sectional production

在1 臺設(shè)備上每批應(yīng)完成的產(chǎn)品量為:

式(3)中:mi為間歇級i 的同步平行單元數(shù);Bi為間歇級i 每1 批完成的產(chǎn)品量,kg;Qi為間歇級i 的生產(chǎn)總量,kg;H 為年生產(chǎn)時間,h。

設(shè)備的體積與設(shè)備加工的產(chǎn)品量之間的關(guān)系為:

式(4)中:Si為間歇級i 的尺寸因子,kg/m3;Vi為設(shè)備體積,m3。

并且有:

引入平行單元以降低這些瓶頸階段的主導(dǎo)地位[19]。同步平行單元的最大數(shù)值被指定為在非覆蓋式下操作時需要設(shè)置的同步平行單元的數(shù)。

式(6)中: Vmax為設(shè)備最大體積,m3。

反應(yīng)設(shè)備總數(shù)為:

式(8)中: nmax為間歇級的最大異步平行單元數(shù)。

2.3 目標(biāo)函數(shù)

該模型以設(shè)備投資最低為目標(biāo)函數(shù)[20],在計算過程中設(shè)備成本的估算通常以體積的指數(shù)函數(shù)表示[21]:

式(9)中:αi為間歇級i 的成本系數(shù);βi為間歇級i的成本指數(shù)。

故總投資為:

3 實例計算

3.1 問題描述

以實際項目為例,該項目包含7 個間歇級,每個間歇級的出料都是固體,包含過濾和干燥2 種操作。因此,我們可以將每個間歇級的設(shè)備等效為1 個具有過濾和干燥功能的反應(yīng)器。 為了確保轉(zhuǎn)化率不受較大影響,將設(shè)備最大體積設(shè)為5 m3。 年生產(chǎn)時間為330 d,每天24 h 不間斷生產(chǎn),故總生產(chǎn)時間為7 920 h。 其他所有輸入數(shù)據(jù)在表1 中給出。

表1 產(chǎn)品加工要求清單Table 1 List of product processing requirements

3.2 算法實現(xiàn)

該模型的主體為遺傳算法,有3 組變量:同步平行單元數(shù)、異步平行單元數(shù)和連續(xù)生產(chǎn)數(shù)。 其中連續(xù)生產(chǎn)是指在2 個連續(xù)批次的同一間歇級生產(chǎn)時間間隔可能較大的情況下前一間歇級中該步驟的產(chǎn)物分為幾次投入到此間歇級中進(jìn)行生產(chǎn),以減少設(shè)備的體積,提高設(shè)備的利用率。

由于變量較多,生成的染色體較為復(fù)雜。 我們決定直接以十進(jìn)制數(shù)生成染色體,并且取消編碼和解碼過程。 該模型的每個染色體由14 個基因組成。分為2 部分,前7 個基因代表每個間歇級的同步平行單元數(shù),后7 個基因代表每個間歇級的異步平行單元數(shù)。 在突變過程中,應(yīng)根據(jù)基因所處的位置使用相應(yīng)的函數(shù)進(jìn)行突變,否則極大可能會產(chǎn)生劣質(zhì)基因。

異步平行單元數(shù)最大值由經(jīng)驗指定,在本模型中指定為4。 然而當(dāng)使用這些基因計算反應(yīng)器的體積時,發(fā)現(xiàn)反應(yīng)器的體積超過了最大體積的極限。于是采用懲罰操作對進(jìn)化過程進(jìn)行優(yōu)化,簡單的流程如圖3 所示。

圖3 初始模型流程圖Fig.3 Flow chart of initial model

程序運行后最優(yōu)值為9.146×105,但是在重新運行模型后發(fā)現(xiàn)最優(yōu)值發(fā)生了變化,圖4a 是模型運行100 次后最優(yōu)值的波動情況。 從圖4a 中可以看出,最優(yōu)值一直在變化,其中最低值為8.998×105,最高值為10.580×105,增加了17.6%。

圖4 最優(yōu)值波動曲線Fig.4 Fluctuation curve of optimal solution after optimization

經(jīng)過計算,發(fā)現(xiàn)隨機(jī)種群生成后,許多染色體不僅不能滿足限制條件的約束,甚至出現(xiàn)嚴(yán)重錯誤。 比如在這些染色體的指導(dǎo)下會出現(xiàn)上一批物料尚未加工完畢便又投入新的物料的現(xiàn)象,這明顯不符合實際情況。 并且這些染色體在種群中占很高的比例,這使得在種群在進(jìn)化過程中很難獲得更優(yōu)秀的基因,并且覆蓋范圍變得狹窄,這使得GA 的特性無法正常發(fā)揮。 圖5a 顯示了100 代種群進(jìn)化過程中每一代中有缺陷基因的比例。 從圖5a 中我們可以看出,在幾乎每一代中,有缺陷基因的比例都超過80%甚至接近100%。

圖5 每一代中有缺陷基因的比例Fig.5 The proportion of faulty genes in each generation

因此,在計算適應(yīng)度前必須對基因進(jìn)行優(yōu)化。于是建立了一種自尋優(yōu)機(jī)制,每次形成新的種群時都對染色體進(jìn)行判斷,并在出現(xiàn)錯誤時對染色體進(jìn)行優(yōu)化。 簡單的流程如圖6 所示。

再次運行模型100 次后發(fā)現(xiàn)最優(yōu)值幾乎穩(wěn)定在8.998×105,如圖4b 所示。 即使在最優(yōu)值發(fā)生變化的地方,最大值也只有9.072×105,只比8.998×105高0.822 %。 并且大部分錯誤基因出現(xiàn)的比例下降到了50%以下,如圖5b 所示。 當(dāng)然自優(yōu)化機(jī)制的作用不僅僅是這樣,它真正的作用是在錯誤基因出現(xiàn)后對其進(jìn)行優(yōu)化,而錯誤基因出現(xiàn)的比例下降是由于上一代錯誤的基因減少造成的,這是一種額外效果。

3.3 結(jié)果

該程序在MATLAB2017b 中運行,運行時間為0.634 s。 經(jīng)過一定代數(shù)的繁衍后收斂到8.998 ×105這一值。 限制循環(huán)時間為120 h,其他數(shù)據(jù)如表2 所示。

將計算結(jié)果繪制成甘特圖如圖7 所示。 從圖7中可以看出,間歇級1 有7 個同步平行單元,間歇級2 有2 個同步平行單元,整個過程中沒有異步平行單元。 間歇級1 是時間限制級。 中間存儲器設(shè)置在間歇級2 中,并且調(diào)用間歇級2 的2 個批次生產(chǎn)時間間隔從原來的120 h 變?yōu)楫?dāng)前的24 h。 每個階段反應(yīng)器的利用率如圖8 所示。

圖6 自優(yōu)化機(jī)制流程圖Fig.6 Flow chart of self-optimization mechanism

表2 遺傳算法計算結(jié)果Table 2 Calculation results of genetic algorithm

圖7 利用遺傳算法得到的甘特圖Fig.7 Gantt chart obtained by genetic algorithm

圖8 利用遺傳算法得到的設(shè)備利用率Fig.8 Reactor utilization obtained by genetic algorithm

4 與一般啟發(fā)式方法進(jìn)行比較

本模型參考鄭國文等[11]所建立的模型,利用枚舉法和回溯法進(jìn)行建模。 首先計算所有滿足約束方程的x 的值,然后將它們帶入圖9 所示的流程圖中來搜索局部最優(yōu)值。 最后從所有局部最適宜值中選擇最小的結(jié)果作為最優(yōu)結(jié)果。

圖9 啟發(fā)式算法流程圖Fig.9 Flow chart of heuristic method

該程序在MATLAB 2017b 中運行并運行14 s。程序運行后,設(shè)備投資局部最優(yōu)值分布折線如圖10所示,其中橫坐標(biāo)代表不同的中間存儲方案,縱坐標(biāo)代表確定存儲方案后模型求得的最優(yōu)解。 從圖10 中可以看出,設(shè)備投資成本的分布范圍較大,最小值出現(xiàn)在3 個位置。 它們分別位于橫坐標(biāo)57、88和96 上,所有與最優(yōu)值相關(guān)的計算結(jié)果列在表3 中。

圖10 局部最優(yōu)值分布曲線Fig.10 Distribution curve of optimal solution

從表3 中可以看出,3 個結(jié)果的同步平行單元數(shù)和異步平行單元數(shù)相同,但是連續(xù)生產(chǎn)次數(shù)不同。 顯然,實際生產(chǎn)中在間歇級1 前設(shè)置中間存儲是沒有意義的,因此我們只選取列表中x1=1 的情況,即僅保留表3 中的第一種情況。

表3 啟發(fā)式算法計算結(jié)果Table 3 Calculation results of heuristic algorithm

這種生產(chǎn)方法以甘特圖的形式表示,見圖11。從圖11 中可以看出,間歇級1 為過程中的時間限制級,包含4 個同步平行單元4 個異步平行單元。 異步平行單元使限制時間由原來的120 h 減少到了60 h。 在間歇級2 中設(shè)置中間存儲,使得上一間歇級的物料分兩批加入此間歇級,從而減小后續(xù)階段反應(yīng)器的體積,增大反應(yīng)器利用率。 可以得出每個階段的反應(yīng)器利用率,如圖12 所示。

比較以上2 個結(jié)果,可以看出,遺傳算法獲得的設(shè)備投資結(jié)果比啟發(fā)式算法獲得的結(jié)果低2. 66%。 這是因為同步平行單元數(shù)和異步平行單元數(shù)是隨機(jī)生成的,并且在后續(xù)的交叉變異等操作過程中使得每個階段的同步平行單元數(shù)和異步平行單元數(shù)更加具有多樣性,因此優(yōu)化過程中遺傳算法的覆蓋范圍比一般啟發(fā)式算法的覆蓋范圍更廣。 并且一般啟發(fā)式算法的同步平行單元數(shù)和異步平行單元數(shù)都是按照一定的規(guī)律進(jìn)行變化的,這使得在優(yōu)化過程中易于陷入局部最優(yōu)解。用遺傳算法建立的模型在計算速度上是用一般啟發(fā)式算法建立的模型的22 倍。 但是,當(dāng)中間存儲的容量變小時,2 者之間的時間差距逐漸減小,這表明要解決的問題越復(fù)雜,遺傳算法的優(yōu)勢越明顯。 但是,設(shè)備的利用率沒有變化。 這是因為用一般啟發(fā)式算法建立的模型使用枚舉法來優(yōu)化設(shè)備的利用率,并且所有可能性都包含在指定范圍內(nèi),因此無法進(jìn)一步優(yōu)化。

圖11 利用一般啟發(fā)式方法得到的甘特圖Fig.11 Gantt chart obtained using general heuristic method

圖12 利用一般啟發(fā)式方法得到的設(shè)備利用率Fig.12 Reactor utilization obtained using general heuristic method

5 結(jié)論

介紹了一種改進(jìn)的遺傳算法在解決單產(chǎn)品間歇化工過程設(shè)計問題中的應(yīng)用。 通過引入自我優(yōu)化機(jī)制和懲罰操作在不影響遺傳算法特性的前提下對基因進(jìn)行人為干預(yù),從而減少種群中劣質(zhì)染色體的出現(xiàn),使種群得以順利穩(wěn)定的繁衍下去。 最后與一般啟發(fā)式算法建立的模型進(jìn)行比較。 結(jié)果表明該模型在計算結(jié)果、收斂速度和計算速度上均優(yōu)于一般啟發(fā)式方法。