（运筹学与控制论专业论文）非线性全局优化的填充函数法(1).pdf

摘要 最优化是一门应用相当广泛的学科，它讨论决策问题的最优选择，构造寻求 最优解的计算方法并研究这些方法的理论性质及实际计算表现。由于社会的进步 和科学技术的发展，最优化问题广泛见于经济计划，工程设计，生产管理，交通运 输，国防军事等重要领域，因此受到高度重视。伴随着计算机的高速发展和最优化 工作者的努力，最优化的理论分析和计算方法得到了极大提高。 求解一般函数的全局最优解问题是热点课题之一。对全局最优化问题有两个 困难需要解决：一是如何从一个局部极小解出发找到更好的局部极小解，另一个 是全局最优解的判定问题。全局最优化算法，从算法的构造上大体可以分为确定 型算法和随机型算法。其中，填充函数法就是随之出现的一种确定型算法，它是解 决第一个困难的实用方法之一。 填充函数的主要思想是：如果已经找到了一个局部极小茁，但它不是全局最 小，我们可以在茁8 处构造一个填充函数使迭代点列离开z + 所在的谷域，找到更 好的点z ( 即处的目标函数值比矿处的目标函数值更小) 。然后以x 为初始点 极小化原问题找到更优的局部极小点。 填充函数法只需应用成熟的局部极小化算法，因此受到理论以及实际工作者 的欢迎。但是由于填充函数是目标函数的复合函数，且目标函数本身可能很复杂， 所以构造的填充函数形式也可能很复杂。再就是参数过多，难于调节。还有早期提 出的填充函数法是沿着线方向搜索方法，使得在实际计算时工作量很大。构造形 式简单以及较少参数的填充函数并使其具有好的性质，以便节约许多冗长的计算 步骤及调整参数的时间，提高算法的效率，是理论和实际工作者继续研究填充函 数的目的。 本论文的主要工作是：在已有填充函数算法的基础上，对三类连续全局最优 化问题尝试提出一些改进和创新。力图在算法效果方面有所提高，在理论方面有 所深化。其内容详细情况如下： 本文包含五章内容，第一章主要介绍了目前国内外主要的几种全局最优化问 题和算法，以及他们的特点。这包括：填充函数法、打洞函数法、分支定界法等。 i 对填充函数法，从算法的思想到相关理论给出了一些深入浅出的说明，在此基础 上，分析了各自的优缺点，为进一步的推广和构造新的填充函数法，提供一些指导 思想和思路。后面四章由四篇独立的文章组成。 第二章，对一般无约束连续全局最优化问题，在无李普希兹连续条件下，提出 了一个新的简单单参数填充函数。针对这个填充函数，设计了算法，对该算法进行 了有效的数值实验，并将该算法的结果与文献8 1 作了对比。结果表明，该算法是 有效的。第三章，对无约束连续全局最优化问题，也提出了一个有别于第二章的新 的单参数填充函数，针对这个填充函数，设计了两个算法，对这两个算法进行了数 值实验，并对这两个算法结果与第二章的算法结果进行了对比。结果表明，这两个 算法都是有效的。第四章，对一般酽空间中带有简单箱子约束全局最优化问题， 在无强制性条件下，提出了一个新的单参数填充函数，针对该填充函数，设计了一 个算法，对算法进行了大量的数值实验，并对数值结果与第三章的算法进行了详 细的对比，结果表明，该算法也是有效的。第五章把无约束全局最优化问题的思想 方法拓广到求解带有约束的非线性规划问题的全局最优化问题。在较弱的条件下。 在r “空间中，对于带有非线性不等式约束的全局优化问题给出了个单参数填 充函数，分析并证明了填充函数的性质，并对该填充函数设计了一个新算法。 关键词非线性规划全局最优化填充函数填充函数方法局部极小点全 局极小点 a b s t r a c t t h eo p t i m i z a t i o ni saw i d e l yu s e dd i s c i p l i n e ，w h i c hd i s c u s s e st h ec h a r a c t e r so f o p t i m a lc h o i c eo i ld e c i s i o np r o b l e m sa n dc o n s t r u c t sc o m p u t i n ga p p r o a c h e st of i n d t h eo p t i m a ls o l u t i o n d u et ot h ea d v a n c e m e n to fs o c i e t ya n dt h ed e v e l o p m e n t o fs c i e n c ea n dt e c h n o l o g y ，t h eo p t i m i z a t i o np r o b l e m sa r eo f t e nd i s c o v e r e di nt h e f i e l do fe c o n o m i cp l a n n i n ga d m i n i s t r a t i o n ，e n g i n e e r i n gd e s i g n ，p r o d u c t i o nm a n a g e m e n t ，t r a f f i ct r a n s p o r t a t i o n ，n a t i o n a ld e f e n c ea n ds oo n t h e ya r es oi m p o r t a n t t h a tm e e tw i t hm u c hr e c o g n i t i o n 。w i t ht h es p e e d yd e v e l o p m e n to fc o m p u t e ra n d t h eh a r dw o r ko fs c i e n t i s t s ，t h et h e o r e t i ca n a l y s i sa n dc o m p u t a t i o n a lm e t h o d so n o p t i m i z a t i o nh a v eb e e nh i g h l yi m p r o v e d t of i n dt h ee f f e c t i v em e t h o d sf o rf i n d i n gt h eg l o b a lo p t i m a ls o l u t i o n so fag e n e r a l m u l t i m i n i m i z e r sf u n c t i o ni so n eo ft h eh o tt o p i c s t h e r et w od i f f i c u l t i e si ng l o b a l o p t i m i z a t i o n o b ei sh o wt ol e a v ef r o mal o c a lm i n i m i z e rt oas m a l l e ro n ea n dt h e o t h e ri sh o wt oj u d g et h a tt h ec u r r e n tm i n i m i z e ri sg l o b a l g l o b a lo p t i m i z a t i o n m e t h o d sc a nb ec l a s s i f i e di n t ot w og r o u p s ：s t o c h a s t i ca n dd e t e r m i n i s t i cm e t h o d s t h ef i l l e df u n c t i o na l g o r i t h mi n t r o d u c e db yg ea n dq i n ( 1 9 8 7 ) i so n eo ft h ew e l l k n o w na u dp r a c t i c a lm e t h o d sf o rs e t t l i n gt h ef i r s td i f f i c u l t y 。t h em a i ni d e ao ff i l l e d f u n o t i o nm e t h o di s ：i fal o c a lm i n i m i z e rz + h a sb e e nf o u n d ，w ec a nm a k eaf i l l e d f u n c t i o n ，s u c ht h a ti t e r a t i v es e q u e n t i a lp o i n t sl e a v et h ev a l l e yi nw h i c hx + l i e st o f i n dab e t t e rp o i n t i nt h el o w e rv a l l e y ( i e f ( x ) 0 ，对于所有 满足忙一z + | | 墨e 的z s ，成立f ( x + ) ，( z ) ，而f ( x + ) 称为局部极小值。 定义1 1 2 x + es 称为一个全局极小点，如果对于所有z s ，成立f ( x 4 ) ，( 。) ，而f ( x + ) 称为全局极小值。 在全局最优化问题中，凸规划具有很好的性质，也就是当目标函数是凸的，可 行域也是凸的时候，凸规划的每个局部极小值就是全局极小值，所以我们可以应用 求局部极小点的方法，求得全局极小点，已有的局部极小化算法对它都是有效的。 而对于非凸的问题，可能存在很多局部极小点，其函数值不同于全局极小值，这样 就使我们在求解全局最优化问题时面临很多困难，所以我们要首先研究目标函数 在可行域s 上的局部和整体性质。为此，我们首先回顾些基本概念，下面的定义 和定理在大部分最优化的教材或文献上都有叙述和证明，可以参考f 1 ，2 ，9 ，3 0 ，5 4 1 。 定义1 1 3 函数f 在s 上的下确界，记作i n f s ( z ) ：。s ) ，是，在s 上 的最大下界；函数f 在s 上的上确界，记作s u p ，( z ) ：x s ，是厂在s 上的 2 上海大学博士学位论文 最小上界。 定义1 1 4 在sc 舻上的一个实值函数i 厂称为李普希兹函数，如果存在一 个常数l = l ( f ，s ) 0 ，使得对于所有茁】，如s ，有 ，( z 2 ) 一f ( x 1 ) sl i i x 2 3 c 1 其中l 称为李普希兹常数。 定理l 1 1 设sc 即是凸的，在包含s 的一个开集上连续可微，并且在 s 上具有有界的梯度，则f 在s 上是李普希兹函数，且李普希兹常数 l s u p i l v f ( x ) | | ：z s ) 定义1 1 5 sc 彤1 称为闭集，如果s 包含所有收敛点列 z ：) cs 的极限 点；scj r n 称为紧集，如果s 是闭的有界集。 由函数在紧集上的连续性，我们可以得到下列著名的魏尔斯特拉斯定理： 定理1 1 2 如果s 是r n 中一个非空紧集，f ( x ) 是s 上的连续函数，那么 ，( z ) 在s 上至少有一个全局极小( 极大) 点。 定义1 1 6 集合s 舻上定义的实值函数f 在s 上的点x 处称为下半 连续，如果有f ( x ) = l i m i n f f ( y ) ；f 在s 上的点z 处称为上半连续，如果有 f ( x ) = l i ms u p ，( ) 容易看出，函数在茁点处既下半连续，又上半连续，则它在z 点处连续。在 定理1 1 2 中如果将，的连续替换成下半连续( 上半连续) ，那么定理仍然成立。 定义1 1 7 在凸集e 上函数f 的上方图e p i ( f ) 表示为：e p i ( f ) = ( z ，r ) cxr ：r ，( 。) ) 。 在极小化问题和凸性的研究中，下半连续的表现形式和重要性与下面的结果 有关： 定理1 1 3 设s 是脚中一个非空闭集，厂是s 上任意一个函数，则下列条 件是等价的： 在s 上，是下半连续的。 2 对于每个o r ，l ( 。) = z s ：，( z ) o ) 是闭的。 3 在r ”+ 1 中，上方图e p i ( f ) 是闭集。 定义1 1 8 定义在r ”中的函数f ( x ) 称为强制的，如果有1 i mf ( x ) = + o 。 z | 1 t 。 3 上海大学博士学位论文 对于无约束最优化，其中s = 彤，若，是强制的，则全局极小点的存在性问 题可以借助定理1 1 2 来讨论。 定理1 1 4 若，( 茁) 是强制的，并且连续，则，( 岱) 在r “中至少有一个全局 极小点。 。 下面给出一些关于局部和全局极小点特征的结果。 定义1 1 9 向量d 胛称为点矿s 处的可行方向，如果存在a + 0 ，使 得对于每个0 a a ，有茁。+ a d s ( s 是问题的可行域) 。 令f 在点z + 的一个邻域内连续可微，并且令d 胛满足d t v f ( x + ) 0 ， 其中表示式d t v f ( x + ) 是在口+ 处沿方向d 的方向导数。对于固定x + 和d ，函数 f ( z + + a d ) 描述了f 沿射线 。= 。+ + a d ，a 0 ) 的情况。因为 ，( z + + a d ) = ，( z 4 ) + a d r v f ( x + + o a d ) ， 这里0 目 1 是某个确定的数。所咀d r v ( z + ) 0 ，使 得对于每个0 a i ，有，( + a d ) ，( 矿) 。也就是，可以沿方向d ，使f 局部 地下降。所以我们有如下定理： 定理1 1 5 假设函数f ( z ) 在一个包含sc 兄”的开集内连续可微。若z + s 是的一个局部极小点( 相对于s ) ，则对于每个可行方向d ，都有d t v f ( x ) 0 。 定义1 1 1 0 点z + s 称为平稳点，如果对于每一个可行方向d ，都有 d r v f ( z + ) 0 。 对于一般问题来说，平稳点并不一定是极小点，但是对于凸规划问题，我们有 下列定理： 定理1 1 6 若，是一个在包含s 的开集内连续可微的凸函数，并且s 是一 个凸集，则矿s 是一个全局极小点， - 3 且仅当矿是一个平稳点。 定理1 1 7 凸函数，：s - - + 咒( 其中s r ”是凸的) 的每一个局部极小点 也是全局极小点。 定义1 1 1 1 凸集s 边界上的点z 称为一个极点，如果不存在互异的两点 。1 ，z 2 s ，使得z = a 1 + ( 1 一a ) z 2 ，0 ，( z ：) ，存在一条从z 到z ： 的下降路径。 若。：是f ( z ) 的局部极大点，则一，扛) 在局部极小点z ：处的盆谷称为_ 厂( 。) 在局部极大点z ：的峰。 定3 ( 1 2 2 设z ；和x ；是函数f ( x ) 的两个不同的极小点。如果，( g ：) ，( z ；) ，则称在z ；处的盆谷b ；比z ：处的盆谷b ：低，或称研比垅高。 一般使用填充函数方法还要求假设1 2 ，2 或假设1 ，2 3 。 假设1 2 2 ，( z ) 只有有限个极小值点。 假设1 2 3 f ( x ) 只有有限个极小值。 孤立点z ：处盆谷目的半径定义为： r = 。i n f 忙一z i 如果f ( x ) 在x ：处的h e s s i a n 矩阵v 2 ，( z i ) 正定，则r 0 。 填充函数算法由两个阶段步组成极小化阶段和填充阶段。这两个阶段交替 使用直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法如 拟牛顿法拟牛顿方法 2 4 ，4 7 ，5 3 ，梯度投影法( 7 1 ，7 7 $ h 共轭梯度法 8 9 等，寻找目标 函数的一个局部极小值点x ：。然后进入第二阶段，主要思想是以当前极小点茁：为 基础定义一个填充函数，并利用它找到一z ? ，使得 f ( x ) 0 。 他们注意到这个函数存在如下缺点： 算法的成功与否，严重地依赖这两个参数，而且在算法执行之前我们不知道这 两个参数的合适取值，只有多次的实验爿有可能找到较好的选择。 由于受到指数项e x p ( 一! j 严) 的影响，当p 太小或忙一| | 太大时，p ( x ，矿) 和v p ( z ，z + ，) 变得很小，从而产生假的平稳点。 p ( x ，矿) 只在线上存在极小点，因此算法实现很困难。 x 为有界闭箱，事实上不是真正无约束全局极小化问题。 为了克服缺陷，葛和秦在【1 5 给出了七个填充函数： m ，琼w ) = 志唧( 一宇) ， g ( x ，x l ，r ，p ) = 一p 2 l o g r + ，( z ) 】一i i z x ；1 1 2 ， d ( x ，z ：，r ，p ) = 一p 2 l o g r + - ，( z ) 一i i z x i l l ， q ( x ，。：，a ) = 一 ，( z ) 一，( z ：) 】e x p ( a l l x 一。：1 1 2 ) ， q ( x ，x ：，a ) = 一【，( z ) 一，( z ：) e x p ( a l l x z ；i i ) ， v e ( x ，x ：，a ) = 一v f ( x ) 一2 a f ( x ) 一，( z ：) 】( z z ：) ， v 亩( z ，。+ 1 ，a ) = 一v f ( z ) 一4 ，( z ) 一，( 。i ) 】i ； j ；斋 他们指出后四个函数是较好的填充函数。l i u 在5 n ( 4 2 ( 2 0 0 1 ) 中给出一个克服以上 缺陷的填充函数： h ( x ，x 1 ，a ) 1 可再顶万厕 其中a 充分大。 葛和秦( 1 9 9 0 ) 在文【1 8 中提出了另一类关于前置点x 0 的填充函数，其定义为 1 4 上海大学博士学位论文 定义1 2 4 若x + l ( p ) ，则在s 。= x x ：f ( x + ) s 厂( z ) ) 上除了 x o s 1 是t ( x ，z + ) 的极小点外，不存在其他平稳点。 2 若是= z x ：f ( x ) 0 ，0 h 0 充分大。 之后l u c i d i _ 币1 p i c c i a l l i ( 2 0 0 2 ) 在文【4 5 l 中进行了更为深入的讨论。并给出了以 下填充函数： u ( x ，a ，h ) = 1 ( 1 i z x o i ) v ( a f ( x ) 一，( z ：) + 州) 这两个定义中都假定1 卸f ( x ) = + ，f c 2 ，且( p ) 的局部极小点的个数为有 l l x l i ( ) 。 限个。 在各种文章中对填充函数的定义有所不同。尤其在文献【1 6 j 的定义中，条件( 3 ) 是 很难实现的，已有很多文献做了改进。如张连生，n gc k ，【8 1 】等对填充函数的定 义进行了改进，设x ：是f ( x ) 的一个局部极小点： 定义1 2 5 函数p ( 茁，z ：) 称为，( z ) 在局部极小点茁：处的填充函数，如果满 足： ( 1 ) x 1 是p ( x ，z i ) 的一个严格局部极大点，( z ) 在点z ：处的盆谷研成为 p ( x ，z ：) 的峰的一部分。 ( 2 ) p ( 。，。：) 在比b ：高的盆谷里没有稳定点。 ( 3 ) 如果存在比研低的盆谷g ，则在z ”和。：的连线上极小化p ( x ，3 7 1 ) 得到极小点z 彤，其中，( z ；，6 ) 是在z ；的邻域，茁”( z ；，6 ) 。 并给出了一个性质较好的函数，如文献 8 1 1 中定义的 p ( z ，z ：，p ，芦) = ，( z ：) 一m i n f ( x ) ，( 。：) 一p l l z 一。：1 1 2 + “ m a x o ，f ( x ) 一，( z ：) 】 2 1 5 上海大学博士学位论文 该文章的另一特点是他们对填充函数的迭代搜索方法进行了详细的讨论，得到了计 算方法上的一些结论。进一步他们把改进后的填充函数用于求解非线性整数规划， 建立了一个近似算法，从而为求解非线性整数规划提供了一个途径。参见 4 4 ，7 9 等。 近来，【7 3 x 寸填充函数的定义又作了改进： 定义1 2 6 函数p ( 。，z ；) 称为f ( x ) 在局部极小点z i 处的填充函数，如果满 足? ( 1 ) 。：是p ( x ，。：) 的一个严格局部极犬点。 ( 2 ) 对任意的。s l ，有v p ( z ，z ：) 0 ，这里s 1 = zf ( x ) ，( z ：) ，t x z ：) ) 。 ( 3 ) 如果z ：不是全局极小点，那么p ( x ，2 c 1 ) 一定在= zf ( x ) o 和r 满足o r 0 z 0 为一个很小的数。 2 对任j 蕞x s 1 = z x ：，( z ) f ( x + ) ) ，v t ( x ，z + ) 0 3 若岛= z x ：f ( x ) 0 ，x o 譬x ，且对所有x x ，满足忙一x o i i 1 。 针对于函数f ( x ) = x s i n x 和它的一个局部极小点。4 = 0 ，下面给出它的修正 打洞函数图像( 见图1 2 2 ) 。 此外，文献i s 2 给出的既是填充函数又是变形打洞函数为 ! ! ! ! 丛蛐= ：坐：2 ! 塑 1 + 她z 4j 1 2 其中，双参数r 0 为较小的r f 数，p 0 为较大的正数。 t ( x ，z + ，r ) 2 可f 南邗 塑= 竺：! 1 1 + 击m a x ( o ，妇) 一，( ) + r ) + r ( m ；n ( o ，( z ) 一，( z + ) + r ) ) 其中，q 2 固定，单参数r 0 为较小的正数。 它们满足条件1 ，2 ，3 。很显然，上述两个函数满足 t ( x o ，x + ，r ，p ) = o 甘f ( x o ) 一f ( x + ) + r = 0 称它们为变形打洞函数。 其它的变形打洞函数： 丑( z ，z + ，n p ) = ( 1 + l i x z o | | 2 ) - l n ( 1 + p ( ，( z ) 一f ( x + ) + r ) 2 ) 上海大学博士学位论文 其中，双参数r 0 是较小的正数，p 0 是较大的正数，x o 隹x 。 疋( + ，r ) = 剐嚣糍臻并铲 其中，o l 3 固定，单参数r 0 是较小的数，z o x 。 1 2 6 积分水平集算法 1 9 7 8 年，郑权教授提出了求解函数全局优化的积分水平集算法。积分水平集 算法可以认为是利用了函数的整体性质，来解决全局最优化问题的，它不同于前 面介绍的各种方法。 考虑问题( 1 1 1 ) ，即： m i n ，( o ) s t z s 设x 是n 维欧氏空间，其中，：x _ r ，s 是x 的一个子集。我们作如下假设 假设1 2 4 ，在s 上是连续的。 假设1 2 5 存在一个实数c ，使得水平集 g c = f z r “：，( z ) 茎c ) 和s 的交集非空而且紧。 因此上述问题可归结为求c + ，使得 此时，令 c 4 娜r a 帆i n m ) h = s n 皿。0 ， 于是，在假设1 2 4 和假设1 2 5 t ，上述问题可以重新叙述为，求c 和+ 满足 ( p ) c m 删i n m ) ， h + = z s ：f ( x ) = c + ) 在此基础上，给出了问题( p ) 的全局最优化解的条件。 2 l 上海大学博士学位论文 定理1 2 3 在假设j 2 4 和假设25 下，如果( 凰) = 0 ，其中皿= z s ： i ( x ) c ) 0 ，p 是l e b e s g u e 测度，那么，c 就是，在s 上的全局极小值，吼 是全局极小值点的集合 定义1 2 7 设c c + = m i n ，( z ) ，令 m ( i ，c ) = 厕1 o s ( z ) d p ， 其中 凰= z s ：f ( x ) sc ) ， 称m ( i ，c ) 是函数f 在水平集也的均值。 定义1 2 8 设c c + = m i n ，( z ) ，令 w l c ) = 厕1 五，( 似) 一钟卢， 其中皿是水平集如上述定义，称( ，c ) 是函数f 在水平集h 。上的均方差。 定理1 2 4 对于问题( p ) ，下面几个性质是等价的： ( ) x + 使问题( p ) 的全局极小值点，c + = ，( z + ) 为相应的全局极小值。 ( 2 ) m ( f ，c ) = 0 ( ，) ( ，c ) = 0 在此基础上给出了积分方法的概念性算法，其详细叙述如下： 算法 1 _ 取2 9 0 s ，给定一个充分小的正数- c ，令c o = f ( z o ) ，峨。= 。s ：，( z ) c o ) ，k = 0 。 2 若弘( 凰。) = 0 ，则c k 为全局极小值，。为全局极小值点集，转6 。 3 计算均值 c k + l = 志j ：m2 而可八。m 且令h e = x s ：，( z ) 茎c k + 1 ) 。若c k 十l = c k ，则c k + 1 为全局极小值，皿 为全局极小值点集，转6 ；否则，转4 。 4 计算方差 v 肚志厶。( m ) 一c 咖- 5 若v f ，则令k ：= k + 1 ，转2 ；否则，转6 。 上海大学博士学位论文 6 令，+ = c k + l ，且h + = 皿。，终止。h + 为，( z ) 在s 中的近似全局极小值点 集，广为相应的近似全局极小值。 如果在上述算法中令e = 0 ，则迭代将无限的进行下去，我们可以得到两个单 调下降的点列 c ) 和 上k ) 。由于这两个点列均有界，故它们都收敛。令 矿2 恕c e 和 + = 熙凰。= n 皿。，0 0r k = l 则我们有下述收敛定理。 定理1 2 5 若 c 。) 为上述算法生成的序列，则c + 是问题( p ) 的全局极小 值，日+ 是全局极小值点集。 积分型求全局极小值算法在理论上给出了收敛性的证明，并且该算法仅需要 计算目标函数值，故适用于较大范围的全局最优问题。但在一般情况下，水平集是 无法得到的，故原始文献中的实际算法是通过m o n t e c a r l o 随机取点来缩小搜 索范围。 1 3全局优化中的随机算法简介 1 3 1 模拟退火法 模拟退火1 3 5 算法是一种随机算法，多用于复杂的组合优化和n p 一难问题。其 思想源于物理上的退火过程，数学上有”马尔可夫链”可以对它进行严格的描述。基 于马尔可夫过程理论，文献 3 8 】理论上证明模拟退火算法以概率1 收敛于全局最优 解。实际应用中许多参数需要调整，是一个启发式算法。 模拟退火算法基本思想如下。算法的研究对象是由一个参数集所确定的某种 配置。为了便于问题的分析，需要设计一个基于该配置的价格函数，( z ) ，于是对 配置的优化过程就转化为对，( z ) 的极小化过程，( z ) 的极小化过程模拟自然界 的退火过程，由个逐步冷却温度t e m p 来控制，对每一个温度值，尝试一定的 步骤，在每一个极小化步中，随机地选择一个新的配置并计算价格函数，这时如果 厂( z ) 的值疗小于以前的值 ，则选择新的配置方案；如果大于以前的值，则计算 2 3 上海大学博士学位论文 概率值：p r o b = e x p 一向k + t e m p ) ，这旱k 是玻尔滋曼常数，然后在( 0 ，1 ) 上产生随机数r a n d ，如果r a n d p r o b ，则选择新的配置方案，否则仍保留原方 案。重复这些步骤，直到系统冷却不再产生更好的配置为止。 模拟退火算法的数学模型可描述为：在给定邻域结构后，模拟退火过程是从一 个状态到另一个状态不断地随机游动。此过程可以用马尔可夫链来描述。当t 为一 确定值时，两个状态的转移概率定义为： l 吼( z ) a ：j ( t ) ， v j i 黝。卜 1 一兰g 冰川地崩 q 删 其中1 d i 表示为状态集合中状态的个数，g i j ( t ) 称为从i 到j 的产生概率。g i j ( t ) 表示在状态i 时，j 状态被选取的概率。a i j ( t ) 称为接受概率，a i 3 ( t ) 表示状态i 产生j 后，接受j 的概率。通常j 被选中的概率记为： 吲归f 煮篇 s z ， 而模拟退火算法中接受j 的概率为： a 埘c t ，2 ：。一 ，。，； ：；：；苫； c 。- s ， 由( 1 3 1 ) ，( 1 3 2 ) ，( 1 3 3 ) 组成模拟退火算法的主要模型。 模拟退火算法分为时齐算法和非时齐算法两类。从理论研究可以发现，按理 论要求达到平稳点分布来应用模拟退火算法是不可能的。时齐算法要求无穷步迭 而言，在可接受时间内达到满意解就可以了，现有的技术尚难保证模拟退火算法 得到全局最优解。详细内容可参见文献【3 8 等。 1 3 2 遗传算法 遗传算法是种全局随机优化算法，它借鉴生物界”适者生存”的自然选择思 想和自然遗传机制通过选择复制和遗传因子的作用2 5 ，使优化群体不断进化，最 上海大学博士学位论文 群体搜索。 针对次数的染色体( 编码) 进行操作，不需要依赖梯度信息。 只利用目标函数作为评优准则，无需其他专业领域知识。 使用随机规则，而不是确定规则进行搜索。 基于这些特点，遗传算法特别适合处理那些带有多参数，多变量，多目标和在多区 域但连通相交差的n p h a r d 问题。并且，在处理很多组合优化问题时，不需要很强 的技巧。同时遗传算法与其它的启发式算法有较好的兼容性。 遗传算法包括以下主要步骤。 1 ) 对优化问题的解进行编码。称一个解的编码为个染色体，组成编码的元素称 为基因。 2 1 适应函数的构造和应用。适应函数依据优化问题目标函数而定。当适应函数确 定以后，自然选择规律以适应函数值的大小决定的概率分布来确定哪些染色体适 应生存，哪些被淘汰。生存下来的染色体组成种群，生成可以繁衍下一代的群体。 3 ) 染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产 生。 4 ) 变异。新解产生过程中可能发生基因变异，使某些解的编码发生变化，使解有 更大的遍历性。 最优化问题的求解过程是从众多的解中找出最优的解。生物进化的适者生存 规律使得最具有生存能力的染色体以最大的可能生存。所以遗传算法可以在优化 问题中应用。在优化问题中，可能点的数目是通过选择，交叉和变异的方法产生。 在选择阶段，确认某些种群产生后代，交叉操作应用于一对选择的种群来产生后 代，变异则被作为后代的修正或保留的种群的修正。象模拟退火算法一样，这类算 法起源于求解组合优化问题，对连续优化问题的作用目前尚非常有限。至今没解 决的主要问题在于可能解的编码问题。关于编码问题的讨论有这样一个观点：虽然 遗传算法、模拟退火、禁忌搜索等，是具有通用性的全局最优算法，但如果不针对 问题设计算法，恐怕计算时间可能非常大。可以通过针对问题的了解，即抓住问题 的特征以换取节省时间，该观点已越来越被人们接受。具体内容可参见文献 6 6 o 上海大学博士学位论文 第二章一个简单单参数填充函数 在这一章罩，我们利用新的填充函数的定义，在无李普希兹连续条件下，对一 般无约束最优化问题提出了一个新的简单单参数填充函数。分析并证明了该填充 函数的性质，针对该填充函数，建立了一个新算法，对该算法进行了大量的数值实 验，并与文献8 1 1 的数值结果进行了详细的对比。对比结果表明，该填充函数法是 有效的。本章取材于 4 0 1 2 1 引言 很多自然科学，经济和工程学上的最新发展与进步都需要求解下面n 维多极 值点的数学规划问题： m i n f ( z ) ：x r “)( 2 1 ，1 ) 其中，：r n _ r 。因此全局优化问题的研究成为一个被高度关注的热点问题之一。 但是由于很可能在一个全局优化问题里有许多局部极小点，因此全局优化问题不 能简单的用通常意义下的求解目标函数局部极小的方法。这些多极小值点的函数 一般会导致两个比较困难的问题：一个是怎样离开一个局部极小点到一个更优的 局部极小点：第二个是怎样判断当前的极小点是否为全局最优解。 由第一章的介绍可知，填充函数法是解决第一个问题的较好的方法之一，本 章我们在原有填充函数法的基础上，给出另一个新的简单单参数填充函数。 本章，考虑如下无约束的全局极小化问题： m i nf ( x ) ( 2 1 2 ) s t z r ” 其中f ：r “- r 。 在本章中，我们首先给出与文献 7 3 , 1 f l 同的填充函数的定义。基于这个定义， 我们构造了一个新的简单的单参数填充函数，在无李普希兹连续的条件下，汪明 了函数满足填充函数的性质。根据填充函数的性质，设计了个算法，并将这个算 法的结果与文献 8 1 】的进行对比，结果表明，算法是有效的，同时也克服了一些原 填充函数法的缺点。 2 6 上海大学博士学位论文 考虑问题( 2 1 2 ) ，对本章作如下假设： 假设2 1 1 函数，( 茁) 是强制性的，也就是当i i = 1 i _ 十o 。时，有，( z ) _ + o 。 由假设2 1 1 ，我i f i n 推出，一定存在一个紧集xcr ”，它的内部包含了，( 叫 的所有全局极小点和函数值较小的局部极小点，而且可以认为目标函数在x 的 边界上的函数值大于在其内部的函数值，因此，问题( 2 1 2 ) 等价于下列问题： m i n ，( o ) s t 3 7 x ( 2 1 ，3 ) 假设2 1 2 问题俾j 驯的不同局部极小点的个数可以是无限的，但不同局部 极小值个数是有限的。 为了便于讨论问题，给出与文献 7 3 】相同的定义： 定义2 1 1 函数尸( 。，矿) 称为，( z ) 在局部极小点3 7 + 处的填充函数，如果满 足： ( 1 ) 。+ 是p ( z ，3 7 + ) 的一个严格局部极大点。 ( 2 ) 对任意的z 函，有、7 p ( x ，x + ) o ，这里矗= 忙j ( x ) f ( z + ) ，z x 矿 ) 。 ( 3 ) 如果z + 不是全局极小点，那么p ( z ，) 一定在s 2 = 。i ，( 。) o 是参数。 当参数p 0 充分大时，下面的几个定理表明函数f ( x ，p ) 是满足定 义2 1 1 的一个填充函数。 定理2 2 1 若x + l ( 尸) ，则3 2 + 是f ( z ，茁+ ，p ) 的一个严格局部极大点。 2 7 上海大学博士学位论文 证明由z + l ( p ) 及，( 。) 的连续知，存在着矿的一个邻域( z + ，矿) ，o - 0 使得对于任意的z ( 七+ ，且z z + 有f ( x ) f ( x + ) 及 r ( x ，z + ：p ) = 一| | z z + 1 1 2 0 ，有f ( x + ) f ( x ) 及 f ( x ，矿，p ) = - i i x 一茁+ | | 2 和v 2 f ( x ，z + ，p ) = 一2 e ， 这里e 是单位矩阵。因此，v 2 f ( x ，z + ，p ) 是负定的。从而，z + 是f ( x ，茁+ ，p ) 上的 一个孤立局部极大点且v f ( x ，z + ，p ) 0 对所有。n ( x + ，盯) 定理2 2 1 表明f ( x ，z + ，p ) 满足填充函数的性质( 1 ) 定理2 2 2 若z + l ( p ) ，则函数r ( x ，z + ，p ) 在s l = zi ，( z ) 兰( x + ) ，z x 扛) ) 上的梯度不等于零。 证明由f ( x + ) - ，( z - ) 口z 。x 8 ，有 f ( x l ，。4 ，p ) = 一i i z l 。+ l | 2 ，v f ( z 1