《非线性最优化问题的一种混合解法》由会员分享，可在线阅读，更多相关《非线性最优化问题的一种混合解法（16页珍藏版）》请在金锄头文库上搜索。
1、摘 要：把BFGS方法与混沌优化方法相结合，基于混沌变量提出一种求 解具有变量边界约束非线性最优化效果的混合优化方法。混合算法统筹 了混沌优化全局搜索才干强和BFGS方法收敛速度快的优点，成为一种 求解非凸优化效果全局最优的有效方法。算例说明，当混沌搜索的次数 到达一定数量时，混合优化方法可以保证算法收敛到全局最优解，且计 算效率比混沌优化方法有很大提高。关键词：混合法；BFGS方法；混沌优化方法；全局最优1 引言在系统工程、控制工程、统计学、反效果优化求解等范围中，很多 效果是具有非凸性的。对此普通的优化技术只能求出局部最优解，由于 这些确定性算法总是解得最近的一个极值点1，只要可以给出很好
2、的 初始点才有能够得出所需求的全局最优解。为此，实践运用中经过在多 个初始点上运用传统数值优化方法来求取全局解的方法依然被人们所 采用，但是这种处置方法求得全局解的概率不高，牢靠性低，树立尽能 够大约率的求解全局解算法依然是一个重要效果。近年来基于梯度法的 全局最优化方法曾经有所研讨2，基于随机搜索技术的遗传算法和模 拟退火算法等在全局优化效果中的运用也失掉越来越大的注重3-4。本文那么基于混沌优化和 BFGS 方法，提出一种求解具有复杂界约束最优化效果(1)的混合算法。min(1)混沌是存在于非线性系统中的一种较为普遍的现象。混沌运动微观 上无序无律，具有内随机性、非周期性和局部不动摇性，微
3、观上有序有 律，并不是完全的随机运动，具有无量嵌套的自相似几何结构、存在普 适性规律，并不是杂乱无章的。应用混沌变量的随机性、遍历性和规律 性特点可以停止优化搜索5，且混沌优化方法容易跳出局部最优点。 但是某些形状需求很长时间才干到达，假设最优值在这些形状时，计算 时间势必很长5。可以说混沌优化具有全局搜索才干，其局部搜索才 干稍显缺乏，文5采用二次载波技术，文6思索逐渐增加寻优变量的 搜索空间都是为了补偿这一弱点。而本文那么采用混沌搜索与BFGS方 法停止优化求解，一方面采用混沌搜索协助BFGS方法跳出局部最优， 另一方面应用BFGS增强解左近的超线性收敛速度和搜索才干，以提高 搜索最优的效
4、率。2混沌一BFGS混合优化方法2.1 BFGS 方法作为求解无约束最优化效果的拟牛顿方法类最有代表性的算法之一，BFGS方法处置凸非线性规划效果，以其完善的数学实际基础、采用不准确线性搜索时的超线性收敛性和处置实践效果有效性，遭到人们的注 重7-9。拟牛顿方法运用了二阶导数信息，但是并不直接计算函数的Hesse矩阵，而是采用一阶梯度信息来结构一系列的正定矩阵来迫 近Hesse矩阵。BFGS方法求解无约束优化效果min ()的主要步骤 如下：给变重赋初值丿，变壘维数毓EFGS方法收敛精度“令咛I (单位阵)，kF计算在miti-得新点一恥 )，:BFGS搜索结束，转点丿的梯度取吐-気吒卅沿占咻
5、一维搜索，确定最忧步长占 占1=占基气计算沉点的梯度g叶1 若则令否则执行(4)ojt+l=E + +疥垃？_冠送少* +吕罠Yk = Sk+1 - gk=k+l,转-2.2 混沌优化方法应用混沌搜索求解效果(1)时，先树立待求变量 与混沌变量 的逐一 对应关系，本文采用。然后，由Logistic映射式(4)发生 个轨迹不 同的混沌变量 停止优化搜索，式(4)中 =4。曾经证明， =4 是单片混沌， 在0，1之间历遍。(1)给定最大混沌变墾运动次数M；O .3o iLI1LA-赋初值* 碣)；苴计算k = 0;=1,2,严=4班1-*)若 kM,若若X恥则严+】工和A* =严尿持不变混沌搜索结
6、束.2.3 混合优化方法step2/为始点陀5搜索，得当前廿陀5方法最优解step3小的数若=碍+爲务 x*B bi 川,取爲是相对于务，切较step 4 m/(/c) n严为始点进行混沌搜索对兄得混沌搜索后的最优解tr*X 及stepE 若、iter=iter+l?x*=x*c转step2；否则执stepBnStep6改变混沌搜索轨迹，再欢进行混沌搜索，即给 卅=(1+荻；,执行巩曲4,得搜索结果 八和+卓广|A = XX加徽小扰动iter=iter+l? z* _，转航曲2；否则计算结束，输出stepl设置混沌搜索的最大次数仏迭代歩数讥肛电 变量赋初值丿,了=/区,也，,xj对全局极大值间
7、题 9 max小I可题min以仰细.辺,可次转化为求解全局极-/w = -了【再,心，庄混合算法中混沌搜索的作用是大范围微观搜索，使得算法具有全局寻优功用。而BFGS搜索的作用是局部地、细致地停止优化搜索，处置的是小范围搜索效果和搜索减速效果。3 算例E 2函数必特性示意图图1函数- 特性示意團采用如下两个十分复杂的、常用于测试遗传算法功用的函数测试本文算法：-10 10.初)=(4 2.1Z2 耳)宀如4 V.)宀若H-4 4函数称为Camel函数，该函数有6个局部极小点(1.607105,0.568651)、(-1.607105, -0.568651)、(1.703607, -0.7960
8、84)、 (-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898, -0.7126)，其 中(-0.0898,0.7126)和(0.0898, -0.7126)为两个全局最小点，最小值为 -1.031628。函数称为Schaffers函数，该函数有有数个极大值， 其中只要0, 0为全局最大点，最大值为1。此函数的最大峰值周围 有一圈脊，它们的取值均为0.990283，因此很容易停留在此局部极大 点。文献10采用该函数对该文提出的基于移动和人工选择的改良遗传 算法GAMAS其功用停止了调查，运转50次，40%的状况下该函数的独一全局最优点可以找到。而采用本文
9、混合算法，由计算机外部随机函 数自动随机消费100个不同的初始点，由这些初始点动身，普通混合算 法迭代24次即可以收敛。M取不同数值时对函数启、矗的计算结果 区分如表1和表2所示，表中计算时间是指在奔腾133微机上计算时间。由表2可见，当M=1500时，本文方法搜索到矗最优解的概率即到 达40%，而此时计算量比文献10小。异样由混合算法的100个起始 点，米用文献5的算法对函数丁优化计算100次，以| / -/* | /作为收敛规范，混沌搜索50000次，计算结果为67次搜索到最优解，概 率为67%，平均计算时间为1.2369s。而即使保证混合算法100次全收 敛到最优解所破费的平均计算时间也
10、只为0.2142s表1，可见混 合算法优于文献5的方法。表1M取不同数值时函数启的计算结果H按索到全局毘优点的次數擁索到最忧的擾率平均计算时间(-a. 0098;0, 7126)(0.0090;-0. 7126)100044鹑830. 1214s300053459 協1955 550005347LOOK0. 2142s披素到全局虽忧点的次数搜亲到璟忧的祸率平均计算吋瓦1500400. 140&S5000731QQ00360.500001001001.6856s4计算结果剖析由表1和表2可见，混合算法全局寻优才干随M的添加而增大，当M到达某一足够大的数值M后，搜索到全局最优的概率可以到达100%
11、。u从实际上说，M趋向无量大时，才干使混沌变量遍历一切形状，才u干真正以概率1搜索到最优点。但是，本文混沌运动M次的作用是协助BFGS方法跳出局部最优点，到达比以后局部最优函数值更小的另一局部最优左近的某一点处，并不是要混沌变量遍历一切形状。由混沌运动遍历特性可知，关于某一详细效果，M到达某一详细有限数值时，混沌u变量的遍历性可以失掉较好模拟，这一点是可以满足的，实践算例也证 明了这一点。由于函数性态、复杂性不同，关于不同函数，如这里的测试函数、，数值M的大小是有差异的。关于同一函数，搜索区间增大，在相反u混沌运动次数下，即使始点相反，总体而言会降低其搜索到全局最优的概率，要保证算法依然以概率
12、1收敛到全局最优，肯定惹起M增大。跟 U踪计算中间结果证明，当M足够大时，混合算法确实具有跳出局部最优 点，继续向全局最优停止搜索的才干；并且混合算法的计算时间主要破 费在为使混合算法具有全局搜索才干而停止混沌搜索上。5结语应用混沌变量的运动特点停止优化，具有十分强的跳出局部最优解 的才干，该方法与BFGS方法结合运用，在可以接受的计算量下可以计 算失掉效果的最优解。实践上，混沌优化可以和普通的下降类算法结合 运用，并非局限于本文采用的BFGS方法。采用的Logistic映射发生混 沌变量序列，只是发生混沌变量的有效方式之一。混沌运动与随机运动是不同的。混沌是确定性系统中由于内禀随机 性而发生
13、的一种复杂的、貌似无规的运动。混沌并不是无序和紊乱，更 像是没有周期的次第。与随机运动相比拟，混沌运动可以在各态历经的 假定下，运用统计的数字特征来描画。并且，混沌运动不重复地经过同 一形状，采用混沌变量停止优化比采用随机变量停止优化具有优势。混沌优化与下降类方法结合运用是有潜力的一种全局优化途径，是 求解具有变量界约束优化效果的牢靠方法。如何进一步提高搜索效率， 以及如何把混沌优化有效运用于复杂约束优化效果是值得进一步研讨 的课题。本文算法全局收敛性的严厉数学证明正在停止之中。参考文献1 胡山鹰，陈丙珍，何小荣，沈静珠非线性规划效果全局优化的模 拟退火法J 清华大学学报，37(6), 199
14、7, 5-9.2 C A Floudas, A Aggarwal, A R Ciric. Global optimum search fornonconvex NLP and MINLP problems. Comput Chem Engng. 1989, 13(10),11171132.3 康立山，谢云，尤矢勇等非数值并行算法第一册模拟退火算法M 北京：迷信出版社，19984 刘勇，康立山，陈琉屏非数值并行算法第二册遗传算法M 北京：迷信出版社，19985 李兵，蒋慰孙混沌优化方法及其运用J控制实际与运用，14(4)， 1997， 613-6156 张彤，王宏伟，王子才变尺度混沌优化方法及其运用J 控制与 决策，14(3)，1999，285-287.7 席少霖非线性最优化方法M 北京：初等教育出版社，1992.8 席少霖，赵凤志.最优化计算方法M上海：上海迷信技术出版社， 1983.9 Press W H, Tenkolsky S A, Vetterling W T, Flannery BP. Numerical Recipes in C, The Art of ScientificComputingM. Second edition, Cambridge University Press
