王玉梅，程輝，錢(qián)鋒（華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

?

改進(jìn)生物地理學(xué)優(yōu)化算法及其在汽油調(diào)合調(diào)度中的應(yīng)用

王玉梅，程輝，錢(qián)鋒
（華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

摘要：汽油調(diào)合和調(diào)度優(yōu)化問(wèn)題中含有典型的非線性約束（NLP）問(wèn)題。針對(duì)一般智能優(yōu)化算法在解決此類優(yōu)化問(wèn)題中易陷于局部極值，提出了一種改進(jìn)的生物地理學(xué)優(yōu)化算法（HMBBO）。該算法設(shè)計(jì)了一種基于種群個(gè)體差異信息的啟發(fā)式變異算子，彌補(bǔ)了Gauss變異、Cauchy變異算子缺乏啟發(fā)式信息的不足，以解決原算法在局部搜索時(shí)易出現(xiàn)的早熟問(wèn)題，提高算法的全局搜索能力，并且采用非線性物種遷移模型以適應(yīng)不同的自然環(huán)境。采用4個(gè)測(cè)試函數(shù)進(jìn)行仿真，結(jié)果表明：HMBBO算法與標(biāo)準(zhǔn)BBO算法、基于Gauss變異及基于Cauchy變異的BBO算法比較，其收斂速度和全局尋優(yōu)能力有明顯改善。汽油調(diào)合和調(diào)度優(yōu)化實(shí)例表明，該算法能夠快速有效地找到全局最優(yōu)解。

關(guān)鍵詞：算法；優(yōu)化；仿真；汽油調(diào)合和調(diào)度優(yōu)化

2015-12-03收到初稿，2015-12-10收到修改稿。

聯(lián)系人：程輝。第一作者：王玉梅（1991—），女，碩士研究生。

引 言

油品調(diào)合是煉油廠生產(chǎn)成品汽油的最后一道工序，它直接影響油品產(chǎn)品的質(zhì)量及全廠的經(jīng)濟(jì)效益。汽油調(diào)合和調(diào)度優(yōu)化問(wèn)題一直是研究的熱點(diǎn)、難點(diǎn)問(wèn)題。它要求在滿足用戶指定的產(chǎn)品需求計(jì)劃的前提下，盡量利用現(xiàn)有組分資源生產(chǎn)更多的產(chǎn)品，或獲得最大利潤(rùn)。文獻(xiàn)[1]針對(duì)汽油調(diào)合調(diào)度優(yōu)化問(wèn)題采用了預(yù)測(cè)汽油辛烷值和蒸氣壓的合適方法，提出基于邏輯的數(shù)學(xué)模型，并采用改進(jìn)的遺傳算法（GA）進(jìn)行求解。文獻(xiàn)[2]建立了新的汽油調(diào)合配比模型以解決現(xiàn)有油品調(diào)合配比優(yōu)化模型不夠準(zhǔn)確的問(wèn)題。然而，傳統(tǒng)的非線性規(guī)劃方法都是在滿足特定條件下才可用，一般群智能優(yōu)化算法在解決此問(wèn)題時(shí)也難以獲得準(zhǔn)確的全局最優(yōu)解。

生物地理學(xué)是研究生物種群在時(shí)間和空間上分布的一門(mén)學(xué)科。Simon[3]于2008年提出了生物地理學(xué)優(yōu)化算法（BBO）。該算法主要通過(guò)模擬生物種群在不同棲息地之間的遷移，以實(shí)現(xiàn)各棲息地之間信息的交流和共享，從而找到所求問(wèn)題的最優(yōu)解。Simon等[4]進(jìn)一步系統(tǒng)地分析了BBO算法的收斂性，盡管BBO算法參數(shù)少、收斂速度較快，實(shí)現(xiàn)較簡(jiǎn)單，但是標(biāo)準(zhǔn)BBO算法也存在不足之處，如全局搜索能力不強(qiáng)，易陷于局部最優(yōu)解。

針對(duì)BBO算法易陷于局部極值的問(wèn)題，本文提出了一種改進(jìn)的生物地理學(xué)優(yōu)化算法（HMBBO）。在原算法的基礎(chǔ)上設(shè)計(jì)了一種基于種群個(gè)體信息差異的啟發(fā)式變異算子[5]，彌補(bǔ)了Gauss變異、Cauchy變異算子缺乏啟發(fā)式信息的不足，從總體上加快了算法的收斂速度，使優(yōu)化不會(huì)過(guò)早地向局部最優(yōu)點(diǎn)方向聚集，從而保證算法在搜索空間的全局搜索能力。并且本文采用余弦遷移模型，使生物地理學(xué)優(yōu)化算法（BBO）能更好地適用于不同特點(diǎn)的優(yōu)化問(wèn)題。采用4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)此優(yōu)化算法進(jìn)行測(cè)試并應(yīng)用于汽油調(diào)合調(diào)度優(yōu)化實(shí)例。

1 生物地理學(xué)優(yōu)化算法

生物地理學(xué)優(yōu)化算法（BBO）是一種基于生物群體的全局優(yōu)化算法。該算法采用整數(shù)編碼，并設(shè)計(jì)了一種基于概率的個(gè)體移動(dòng)算子，使得不同個(gè)體之間進(jìn)行信息交流與共享。每個(gè)個(gè)體具有各自的適宜值（habitat suitability index, HSI)用于對(duì)個(gè)體進(jìn)行評(píng)價(jià)，也具有一對(duì)基于種群數(shù)目的遷入率（λ）和遷出率（μ）。HSI影響生物種群在棲息地分布和遷移。HSI值較高的棲息地具有較好的生存環(huán)境，能容納的種群數(shù)量較多，而HSI值低的棲息地生存環(huán)境較差，所能容納的種群數(shù)量相對(duì)較少。但是，HSI值高的棲息地隨著物種數(shù)目的增多，所能容納新物種遷入的能力變差，種群遷入率低，遷出率較高；反之，HSI值低的棲息地具有較高的遷入率λ和較低的遷出率μ。

BBO算法主要通過(guò)遷移和變異[6]搜索全局的最優(yōu)解。

BBO算法采用遷移操作使得不同棲息地之間的信息進(jìn)行交流與共享，以此對(duì)解空間進(jìn)行搜索。設(shè)每個(gè)棲息地i所容納的種群數(shù)量為Si，其對(duì)應(yīng)的遷入率和遷出率可由式（1）、式（2）計(jì)算得出

當(dāng)某一個(gè)個(gè)體滿足遷移條件時(shí)，用遷出率μ選取新個(gè)體Y以替換原個(gè)體。

BBO算法根據(jù)每個(gè)棲息地的種群數(shù)量概率Pi對(duì)棲息地的特征向量進(jìn)行變異，以此增加種群的多樣性，避免尋優(yōu)過(guò)程過(guò)早的陷于局部最優(yōu)解中。每個(gè)點(diǎn)的變異概率為

其中，mmax為最大變異概率，Pmax=argmaxPi(i=1,2,…,NP)），Pi的定義如下

2 改進(jìn)的生物地理學(xué)優(yōu)化算法

標(biāo)準(zhǔn)BBO算法采用隨機(jī)變異策略，它是在一定的基因取值范圍之內(nèi)，采用隨機(jī)值替代即將發(fā)生變異的基因。文獻(xiàn)[7]引入高斯變異策略，高斯變異每一次變異產(chǎn)生的幅度是不同的，變異所產(chǎn)生的取值服從高斯分布。它用高斯分布函數(shù)替代隨機(jī)變異所產(chǎn)生的隨機(jī)數(shù)，即式（5）。另一種變異策略為柯西變異[8]，它與高斯變異原理相同，其原理如式（6）。

本文采用啟發(fā)式變異算子，使得BBO算法的變異策略可以隨著所優(yōu)化變量的狀態(tài)進(jìn)行動(dòng)態(tài)更新，從而實(shí)現(xiàn)算法的啟發(fā)式迭代，也使得解的部分分量在一定范圍內(nèi)產(chǎn)生較大的變化，增強(qiáng)解空間的搜索能力，使得算法跳出局部極小值，提高算法的全局搜索能力。

2.1 個(gè)體表示及其初始化

新算法采用實(shí)數(shù)編碼。設(shè)種群數(shù)目為NP，其中個(gè)體解向量為

初始化為

其中，L=(l1,l2,…,lD),U=(u1,u2,…,uD)分別表示解向量的下界和上界。

2.2 非線性遷移模型

考慮到自然環(huán)境中種群的遷移，本文采用如下非線性遷移模型

圖1 物種遷移模型Fig.1 Species migration model

2.3 啟發(fā)式變異算子

文中提出一種啟發(fā)式變異的BBO算法，采用啟發(fā)式變異算子，按照式（11）產(chǎn)生新的變異個(gè)體。

式中，當(dāng)?shù)螖?shù)G=0時(shí)，?i?。?,1] 區(qū)間的均勻隨機(jī)數(shù)；當(dāng)G＞0時(shí)，?i則以0.1的概率?。?,1]區(qū)間的均勻隨機(jī)數(shù)作更新，并以0.9的概率保持不變。α (j)是[0,1]區(qū)間的均勻隨機(jī)數(shù)，βi為變異控制系數(shù)，以0.1的概率取(0,1]區(qū)間的均勻隨機(jī)數(shù)作更新，O(i)為[1,2,…,n]中均勻分布的隨機(jī)整數(shù)，為保證種群個(gè)體中至少有一維會(huì)發(fā)生變異。為變異步長(zhǎng)，如

其中，i1、i2是[1,2,…,n]區(qū)間的隨機(jī)均勻整數(shù)，滿足i1、i2和i互不相同。

2.4 改進(jìn)算法步驟

綜上所述，改進(jìn)生物地理學(xué)優(yōu)化算法（HMBBO）步驟如下。

（1）采用初始化策略初始化種群，確定搜索空間的上下界，設(shè)置相關(guān)參數(shù)（種群規(guī)模NP、閾值E、閾值I、精英個(gè)體keep、最大變異率mmax）并評(píng)估適應(yīng)值。

（2）對(duì)種群按照適應(yīng)值進(jìn)行排序，保留精英個(gè)體。

（3）計(jì)算種群個(gè)體遷入率λ遷出率μ。

（4）利用遷移算子改變種群，進(jìn)行遷移過(guò)程。

（5）對(duì)種群進(jìn)行啟發(fā)式變異得到下一代種群，評(píng)估適應(yīng)值。

（6）判斷終止條件是否滿足，若滿足則終止，輸出最優(yōu)解，否則轉(zhuǎn)步驟（3）。

3 仿真結(jié)果與分析

為驗(yàn)證HMBBO算法的性能，本文采用4個(gè)經(jīng)典的標(biāo)準(zhǔn)測(cè)試函數(shù)做仿真，如表1所示，n為測(cè)試函數(shù)的維數(shù)，S為其約束空間，fmin為測(cè)試函數(shù)的全局最優(yōu)點(diǎn)。對(duì)標(biāo)準(zhǔn)BBO算法，GMBBO算法、CMBBO算法和HMBBO算法分別進(jìn)行測(cè)試，為了增加可比性，所有測(cè)試的公共參數(shù)均設(shè)置相同。其中最大進(jìn)化代數(shù)Kmax=500，種群NP=50，維數(shù)D=35，精英保留個(gè)數(shù)keep=3，最大遷入遷出率λ=μ=1，最大變異概率mmax=0.05，針對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行20次，所得測(cè)試結(jié)果如表2所示。

表1 基準(zhǔn)測(cè)試函數(shù)Table 1 Basic characters of test functions

表2 測(cè)試結(jié)果Table 2 Optimization results

圖2 Sphere進(jìn)化曲線Fig.2 Evolution curve of Sphere

圖3 Rastrigin進(jìn)化曲線Fig.3 Evolution curve of Rastrigin

圖2～圖5分別繪制了所測(cè)試的函數(shù)隨進(jìn)化代數(shù)搜索最優(yōu)值的進(jìn)化曲線，y坐標(biāo)軸為測(cè)試函數(shù)目標(biāo)值的對(duì)數(shù)坐標(biāo)軸。

圖4 Ackleys進(jìn)化曲線Fig.4 Evolution curve of Ackley

圖5 Griwank進(jìn)化曲線Fig.5 Evolution curve of Griwank

由圖2～圖5可知，標(biāo)準(zhǔn)的BBO算法、GMBBO算法及CMBBO算法在初期有一定的收斂速度但在后期收斂速度很慢。而改進(jìn)的BBO算法（HMBBO）隨著迭代的進(jìn)行體現(xiàn)了更好的全局搜索性能，其引入的啟發(fā)式變異算子，保證了算法在全局搜索中有較好的收斂速度，且改善了算法后期陷于停滯狀態(tài)，使得算法有效地跳出局部極值點(diǎn)，算法全局搜索性能明顯提高。

4 應(yīng)用研究

汽油調(diào)合是將各種不同屬性的組分油和少量添加劑按一定比例調(diào)合成符合規(guī)定的成品油。汽油調(diào)合和調(diào)度[9-11]的目的就是在滿足產(chǎn)品質(zhì)量和市場(chǎng)需求的前提下，達(dá)到產(chǎn)品利潤(rùn)最大和質(zhì)量過(guò)剩最小，其目標(biāo)函數(shù)模型往往伴隨大量的物料平衡約束、非線性調(diào)合屬性約束及其他約束，求解困難。近年來(lái)，一些學(xué)者采用遺傳算法、粒子群算法[12]等智能優(yōu)化算法及其他改進(jìn)的進(jìn)化算法求解油品調(diào)合和調(diào)度問(wèn)題[13-14]。

4.1 問(wèn)題描述

本文以某煉油廠汽油調(diào)合為背景，5種調(diào)合組分為：輕直餾石腦油、重整油、正丁烷、催化裂化汽油和烷基化油，兩種成品油分別為常規(guī)汽油和優(yōu)質(zhì)汽油。

（1）目標(biāo)函數(shù)。本文汽油調(diào)合生產(chǎn)調(diào)度的目標(biāo)函數(shù)為最終調(diào)合產(chǎn)品最大利潤(rùn)，其數(shù)學(xué)模型為

（2）約束條件[15]

物料平衡約束

產(chǎn)品市場(chǎng)需求約束

組分油庫(kù)存約束

調(diào)合質(zhì)量合格約束

式中，D為天數(shù)；N為產(chǎn)品油的種類數(shù)目；M為組分油的種類數(shù)目；Ppn為產(chǎn)品油n的價(jià)格；Pcn,m為組成產(chǎn)品油n的組分油m的價(jià)格；Vpn為產(chǎn)品油n的市場(chǎng)需求量；Vcn,m為生產(chǎn)產(chǎn)品油n的組分油m的使用量；Vpn min、Vpn max為產(chǎn)品油n最小、大市場(chǎng)需求量；Vcm min、Vcm max為組分油m可使用的最小、大量；Qpn為產(chǎn)品油n的質(zhì)量屬性（包括RON、MON 和RVP）；Qpn min、Qpn max為產(chǎn)品油n規(guī)定的質(zhì)量屬性標(biāo)準(zhǔn)。

4.2 數(shù)據(jù)及結(jié)果分析

表3 各組分屬性及經(jīng)濟(jì)數(shù)據(jù)Table 3 Property of components and economic data

本文做仿真應(yīng)用采用的數(shù)據(jù)如下，其各組分、產(chǎn)品的質(zhì)量指標(biāo)，市場(chǎng)供求關(guān)系數(shù)據(jù)見(jiàn)表3、表4。為與文獻(xiàn)[15]作比較，其中，種群規(guī)模設(shè)置為60，迭代次數(shù)為1000，目標(biāo)函數(shù)為

表4 各產(chǎn)品指標(biāo)及經(jīng)濟(jì)數(shù)據(jù)Table 4 Property of product and economic data

根據(jù)表中數(shù)據(jù)進(jìn)行多次仿真研究，得利潤(rùn)最大值為75249.737$（其中常規(guī)汽油各組分值分別為[3096.230,1385.700,148.621,2184.906,200.646],優(yōu)質(zhì)汽油各組分值分別為[2736.820,390.300,945.123, 4319.504,1604.235]),而文獻(xiàn)[15]中得到的最好結(jié)果為73165.0$（其中常規(guī)汽油各組分值分別是[4119.915,2523.325,135.874,1022.833,128.976]，優(yōu)質(zhì)汽油各組分值分別是[4767.480,1433.063,225.583, 3426.985,143.892]),由此驗(yàn)證了該算法的有效性。

5 結(jié) 論

本文提出的基于啟發(fā)式變異的生物地理學(xué)優(yōu)化算法（HMBBO）是在BBO算法基礎(chǔ)上改進(jìn)而來(lái)的。該算法采用啟發(fā)式變異算子，在一定范圍內(nèi)增加種群個(gè)體的多樣性，使算法不易陷于局部極值。4個(gè)測(cè)試函數(shù)仿真測(cè)試結(jié)果表明：該算法具有較好的收斂速度和全局搜算性能。且在汽油調(diào)合生產(chǎn)調(diào)度應(yīng)用研究中能夠找到合適的最優(yōu)利潤(rùn)，從而驗(yàn)證了該算法的有效性。

References

[1] WANG J D, WANG W L. Research of gasoline blending optimization based on genetic algorithm [J]. Control and Instruments in Chemical Industry, 2005, 32(1): 6-9.

[2] LI T. Modified PSO and the application for gasoline blending recipe optimization[D]. Dalian: Dalian University of Technology, 2006.

[3] SIMON D. Biogeography-based optimization [J]. IEEE Transactions on Evolutionary Computation, 2008, 12(6): 702-713.

[4] SIMON D, MEHMET E, DU D W. Markov analysis of biogeography-based optimization [OL]. 2009. http://academic. Csuohio. Edu/simond/bbo.

[5] HU L M, HUANG H, CAI Z Q. Improved evolutionary programming algorithm based on heuristic mutation [J]. Journal of South China University of Technology (Natural Science Edition), 2013, 41(5): 73-79.

[6] SARVIR S, GAGAN S. Mutation effects on BBO evolution in optimizing Yagi-Uda antenna design[C]//2012 Third International Conference on Emerging Applications of Information Technology (EAIT). IEEE, 2012: 47-51.

[7] CHEN J L. Biogeography-based optimization model based on Gaussian mutation [J]. Computer Simulation，2013, 30(7): 292-325.

[8] HAN S, PAN L W. An improved biogeography-based optimization algorithm and its application [J]. Yellow River, 2014, 36(2): 120-124.

[9] PEDRO A, CASTILLO C, VLADIMIR M. Multiscale models for integrated planning and scheduling(Ⅰ): Gasoline blending planning [J]. AIChE J., 2014, 60(6): 2158-2178.

[10] PEDRO A, CASTILLO C, VLADIMIR M. Multiscale models for integrated planning and scheduling(Ⅰ): gasoline blend scheduling [J]. AIChE J., 2014, 60(7): 2475-2497.

[11] JIA Z, IERAPETRITOU M. Mixed-integer linearprogramming model for gasoline blending and distribution scheduling [J]. Industrial & Engineering Chemistry Research, 2003, 42(4): 825-835.

[12] ZHAO X. Blending scheduling based on particle swarm optimization algorithm//Control and Decision Conference(CCDC)[C]. IEEE, 2010: 1192-1196.

[13] GLISMAN K, GRUHN G.Short-term scheduling and recipe optimization of blending processes [J]. Computers & Chemical Engineering, 2001, 25(4): 627-634.

[14] CHEN X, WANG N. Optimization of short-time gasoline blending scheduling problem with a DNA based hybrid genetic algorithm [J]. Chemical Engineering and Processing, 2010, 49(4): 1076-1083.

[15] ZHAO J, WANG N. A Bio-inspired algorithm based on membrane computing and its application to gasoline blending scheduling [J]. Computers & Chemical Engineering, 2011, 35(2): 272-283.

研究論文

Received date: 2015-12-03.

Foundation item: supported by the National Natural Science Foundation of China(61333010, 61422303) and Shanghai Science and Technology Committee Program (13111103800).

Improved biogeography-based optimization algorithm and its application in gasoline blending scheduling

WANG Yumei, CHEN Hui, QIAN Feng
(Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China)

Abstract:The biogeography-based optimization (BBO) is a new swarm intelligence algorithm. To improve the global searching ability, solve the prematurity of BBO, a heuristic mutation operator is designed, which based on the differential information among the population individuals. It makes up the lack of the heuristic information on Gauss, Cauchy mutation operators. And the nonlinear migration model was introduced to the BBO considering to the natural environment. Tests are carried out through four standard test functions on the standard BBO, GMBBO, CMBBO and HMBBO independently, the results shows that HMBBO has a preferable convergence rate and search accuracy. The application of gasoline blending scheduling shows that HMBBO is effective.

Key words:algorithm; optimization; simulation; gasoline blending scheduling

DOI：10.11949/j.issn.0438-1157.20151812

中圖分類號(hào)：TE 624

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：0438—1157（2016）03—0773—06

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（61333010，61422303）；上海市科學(xué)技術(shù)委員會(huì)項(xiàng)目(13111103800)。

Corresponding author:CHENG Hui, huihyva@ecust.edu.cn