（应用数学专业论文）全局优化问题的填充函数法和区间算法.pdf

摘要 本文对两类全局优化算法( 填充函数法和区间算法) 作了比较深入的研究， 在此基础上对这些算法作了进一步的推广和应用，取得了较为满意的结果，主要 内容如下： 在已有的填充函数法的基础上，针对一类非光滑问题提出了一类改进的双参 数填充函数法，此填充函数形式简洁，运算量低，大量的数值实验表明与已有相 关文献比较该方法的精度和运算效率都有所提高 对于l i p s e h i t z 规划，针对双参数填充函数法在参数选取时的局限性，本文构 造了一类应用更广的单参数填充函数，提高了算法的执行效率，理论分析和数值 试验均表明该算法比已有的相关算法优越 利用线性加权法将多目标规划转化为单目标规划，根据其特点，构造了一种 新的填充函数法，并利用此算法求得该单目标规划的全局最优解，即原规划的最 小弱有效解，数值试验表明该算法是可行有效的，且能保证得到全局最优解 此外对离散的m i n i m a x 问题，通过引入拟偏导数的概念，建立了目标函数 的区间扩张和无解区域删除检验原则，基于m o o r e 的区间二分原则提出了求解离 散的i n h l i m a x 问题的区间算法理论分析和数值结果均表明该算法是有效的，在 给定精度内能求出全部最优解 关键词：l l p s c h i t z 规划多目标规划m i n i m a x 问题填充函数法区间算法 a b s t r a c t t h i st h e s i si sd e v o t e dt ot w og l o b a lo p t i m i z a t i o na l g o r i t h m s ，s u c ha saf i l l e d f u n c t i o nm e t h o da n da l li n t e r v a la l g o r i t h m t h e i rp r o p e r t i e sa n de x t e n d e da p p l i c a t i o n s a r ed i s c u s s e do ne m p h a s i sa n dt h es a t i s f a c t o r yr e s u l t sa r ea c h i e v e d t l l em a i nw o r ko f t h ed i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： b a s e do ns o m e e x i s t i n gf i l l e df u n c t i o nm e t h o d s i nt h er e f e r e n c e s ，am o d i f i e df i l l e d f i m c t i o nm e t h o dw i t ht w o a d j u s t a b l ep a r a m e t e r s i sc o n s t r u c t e df o rn o n s m o o t h o p t i m i z a t i o n t h i s m e t h o di s s i m p l ea n df e a s i b l e t h e o r e t i c a la n a l y s e sa n dal a r g e a m o u n to fn b i n e r i c a lr e s u l t ss h o wt h a tt h i sm e t h o di sb e t t e rt h a no t h e rm e t h o d si nt h e a s p e c t ss u c h a sa c c u r a c y , r u n t i m ea n di t e r a t i v en u m b e r t h ef i l l e df u n c t i o nw i t ht w op a r a m e t e r sh a ss o m ed i s a d v a n t a g e s ，e s p e c i a l l y ，t h e e x c e s s i v er e s t r i c t i o no nt h ec h o i c e so ft h ep a r a m e t e rv a l u e s s oam o d i f i e df i l l e d f u n c t i o nw i t ho n l yo r ep a r a m e t e ri sp r o p o s e dw i t hm u c hi m p r o v e dp e r f o r m a n c ef o ra l i p s c h i t zp r o g r a m m i n g n u m e r i c a le x p e r i m e n t s s h o wt h a tt h em e t h o di se f f i c i e n t 伍s p a p e r d e a l sw i t ht h et r a n s f o r m a t i o no f a m u l t 币l eo b j e c t i v ep r o g r a m m i n g i n t o as i n g l eo b j e c t i v ep r o g r a m m i n g b yt h ec h a r a c t e ro f t h es i n g l eo b j e c t i v ep r o g r a m m i n g ， an o v e lf i l l e df u n c t i o nm e t h o di sd e s c r i b e d g l o b a lo p t i m a ls o l u t i o n so ft h es i n g l e o b j e c t i v ep r o g r a m m i n g a 弛o b t a i n e db yt h em e t h o d ，i e ，t h em i n i m a lw e a k l ye f f i c i e n t s o l u t i o n st ot h eo r i g i n a lp r o g r a m m i n g t h en u m e r i c a lt e s t ss h o w t h a ti ti sp r a c t i c a la n d e f f e c t i v e m o r e o v e r , o u rf i l l e df u n c t i o ng u a r a n t e e si t sm i n i m u m t ob ea l w a y sa c h i e v e d a tap o i mw h e r ei t sf u n c t i o nv a l u ei sn o th i 曲e rt h a nt h ef u n c t i o nv a l u eo f t h ec u r r e n t m i n i l u u r f l b e s i d e sa l lo ft h ea b o v e ，a st oad i s c r e t em i n i m a xp r o b l e m ，t h ei n t e r v a le x t e n s i o n o fo b j e c t i v ef u n c t i o na n dr e g i o nd e l e t i o nt e s t r u l e sa l ed i s c u s s e dv i aq u a s i - w a a l d e r i v a t i v e a ni n t e r v a la l g o r i t h mi sd e s c r i b e db a s e do nt h eb i s e c t i o nr u l eo fm o o r e t h e o r e t i c a la n a l y s e sa n dn u m e r i c a lr e s u l t ss h o w t h a tt h ea l g o r i t h mi se f f i c i e n ta n dt h a t a l lg l o b a lo p t i m a lp o i n t sc a n b ef o u n d i nt h eg i v e n 删y k e y w o r d s ：l i p s e h i t zp r o g r a m m i n gm u l t i p l eo m e e t i v ep r o g r a m m i n g m i n i m a xp r o b l e m f i l l e df u n c t i o nm e t h o d i n t e r v a la l g o r i t h m 创新性声明 y 6 9 5 6 5 9 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：j 匝 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可阻允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名关葛 导师签名：趁i 至：臣旦日期丛! ：! 垒 第一章绪论 本章给出了论文的写作背景及其意义，介绍了近几年备受关注的几类非凸优 化问题全局最优解的算法以及它们的研究现状，最后扼要介绍了本文的主要工作 1 1 引言 自二十世纪七十年代以来，非线性规划一直是各学科普遍关注的熟点研究领 域，作为非线性科学研究中的一个非常活跃的数学分支全局优化的理论和算 法从其诞生之日起便受到广泛的关注全局最优化问题多种多样，它广泛应用于 工农业、国防、金融、化工、能源、通讯等领域，丽且与分析、几何、代数、概 率以及计算机科学、系统科学、自动化等有密切联系，互相促进 由于自然科学、经济和工程技术等领域的发展都依赖于计算相应优化问题的 全局最优解的数值技术，从而使得全局最优化在自然科学工程技术和经济管理等 领域也产生了深远的影响在寻找有效的优化技术方面人们付出了巨大的努力， 使得优化方法取得了巨大的发展 1 2 全局优化问题的研究现状 在过去几十年里，关于局部优化方法及其在工程和科学中的应用等方面的研究 已获得丰富的理论和优秀的数值方法但大量的最优化问题，特别是从工程优化 中设计出来的优化模型都要求全局解而不是局部解，它们来源于分子生物学川、经 济金融”、网络运输 3 1 、数据挖掘与知识发现、图像处理与模式识别【”、环境 工程、化学工程设计与工业制造等另外，科学与工程的许多最新成果都依赖于 计算优化问题全局解的数值技术全局优化主要研究非线性函数在某个区域上的 全局最优点的特征及其计算方法，用传统的非线性规划求解方法已无法有效地求 解全局优化问题的研究始于六十年代中期，但这项研究进展缓慢，与求解局部 极值问题相比，其主要困难在于问题中局部极值点的个数及极值点的大体位置均 为未知；判断一个局部极值点是否为总体极值点的判别准则不易确定近年来， 全局优化已成为优化领域最受关注的方向之一，已引起许多优化工作者的广泛关 注 随着全局优化问题的广泛应用，许多全局优化算法得到不断地发展现有的全 ； ： ：盒垦垡些塑壁墼堡蜜鬻螫鋈銎壁画基鎏 ； 局优化算法依据它们的收敛性质分为随机型方法和确定型方法两大类前者包含 遗传算法、模拟退火算法、演化策略、进化程序等，这类算法从当前近似值x 。出 发，以随机扰动方式生成新的初始点i n “( x n + - = x n + 吒，其中吒为一随机变量) ， 并以一定概率接受x n + t 或以x n + 为初始值而由某个局部优化过程产生的局部极小 为新的近似x 。，这一过程直至满足某一人为给定的终止准则当算法的执行时间 趋于无穷时，它们按照概率逼近收敛到最优解这类方法具有算法易于设计，对 目标函数要求不高从而应用广泛，容易实现，稳定性好等优点但效率低，可靠 性差，不能保证产生优化问题的最优解，并且它的理论基础也不完善【6 】，结论常 常带有随机性相比之下，确定性方法可以充分利用优化问蹶的特殊结构，通常 能在预先给定的精度内有限步收敛于问题的最优解这类方法包括：牛顿法、共 轭梯度法、变尺度法、分支定界法、网格算法、罚函数法、积分水平集法、区间 算法、填充函数法、神经网络方法等这类方法依据某一确定性策略搜索局部极 小，并试图跳越己获得的局部极小而达到某个全局最优点这类方法虽然有较高 的计算效率，但算法复杂一般的确定性方法大体可分为两类：解析方法，直接 方法前者主要利用函数的分析性质去构造迭代公式，使之收敛到极值和极值点， 主要有：最速下降法、牛顿法、共轭梯度法、变尺度法等对于多变量的一般非 线性函数的极小化问题，虽然利用导数能够为寻找极值点提供有效信息，但是为 求其导数却可能不得不耗费大量时间来做计算导数的工作，而且目标函数的导数 有时是不存在的。甚至目标函数本身是不明确的解析表达式，这就迫使人们寻找 不需要计算函数导数或梯度的方法直接方法对函数的分析性质没有要求，而且 根据一定的数学原理，用尽量少的计算量，通过直接比较函数值的大小来确定极 值点的位置直接方法有：区间方法、填充函数法、分支定界法、网格算法等 1 3 填充函数法和区间算法 非凸全局优化问题是n p 难问题，由于它的多极值性，即使给定问题的连续 性和光滑性，用经典的非线性规划技术也不能成功地求解全局优化问题特别是 至今还没有很好的全局性判定准则，使得求解变得十分困难因此，对非凸全局 优化方法的研究一方面具有重要的理论意义和应用价值，另一方面又是一个极 具挑战性的研究课题本文研究了两类非凸优化问题的全局最优解的计算方法， 即填充函数法、区间算法，对算法的性质、收敛性及推广应用进行了深入的研究 下面给出填充函数法、区间算法的基本思想及研究现状 ( 1 ) 填充函数法 填充函数法( f i l l e d f i m c t i o nm e t h o d ) 考虑问题 四) 卿，( 硝 其中q c r “为紧集，假设忪l i - 佃时，( x ) 斗抽它的基本思想是根据目标函 数厂( x ) 的一个已知极小值点x 。，构造个填充函数p ( z ) ，x ，为其极大值点，在任 何比f ( x 。) 函数值大的谷域中没有p ( x ) 的极小点或鞍点，而在某个比，( x ，) 函数值 ，j 、的谷域率有工) 酌极，j 、值点或鞍点z ，然后以工为扔始点去极小化厂 ，并找 到厂( 曲的一个新的极小值点x 2 ，使得f ( x ：) f ( x ，) ，用x ：代替x 。，重复上述过程， 直到找到，( z ) 的全局极小值点 填充函数法是葛人溥( 1 9 8 3 ) 1 首次提出的求解多变量函数全局极值点的一类 有效的算法，葛针对凸可微优化阂题提出的填充函数如下： p ( x ，p ) = o ( r + ( 上) ) 1 e x p 卜n 工- 膏i0 7 户2 】。 其中r ，p 为参数理论分析和数值试验表明填充函数法是解决多元函数全局极小化 闷题的一静成功的方法。孔敏、庄建鸯州提出了一类求解非光滑优化问题总体投 值点的填充函数法，扩大了参数的适用范围所提出的填充函数为： p c x ，p ) = i n 1 + i ( r + f ( x ) ) l e x p ( - i i 石一i 酽, 0 2 ) 孔敏和庄建南利用非光滑分析理论，使得填充函数迸一步拓展应用于非光滑规划 全局寻优闯题的求解中由于双参的填充函数在参数的选取上受到过多的约柬， 葛人溥( 1 9 r 7 ) t ”1 提出新的单参数填充函数： p ( x ，一) = - ( ( x ) - f ( x ? ) ) e x p ( - a0 工一x ：1 1 2 ) 李宝秀、沈渝1 5 1 构造了求解l i p s e h i t z 规划的一类更广的单参数埂充函数法，且收 敛条件比前文弱了许多所提出的壤充函数为： p ( x ，= - ( f ( x ) - f ( x ：) ) e x p ( a6x - - 耳2 ) 圆区同算法 区间算法( i n t e r v a la l g o r i t h m ) 考虑问瑟 ( p ) 鼍罂( x ) 其中j 是圩维区间，f ：r 1 - - 9 , r 区间全局优化的基本思想是将分支定界方 法和m o o r e - s k e l b o e 婶l 算法相结合对这类算法，h a n s e n t 7 习首次提出区间全局优 化这一概念在这一研究领域，所有算法都包含精确区间计算，算法的执行效率 都依赖于目标函数、梯度和约束的区间扩张的构造方法 区间方法可分为五个基本步骤：定界、分支、终止、删除和分裂其中包含区 问分裂规则、删除规则及区间选择规则，各区间算法的不同之处在于这几种规则 的不同处理手段上 在分裂规则中，包括分裂方向的选取和分裂盒子个数的选取c s e n d e s 和r a t z 在1 9 9 7 年”1 研究了四种分裂方向的选取规则，当区间选择方向确定后，如何分裂 区间就显得十分重要传统的方法是将a 沿最长边二等分两个盒子m 】最近 c a s a d o 5 9 1 和m a r k 6 t t “1 等提出了一种新的多分裂技术，研究表明：在单个迭代步里， 将区阅分裂成多个子区闯。能如快算法的收敛速度 在删除规则中，所谓加速工具就是用来删除不含全局极小点的区间或收缩子区 问现有的加速工具有c u t - o f f 测试，单调性测试，凸性测试和区间n e w t o n 方法 等 在区间选择规则中，常规方法是按m o o r e - s k e l b o e 算法，即从l 中选取具有最 小( 并) 的盒子进行分裂最近c a s a d o ( 2 0 0 1 ) t ”提出新的启发式选择规则 上述两类算法对目标函数和约束函数表达式的形式没有具体要求以上列举了 两类算法的研究状况，还有许多非凸优化算法的研究工作也取得了新的进展，如 分支定界法、进化算法、l i p s c h i t z 方法等近年来，对非凸优化问题的研究已经 取得了很大的进展，但由于这些问题的复杂性，要设计出更有效的全局优化方法， 特剐是对大规模阔题，还需要科学工作者不懈的努力 1 4 本文的主要内容 本论文主要研究和构造了两类全局优化算法；填充函数法和区间算法，给出了 算法的理论分析和数值结果，已取得了熏要进展全文共分五章，主要内容如下： ( 1 ) 在已有的填充函数法的基础上，对一类非光滑问题提出了一类改进的双参 填充函数法，并进行了理论分析移大量的数值计算 ( 2 ) 针对l i p s c h i t z 规划本文构造了一类应用更广的单参数填充函数，并给出 了算法理论分析和数值试验均表明该算法是可行、有效的 ( 3 ) 先利用线性加权法将多目标规划转化为单目标规划，再利用填充函数法求 得该单目标规划的全局最优解，从而得到原规划的最小弱有效解 ( 4 ) 通过引入拟偏导数的概念，建立了目标函数的区间扩张和无解区域删除检 验原则，提出了求解离散的m i n i m a x 问题的区间算法理论分析和数值结果均表 明该算法是有效的 第二章一类非光滑规划的双参数填充函数法 本章主要讨论了求解弱半光滑规划的全局极值点问题，根据已有的填充函数 法，针对所求问题的特点，提出了双参数填充函数法理论分析及数值试验均表 明本章提出的方法均优于已有的相关算法。 2 1 引言 填充函数法是近年来发展起来的求解优化问题全局极值点的一种有效方法， 由于其简单的构造形式及算法的有效性而得到了研究者的广泛关注它的基本思 想是通过构造一个辅助函数使问题从一个局部极小解转到另一更优的局部极小 解，如此循环，直至求得问题的全局最优解 考虑闯题 口) 鼍磐，( 功 ( 2 - 1 ) 其中厂：q c 掣一震，q 为紧集，苁曲在q 内有极小值点 本章假定当0 x l l 专佃时，f ( x ) 寸佃 先给出几个基本概念和引理 定义2 1 f ：q t - r “一r ，线段x 。一x ：称为，( 的一个下降线段，如果对任意 0 口 口 1 ，不等式 f ( x 1 ) f ( o v c 2 + ( 1 一o o x i ) 定理2 , 3 f 是弱半光滑函数，且满足 ，( x ，d ) = m a x 善7 di 善耖( z ) 假定0 i n t o f ( x i ) ，则f 是一个孤立的局部极小点 2 2 2 双参数填充函数及其构造 设x i 为，( z ) 的一个局部极小点，构造函数 讪，= 去一学， 任， 其中，p 为参数，下面证明在一定条件下只。，( x ) 是厂( 工) 在x ：处的填充函数( 定义见 3 c 1 4 1 ) 定理2 , 4 设i 为，( x ) 的个局部极小点，只，( 曲如( 2 - 3 ) 定义，这里，为常数， 满足：，+ 厂( x ? ) 0 ，则x ：为p ，( 习的一个局部极大点，r f ( x ) 在x i 的整个谷 域为p r ，( x ) 的山域的一部分( 与p 无关) 证明( 1 ) 对任意x s ：，工x 0 有，( z ) ，( z ：) 于是，+ 厂( ，) ，+ 厂( x ；) 0 ， 所以有不等式 啪) = 而1 一学 0 ，妒( ，) 在【o ，l 】上严 格单调递增，所以i 南丽与一等雌一石2 在 o ，1 上都是严格单调递减的，故矿) 在 o ，1 上也是严格单调递减的，结论得证 定理2 5 设x ：是，( x ) 的一个局部极小点，只，( x ) 如( 2 3 ) 定义，且满足 叭斋 0 反证：如果，( ；) ，o ：) 则 ，+ 厂( 而，+ 厂( 0 ) 0 ( 2 5 ) 令踯) = 南，则有 。叫，一与弘， 由非光滑分析理论有： 解，面= 蔚( ，( - ) ) 一v 学 ：帮_ ) ) 一下2 ( x - x , ) ， 由于，：q e r ”呻冠s ：r 寸胄，s 在，( ；) 处强可微( ，( ；) + r o ) ，故 帮( ，6 ) ) 亡忸孝i 毒o f ( x ) ，球瓠( ，( - ) ) 。矗斋矧善e 钞m 于是 面c - 焉+ 学 又因为；是只，( x j 的局部极小点，所以o 衅，6 ) 。故存在善e f ( x ) ，使得 喜i + 掣：o p + ，( _ ) ) 2 。p 2 上式两端与；一x ? 作内积得 螳+ 业雩也：o ( ，+ ，( ) 2p 。 即 2 i i x - x ： 1 1 2 = 篙 利用c a u c h y s c h w a r t z 不等式得 2 i i x - x ：1 1 2 s 紫 由0 孝 l 上，j j x - - 工：i i d ，从而有 2 ： 丝 ( r + 厂o ) ) 2 再由( 2 5 ) 式得： 芝r ；丝 ( r + ，( x ：) ) 2 一三 这与条件( 2 - 4 ) 矛盾，因此，( ；) m ? ) 由定理2 4 ，定理2 5 可知，若，p 满足条件( 2 - 4 ) 时。由犯一3 ) 所定义的函数 只，( d 为，( 力在工：处的填充函数，故可以在一定条件下求得，( x ) 在x ；处的埃充函 数的极小点或鞍点；，从而保证j r ( - ) 厂o ：) 于是以；为初始点，极小化厂( x ) 所 得另一个局部极小点x ；一定满足j r ( x ：) ，( 并) ，依次进行下去，我们可以得到 厂( x ) 的一组全局极小点序列 x ； ，扣1 , 2 ，m - i ，满足 f ( x 2 ) 0 ，且 o ( ( 州) 2 0 ，( x i ) d s 0 ， 由于对任意善钎，有 善7 d s ，“田 0 ，所以d 是只，( 功在x 处 的一个上升方向 ( 2 ) 要使对任意玎僻，( 曲，有矿d 0 由( 2 - 7 ) 式知，只要证明对任意善矽( x ) 有 圭旦；+ t 2 ( x - x ；) r d o ，p 0 s t e p 3 从茸出发，利用非光滑函数局部极小化算法，对0 ，( x ) 极小化，所得 序列为k 如果k 走出q ，可采用轮换坐标搜索法，置 x l ：= x ：6 ，i ；1 , 2 ，h( 2 9 ) 其中e ( f = l ，2 ，一) 为单位坐标向量，5 为预先给定的常数如果以x 。和( 2 9 ) 为初 始点所得到的极小化序列依然离开q 。则转向s t e p 9 s t e p 4 若斗满足以下几个条件之一，则置；：= 扎 ( 1 ) f ( x 。) ， ：) ； ( 2 ) 只，( x d 只。，( 屯i ) ； ( 3 ( h x ：) 善0 ，v 善啤， 。) ； ( 4 ) 忙i i ，( x ：) ，且4 ，( x ：) ，且4 a ，则置x ：= 工；，终止计算 s t e p 9 缩小r 从而使比值_ ；7 i 增大，置a ：= a + l ，转s t e p 2 r + _ ，【毛) 算法中每一步迭代用的均为非光滑极小化算法，这样在求解极小点或鞍点的 过程中得到的点列有可自2 不在定义域内，为此文中采用了轮换坐标搜索法( 详见算 法s t e p 3 ) 。也可在算法s t e p 3 中置x 。_ - x ：土( x ；- x ；) j l x ；一# f | 代替( 2 9 ) 式如 何将这种影响降至最低，也是作者进一步要研究的问题 另外，本文提出的方法对光滑函数也同样适用求解非光滑函数局部极小化 的方法很多，此算法中可用文【9 】中z o w e 提出的b - t 算法( b u n d l e t r u s t e r i n g a l g o r i t h m ) 2 4 数值结果及其讨论 这一部分将通过数值试验及其结果比较验证算法的有效性 为了叙述方便把文 1 4 1 和文 1 7 1 的算法分别记为算法l 、算法2 。以下算例是在 p e n t i u mi v 微机上采用m a f l a b6 1 语言编程进行运算的，算法的终止准则为 f = 1 0 8 例1 i “，( x ) = ( x 2 - 1 2 7 5 x ? z 2 + 5 x l 万一6 ) 2 + 1 0 ( 1 一o 1 2 5 1 r r ) c o s x l + 1 0 ， - 5 s 而1 0 ，0 s x 2 1 5 傍2 t ”，( x ) = 矸十霹- c o s ( 1 8 x 1 ) 一c o s ( 1 8 x 2 ) ， 一l 而，石2 墨l ， 例3 t 。刚，( x ) = 1 0 s i n 2 ( 荔1 ) + ( x 6 1 ) 2 5 + o i i ) 2 【i + 1 0 s i n 2 ( ，“j j ，r 6 ， 一1 0 置1 0 ，i = 1 ，2 ，6 例4 胁刖，( 功= 1 0 s i n 2 ( 形1 ) + 0 6 一1 ) 2 + 5o ，一1 ) 2 口+ 1 0 s i n 2 ( 砂f + 1 ) 】弦6 ， ，t l y j = + 3 4 ，一1 0 x 1 0 ，i = 1 , 2 ，6 侈95 t “2 1 ，( 功= s i n 2 ( 3 瓣1 ) + ( x 6 1 ) 2 1 + s i n 2 ( 2 ，6 ) 】 5 + ( x 。一1 ) 2 1 + s i n 2 ( 3 + t ) 】 1 0 ， t = l 一1 0 x - 1 0 ，i = 1 ，6 大量的数值运算表明，在同一初始点的前提下，本文算法的迭代步数比算法1 、 算法2 少，而且当选取的初始点越靠近箱式约束的边界时算法1 、算法2 的迭代步 数明显增加，而本文的迭代步数变化不大另外，在相同的初始点情况下，本文 的c p u 用时比算法1 、算法2 少 对于例1 ，任意选取初始点( 4 0 0 个) ，利用算法1 、算法2 及本文算法求得全局 极值点均有3 个，在所选的精度范围内，三种算法所得的结果相同，它们分别为： ( 3 1 4 1 5 9 2 6 3 ，1 2 2 7 4 9 9 9 9 ) , ( 3 1 4 1 5 9 2 6 2 ，2 2 7 4 9 9 9 7 1 ) ，( 9 4 2 4 7 7 7 8 9 ，2 4 7 4 9 9 9 6 1 ) 以初始点( 0 ，1 0 ) 为例，本文算法与算法l 、算法2 的结果均为( 3 1 4 1 5 9 2 6 3 ， 1 2 2 7 4 9 9 9 9 7 ) ，迭代步数分别为1 、7 、5 步 对于例2 例5 ，我们仅以两个初始点为例( 一个在箱式约束内部，另一个靠近 箱式约束的边界) ，结果比较详见表2 1 表2 4 表中所用符号意义表示如下： s u m ：极值点的总数 表2 1 运行效率结果比较i 倒2例3例4饲5 韧始点 6 0 0 3 ，0 0 8 )1 ，一1 ，一l ，l ，1 ，1 )( 】，0 3 ，0 9 1 1 1 2 ，1 )( 2 ，3 ，4 ，q 一】，- 1 ) c 阿本文o 1 5 60 7 6 6 0 4 5 30 1 7 2 用时 算法10 8 5 92 9 3 20 7 1 2o 5 1 5 ( 秒) 算法21 0 9 3】7 0 81 9 5 50 4 3 6 本文 35l2 迭代 算法176 58 、 1 0 步数 算法27l o4 51 0 表2 2 运行效率结果比较 倒2倒3倒4倒5 初始点 ( - 0 5 ，0 8 )( 7 ，7 ，7 ，7 ，7 ，7 )( 6 ，7 ，6 ，7 , - 5 ，- 8 )( - 6 , - 7 886 ，7 ) c p i j本文0 0 4 70 1 8 70 0 7 90 5 5 2 用时 算法10 0 9 43 3 7 10 2 6 60 9 1 0 ( 秒) 算法2 o 1 1 00 2 6 60 2 5 02 9 4 4 本文l 239 迭代 算法1 81 3 11 61 4 步数 算法2 71 65 24 0 表2 3 全局最优解结果比较i 倒2例3例4例5 初始点 ( - o 0 3 ，0 0 s ) ( - l ，- 1 ，- 1 1 11 ) ( 1 ，0 8 , 0 9 a 1 ，1 2 ，1 )( 2 ，3 ，4 ，0 , - 1 , - 1 ) s u m5 0 5 03 0 1 8 0 ( 1 o o o o o o 0 0 3 0 0 0 0 0 4 5 1 ， ( 0 9 9 9 9 9 5 5 8 ，1 0 0 0 4 2 6 9 2 ,( 1 ，0 0 0 0 0 0 0 0 ，l ，0 0 0 0 0 0 1 3 ， 本倡9 e 4 ) 8 , t 0 0 0 0 0 4 5 0 , 1 0 0 0 0 0 4 5 2 1 0 0 0 2 0 1 4 0 , 0 9 9 9 8 1 1 7 5 ， 0 9 9 9 9 9 9 8 1 ，1 0 0 0 0 0 0 1 8 ， 文 2 4 e - 0 8 ) 1 0 0 0 0 0 4 5 0 , 1 0 0 0 0 0 4 5 1 ) 1 0 0 0 2 3 9 4 5 。1 0 0 0 0 0 0 5 2 )o 9 9 9 9 9 9 9 1 o 9 9 9 9 9 9 9 9 ) 全 算 ( 1 0 0 0 0 0 0 0 6 ，i 0 0 0 0 0 t t 0 , 0 9 9 9 9 9 9 17 0 9 9 9 9 3 6 5 7 ,( 1 0 0 0 0 0 5 1 4 。0 9 9 9 9 8 8 1 6 ， 局 法 ( - 2 8 e 0 8 , 0 9 9 9 9 9 9 t 7 , 0 9 9 9 9 9 9 1 7 ，0 9 9 9 9 7 0 0 7 , 1 0 0 0 0 2 7 9 6 , 0 9 9 9 9 6 4 6 9 , o 9 9 9 9 7 0 2 4 ， 极 1 9 0 e - 0 8 ) l _ 0 0 0 0 0 0 2 8 , 1 0 0 0 0 0 2 3 7 )o 9 9 9 9 6 4 3 9 , o 9 9 9 9 9 9 9 1 ) i 0 0 0 0 2 1 9 0 , 1 0 0 0 1 6 9 8 3 ) 小 点 算( 1 0 0 0 0 0 0 0 8 ，1 0 0 0 0 0 2 0 8 ，( 1 0 0 0 0 0 0 4 1 ，0 9 9 9 9 6 6 6 3 ， ( 0 9 9 9 9 9 8 2 0 ，0 9 9 9 9 8 7 7 9 ， 法 ( - 2 $ f , - 0 8 。 0 9 9 9 9 9 8 9 2 ，t 0 0 0 0 0 6 5 0 ,0 9 9 9 9 8 4 2 6 ，i 0 0 0 0 t 4 2 , 0 9 9 9 9 6 3 5 9 。0 9 9 9 9 6 9 3 2 ， 2 9 ，0 e - 0 8 ) 1 0 0 0 0 0 0 3 6 1 0 0 0 0 0 2 9 0 ) 0 9 9 9 9 8 1 2 8 0 9 9 9 9 9 9 9 6 ) 1 0 0 0 0 2 2 5 8 ，1 0 0 0 1 7 5 1 2 ) 倒2例3例4例5 初始点 ( - 0 5 ，0 8 )( 7 ，7 ，7 ，7 ，7 ，7 )( 6 ，7 , 6 ，7 , - 5 ，- 8 )( - 6 ，- 7 886 ，7 ) s u m5 05 03 01 8 0 本 ( 4 9 e - 0 8 ，( 1 ，0 0 0 0 0 0 0 0 , t 0 0 0 0 0 4 6 8 ，( 09 9 9 9 9 9 8 9 , 0 9 9 9 9 5 9 0 7 ，( o 9 9 9 9 6 1 1 3 ，1 0 0 0 0 0 8 9 0 ， 文 _ 4 2 e - 0 8 ) 1 0 0 0 0 0 4 2 3 ，1 0 0 0 0 0 4 7 5 ，0 9 9 9 9 8 0 1o ，1 0 0 0 0 0 2 8 9 ， 0 9 9 9 9 3 8 1 1 ，10 0 0 2 5 2 6 3 ， 全 1 0 0 0 0 0 4 3 7 ，1 0 0 0 0 0 4 4 8 )0 9 9 9 9 9 0 1 7 , 10 0 0 0 0 6 8 蚧 09 9 9 4 3 3 3 8 ，1 0 0 0 0 0 7 2 4 ) 局 极 算 ( 5 2 e - 0 8 ，f 1 0 0 0 0 0 0 0 6 ，1 0 0 0 0 0 1 7 0 ,( i 0 0 0 3 0 6 1 2 ，1 0 0 0 1 4 9 6 6 ，( o9 9 9 9 7 3 4 9 ，1 0 0 0 0 0 0 0 3 ， 法 - 4 0 e 0 8 ) 0 9 9 9 9 9 9 17 0 9 9 9 9 9 9 1 7 ， ( 0 9 9 9 9 8 0 1 9 , 1 1 1 0 0 0 7 4 7 8 ，0 9 9 9 9 6 1 5 1 ，0 9 9 9 9 3 5 3 8 ， 小 11 0 0 0 0 0 0 2 8 ，1 0 0 0 0 0 2 3 7 )1 0 0 0 0 7 4 7 8 ，0 9 9 9 9 5 0 4 7 ) 0 9 9 9 2 6 3 6 2 10 0 0 1 3 9 0 1 ) 点 算 ( 6 8 e - 0 8 ，( 0 9 9 9 9 9 9 9 8 ，1 0 0 0 0 0 0 1 6 ， ( 1 0 0 0 0 0 4 4 ，09 9 6 0 4 0 4 0 ，( 0 9 9 9 9 9 9 2 4 ，1 0 0 0 0 0 4 3 8 ， 法1 4 e - 0 8 10 9 9 9 9 9 9 7 8 1 0 0 0 0 0 0 2 2 。0 ，9 9 9 9 0 6 4 1 ，! 0 0 0 0 0 2 5 7 ，09 9 9 9 6 4 3 2 ，0 9 9 9 9 4 4 4 4 ， 2 0 9 9 9 9 9 9 8 9 ，0 9 9 9 9 9 9 9 9 )0 。9 9 9 9 9 0 3 毛t 0 0 0 0 0 6 4 t ) 0 9 9 9