非线性最优化问题的一种混合解法

摘 要：把bfgs 方法 与混沌优化方法相结合，基于混沌变量提出一种求解具有变量边界约束非线性最优化 问题 的混合优化方法。混合算法兼顾了混沌优化全局搜索能力强和bfgs方法收敛速度快的优点，成为一种求解非凸优化问题全局最优的有效方法。算例表明，当混沌搜索的次数达到一定数量时，混合优化方法可以保证算法收敛到全局最优解，且 计算 效率比混沌优化方法有很大提高。

关键词：混合法；bfgs方法；混沌优化方法；全局最优

1 引言

在系统工程、控制工程、统计学、反问题优化求解等领域中，很多问题是具有非凸性的。对此普通的优化技术只能求出局部最优解，因为这些确定性算法总是解得最近的一个极值点[1]，只有能够给出很好的初始点才有可能得出所需要的全局最优解。为此，实际 应用 中通过在多个初始点上使用传统数值优化方法来求取全局解的方法仍然被人们所采用，但是这种处理方法求得全局解的概率不高，可靠性低，建立尽可能大概率的求解全局解算法仍然是一个重要问题。近年来基于梯度法的全局最优化方法已经有所 研究 [2]，基于随机搜索技术的遗传算法和模拟退火算法等在全局优化问题中的应用也得到越来越大的重视[3-4]。本文则基于混沌优化和bfgs方法，提出一种求解具有简单界约束最优化问题(1)的混合算法。 min (1) 混沌是存在于非线性系统中的一种较为普遍的现象。混沌运动宏观上无序无律，具有内随机性、非周期性和局部不稳定性，微观上有序有律，并不是完全的随机运动，具有无穷嵌套的自相似几何结构、存在普适性 规律 ，并不是杂乱无章的。利用混沌变量的随机性、遍历性和规律性特点可以进行优化搜索[5]，且混沌优化方法容易跳出局部最优点。但是某些状态需要很长时间才能达到，如果最优值在这些状态时，计算时间势必很长[5]。可以说混沌优化具有全局搜索能力，其局部搜索能力稍显不足，文[5]采用二次载波技术，文[6]考虑逐渐缩小寻优变量的搜索空间都是为了弥补这一弱点。而本文则采用混沌搜索与bfgs方法进行优化求解，一方面采用混沌搜索帮助bfgs方法跳出局部最优，另一方面利用bfgs增强解附近的超线性收敛速度和搜索能力，以提高搜索最优的效率。

2 混沌－bfgs混合优化方法

2.1 bfgs方法

作为求解无约束最优化问题的拟牛顿方法类最有代表性的算法之一，bfgs方法处理凸非线性规划问题，以其完善的数学 理论 基础、采用不精确线性搜索时的超线性收敛性和处理实际问题有效性，受到人们的重视[7-9]。拟牛顿方法使用了二阶导数信息，但是并不直接计算函数的hesse矩阵，而是采用一阶梯度信息 来构造一系列的正定矩阵 来逼近hesse矩阵 。bfgs方法求解无约束优化问题min ( )的主要步骤如下：

(1) 给变量赋初值x0，变量维数n和bfgs方法收敛精度ε，令b0=i（单位阵），k=0，计算 在点x0的梯度g0。

(2) 取sk=-bk-1gk，沿sk作一维搜索，确定最优步长αk， ，得新点xk+1=xk+αksk，计算xk+1点的梯度gk+1。

(3) 若||gk+1||≤ε，则令 ， ，bfgs搜索结束，转步骤3；否则执行(4)。

(4) 计算bk+1：

(2)

(3)

(5) k=k+1，转(2)。

2.2 混沌优化方法

利用混沌搜索求解问题(1)时，先建立待求变量 与混沌变量 的一一对应关系，本文采用 。然后,由logistic映射式(4)产生 个轨迹不同的混沌变量 （ ）进行优化搜索，式(4)中 =4。已经证明， =4是“单片”混沌， 在[0,1]之间历遍。

(4)

(1)给定最大混沌变量运动次数m；给 赋初值 ，计算 和 ；置 ， 。

(2) 。

(3) 。

(4) 若k

若 ，令 ， ；

若 ， 和 保持不变；

然后令k=k+1， ，转(2)。

若k&m，则 ， ，混沌搜索结束。

2.3 混合优化方法

混沌方法和bfgs方法混合求解连续对象的全局极小值优化问题(1)的步骤如下： step1 设置混沌搜索的最大次数m，迭代步数iter=0，变量赋初值x0， 。

step2 以 为始点bfgs搜索，得当前bfgs方法最优解 及 = 。

step3 若 ，取 = ；若 ，取 ；若 ，取 ， 是相对于 , 较小的数。

step 4 以 为始点进行混沌搜索m次，得混沌搜索后的最优解 及 = 。

step5 若

step6 改变混沌搜索轨迹，再次进行混沌搜索，即给 加微小扰动 ，执行step 4，得搜索结果 和 。若

混合算法中混沌搜索的作用是大范围宏观搜索，使得算法具有全局寻优性能。而bfgs搜索的作用是局部地、细致地进行优化搜索，处理的是小范围搜索问题和搜索加速问题。 3 算例

图 1 函数- 特性示意图 图 2 函数 特性示意图

采用如下两个非常复杂的、常用于测试遗传算法性能的函数测试本文算法：

函数 称为camel 函数，该函数有6个局部极小点(1.607105, 0.568651)、(-1.607105, -0.568651)、(1.703607, -0.796084)、(-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898,-0.7126)，其中(-0.0898,0.7126)和(0.0898,-0.7126)为两个全局最小点，最小值为-1.031628。函数 称为 schaffer's函数，该函数有无数个极大值，其中只有（0，0）为

全局最大点，最大值为1。此函数的最大峰值周围有一圈脊，它们的取值均为0.990283，因此很容易停留在此局部极大点。 文献 [10]采用该函数对该文提出的基于移动和人工选择的改进遗传算法（gamas）其性能进行了考察，运行50次，40％的情况下该函数的唯一全局最优点能够找到。而采用本文混合算法，由计算机内部随机函数自动随机生产100个不同的初始点，由这些初始点出发，一般混合算法迭代2－4次即能够收敛。m取不同数值时对函数 、 的计算结果分别如表1和表2所示，表中计算时间是指在奔腾133微机上计算时间。 由表2可见，当m=1500时，本文方法搜索到 最优解的概率即达到40％，而此时计算量比文献[10]小。同样由混合算法的100个起始点，采用文献[5]的算法对函数 优化计算100次，以 作为收敛标准，混沌搜索50000次，计算结果为67次搜索到最优解，概率为67%，平均计算时间为1.2369s。而即使保证混合算法100次全收敛到

时间也只为0.2142s（表1），可见混合算法优于文献[5]的方法。最优解所花费的平均计算