基于AEA算法的自适应惩罚函数求解约束优化及其在丁烯烷化过程的应用1
桑志祥，李绍军，张杰
(华东理工大学 化工过程先进控制和优化技术教育部重点实验室， 上海 200237)
摘要：本文提出了一种基于AEA算法处理约束问题的自适应惩罚函数法。该算法通过统计迭代种群中个体对每个约束条件违反的次数，判定各约束的强弱地位，动态自适应地调整各个约束的惩罚系数，对于强约束给予较大的惩罚系数。同时对目标函数做出了相适应区分修改，使得可行解和不可行解的目标函数值出现一定的区分，目标函数项和惩罚项趋于平衡，避免了惩罚力度过大或过小，有利于算法前期快速进入可行解区域，后期寻找最满意解。通过标准测试函数试验结果与DE+AMP、SSaDE算法进行比较，表明了本文提出的方法具有良好的适用性以及全局优化性能，将该方法应用于丁烯烷化过程的约束优化，取得了令人满意的结果。 关键字：自适应惩罚函数；约束优化；AEA；丁烯烷化过程
中图分类号：TP301 文献标识码：A
A New Adaptive Penalty Function Based AEA Algorithm for Solving Constrained Optimization Problems and Its Application in Process Optimization of Butene Alkylation
SANG Zhi-xiang, LI Shao-jun, ZHANG Jie
(Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education,
Shanghai, East China University of Science and Technology, 200237, China)
Abstract: A new adaptive penalty function method based on the AEA algorithm is proposed to process constrained problems in this paper. It can determine the intensity of each constraint by the conditions breach number of each constraint in iterative population and adjust the punishment coefficient of various constraints dynamically and adaptively. And greater punishment coefficient will be given for a stronger constraint. In addition, the objective function is made a change accordingly, so that it contributes to distinguishing the objective function values between feasible solution and unfeasible solution. The improvements of objective function and penalty are helpful for balancing them and avoiding the penalty is too large or too small. The algorithm would quickly enter the feasible solution area in earlier stage, and find the most satisfied solution later. Comparisons of the standard test functions results with DE+AMP, SSaDE algorithm show that the proposed method has good applicability and global optimization performance. Furthermore, this method was applied to the process optimization of butene alkylation and satisfactory result was achieved.
Keywords: adaptive penalty function; constrained optimization; AEA; butene alkylation process
1.引言
现代化工系统是一类典型的具有规模大、范围大、变量多、约束条件多等特点的复杂系统，其数学模型难于建立或较为复杂，求解困难，实现最优化的困难很大。许多化工过程建模实际是对非测量参数进行估计，由于实际过程中存在很多限制条件，所以在建模时需要增加相应的约束条件，这也导致整个优化过程变得复杂，对于参数估计工具更高。例如用液态硫酸来烷化汽车燃料是炼油厂最常见的一种催化过程，在烷化过程建模中，物料组成分多，影响因素多且相互间关系复杂。
目前，求解非线性约束优化问题的方法可分为两类：确定性和随机性方法[1]。确定性方法需要函数的
1
基金项目：国家自然科学基金的资助(20976048, 21176072)。
作者简介：桑志祥(1987-)，男，江苏兴化人，华东理工大学硕士研究生。联系人：李绍军，lishaojun@ecust.edu.cn。
导数等信息，且对函数的连续性和可微性要求较强，使其应用受到一定程度的限制。随机性方法一般只需利用函数值，对函数分析性要求较低，适用于解决一般的复杂工程优化问题，且适应面宽泛。进化算法作为随机性方法已经成功地应用于解决各种有约束优化问题[2]。利用进化算法求解约束问题对算法自身性能和约束处理方法具有极大的依赖性，特别是后者对算法的计算效率、效果有着极为重要的影响。王凌[3]等人对几种代表性的约束处理方法进行了综述研究，包括惩罚函数法、随机排序法、基于可行性的方法等等。其中惩罚函数法因为执行简单，是进化算法处理有约束优化问题最常用的方法。文献[4]对惩罚函数的运作方式进行了详细的介绍。自适应惩罚函数法具有较好的优化效果，它能利用搜索过程中的反馈信息动态自适应地调节参数，减轻了使用者对惩罚系数的人为设定。例如在文献[5]中，Lemonge和Barbosa提出了一种自适应惩罚方法（AMP），惩罚系数根据各约束条件违反程度决定，难满足的约束条件设定较大的惩罚系数。
本文基于AEA（Alopex-based Evolutionary Algorithm）算法[6]提出了一种新的自适应惩罚函数法处理约束问题。新的自适应惩罚函数法，充分利用函数各约束条件被违反次数统计量判定约束强弱，动态自适应地调整各个约束的惩罚系数，同时考虑到目标函数与惩罚项之间的关系，对目标函数做出了相适应修改，使得两者间的关系更加趋于平衡，避免了惩罚力度过大或过小。通过标准测试函数试验结果表明，新方法取得令人满意的结果，且是一种结构简单、易于实现、通用性强、性能稳定的方法。
2. 基本AEA算法
AEA（Alopex-based Evolutionary Algorithm）算法[6]是一种将Alopex的计算方式和群体进化相结合的新型群智能进化算法。通过与GA算法、PSO算法、DE算法在标准测试函数和动力反应学参数估计的测试结果比较，表明AEA算法具有较好的全局收敛性能，在无约束优化问题中表现较为优异。目前，GA算法、PSO算法、DE算法等进化算法在约束优化问题求解中得到广泛应用，且取得较为满意的效果。
Li Shaojun等[6]根据进化算法的群优化和Alopex算法的根据目标函数变化的信息来影响来改变变量的特点的启发，提出了一种新的群智能进化算法—AEA算法。在AEA算法中，利用每次迭代产生两个种群直接进行Alopex操作实现群体进化。算法的总体思想是假设第k次迭代的种群为X1k，首先将该种群内的个体重新排序得到新的种群X2k，然后分别计算X1k, X2k对应位置个体的差值和目标函数值之差，进而得到个体之间相关性的表达式即自变量之差与对应目标函数值之差的乘积。根据该乘积可计算出一个概率pk，概率pk决定了X1k的各个个体分量的行走方向，在一定程度上避免了算法过早陷于局部最优。该概率pk体现了全局搜索和局部搜索的权衡。所有个体都以较大概率向梯度下降的方向进行搜索（局部搜索）和以较小的概率向梯度下降相反的方向搜索（全局搜索）。
3. 一种新型自适应惩罚函数处理方法
约束优化问题一般转化下述模型：
mins..tf(X)gi(X)?0i?1,2,...,q;hi(X)?0i?q?1,q?2,...,m (1)
UxLj?xj?xjj?1,2,...,n其中，X为决策变量，f(X)为目标函数；gi(X)?0(i?1,2,...,q)表示不等式约束，q为不等式约束个数；
Uhi(X)?0(i?q?1,q?2,...,m)表示等式约束，(m?q)为等式约束个数；xLj与xj分别为第j个决策变量xj的下限与上限约束，n表示决策变量的个数，即优化问题的维数。
惩罚函数法因为执行简单、有效而得到了广泛的应用，其主要思想是对目标函数添加惩罚项来构造惩罚适应值函数，将约束优化问题转换为无约束问题进行处理。但在实际应用惩罚函数中，发现惩罚参数的选取比较困难，而算法的性能又强烈地依赖于参数。如果惩罚项参数过火，可能可以保证进入可行域，但
是会降低对不可行域的探索，因此失去了由不可行解提供的一些有价值的信息；如果惩罚项参数过小，导致惩罚项相对于目标函数值过小而被忽略，搜索时间更多地花费在不可行域上[7]。针对这种情况，本文提出了一种结构简单的自适应惩罚函数法。
首先，对种群中的候选解x违反每一约束条件的程度函数vi(x)定义如下：
?max{0,g(X)}ifi?1,2,...,q?ivi(X)?? (2)
?ifi?q?1,q?2,...,m?hi(X)其中q为不等式约束的个数，（m-q）为等式约束的个数。若候选解x违反约束条件，则必然有vi(X)?0，且vi(X)的值越大说明该候选解违反约束程度越大；若候选解不违反约束条件，即为可行解时，显然有
vi(X)?0。通过对目标函数引进一个惩罚项来构造惩罚适应值函数，定义如下式：
?f(X)?F(X)??m?fmax??ki?vi(X)i?1?ifXisfeasibleotherwise (3)
fmax?max{f(X1),f(X2),...,f(XM)} (4)
其中，M为种群的规模。当候选解为可行解时，惩罚适应值函数值F(X)等于原目标函数值f(X)；当候选解违反约束条件时，则通过（3）式构造一个添加惩罚项的惩罚适应值函数值F(x)，这里新的惩罚适应值函数值F(X)分成两步进行构造，第一步构造目标函数，由于候选解已经违反约束，其目标函数值显然不是期望的结果，另外为了区分不可行解与可行解，这里利用当代种群中最大的目标函数值fmax替换不可行解的目标函数值f(Xi)，从数值上不难发现，经替换后不可行解的目标函数值都不小于可行解的目标函数值，从而在目标函数f(X)这一方面产生了明显的区分。第二步即为添加惩罚项 ，由式（2）和 式（5）可以发现惩罚值?ki?vi(X)始终为非负数，这更加有利于区分可行解与不可行解（即使在原种群中
i?1m可行解目标函数值为最大值）。同时考虑到不同约束条件存在强弱之分，相应地强约束应给予较大惩罚系数，反之弱约束给予较小惩罚系数。本文中通过每代种群中所有个体违反同一约束条件的次数判定强弱，即对于同一约束条件，违反的个体数越多则说明该约束较强，反之则较弱。惩罚系数定义如下式：
ki?fmax?10si/N(i?1,2,...,m) (5)
其中，si表示第i个约束条件在每代种群中被违反的次数总和。
在进化初期，进入种群的可行解较少，相应地各约束条件被违反次数较大，惩罚系数必然较大；随着进化发展，种群中可行解越来越多，自然各约束条件被违反次数减少，惩罚系数不断减小，这有利于将搜索策略的重心从搜索可行解转移到搜索好的目标函数值。同时也可以让有较小目标函数值和较小违反约束条件的非可行解进入种群，这一点对于最优解刚好落于可行域和不可行域的边界上非常重要[7]。除此之外，惩罚函数法的另外一个技术难点即为平衡目标函数值与惩罚值之间的关系，本文在惩罚系数中利用fmax既保证了惩罚项始终为正数同时又保证了目标函数值和惩罚值处于平衡的关系。新提出的自适应惩罚函数结合AEA算法的计算流程可以归纳如下(以求函数最小值为例)：
step 1：设定种群大小M，目标函数值及最大迭代次数K,迭代次数k=1。初始化种群S，将个体随机散布在解空间中，并计算每个个体的目标函数值。
step 2：判断种群Sk各个个体是否满足约束条件，若满足条件，则该个体惩罚适应值函数值F(Xk)等于原目标函数值；否则根据式(2)-(5)计算惩罚适应值函数值。
step 3：根据种群Sk生成两个顺序不同的种群S1k,S2k(相同的个体不出现在相同位置)。设在种群S1k和S2k中相应的个体作为X1k和X2k，计算两个体的向量之差和惩罚适应值函数的积Ck，由此得到温度
Tk。
step 4: 根据文献[8]计算概率向量pk,确定个体X1k的行走方向，再根据AEA算法对个体X1k中的每个变量进行更新，并按照是否满足约束条件计算新的惩罚适应值函数值。
step 5: 对比个体X1k的惩罚适应值函数值改变情况，如果获得改进，则用新的个体替换原个体X1k，否则种群S1k中的相应个体保持不变。
step 6:评价种群S1k，判断最优个体目标函数是否达到目标值，达到目标值输出全局最优值，否则迭代次数k加1，利用S1k，替换种群Sk?1。
step 7: 判断是否达到最大迭代次数，若超过最大迭代次数，输出全局最优值，退出计算，否则返回step 2。
4. 数值试验
为了测试检验AEA结合新的自适应惩罚函数法解决约束优化问题的性能，从文献[8]、[9]中选取了6
个标准测试函数作为数值试验对象,它们都是高维的带有约束条件的函数优化问题，约束条件包含不等式约束和等式约束。
表1 AEA求解结果与SSaDE、DE+AMP的比较
Table1 Comparison results among AEA, SSaDE and DE+AMP
Test function / Optimum
Best
F1/-15
Worst Mean St.dev Best
F2/0.8036
Worst Mean St.dev Best
F3/1
Worst Mean St.dev Best
F4/-30665.5
Worst Mean St.dev Best
F5/24.306
Worst Mean St.dev Best
F6/0.75
Worst Mean St.dev
AEA -15 -15 -15 2.47E-11 0.8036 0.7849 0.7978 0.00616 0.9015 0.7904 0.8477 0.02809 -30665.5 -30665.5 -30665.5 1.28E-10 24.346 24.680 24.477 0.08458 0.75 0.77 0.752 0.0047
SSaDE-15 -9 -12.95 1.836 0.8036 0.5701 0.714 3.32254 0.747 0 0.0517 1.56738 -30665.5 -30665.5 -30665.5
0 24.306 27.602 24.74 1.1826 0.75 1 0.94 0.66446
[8]
DE+AMP[9]
-15 -13 -8 2.394 0.8036 0.6066 0.7405 0.04906 0.2864 0 0.0169 0.06382 -30665.5 -30665.5 -30665.5
0 24.306 29.0591 25.048 1.37164 1 1 1 0
为了便于与文献[8]、[9]结果进行比较，本文同样对每个函数独立运行30次，并记录其最好值，最差值，平均值和标准差，详见表1。文献[8]采用的是自适应DE算法(SSaDE)方法，文献[9]采用的是DE算法结合自适应惩罚函数法(AMP)方法。从表中的比较数据可以发现，本文提出的新方法尽在管函数F3、F5未能找到最优值，但相对于其他两种方法无论是均值还是稳定性都有一定的优势。F2被认为是最难解
决的问题，它是一个非常复杂的非线性高维多峰函数。新方法对其运行结果非常令人满意，较小的标准差也反映了算法具有较好的稳定性。在函数F1、F6中，新方法明显取得了更好的结果。这些都说明本文提出的新的自适应惩罚函数法在处理约束优化问题具有很大的潜力。
5.丁烯烷化过程的约束优化
丁烯烷化过程首先将含100%丁烯的烯烃进料、循环纯异丁烷、100%的异丁烷补充流和新鲜的酸催化
剂引入反应器，再将废酸从反应器内移走，反应产物还将通过分离器使异丁烷与烷基化物分离。Adjima等[12]为该过程建立了以收益（profit）最大为目标的优化模型，具体流程示意图以及优化表达式如文献[10]。在该优化模型中，共含有7非线性变量，14个约束条件，众多的约束条件增加优化的难度。其中7个非线性变量含义为：x1为烯烃流速（桶/天），x2为酸添加速率（千磅/天），x3为烷基化物产率（桶/天），x4为酸强度（质量分数），x5为马达法辛烷值，x6为异丁烷补充流与烯烃的比率，x7为F-4性能值。文献[10]采用基于?的分支定界法(α-based branch and bound,αBB)对其求解，αBB是一种确定性的全局优化算法,它构造了包含最优点的上下界收敛序列,对于二次可微约束非线性优化问题能以任意精度逼近全局最优解,但参数α较难确定,且搜索时间很长。文献[11]采用基于蚁群算法求解约束问题，具有一定的随机性，但是易于陷入局部最优且算法的稳健性较差。
本文采用基于AEA算法的自适应惩罚函数法对丁烯烷化过程模型求解,为与文献[10][11]具有比较性，本文设定种群规模M=50，迭代次数K=2000，在容许度δ为3个不同值下各独立运行10次。表2列出了运行结果，包括目标函数值profit的最优解，相应的违反约束条件的第1、第3、第6个约束值，以及运行10次最优值的平均值、最好值和最差值。表2还列出了CACS算法和αBB算法的运行结果,数据取自文献[11]。通过对比表2数据不难发现，CACS能够取得符合要求的解，但是均陷入的局部最优，且在δ=5×10-4时，违反了第3个约束；αBB算法则三个约束均处于违反状态，第6个约束尤为严重；而通过数据可以看出，本文提出的自适应惩罚函数法在三种不同的容许度下，均取得了较为理想的最优值，所有的约束全部满足，目标函数值profit的最大值相比其他两种算法取得了较大的提高。基于AEA算法的自适应惩罚函数法对于约束优化问题的适用性、稳健性和全局优化性能均令人满意。
表2 AEA算法、CACS算法以及αBB算法的数据结果比较 Table 2 Comparison of results by AEA, CACS and αBB with different δ
Methodsδ=0AEAδ=5×10-6δ=5×10δ=0CACSαBBδ=5×10δ=5×10-4x11698.01694.31694.51698.8-6-4x248.72248.66047.53054.17853.3654.34653.66x33030.13028.03029.13031.53034.73033.23031.3x490.99191.00690.83690.13790.18390.18390.11x594.99794.99794.99994.99294.99994.99995.000x69.7059.6839.84810.53510.32210.5110.5x7153.49153.52153.53153.51153.66153.33153.53g1-4.496-0.4534-0.1488-0.272-1.994-0.6440.0165g3-0.592-0.066-0.267-0.026-0.0644.58874.7521g6-407-1916-36-4409-2155-20801727.9Best1874.11874.61876.11763.11763.81776.81772.8profitAverage1870.11871.41872.61761.01762.51775.1-Worst1864.91864.91864.91757.41758.71772.5-1700.41700.61698.2
6. 结论
本文提出了一种新的自适应惩罚函数法，它充分利用函数各约束条件的强弱之分，动态自适应地调
整各个约束的惩罚系数，同时考虑到目标函数与惩罚项之间的关系，对目标函数做出了相适应修改，使得两者间的关系更加趋于平衡，避免了惩罚力度过大或过小。通过标准测试函数试验结果表明，新方法取得令人满意的结果，且是一种结构简单、易于实现、通用性强、性能稳定的方法，有非常大的潜力来处理实际工程各种约束优化问题。将基于AEA算法新型自适应惩罚函数法应用于丁烯烷化过程的约束优化,取得了令人满意的结果,进一步表明了本文提出的方法对约束优化问题的适用性、稳健性和全局优化性能。
符号说明：
F(X)
—惩罚适应值函数值 — 目标函数 — 最大的目标函数值 — 不等式约束 — 等式约束 — 当前的迭代次数 — 惩罚系数 — 种群大小 — 约束个数总数 — 决策变量的个数 — 行走方向概率 — 收益最大值 — 不等式约束个数
si
—第i个约束条件在种群中被违反次数总和 — 候选选解x违反每一约束条件的程度函数 — 候选解x违反每一约束条件的程度函数 — 变量的下限 — 变量的下限 — 烯烃流速（桶/天） — 酸添加速率（千磅/天） — 烷基化物产率（桶/天） — 酸强度（质量分数） — 马达法辛烷值
— 异丁烷补充流与烯烃的比率 — F-4性能值 — 容许度
f(X) fmax gi(X) hi(X) k ki
F(X)
vi(x)
xL
xU
x1
x2 x3 x4 x5 x6
M m n
pk
profit
x7
δ
q
参考文献 [1]
Jonies J.A, Houck R.C. On the Use of Non-stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with GA's[J]. Proc IEEE Int of Evol Comp, 1994, 26(2):579-584.
[2] Michalewicz Z, Schoenauer M. Evolutionary algorithm for constrained parameter optimization problems[J]. Evolutionary Computation, 1996, 4(1):1-32.
[3] WANG Ling(王凌), HE Qie(何锲), JIN Yi-hui(金以慧). Summary of Intelligent Constraint Handling Techniques(智能约束处理技术综述)[J]. Control and Instruments in Chemical Industry(化工自动化及仪表), 2008, 35(1): 1-7.
[4] Coello C.A.C. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art[J]. Computer Methods in Applied Mechanics and Engineering, 2002, 191(11-12): 1245-1287.
[5] Afonso C C, Lemonge, Helio J C. An adaptive penalty scheme for genetic algorithms in structural optimization[J]. International Journal For Numerical Methods In Engeineering, 2004, 59(5):703-736.
[6]
DONG Yue-hua(董跃华), SANG Zhi-xiang(桑志祥), LI Shao-jun(李绍军). Improved AEA and its Simulation on Parameter Estimation of Heavy Oil Thermal Cracking Three Lumps Model(改进的AEA算法及其在重油热解模型参数估计中的应用)[J]. J Chem Eng of Chinese Univ (高校化学工程学报), 2012, 26(2):332-337.
[7] GAN Min(甘敏), PENG Hui(彭辉). A New Adaptive Penalty Function Based Algorithm for Solving Constrained Optimization Problems(一种新的自适应惩罚函数算法求解约束优化问题)[J]. Information and Control(信息与控制),2009, 38(1): 24-28.
[8] Huang V L, Qin A K, Suganthan P N. Self-adaptive differential evolution algorithm for contrained real-parameter optimization[J]. IEEE congress on evolutionary computation, 2006: 17 - 24.
[9] Silva E K, Barbosa H J C, Lemonge A C C. An adaptive constraint handling technique for differential evolution in engineering optimization[J]. International conference on engineering optimization, 2008: 46-56.
[10] Adjiman C S, Dallwing S, Floudas C A, Neumaier A. A global optimization method, αBB, for general twice-differentiable constrained
NLPs-Ⅰ.Theoretical advances[J]. Computers and Chemical Engineering, 1998, 22(9): 1137 -1158.
[11] HE Yi-jun(贺益君), CHEN De-zhao(陈德钊). Constrained ant colony system and its application in process optimization of butene
alkylation(连续约束蚁群优化算法的构建及其在丁烯烷化过程中的应用)[J]. J Chem Ind and Eng(China)(化工学报), 2005, 56(9): 1708-1713.