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

《非线性最优化问题的一种混合解法3061.docx》由会员分享，可在线阅读，更多相关《非线性最优化问题的一种混合解法3061.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Evaluation Warning: The document was created with Spire.Doc for .NET.非线性最优化问题的一种混合解法摘 要：把BFGS方法与混沌优化方法相结合，基于混沌变量提出一种求解具有变量边界约束非线性最优化问题的混合优化方法。混合算法兼顾了混沌优化全局搜索能力强和BFGS方法收敛速度快的优点，成为一种求解非凸优化问题全局最优的有效方法。算例表明，当混沌搜索的次数达到一定数量时，混合优化方法可以保证算法收敛到全局最优解，且计算效率比混沌优化方法有很大提高。关键词：混混合法；BFGGS方法法；混沌沌优化方方法；全全局最优优1 引言言 在在系

2、统工工程、控控制工程程、统计计学、反反问题优优化求解解等领域域中，很很多问题题是具有有非凸性性的。对对此普通通的优化化技术只只能求出出局部最最优解，因因为这些些确定性性算法总总是解得得最近的的一个极极值点1，只只有能够够给出很很好的初初始点才才有可能能得出所所需要的的全局最最优解。为为此，实实际应用用中通过过在多个个初始点点上使用用传统数数值优化化方法来来求取全全局解的的方法仍仍然被人人们所采采用，但但是这种种处理方方法求得得全局解解的概率率不高，可可靠性低低，建立立尽可能能大概率率的求解解全局解解算法仍仍然是一一个重要要问题。近近年来基基于梯度度法的全全局最优优化方法法已经有有所研究究2，基

3、于于随机搜搜索技术术的遗传传算法和和模拟退退火算法法等在全全局优化化问题中中的应用用也得到到越来越越大的重重视33-4。本文文则基于于混沌优优化和BBFGSS方法，提提出一种种求解具具有简单单界约束束最优化化问题(1)的的混合算算法。 minn (1) 混混沌是存存在于非非线性系系统中的的一种较较为普遍遍的现象象。混沌沌运动宏宏观上无无序无律律，具有有内随机机性、非非周期性性和局部部不稳定定性，微微观上有有序有律律，并不不是完全全的随机机运动，具具有无穷穷嵌套的的自相似似几何结结构、存存在普适适性规律律，并不不是杂乱乱无章的的。利用用混沌变变量的随随机性、遍遍历性和和规律性性特点可可以进行行优

4、化搜搜索55，且且混沌优优化方法法容易跳跳出局部部最优点点。但是是某些状状态需要要很长时时间才能能达到，如如果最优优值在这这些状态态时，计计算时间间势必很很长55。可可以说混混沌优化化具有全全局搜索索能力，其其局部搜搜索能力力稍显不不足，文文5采用二二次载波波技术，文文6考虑逐逐渐缩小小寻优变变量的搜搜索空间间都是为为了弥补补这一弱弱点。而而本文则则采用混混沌搜索索与BFFGS方方法进行行优化求求解，一一方面采采用混沌沌搜索帮帮助BFFGS方方法跳出出局部最最优，另另一方面面利用BBFGSS增强解解附近的的超线性性收敛速速度和搜搜索能力力，以提提高搜索索最优的的效率。 2 混沌沌BFFGS混混

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

6、解问题(1)时时，先建建立待求求变量 与混混沌变量量 的一一一对应应关系，本本文采用用 。然然后,由Loggisttic映射射式(44)产生生 个轨轨迹不同同的混沌沌变量 （ ）进进行优化化搜索，式式(4)中 =4。已已经证明明， =4是是“单片”混沌， 在0,1之之间历遍遍。 2.3 混混合优化化方法 混合算法中中混沌搜搜索的作作用是大大范围宏宏观搜索索，使得得算法具具有全局局寻优性性能。而而BFGGS搜索索的作用用是局部部地、细细致地进进行优化化搜索，处处理的是是小范围围搜索问问题和搜搜索加速速问题。3 算例例 采用如下两两个非常常复杂的的、常用用于测试试遗传算算法性能能的函数数测试本本文

7、算法法： 函数 称为为Cammel 函数，该该函数有有6个局部部极小点点(1.60771055, 00.56686551)、(-11.60071005, -0.56886511)、(1.70336077, -0.77960084)、(-11.70036007, 0.77960084)、(-00.08898,0.771266)和(0.08998,-0.771266)，其其中(-0.008988,0.71226)和(0.08998,-0.771266)为两两个全局局最小点点，最小小值为-1.00316628。函函数 称为 SSchaaffeerss函数，该该函数有有无数个个极大值值，其中中只有（0

8、0，0）为为全局最最大点，最最大值为为1。此此函数的的最大峰峰值周围围有一圈圈脊，它它们的取取值均为为0.99902283，因因此很容容易停留留在此局局部极大大点。文文献110采采用该函函数对该该文提出出的基于于移动和和人工选选择的改改进遗传传算法（GGAMAAS）其其性能进进行了考考察，运运行500次，440的的情况下下该函数数的唯一一全局最最优点能能够找到到。而采采用本文文混合算算法，由由计算机机内部随随机函数数自动随随机生产产1000个不同同的初始始点，由由这些初初始点出出发，一一般混合合算法迭迭代24次即即能够收收敛。MM取不同同数值时时对函数数 、 的计算算结果分分别如表表1和表表2

9、所示示，表中中计算时时间是指指在奔腾腾1333微机上上计算时时间。 由表2可见见，当MM=15500时时，本文文方法搜搜索到 最优解解的概率率即达到到40，而而此时计计算量比比文献10小。同同样由混混合算法法的1000个起起始点，采采用文献献5的算法法对函数数 优化计计算1000次，以以 作为收收敛标准准，混沌沌搜索5500000次，计计算结果果为677次搜索索到最优优解，概概率为667%，平平均计算算时间为为1.223699s。而而即使保保证混合合算法1100次次全收敛敛到 最优解解所花费费的平均均计算时时间也只只为0.21442s（表表1），可可见混合合算法优优于文献献5的方法法。表1MM

10、取不同同数值时时函数 的计算算结果4 计算算结果分析析 由表1和表表2可见，混混合算法法全局寻寻优能力力随M的增加加而增大大，当MM达到某某一足够够大的数数值Mu后，搜搜索到全全局最优优的概率率可以达达到1000。从理论上上说，MMu趋向无无穷大时时，才能能使混沌沌变量遍遍历所有有状态，才才能真正正以概率率1搜索到到最优点点。但是是，本文文混沌运运动M次的作作用是帮帮助BFFGS方方法跳出出局部最最优点，达达到比当当前局部部最优函函数值更更小的另另一局部部最优附附近的某某一点处处，并不不是要混混沌变量量遍历所所有状态态。由混混沌运动动遍历特特性可知知，对于于某一具具体问题题，Mu达到某某一具体

11、体有限数数值时，混混沌变量量的遍历历性可以以得到较较好模拟拟，这一一点是可可以满足足的，实实际算例例也证实实了这一一点。 由由于函数数性态、复复杂性不不同，对对于不同同函数，如如这里的的测试函函数 、 ，数值值Mu的大小小是有差差别的。对对于同一一函数，搜搜索区间间增大，在在相同混混沌运动动次数下下，即使使始点相相同，总总体而言言会降低低其搜索索到全局局最优的的概率,要保证证算法仍仍然以概概率1收收敛到全全局最优优，必然然引起MMu 增大大。跟踪踪计算中中间结果果证实，当当M足够大大时，混混合算法法的确具具有跳出出局部最最优点，继继续向全全局最优优进行搜搜索的能能力；并并且混合合算法的的计算时

12、时间主要要花费在在为使混混合算法法具有全全局搜索索能力而而进行混混沌搜索索上。5 结语语 利用混沌变变量的运运动特点点进行优优化，具具有非常常强的跳跳出局部部最优解解的能力力，该方方法与BBFGSS方法结结合使用用，在可可以接受受的计算算量下能能够计算算得到问问题的最最优解。实实际上，混混沌优化化可以和和一般的的下降类类算法结结合使用用，并非非局限于于本文采采用的BBFGSS方法。采采用的LLogiistiic映射射产生混混沌变量量序列，只只是产生生混沌变变量的有有效方式式之一。混沌运动与与随机运运动是不不同的。混混沌是确确定性系系统中由由于内禀禀随机性性而产生生的一种种复杂的的、貌似似无规的

13、的运动。混混沌并不不是无序序和紊乱乱，更像像是没有有周期的的秩序。与与随机运运动相比比较，混混沌运动动可以在在各态历历经的假假设下，应用统计的数字特征来描述。并且，混沌运动不重复地经过同一状态，采用混沌变量进行优化比采用随机变量进行优化具有优势。混沌优化与与下降类类方法结结合使用用是有潜潜力的一一种全局局优化途途径，是是求解具具有变量量界约束束优化问问题的可可靠方法法。如何何进一步步提高搜搜索效率率，以及及如何把把混沌优优化有效效应用于于复杂约约束优化化问题是是值得进进一步研研究的课课题。本文算法全全局收敛敛性的严严格数学学证明正正在进行行之中。参考文献 1胡山山鹰，陈陈丙珍，何何小荣，沈沈静

14、珠非线性性规划问问题全局局优化的的模拟退退火法J清华华大学学学报，337(66)，19997，5-99 2C A FFlouudass, AA Agggarrwall, AA R Cirric Glooball opptimmum seaarchh foor nnoncconvvex NLPP annd MMINLLP pprobblemmsJJ. Commputt Chhem Enggng 19989， 133(100)， 1111711332 3康立立山，谢谢云，尤尤矢勇等等非数数值并行行算法（第第一册）模拟退火算法M北京：科学出版社，1998 4刘勇勇，康立立山，陈陈琉屏非数值值并行算算

15、法（第第二册）遗传算法M北京：科学出版社，1998 5李兵兵，蒋慰慰孙混混沌优化化方法及及其应用用J控制制理论与与应用，14(4)，1997，613-615 6张彤彤，王宏宏伟，王王子才变尺度度混沌优优化方法法及其应应用J控制制与决策策，144(3)，19999，2855-2887 7席少少霖非非线性最最优化方方法M北京京：高等等教育出版版社，119922 8席少少霖，赵赵凤志最优化化计算方方法M上海海：上海海科学技技术出版版社，119833 9Prresss W H, Tennkollskyy S A, Vettterrlinng WW T, Fllannneryy B PNummeriic

16、all Reecippes in C, Thee Arrt oof SScieentiificc CoompuutinngMM Seeconnd eedittionn， Caambrridgge UUnivverssityy Prresss， 19992 10JJ C PorrtsThee deevellopmmentt annd eevalluattionn off ann immproovedd geenettic alggoriithmm baasedd onn miigraatioon aand arttifiiciaal sseleectiionJIEEEE TTranns. Sys

17、st. Mann annd CCybeern.19994, 24(1)，73-85 A Hybbridd Appprooachh foor NNonllineear OpttimiizattionnAbstrractt：Coombiinedd BFFGS metthodd wiith chaaos opttimiizattionn meethood, a hhybrrid appproaach wass prropoosedd too soolvee noonliineaar ooptiimizzatiion proobleems witth bbounndarry rresttraiints

18、s off vaariaablees. Thee hyybriid mmethhod is an efffecttivee appprooachh too soolvee nooncoonveex ooptiimizzatiion proobleems, ass itt giivenn booth atttenttionns tto tthe inhhereent virrtuee too loocatte gglobbal opttimuum oof cchaoos ooptiimizzatiion metthodd annd tthe advvanttagee off hiigh conn

19、verrgennce speeed of BFGGS mmethhod. Nuumerricaal eexammplees iilluustrratee thhat thee prreseent metthodd poosseessees bbothh goood cappabiilitty tto ssearrch glooball opptimma aand farr hiigheer cconvverggencce sspeeed tthann thhat of chaaos opttimiizattionn meethood.key wwordds：hybbridd appprooachh；BFGGS mmethhod；chaaos opttimiizattionn meethood；glooball opptimmum