改進生物地理學優化算法及其在汽油調合調度中的應用

王玉梅，程輝，錢鋒（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

?

改進生物地理學優化算法及其在汽油調合調度中的應用

王玉梅，程輝，錢鋒
（華東理工大學化工過程先進控制和優化技術教育部重點實驗室，上海 200237）

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

關鍵詞：算法；優化；仿真；汽油調合和調度優化

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

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

引 言

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

生物地理學是研究生物種群在時間和空間上分布的一門學科。Simon[3]于2008年提出了生物地理學優化算法（BBO）。該算法主要通過模擬生物種群在不同棲息地之間的遷移，以實現各棲息地之間信息的交流和共享，從而找到所求問題的最優解。Simon等[4]進一步系統地分析了BBO算法的收斂性，盡管BBO算法參數少、收斂速度較快，實現較簡單，但是標準BBO算法也存在不足之處，如全局搜索能力不強，易陷于局部最優解。

針對BBO算法易陷于局部極值的問題，本文提出了一種改進的生物地理學優化算法（HMBBO）。在原算法的基礎上設計了一種基于種群個體信息差異的啟發式變異算子[5]，彌補了Gauss變異、Cauchy變異算子缺乏啟發式信息的不足，從總體上加快了算法的收斂速度，使優化不會過早地向局部最優點方向聚集，從而保證算法在搜索空間的全局搜索能力。并且本文采用余弦遷移模型，使生物地理學優化算法（BBO）能更好地適用于不同特點的優化問題。采用4個標準測試函數對此優化算法進行測試并應用于汽油調合調度優化實例。

1 生物地理學優化算法

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

BBO算法主要通過遷移和變異[6]搜索全局的最優解。

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

當某一個個體滿足遷移條件時，用遷出率μ選取新個體Y以替換原個體。

BBO算法根據每個棲息地的種群數量概率Pi對棲息地的特征向量進行變異，以此增加種群的多樣性，避免尋優過程過早的陷于局部最優解中。每個點的變異概率為

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

2 改進的生物地理學優化算法

標準BBO算法采用隨機變異策略，它是在一定的基因取值范圍之內，采用隨機值替代即將發生變異的基因。文獻[7]引入高斯變異策略，高斯變異每一次變異產生的幅度是不同的，變異所產生的取值服從高斯分布。它用高斯分布函數替代隨機變異所產生的隨機數，即式（5）。另一種變異策略為柯西變異[8]，它與高斯變異原理相同，其原理如式（6）。

本文采用啟發式變異算子，使得BBO算法的變異策略可以隨著所優化變量的狀態進行動態更新，從而實現算法的啟發式迭代，也使得解的部分分量在一定范圍內產生較大的變化，增強解空間的搜索能力，使得算法跳出局部極小值，提高算法的全局搜索能力。

2.1 個體表示及其初始化

新算法采用實數編碼。設種群數目為NP，其中個體解向量為

初始化為

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

2.2 非線性遷移模型

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

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

2.3 啟發式變異算子

文中提出一種啟發式變異的BBO算法，采用啟發式變異算子，按照式（11）產生新的變異個體。

式中，當迭代次數G=0時，?i取（0,1] 區間的均勻隨機數；當G＞0時，?i則以0.1的概率取（0,1]區間的均勻隨機數作更新，并以0.9的概率保持不變。α (j)是[0,1]區間的均勻隨機數，βi為變異控制系數，以0.1的概率取(0,1]區間的均勻隨機數作更新，O(i)為[1,2,…,n]中均勻分布的隨機整數，為保證種群個體中至少有一維會發生變異。為變異步長，如

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

2.4 改進算法步驟

綜上所述，改進生物地理學優化算法（HMBBO）步驟如下。

（1）采用初始化策略初始化種群，確定搜索空間的上下界，設置相關參數（種群規模NP、閾值E、閾值I、精英個體keep、最大變異率mmax）并評估適應值。

（2）對種群按照適應值進行排序，保留精英個體。

（3）計算種群個體遷入率λ遷出率μ。

（4）利用遷移算子改變種群，進行遷移過程。

（5）對種群進行啟發式變異得到下一代種群，評估適應值。

（6）判斷終止條件是否滿足，若滿足則終止，輸出最優解，否則轉步驟（3）。

3 仿真結果與分析

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

表1 基準測試函數Table 1 Basic characters of test functions

表2 測試結果Table 2 Optimization results

圖2 Sphere進化曲線Fig.2 Evolution curve of Sphere

圖3 Rastrigin進化曲線Fig.3 Evolution curve of Rastrigin

圖2～圖5分別繪制了所測試的函數隨進化代數搜索最優值的進化曲線，y坐標軸為測試函數目標值的對數坐標軸。

圖4 Ackleys進化曲線Fig.4 Evolution curve of Ackley

圖5 Griwank進化曲線Fig.5 Evolution curve of Griwank

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

4 應用研究

汽油調合是將各種不同屬性的組分油和少量添加劑按一定比例調合成符合規定的成品油。汽油調合和調度[9-11]的目的就是在滿足產品質量和市場需求的前提下，達到產品利潤最大和質量過剩最小，其目標函數模型往往伴隨大量的物料平衡約束、非線性調合屬性約束及其他約束，求解困難。近年來，一些學者采用遺傳算法、粒子群算法[12]等智能優化算法及其他改進的進化算法求解油品調合和調度問題[13-14]。

4.1 問題描述

本文以某煉油廠汽油調合為背景，5種調合組分為：輕直餾石腦油、重整油、正丁烷、催化裂化汽油和烷基化油，兩種成品油分別為常規汽油和優質汽油。

（1）目標函數。本文汽油調合生產調度的目標函數為最終調合產品最大利潤，其數學模型為

（2）約束條件[15]

物料平衡約束

產品市場需求約束

組分油庫存約束

調合質量合格約束

式中，D為天數；N為產品油的種類數目；M為組分油的種類數目；Ppn為產品油n的價格；Pcn,m為組成產品油n的組分油m的價格；Vpn為產品油n的市場需求量；Vcn,m為生產產品油n的組分油m的使用量；Vpn min、Vpn max為產品油n最小、大市場需求量；Vcm min、Vcm max為組分油m可使用的最小、大量；Qpn為產品油n的質量屬性（包括RON、MON 和RVP）；Qpn min、Qpn max為產品油n規定的質量屬性標準。

4.2 數據及結果分析

表3 各組分屬性及經濟數據Table 3 Property of components and economic data

本文做仿真應用采用的數據如下，其各組分、產品的質量指標，市場供求關系數據見表3、表4。為與文獻[15]作比較，其中，種群規模設置為60，迭代次數為1000，目標函數為

表4 各產品指標及經濟數據Table 4 Property of product and economic data

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

5 結 論

本文提出的基于啟發式變異的生物地理學優化算法（HMBBO）是在BBO算法基礎上改進而來的。該算法采用啟發式變異算子，在一定范圍內增加種群個體的多樣性，使算法不易陷于局部極值。4個測試函數仿真測試結果表明：該算法具有較好的收斂速度和全局搜算性能。且在汽油調合生產調度應用研究中能夠找到合適的最優利潤，從而驗證了該算法的有效性。

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

中圖分類號：TE 624

文獻標志碼：A

文章編號：0438—1157（2016）03—0773—06

基金項目：國家自然科學基金項目（61333010，61422303）；上海市科學技術委員會項目(13111103800)。

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