（运筹学与控制论专业论文）求解全局优化的填充法函数方法.pdf

摘要 通常一个求总极值的问题可以表述为：对于给定的一个n 维空间中的紧致集dc 形，及 给定的连可微续函数，：r ”_ r ，寻找某一点矿d ，使得对于一切的z d ，满足，( z + ) s ，( z ) 即求下述问题的解： 9 f d b 贻dm )0 或考虑求解更一般问题的解： 其中s = 。l g ：( z ) 0 ，i = 1 ，2 可微函数。 求总极值问题的方法在军事、 的应用。 g f 0 6 赌m ) r 是n 维欧氏空间的约束集玑( z ) ，i = 1 ，2 ，m 为连续 科学技术、工程设计、自动控制、经济管理等领域有着广泛 遗憾的是全局优化的理论与算法远不及局部优化的那么成熟，至今为止对于一般非凸函数 还缺少判别全局最优性的条件。 本文组织如下：第一章对全局优化求解方法进行介绍；第二章介绍填充函数方法的主要思 想以及所做的工作：第三章在所做工作的基础上构造一个性态更好的填充函数，并给出理 论证明；第四章在给出的填充函数的理论基础上给出实现算法，其数值试验的结果证明了 我们所提出的填充函数是有效的。 关键词：局部极小，全局极小，填充函数 、 ab s t r a c t t h e g l o b a lo p t i m i z a t i o np r o b l e mc a nb es t a t e da sf o l l o w s ： g i v e nan o n e m p t y ，c o m p a c ts e tdcr “a n dac o n t i n u o u sd i f f e r e n t i a b l ef u n c t i o n ，：a - - + r w h e r eacr “i sas u i t a b l es e t c o n t a i n i n gd f i n d a tl e a s to n ep o i n t 茁+ ds u c ht h a t f ( x ) ，( z ) ，f o ra l lz d ，i e g l o b m i n x e d ，( z ) o rw ec o n s i d e rt h em o r e g e n e r a l l yc a s e sa sf o l l o w s ： g l d b 墨一i n f ( z ) w h e r es = z 1 9 ：( z ) 0 ，i = 1 ，2 ，r i sac o n s t r a i n e ds e ti n r “9 。( z ) ，i = 1 ，2 c o n t i n u o u sd i 黯r e n t i a b t ef u n c t i o n s t h e r ea r em a n ) a p p l i c a t i o n so fn o n l i n e a r g l o b a lo p t i m i z a t i o ni nt h e f i e l do fm i l i t a r i n e s s ：s c i e n c e a n dt e c h n o l o g y , o p t i m a ld e s i g no fe n g i n e e r i n g ，a u t o m a t i cc o n t r o l ，e c o n o m i cm a n a g e m e n ta n d s oo n u n f o r t u n a t e l y ，t h et h e o r ya n da l g o r i t h mo fg l o b a lo p t i m i z a t i o ni sn o w h e r en e a ra sm a t u r ea s t h a to ft h el o c a lo p t i m i z a t i o n ，s of a r ，f o rn o n c o n v e xf u a c t i o n ，t h e r el a c k so ft h ec r i t e r i o nf o r g l o b a lo p t i m i z a t i o n t h ep a p e ri so r g a n i z e da sf o i l o w s ：i nc h a p t e r1 ，ab r i e fi n t r o d u c t i o ni s g i v e nt ot h es i g n i f i c a n c ea n dt h ep o p u l a rm e t h o d st ot h eg l o b a lo p t i m i z a t i o np r o b l e m s i n c h a p t e r2 ，w ei n t r o d u c es o m em a i ni d e aa n ds o m ew o r ko nt h ef i l l e df u n c t i o nm e t h o d i n c h a p t e r3 ，w eg i v ean e wf i l l e df u n c t i o no nt h eb a s eo ft h ew o r kt h a th a sb e e nd o n ea l r e a d y i nc h a p t e r4 w ec o n s t r u c ta ni m p l e m e n t a b l ea l g o r i t h ma c c o r d i n gt ot h ef i l l e d f u n c t i o n n u m e r i c a le x a m p l e si s g i v e nt oi l l u s t r a t et h ee f f e c t i v e n e s so ft h ei m p l e m e n t a b l ea l g o r i t h m k e yw o r d s ：l o c a lo p t i m i z a t i o n ，g l o b a lo p t i m i z a t i o n ，f i l l e df u n c t i o n i i 第一章绪论 在这一章中，我们主要对于全局最优化的作用、意义、主要困难和目前的有关方法给予简 要的介绍。 1 1全局最优化的作用、意义及主要困难 全局最优化的研究目标是对于无约束或有约束的非线性函数求其全局最小( 或最大) 。全 局最优化问题通常可以表述为：给定礼维欧氏空间中的一个非空闭集d 和一个连续可微函 数f ：r “斗r ，寻找点x d ，使得，( z + ) ，( z ) 对所有的z d 成立。即 9 1 0 bm 唤，( 茁) ( 1 1 1 ) z t 客观世界中的很多实际问题都可以抽象成全局优化的数学模型。全局优化的应用涉及科学 技术、军事、工程设计、智能控制、经济管理等现实世界中的方方面面，有着广泛的应用 背景。然而由于问题全局性的要求，使得在求解全局优化问题的算法研究中存在着相当的 难度，其主要的难点是；现有的非线性优化方法一般只能求出局部最优点此外，还缺乏 有效的判别准则来判断一个局部最优点是否是全局最优，从而使得那些利用导数、梯度和 次梯度求局部最优解的方法难以找到全局最优解。因此，关于全局优化问题的求解到目前 为止仍然是个非常困难的问题，有很多理论和实践问题亟待解决。 1 2全局最优化问题研究的有关方法 求解全局优化问题的算法，大致可以分为两类：一类是确定性算法：一类是随机算法和启 发式算法。 确定性算法其主旨是利用问题的解析性质产生一确定性的有限或无限点序列使其收敛于全 3 局最优解。主要的解析性质是凸函数的连续性、可微性。确定性算法主要包括以下一些算 法：外逼近方法，隧道函数法，填充函数法，分支定界法，区间方法，积分方法等。 随机算法适用于确定性算法无法应用的全局优化问题。这些方法一般仅需非常弱的假设， 而且至少能够提供概率收敛的框架。随机算法主要分成三类：二阶段法，随机搜索方法， 随机函数方法。 某些算法通常是通过模拟生物进化，人工智能，数学与物理科学，神经系统和统计力学等 概念，以直观为基础构造的。此类算法我们称为启发式算法。启发式算法主要包括禁忌搜 索，模拟退火，遗传算法，人工神经网络等。 下面我们对部分算法进行简要介绍。 1 2 1 外逼近方法 外逼近方法，是用一系列比较简单的松弛集合从可行域的外侧来逼近可行域的方 法。在优化领域特别是组合优化中，外逼近方法已经成为一种基本的方法，最早的文献可 见g o m o r y ( 1 9 5 8 ，1 9 6 0 ) ，c h e n e y 和g o l d s t e i n ( 1 9 5 9 ) 及t k e l l e y ( 1 9 6 0 ) 在全局优化问题中，该方 法可以用来求解凹规划( h o f f m a n1 9 8 1 ，t h i e u ，t a m 和b a n1 9 8 3 ，t u y1 9 8 3 ，t h o a i1 9 8 4 ) ，具 有反凸约束的问题( t u y1 9 8 7 ) ，d c 规划( t u y l 9 8 6 ，t h o a i1 9 8 8 ) 和l i p s c h i t z i a n 规划( t h a c h 和t u y1 9 8 7 ) 等。 1 2 2 隧道函数法 隧道函数法由l e v y 和m o n t a l v o ( 1 9 8 5 ) 首先提出，该方法要求目标函数，( z ) 二次连续可微，且 假设，( z ) 只有有限个孤立极4 、点。算法由两个过程组成：极小化过程和“凿隧道过程”。 这两个过程交替进行，从而得到目标函数的全局最优解。 1 2 3 填充函数法 填充函数法是g e ( 1 9 8 3 ，1 9 8 4 ，1 9 9 0 ) 及g e 和q i u ( 1 9 8 7 ) 所作的工作。其主要思想是：首先应用求 局部极值的方法，找到目标函数，( z ) 的一个局部极小点z ：；然后构造z ：处的填充函数，求解 填充函数可以找到一个在比o ：处的盆谷低的盆谷中的点z 7 ，以一为初始点，求，( z ) 的另一局 部极小点z ；，继续在端处构造填充函数，不断循环从而最终找到目标函数的全局极小点。 假定目标函数为二次连续可微，局部极小点只有有限个。 4 1 2 4 分支定界法 分支定界法是求解最优化问题，特别是组合最优化及全局最优化问题中使用的较为广 泛的一种方法该方法的主要思想是，将可行域松弛并不断地划分成小区域，在这些 小区域上函数的上、下界容易确定，即不断地实施分支和定界等步骤，最终找到目标 函数的全局最优解。该方法主要应用于凹规划，d c 规划和l i p s c h i t z i a n 规划。文献 参见t u y ( t u yk h a c h a t u r o v 和u t k i n1 9 8 7 ) 及h o r s t ( h o r s t1 9 7 6 ，h o r s t1 9 8 6 ，t u yt h i e u 和t h a i1 9 8 5 ，t h o a i 和t u y1 9 8 0 ) 等。 1 2 5区间方法 m o o r e ( 1 9 6 6 ) 首先发现了区间分析是计算一个函数在子箱x 上的下界的极有效的工具，它几 乎可阻计算出全局最优值，。1 9 7 4 年，s k e l b o e 把m o o r e 的一部分思想与分支定界原理结合起 来。最后，m o o r e ( 1 9 7 6 ) 再次修改，得到了m o o r e s k e l b o e 算法。算法的主要思想是：先作目 标函数，：x - 4 r 的扩张函数f ：i ( x ) - - + i ，然后利用分支定界的思想，把x 逐步细分，最 后找到全局最优值，。 1 2 6 积分方法 积分方法由郑权( 郑权、蒋百川和庄松林1 9 7 8 ，c h e wa n dz h e n g1 9 8 8 z h e n ga n dz h u a n g 1 9 9 5 ) 等提出，其突出的优点是思想简明直观，对目标函数和约束函数的f 艮制较少f 只要求函 数连续) ，并有修正准则，应用范围较广。数值例子说明，该方法是一种较为有效的全局优 化方法。不足之处是计算量较大。 1 2 7 二阶段方法 二阶段方法主要由全局步和局部步组成。全局步是计算函数在可行域上随机样本点处的函 数值，局部步是在这些样本点处进行内部搜索。通过上述两步产生问题的全局最优解。 1 2 8 随机搜索方法 随机搜索方法是一种由可行域内遵循某种预先给定的概率分布所产生的点序列构成的算 法。这种算法可应用于无法进行局部搜索过程的问题，具有很好的适应性。此类算法中 最基本的算法就是p r s 算法，更一般的方法为基于观察到的样本点适当地校正样本点的分 布。 1 2 9 禁忌搜索算法 禁忌搜索( t a b us e a r c h ) 算法是局部邻域搜索算法的推广，是人工智能在组合优化算法中 的一个成功应用。g l o v e r 在1 9 8 6 年首次提出这一概念，进而形成了套完整算法。该算法 的特点是采用了禁忌技术。所谓禁忌技术就是禁止重复前面的工作。为了回避局部邻域搜 索陷入局部最优的不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在 下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优 点。 1 2 1 0 模拟退火算法 模拟退火( s i m u l a t e da n n e a l i n g ) 算法是局部搜索算法的拓展。它不同于局部搜索之处是以 一定的概率选择邻域中费用值大的状态。理论上来说，它是一个跳出局部最优求全局最优 的算法。模拟退火算法的思想最早m e t r o p o l i s 在1 9 5 3 年提出，1 9 8 3 年k i r k p a t r i c k 将其成 功地应用到组合最优化中。 1 2 1 1遗传算法 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局化概率搜索 算法。该算法最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年代对自然和人工自 适应系统的研究。7 0 年代d ej o n g 基于遗产算法的思想在计算机上进行了大量的纯数值函 数优化计算试验。8 0 年代，g o l d b e r g 在一系列研究工作的基础上进行归纳总结，形成了遗 传算法的基础框架。 1 2 1 2人工神经网络 人工神经网络的早期工作可以追溯到1 9 4 3 年m c c u l l o c h 和p i t t s 建立的第一个模型，后被扩 展为“认知”( p e r e e p t r o n ) 模型。2 0 世纪8 0 年代，h o p f i e l d 将人工神经网络成功地应用于 组合优化问题。m c c l e l l a n d 和r u m e l h a r t 构造的多层反馈学习算法成功地解决了单隐含层认 6 知网络的“异或”问题及其它的识别问题，他们的突破使得人工神经网络成为新的研究热 点。 7 第二章用填充函数求解全局最优化问题的算法 现实世界中，许多实际问题的解决都需要我们对全局最优化问题进行求解在对这类全局最 优化问题的研究过程中斗多不同的求解方法被提出来，其中包括填充函数方法本章主要介 绍了填充函数方法的研究概况。 2 1 填充函数法的主要思想 填充函数方法最初是由葛人傅( g e l 9 8 3 ，1 9 8 4 ，1 9 9 0 ) 提出来的。 考虑全局最优化问题： 。r a r i n 。m ) ， ( 2 1 1 ) 其中，是二次连续可微函数，且满足条件 ，( z ) _ + o 。，忪| | _ + + 。( 2 1 2 ) 在上述条件下，一定存在一个有界闭集xcr “，在x 内部包含，( z ) 的所有全局最优点。我 们假定x 是已知的，并假设，( z ) 在x 中只有有限个极小点，所以这些极小点都是孤立极小点。 于是( 2 1 ，1 ) 可写为： m 耐i n ，( 。) t ( 2 1 3 ) 定义，( 。) 在孤立极小点z i 的锰谷研是一个连通域，z ! b ：，而且从磁中任意一点出发 的，( 。) 的最速下降轨迹趋向于z ：，但从b ：外面的点出发的最速下降轨迹均不趋向于z i 。 定义在孤立极小点。i 的盆谷b ：的半径为 r = m i n 忪一z 孙( 2 1 4 ) z g 研。 、7 若，( z ) 在。i 处的日e s s 纰礼阵v 2 ，( z ：) 是正定的，则半径r 大于零。 称，( z ) 在z ；处的盆谷彩低于( 高于) ，( z ) 在z ：的盆谷b ；，当且仅当，( z ；) ( ) ，( 。：) 。，( z ) 在 r 极大点矗处的山丘定义为一，( z ) 在其极小点贲处的盆谷。 填充函数方法的主要思想是：首先用一个求局部极小的方法，如变尺度法等，找 到，( z ) 在x e p 的一个局部极小点z ：；然后，设法找出， ) 的另一个局部极小点z ；，并且满足 不等式： ，( z ；) 0 。 g e 证明了，当参数r ，p 满足某些条件时， 其算法如下： 步1 选e 0 ，f l o ，使f l 。和，2 不太大，同时使f 7 缶可较小。 步3 构造填充函数 晰= 南e 丹与掣) 9 用b f g s 方法求其极小，初始点选为 x 1 = z j + 如l ， 6 0 其中6 可选p v 幢 步4 若p ( x ，r ，p ) 的极小化序列超出x ，则依次选 z ，= z ：+ 6 e 。，i = 2 ，- - ，o ，6 0 ( 2 1 7 ) ( 2 18 ) 如果由式( 2 i 7 ) 和( 2 1 8 ) 表示的所有的矗都用过了，且所有的极小化序列都超过出x ，则转 步1 0 步5 若在极小g p ( z ，r ，p ) 过程中，下列条件之一在z t 成立，则令z ；否则继续极小 化p ( z ，r ，p ) 。 ( 1 ) ( z k z i ) r v p ( x ，r ，p ) 0 ； ( 2 ) f ( x 女) 0 同时，妒( t ) 必须满足如下性质中的一部分： ( 1 ) 妒7 ( ) 三0 ，v t 0 ，+ 。) ；妒( ) o , v t ( - t l ，o ) ，其中l 0 ( 2 ) l i r a + 旧妒( t ) = 0 ，l i r a + + o 。t 妒= 0 即妒是至少以1 肛的速率单调递减直至o ( 3 a ) 妒( 0 ) = 0 ，l i m t 一+ 。妒( t ) = b o ； ( 3 b ) 妒( 0 ) = 0 ，l i m t - + + 。妒0 ) 0 ， ( 4 ) l i m t - - - - - o o 妒( t ) = 一。 ( 5 ) “m t + + 。妒“( t ) = 0 假设z o r n 是给定的点，z ：是，( 。) 的一个局部极小点，z + 是，( z ) 的全局最优点，参数r2 1 p 0 填充函数构造如下： 仉( z ，r 1p ) = 叼( ；| 1 z z 。| | 2 ) 妒( 丁 ，( z ) 一，( z ：) + 卢i ) ， ( 2 2 l o ) 其中， ( i ) 叩( t ) 满足上述性质( 1 ) 和( 2 ) 。 ( i i ) 妒( f ) 满足上述性质( 1 ) ，( 2 ) ，和( 3 a ) ； ( i i i ) p n 足0 p ，( z j ) 一f ( x + ) v ( 。，r ，p ) = 卵( ；i i z 一茁o l l 2 ) + 妒( 丁【，( z ) 一，( z ：) + p ) - ( 22 1 1 ) 其中 ( i ) 机f ) 满足上述性质( 1 ) 和( 2 ) ； ( i i ) f ( f ) 满足上述性质( 1 ) ，( 2 ) ，( 3 b ) ，( 4 ) 和( 5 ) ： ( i i i ) p 满足0 0 是满足适当条件的参数。 1 3 第三章新的填充函数 这一章中，我们对填充函数的定义作了进一步的改进，给出了填充函数的新定义，并且构 造了一个性态更好的填充函数。我们给出的填充函数为单参数形式，并且该填充函数一定 有一个局部极小点属于目标函数值比当前的局部极小值小的区域内。本章证明了我们给出 的填充函数满足填充函数的新定义。 3 1填充函数的新定义 下面我们给出填充函数的定义： 设z ：是函数，( z ) 的一个局部极小点，z ；是满足，( z ；) 0 使得对所 有的z ( z j ，盯t ) ，z z ：，成立 ，( z i ) s ，( z ) ，( 32 1 ) 于是对z 扣：，盯i ) 成立： p ( z ：，z j ，e ) = f 一 2 + 订可丽而 r ( 32 2 ) = p ( z ，z i ，) 所以，。i 是p 扛，x l ，e ) 的一个严格局部极小点。 ，32 1 表明：，( z ) 的一个局部极小点是p ( z ，z i ，e ) 的个严格局部极大点，且显然_ 厂( z ) 在z j 处的局部极小点邻域为p ( z ，z ：，e ) 在z ：处的局部极大点邻域即p ( z ，。：，e ) 满足填充函数性 质p o ) 】5 定理3 2 2 如果，( z ) ，( z ：) ，z z i ，那么，对足够小的e o ，成立v p ( z ，z j ，e ) 0 v p e 。，z ：，e ，= 一。c z 一嚣；，一；j ；i i j 嬲 c 。z s ， ( i i ) 女口果v ，( 。) 。，男口么，令d ( z ) = i ；j j 蒜 当o e 参丢时，有 v 杈叩沁) d ( 垆m 川i 卜警揣襞群 禹 一。陋侧一鬻靠黼禹c 。， p ( x ，z ：，e ) 0 ，f ( x 2 ) f ( x 1 ) 兰，( z ：) ，那么 p ( x 2 ，x 1 ，) p ( x l ，j 7 + 1 ，f ) ，( 。2 ) ，( z i ) ， 监型业兹肖摊高等糍拶巡， 。剐 那么， p ( 工2 ，x l ，e ) p ( x l ，z i ，e ) e = p ( z ：，t 1 ，e ) 证明若p ( z 2 ，z i ，e ) o ，则有： 一i i z 。一。训2 + 丁干_ i 了耳i 前 一 x l - - x 川2 + r 干_ i 7 石i 斋 f _ ( 3 2 1 0 ) 由此可以推得， 监型业舞咎摊高掣器笋幽，( 3 。圳 显然， p ( z ，z i ，e ) = 一i i z t z ：| 2 + i _ = f _ i 7 i ；j 丽 0 ，p ( z ，z ：f ) 在z i 和z 2 的连线上有极小值。 证明因为z ；是，( z ) 的严格局部极小点，那么存在z ；的一个邻域( z ；，叻) ，口2 o , 对f f f t 的z ；( 誓；。0 ) ( z ；，有， ，( z ；) ，( z ；) o 足够小 选取z ；l 。i 。n ( z ；，j 2 ) ，使得 并且令x 2 充分接近z ；，使得 z ；一z ；| | zi i x z z ：m ，( z z ) 一，( z ：) z ，( z ；) 一，( z i ) 因此，我们有，( z 。) 一，( z ：) p ( x 2 z ：，e ) 显然，对任意的z l 2 _ r _ 2 1z z ：，有，( z ) ，( z i ) 由定理3 2 4 可知， p ( x ，z ：，e ) 0 4 够小时，有 ( 3 2 1 3 ) ( 3 21 4 ) p ( z 茁：，e ) = 一i i z z i | | 2 + i _ = j 弋j i ；斋 一l | z ；一z ：i | 。+ e + ：( ，( z ；) 一，( z ：) ) 3 ( 3 _ 2 - 1 5 ) = p ( 。：，x i ，e ) 1 8 p ( z ，：e + 1 ，e ) 0 ，如果。；是p 扛，。：，f ) 的一个局部极小点，那么成立 ，( 茁；) f ( x d ， p ( z ；，x + 1 ，e ) o 足够小时，v p ( x ；，z ：，) o ，故z ；y f i 是p ( x ，x + 1 ，) 的局部极小点。这 与z ；为p ，z ：，) 的局部极小点矛盾，所以一定有，( z ；) ，( 茁! ) ，并且， p ( z ；，z ：，e ) = 一1 | 工； z ：l 】2 + e + ( ，( z ；) 一( x j ) ) 3 e = p ( z + 1 ，z 1 ，e ) 定理3 2 8 如果茁；是，( z ) 的满足，( z ；) 0 为某一实数，并且成立 ，( 牙) ，( z ：) ，p ( 牙，z ：，e ) p ( 。i ，z ：，e ) = e 证明。因为z ；是，( z ) 的严格局部极小点，且，( z ；) o ，使得对所有的 r ： ( 。；，g 2 ) ，z ：z ；，有 ，( z ；) ，( z ：) o 满足，( t ；) + e 2 0 适当小 1 9 e “ f f z ；一z ：f i i 1 1 2 + f + ( ，扛；) ，( z ：) ) 3 1 1 2 + e + ；( ，咖) 一，扛：) ) 3 ( 3 2 1 6 ) p ( z ；，z ：，e ) = 一| z ；一z 州2 + e + ；( 厂( z ；) ，扛；) ) 3 p ( z ，。i ，e ) ( 3 2 1 7 ) = 一i t - - 州2 + e + ( ，( z ) 一，( z ：) ) 3 ， 那么，当e 2 充分小时， i x - - 3 c ：1 i z l | z ；一z i i l 2 【( ，( z ) 一，( z i ) ) 3 一( ，( 。；) 一，( z ：) ) 3 】 = 詈匿+ 3 f 2 ( ，( ；) 一，扛i ) ) + 3 ( ，( ) 一，p ：) ) 2 ) ( 3 2 1 8 3 詈( m ；) 一m 舭 即 心e 拶掣褡缘 因为e 元。；) 帕是有界闭集，由式( 3 - 2 1 6 ) ，( 3 2 1 7 ) 可知， 令 我们可以得到 p ( t 勰1 ，f ) 。；罱p ( 郴4 1 6 ) 爵。拍：= z ( z ；，) ：，( z ) 曼，( z ；) + e 2 f 32 ，1 9 1 ( 3 ，2 2 0 ) m i n 伽赫。如z = m 浊御赫。e 弛。p z 2 p ( 茔，z i ，) f 32 2 1 ) p ( z ；，。i ，e ) r a i n z e 元。；) 。p ( z ，z i ，) 卅 叫 2 z 上 一 一 l i o 充分小时，a 为开集。 所以，牙是p ( z ，z ：，f ) 的局部极小点，并且 牙( z ；，盯2 ) ，( z ；) ，( 牙) ，( z ：) ； p ( 雪，x ，e ) p ( z ；，。i ，e ) = 一f l z ；一z 刊2 + e + ；( ，( z ；) 一，( z ：) ) 3 o 足够 小时，满足f ( x ) 2 ，( z ：) ，z z ：的点z 才不是填充函数的平稳点。因此。我们取比较小的参 数e 的初始值，并在求解过程中不断调整使之逐渐变小，以保证我们在极小化填充函数的过 程不会在f ( x ) 兰，( z i ) 的区域内终止。 ( 2 ) 灵活考虑中间结果 求解填充函数局部极小点的目的只有一个，就是找到目标函数值比当前局部最优值更小的 可行解。因此，在求解填充函数局部极小点过程中，如果有某个跌代点的目标函数值比当 前局部最优值更小，则立刻转入下一步求解目标函数的局部极小点；否则，我们在迭代路 径周围随机投点，一旦发现目标函数值比当前局部最优值更小的可行解，立刻转入下步 求解目标函数的局部极小点。 f 3 ) 终止准则问题 在该算法中，我们用如下的条件作为算法停止的条件： 如果我们取遍参数e 的范围中的值，仍没有得到目标函数值更优的可行解，这时我们认为当 前局部极小点即为全局极小点，算法终止。 2 2 4 2 实现算法 结合上述的一些问题，我们给出实现算法： 步1 取可行点z o ，p 为终止参数。 初始化参数：p 可以取值为1 0 。6 ，e 可以取值为1 0 3 今k ：= 0 步2 以z 为初始点，通过局部极小化算法( n r 算法) 求解，( z ) 的局部最优解z i 步3 构造填充函数 p ( z ；z ；e ) = - i i x z ；1 | 2 + 币丽+ ( m i n 。，m ) 一m ：) ) ) 3 步4 利用局部极小化算法( n - r 算法) 极小化填充函数。在填充函数的局部极小化过程中得 到迭代点列 z i ) ，t = l ，2 ，丁 ( a ) 如果得到填充函数的局部极小点z 玉，则令：= k + 1 ，z ：= z ；k ，转步2 ( b ) 如果在极小化过程中得到某个z 挈，1st o t ，使得，( z ) ，( z ；) ，则令女：= 女+ 1 ，孤：= z 挈，转步2 ； ( c ) 如果在极小化过程中迭代点列到达边界，则依次在迭代点。；( = 1 ，2 ，：t ) 的 邻域( z 2 ，o 5 i i x l x ：1 1 ) 内进行随机投点，一旦发现某点一满足，( z ) ，( z ；) ，则令 k ：= + 1 ，z 女：= 一，转步2 步5 如果步4 中的三项都不满足，此时进行参数调节： 若e p ，减小e ( 可取e ：= l o 一1 e ) ，转步3 ； 若e p ，算法终止，z ；为全局极小点，( z ：) 为全局最优值。 2 3 第五章数值试验 这一章中，我们在前面所提出的填充函数及其算法的基础上进行数值实验。数值结果说明 了算法的有效性。 问题1 m i n m ) = 2 平一1 0 5 z + 社1 - - x t x 2 d - x l s t 一3sx l 3 ，一3s0 2 3 此目标函数称之为3 一h u m p c a m e l b a c k 函数，具有三个极小值，二个鞍点。利用第四章中 的实现算法求得函数问题的解为矿= ( - 1 0 6 e 6 ，一3 3 5 e 一7 ) ，最优值为f = 2 0 2 e 一1 2 问题2 m i n ，( z ) = x - 4 - 4 z + 4 。i + z ；， s t 一3 2 7 1 3 一3 z 2s3 函数问题的解为z + = ( 7 2 3 e 一8 ，一3 1 l e 一8 ) ，最优值为，+ = 2 4 6 e 一1 4 。 问题3 r a i ny ( 5 7 ) = 1 + 2 x 2 + c s i n ( 4 1 r x 2 ) 一x 1 2 + x 2 0 5 s i n ( 2 7 r x l ) 2 5t 0 x l 1 0 ， 1 0 z 2 0 其中c 为参数，取值为c = 0 5 此目标函数为二维函数。函数问题的解为 z + = ( 一0 0 2 1 4 8 8 ，- 0 1 4 6 5 2 3 ) ，最优值为f + = 0 0 6 7 0 9 7 1 问题4 丁l t 2 4 x ；+ 4 z ； 一3 z 。 3 此目标函数称之为 6 一h u m p c a m e l b a c k 函数，至少有四个最优点，两两关于原点对 称。利用第四章中的实现算法求得函数问题的解为z + = ( 0 0 8 9 8 4 2 ，0 7 1 2 6 5 6 4 ) ，最优值 6 1 ，铲。 卜 一 珩z 1 2 3 一 2 t 妇 s r 为f + = 1 0 3 1 6 2 8 2 6 参考文献 【1 b a r h e n ，j p r o t o p o p e s c u ，v a n dr e s i s t e r ，d ( 1 9 9 7 ) ，t r u s t ：ad e t e r m i n i s t i ca l g o r i t h mf o r g l o b a lo p t i m i z a t i o n ，s c i e n c e2 7 6 ，1 0 9 4 1 0 9 7 2 】b r a n i n ，f ( 1 9 7 2 ) ，w i d e l yc o n v e r g e n tm e t h o d s f o rf i n d i n gm u l t i p l es o l u t i o n so f s i m u l t a n e o u s n o n l i n e a re q u a t i o n s 工b mj o u r n a lo fr e s e a r c hd e v e l o p n e n t1 6 ：5 0 4 5 2 2 3 】c e t i n ，b + c ，b a r h e n ，j a n db u r d i c k ，j w ( 1 9 9 3 ) ，t e r m i n a lr e p e l l e ru n c o n s t r a i n e d s u b e n e r g yt u n n e l i n g ( t r u s t ) f o rf a s tg l o b a lo p t i m i z a t i o n ，j o u r n a lo fo p t i m i z a t i o na n d a p p l i c a t i o n s7 7 ，9 7 1 2 6 4 c v i j o v i d ，d a n dk l i n o w s k i ，j ( 1 9 9 5 ) ，t a b o os e a r c h ：a na p p r o a c h t ot h em u l t i p l em i n i m a p r o b l e m s c i e n c e2 6 7 ，6 6 4 6 6 6 5 】d p b e r t s e k a s ，n e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sf o rap e n a l t ym e t h o dt ob ee x a c t ， m a t h e m a t i c a lp r o g r a m m i n g9 ( 1 9 7 5 ) ，8 9 9 6 d i x o n ，l c w a n ds z e 9 7 0 ，g p ( e d s ) ( 1 9 7 5 ) ，t o w a r d sg l o b a lo p t i m i z a t