《非线性最优化问题的一种混合解法》由会员分享，可在线阅读，更多相关《非线性最优化问题的一种混合解法（3页珍藏版）》请在金锄头文库上搜索。
1、摘 要：把 bfgs 方法 与混沌优化方法相结合，基于混沌变量提出一种求解具有变量边界约 束非线性最优化 问题 的混合优化方法。混合算法兼顾了混沌优化全局搜索能力强和 bfgs 方法收敛速度快的优点，成为一种求解非凸优化问题全局最优的有效方法。算例表明，当混 沌搜索的次数达到一定数量时，混合优化方法可以保证算法收敛到全局最优解，且 计算 效 率比混沌优化方法有很大提高。关键词：混合法； bfgs 方法；混沌优化方法；全局最优1 引言 在系统工程、控制工程、统计学、反问题优化求解等领域中，很多问题是具有非凸性的。对此普通的优化技术只能求出局部最优解， 因为这些确定性算法总是解得最近的一个极值点
2、1 ， 只有能够给出很好的初始点才有可能得出所需要的全局最优解。为此，实际 应用 中通过在 多个初始点上使用传统数值优化方法来求取全局解的方法仍然被人们所采用，但是这种处理 方法求得全局解的概率不高，可靠性低，建立尽可能大概率的求解全局解算法仍然是一个重 要问题。 近年来基于梯度法的全局最优化方法已经有所研究 2 ，基于随机搜索技术的遗传算法和模拟退火算法等在全局优化问题中的应用也得到越来越大的重视 3-4 。本文则基于混 沌优化和 bfgs 方法，提出一种求解具有简单界约束最优化问题 (1) 的混合算法。 min (1) 混沌是存在于非线性系统中的一种较为普遍的现象。 混沌运动宏观上无序无律
3、， 具有内随机 性、非周期性和局部不稳定性，微观上有序有律，并不是完全的随机运动，具有无穷嵌套的 自相似几何结构、存在普适性 规律 ，并不是杂乱无章的。利用混沌变量的随机性、遍历性 和规律性特点可以进行优化搜索 5 ，且混沌优化方法容易跳出局部最优点。 但是某些状态需 要很长时间才能达到， 如果最优值在这些状态时， 计算时间势必很长 5 。可以说混沌优化具 有全局搜索能力，其局部搜索能力稍显不足，文 5 采用二次载波技术，文 6 考虑逐渐缩小 寻优变量的搜索空间都是为了弥补这一弱点。 而本文则采用混沌搜索与 bfgs 方法进行优化求 解，一方面采用混沌搜索帮助 bfgs 方法跳出局部最优，另一
4、方面利用 bfgs 增强解附近的超 线性收敛速度和搜索能力，以提高搜索最优的效率。2 混沌 bfgs 混合优化方法2.1 bfgs 方法 作为求解无约束最优化问题的拟牛顿方法类最有代表性的算法之一， bfgs 方法处理凸非线性 规划问题，以其完善的数学 理论 基础、采用不精确线性搜索时的超线性收敛性和处理实际 问题有效性， 受到人们的重视 7-9 。拟牛顿方法使用了二阶导数信息， 但是并不直接计算函来逼近 hesse 矩阵数的 hesse 矩阵，而是采用一阶梯度信息来构造一系列的正定矩阵bfgs 方法求解无约束优化问题 min ( ) 的主要步骤如下：(1) 给变量赋初值X0，变量维数n和bf
5、gs方法收敛精度，令bO=i (单位阵)，k=0,计算 在点 x0 的梯度 g0。，得新点 xk+1=xk+ a ksk ，计3；否则执行 (4) 。的一一对应关系， 本文采用 。)进行优化搜索，式 (4) 中(2) 取sk=-bk-1gk，沿sk作一维搜索，确定最优步长a k,算 xk+1 点的梯度 gk+1 。(3) 若|gk+1| w & ,则令 ，bfgs搜索结束，转步骤(4) 计算 bk+1 ：(2)(3)(5) k=k+1 ，转(2) 。2.2 混沌优化方法利用混沌搜索求解问题 (1)时，先建立待求变量 与混沌变量 然后，由logistic 映射式产生个轨迹不同的混沌变量=4。已经
6、证明，=4 是“单片”混沌， 在0,1 之间历遍。(4)(1) 给定最大混沌变量运动次数m;给 赋初值 ，计算和；置，。(2) 。(3) 。(4) 若 k<m ，若 ，令 ， ；若 ， 和 保持不变；然后令 k=k+1 ， ，转 (2) 。若k&m则，混沌搜索结束。2.3 混合优化方法混沌方法和 bfgs 方法混合求解连续对象的全局极小值优化问题 (1) 的步骤如下：stepl设置混沌搜索的最大次数m,迭代步数iter=O，变量赋初值x0，。step2 以 为始点 bfgs 搜索，得当前 bfgs 方法最优解 及 =。step3 若 ,取 = ;若 ,取 ;若 ,取 , 是相对于 , 较
7、小的数。step 4 以为始点进行混沌搜索m次，得混沌搜索后的最优解及=。step5 若 < , iter=iter+1 , ,转 step2 ;否则执行 step6 。step6 改变混沌搜索轨迹,再次进行混沌搜索,即给加微小扰动 ,执行 step 4,得搜索结果 和 。若 < , iter=iter+1 , ,转 step2 ;否则计算结束,输出 、。对全局极大值问题, max ,可以转化为求解全局极小问题 min 。 混合算法中混沌搜索的作用是大范围宏观搜索, 使得算法具有全局寻优性能。 而 bfgs 搜索的 作用是局部地、细致地进行优化搜索,处理的是小范围搜索问题和搜索加速
8、问题。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 。函数 称为 schaff
9、ers 函数,该函数有无数个极大值,其中只有( 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 的方法。
