改进生物地理学优化算法及其在汽油调合调度中的应用

王玉梅，程辉，钱锋（华东理工大学化工过程先进控制和优化技术教育部重点实验室，上海 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