求解非线性极大极小问题的一种新的混合算法

刘国志

（辽宁石油化工大学 理学院，抚顺 113001）

考虑如下的极大极小问题：

其中fi(x)(i =1,2,…,m ) 为变量 x ∈Ω⊂Rn的非线性光滑实值函数。由于目标函数是一个不可微函数，所以该问题是一个较为复杂的不可微优化问题。非线性极大极小问题由于其在工程设计、电子线路规划、方程组求解、数据拟合以及多目标优化中有着广泛应用，受到了人们广泛关注。关于它的求解方法较多，较为流行的有两类：一是把问题（1）转化为非线性规划问题

1 非线性极大极小问题的新的混合算法

1.1 粒子群算法

令n表示搜索空间的维数，xi=(xi1,xi2,…,xin)表示微粒i当前的位置，pi=(pi1,pi2,…,pin)表示微粒i曾经达到的最好位置。种群中最优微粒的序号用g表示，微粒i的速度用Vi=(vi1,vi2,…,viD)表示。每个微粒根据（2）式来更新自己的速度和位置：

式中：k表示迭代次数，c1,c2为学习因子，rand(·)，Rand(·)是[0,1]区间的随机数，为惯性权重。

1.2 可行基规则

众所周知，惩罚函数法由于其简单且易实施一直是最流行的约束处理技术.问题（2）的精确罚函数可构造为：

称viol(x)为约束偏差函数，其中M是一个适当大的正数.

由于在惩罚函数中同时考虑了目标函数和约束偏差函数，因此这种方法表现好坏与惩罚因子的选取有着直接的关系.然而选择适当的罚因子一般不是一件容易的事情，它与所讨论的问题有关.为了避免罚因子的选取，本文采用文［3-4］所提出的可行基规则处理约束条件，具体叙述如下.

当一个是可行解，另外一个是不可行解时，可行解优先；

当两个解都是可行解时，目标函数值小的优先；

当两个解都是不可行解时，约束偏差函数值小的优先。

关于第i个例子曾经达到的最好位置 pi和所有粒子的历史最好位置gbest，在每一代按着上述规则进行更新。

1.3 新的混合算法

混合算法把微粒群算法全局寻优性和Hooke-Jeeves方法的快速收敛性结合起来，利用可行基规则，避免了惩罚函数法的缺点，且计算结果表明了Hooke-Jeeves方法的快速收敛性和微粒群算法的可靠性都得到了进一步的改善。

混合算法：

第1步：随机初始化一群微粒的位置和速度；

第2步：以z为评价函数，分别对每个微粒求问题（2）目标函数值；

第3步：以当前最好微粒位置 pg为初始点，使用Hooke-Jeeves搜索法进行优化计算求出（4）式的最优解x*，并令 pg=x*；

第4步：根据式（3）更新每个微粒的速度和位置；

第5步：对每个微粒，将其经历过的最好位置pbest按可行基规则更新；

第6步：对每个微粒，将其全局所经历的最好位置 pg按可行基规则更新；

第7步：如果没有达到结束条件（通常为足够好的函数值或达到一个预先给定的最大迭代次数或最优解停滞不再变化），则返回第2步。

2 实例分析

为了测试本文算法的求解性能，下面选择两个例子进行数值计算，其参数设置为：

表1 例1的计算结果Tab.1 Computable result for example 1

表2 例2的计算结果Tab.2 Computable result for example 2

本例的极大极小最优解为 x*=[1,1]T，f(x*)=f1(x*)=f2(x*)=f3(x*)=2。

从表1和表2可以看出，本文提出的算法的计算结果较文［1］和文［2］好的多，而且基本上达到了理论值。

3 结论

非线性极大极小问题是一类经常出现在工程、电子线路规划方程组求解数据拟合以及多目标优化中的一类非光滑优化问题。因此求解非线性极大极小问题精度较高的解具有非常重要的现实意义。本文提出了一个求解这类问题的一个新的算法—Hooke-Jeeves搜索法和与可行基规则相结合的微粒群算法的混合算法。通过实例计算结果表明，这种新的算法在收敛速度和求解精度上都有了很大的提高。因此可以应用到工程实际中。

［1］李兴斯.解非线性极大极小问题的凝聚函数法［J］.计算结构力学及其应用，1991（1）：85-91.

［2］雍龙泉，孙培民，张建科.一类非线性极大极小问题的极大熵社会认知算法［J］.计算机工程与应用，2010，46（26）：36-42.

［3］K Deb.An efficient constraint handling method for genetic algorithms，Comput.Meth Appl Mech Eng，2000（186）：311-338.

［4］Qie He，Ling Wang.A hybrid particle swarm optimizatuion with a feasibility-based rule for constrained optimization［J］.Applied Mathematics and Computation，2007，186（2）：1407-1422.