求解约束化工优化问题的混合布谷鸟搜索算法

摘 要：

针对布谷鸟搜索算法存在收敛速度慢和易陷入局部最优等缺陷，提出一种基于Rosenbrock搜索和柯西变异的混合布谷鸟搜索算法用于求解约束化工优化问题。该算法首先采用佳点集方法对鸟窝位置进行初始化，为全局搜索的多样性奠定基础；然后利用Rosenbrock搜索算法对当前最优位置进行局部搜索，以提高算法的收敛速度；最后对当前最优解进行柯西变异以避免算法陷入局部最优。两个约束化工优化问题的实验结果表明了该混合算法的有效性。

关键词：化工优化； 布谷鸟搜索算法； Rosenbrock局部搜索； 佳点集方法； 柯西变异

中图分类号： TP301.6

文献标志码：A

Hybrid cuckoo search algorithm for solving constrained

chemical engineering optimization problems

Abstract：

The Cuckoo Search （CS） algorithm has a few disadvantages in the global searching， including slow convergence and high possibility of being trapped in local optimum. To overcome these disadvantages， a effective hybrid CS algorithm based on Rosenbrock local search and Cauchy mutation was proposed to solve the constrained numerical and chemical engineering optimization problems. Firstly， good point set method was used to initiate bird nests position， which strengthened the diversity of global searching. Secondly， for the current best position， Rosenbrock local search technique was introduced to improve the convergence speed of CS algorithm. Thirdly， a Gaussian mutation operator would be given on the global optimum of each generation， thus， the algorithm could effectively jump out of local minima. The experimental results with several constrained numerical functions and chemical engineering optimization problems show a promising performance of the proposed algorithm.

Key words：

chemical engineering optimization； Cuckoo Search （CS） algorithm； Rosenbrock local search； good point set method； Cauchy mutation

0 引言

在化工生产过程中的许多优化问题通常含有约束条件，目标函数具有高度非线性。不失一般性，约束化工优化问题可以描述为一个含有等式约束、不等式约束和变量界约束的非线性规划问题：

传统的基于梯度信息的优化方法难以对问题（1）进行有效的求解。与传统的优化方法相比，以遗传算法（Genetic Algorithm， GA）、粒子群优化（Particle Swarm Optimization， PSO）算法、差分进化算法、蚁群算法等为代表的进化算法是一类基于种群迭代的全局搜索方法，具有不依赖于所求问题的梯度信息、易于实现，能以较高概率收敛于问题的全局最优解等特点，因此进化算法在函数优化、神经网络训练、参数优化、机器学习以及工程应用领域中得到了广泛的应用[1-2]。鉴于进化算法是一类基于无约束的优化方法，在处理约束优化问题时要结合合适的约束处理技术。在过去的几十年中，研究者提出了大量的约束优化进化算法[3]。

布谷鸟搜索（Cuckoo Search， CS）算法是英国剑桥大学学者Yang和Deb于2009年提出的一种新的全局启发式搜索方法[4]。CS算法是基于对布谷鸟寻窝产卵行为的模拟，已被证明在收敛速度和精度方面都要优于遗传算法和粒子群优化算法[4]。由于CS算法具有算法简单、参数设置少、易于实现等特点，因此在很多领域有着广泛的应用。

Gandomt等[5]提出一种求解结构优化问题的CS算法。Walton等[6]提出一种基于信息交换的CS算法用于求解全局优化问题。Yang和Deb[7]提出一种多目标优化CS算法用于求解工程设计多目标优化问题。上述三种算法是利用基本CS算法进行求解，然而，基本CS算法存在后期收敛速度慢、易陷入局部最优等缺点。

Haupt等[8]指出，一个多样性较好的初始种群对寻找全局最优解很有帮助。另外，基于种群迭代的启发式搜索算法与确定性方法或局部搜索算法混合可以平衡算法的勘探和开采能力。因此，本文提出一种基于Rosenbrock局部搜索和柯西变异的混合CS算法用于求解约束化工优化问题。实验结果表明了混合算法能有效地处理复杂优化问题。

1 基本布谷鸟搜索算法

布谷鸟搜索（CS）算法是模拟自然界中布谷鸟寄生孵育雏鸟的生物行为而构建出的随机搜索算法，其原理为：将布谷鸟所选宿主鸟窝映射为搜索空间中的解，宿主鸟窝所在位置的优劣用来表示所求问题中解的适应度值，布谷鸟搜寻和选择鸟窝的过程表示为算法的搜索和优化迭代过程。与真实的布谷鸟寄生孵育行为相比，CS算法作了如下假设[4]：

1）布谷鸟一次只产一个卵，且随机放在某一个被选择的鸟窝中；

2）位置最好的宿主鸟窝将会保留到下一代；

3）布谷鸟可利用的宿主鸟窝数量n是固定的，放置在宿主鸟窝中的布谷鸟蛋被发现的概率Pa∈[0，1]。

基本CS算法的基本步骤如下：

步骤1 设置参数，随机产生N个鸟窝位置。

步骤2 评价各个鸟窝位置的适应度值，确定全局最优位置，并保留到下一代。

步骤3 利用式（2）和（3）进行位置更新，评估更新后的位置，并与原位置进行比较，较优的位置进入下一代。

2 混合布谷鸟搜索算法

2.1 种群初始化

由文献[8]可知，对于基于种群迭代的随机搜索算法，多样性较好的初始种群对算法全局寻优效率很有帮助。传统的CS算法通常是在搜索空间中随机产生初始种群，这样可能导致初始群体多样性较差，从而会影响算法的效率，而所期望的是产生初始群体时应保持其具有较好的多样性。

佳点集方法是一种有效的、可以减少实验次数的实验方法。在相同取点数个数的条件下，佳点序列要比其他方法选取的点序列更均匀[9]。因此，本文采用佳点集方法生成初始种群，从而保证了初始种群的多样性。图1是采用佳点集方法产生的规模为80的二维初始种群分布。

从图1可以清晰地看出，与随机方法相比，佳点集方法生成的初始种群个体分布均匀，没有重叠点，具有较好的多样性。

2.2 Rosenbrock局部搜索

Rosenbrock搜索算法是一种不使用梯度信息的直接方法，具有较强的局部搜索能力，它包括两个过程，即探测过程和构造搜索过程，其具体步骤[10]如下：

第一阶段：探测过程。

2.4 约束处理技术

布谷鸟搜索算法是基于无约束的随机优化算法，利用它求解约束优化问题时一定要结合约束处理技术。Deb提出了一种基于联赛选择算子的可行性规则来选择个体[11]：

1）如果被选择的两个个体均为可行解，则目标函数值小的要优；

2）如果被选择的两个个体，一个为可行解，另一个为不可行解，则可行解要优；

3）如果被选择册两个个体均为不可行解，则约束违反度低的要优。约束违反度为

2.5 算法步骤

步骤1 设置算法参数，令k=1。

步骤2 在搜索空间中利用佳点集方法产生初始鸟窝位置。

步骤3 根据可行性规则计算各个体的适应度值并排序，找出当前最优鸟窝位置和其对应的最优适应度值。

步骤4 判断算法是否满足终止条件，若满足，则算法结束；否则，转步骤5。

步骤5 按式（2）和（3）更新鸟窝的位置，得到新的鸟窝位置。

步骤6 随机产生一个均匀分布的数r∈[0，1]，如果r>Pa，则随机改变发现概率较大的鸟窝位置，找出并保留最优鸟窝位置及对应值。

步骤7 利用Rosenbrock算法对当前最优解进行局部搜索，以一定概率对其进行柯西变异，令k=k+1，转向步骤3。

3 数值实验及分析

为验证混合布谷鸟搜索（Hybrid CS， HCS）算法的有效性，本文选择两个标准测试函数来测试其性能。两个测试函数的表达式[12]如下：

从表1中的结果可知，对于函数F1，与SR和HGA相比，无论是解的质量上（最优结果、平均结果和最差结果），还是算法稳定性方面（标准差），HCS算法都要优。与HEA相比，HCS算法获得了较好的平均值、最差值和标准差值；而HEA则得到了较好的最优结果。

对于函数F2，四种算法均找到了全局最优解。与HGA相比，HCS算法得到了相似的最优结果、平均结果和较好的最差结果、标准差值；与HEA相比，HCS算法得到的结果稍差；与SR算法相比，HCS算法得到了较好的平均结果、最差结果和标准差值。

对于函数F1和F2，HCS算法30次实验运行的CPU时间分别为373.96s和270.31s。

图2和图3分别给出了HCS算法对两个函数的寻优收敛曲线。

在图4中，化工反应网络优化设计问题有6个设计变量，分别为每个罐中的反应物CA1（记为x1）、CA2（记为x2）、CB1（记为x3）和CB2（记为x4），以及两个罐的容量V1（记为x5）和V2（记为x6）。

4.2 热交换器网络优化设计问题

热交换器网络优化设计问题[13]的结构如图5所示。它有6个决策变量，包括A1（x1）、A2（x2）、A3（x3）、T1（x4）、T2（x5）、T3（x6）、T4（x7）、T5（x8）和6个非线性不等式约束。

5 结语

布谷鸟搜索算法具有后期收敛速度慢、易陷入局部最优的缺陷。提出一种基于Rosenbrock搜索和柯西变异的混合布谷鸟搜索算法，在算法的进程中，首先引入佳点集方法产生初始种群以维持个体的多样性，然后使用Rosenbrock算法对当前最优解进行局部搜索以提高算法的收敛速度，接着对当前最优解进行柯西变异，以增强算法跳出局部最优的能力。对几个标准测试函数和两个约束化工优化设计问题的实验结果表明了HCGA具有较好的优化性能。

参考文献：

[1] LI C， YANG S， NGUYEN T. A self-learning particle swarm optimizer for global optimization problems[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B， 2012， 42（3）： 627-646.

[2] EPITROPAKIS M， TASOULIS D， PAVLIDIS N. Enhancing differential evolution utilizing proximity-based mutation operators[J]. IEEE Transactions on Evolutionary Computation， 2011， 15（1）： 99-119.

[3] LONG W， LIANG X M， HUANG Y F， et al. A hybrid differential evolution augmented Lagrangian method for constrained optimization numerical and engineering optimization[J]. Computer-Aided Design， 2013， 45（12）： 1562-1574.

[4] YANG X， DEB S. Cuckoo search via Lévy flights[C]// Proceedings of 2009 World Congress on Nature and Biologically Inspired Computing. Piscataway： IEEE， 2009： 210-214.

[5] GANDOMT A， YANG X， ALAVI A. Cuckoo search algorithm： a meta-heuristic approach to solve structural optimization problems[J]. Engineering with Computer， 2013， 29（1）： 17-35.

[6] WALTON S， HASSAN O， MORGAN K， et al. Modified cuckoo search： a new gradient free optimization algorithm[J]. Chaos， Solitons & Fractals， 2011， 44（9）： 710-718.

[7] YANG X， DEB S. Multi-objective cuckoo search for design optimization[J]. Computers & Operations Research， 2013， 40（6）： 1616-1624.

[8] HAUPT R L， HAUPT S E. Practical genetic algorithms[M]. New York： John Wiley & Sons， 2004.

[9] LONG W， LIANG X， XU S， et al. A hybrid evolutionary algorithm based on clustering good-point set crossover for constrained optimization[J]. Journal of Computer Research and Development， 2012， 49（8）： 1753-1761.（龙文， 梁昔明， 徐松金， 等. 聚类佳点集交叉的约束优化进化算法[J]. 计算机研究与发展， 2012， 49（8）： 1753-1761.）

[10] JIA S， DU B. Hybrid optimized algorithms based on the Rosenbrock search method and dynamic inertia weight PSO[J]. Control and Decision， 2011， 26（7）： 1060-1064.（贾树晋， 杜斌. Rosenbrock搜索与动态惯性权重粒子群混合优化算法[J]. 控制与决策， 2011， 26（7）： 1060-1064.）

[11] DEB K. An efficient constrained handling method for genetic algorithm[J]. Computer Methods in Applied Mechanical and Engineering， 2000， 186（2/3/4）： 311-338.

[12] RUNARSSON T P， YAO X. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation， 2000， 4（3）： 284-294.

[13] KHEAWHOM S. Efficient constraint handling scheme for differential evolutionary algorithm in solving chemical engineering optimization problem[J]. Journal of Industrial and Engineering Chemistry， 2010， 16（4）： 620-628.

[14] BABU B V， ANGIRA R. Modified Differential Evolution （MDE） for optimization of nonlinear chemical processes[J]. Computers and Chemical Engineering， 2006， 30（6/7）： 989-1002.

[15] AMIRJANOV A. The development of a changing range genetic algorithm[J]. Computer Methods in Applied Mechanics and Engineering， 2006， 195（19/20/21/22）： 2495-2508.

[16] CABRERA J C F， COELLO C A C. Handling constraints in particle swarm optimization using a small population size[C]// Proceedings of the 2007 International Conference on Artificial Intelligence. Berlin： Springer-Verlag， 2007： 41-51.

[17] GANDOMI A H， YANG X S， ALAVI A H. Bat algorithm for constrained optimization tasks[J]. Neural Computing and Applications， 2013， 22（6）： 1239-1255.